= Solution
In the vector space $\mathbb F_2^n$, addition and subtraction agree. Put $V=\langle Y\rangle$, the <vector subspace> spanned by $Y$, and
$$
H=A+A+V.
$$
Part b gives $4A\subseteq2A+V=H$. Conversely $2A\subseteq4A$, because two copies of any fixed element of $A$ sum to zero. Hence
$$
H+H=4A+V\subseteq2A+V=H,
$$
and $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\leq2K^2-2$. Consequently
$$
|H|\leq|A+A|\,|V|
\leq K2^{2K^2-2}|A|
\leq K^2 2^{2K^2-2}|A|,
$$
where the last inequality uses $K\geq1$. This is the requested bound.
Back to article page
