Selberg sieve

In number theory, the Selberg sieve is a technique for estimating the size of "sifted sets" of positive integers which satisfy a set of conditions which are expressed by congruences. It was developed by Atle Selberg in the 1940s.

Atle Selberg

Description

In terms of sieve theory the Selberg sieve is of combinatorial type: that is, derives from a careful use of the inclusion–exclusion principle. Selberg replaced the values of the Möbius function which arise in this by a system of weights which are then optimised to fit the given problem. The result gives an upper bound for the size of the sifted set.

Let $A$ be a set of positive integers $\leq x$ and let $P$ be a set of primes. Let $A_{d}$ denote the set of elements of $A$ divisible by $d$ when $d$ is a product of distinct primes from $P$. Further let $A_{1}$ denote $A$ itself. Let $z$ be a positive real number and $P(z)$ denote the product of the primes in $P$ which are $\leq z$. The object of the sieve is to estimate

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

We assume that |A_d| may be estimated by

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

where f is a multiplicative function and X   =   |A|. Let the function g be obtained from f by Möbius inversion, that is

$g(n)=\sum _{d\mid n}\mu (d)f(n/d)$

$f(n)=\sum _{d\mid n}g(d)$

where μ is the Möbius function. Put

$V(z)=\sum _{\begin{smallmatrix}d<z\\d\mid P(z)\end{smallmatrix}}{\frac {1}{g(d)}}.$

Then

$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)$

where $[d_{1},d_{2}]$ denotes the least common multiple of $d_{1}$ and $d_{2}$. It is often useful to estimate $V(z)$ by the bound

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

Applications

• The Brun–Titchmarsh theorem on the number of primes in arithmetic progression;
• The number of n ≤ x such that n is coprime to φ(n) is asymptotic to e^−γ x / log log log (x) .

References

• Cojocaru, Alina Carmen; Murty, M. Ram (2005). An introduction to sieve methods and their applications. London Mathematical Society Student Texts. Vol. 66. Cambridge University Press. pp. 113–134. ISBN 0-521-61275-6. Zbl 1121.11063.
• Diamond, Harold G.; Halberstam, Heini (2008). A Higher-Dimensional Sieve Method: with Procedures for Computing Sieve Functions. Cambridge Tracts in Mathematics. Vol. 177. With William F. Galway. Cambridge: Cambridge University Press. ISBN 978-0-521-89487-6. Zbl 1207.11099.
• Greaves, George (2001). Sieves in number theory. Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. Vol. 43. Berlin: Springer-Verlag. ISBN 3-540-41647-1. Zbl 1003.11044.
• Halberstam, Heini; Richert, H.E. (1974). Sieve Methods. London Mathematical Society Monographs. Vol. 4. Academic Press. ISBN 0-12-318250-6. Zbl 0298.10026.
• Hooley, Christopher (1976). Applications of sieve methods to the theory of numbers. Cambridge Tracts in Mathematics. Vol. 70. Cambridge University Press. pp. 7–12. ISBN 0-521-20915-3. Zbl 0327.10044.
• Selberg, Atle (1947). "On an elementary method in the theory of primes". Norske Vid. Selsk. Forh. Trondheim. 19: 64–67. ISSN 0368-6302. Zbl 0041.01903.