28 1. Arithmetic Functions
making it available to count primes analytically. A modern version of Legendre’s
sieve formula is
π(x) = π(

x) 1 +
, P =

Though the Legendre sieve formula gives π(x) exactly, it is difficult to extract
strong information about the distribution of the primes from it and many years
passed before the idea of sieving had any impact on number theory beyond the
preparation of tables and other computational work. The main objective of modern
sieve theory is to find upper and lower bounds on the number of elements of a finite
set of integers remaining after those elements that lie in some prescribed arithmetic
progressions have been removed. This is such a flexible framework that a wide
variety of arithmetical problems are amenable to sieve methods to some extent.
The young French mathematician J. Merlin began making progress on sieve
theory around 1911, but he fell in the Great War. From 1915 V. Brun obtained
results on the primes by means of sieving, that were not accessible by any other
method. Since then, a vast amount of work has been done to improve sieve methods
and develop new and more powerful ones. They have had a very broad impact
on analytic number theory, leading to proofs of many important results, often in
combination with ideas from outside sieve theory. Some of the most striking results
obtained by means of sieves are:
The series of reciprocals of primes p for which p + 2 is prime, is finite or
convergent (Brun [Bru15] in 1915.)
There are infinitely many primes p for which p +2 has at most two prime
factors (J. R. Chen [Che73] in 1966.)
For every sufficiently large even integer n there is some prime p and some
integer m with at most two prime factors so that n = p + m (Chen
[Che73] in 1966.)
There are infinitely many integers m for which m2 + 1 has at most two
prime factors (H. Iwaniec [Iwa78] in 1978.)
The polynomial
takes infinitely many prime values (J. B. Fried-
lander and H. Iwaniec [FI98] in 1998.)
The polynomial
takes infinitely many prime values (D. R. Heath-
Brown [HB01] in 2001.)
The first two results are related to the twin prime problem, to prove that there
are infinitely many pairs of primes that differ by 2. The third is related to the
binary Goldbach problem, asserting that every even integer n 4 is the sum of
two primes, and the next two are related to the conjecture that the polynomial
+ 1 takes infinitely many prime values. All three problems are old, and all
are unsolved. The first of the six results above is nowadays not very difficult to
prove. Indeed M. Ram Murty and N. Saradha [MS87] discovered that even the
sieve of Eratosthenes suffices, when combined with an elementary device due to
R. A. Rankin. There is an exposition of their proof in An Introduction to Sieve
Methods and their Applications by A. C. Cojocaru and M. Ram Murty [CM06].
The proofs of the other five results are much more difficult.
Previous Page Next Page