Additive Combinatorics / Edition 1

Additive Combinatorics / Edition 1

by Terence Tao, Van H. Vu
     
 

View All Available Formats & Editions

ISBN-10: 0521853869

ISBN-13: 9780521853866

Pub. Date: 09/25/2006

Publisher: Cambridge University Press

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.

Now in paperback, this

Overview

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.

Now in paperback, this graduate-level textbook will quickly 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 way, 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 the Green-Tao theorem on arithmetic progressions; Erdos distance problems; and the newly developing field of sum-product estimates. The text is supplemented by a large number of exercises and other material that has not previously appeared elsewhere.

Product Details

ISBN-13:
9780521853866
Publisher:
Cambridge University Press
Publication date:
09/25/2006
Series:
Cambridge Studies in Advanced Mathematics Series, #105
Edition description:
First Edition
Pages:
532
Product dimensions:
5.98(w) x 8.98(h) x 1.30(d)

Table of Contents

Prologue 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ász 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édi-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 Lp theory 156

4.3 Linear bias 160

4.4 Bohr sets 165

4.5 Λ(p) constants, Bh[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-Szeméredi-Gowers theorem 261

6.5 Plünnecke'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éen 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édi-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édi'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édi regularity lemma 406

10.7 Szemerédi's argument 411

11 Szemerédi'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

Customer Reviews

Average Review:

Write a Review

and post it to your social network

     

Most Helpful Customer Reviews

See all customer reviews >