Plünnecke–Ruzsa inequality

Remarks

Petridis gave a short proof. Choose a nonempty $X \subseteq A$ that minimizes the ratio $\abs{X + B} / \abs{X}$, and call the minimum $K'$, so $K' \le K$. He showed that $\abs{X + B + C} \le K' \abs{X + C}$ for every finite set $C$, and induction gives $\abs{X + mB} \le K^m \abs{X}$. The Ruzsa triangle inequality then handles the differences. With $B = A$, a set with $\abs{A + A} \le K\abs{A}$ satisfies $\abs{mA - nA} \le K^{m+n}\abs{A}$, so small doubling controls all iterated sums. For $A = \set{1, \dots, N}$ one has $\abs{A + A} = 2N - 1 \le 2\abs{A}$, and indeed $\abs{mA - nA} \le (m + n)N \le 2^{m+n} N$.

Going deeper

For a student

The Plünnecke–Ruzsa inequality is a basic tool in additive combinatorics. It is used in the proof of Freiman's theorem. It is often combined with the Balog–Szemerédi–Gowers theorem. Plünnecke's original proof used a graph-theoretic argument with layered commutative graphs, and Ruzsa turned it into the form above.