Additive combinatorics

Additive combinatorics is a rapidly developing and rather exciting area of mathematics. One major study in additive combinatorics is the inverse problems: given that the size of the sum set A + B is small, what can we say about the structures of A and B? In the case of the integers, the classical Freiman's theorem provides a potent partial answer to this question in terms of multi-dimensional arithmetic progressions. Another typical problem is simply 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 for A+B being that |A+B| is sufficiently small and the structural conclusion then being that either A or B is the empty set; such problems are often considered 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 draw from across the spectrum 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 (in fact the term additive combinatorics was coined by Terence Tao and Van H. Vu in their book in 2000's), an extremely old problem Cauchy–Davenport theorem is one of the most fundamental results in this field. According to the theorem, suppose that A and B are finite subsets of $\mathbb {Z} /p\mathbb {Z}$, then the following inequality holds.

$|A|+|B|\geq \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 an inverse problem, namely we can consider under what conditions of A and B the equality holds. Vosper's theorem answers this point. Suppose that $|A|,|B|\geq 2$ and

$|A+B|\leq |A|+|B|-1\leq p-2,$

then A and B are arithmetic progressions with the same difference.

Basic notions

Operations of sets

Let A and B be finite subsets of an abelian group, then the sum set is defined to be

$A+B=\{a+b:a\in A,b\in B\}.$

For example, we can write $\{1,2,3,4\}+\{1,2,3\}=\{2,3,4,5,6,7\}$. Similarly we can define the difference set of A and B to be

$A-B=\{a-b:a\in A,b\in B\}.$

Doubling constant

Let A be a subset of an abelian group. The doubling constant measures how big the sum set $|A+A|$ is compared to its original size |A|. We define the doubling constant of A to be

$K={\dfrac {|A+A|}{|A|}}.$

Ruzsa distance

Let A and B be two subsets of an abelian group. We define the Ruzsa distance between these two sets to be the quantity

$d(A,B)=\log {\dfrac {|A-B|}{\sqrt {|A||B|}}}.$

Note that since $d(A,A)$ cannot be zero, the Ruzsa distance is not a metric. Ruzsa triangle inequality tells us that the Ruzsa distance obeys the trianagle inequality:

$d(B,C)\leq d(A,B)+d(A,C).$