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

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 finite set of positive integers. Let P be some set of prime numbers. For each prime p in P, let A_p denote the set of elements of A that are divisible by p. This notation can be extended to other integers d that are products of distinct primes in P. In this case, define A_d to be the intersection of the sets A_p for the prime factors p of d. Finally, define A_1 to be A itself. Let z be an arbitrary positive real number. The object of the sieve is to estimate: where the notation |X| denotes the cardinality of a set X, which in this case is just its number of elements. Suppose in addition that |A_d| may be estimated by where w is some multiplicative function, and R_d is some error function. Let

Brun's pure sieve

This formulation is from Cojocaru & Murty, Theorem 6.1.2. With the notation as above, suppose that Then where X is the cardinal of A, b is any positive integer and the O invokes big O notation. In particular, letting x denote the maximum element in A, if 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 (C=3).