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 an abelian 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 First important to defining Plünnecke graphs is the notion of a commutative graph.

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.

Now a Plünnecke graph is defined as follows.

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$. A Plünnecke graph is a layered graph which is commutative.

The relevant example of a Plünnecke graph is the following, showing how the structure of the sets $A,A+B,A+2B,\dots ,A+mB$ is a case of that of 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^{m}$. Then, by Ruzsa's triangle inequality (on $-X',mB,nB$),

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

thus proving the Plünnecke-Ruzsa inequality.

See also

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