Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 129 / 1 / i / Solution

The Plünnecke-Ruzsa inequality says that if $A,B$ are finite nonempty subsets of an abelian group andthen for all nonnegative integers $m,n$,

Choose a nonempty $X\subseteq A$ minimizingthen $K^{\prime }\le K$. We first prove the Petridis minimal-growth lemmafor every finite $C$, by induction on $|C|$. Remove $c\in C$, write $C^{\prime }=C\setminus \{c\}$, and letThe new points contributed to $X+C$ by $X+c$ are exactly $|X\setminus X^{\prime }|$. Moreover, $X^{\prime }+B+c\subseteq (X+B+c)\cap (X+B+C^{\prime })$, soThe induction hypothesis, the identity $|X+B|=K^{\prime }|X|$, and minimality, which gives $|X^{\prime }+B|\ge K^{\prime }|X^{\prime }|$, yieldIteration with $C=(r-1)B$ gives

Finally, the Ruzsa triangle inequality givesas required.