# 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 ${\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},}$

where ${\displaystyle w}$  is some multiplicative function, and ${\displaystyle R_{d}}$  is some error function. Let
${\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)  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}}

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 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  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}$ ).

## References

• Viggo Brun (1915). "Über das Goldbachsche Gesetz und die Anzahl der Primzahlpaare". Archiv for Mathematik og Naturvidenskab. B34 (8).
• Viggo Brun (1919). "La série ${\displaystyle {\tfrac {1}{5}}+{\tfrac {1}{7}}+{\tfrac {1}{11}}+{\tfrac {1}{13}}+{\tfrac {1}{17}}+{\tfrac {1}{19}}+{\tfrac {1}{29}}+{\tfrac {1}{31}}+{\tfrac {1}{41}}+{\tfrac {1}{43}}+{\tfrac {1}{59}}+{\tfrac {1}{61}}+\cdots }$  où les dénominateurs sont "nombres premiers jumeaux" est convergente ou finie". Bulletin des Sciences Mathématiques. 43: 100–104, 124–128. JFM 47.0163.01.
• Alina Carmen Cojocaru; M. Ram Murty (2005). An introduction to sieve methods and their applications. London Mathematical Society Student Texts. Vol. 66. Cambridge University Press. pp. 80–112. ISBN 0-521-61275-6.
• George Greaves (2001). Sieves in number theory. Ergebnisse der Mathematik und ihrer Grenzgebiete (3. Folge). Vol. 43. Springer-Verlag. pp. 71–101. ISBN 3-540-41647-1.
• Heini Halberstam; H.E. Richert (1974). Sieve Methods. Academic Press. ISBN 0-12-318250-6.
• Christopher Hooley (1976). Applications of sieve methods to the theory of numbers. Cambridge University Press. ISBN 0-521-20915-3..