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.

References

• .