Additive Combinatorics

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

Another Logic Books
Download