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.
The following sumset notation is standard in additive combinatorics.
of an abelian group and a natural number
The most commonly cited version of the statement of the Plünnecke–Ruzsa inequality is the following.
are finite subsets of an abelian group and
In this case, the Plünnecke–Ruzsa inequality states that sumsets formed from a set with small doubling constant must also be small.
The version of this inequality that was originally proven by Plünnecke (1970)[1] is slightly weaker.
Theorem (Plünnecke's inequality) — Suppose
are finite subsets of an abelian group and
Its statement is: Theorem (Ruzsa triangle inequality) — If
The following simple proof of the Plünnecke–Ruzsa inequality is due to Petridis (2014).
be finite subsets of an abelian group
, Proof: This is demonstrated by induction on the size of
, so For the inductive step, assume the inequality holds for all
Hence, Putting the above two inequalities together gives This completes the proof of the lemma.
For inductive step, suppose this is true for
Finally, the Ruzsa triangle inequality gives Because
Plünnecke graphs are a way to capture the additive structure of the sets
is called semicommutative if, whenever there exist distinct
The canonical example of a Plünnecke graph is the following, which shows how the structure of the sets
by definition, so every vertex has outdegree equal to the size of
It can be similarly checked that the graph formed by reversing all edges of
In a Plünnecke graph, the image of a set
which can be reached by a path starting from some vertex in
, is then defined as the minimum factor by which the image of a set must exceed the size of the original set.
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