Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 88 / 1

Assume $A$ is finite and nonempty; the empty case is immediate. Here $2A=A+A$. Choose a nonempty subset $X\subseteq A$ minimizingTaking $X=A$ as a competitor gives $K\le C$, and every subset $Y\subseteq X$ satisfies $|Y+A|\ge K|Y|$, including $Y=\varnothing$.

We first prove the Petridis minimal-growth lemma in the particular form needed: for every finite set $S$,List $S=\{s_1,\dots ,s_t\}$ and let $X_j$ consist of those $x\in X$ for which $x+s_j$ does not belong to an earlier translate $X+s_h$, $h<j$. The sets $X_j+s_j$ partition $X+S$, so $|X+S|={\sum }_j|X_j|$.

If $x\in X\setminus X_j$, then $x+s_j=x^{\prime }+s_h$ for some earlier $h$ and $x^{\prime }\in X$. Hence every point of $x+A+s_j$ already belongs to $X+A+s_h$. Therefore the new points contributed by $(X+A)+s_j$ are contained inTheir number is at mostSumming over $j$ proves the lemma. With $S=A$, it gives

We also prove the Ruzsa triangle inequality directly. For each $d\in U-V$, choose one representation $d=u_d-v_d$. The mapfrom $(U-V)\times X$ into $(X+U)\times (X+V)$ is injective: subtracting the output coordinates recovers $d$, after which either coordinate recovers $x$. Thus $|U-V||X|\le |X+U||X+V|$. Taking $U=V=2A$ now yieldsThis proves the required growth and difference set estimates directly.