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

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.