= Solution
The <Freiman-Ruzsa theorem over a finite field> states that if $A\subseteq\mathbb F_p^n$ and $|A+A|\leq K|A|$, then $A$ is contained in a <vector subspace> $H$ with
$$
|H|\leq K^2p^{K^4}|A|.
$$
After translating $A$, assume $0\in A$. Put $S=A-A$, and choose $X\subseteq A+S$ maximal subject to the translates $x+A$, $x\in X$, being pairwise disjoint. Since $X+A\subseteq2A+S=3A-A$, the <Plünnecke-Ruzsa inequality> gives
$$
|X||A|=|X+A|\leq|3A-A|\leq K^4|A|,
$$
so $|X|\leq K^4$.
Maximality gives $A+S\subseteq X+S$: if $y\in A+S$ is not already in $X$, then $(y+A)\cap(x+A)\ne\varnothing$ for some $x\in X$, whence $y\in x+A-A=x+S$. Inductively, $mA+S\subseteq\langle X\rangle+S$ for every positive integer $m$. Because $0\in A$, every element of $\langle A\rangle$ belongs to some $mA$ in the finite vector space, and therefore
$$
H:=\langle A\rangle\subseteq\langle X\rangle+S.
$$
Finally, $|\langle X\rangle|\leq p^{|X|}$ and $|S|\leq K^2|A|$ by the Plünnecke-Ruzsa inequality, so
$$
|H|\leq p^{|X|}|S|\leq K^2p^{K^4}|A|.
$$
Back to article page
