= Solution
The <Plünnecke-Ruzsa inequality> says that if $A,B$ are finite nonempty subsets of an <abelian group> and
$$
|A+B|\le K|A|,
$$
then for all nonnegative integers $m,n$,
$$
\boxed{|mB-nB|\le K^{m+n}|A|.}
$$
Choose a nonempty $X\subseteq A$ minimizing
$$
K'=\frac{|X+B|}{|X|};
$$
then $K'\le K$. We first prove the <Petridis minimal-growth lemma>
$$
|X+B+C|\le K'|X+C|
$$
for every finite $C$, by induction on $|C|$. Remove $c\in C$, write $C'=C\setminus\{c\}$, and let
$$
X'={x\in X:x+c\in X+C'}.
$$
The new points contributed to $X+C$ by $X+c$ are exactly $|X\setminus X'|$. Moreover, $X'+B+c\subseteq(X+B+c)\cap(X+B+C')$, so
$$
|X+B+C|
\le |X+B+C'|+|X+B|-|X'+B|.
$$
The induction hypothesis, the identity $|X+B|=K'|X|$, and minimality, which gives $|X'+B|\ge K'|X'|$, yield
$$
|X+B+C|\le K'|X+C'|+K'|X|-K'|X'|=K'|X+C|.
$$
Iteration with $C=(r-1)B$ gives
$$
|X+rB|\le (K')^r|X|\le K^r|X|.
$$
Finally, the <Ruzsa triangle inequality> gives
$$
|mB-nB|le\frac{|X+mB|\,|X+nB|}{|X|}
\le K^{m+n}|X|le K^{m+n}|A|,
$$
as required.
Back to article page
