Brun sieve

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.

Description

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 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 primes in P ≤ z. The object of the sieve is to estimate

S(A,P,z)=\left\vert A\setminus \bigcup _{{p\in P(z)}}A_{p}\right\vert .

We assume that |A_d| may be estimated by

\left\vert A_{d}\right\vert ={\frac {w(d)}{d}}X+R_{d}

where w is a multiplicative function and X = |A|. Let

W(z)=\prod _{{p\in P(z)}}\left(1-{\frac {w(p)}{p}}\right).

Brun's pure sieve

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

|R_d| ≤ w(d) for any squarefree d composed of primes in P ;
w(p) < C for all p in P ;
$\sum _{{p\in P_{z}}}{\frac {w(p)}{p}}<D\log \log z+E;$

where C, D, E are constants.

Then

S(A,P,z)=X\cdot W(z)\cdot \left({1+O\left((\log z)^{{-b\log b}}\right)}\right)+O\left(z^{{b\log \log z}}\right)

where b is any positive integer. In particular, if log z < c log x / log log x for a suitably small c, then

S(A,P,z)=X\cdot W(z)(1+o(1)).\,

Applications

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 C primes (where C 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 (C = 3).

References

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 1/5+1/7+1/11+1/13+1/17+1/19+1/29+1/31+1/41+1/43+1/59+1/61+..., où les dénominateurs sont nombres premiers jumeaux est convergente ou finie". Bulletin des Sciences Mathématiques. 43: 100–104, 124–128.
Alina Carmen Cojocaru; M. Ram Murty (2005). An introduction to sieve methods and their applications. London Mathematical Society Student Texts. 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). 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. .

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