zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
An introduction to sieve methods and their applications. (English) Zbl 1121.11063
London Mathematical Society Lecture Note Series 66. Cambridge: Cambridge University Press (ISBN 0-521-84816-4/hbk; 0-521-61275-6/pbk). xii, 224 p. £ 22.99, $ 39.99/pbk; £ 50.00, $ 90.0/hbk (2006).

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 ν(n) of prime factors of n. Generalizing this classical result of Hardy and Ramanujan, the authors determine the normal order of ν(f(n)), where f is a polynomial with integer coefficients. They also investigate the normal order of ν(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 𝔽 p [x] and of counting irreducible polynomials with bounded height in [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 π(x)x/loglogx for the number of primes π(x) not exceeding x. The authors then investigate ways to refine the sieve of Eratosthenes-Legendre to obtain better bounds for π(x) by elementary means. To this end, they introduce “Rankin’s trick” in the estimation of the function Ψ(x,z), the number of positive integers nx composed by prime factors not exceeding z (z-smooth numbers). Rankin’s trick results in the bound π(x)x(loglogx)/logx which is much closer to the true order of magnitude x/logx of π(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 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 μ-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 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 π(x;q,a) of primes px such that pamodq. In particular, this bound contains Chebyshev’s bound π(x)x/logx.

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 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 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.

MSC:
11N35Sieves
11-01Textbooks (number theory)
11N36Applications of sieve methods
Keywords:
sieve methods