热门问题
时间线
聊天
视角
塞尔伯格筛法
来自维基百科,自由的百科全书
Remove ads
在数论中,塞尔伯格筛法(Selberg sieve)是一个用以估计满足特定条件的“筛选过的”正整数集大小的技巧,而这些条件一般都以同余表示。这筛法由阿特勒·塞尔伯格于1940年代发展。

描述
在筛法的术语中,塞尔伯格筛法是一种“组合筛法”,也就是一种透过小心应用容斥原理进行“筛选”的筛法。在此筛法中,塞尔伯格以一组针对问题最佳化的权重取代默比乌斯函数,而这可给出“筛选过的”的集合大小的上界。
设为不大于的正整数的集合,并假定为质数的集合,然后设是中可为中的质数整除的数组成的集合;此外,可设为中的不同质数的乘积,在这种状况下,可相应地定义为中可被整除的数的集合,并定义为本身。
设为任意实数,而为中不大于的质数的乘积,那这筛法的目标就是估计下式:
我们可以假定说可由下式估计:
其中是一个积性函数、是的元素个数。
另外,设是个由对进行默比乌斯反演所得到的函数,也就是说,且,其中是默比乌斯函数。
在这种状况下,设,就可得下列关系式:
其中是及的最小公倍数。
此外,的数值可由下式估计:
Remove ads
应用
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.
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads