28 1. Arithmetic Functions

making it available to count primes analytically. A modern version of Legendre’s

sieve formula is

π(x) = π(

√

x) − 1 +

d|P

μ(d)

x

d

, P =

p≤

√

x

p.

Though the Legendre sieve formula gives π(x) exactly, it is diﬃcult 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 suﬃciently 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

m2

+

n4

takes infinitely many prime values (J. B. Fried-

lander and H. Iwaniec [FI98] in 1998.)

• The polynomial

m3+2n3

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

m2

+ 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 diﬃcult to

prove. Indeed M. Ram Murty and N. Saradha [MS87] discovered that even the

sieve of Eratosthenes suﬃces, 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 diﬃcult.