Contents

Brun sieve

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

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

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

• 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..