Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 129 (Introduction to Additive Combinatorics)

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.

For $\Gamma \subseteq \hat{G}$ and $\rho >0$, the Bohr set isWriting $d=|\Gamma |$, the lower bound for the size of a Bohr set is

Solved by gpt-5.6-sol high.

Use normalized convolution and Fourier coefficients, and define the large spectrumBy the Parseval identity and $0\le f\le 1$,so $|\Gamma |\le {ϵ}^{-2}{\delta }^{-1}$.

The convolution theorem givesIf $y\in B(\Gamma ,ϵ)$, the part over $\Gamma$ is at mostbecause $|\hat{f}(\gamma )|\le \delta$. On the complementary spectrum, $|\hat{f}(\gamma )|<ϵ\delta$ and $|\gamma (y)-1|\le 2$, so the contribution is less than $2ϵ{\delta }^2$. The required difference is therefore less than $3ϵ{\delta }^2$.

Solved by gpt-5.6-sol high.

Apply the preceding Fourier argument to $f=1_A$, retaining the frequencies needed to make the oscillation of $1_A\ast 1_A\ast 1_A$ strictly smaller than its mean ${\alpha }^3$. The standard optimized cutoff gives a set $\Gamma \subseteq \hat{G}$ withsuch that the nonnegative function $F=1_A\ast 1_A\ast 1_A$ cannot fall from a maximal value to zero under any shift in $B(\Gamma ,\alpha )$. If $x$ maximizes $F$, thenThe support of a convolution of indicator functions is the corresponding sumset, so

Solved by gpt-5.6-sol high.

Write $d=|\Gamma |$ and identify each character with a residue $r_j\in \mathbb{Z}/N\mathbb{Z}$. Partition the $d$-dimensional torus into $Q^d$ cubes of side $1/Q$, where $Q$ is comparable to $N^{1/d}$. Applying the pigeonhole principle to the pointsgives a nonzero residue $q$ satisfyingConsequently $|e^{2\pi imq{r}_j/N}-1|\le \rho$ whenever $|m|\le \rho Q/(4\pi )$. After allowing for integer parts and the small values of $Q$, this produces the centered arithmetic progressionof length at least $\frac{1}{8}\rho N^{1/d}$.

Solved by gpt-5.6-sol high.

Part c gives $x+B(\Gamma ,\alpha )\subseteq A+A+A$ with $d=|\Gamma |\le 2{\alpha }^{-3}$. By the arithmetic progression in a cyclic Bohr set, $B(\Gamma ,\alpha )$ contains a centered progression of length at leastIts translate by $x$ is the required arithmetic progression in $A+A+A$.

Solved by gpt-5.6-sol high.

One standard normalized form of the Croot-Sisask almost-periodicity theorem is this. Let $A,S$ be finite subsets of an abelian group with $|A+S|\le K|A|$, let $q\ge 2$, let $0<ϵ<1$, and let $f$ be a complex function. There is $T\subseteq S$ withsuch that every $t\in T-T$ satisfies

For the proof, sample $k=O(q/{ϵ}^2)$ independent points of $A$ and approximate $1_A\ast f$ by the empirical average of the corresponding translates of $f$. A moment inequality bounds the expected $L^q$ error, so many samples are good. The small size of $A+S$ lets a translation and pigeonhole argument find many shifts in $S$ producing the same good approximation. Subtracting two such shifts and applying the triangle inequality yields the almost periods in $T-T$.

Solved by gpt-5.6-sol high.

Apply the assumed finite-field character approximation with error $ϵ/2$. We obtain $k\le 4q/{ϵ}^2$ characters ${\gamma }_i$ and a functionsuch that $\Vert f-P{\Vert }_{L^q}\le (ϵ/2)\Vert \hat{f}{\Vert }_{{\ell }^1}$. LetEach character has a kernel of codimension at most one, so $\mathrm{codim}W\le k\le 4q/{ϵ}^2$. For $x\in W$, ${\tau }_{x}P=P$, and translation invariance of the $L^q$ norm gives

Solved by gpt-5.6-sol high.

Put $F=1_A\ast 1_A$. Then $0\le F\le 1$, $\mathbb{E}F={\alpha }^2$, and the Parseval identity givesSet $d=\lfloor {\alpha }^{2}n/(8p^2)\rfloor$. If $d<2$, the asserted integer lower bound is trivial. Otherwise take $q=d$ and $ϵ=3\alpha /(4p)$ in part b. The resulting subspace $W$ hasThus $\dim W\ge n/9>d$, and we may choose a $d$-dimensional subspace $D\le W$.

For $x\in D$, part b givesApply the supplied maximal inequality to $g(x,y)=F(y+x)-F(y)$. Since $|D{|}^{1/q}=p$, it givesHence some $y$ satisfies $F(y)>su{p}_{x\in D}|F(y+x)-F(y)|$, so $F(y+x)>0$ for every $x\in D$. Since $\mathrm{supp}F=A+A$, this proves

Solved by gpt-5.6-sol high.

For functions $(f_{ϵ}{)}_{ϵ\in \{0,1{\}}^3}$ on ${\mathbb{F}}_p^n$, the Gowers inner product iswhere $\mathcal{C}$ is the complex conjugate operator. The Gowers uniformity norm isThe Gowers-Cauchy-Schwarz inequality states

Solved by gpt-5.6-sol high.

Repeated Cauchy-Schwarz inequality shows that the $U^3$ norm dominates the absolute mean of a function:Taking $f=1_A$ and using $\mathbb{E}{1}_A=\alpha$ gives

Solved by gpt-5.6-sol high.

For $h(x)=e_p(q(x))$, the product in the $U^3$ cube average isThe expression in parentheses is the third additive derivative of the quadratic form $q$, so it vanishes. Every cube contributes one and therefore the quadratic phase satisfies

Solved by gpt-5.6-sol high.

Apply the Cauchy-Schwarz inequality successively in the three shift variables to the correlation with the quadratic phase $h$. At the third step the third additive derivative of its phase vanishes, leavingThus $|⟨f,h⟩|\ge \delta$ implies

Solved by gpt-5.6-sol high.

Expand the $U^3$ cube product forWhenever all eight $x$-vertices of the cube lie in $S$, the Freiman homomorphism property makes every second additive derivative of $\varphi$ vanish. Consequently the coefficients of $y$ and of each of the three $y$-direction increments in the phase cancel, so the phase product around the cube is one. It follows thatPart b(i), applied to $S$, now givesSince $|g|\le 1$, one can apply the inverse theorem for the Gowers U3 norm over a finite field: $g$ has nontrivial correlation, quantitatively in $p$ and $\sigma$, with a quadratic phase on ${\mathbb{F}}_p^{n+N}$.

Solved by gpt-5.6-sol high.