fbpx
维基百科

塞尔伯格筛法

數論中,塞爾伯格篩法(Selberg sieve)是一個用以估計滿足特定條件的「篩選過的」正整數集大小的技巧,而這些條件一般都以同餘表示。這篩法由阿特勒·塞爾伯格於1940年代發展。

阿特勒·塞爾伯格

描述 编辑

篩法的術語中,塞爾伯格篩法是一種「組合篩法」,也就是一種透過小心應用容斥原理進行「篩選」的篩法。在此篩法中,塞爾伯格以一組針對問題最佳化的權重取代默比烏斯函數,而這可給出「篩選過的」的集合大小的上界。

 為不大於 的正整數的集合,並假定 為質數的集合,然後設  中可為 中的質數 整除的數組成的集合;此外,可設  中的不同質數的乘積,在這種狀況下,可相應地定義  中可被 整除的數的集合,並定義  本身。

 為任意實數,而  中不大於 的質數的乘積,那這篩法的目標就是估計下式:

 

我們可以假定說 可由下式估計:

 

其中 是一個積性函數  的元素個數。

另外,設 是個由對 進行默比烏斯反演所得到的函數,也就是說,  ,其中 默比烏斯函數

在這種狀況下,設 ,就可得下列關係式:

 

其中   最小公倍數

此外, 的數值可由下式估計:

 

應用 编辑

  • 算數數列中的質數英语primes in arithmetic progression相關問題上的布朗—第區馬許定理英语Brun–Titchmarsh theorem
  • 不大於 且與歐拉函數 互質的 的數量,與 呈現非病態的(asymptotic)關係。

參考資料 编辑

  • Cojocaru, Alina Carmen; Murty, M. Ram. An introduction to sieve methods and their applications. London Mathematical Society Student Texts 66. Cambridge University Press. 2005: 113–134. ISBN 0-521-61275-6. Zbl 1121.11063. 
  • Diamond, Harold G.; Halberstam, Heini. A Higher-Dimensional Sieve Method: with Procedures for Computing Sieve Functions. Cambridge Tracts in Mathematics 177. With William F. Galway. Cambridge: Cambridge University Press. 2008. ISBN 978-0-521-89487-6. Zbl 1207.11099. 
  • Greaves, George. Sieves in number theory. Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge 43. Berlin: Springer-Verlag. 2001. ISBN 3-540-41647-1. Zbl 1003.11044. 
  • Halberstam, Heini; Richert, H.E. Sieve Methods. London Mathematical Society Monographs 4. Academic Press. 1974. ISBN 0-12-318250-6. Zbl 0298.10026. 
  • Hooley, Christopher. Applications of sieve methods to the theory of numbers. Cambridge Tracts in Mathematics 70. Cambridge University Press. 1976: 7–12. ISBN 0-521-20915-3. Zbl 0327.10044. 
  • Selberg, Atle. On an elementary method in the theory of primes. Norske Vid. Selsk. Forh. Trondheim. 1947, 19: 64–67. ISSN 0368-6302. Zbl 0041.01903. 

