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 edit
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 be a set of positive integers and let be a set of primes. Let denote the set of elements of divisible by when is a product of distinct primes from . Further let denote itself. Let be a positive real number and denote the product of the primes in which are . The object of the sieve is to estimate
We assume that |Ad| may be estimated by
where f is a multiplicative function and X = |A|. Let the function g be obtained from f by Möbius inversion, that is
where μ is the Möbius function. Put
Then
where denotes the least common multiple of and . It is often useful to estimate by the bound
Applications edit
- 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 edit
- 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.