The book under review gives a self-contained introduction to various sieve methods, such as the classical sieves of Brun and Selberg, the large sieve, and several other sieve methods. Complicated technical aspects of the theory are avoided, which makes the book easy to read. The authors consider a large variety of interesting applications, and every chapter is complemented by many exercises. Therefore the book is an ideal textbook for students to learn the foundations of sieve theory. It is also a useful source for experts in the material.
After introducing some basic notions, the authors deal with certain elementary and technically easy sieves, like the larger sieve by P. X. Gallagher [Acta Arith. 18, 77–81 (1971; Zbl 0231.10028)], which is most useful in situations when a positive proportion of the residue classes are excluded modulo each sifting prime, the square sieve by D. R. Heath-Brown [Math. Ann. 266, 251–259 (1984; Zbl 0514.10038)], which detects squares in sequences of natural numbers, and sieves using Dirichlet series. This part is succeded by a chapter on Turán’s normal order method which has its origin in the work of Hardy and Ramanujan on the normal order of the number \(\nu(n)\) of prime factors of \(n\). Generalizing this classical result of Hardy and Ramanujan, the authors determine the normal order of \(\nu(f(n))\), where \(f\) is a polynomial with integer coefficients. They also investigate the normal order of \(\nu(p-1)\), where \(p\) runs over the primes, and other interesting questions related to normal orders.
Then the authors formalize Turán’s method and develop it further into a sieve they call “Turán sieve”. This sieve is simpler than the classical sieve of Eratosthenes but gives comparable results in some cases. Among other applications of the Turan sieve, the authors consider the problems of counting irreducible polynomials in \(\mathbb{F}_p[x]\) and of counting irreducible polynomials with bounded height in \(\mathbb{Z}[x]\).
The authors then turn to the sieve of Eratosthenes. They describe a form of this sieve due to A. M. Legendre which leads to his upper bound \(\pi(x)\ll x/\log\log x\) for the number of primes \(\pi(x)\) not exceeding \(x\). The authors then investigate ways to refine the sieve of Eratosthenes-Legendre to obtain better bounds for \(\pi(x)\) by elementary means. To this end, they introduce “Rankin’s trick” in the estimation of the function \(\Psi(x,z)\), the number of positive integers \(n\leq x\) composed by prime factors not exceeding \(z\) (\(z\)-smooth numbers). Rankin’s trick results in the bound \(\pi(x)\ll x(\log\log x)/\log x\) which is much closer to the true order of magnitude \(x/\log x\) of \(\pi(x)\) (prime number theorem) than Legendre’s bound. The authors then formalize the sieve of Eratosthenes-Legendre-Rankin and, as an application, give a remarkably simple proof of Brun’s observation that the series \(\sum\limits_{p} 1/p\) converges as \(p\) runs over all primes such that \((p,p+2)\) is a twin prime.
Viggo Brun’s combinatorial sieve method is developed in the following chapter. In the beginning, a description is given of what is known as “Brun’s pure sieve” whose key idea lies in truncating the Möbius \(\mu\)-function. Brun’s pure sieve yields results comparable to the sieve of Eratosthenes-Legendre-Rankin. In particular, it is capable of proving the above-mentioned result on the convergence of the series \(\sum\limits_{p} 1/p\), where \(p\) runs over primes such that \(p+2\) is also a prime. The authors then develop Brun’s sieve in full and employ it to establish that there are infinitely many pairs \((n,n+2)\) of integers having at most seven prime factors. They also employ Brun’s sieve to give a proof of Shnirelmann’s theorem which asserts that every natural number can be written as a sum of a bounded number of primes.
After describing the rather complicated combinatorial sieve of Brun, the authors discuss Selberg’s upper bound sieve method, which may be considered to be the most “popular” sieve. In its less advanced form, it is simpler and easier to use than Brun’s sieve but yields comparable upper bounds. The idea of this sieve is to replace the Möbius function with a quadratic form which is chosen in such a way that the resulting estimates for the sifting function are optimal. As an application, the authors present the Brun-Titchmarsh theorem, a remarkably sharp upper bound for the number \(\pi(x;q,a)\) of primes \(p\leq x\) such that \(p\equiv a \bmod q\). In particular, this bound contains Chebyshev’s bound \(\pi(x)\ll x/\log x\).
The next two chapters are devoted to the large sieve which originated in the work of Yu. V. Linnik [C. R. (Dokl.) Acad. Sci. URSS, N. Ser. 36, 119–120 (1942; Zbl 0063.03570)] on the least quadratic non-residue modulo \(p\), and its applications to primes in arithmetic progressions. The large sieve is most powerful in situations when the number of excluded residue classes modulo the sifting primes is not bounded by an absolute constant (this explains the expression “large sieve”). Unlike the sieves of Brun and Selberg, the large sieve is not of combinatorial nature. Its arithmetic form is rather a consequence of a general analytic inequality that compares a discrete and a continuous mean value of a trigonometrical polynomial. The authors follow a method of Gallagher to prove this large sieve inequality. They further derive a version of the large sieve for Dirichlet characters which then serves as a key tool in the proofs of the important mean value theorems of Barban-Davenport-Halberstam and Bombieri-Vinogradov on primes in arithmetic progressions. As an application of the Bombieri-Vinogradov problem, the authors consider the Titchmarsh divisor problem on the average order of \(d(p+a)\), where \(a\) is a fixed non-zero integer, \(p\) runs over the primes, and \(d(n)\) is the number of divisors of \(n\).
Whereas Brun’s sieve yields lower and upper bounds by construction, the initial method of Selberg yields only upper bounds. An important problem, which can be approached in different ways, is the question how to modify Selberg’s method to obtain also lower bounds. The authors take a rather direct approach due to E. Bombieri. Here the key idea is to inject certain weights into Selberg’s method. Using the resulting lower bound sieve together with the Bombieri-Vinogradov theorem, they prove in a quite short and elegant way that there exist infinitely many primes \(p\) such that \(p+2\) has at most 4 prime factors. As another application, they consider Artin’s conjecture on primitive roots.
The book concludes with a chapter on recent extensions of the large sieve to automorphic representations on \(\text{GL}(n)\). Following W. Duke and E. Kowalski [Invent. Math. 139, No. 1, 1–39 (2000; Zbl 1033.11026)], the authors first describe a general duality formalism. They then discuss an analogue of Linnik’s problem on the least quadratic non-residue modulo \(p\), mentioned before in this review, for elliptic curves and briefly describe Duke’s and Kowalski’s attack on this problem. Their method uses the celebrated modularity theorem of A. Wiles [Ann. Math. (2) 141, No. 3, 443–551 (1995; Zbl 0823.11029)] together with a version of the large sieve for cusp forms obtained by employing the said duality formalism and the Rankin-Selberg theory on twists of automorphic \(L\)-functions. Finally, the authors give a brief outline of a general large sieve inequality for automorphic representations on \(\text{GL}(n)\) developed by Duke and Kowalski.
Often sieve theory is considered to be technically complicated and difficult to learn. This excellent introductory book however brings the interested student quickly into a position to apply sieve methods successfully to various problems in analytic number theory.