Past exam of the mathematics course of the University of Cambridge / 2001 / iii / Paper 76 / 3

The sumset form of Plünnecke's inequality states: for nonempty finite sets $A,B$ in an abelian group, if $|A+B|\le K|A|$, there is a nonempty $X\subseteq A$ such thatHere $0B=\{0\}$. The same $X$ can be used for every $m$. This sumset statement follows from an elementary minimal-growth argument.

Choose $X$ minimizing $\kappa =|X+B|/|X|$ among nonempty subsets of $A$. Then $\kappa \le K$ and $|Y+B|\ge \kappa |Y|$ for every $Y\subseteq X$, including the empty set. We prove the Petridis minimal-growth lemmafor each finite set $C$. Enumerate $C=\{c_1,\dots ,c_t\}$. Put $C_i=\{c_1,\dots ,c_i\}$ and defineThe disjoint new contributions to $X+C$ have sizes $|X_i|$, so $|X+C|={\sum }_i|X_i|$. For $y\in Y_i$, the point $y+c_i$ was already present in $X+C_{i-1}$, hence $y+B+c_i\subseteq X+B+C_{i-1}$. Consequently the new contribution at stage $i$ to $X+B+C$ has size at mostSumming proves the lemma. Starting with $C=\{0\}$ and then taking $C=(m-1)B$ gives inductively $|X+mB|\le {\kappa }^m|X|\le K^m|X|$, proving the stated Plünnecke inequality.

Apply Plünnecke's inequality with the summand set also equal to $A$. There is a nonempty $X\subseteq A$ satisfying $|X+mA|\le C^m|X|$ for every $m\ge 0$.

We need the Ruzsa triangle inequality in a form whose short proof also fixes the signs. For every $z\in R-S$, choose one representation $z=r_z-s_z$. The mapis injective into $(R+X)\times (S+X)$: its difference recovers $z$, then the fixed representation recovers $x$. ThereforeUse $R=rA$ and $S=sA$ and the common set $X$ from the previous part:ThusThe shared minimizing subset is important; applying separate growth estimates with unrelated subsets would not justify this bound.