Selberg sieve

In mathematics, in the field of 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.

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 ≤ x and let P be a set of primes. For each p in P, let A_p denote the set of elements of A divisible by p and extend this to let A_d the intersection of the A_p for p dividing d, when d is a product of distinct primes from P. Further let A₁ denote A itself. Let z be a positive real number and P(z) denote the product of the primes in P which are ≤ z. The object of the sieve is to estimate

$S(A,P,z)=|A\setminus \bigcup _{p\in P(z)}{A}_p|.$

We assume that |A_d| may be estimated by

$\left|A_d\right|=\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{array}{c}d<z\\ d\mid P(z)\end{array}}\frac{{\mu }^2(d)}{g(d)}.$

Then

$S(A,P,z)\le \frac{X}{V(z)}+O\left(\sum _{\begin{array}{c}{d}_1,d_2<z\\ d_1,d_2\mid P(z)\end{array}}\left|R_{[d_1,d_2]}\right|\right).$

It is often useful to estimate V(z) by the bound

$V(z)\ge \sum _{d\le z}\frac{1}{f(d)}.$

Applications

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

References

• Alina Carmen Cojocaru; M. Ram Murty. An introduction to sieve methods and their applications. London Mathematical Society Student Texts. 66. Cambridge University Press. pp. 113-134. ISBN 0-521-61275-6. 
• George Greaves (2001). Sieves in number theory. Springer-Verlag. ISBN 3-540-41647-1. 
• Heini Halberstam; H.E. Richert (1974). Sieve Methods. Academic Press. ISBN 0-12-318250-6. 
• Christopher Hooley (1976). Applications of sieve methods to the theory of numbers. Cambridge University Press. pp. 7-12. ISBN 0-521-20915-3. 
• Atle Selberg (1947). "On an elementary method in the theory of primes". Norske Vid. Selsk. Forh. Trondheim 19: 64-67.