Additive Combinatorics

by Terence Tao , Van H. Vu

• ISBN13: 9780521136563
• ISBN10: 0521136563
• Format: Paperback
• Copyright: 2009-12-21
• Publisher: Cambridge University Press

Summary

Additive combinatorics is the theory of counting additive structures in sets. While this theory has been developing for many decades, the field has seen exciting advances and dramatic changes in direction in recent years thanks to its connections with other areas of mathematics, such as number theory, ergodic theory, and graph theory.

Table of Contents

Prologue	p. xi
The probabilistic method	p. 1
The first moment method	p. 2
The second moment method	p. 6
The exponential moment method	p. 9
Correlation inequalities	p. 19
The Lovász local lemma	p. 23
Janson's inequality	p. 27
Concentration of polynomials	p. 33
Thin bases of higher order	p. 37
Thin Waring bases	p. 42
Appendix: the distribution of the primes	p. 45
Sum set estimates	p. 51
Sum sets	p. 54
Doubling constants	p. 57
Ruzsa distance and additive energy	p. 59
Covering lemmas	p. 69
The Balog-Szemerédi-Gowers theorem	p. 78
Symmetry sets and imbalanced partial sum sets	p. 83
Non-commutative analogs	p. 92
Elementary sum-product estimates	p. 99
Additive geometry	p. 112
Additive groups	p. 113
Progressions	p. 119
Convex bodies	p. 122
The Brunn-Minkowski inequality	p. 127
Intersecting a convex set with a lattice	p. 130
Progressions and proper progressions	p. 143
Fourier-analytic methods	p. 149
Basic theory	p. 150
Lp theory	p. 156
Linear bias	p. 160
Bohr sets	p. 165
¿(p) constants, Bh[g] sets, and dissociated sets	p. 172
The spectrum of an additive set	p. 181
Progressions in sum sets	p. 189
Inverse sum set theorems	p. 198
Minimal size of sum sets and the e-transform	p. 198
Sum sets in vector spaces	p. 211
Freiman homomorphisms	p. 220
Torsion and torsion-free inverse theorems	p. 227
Universal ambient groups	p. 233
Freiman's theorem in an arbitrary group	p. 239
Graph-theoretic methods	p. 246
Basic notions	p. 247
Independent sets, sum-free subsets, and Sidon sets	p. 248
Ramsey theory	p. 254
Proof of the Balog-Szeméredi-Gowers theorem	p. 261
Plünnecke's theorem	p. 267
The Littlewood-Offord problem	p. 276
The combinatorial approach	p. 277
The Fourier-analytic approach	p. 281
The Esséen concentration inequality	p. 290
Inverse Littlewood-Offord results	p. 292
Random Bernoulli matrices	p. 297
The quadratic Littlewood-Offord problem	p. 304
Incidence geometry	p. 308
The crossing number of a graph	p. 308
The Szemerédi-Trotter theorem	p. 311
The sum-product problem in R	p. 315
Cell decompositions and the distinct distances problem	p. 319
The sum-product problem in other fields	p. 325
Algebraic methods	p. 329
The combinatorial Nullstellensatz	p. 330
Restricted sum sets	p. 333
Snevily's conjecture	p. 342
Finite fields	p. 345
Davenport's problem	p. 350
Kemnitz's conjecture	p. 354
Stepanov's method	p. 356
Cyclotomic fields, and the uncertainty principle	p. 362
Szemerédi's theorem for k = 3	p. 369
General strategy	p. 372
The small torsion case	p. 378
The integer case	p. 386
Quantitative bounds	p. 389
An ergodic argument	p. 398
The Szemerédi regularity lemma	p. 406
Szemerédi's argument	p. 411
Szemerédi's theorem for k > 3	p. 414
Gowers uniformity norms	p. 417
Hard obstructions to uniformity	p. 424
Proof of Theorem 11.6	p. 432
Soft obstructions to uniformity	p. 440
The infinitary ergodic approach	p. 448
The hypergraph approach	p. 454
Arithmetic progressions in the primes	p. 463
Long arithmetic progressions in sum sets	p. 470
Introduction	p. 470
Proof of Theorem 12.4	p. 473
Generalizations and variants	p. 477
Complete and subcomplete sequences	p. 480
Proof of Theorem 12.17	p. 482
Further applications	p. 484
Bibliography	p. 488
Index	p. 505
Table of Contents provided by Ingram. All Rights Reserved.