Selberg sieve explained

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.

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 \le 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 \le z . The object of the sieve is to estimateS(A,P,z) = \left\vert A \setminus c up _{p} A _{p} \right\vert .

We assume that |A_d| may be estimated by

\left\vert A _{d} \right\vert = (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} \mu(d) f(n/d) f(n) = \sum _{d} g(d)

where μ is the Möbius function. Put

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

Then

S(A,P,z) \le (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 boundV(z) \ge \sum _{d} (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

• Book: Alina Carmen . Cojocaru. Alina Carmen Cojocaru . M. Ram . Murty . M. Ram Murty . An introduction to sieve methods and their applications . London Mathematical Society Student Texts . 66 . Cambridge University Press . 0-521-61275-6 . 113–134 . 2005 . 1121.11063 .
• Book: Diamond . Harold G. . Halberstam . Heini . Heini Halberstam . With William F. Galway . A Higher-Dimensional Sieve Method: with Procedures for Computing Sieve Functions . Cambridge Tracts in Mathematics . 177 . Cambridge University Press . Cambridge . 2008 . 978-0-521-89487-6 . 1207.11099 .
• Book: Greaves, George . Sieves in number theory . Springer-Verlag . 2001 . 3-540-41647-1 . 1003.11044 . Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge . 43 . Berlin .
• Book: Heini . Halberstam . Heini Halberstam . H.E. . Richert . Hans-Egon Richert . Sieve Methods . Academic Press . 1974 . 0-12-318250-6 . 0298.10026 . London Mathematical Society Monographs . 4 .
• Book: Hooley, Christopher . Christopher Hooley

. Christopher Hooley . Applications of sieve methods to the theory of numbers . Cambridge University Press . 1976 . 0-521-20915-3. 7–12 . 0327.10044 . Cambridge Tracts in Mathematics . 70 .

• Atle . Selberg . Atle Selberg . On an elementary method in the theory of primes . Norske Vid. Selsk. Forh. Trondheim . 19 . 1947 . 64–67 . 0041.01903 . 0368-6302 .