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

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

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.