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.