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

The Freiman-Ruzsa theorem over a finite field states that if $A\subseteq {\mathbb{F}}_p^n$ and $|A+A|\le K|A|$, then $A$ is contained in a vector subspace $H$ withAfter 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\subseteq 2A+S=3A-A$, the Plünnecke-Ruzsa inequality givesso $|X|\le 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 ⟨X⟩+S$ for every positive integer $m$. Because $0\in A$, every element of $⟨A⟩$ belongs to some $mA$ in the finite vector space, and thereforeFinally, $|⟨X⟩|\le p^{|X|}$ and $|S|\le K^2|A|$ by the Plünnecke-Ruzsa inequality, so

Solved by gpt-5.6-sol high.

Let $H\le {\mathbb{F}}_p^n$ be a subspace with $|H|$ much larger than $K^2$, and choose linearly independent vectors $e_1,\dots ,e_{K-1}$ whose images are independent modulo $H$. SetThen $|A|=|H|+K-1\sim |H|$, while $A+A$ is the union of $H$, the $K-1$ disjoint cosets $e_i+H$, and at most $K^2$ exceptional sums $e_i+e_j$. HenceEvery subspace containing $A$ must contain $H$ and all $e_i$, so it has at least $p^{K-1}|H|\sim p^{K-1}|A|$ elements. Thus the exponential dependence on $K$ in the Freiman-Ruzsa theorem over a finite field cannot in general be replaced by a subexponential one.

Solved by gpt-5.6-sol high.

The hypothesis says that the normalized additive energy of $A$ is at least $\eta$. By the Balog-Szemerédi-Gowers theorem, for an absolute $C_0$ there is $A^{\prime }\subseteq A$ such thatThe finite-field Bogolyubov-Ruzsa consequence of the Freiman-Ruzsa theorem over a finite field says that a set of doubling at most $K$ has a vector subspacewith $|V|\ge p^{-K^{C_1}}|A^{\prime }|$ for an absolute $C_1$. Taking $K={\eta }^{-C_0}$ and enlarging the absolute exponent givesThis is an energy form of the Bogolyubov lemma: the usual lemma assumes positive density in an ambient group, whereas the Balog-Szemerédi-Gowers theorem first extracts a dense structured model from the many additive quadruples. The resulting bound depends on the energy parameter rather than on the possibly tiny ambient density of $A$.

Solved by gpt-5.6-sol high.