Introduction to Sumsets II

This is a sequel to a previous post. However, one can technically read it without reading the previous post.

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 := \underbrace{A+\dots A}_{k \text{ times}}$$

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

for $A,B\subseteq Z$.

Theorem 1 : We have

$$\left\vert A-C\right\vert \left\vert B\right\vert \le \left\vert A-B\right\vert \left\vert B-C\right\vert$$

where $A$, $B$ and $C$ are finite subset of $\mathbb R$.

Proof : For all $d\in A-C$, we fix the representation $d=a_d-c_d$ where $a_d\in A$ and $c_d\in C$. Now, we define

\begin{align*} &f:(A-C)\times B \to (A-B)\times (B-C)\\ &(d,b)\mapsto (a_d-b, b-c_d) \end{align*}

Note that if $f(x,y)=(u,v)$, then we must have $x=u+v$ and $y$ is determined by the equations $y=a_x-u$ and $y=c_x+v$. So, an image determines its unique inverse, that is, $f$ is injective.

This completes the proof.

Remark : Theorem 1 can be interpreted as a triangle inequality under the norm

$$\Delta(A,B)=\log\frac{\left\vert A-B\right\vert}{\sqrt{\left\vert A\right\vert\left\vert B\right\vert}}$$

although this definition of $\Delta$ is not really a distance as $\Delta(A,A)\neq 0$.

Putting $C=A$ and then $B=-A$ in Theorem 1 we have

Corollary 2 : For all $A,B\subset \mathbb R$, we have

\begin{align*} &\left\vert A-A\right\vert \le \frac{\left\vert A-B\right\vert^2}{\left\vert B\right\vert}\\ &\left\vert A-A\right\vert \le \frac{\left\vert A+A\right\vert^2}{\left\vert A\right\vert} \end{align*}

The last inequality basically says that if $A$ has small doubling, then $A-A$ is also small. Now, we want to show that $A-A$ being small also implies that $A+A$ is. For that, we proceed with

Lemma 3 : Let $A,B\subset \mathbb R$ be finite. If there is a $c>0$ so that

$$\left\vert A+B\right\vert =c\left\vert A\right\vert \qquad \text{and}\qquad \left\vert A^\prime +B\right\vert \ge c\left\vert A^\prime\right\vert\;\;\;\forall A^\prime \subset A,$$

then, we have

$$\left\vert A+B+C\right\vert \le c\left\vert A+C\right\vert$$

for any finite $C\subset \mathbb R$.

Proof : We use induction on the size of $C$. For $\left\vert C\right\vert =1$, i.e., $C=\{x\}$, we have

$$\left\vert A+B+x\right\vert =\left\vert A+B\right\vert =c\left\vert A\right\vert =c\left\vert A+x\right\vert$$

and hence the statement is trivial.

Now, let us assume that the statement is true for a non-empty set $C$, and define $C^\prime := C\cup \{x\}$ for some $x\notin C$. We define

$$A^\prime := \{a\in A : a+x\in A+C\} = A\cap (A+C-x)\subset A$$

so that

$$\left\vert A+C^\prime\right\vert =\left\vert A+C\right\vert +\left\vert A\right\vert -\left\vert A^\prime\right\vert$$

since $A^\prime +x=(A+x)\cap (A+C)$ and $A+C^\prime =(A+C)\cup (A+x)$.

Now, $A^\prime +x\subset A+C \implies A^\prime +B+x\subset A+B+C$ so that

$$A+B+C^\prime = (A+B+C)\cup (A+B+x) = (A+B+C)\cup \left [(A+B+x)\setminus (A^\prime +B+x)\right ]$$

and

$$\left\vert A+B+C^\prime\right\vert \le \left\vert A+B+C\right\vert + \left\vert A+B\right\vert - \left\vert A^\prime +B\right\vert$$

and hence, using the Induction Hypothesis, we have

$$\left\vert A+B+C^\prime\right\vert \le c\left\vert A+C\right\vert +c\left\vert A\right\vert -c\left\vert A^\prime\right\vert =c\left\vert A+C^\prime\right\vert$$

hence completing the proof.

This lemma will help us to prove the two following important consequences.

Theorem 4 : We have

$$\left\vert A+C\right\vert \left\vert B\right\vert \le \left\vert A+B\right\vert \left\vert B+C\right\vert$$

for all $A,B,C\subset \mathbb R$.

Proof : Let $U\subset B$ be such that $\frac{\left\vert U+A\right\vert}{\left\vert U\right\vert}=c$ is minimal. This implies

$$\left\vert U+A+C\right\vert \le c\left\vert U+C\right\vert$$

using the previous lemma.

Again, since $B$ itself is considered when the minimum is selected, we have $\left\vert A+C\right\vert \le \left\vert U+A+C\right\vert$, $\left\vert U+C\right\vert \le \left\vert B+C\right\vert$ and $c\le \frac{\left\vert A+B\right\vert}{\left\vert B\right\vert}$. These four inequalities complete the proof.

Corollary 5 : We have

\begin{align*} &\left\vert A+A\right\vert \le \frac{\left\vert A+B\right\vert^2}{\left\vert B\right\vert}\\ &\left\vert A+A\right\vert \le \frac{\left\vert A-A\right\vert^2}{\left\vert A\right\vert} \end{align*}

for all $A, B$.

Proof : Put $C=A$ and then $B=-A$ in the previous theorem.

Corollary 6 : We have

