Selberg sieve

Atle Selberg

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)=\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 {\mu ^{2}(d)}{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).

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. 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. 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. 43. Berlin: Springer-Verlag. ISBN 3-540-41647-1. Zbl 1003.11044.
Halberstam, Heini; Richert, H.E. (1974). Sieve Methods. London Mathematical Society Monographs. 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. 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.

This article is issued from Wikipedia - version of the 7/12/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.