Additive combinatorics. (English) Zbl 1127.11002

Tao, Terence; Vu, Van H.

Cambridge Studies in Advanced Mathematics 105. Cambridge: Cambridge University Press (ISBN 0-521-85386-9/hbk). xviii, 512 p. (2006).

The present book mirrors the development of modern additive combinatorics. It arouse out of lectures by the authors at various universities on the subject which became vivid in the last several decades and culminated in the celebrated Green-Tao theorem on arithmetic progressions in the primes. The book gathers diverse important techniques used in additive combinatorics, and its main advantage is that it is written in a very readable and easy to understand style. The authors try very successfully to develop all the necessary background material from the beginning in a concise matter what makes the book useful not only to graduate students, but also to researchers who are interested to learn more about the variety of diverse tools and ideas applied in this fascinating subject.
The first chapter introduces (or polishes up) the basic probabilistic tools, and shows their applications to additive bases and the primes. The second chapter is devoted to the inverse sum set problem and to elementary theory of sum set estimates. Ruzsa triangle theorem, Chang covering theorem or Balog-Szemerédi-Govers theorem or its asymmetric version can be found here. The third chapter goes a step further, when special structural properties of added sets are taken into account. The aim is to study these sets according to their structure (generalized arithmetic progressions, convex sets, lattices, finite subgroups), their dimension, size and the behavior under addition and subtraction.
The fourth chapter is devoted to the development and applications (Bohr sets contain large coset progressions, Chang theorem, or Bourgain theorem) of the Fourier-analytic tools. The fifth chapter “Inverse sum set theorems” culminates in several versions of the Freiman theorem and introduces the concept of a Freiman homomorphism.
Chapter 6 opens the way to the tools from graph theory which play an important role here. The reader finds a brief tour of Ramsey theory, Turán theorem or Plünnecke inequalities for commutative directed graphs. In the seventh chapter two different techniques are used on the background of the direct and inverse Littlewood-Offord problem. The first one is the Erdős approach based on chain and anti-chain techniques, and the second one the Fourier-analytic one based on Halász ideas. In chapter 8 ”Incidence geometry” a simple proof of Szemerédi-Trotter theorem on point-line incidence (or its more dimensional variant) is given. Also results on Erdős distinct distance problem or variant of sum-product problem are discussed here.
Chapter 9 “Algebraic methods” introduces the used tools from algebraic geometry, namely the so called polynomial method based on the effort to control the zero locus of multiple polynomials (Nullstellensatz, Chevalley-Warning theorem, Stepanov method). Application to Cauchy-Davenport inequality, Alon case of Snevily conjecture, Davenport problem or Kemnitz conjecture are given here.
Chapters 10 and 11 deal with the deep Szemerédi theorem (cases \(k=3\) and \(k>3\), respectively). The Szemerédi regularity lemma is discussed here together with the ergodic-theoretic proof of Furstenberg, the Govers additive combinatorial proof as well as the hypergraph approach.
Chapter 11 then ends with an informal discussion of the Green-Tao theorem in the light of the presented techniques.
The last chapter 12 is devoted to long arithmetic progression in sum sets. It also contains recent results of Szemerédi and Vu on subcomplete sets, applications to the Olson problem or monochromatic sum sets.
The book can only be recommended to everybody interested in the “additive branch” of the combinatorics.

Reviewer: Štefan Porubský (Praha)

MSC:

11-02	Research exposition (monographs, survey articles) pertaining to number theory
05-02	Research exposition (monographs, survey articles) pertaining to combinatorics
05D10	Ramsey theory
05D40	Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)
11B75	Other combinatorial number theory
11B13	Additive bases, including sumsets
11N13	Primes in congruence classes
11P70	Inverse problems of additive number theory, including sumsets
11K31	Special sequences
11P82	Analytic theory of partitions
28D05	Measure-preserving transformations
37A45	Relations of ergodic theory with number theory and harmonic analysis (MSC2010)

Keywords:

additive problems; sum sets; Lovász local lemma; Balog-Szemerédi-Govers theorem; progressions; inverse sum set theorem; Ramsey theory; Littlewood-Offord problem; Szemerédi-trotter theorem; incidence geometry; long arithmetic progressions; combinatorial Nullstellensatz; Szemerédi theorem; arithmetic progressions in the primes; sum-free sets; Sidon sets