塞尔伯格筛法

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

阿特勒·塞尔伯格

描述

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

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

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

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

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

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

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

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

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

${\displaystyle 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)}$

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

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

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

应用

• 算数数列中的质数（英语：primes in arithmetic progression）相关问题上的布朗-第区马许定理。
• 不大于${\displaystyle x}$且与欧拉函数${\displaystyle \varphi (n)}$互质的${\displaystyle n}$的数量，与${\displaystyle {\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.