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 ${\displaystyle B}$, given that there is another set ${\displaystyle A}$ so that ${\displaystyle A+B}$ is not much larger than ${\displaystyle A}$. A slightly weaker version of this inequality was originally proven and published by Helmut Plünnecke (1970).[1] Imre Ruzsa (1989)[2] 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 ${\displaystyle A}$ and ${\displaystyle B}$ of an abelian group and a natural number ${\displaystyle k}$, the following are defined:

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

The set ${\displaystyle A+B}$ is known as the sumset of ${\displaystyle A}$ and ${\displaystyle B}$.

Plünnecke-Ruzsa inequality

The most commonly cited version of the statement of the Plünnecke-Ruzsa inequality is the following.[3]

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

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

This is often used when ${\displaystyle A=B}$, in which case the constant ${\displaystyle K=|2A|/|A|}$ is known as the doubling constant of ${\displaystyle 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)[1] is slightly weaker.

Theorem (Plünnecke's inequality) — Suppose ${\displaystyle A}$ and ${\displaystyle B}$ are finite subsets of an abelian group and ${\displaystyle K}$ is a constant so that ${\displaystyle |A+B|\leq K|A|}$. Then for all nonnegative integer ${\displaystyle m}$, ${\displaystyle |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 ${\displaystyle A}$, ${\displaystyle B}$, and ${\displaystyle C}$ are finite subsets of an abelian group, then

${\displaystyle |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).[4]

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

${\displaystyle |X+B+C|\leq K'|X+C|.}$

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

${\displaystyle |X+B+C|=|X+B|=K'|X|=K'|X+C|.}$

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

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

Hence, considering the sizes of the sets,

${\displaystyle {\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 ${\displaystyle Z}$ implies that ${\displaystyle Z\subseteq X\subseteq A}$, so by the definition of ${\displaystyle X}$, ${\displaystyle |Z+B|\geq K'|Z|}$. Thus, applying the inductive hypothesis on ${\displaystyle C'}$ and using the definition of ${\displaystyle X}$,

${\displaystyle {\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 ${\displaystyle W=\{x\in X:x+\gamma \in X+C'\}}$. Suppose ${\displaystyle y\in X+C'}$ and ${\displaystyle y\in X+\{\gamma \}}$, then there exists ${\displaystyle x\in X}$ such that ${\displaystyle x+\gamma =y\in X+C'}$. Thus, by definition, ${\displaystyle x\in W}$, so ${\displaystyle y\in W+\{\gamma \}}$. Hence, the sets ${\displaystyle X+C'}$ and ${\displaystyle (X+\{\gamma \})\backslash (W+\{\gamma \})}$ are disjoint. The definitions of ${\displaystyle W}$ and ${\displaystyle C'}$ thus imply that

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

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

${\displaystyle {\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

${\displaystyle |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 ${\displaystyle X}$ and ${\displaystyle K'}$ as in the statement of the lemma. It is first necessary to show that

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

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

${\displaystyle |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

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

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

${\displaystyle |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 ${\displaystyle A,A+B,A+2B,\dots }$ in a graph theoretic manner[5][6] First important to defining Plünnecke graphs is the notion of a commutative graph.

Definition. A directed graph ${\displaystyle G}$ is called semicommutative if, whenever there exist distinct ${\displaystyle x,y,z_{1},z_{2},\dots ,z_{k}}$ such that ${\displaystyle (x,y)}$ and ${\displaystyle (y,z_{i})}$ are edges in ${\displaystyle G}$ for each ${\displaystyle i}$, then there also exist distinct ${\displaystyle y_{1},y_{2},\dots ,y_{k}}$ so that ${\displaystyle (x,y_{i})}$ and ${\displaystyle (y_{i},z_{i})}$ are edges in ${\displaystyle G}$ for each ${\displaystyle i}$. ${\displaystyle 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 ${\displaystyle G}$ whose vertex set can be partitioned ${\displaystyle V_{0}\cup V_{1}\cup \dots \cup V_{m}}$ so that all edges in ${\displaystyle G}$ are from ${\displaystyle V_{i}}$ to ${\displaystyle V_{i+1}}$, for some ${\displaystyle 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 ${\displaystyle A,A+B,A+2B,\dots ,A+mB}$ is a case of that of a Plünnecke graph.

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

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

The magnification ratio between ${\displaystyle V_{0}}$ and ${\displaystyle V_{j}}$, denoted ${\displaystyle \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,

${\displaystyle \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 ${\displaystyle G}$ be a Plünnecke graph. Then, ${\displaystyle \mu _{j}(G)^{1/j}}$ is decreasing in ${\displaystyle 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.[5]

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 ${\displaystyle j=m}$ and ${\displaystyle j=1}$, yields that if ${\displaystyle |A+B|/|A|=K}$, then there exists ${\displaystyle X\subseteq A}$ so that ${\displaystyle |X+mB|/|X|\leq K^{m}}$. Applying this result once again with ${\displaystyle X}$ instead of ${\displaystyle A}$, there exists ${\displaystyle X'\subseteq X}$ so that ${\displaystyle |X'+nB|/|X'|\leq K^{m}}$. Then, by Ruzsa's triangle inequality (on ${\displaystyle -X',mB,nB}$),

${\displaystyle |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

References

1. Plünnecke, H. (1970). "Eine zahlentheoretische anwendung der graphtheorie". J. Reine Angew. Math. 243: 171–183.
2. Ruzsa, I. (1989). "An application of graph theory to additive number theory". Scientia, Ser. A. 3: 97–109.
3. Candela, P.; González-Sánchez, D.; de Roton, A. (2017). "A Plünnecke-Ruzsa inequality in compact abelian groups". arXiv:1712.07615 [math.CO].
4. Petridis, G. (2014). "The Plünnecke–Ruzsa Inequality: An Overview". Springer Proc. Math. Stat. Springer Proceedings in Mathematics & Statistics. 101: 229–241. doi:10.1007/978-1-4939-1601-6_16. ISBN 978-1-4939-1600-9.
5. Tao, T.; Vu, V. (2006). Additive Combinatorics. Cambridge: Cambridge University Press. ISBN 978-0-521-85386-6.
6. Ruzsa, I., Sumsets and structure (PDF).