= Solution
We first prove the needed <Petridis minimal-growth lemma>. For finite nonempty <sets> $A,D$, choose a nonempty $X\subseteq A$ minimizing $K_0=|X+D|/|X|$. Thus $|Y+D|\geq K_0|Y|$ for every $Y\subseteq X$, including the empty <set>. For any finite $T=\{t_1,\ldots,t_r\}$, define
$$
X_i=\{x\in X:x+t_i\notin\bigcup_{j<i}(X+t_j)\}.
$$
The <sets> $X_i+t_i$ partition $X+T$. If $x\notin X_i$, then $x+t_i\in X+t_j$ for some $j<i$, and therefore $x+D+t_i\subseteq X+D+t_j$. The newly contributed portion of $X+D+t_i$ consequently has size at most
$$
|X+D|-|(X\setminus X_i)+D|\leq K_0|X_i|.
$$
Sum over $i$ to obtain $|X+D+T|\leq K_0|X+T|$. Apply this successively with $T=(r-1)D$ to get $|X+rD|\leq K_0^r|X|$.
Use $D=-A$. The hypothesis implies $K_0\leq|A-A|/|A|\leq C$, so $|X-2A|\leq C^2|X|$. We also prove the <Ruzsa triangle inequality>: for finite nonempty $U,V,W$,
$$
|U-W|\,|V|\leq|U-V|\,|V-W|.
$$
For each $s\in U-W$, fix $u_s,w_s$ with $s=u_s-w_s$. The map $(s,v)\mapsto(u_s-v,v-w_s)$ is injective: summing its coordinates recovers $s$, and then its first coordinate recovers $v$. This proves the inequality.
Apply it with $U=W=2A$ and $V=X$. Both right-hand factors have <cardinality> $|X-2A|$, giving
$$
|2A-2A|\leq\frac{|X-2A|^2}{|X|}\leq C^4|X|\leq C^4n.
$$
Thus $\boxed{K=C^4\text{ suffices}}$. This is the required case of the <Plünnecke-Ruzsa inequality>, proved here using the minimal-growth argument and the explicit injection. If $A$ is empty the conclusion holds directly.
Back to article page
