{{Short description|Pre-generalisation of the fundamental lemma of sieve theory}} 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 <math>A</math> be a finite set of positive integers. Let <math>P</math> be some set of prime numbers. For each prime <math>p</math> in <math>P</math>, let <math>A_p</math> denote the set of elements of <math>A</math> that are divisible by <math>p</math>. This notation can be extended to other integers <math>d</math> that are products of distinct primes in <math>P</math>. In this case, define <math>A_d</math> to be the intersection of the sets <math>A_p</math> for the prime factors <math>p</math> of <math>d</math>. Finally, define <math>A_1</math> to be <math>A</math> itself. Let <math>z</math> be an arbitrary positive real number. The object of the sieve is to estimate: <math display="block">S(A,P,z) = \biggl\vert A \setminus \bigcup_{p \in P\atop p \le z} A_p \biggr\vert , </math>
where the notation <math>|X|</math> denotes the cardinality of a set <math>X</math>, which in this case is just its number of elements. Suppose in addition that <math>|A_d|</math> may be estimated by <math display=block> \left\vert A_d \right\vert = \frac{w(d)}{d} |A| + R_d,</math> where <math>w</math> is some multiplicative function, and <math>R_d</math> is some error function. Let <math display="block"> W(z) = \prod_{p \in P\atop p \le z} \left(1 - \frac{w(p)}{p} \right) . </math>
===Brun's pure sieve=== This formulation is from [https://books.google.com/books?id=1swo9Yf3d2YC Cojocaru & Murty], Theorem 6.1.2. With the notation as above, suppose that *<math>| R_d | \leq w(d) </math> for any squarefree <math>d</math> composed of primes in <math>P</math>; *<math>w(p) < C </math> for all <math>p</math> in <math>P</math>; *There exist constants <math>C, D, E</math> such that, for any positive real number <math>z</math>, <math display=block> \sum_{p \in P\atop p \le z} \frac{w(p)}{p} < D \log\log z + E.</math>
Then <math display=block> 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)</math>
where <math>X</math> is the cardinal of <math>A</math>, <math>b</math> is any positive integer and the <math>O</math> invokes big O notation. In particular, letting <math>x</math> denote the maximum element in <math>A</math>, if <math>\log z< c\log x/\log\log x</math> for a suitably small <math>c</math>, then <math display=block> S(A,P,z) = X \cdot W(z) (1+o(1)) .</math>
==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 <math>C</math> primes (where <math>C</math> 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 (<math>C=3</math>).
==References== * {{cite journal | author=Viggo Brun | author-link=Viggo Brun | title=Über das Goldbachsche Gesetz und die Anzahl der Primzahlpaare | journal=Archiv for Mathematik og Naturvidenskab | volume=B34 | issue=8 | year=1915 }} * {{cite journal | author=Viggo Brun | title=La série <math>\tfrac15 + \tfrac17 + \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</math> où les dénominateurs sont "nombres premiers jumeaux" est convergente ou finie | journal=Bulletin des Sciences Mathématiques | year=1919 | volume=43 | pages=100–104, 124–128|jfm=47.0163.01 }} * {{cite book | author=Alina Carmen Cojocaru |author2=M. Ram Murty | title=An introduction to sieve methods and their applications | series=London Mathematical Society Student Texts | volume=66 | publisher=Cambridge University Press | isbn=0-521-61275-6 | pages=80–112 | year=2005 }} * {{cite book | author=George Greaves | title=Sieves in number theory | series=Ergebnisse der Mathematik und ihrer Grenzgebiete (3. Folge) | volume=43 | publisher=Springer-Verlag | date=2001 | isbn=3-540-41647-1 | pages=71–101}} * {{cite book | author=Heini Halberstam | author-link=Heini Halberstam |author2=H.E. Richert | title=Sieve Methods | publisher=Academic Press | date=1974 | isbn=0-12-318250-6}} * {{cite book | author= Christopher Hooley | author-link=Christopher Hooley | title=Applications of sieve methods to the theory of numbers | publisher=Cambridge University Press | date=1976 | isbn=0-521-20915-3}}.
Category:Sieve theory