塞尔伯格筛法, 在數論中, 塞爾伯格篩法, selberg, sieve, 是一個用以估計滿足特定條件的, 篩選過的, 正整數集大小的技巧, 而這些條件一般都以同餘表示, 這篩法由阿特勒, 塞爾伯格於1940年代發展, 阿特勒, 塞爾伯格描述, 编辑在篩法的術語中, 塞爾伯格篩法是一種, 組合篩法, 也就是一種透過小心應用容斥原理進行, 篩選, 的篩法, 在此篩法中, 塞爾伯格以一組針對問題最佳化的權重取代默比烏斯函數, 而這可給出, 篩選過的, 的集合大小的上界, 設a, displaystyle, nbsp, . 在數論中 塞爾伯格篩法 Selberg sieve 是一個用以估計滿足特定條件的 篩選過的 正整數集大小的技巧 而這些條件一般都以同餘表示 這篩法由阿特勒 塞爾伯格於1940年代發展 阿特勒 塞爾伯格描述 编辑在篩法的術語中 塞爾伯格篩法是一種 組合篩法 也就是一種透過小心應用容斥原理進行 篩選 的篩法 在此篩法中 塞爾伯格以一組針對問題最佳化的權重取代默比烏斯函數 而這可給出 篩選過的 的集合大小的上界 設A displaystyle A nbsp 為不大於x displaystyle x nbsp 的正整數的集合 並假定P displaystyle P nbsp 為質數的集合 然後設A p displaystyle A p nbsp 是A displaystyle A nbsp 中可為P displaystyle P nbsp 中的質數p displaystyle p nbsp 整除的數組成的集合 此外 可設d displaystyle d nbsp 為P displaystyle P nbsp 中的不同質數的乘積 在這種狀況下 可相應地定義A d displaystyle A d nbsp 為A displaystyle A nbsp 中可被d displaystyle d nbsp 整除的數的集合 並定義A 1 displaystyle A 1 nbsp 為A displaystyle A nbsp 本身 設z displaystyle z nbsp 為任意實數 而P z displaystyle P z nbsp 為P displaystyle P nbsp 中不大於z displaystyle z nbsp 的質數的乘積 那這篩法的目標就是估計下式 S A P z A p P z A p displaystyle S A P z left vert A setminus bigcup p mid P z A p right vert nbsp 我們可以假定說 A d displaystyle left A d right nbsp 可由下式估計 A d 1 f d X R d displaystyle left vert A d right vert frac 1 f d X R d nbsp 其中f displaystyle f nbsp 是一個積性函數 X displaystyle X nbsp 是A displaystyle A nbsp 的元素個數 另外 設g displaystyle g nbsp 是個由對f displaystyle f nbsp 進行默比烏斯反演所得到的函數 也就是說 g n d n m d f n d displaystyle g n sum d mid n mu d f n d nbsp 且f n d n g d displaystyle f n sum d mid n g d nbsp 其中m displaystyle mu nbsp 是默比烏斯函數 在這種狀況下 設V z d lt z d P z 1 g d displaystyle V z sum begin smallmatrix d lt z d mid P z end smallmatrix frac 1 g d nbsp 就可得下列關係式 S A P z X V z O d 1 d 2 lt z d 1 d 2 P z R d 1 d 2 displaystyle S A P z leq frac X V z O left sum begin smallmatrix d 1 d 2 lt z d 1 d 2 mid P z end smallmatrix left vert R d 1 d 2 right vert right nbsp 其中 d 1 d 2 displaystyle d 1 d 2 nbsp 是d 1 displaystyle d 1 nbsp 及d 2 displaystyle d 2 nbsp 的最小公倍數 此外 V z displaystyle V z nbsp 的數值可由下式估計 V z d z 1 f d displaystyle V z geq sum d leq z frac 1 f d nbsp 應用 编辑算數數列中的質數 英语 primes in arithmetic progression 相關問題上的布朗 第區馬許定理 英语 Brun Titchmarsh theorem 不大於x displaystyle x nbsp 且與歐拉函數f n displaystyle varphi n nbsp 互質的n displaystyle n nbsp 的數量 與e g log log log x displaystyle frac e gamma log log log x nbsp 呈現非病態的 asymptotic 關係 參考資料 编辑Cojocaru Alina Carmen Murty M Ram An introduction to sieve methods and their applications London Mathematical Society Student Texts 66 Cambridge University Press 2005 113 134 ISBN 0 521 61275 6 Zbl 1121 11063 Diamond Harold G Halberstam Heini A Higher Dimensional Sieve Method with Procedures for Computing Sieve Functions Cambridge Tracts in Mathematics 177 With William F Galway Cambridge Cambridge University Press 2008 ISBN 978 0 521 89487 6 Zbl 1207 11099 Greaves George Sieves in number theory Ergebnisse der Mathematik und ihrer Grenzgebiete 3 Folge 43 Berlin Springer Verlag 2001 ISBN 3 540 41647 1 Zbl 1003 11044 Halberstam Heini Richert H E Sieve Methods London Mathematical Society Monographs 4 Academic Press 1974 ISBN 0 12 318250 6 Zbl 0298 10026 Hooley Christopher Applications of sieve methods to the theory of numbers Cambridge Tracts in Mathematics 70 Cambridge University Press 1976 7 12 ISBN 0 521 20915 3 Zbl 0327 10044 Selberg Atle On an elementary method in the theory of primes Norske Vid Selsk Forh Trondheim 1947 19 64 67 ISSN 0368 6302 Zbl 0041 01903 取自 https zh wikipedia org w index php title 塞尔伯格筛法 amp oldid 77150048, 维基百科,wiki,书籍,书籍,图书馆,

文章

,阅读,下载,免费,免费下载,mp3,视频,mp4,3gp, jpg,jpeg,gif,png,图片,音乐,歌曲,电影,书籍,游戏,游戏。