Brun sieve


In the field of number theory, the Brun 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 Ap denote the set of elements of A divisible by p and extend this to let Ad the intersection of the Ap for p dividing d, when d is a product of distinct primes from P. Further let A1 denote A itself. Let z be a positive real number and P denote the primes in P ≤ z. The object of the sieve is to estimate
We assume that |Ad | may be estimated by
where w is a multiplicative function and X = |A|. Let

Brun's pure sieve

This formulation is from , Theorem 6.1.2. With the notation as above, assume that
where C, D, E are constants.
Then
where b is any positive integer. In particular, if log z < c log x / log log x for a suitably small c, then

Applications

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