在数论 中，塞尔伯格筛法 （Selberg sieve）是一个用以估计满足特定条件的“筛选过的”正整数 集大小的技巧，而这些条件一般都以同余 表示。这筛法由阿特勒·塞尔伯格 于1940年代发展。
阿特勒·塞尔伯格 描述
在筛法 的术语中，塞尔伯格筛法是一种“组合筛法”，也就是一种透过小心应用容斥原理 进行“筛选”的筛法。在此筛法中，塞尔伯格以一组针对问题最佳化的权重取代默比乌斯函数 ，而这可给出“筛选过的”的集合大小的上界。
设
A
{\displaystyle A}
x
{\displaystyle x}
P
{\displaystyle P}
A
p
{\displaystyle A_{p}}
A
{\displaystyle A}
P
{\displaystyle P}
p
{\displaystyle p}
d
{\displaystyle d}
P
{\displaystyle P}
A
d
{\displaystyle A_{d}}
A
{\displaystyle A}
d
{\displaystyle d}
A
1
{\displaystyle A_{1}}
A
{\displaystyle A}
设
z
{\displaystyle z}
P
(
z
)
{\displaystyle P(z)}
P
{\displaystyle P}
z
{\displaystyle z}
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 .}
我们可以假定说
|
A
d
|
{\displaystyle \left|A_{d}\right|}
|
A
d
|
=
1
f
(
d
)
X
+
R
d
.
{\displaystyle \left\vert A_{d}\right\vert ={\frac {1}{f(d)}}X+R_{d}.}
其中
f
{\displaystyle f}
积性函数 、
X
{\displaystyle X}
A
{\displaystyle A}
另外，设
g
{\displaystyle g}
f
{\displaystyle f}
默比乌斯反演 所得到的函数，也就是说，
g
(
n
)
=
∑
d
∣
n
μ
(
d
)
f
(
n
/
d
)
{\displaystyle g(n)=\sum _{d\mid n}\mu (d)f(n/d)}
f
(
n
)
=
∑
d
∣
n
g
(
d
)
{\displaystyle f(n)=\sum _{d\mid n}g(d)}
μ
{\displaystyle \mu }
默比乌斯函数 。
在这种状况下，设
V
(
z
)
=
∑
d
<
z
d
∣
P
(
z
)
1
g
(
d
)
.
{\displaystyle V(z)=\sum _{\begin{smallmatrix}d<z\\d\mid P(z)\end{smallmatrix}}{\frac {1}{g(d)}}.}
S
(
A
,
P
,
z
)
≤
X
V
(
z
)
+
O
(
∑
d
1
,
d
2
<
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}<z\\d_{1},d_{2}\mid P(z)\end{smallmatrix}}\left\vert R_{[d_{1},d_{2}]}\right\vert }\right)}
其中
[
d
1
,
d
2
]
{\displaystyle [d_{1},d_{2}]}
d
1
{\displaystyle d_{1}}
d
2
{\displaystyle d_{2}}
最小公倍数 。
此外，
V
(
z
)
{\displaystyle V(z)}
V
(
z
)
≥
∑
d
≤
z
1
f
(
d
)
.
{\displaystyle V(z)\geq \sum _{d\leq z}{\frac {1}{f(d)}}.\,}
应用
算数数列中的质数 布朗-第区马许定理 。不大于
x
{\displaystyle x}
欧拉函数
φ
(
n
)
{\displaystyle \varphi (n)}
n
{\displaystyle n}
e
−
γ
log
log
log
(
x
)
{\displaystyle {\frac {e^{-\gamma }}{\log {\log {\log {(x)}}}}}}
参考资料
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-6Zbl 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-6Zbl 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-1Zbl 1003.11044 Halberstam, Heini ; Richert, H.E. Sieve Methods. London Mathematical Society Monographs 4 . Academic Press. 1974. ISBN 0-12-318250-6Zbl 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-3Zbl 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 
![{\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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/49f19de32de2d21f372487b183926a623ddb9e22)
![{\displaystyle [d_{1},d_{2}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/941f84148c54933db2f70ce734e063b703bb9f0c)
