Plünnecke–Ruzsa inequality

In additive combinatorics, the Plünnecke–Ruzsa inequality is an inequality that bounds the size of various sumsets of a set $B$, given that there is another set $A$ so that $A+B$ is not much larger than $A$. A slightly weaker version of this inequality was originally proven and published by Helmut Plünnecke (1970). Imre Ruzsa (1989) later published a simpler proof of the current, more general, version of the inequality. The inequality forms a crucial step in the proof of Freiman's theorem.

Statement

The following sumset notation is standard in additive combinatorics. For subsets $A$ and $B$ of an abelian group and a natural number $k$, the following are defined:

• $A+B=\{a+b:a\in A,b\in B\}$
• $A-B=\{a-b:a\in A,b\in B\}$
• $kA=\underbrace {A+A+\cdots +A} _{k{\text{ times}}}$

The set $A+B$ is known as the sumset of $A$ and $B$.

Plünnecke-Ruzsa inequality

The most commonly cited version of the statement of the Plünnecke–Ruzsa inequality is the following.

Theorem (Plünnecke-Ruzsa inequality) — If $A$ and $B$ are finite subsets of an abelian group and $K$ is a constant so that $|A+B|\leq K|A|$, then for all nonnegative integers $m$ and $n$,

$|mB-nB|\leq K^{m+n}|A|.$

This is often used when $A=B$, in which case the constant $K=|2A|/|A|$ is known as the doubling constant of $A$. In this case, the Plünnecke–Ruzsa inequality states that sumsets formed from a set with small doubling constant must also be small.

Plünnecke's inequality

The version of this inequality that was originally proven by Plünnecke (1970) is slightly weaker.

