= Solution
Starting with $y_1=0$, choose $y_j\in A+A$ for as long as
$$
\left|(X+y_j)\mathbin{\backslash}\bigcup_{i<j}(X+y_i)\right|\geq\frac12|X|.
$$
The union of these translates lies in $X+2A$, whose size is at most $K^2|X|$ by part a. The first translate contributes $|X|$, and every later translate contributes at least $|X|/2$, so
$$
|X|+(m-1)\frac{|X|}{2}\leq K^2|X|,
\qquad m\leq2K^2-1.
$$
Let $Y=\{y_1,\ldots,y_m\}$. Maximality says that, for each $z\in A+A$, more than half of the elements $x\in X$ satisfy
$$
x+z\in X+y_i
$$
for some $y_i\in Y$. Given $z,z'\in A+A$, the two corresponding subsets of $X$ each have more than $|X|/2$ elements, so they intersect. For an $x$ in their intersection there are $x_i,x_j\in X$ and $y_i,y_j\in Y$ such that
$$
x+z=x_i+y_i,
\qquad x+z'=x_j+y_j.
$$
Subtracting gives
$$
z-z'=x_i-x_j+y_i-y_j\in A-A+Y-Y.
$$
As every element of $A+A-A-A$ is some $z-z'$, this proves
$$
A+A-A-A\subseteq A-A+Y-Y.
$$
Back to article page
