Additive combinatorics

Another typical problem is to find a lower bound for |A + B| in terms of |A| and |B|. This can be viewed as an inverse problem with the given information that |A + B| is sufficiently small and the structural conclusion is then of the form that either A or B is the empty set; however, in literature, such problems are sometimes considered to be direct problems as well. Examples of this type include the Erdős–Heilbronn Conjecture (for a restricted sumset) and the Cauchy–Davenport Theorem. The methods used for tackling such questions often come from many different fields of mathematics, including combinatorics, ergodic theory, analysis, graph theory, group theory, and linear-algebraic and polynomial methods.

History of additive combinatorics

Although additive combinatorics is a fairly new branch of combinatorics (the term additive combinatorics was coined by Terence Tao and Van H. Vu in their 2006 book of the same name), a much older problem, the Cauchy–Davenport theorem, is one of the most fundamental results in this field.

Cauchy–Davenport theorem

Suppose that A and B are finite subsets of the cyclic group ℤ/pℤ for a prime p, then the following inequality holds.

${\displaystyle |A+B|\ge min(|A|+|B|-1,p)}$

Vosper's theorem

Now we have the inequality for the cardinality of the sum set A + B, it is natural to ask the inverse problem, namely under what conditions on A and B does the equality hold? Vosper's theorem answers this question. Suppose that |A|,|B| ≥ 2 (that is, barring edge cases) and

${\displaystyle |A+B|\le |A|+|B|-1\le p-2,}$

then A and B are arithmetic progressions with the same difference. This illustrates the structures that are often studied in additive combinatorics: the combinatorial structure of A + B as compared to the algebraic structure of arithmetic progressions.

Plünnecke–Ruzsa inequality

A useful theorem in additive combinatorics is Plünnecke–Ruzsa inequality. This theorem gives an upper bound on the cardinality of |nA − mA| in terms of the doubling constant of A. For instance using Plünnecke–Ruzsa inequality, we are able to prove a version of Freiman's Theorem in finite fields.