Additive Combinatorics

by Terence Tao , Van H. Vu

• ISBN13: 9780521853866
• ISBN10: 0521853869
• Edition: 1st
• Format: Hardcover
• Copyright: 2006-09-25
• Publisher: Cambridge University Press

Summary

Additive combinatorics is the theory of counting additive structures in sets. This theory has seen exciting developments and dramatic changes in direction in recent years thanks to its connections with areas such as number theory, ergodic theory and graph theory. This graduate level textbook will allow students and researchers easy entry into this fascinating field. Here, for the first time, the authors bring together in a self-contained and systematic manner the many different tools and ideas that are used in the modern theory, presenting them in an accessible, coherent, and intuitively clear manner, and providing immediate applications to problems in additive combinatorics. The power of these tools is well demonstrated in the presentation of recent advances such as Szemeredi's theorem on arithmetic progressions, the Kakeya conjecture and Erdos distance problems, and the developing field of sum-product estimates. The text is supplemented by a large number of exercises and new material.

Table of Contents

Prologue	xi
1 The probabilistic method	1	(50)
1.1 The first moment method	2	(4)
1.2 The second moment method	6	(3)
1.3 The exponential moment method	9	(10)
1.4 Correlation inequalities	19	(4)
1.5 The Lovász local lemma	23	(4)
1.6 Janson's inequality	27	(6)
1.7 Concentration of polynomials	33	(4)
1.8 Thin bases of higher order	37	(5)
1.9 Thin Waring bases	42	(3)
1.10 Appendix: the distribution of the primes	45	(6)
2 Sum set estimates	51	(61)
2.1 Sum sets	54	(3)
2.2 Doubling constants	57	(2)
2.3 Ruzsa distance and additive energy	59	(10)
2.4 Covering lemmas	69	(9)
2.5 The Balog–Szemerédi–Gowers theorem	78	(5)
2.6 Symmetry sets and imbalanced partial sum sets	83	(9)
2.7 Non-commutative analogs	92	(7)
2.8 Elementary sum-product estimates	99	(13)
3 Additive geometry	112	(37)
3.1 Additive groups	113	(6)
3.2 Progressions	119	(3)
3.3 Convex bodies	122	(5)
3.4 The Brunn-Minkowski inequality	127	(3)
3.5 Intersecting a convex set with a lattice	130	(13)
3.6 Progressions and proper progressions	143	(6)
4 Fourier-analytic methods	149	(49)
4.1 Basic theory	150	(6)
4.2 Lp theory	156	(4)
4.3 Linear bias	160	(5)
4.4 Bohr sets	165	(7)
4.5 Λ(p) constants, Bh[g] sets, and dissociated sets	172	(9)
4.6 The spectrum of an additive set	181	(8)
4.7 Progressions in sum sets	189	(9)
5 Inverse sum set theorems	198	(48)
5.1 Minimal size of sum sets and the e-transform	198	(13)
5.2 Sum sets in vector spaces	211	(9)
5.3 Freiman homomorphisms	220	(7)
5.4 Torsion and torsion-free inverse theorems	227	(6)
5.5 Universal ambient groups	233	(6)
5.6 Freiman's theorem in an arbitrary group	239	(7)
6 Graph-theoretic methods	246	(30)
6.1 Basic Notions	247	(1)
6.2 Independent sets, sum-free subsets, and Sidon sets	248	(6)
6.3 Ramsey theory	254	(7)
6.4 Proof of the Balog-Szemerédi-Gowers theorem	261	(6)
6.5 Plünnecke's theorem	267	(9)
7 The Littlewood-Offord problem	276	(32)
7.1 The combinatorial approach	277	(4)
7.2 The Fourier-analytic approach	281	(9)
7.3 The Esséen concentration inequality	290	(2)
7.4 Inverse Littlewood-Offord results	292	(5)
7.5 Random Bernoulli matrices	297	(7)
7.6 The quadratic Littlewood-Offord problem	304	(4)
8 Incidence geometry	308	(21)
8.1 The crossing number of a graph	308	(3)
8.2 The Szemerédi-Trotter theorem	311	(4)
8.3 The sum-product problem in R	315	(4)
8.4 Cell decompositions and the distinct distances problem	319	(6)
8.5 The sum-product problem in other fields	325	(4)
9 Algebraic methods	329	(40)
9.1 The combinatorial Nullstellensatz	330	(3)
9.2 Restricted sum sets	333	(9)
9.3 Snevily's conjecture	342	(3)
9.4 Finite fields	345	(5)
9.5 Davenport's problem	350	(4)
9.6 Kemnitz's conjecture	354	(2)
9.7 Stepanov's method	356	(6)
9.8 Cyclotomic fields, and the uncertainty principle	362	(7)
10 Szemerédi's theorem for k = 3	369	(45)
10.1 General strategy	372	(6)
10.2 The small torsion case	378	(8)
10.3 The integer case	386	(3)
10.4 Quantitative bounds	389	(9)
10.5 An ergodic argument	398	(8)
10.6 The Szemerédi regularity lemma	406	(5)
10.7 Szemeredi's argument	411	(3)
11 Szemeredi's theorem for k > 3	414	(56)
11.1 Gowers uniformity norms	417	(7)
11.2 Hard obstructions to uniformity	424	(8)
11.3 Proof of Theorem 11.6	432	(8)
11.4 Soft obstructions to uniformity	440	(8)
11.5 The infinitary ergodic approach	448	(6)
11.6 The hypergraph approach	454	(9)
11.7 Arithmetic progressions in the primes	463	(7)
12 Long arithmetic progressions in sum sets	470	(18)
12.1 Introduction	470	(3)
12.2 Proof of Theorem 12.4	473	(4)
12.3 Generalizations and variants	477	(3)
12.4 Complete and subcomplete sequences	480	(2)
12.5 Proof of Theorem 12.17	482	(2)
12.6 Further applications	484	(4)
Bibliography	488	(17)
Index	505