Brun sieve

In the field of

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

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
  .
• ISBN 0-12-318250-6
  .
• ISBN 0-521-20915-3
  ..