Additive Combinatorics

Additive Combinatorics is an area connecting additive number theory and combinatorics, which has seen tremendous progresses in the last ten years or so. It has now become clear that ideas from combinatorics can be used quite effectively to attack deep problems in number theory and asymptotic group theory.

Tao and I wrote a monograph “Additive Combinatorics”, which can be used as an introduction to the area (see the review by B. Green). In recent years, there have been lots of activities focusing on recent progresses in this area at AIM, IAS, MSRI and many other institutions.

My favorite topic here is “Inverse theorems”.  (They are also called structural or rigidity theorems.) The big picture here is that a typical (random or pseudo-random) set of natural numbers (or elements of some groups in general) should satisfy all “nice” additive properties. If a set fails to satisfy some nice property, then it does have a very specific structure. A famous example is Freiman inverse theorem, which asserts that if A is set of natural numbers and A+A has few elements, then A must resemble an arithmetic progression. For many results which can be proved using inverse theorems, see this survey, which also contains several open questions.

Representative publications:


(1) E. Szemeredi and V. Vu, Infinite progressions in sumsets, Annals of Mathematics.

We proved an old conjecture of Folkman showing that if A is a set of natural number of asymptotic density at least Cn^{1/2} for some large constant C then the collection of all subset sums of A contains an infinite arithmetic progression.

(2) T. Tao and V. Vu,  Inverse Littlewood-Offord theorems and the condition number of random matrices, Annals of Mathematics.

Let x_i be random variables with mean 0 and variance 1 and a_i be vectors in R^d. We show that if the small probability Pr (S in B(v,r)) is large, when S is the sum of a_i x_i and B( v,r) is a small  ball centered at v in R^d having radius r, then the a_i must have a strong additive structure. This information can be in turned used to estimate the smallest singular value of a random matrix.



One thought on “Additive Combinatorics

  1. Pingback: Small ball probability and Inverse Littlewood-Offord theorems « Vuhavan's Blog

Comments are closed.