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.

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2014 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.