Introduction to Sumsets

After finding a quetsion on Math Stack Exchange, I decided to take a large chunk out of my MS thesis and present it.

Given $A,B\subseteq Z$ for a commutative ring $Z$, we define

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

to be the sumset of $A$ and $B$.

Similarly,

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

$$kA:=\underset{k\text{ times}}{\underbrace{A+\dots A}}$$

$$b+A:=\{b\}+A$$

for $A,B\subseteq Z$.

Theorem 1 : If $A$ and $B$ are two finite subsets of $\mathbb{R}$, then

$$|A|+|B|-1\le |A+B|\le |A||B|$$

and the lower bound is sharp iff $A$ and $B$ are arithmetic progressions of same difference.

Proof : The upper bound is obvious as we can just choose $A$ and $B$ in such a manner that all the sums of the form $a+b$ are different. One example of such a set is

$$A=\{0,1,\dots ,r-1\},B=r\cdot \{0,1,\dots ,s-1\}$$

so that

$$A+B=\{0,1,\dots ,rs-1\}$$

hence completing the proof.

  

Denoting $A=\{a_1<a_2<\cdots <a_r\}$ and $B=\{b_1<b_2<\cdots <b_s\}$, and noting that the following chain of inequalities

$$a_1+b_1<a_1+b_2<a_1+b_3<\cdots <a_1+b_s<a_2+b_s<\cdots <a_r+b_s$$

contains $r+s-1$ different elements of $A+B$ immediately completes the proof of the lower bound.

  

Now, let us assume that the lower bound is tight. Then, the following chain of inequalities

$$a_1+b_1<a_2+b_1<a_2+b_2<a_2+b_3<\cdots <a_2+b_s<a_3+b_s<\cdots <a_r+b_s$$

and the previous one must be the same.

The first and the last $r-1$ terms are clearly equal, the other $s-1$ terms determine the equations

$$\begin{array}{rl}{a}_1+b_2& =a_2+b_1\\ a_1+b_3& =a_2+b_2\\ & .\\ & .\\ & .\\ a_1+b_s& =a_2+b_{s-1}\end{array}$$

which on rearranging gives

$$\begin{array}{rl}{b}_2-b_1& =a_2-a_1\\ b_3-b_2& =a_2-a_1\\ & .\\ & .\\ & .\\ b_s-b_{s-1}& =a_2-a_1\end{array}$$

and hence $B$ is an arithmetic progression with difference $a_2-a_1$. Since the roles of $A$ and $B$ are symmetric in the statement, then so must be $A$.

In fact, a more general statement is true.

Theorem 2 : If $A_1,A_2,\dots ,A_k$, $k\ge 2$ are finite subsets of $\mathbb{R}$, then

$$|A_1|+|A_2|+\dots |A_k|-k+1\le |A_1+A_2+\dots A_k|\le |A_1||A_2|\dots |A_k|$$

and the lower bound is sharp iff $A_1,A_2,\dots ,A_k$ are arithmetic progressions of same difference.

Proof : We proceed by Induction.

The case $k=2$ is precisely the last theorem.

Now, let us assume that the statement is true for $k-1$.

Let $A=A_1+A_2+\cdots +A_{k-1}$ and $B=A_k$ so that $A+B=A_1+A_2+\cdots +A_k$. Using the previous theorem and the Induction Hypothesis, we get

$$\begin{array}{rl}|A_1|+|A_2|+\dots |A_{k-1}|-k+2+|A_k|-1& \le |A|+|B|-1\\ & \le |A+B|\\ & \le |A||B|\\ & \le |A_1||A_2|\dots |A_k|\end{array}$$

and hence the proof follows.

  

Now, we just notice that the left inequality can be an equality only if

$$|A_1|+|A_2|+\dots |A_{k-1}|-k+2=|A_1+A_2+\cdots +A_{k-1}|=|A|$$

and

$$|A|+|B|-1=|A+B|.$$

The first relation implies that $A_1,\dots ,A_{k-1}$ and hence $A_1+\cdots +A_{k-1}=A$ are arithmetic progressions of same difference, and the second relation implies that $B$ is also an arithmetic progression of same difference. This completes the proof.

Corollary 3 : Let $A$ be a finite subset of $\mathbb{R}$. Then, for an integer $k\ge 2$, we have

$$k|A|-k+1\le |kA|\le |A{|}^k$$

and the lower bound is sharp iff $A$ is an arithmetic progression.

However, it should be noted that the upper bound in the last corollary is not sharp. The sharp upper bound is given by the following theorem.

Theorem 4 : Let $A$ be a finite subset of $\mathbb{R}$. Then,

$$|kA|\le (\genfrac{}{}{0ex}{}{|A|+k-1}{k})$$

for any integer $k\ge 1$.

Proof : The number of ways of choosing unordered $k$-tuples from a set of cardinality $|A|$ is the number of non-zero integer solutions of the equation

$$x_1+\cdots +x_{|A|}=k$$

which is $(\genfrac{}{}{0ex}{}{|A|+k-1}{k})$.

This upper bound is indeed sharp and the case $k=2$ of the sharp upper bound is called a Sidon set.

The moral of Corollary 3 is that if $A+A$ is smallest possible, then $A$ has a well defined structure, namely it is an arithmetic progression. We want to understand whether $A+A$ being small, say $\le C\left|A\right|$ still implies some structure in $A$. To do that, we investigate some examples now.

Clearly, if $A$ is a set of $r$ members of an arithmetic progression of length $2r$, then $A+A$ is part of an arithmetic progression of length $4r-1$ and hence $|A+A|\le 4r-1$.

Now, considering $A=\{0,1,\dots ,r-2,N\}$ for some $N>r-2$, we see that

$$A+A=\{0,1,\dots ,2r-4\}\cup \{N,N+1,\dots ,N+r-2\}\cup \{2N\}$$

and so, if $r-2<N\le 2r-4$, then $|A+A|=N+r\le 3r-4$, and if $N>2r-4$, then $|A+A|=3r-3$. The first one is an example of having $r$ members of an arithmetic progression of size $N+1$ ($\le 2r-3$) such that $|A+A|\le 3r-4$. And the second one is an example of the same where $|A+A|=3r-3$ but $A$ cannot be covered with any arithmetic progression of reasonable size.

And next, we consider

$$Q=\{a_0+a_1{n}_1+\cdots +a_d{n}_d:0\le n_j\le N_j,j=1,\dots ,d\}$$

where $a_0,a_1,\dots ,a_d$ are fixed, and $N_1,\dots ,N_d$ are integers $\ge 2$. This is a generalized arithmetic progression of dimension $\dim (Q)=d$ and volume $\mathrm{vol}(Q)=N_1\dots N_d$.

Obviously, $\left|Q\right|\le \mathrm{vol}(Q)$, and the equality holds only if all the elements are different in which case we call $Q$ to be proper.

It was Gregori Freiman in the 1960’s who recognized if $A+A$ is small, say $\le C\left|A\right|$, then $A$ still has a special structure, though not that strong. Freiman's theorem is one of the deepest results in the theory of sumsets and it is obligatory to state it in a discussion about Additive Combinatorics.

Theorem 5 (Freiman, Ruzsa) : If $A$ is a set of positive integers and $C\ge 2$ such that $|A+A|\le C\left|A\right|$, then there is a generalized AP, $Q$ with $A\subset Q$, $\mathrm{vol}(Q)\le F(C)\left|A\right|$ and $\dim (Q)\le d(C)$ for some functions $F(C)$ and $d(C)$.