Brun’s pure sieve
In the first quarter of the twentieth century Viggo Brun developed
an extension of the sieve of Eratosthenes
that yielded good
estimates on the number of elements of a set that
are not divisible (http://planetmath.org/Divisibility) by any of the primes provided
only that is “sufficiently regularly distributed”
modulo these primes. That allowed him to prove that the sum of
reciprocals of twin primes
converges (the limit is now known as
Brun’s constant), and that every sufficiently large even number
is
a sum of two numbers each having at most prime factors
. In
what follows we describe the simplest form of Brun’s sieve, known
as Brun’s pure sieve.
The sieve of Eratosthenes (http://planetmath.org/SieveOfEratosthenes2) is based on the principle of inclusion-exclusion in the form
(1) |
Brun’s sieve is based on the observation that the partial sums of (1) alternatively overcount and undercount the number of elements of counted by the left side, that is,
(2) |
where denotes the number of prime (http://planetmath.org/Prime) factors of . In applications can usually be approximated by a multiple of a multiplicative function, that is,
where is some multiplicative function of , and is small compared to . Then the estimate in (2) takes the form
(3) |
If the truncated sum is a good approximation to the full sum, then
this formula is an improvement over the
sieve of Eratosthenes (http://planetmath.org/SieveOfEratosthenes2) because the sum over error
terms is shorter.
Since is greater than for every and every such that , we have that
and since the sum of a multiplicative function can be
written as an Euler product![]() | ||||
to minimize the error term we choose , and get | ||||
Combining this with (3) and (2) we obtain
(4) |
provided that .
Example. (Upper bound on the number of primes.) If we set
to be all the primes less , and
, then the right hand side
of (4) provides an upper bound for the number of
primes between and .
We have that and . The second error term in (4) has at most summands, and the first error term is bounded by by Merten’s theorem. Thus, the estimate (4) becomes
In order to squeeze out the best upper bound on the number of primes
not exceeding we have to minimize the right side of the
inequality above. The nearly optimal choice is ,
and for a sufficiently large constant .
With this choice we obtain
This inequality is stronger than the one obtained by an application of the sieve of Eratosthenes (http://planetmath.org/SieveOfEratosthenes2).
Example. (Upper bound on the number of twin primes.) If and , then the integers and cannot both be primes. Let be as above, and set . Then , and if . The remainder does not exceed . Like above we obtain
where denotes the number of twin primes not exceeding . Upon setting , and we obtain
This is the original result for which Viggo Brun developed the sieve now bearing his name. This result can be put in following striking form:
Theorem.
The sum
converges.
General combinatorial sieve
The inequality (2) was based on the observation that
(5) |
where is the characteristic function of the set of
integers with no more than prime factors, and is
the characteristic function of the set of integers with no more
than prime factors. It is possible to choose different
functions and that satisfy the
inequality (5) to obtain bounds similar
to (4). The problem of optimal choice of these
functions in general is very hard. For more detailed information
on Brun’s sieve and sieves in general one should consult the
monographs
[1, 2, 3].
References
-
1
George Greaves.
Sieves in number theory
. Springer, 2001. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=1003.11044Zbl 1003.11044.
- 2 H. Halberstam and H.-E. Richert. Sieve methods, volume 4 of London Mathematical Society Monographs. 1974. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0298.10026Zbl 0298.10026.
- 3 C. Hooley. Application of sieve methods to the theory of numbers, volume 70 of Cambridge Tracts in Mathematics. Cambridge Univ. Press, 1976. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0327.10044Zbl 0327.10044.
-
4
Gérald Tenenbaum.
Introduction to Analytic
and Probabilistic Number Theory, volume 46 of Cambridge Studies in Advanced Mathematics. Cambridge Univ. Press. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0831.11001Zbl 0831.11001.
Title | Brun’s pure sieve |
Canonical name | BrunsPureSieve |
Date of creation | 2013-03-22 14:10:54 |
Last modified on | 2013-03-22 14:10:54 |
Owner | bbukh (348) |
Last modified by | bbukh (348) |
Numerical id | 11 |
Author | bbukh (348) |
Entry type | Topic |
Classification | msc 11N36 |
Classification | msc 11N35 |
Related topic | PrincipleOfInclusionExclusion |
Related topic | SieveOfEratosthenes2 |
Related topic | BrunsConstant |
Related topic | BonferroniInequalities |
Defines | combinatorial sieve |