# 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 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:

$S(A,P,z)={\biggl \vert }A\setminus \bigcup _{p\in P \atop p\leq z}A_{p}{\biggr \vert },$

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

$\left\vert A_{d}\right\vert ={\frac {w(d)}{d}}|A|+R_{d},$

where $w$  is some multiplicative function, and $R_{d}$  is some error function. Let
$W(z)=\prod _{p\in P \atop p\leq 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, suppose that

• $|R_{d}|\leq w(d)$  for any squarefree $d$  composed of primes in $P$ ;
• $w(p)  for all $p$  in $P$ ;
• There exist constants $C,D,E$  such that, for any positive real number $z$ ,
$\sum _{p\in P \atop p\leq z}{\frac {w(p)}{p}}

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 and the $O$  invokes big O notation. In particular, letting $x$  denote the maximum element in $A$ , if $\log z  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$ ).