In the field of number theory, the Brun sieve (also called Brun's pure 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 Viggo Brun in 1915 and later generalized to the fundamental lemma of sieve theory by others.

Description

edit

In terms of sieve theory the Brun sieve is of combinatorial type; that is, it derives from a careful use of the inclusion–exclusion principle.

Let   be a finite set of positive integers. Let   be some set of prime numbers. For each prime   in  , let   denote the set of elements of   that are divisible by  . This notation can be extended to other integers   that are products of distinct primes in  . In this case, define   to be the intersection of the sets   for the prime factors   of  . Finally, define   to be   itself. Let   be an arbitrary positive real number. The object of the sieve is to estimate:  

where the notation   denotes the cardinality of a set  , which in this case is just its number of elements. Suppose in addition that   may be estimated by   where   is some multiplicative function, and   is some error function. Let  

Brun's pure sieve

edit

This formulation is from Cojocaru & Murty, Theorem 6.1.2. With the notation as above, suppose that

  •   for any squarefree   composed of primes in  ;
  •   for all   in  ;
  • There exist constants   such that, for any positive real number  ,  

Then  

where   is the cardinal of  ,   is any positive integer and the   invokes big O notation. In particular, letting   denote the maximum element in  , if   for a suitably small  , then  

Applications

edit
  • Brun's theorem: the sum of the reciprocals of the twin primes converges;
  • Schnirelmann's theorem: every even number is a sum of at most   primes (where   can be taken to be 6);
  • There are infinitely many pairs of integers differing by 2, where each of the member of the pair is the product of at most 9 primes;
  • Every even number is the sum of two numbers each of which is the product of at most 9 primes.

The last two results were superseded by Chen's theorem, and the second by Goldbach's weak conjecture ( ).

References

edit
  • Viggo Brun (1915). "Über das Goldbachsche Gesetz und die Anzahl der Primzahlpaare". Archiv for Mathematik og Naturvidenskab. B34 (8).
  • Viggo Brun (1919). "La série   où les dénominateurs sont "nombres premiers jumeaux" est convergente ou finie". Bulletin des Sciences Mathématiques. 43: 100–104, 124–128. JFM 47.0163.01.
  • Alina Carmen Cojocaru; M. Ram Murty (2005). An introduction to sieve methods and their applications. London Mathematical Society Student Texts. Vol. 66. Cambridge University Press. pp. 80–112. ISBN 0-521-61275-6.
  • George Greaves (2001). Sieves in number theory. Ergebnisse der Mathematik und ihrer Grenzgebiete (3. Folge). Vol. 43. Springer-Verlag. pp. 71–101. 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. ISBN 0-521-20915-3..