Past exam of the mathematics course of the University of Cambridge / 2015 / iii / Paper 12 / 3 / Solution

An additive form of the Plünnecke inequality is the following. If $A,B$ are nonempty finite subsets of an abelian group and $|A+B|\le K|A|$, then there is one nonempty $X\subseteq A$ such that, simultaneously for every integer $m\ge 0$,Here $mB$ is an iterated sumset and $0B=\{0\}$. In particular, its Plünnecke-Ruzsa inequality consequence isWe prove both statements, so that the sumset and difference set formulations are covered.

Choose a nonempty $X\subseteq A$ minimizing the ratio $|X+B|/|X|$, and denote this minimum by $\kappa$. Such a minimizer exists because $A$ is finite, and $\kappa \le K$. Every $Z\subseteq X$ satisfies $|Z+B|\ge \kappa |Z|$, with the empty case also valid. We first prove the Petridis minimal-growth lemmafor every finite nonempty $C$.

List $C=\{c_1,\dots ,c_t\}$. Let $U_i=X+\{c_1,\dots ,c_i\}$ and $U_0=\varnothing$. DefineThe new points of $U_i$ are exactly $X_i+c_i$, so $|X+C|={\sum }_i|X_i|$. Since $Z_i+c_i\subseteq U_{i-1}$, the sumset $Z_i+B+c_i$ is already contained in $U_{i-1}+B$. It follows that the new points introduced into $U_i+B$ are contained inAs $Z_i+B\subseteq X+B$, their number is at mostSumming these increments proves the Petridis minimal-growth lemma. Taking $C=(m-1)B$ for $m\ge 1$ and iterating now givesThis proves the Plünnecke inequality with the same minimizing set $X$ for every $m$.

To obtain the difference set bound, we also prove the required Ruzsa triangle inequality. For finite $U,V,Z$ with $Z\ne \varnothing$, choose one representation $d=u_d-v_d$ of each $d\in U-V$. The mapis an injection: the sum of the output coordinates recovers $d$, and the first coordinate then recovers $z$ because $u_d$ was fixed. ThusUse $U=kB$, $V=\ell B$, and $Z=-X$. The already proved Plünnecke inequality yieldsThis finishes the proof of the stated Plünnecke-Ruzsa inequality. The use of an abelian group is essential in commuting the translates and sumsets in the minimal-growth argument.