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, 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

:

We assume that |"A"_"d"| may be estimated by

:$leftvert\; A\_d\; ightvert\; =\; 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\}\; ight)\; .$

Brun's pure sieve

This formulation is from Cocojaru & 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" ;
*

where "C", "D", "E" are constants.

Then

:$S(A,P,z)\; =\; X\; cdot\; W(z)\; cdot\; left(\{1\; +\; Oleft(((log\; z)^\{-b\; log\; b\}\; ight)\}\; ight)\; +\; Oleft(z^\{b\; loglog\; z\}\; ight)\; .$

In particular, if log "z" &lt; "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.

References

*
*
*
*
*
*.