Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 129 / 1

Choose a nonempty $X\subseteq A$ for which $|X+A|/|X|$ is minimal, and write this minimum as $K^{\prime }$. Since $X=A$ is an available choice, $K^{\prime }\le K$. The Petridis minimal-growth lemma givesfor every finite $C$. Taking $C=(t-1)A$ and iterating yieldsfor every integer $t\ge 1$.

Starting with $y_1=0$, choose $y_j\in A+A$ for as long asThe 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$, soLet $Y=\{y_1,\dots ,y_m\}$. Maximality says that, for each $z\in A+A$, more than half of the elements $x\in X$ satisfyfor some $y_i\in Y$. Given $z,z^{\prime }\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 thatSubtracting givesAs every element of $A+A-A-A$ is some $z-z^{\prime }$, this proves

In the vector space ${\mathbb{F}}_2^n$, addition and subtraction agree. Put $V=⟨Y⟩$, the vector subspace spanned by $Y$, andPart b gives $4A\subseteq 2A+V=H$. Conversely $2A\subseteq 4A$, because two copies of any fixed element of $A$ sum to zero. Henceand $0\in H$, so $H$ is a subgroup. For any $a_0\in A$, every $a\in A$ satisfies $a-a_0=a+a_0\in H$, and therefore $A\subseteq a_0+H$.

Because $y_1=0$, the dimension of a vector space $V$ is at most $|Y|-1\le 2K^2-2$. Consequentlywhere the last inequality uses $K\ge 1$. This is the requested bound.

Let $e_1,\dots ,e_m$ be the standard basis of ${\mathbb{F}}_2^m$ and takeIts sumset consists of zero, the $m$ basis vectors, and the $\left(\genfrac{}{}{0ex}{}{m}{2}\right)$ sums of two distinct basis vectors. ThusIf a coset $x+H$ contains $A_m$, then every difference of two elements of $A_m$ lies in $H$. In particular every $e_i$ lies in $H$, so $H={\mathbb{F}}_2^m$ andSince $m=2K_m+O(1)$, this ratio is eventually much larger than $K_m^{-1}{2}^{K_m}$. Hence no bound valid for all $K$ can replace the factor in part c by a function smaller than $K^{-1}{2}^K$.