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

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

for $A,B\subseteq Z$.

Theorem 1 : We have

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

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{array}{rl}& f:(A-C)\times B\to (A-B)\times (B-C)\\ & (d,b)\mapsto (a_d-b,b-c_d)\end{array}$$

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

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

although this definition of $\mathrm{\Delta }$ is not really a distance as $\mathrm{\Delta }(A,A)\ne 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{array}{rl}& |A-A|\le \frac{{|A-B|}^2}{\left|B\right|}\\ & |A-A|\le \frac{{|A+A|}^2}{\left|A\right|}\end{array}$$

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

$$|A+B|=c\left|A\right|\text{and}|A^{\prime }+B|\ge c\left|A^{\prime }\right|\mathrm{\forall }{A}^{\prime }\subset A,$$

then, we have

$$|A+B+C|\le c|A+C|$$

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

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

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

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

$$|A+C^{\prime }|=|A+C|+\left|A\right|-\left|A^{\prime }\right|$$

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⟹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 [(A+B+x)\setminus (A^{\prime }+B+x)]$$

and

$$|A+B+C^{\prime }|\le |A+B+C|+|A+B|-|A^{\prime }+B|$$

and hence, using the Induction Hypothesis, we have

$$|A+B+C^{\prime }|\le c|A+C|+c\left|A\right|-c\left|A^{\prime }\right|=c|A+C^{\prime }|$$

hence completing the proof.

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

Theorem 4 : We have

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

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

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

$$|U+A+C|\le c|U+C|$$

using the previous lemma.

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

Corollary 5 : We have

$$\begin{array}{rl}& |A+A|\le \frac{{|A+B|}^2}{\left|B\right|}\\ & |A+A|\le \frac{{|A-A|}^2}{\left|A\right|}\end{array}$$

for all $A,B$.

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

Corollary 6 : We have

$$\begin{array}{rl}& |A-B|\le \frac{{|A+B|}^3}{\left|A\right|\left|B\right|}\\ & |A+B|\le \frac{{|A-B|}^3}{\left|A\right|\left|B\right|}\end{array}$$

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

$$|A+B|=c\left|A\right|\text{and}|A^{\prime }+B|\ge c\left|A^{\prime }\right|\mathrm{\forall }{A}^{\prime }\subset A$$

for some $c>0$, then

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

for all positive integers $h$.

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

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

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

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{|A+B|}{\left|A\right|}$ so that $|A+B|=c^{\prime }\left|A\right|$. Obviously $c^{\prime }\le c$. Also, $|A^{\prime }+B|\le c^{\prime }\left|A^{\prime }\right|$ for all $A^{\prime }\subset A$ and hence the conditions of Corollary 7 are satisfied. This gives

$$\left|hB\right|\le |A+hB|\le (c^{\prime }{)}^h\left|A\right|\le c^h\left|B\right|$$

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

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

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

hence completing the proof.