热门问题
时间线
聊天
视角

塞尔伯格筛法

来自维基百科,自由的百科全书

塞尔伯格筛法
Remove ads

数论中,塞尔伯格筛法(Selberg sieve)是一个用以估计满足特定条件的“筛选过的”正整数集大小的技巧,而这些条件一般都以同余表示。这筛法由阿特勒·塞尔伯格于1940年代发展。

Thumb
阿特勒·塞尔伯格

描述

筛法的术语中,塞尔伯格筛法是一种“组合筛法”,也就是一种透过小心应用容斥原理进行“筛选”的筛法。在此筛法中,塞尔伯格以一组针对问题最佳化的权重取代默比乌斯函数,而这可给出“筛选过的”的集合大小的上界。

为不大于的正整数的集合,并假定为质数的集合,然后设中可为中的质数整除的数组成的集合;此外,可设中的不同质数的乘积,在这种状况下,可相应地定义中可被整除的数的集合,并定义本身。

为任意实数,而中不大于的质数的乘积,那这筛法的目标就是估计下式:

我们可以假定说可由下式估计:

其中是一个积性函数的元素个数。

另外,设是个由对进行默比乌斯反演所得到的函数,也就是说,,其中默比乌斯函数

在这种状况下,设,就可得下列关系式:

其中最小公倍数

此外,的数值可由下式估计:

Remove ads

应用

  • 算数数列中的质数相关问题上的布朗-第区马许定理
  • 不大于且与欧拉函数互质的的数量,与呈现非病态的(asymptotic)关系。
Remove ads

参考资料

  • 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.
Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads