Past exam of the mathematics course of the University of Cambridge / 2003 / iii / Paper 25 / 4 / ii / Solution

The graph form of Plünnecke inequality statesEquivalently these roots are nonincreasing along the layers. If $D_n=0$ the conclusion is immediate. Otherwise put $C=D_n^{1/n}$ and use the weighted cut lemma for commutative graphs proved in part (i). For a minimum endpoint cut $S_0\cup S_n$,The bottom layer is a cut of this weight. Comparing with $(V_0\setminus Z)\cup {\mathrm{Im}}^{(k)}Z$ gives $|{\mathrm{Im}}^{(k)}Z|\ge C^k|Z|$, as required. In an addition graph, $D_1\le K$ when $|A+B|\le K|A|$, so $D_m\le K^m$: some nonempty bottom subset has growth at most $K^m$ at height $m$.

The useful simultaneous sumset form says that a nonempty $X\subseteq A$ can be chosen with $|X+mB|\le K^m|X|$ for every $m$. To verify the common-subset assertion directly, choose $X$ minimizing $K^{\prime }=|X+B|/|X|$ among subsets of $A$. For a finite set $T=\{t_1,\dots ,t_s\}$, let $X_i$ consist of those $x\in X$ for which $x+t_i$ is a new point of $X+T$. The translated $X_i$ partition $X+T$. Points contributed by $(X\setminus X_i)+B+t_i$ are already present in earlier translates of $X+B$, so the new contribution at stage $i$ has size at mostThe inequality also holds when the complementary set is empty. Summing gives $|X+B+T|\le K^{\prime }|X+T|$. Taking $T=(m-1)B$ and iterating proves $|X+mB|\le (K^{\prime }{)}^m|X|\le K^m|X|$. This is the Petridis minimal-growth lemma calculation and supplies a single subset for all needed heights.