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 ${\displaystyle A}$ be a finite set of positive integers. Let ${\displaystyle P}$ be some set of prime numbers. For each prime ${\displaystyle p}$ in ${\displaystyle P}$, let ${\displaystyle A_{p))$ denote the set of elements of ${\displaystyle A}$ that are divisible by ${\displaystyle p}$. This notation can be extended to other integers ${\displaystyle d}$ that are products of distinct primes in ${\displaystyle P}$. In this case, define ${\displaystyle A_{d))$ to be the intersection of the sets ${\displaystyle A_{p))$ for the prime factors ${\displaystyle p}$ of ${\displaystyle d}$. Finally, define ${\displaystyle A_{1))$ to be ${\displaystyle A}$ itself. Let ${\displaystyle z}$ be an arbitrary positive real number. The object of the sieve is to estimate:

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

where the notation ${\displaystyle |X|}$ denotes the cardinality of a set ${\displaystyle X}$, which in this case is just its number of elements. Suppose in addition that ${\displaystyle |A_{d}|}$ may be estimated by

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

${\displaystyle w}$

${\displaystyle R_{d))$

$${\displaystyle 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

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

  

Then

$${\displaystyle 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 ${\displaystyle X}$ is the cardinal of ${\displaystyle A}$, ${\displaystyle b}$ is any positive integer and the ${\displaystyle O}$ invokes big O notation. In particular, letting ${\displaystyle x}$ denote the maximum element in ${\displaystyle A}$, if ${\displaystyle \log z<c\log x/\log \log x}$ for a suitably small ${\displaystyle c}$, then

$${\displaystyle 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 ${\displaystyle C}$ primes (where ${\displaystyle 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 (${\displaystyle C=3}$).