\begin{align*} &\left\vert A-B\right\vert \le \frac{\left\vert A+B\right\vert^3}{\left\vert A\right\vert \left\vert B\right\vert}\\ &\left\vert A+B\right\vert \le \frac{\left\vert A-B\right\vert^3}{\left\vert A\right\vert \left\vert B\right\vert} \end{align*}

for all $A,B$.

Proof : Use the previous corollary in Theorem 1 and then set $-B$ to $B$.

Corollary 7 : Let $A,B\subset \mathbb R$ be finite. If we have

$$\left\vert A+B\right\vert =c\left\vert A\right\vert \qquad \text{and}\qquad \left\vert A^\prime +B\right\vert \ge c\left\vert A^\prime\right\vert\;\;\;\forall A^\prime\subset A$$

for some $c>0$, then

$$\left\vert A+hB\right\vert \le c^h \left\vert A\right\vert$$

for all positive integers $h$.

Proof : Set $C=(h-1)B$ in Lemma 3 to get $\left\vert A+hB\right\vert \le c\left\vert A+(h-1)B\right\vert$ and use Induction.

Theorem 8 (Plünnecke-Ruzsa Inequality) : Let $B\subset \mathbb R$ be finite satisfying $\left\vert B+B\right\vert \le c\left\vert B\right\vert$ (or $\left\vert B-B\right\vert \le c\left\vert B\right\vert$). Then

$$\left\vert mB-nB\right\vert \le c^{m+n}\left\vert B\right\vert$$

for all $m,n\in \mathbb N$.

Proof : Let the non empty set $A\subset B$ (or $A\subset -B$) be one of the sets that minimizes $\frac{\left\vert A+B\right\vert}{\left\vert A\right\vert}$ so that $\left\vert A+B\right\vert =c^\prime \left\vert A\right\vert$. Obviously $c^\prime\le c$. Also, $\left\vert A^\prime +B\right\vert \le c^\prime \left\vert A^\prime\right\vert$ for all $A^\prime \subset A$ and hence the conditions of Corollary 7 are satisfied. This gives

$$\left\vert hB\right\vert \le \left\vert A+hB\right\vert \le (c^\prime)^h \left\vert A\right\vert \le c^h\left\vert B\right\vert$$

hence proving the statement for the case $m=0$ or $n=0$.

Now, if $m,n\neq 0$, we use Theorem 1 and set $A\mapsto mB$, $B\mapsto -A$ and $C\mapsto nB$ to get

$$\left\vert mB-nB\right\vert \left\vert A\right\vert \le \left\vert A+mB\right\vert \left\vert A+nB\right\vert \le (c^\prime)^m\left\vert A\right\vert (c^\prime)^n \left\vert A\right\vert \le c^{m+n}\left\vert B\right\vert \left\vert A\right\vert$$

hence completing the proof.

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 := \underbrace{A+\dots A}_{k \text{ times}}$$

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

for $A,B\subseteq Z$.

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

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

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<\dots <a_r\}$ and $B=\{b_1<b_2<\dots <b_s\}$, and noting that the following chain of inequalities

$$a_1+b_1<a_1+b_2<a_1+b_3<\dots <a_1+b_s<a_2+b_s<\dots <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<\dots <a_2+b_s<a_3+b_s<\dots <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{align*} 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{align*}

which on rearranging gives

\begin{align*} 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{align*}

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

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

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+\dots +A_{k-1}$ and $B=A_k$ so that $A+B=A_1+A_2+\dots +A_{k}$. Using the previous theorem and the Induction Hypothesis, we get

\begin{align*} \vert A_1\vert + \vert A_2\vert +\dots \vert A_{k-1}\vert -k+2 +\vert A_k\vert -1 &\le \vert A\vert + \vert B\vert -1\\ &\le \vert A+B\vert\\ &\le \vert A\vert \vert B\vert\\ &\le \vert A_1\vert \vert A_2\vert\dots \vert A_k\vert \end{align*}

and hence the proof follows.

  

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

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

and

$$\vert A\vert + \vert B\vert -1 = \vert A+B\vert.$$

The first relation implies that $A_1,\dots ,A_{k-1}$ and hence $A_1+\dots +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\vert A \vert -k+1\le \vert kA \vert\le \vert A \vert^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,

$$\vert kA \vert\le \binom{\vert A \vert +k-1}{k}$$

for any integer $k\ge 1$.

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

$$x_1+\dots +x_{\vert A \vert}=k$$

which is $\binom{\vert A \vert+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\vert A \right\vert$ 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 $\left\vert A+A \right\vert \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 $\left\vert A+A \right\vert = N + r \le 3r - 4$, and if $N > 2r - 4$, then $\left\vert A+A \right\vert = 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 $\left\vert A+A \right\vert \le 3r - 4$. And the second one is an example of the same where $\left\vert A+A \right\vert = 3r - 3$ but $A$ cannot be covered with any arithmetic progression of reasonable size.

And next, we consider

$$Q = \{a_0 + a_1n_1 + \dots + a_dn_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 $\operatorname{dim}(Q) = d$ and volume $\operatorname{vol}(Q) = N_1 \dots N_d$.

Obviously, $\left\vert Q \right\vert \le \operatorname{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\vert A \right\vert$, 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 $\left\vert A + A \right\vert \le C \left\vert A \right\vert$, then there is a generalized AP, $Q$ with $A \subset Q$, $\operatorname{vol}(Q) \le F(C) \left\vert A \right\vert$ and $\operatorname{dim}(Q) \le d(C)$ for some functions $F(C)$ and $d(C)$.