An Introduction to Sieve Methods and Their Applications

by Alina Carmen Cojocaru , M. Ram Murty

• ISBN13: 9780521612753
• ISBN10: 0521612756
• Format: Paperback
• Copyright: 2006-01-30
• Publisher: Cambridge University Press

Summary

Sieve theory has a rich and romantic history. The ancient question of whether there exist infinitely many twin primes (primes p such that p+2 is also prime), and Goldbach's conjecture that every even number can be written as the sum of two prime numbers, have been two of the problems that have inspired the development of the theory. This book provides a motivating introduction to sieve theory. Rather than focus on technical details which can obscure the beauty of the theory, the authors focus on examples and applications, developing the theory in parallel. The text can be used for a senior level undergraduate course or an introductory graduate course in analytic number theory.

Table of Contents

Preface	xi
1 Some basic notions	1	(14)
1.1 The big 'O' and little 'o' notation	1	(1)
1.2 The Möbius function	2	(2)
1.3 The technique of partial summation	4	(1)
1.4 Chebycheff's theorem	5	(5)
1.5 Exercises	10	(5)
2 Some elementary sieves	15	(17)
2.1 Generalities	15	(2)
2.2 The larger sieve	17	(4)
2.3 The square sieve	21	(4)
2.4 Sieving using Dirichlet series	25	(2)
2.5 Exercises	27	(5)
3 The normal order method	32	(15)
3.1 A theorem of Hardy and Ramanujan	32	(3)
3.2 The normal number of prime divisors of a polynomial	35	(3)
3.3 Prime estimates	38	(2)
3.4 Application of the method to other sequences	40	(3)
3.5 Exercises	43	(4)
4 The Turán sieve	47	(16)
4.1 The basic inequality	47	(2)
4.2 Counting irreducible polynomials in Fp[x]	49	(2)
4.3 Counting irreducible polynomials in Z[x]	51	(2)
4.4 Square values of polynomials	53	(2)
4.5 An application with Hilbert symbols	55	(3)
4.6 Exercises	58	(5)
5 The sieve of Eratosthenes	63	(17)
5.1 The sieve of Eratosthenes	63	(2)
5.2 Mertens' theorem	65	(3)
5.3 Rankin's trick and the function Ψ(x, z)	68	(2)
5.4 The general sieve of Eratosthenes and applications	70	(4)
5.5 Exercises	74	(6)
6 Brun's sieve	80	(33)
6.1 Brun's pure sieve	81	(6)
6.2 Brun's main theorem	87	(13)
6.3 Schnirelman's theorem	100	(6)
6.4 A theorem of Romanoff	106	(2)
6.5 Exercises	108	(5)
7 Selberg's sieve	113	(22)
7.1 Chebycheff's theorem revisited	113	(5)
7.2 Selberg's sieve	118	(6)
7.3 The Brun—Titchmarsh theorem and applications	124	(6)
7.4 Exercises	130	(5)
8 The large sieve	135	(21)
8.1 The large sieve inequality	136	(3)
8.2 The large sieve	139	(3)
8.3 Weighted sums of Dirichlet characters	142	(5)
8.4 An average result	147	(4)
8.5 Exercises	151	(5)
9 The Bombieri—Vinogradov theorem	156	(21)
9.1 A general theorem	157	(10)
9.2 The Bombieri—Vinogradov theorem	167	(5)
9.3 The Titchmarsh divisor problem	172	(2)
9.4 Exercises	174	(3)
10 The lower bound sieve	177	(24)
10.1 The lower bound sieve	177	(8)
10.2 Twin primes	185	(8)
10.3 Quantitative results and variations	193	(2)
10.4 Application to primitive roots	195	(4)
10.5 Exercises	199	(2)
11 New directions in sieve theory	201	(17)
11.1 A duality principle	201	(4)
11.2 A general formalism	205	(2)
11.3 Linnik's problem for elliptic curves	207	(2)
11.4 Linnik's problem for cusp forms	209	(4)
11.5 The large sieve inequality on GL(n)	213	(3)
11.6 Exercises	216	(2)
References	218	(4)
Index	222