塞尔伯格筛法

阿特勒·塞尔伯格

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

描述

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

设$A$为不大于$x$的正整数的集合，并假定$P$为质数的集合，然后设$A_{p}$是$A$中可为$P$中的质数$p$整除的数组成的集合；此外，可设$d$为$P$中的不同质数的乘积，在这种状况下，可相应地定义$A_{d}$为$A$中可被$d$整除的数的集合，并定义$A_{1}$为$A$本身。

设$z$为任意实数，而$P(z)$为$P$中不大于$z$的质数的乘积，那这筛法的目标就是估计下式：

$S(A,P,z)=\left\vert A\setminus \bigcup _{p\mid P(z)}A_{p}\right\vert .$

我们可以假定说$\left|A_{d}\right|$可由下式估计：

$\left\vert A_{d}\right\vert ={\frac {1}{f(d)}}X+R_{d}.$

其中$f$是一个积性函数、$X$是$A$的元素个数。

另外，设$g$是个由对$f$进行默比乌斯反演所得到的函数，也就是说，$g(n)=\sum _{d\mid n}\mu (d)f(n/d)$且$f(n)=\sum _{d\mid n}g(d)$，其中$\mu$是默比乌斯函数。

在这种状况下，设$V(z)=\sum _{\begin{smallmatrix}d<z\\d\mid P(z)\end{smallmatrix}}{\frac {1}{g(d)}}.$，就可得下列关系式：

$S(A,P,z)\leq {\frac {X}{V(z)}}+O\left({\sum _{\begin{smallmatrix}d_{1},d_{2}<z\\d_{1},d_{2}\mid P(z)\end{smallmatrix}}\left\vert R_{[d_{1},d_{2}]}\right\vert }\right)$

其中$[d_{1},d_{2}]$是$d_{1}$及$d_{2}$的最小公倍数。

此外，$V(z)$的数值可由下式估计：

$V(z)\geq \sum _{d\leq z}{\frac {1}{f(d)}}.\,$

应用

• 算数数列中的质数相关问题上的布朗-第区马许定理。
• 不大于$x$且与欧拉函数$\varphi (n)$互质的$n$的数量，与${\frac {e^{-\gamma }}{\log {\log {\log {(x)}}}}}$呈现非病态的（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.