Theorem (Plünnecke's inequality) — Suppose $A$ and $B$ are finite subsets of an abelian group and $K$ is a constant so that $|A+B|\leq K|A|$. Then for all nonnegative integer $m$, $|mB|\leq K^{m}|A|.$

Proof

Ruzsa triangle inequality

Main article: Ruzsa triangle inequality

The Ruzsa triangle inequality is an important tool which is used to generalize Plünnecke's inequality to the Plünnecke–Ruzsa inequality. Its statement is:

Theorem (Ruzsa triangle inequality) — If $A$, $B$, and $C$ are finite subsets of a group, then

$|A||B-C|\leq |A-B||A-C|.$

Proof of Plünnecke-Ruzsa inequality

The following simple proof of the Plünnecke–Ruzsa inequality is due to Petridis (2014).

Lemma: Let $A$ and $B$ be finite subsets of an abelian group $G$. If $X\subseteq A$ is a nonempty subset that minimizes the value of $K'=|X+B|/|X|$, then for all finite subsets $C\subset G$,

$|X+B+C|\leq K'|X+C|.$

Proof: This is demonstrated by induction on the size of $|C|$. For the base case of $|C|=1$, note that $S+C$ is simply a translation of $S$ for any $S\subseteq G$, so

$|X+B+C|=|X+B|=K'|X|=K'|X+C|.$

For the inductive step, assume the inequality holds for all $C\subseteq G$ with $|C|\leq n$ for some positive integer $n$. Let $C$ be a subset of $G$ with $|C|=n+1$, and let $C=C'\sqcup \{\gamma \}$ for some $\gamma \in C$. (In particular, the inequality holds for $C'$.) Finally, let $Z=\{x\in X:x+B+\{\gamma \}\subseteq X+B+C'\}$. The definition of $Z$ implies that $Z+B+\{\gamma \}\subseteq X+B+C'$. Thus, by the definition of these sets,

$X+B+C=(X+B+C')\cup ((X+B+\{\gamma \})\backslash (Z+B+\{\gamma \})).$

Hence, considering the sizes of the sets,

${\begin{aligned}|X+B+C|&\leq |X+B+C'|+|(X+B+\{\gamma \})\backslash (Z+B+\{\gamma \})|\\&=|X+B+C'|+|X+B+\{\gamma \}|-|Z+B+\{\gamma \}|\\&=|X+B+C'|+|X+B|-|Z+B|.\end{aligned}}$

The definition of $Z$ implies that $Z\subseteq X\subseteq A$, so by the definition of $X$, $|Z+B|\geq K'|Z|$. Thus, applying the inductive hypothesis on $C'$ and using the definition of $X$,

${\begin{aligned}|X+B+C|&\leq |X+B+C'|+|X+B|-|Z+B|\\&\leq K'|X+C'|+|X+B|-|Z+B|\\&\leq K'|X+C'|+K'|X|-|Z+B|\\&\leq K'|X+C'|+K'|X|-K'|Z|\\&=K'(|X+C'|+|X|-|Z|).\end{aligned}}$

To bound the right side of this inequality, let $W=\{x\in X:x+\gamma \in X+C'\}$. Suppose $y\in X+C'$ and $y\in X+\{\gamma \}$, then there exists $x\in X$ such that $x+\gamma =y\in X+C'$. Thus, by definition, $x\in W$, so $y\in W+\{\gamma \}$. Hence, the sets $X+C'$ and $(X+\{\gamma \})\backslash (W+\{\gamma \})$ are disjoint. The definitions of $W$ and $C'$ thus imply that

$X+C=(X+C')\sqcup ((X+\{\gamma \})\backslash (W+\{\gamma \})).$

Again by definition, $W\subseteq Z$, so $|W|\leq |Z|$. Hence,

${\begin{aligned}|X+C|&=|X+C'|+|(X+\{\gamma \})\backslash (W+\{\gamma \})|\\&=|X+C'|+|X+\{\gamma \}|-|W+\{\gamma \}|\\&=|X+C'|+|X|-|W|\\&\geq |X+C'|+|X|-|Z|.\end{aligned}}$

Putting the above two inequalities together gives

$|X+B+C|\leq K'(|X+C'|+|X|-|Z|)\leq K'|X+C|.$

This completes the proof of the lemma.

To prove the Plünnecke–Ruzsa inequality, take $X$ and $K'$ as in the statement of the lemma. It is first necessary to show that

$|X+nB|\leq K^{n}|X|.$

This can be proved by induction. For the base case, the definitions of $K$ and $K'$ imply that $K'\leq K$. Thus, the definition of $X$ implies that $|X+B|\leq K|X|$. For inductive step, suppose this is true for $n=j$. Applying the lemma with $C=jB$ and the inductive hypothesis gives

$|X+(j+1)B|\leq K'|X+jB|\leq K|X+jB|\leq K^{j+1}|X|.$

This completes the induction. Finally, the Ruzsa triangle inequality gives

$|mB-nB|\leq {\frac {|X+mB||X+nB|}{|X|}}\leq {\frac {K^{m}|X|K^{n}|X|}{|X|}}=K^{m+n}|X|.$

Because $X\subseteq A$, it must be the case that $|X|\leq |A|$. Therefore,

$|mB-nB|\leq K^{m+n}|A|.$

This completes the proof of the Plünnecke–Ruzsa inequality.

Plünnecke graphs

Both Plünnecke's proof of Plünnecke's inequality and Ruzsa's original proof of the Plünnecke–Ruzsa inequality use the method of Plünnecke graphs. Plünnecke graphs are a way to capture the additive structure of the sets $A,A+B,A+2B,\dots$ in a graph theoretic manner

To define a Plünnecke graph we first define commutative graphs and layered graphs:

Definition. A directed graph $G$ is called semicommutative if, whenever there exist distinct $x,y,z_{1},z_{2},\dots ,z_{k}$ such that $(x,y)$ and $(y,z_{i})$ are edges in $G$ for each $i$, then there also exist distinct $y_{1},y_{2},\dots ,y_{k}$ so that $(x,y_{i})$ and $(y_{i},z_{i})$ are edges in $G$ for each $i$.

$G$ is called commutative if it is semicommutative and the graph formed by reversing all its edges is also semicommutative.

Definition. A layered graph is a (directed) graph $G$ whose vertex set can be partitioned $V_{0}\cup V_{1}\cup \dots \cup V_{m}$ so that all edges in $G$ are from $V_{i}$ to $V_{i+1}$, for some $i$.

Definition. A Plünnecke graph is a layered graph which is commutative.

The canonical example of a Plünnecke graph is the following, which shows how the structure of the sets $A,A+B,A+2B,\dots ,A+mB$ form a Plünnecke graph.

Example. Let $A,B$ be subsets of an abelian group. Then, let $G$ be the layered graph so that each layer $V_{j}$ is a copy of $A+jB$, so that $V_{0}=A$, $V_{1}=A+B$, ..., $V_{m}=A+mB$. Create the edge $(x,y)$ (where $x\in V_{i}$ and $y\in V_{i+1}$) whenever there exists $b\in B$ such that $y=x+b$. (In particular, if $x\in V_{i}$, then $x+b\in V_{i+1}$ by definition, so every vertex has outdegree equal to the size of $B$.) Then $G$ is a Plünnecke graph. For example, to check that $G$ is semicommutative, if $(x,y)$ and $(y,z_{i})$ are edges in $G$ for each $i$, then $y-x,z_{i}-y\in B$. Then, let $y_{i}=x+z_{i}-y$, so that $y_{i}-x=z_{i}-y\in B$ and $z_{i}-y_{i}=y-x\in B$. Thus, $G$ is semicommutative. It can be similarly checked that the graph formed by reversing all edges of $G$ is also semicommutative, so $G$ is a Plünnecke graph.

In a Plünnecke graph, the image of a set $X\subseteq V_{0}$ in $V_{j}$, written ${\text{im}}(X,V_{j})$, is defined to be the set of vertices in $V_{j}$ which can be reached by a path starting from some vertex in $X$. In particular, in the aforementioned example, ${\text{im}}(X,V_{j})$ is just $X+jB$.

The magnification ratio between $V_{0}$ and $V_{j}$, denoted $\mu _{j}(G)$, is then defined as the minimum factor by which the image of a set must exceed the size of the original set. Formally,

$\mu _{j}(G)=\min _{X\subseteq V_{0},X\neq \emptyset }{\frac {|{\text{im}}(X,V_{j})|}{|X|}}.$

Plünnecke's theorem is the following statement about Plünnecke graphs.

Theorem (Plünnecke's theorem) — Let $G$ be a Plünnecke graph. Then, $\mu _{j}(G)^{1/j}$ is decreasing in $j$.

The proof of Plünnecke's theorem involves a technique known as the "tensor product trick", in addition to an application of Menger's theorem.

The Plünnecke–Ruzsa inequality is a fairly direct consequence of Plünnecke's theorem and the Ruzsa triangle inequality. Applying Plünnecke's theorem to the graph given in the example, at $j=m$ and $j=1$, yields that if $|A+B|/|A|=K$, then there exists $X\subseteq A$ so that $|X+mB|/|X|\leq K^{m}$. Applying this result once again with $X$ instead of $A$, there exists $X'\subseteq X$ so that $|X'+nB|/|X'|\leq K^{n}$. Then, by Ruzsa's triangle inequality (on $-X',mB,nB$),

$|mB-nB|\leq |X'+mB||X'+nB|/|X'|\leq K^{m}|X|K^{n}=K^{m+n}|X|,$

thus proving the Plünnecke–Ruzsa inequality.

See also

• Additive combinatorics
• Freiman's theorem
• Ruzsa triangle inequality