4. Structure of set addition

Sum set

Given two finite sets of \(A\) and \(B\) of elements in an abelian group. We define their sumset to be

\[ A+B=\{a+b|a\in A,b\in B\} \]

Additive combinatorics is an area of combinatorics in mathematics. A fundamental problem in this field is the inverse sum set problem: if \(A+B\) is small, what can we say about \(A\) and \(B\) ? A more specific question one may raise is: if \(A\) is a finite non-empty set such that \(|A + A| = K|A|\) for some small number \(K\), what can one say about \(A\) ?

First, we would like to clarify some notations:

• Given a positive integer \(k\), we define the iterated sumset

\[ kA = A + \cdots + A\quad (k\text{ times}) \]

This is different from dilating a set, which is denoted by

\[ \lambda\cdot A = \{\lambda a | a\in A\} \]

Similar to the sumset, we can define the difference set

\[ A-B= \{a-b|a\in A,b\in B\} \]

First, how small or large can \(A+A\) be given \(|A|\) ? We have a trivial estimation for this:

Proposition 1: Let \(A,B\) be two sets in the same abelian group \(Z\), let \(x\in Z\). Then we have the identity \(|A + x| = |-A|=|A|\), the inequalities

\[ \max(|A|,|B|)\le |A-B|,|A + B|\le |A||B| \]

and the inequalities

\[ |A|\le |A + A|\le \frac{|A|(|A| + 1)}{2} \]

Moreover, if \(A,B\) are sets of integers, we can say that

\[ |A+B|\ge |A| + |B| - 1 \]

Proof: For the first identity, we see that \(A+x = \{a+x |a\in A\}\) is a translation of the original set \(A\), thus their size must be equal. We can see why \(|A+ B|\ge |A|\) based on this identity, and the upper bound of \(|A+B|\) comes from counting all possible pairs of \((a,b)\) such that \(a\in A,b\in B\).

The upper bound of \(|A+A|\) follows from that there are in total \(\binom{|A|}{2}\) numbers of unordered pairs of elements in \(A\).

Interestingly, for \(A,B\subset \mathbb Z\), we can sort the elements of \(A\) and \(B\) in increasing order like

\[ a_1< a_2<\cdots < a_n,b_1<b_2<\cdots < b_m \]

then

\[ a_1+b_1<a_2+b_1<\cdots < a_n + b_1 < a_n + b_2< \cdots < a_n + b_m \]

are \(n +m - 1=|A| + |B| - 1\) distinct elements in \(A+B\).

We also want to quantify our measure when talking about \(|A+A|\) is not too much larger than \(|A|\). A good way to do this is defining the ratio of their size, called doubling constant \(\sigma[A]\):

\[ \sigma[A] = \frac{|A+A|}{|A|} \]

Ruzsa triangle inequality

Relating to sizes of sumsets, mathematicians have developed some basic and useful inequalities.

(Ruzsa triangle inequality) If \(A,B,C\) are finite subsets of an abelian group, then

\[ |A||B-C|\le |A-B||A-C| \]

Proof: For any element \(d\in B -C\), we fix a choice of \(b\in B\) and \(c\in C\) such that \(b-c=d\) to represent it. Then we can map any element \((a,b-c)\in A\times (B-C)\) to an element \((x,y)=(a-b,a-c)\in(A-B)\times (A-C)\). This is injective, since we can get back \(d\) by taking \(d=y-x\) and then \(a=x + b\).

Remark: By replacing \(B\) with \(-B\) or/and \(C\) with \(-C\), we can get other additional inequalities with similar forms:

\[ \begin{aligned} |A||B+C|\le |A+B||A-C|\\ |A||B+C|\le |A-B||A+C|\\ |A||B-C|\le |A+B||A+C|\\ \end{aligned} \]

It might not be clear why this is called a triangle inequality. Well, if we define the Ruzsa distance between two finite sets \(A,B\) as

\[ d(A,B) =\log \frac{|A-B|}{\sqrt{|A||B|}} \]

Then the theorem can be rewritten as

\[ d(A,B) + d(A,C)\le d(B,C) \]

However, we do understand that the function \(d\) is not a metric measure because \(d(A,A)\ne 0\).

Plünnecke’s inequality

If we have sets \(A,B\) such that \(A+B\) is not much bigger than \(A\), what can we say about the bound of the size of iterated sumsets of \(B\)?

(Plünnecke’s inequality) Let \(A,B\) be finite subsets of an abelian group satisfying

\[ |A+B|\le K|A| \]

then for all non-negative integers \(m,n\),

\[ |mB - nB|\le K^{m+n}|A| \]

The following lemma bounds the expansion ratio, which is quite important in our proof.

Lemma: Let \(X\) and \(B\) be two finite sets in an abelian group with \(|X| > 0\). Suppose for all \(Y\subset X\),

\[ \frac{|Y+B|}{|Y|}\ge\frac{|X + B|}{|X|} \]

Then for any nonempty finite subsets \(C\) of the abelian group,

\[ \frac{|X+C+B|}{|X+C|}\le\frac{|X+ B|}{|X|} \]

Proof: We can proceed by induction on the size of \(C\). When \(|C|=1\), \(|X+C+B|=|X+B|,|X+C|=|X|\), so the statement holds. For our convenience, say \(K=|X+B|/|X|\) .

For the induction step, assume that we have some \(C\) such that the lemma is true. We consider the set \(C'=C\cup\{c\}\) for some \(c\notin C\). It suffices to prove that the ratio between the number of elements we add in \(X+C'+B\) and the number of elements we add in \(X+C'\) satisfies the condition. More formally,

\[ |(X+c+B)\setminus(X+C+B)|\le K|(X+c)\setminus(X+C)| \]

Let

\[ Y=\{x\in X| x+c +B\subset x + C+ B\} \]

be a subset of \(X\). Since \(|X+c+B|=|X+B|\), the size of the increment is bounded by the number of overlapping elements in set \(X+c+B\) and \(X+C+B\).

\[ |(X+c+B)\setminus(X+C+B)|\le |X+B|-|Y+B| \]

Moreover, if \(x\in X\) satisifes \(x+c\in X+C\), then \(x+c+B\subset x+C+B\) and hence \(x\in Y\). So we have

\[ |(X+c)\setminus(X+C)|\ge |X| - |Y| \]

Combining previous results, it suffices to show that

\[ |X+B|-|Y+B|\le K(|X|-|Y|)=|X+B|-K|Y| \]

which can be rewritten as

\[ \frac{|Y+B|}{|Y|}\ge K=\frac{|X+B|}{|X|} \]

which is clearly true based on our hypothesis.

We call \(|X+B|/|X|\) the expansion ratio of a set \(X\). Next, we can apply this lemma to prove our inequality.

Proof: First, we want to choose some suitable sets so we can apply our lemma. Choose \(X\) among all the non-empty subsets of \(A\) with the minimum expansion ratio. Hence, the condition in the lemma is satisfied. We also have

\[ \frac{|X+B|}{|B|}\le \frac{|A+B|}{|A|}\le K \]

apply our lemma with \(C=nB\), then

\[ \frac{|X+(n+1)B|}{|X+nB|}\le \frac{|X+B|}{|B|}\le K \]

Induction on \(n\) yields

\[ |X+nB|\le K^n|X| \]

Finally, we can apply Ruzsa triangle inequality for all \(m,n\ge 0\):

\[ |mB -nB|\le \frac{|X+mB||X+nB|}{|X|}\le K^{m+n}|X|\le K^{m+n}|X| \]