Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 129 / 4

The Finite-field Szemerédi theorem for four-term arithmetic progressions says that for every $\delta >0$ there is $N=N(\delta )$ such that, for every prime $p\ge 5$, whenever $|{\mathbb{F}}_p^n|\ge N$ and $A\subseteq {\mathbb{F}}_p^n$ has density at least $\delta$, there exist $x,d\in {\mathbb{F}}_p^n$ with $d\ne 0$ and

The Fourier density-increment proof of the Meshulam theorem controls three-term progressions through ordinary Fourier coefficients, equivalently the $U^2$ norm. Four-term progressions are controlled by the Gowers uniformity norm $U^3$. A function can have small correlation with every linear character while correlating strongly with a quadratic phase; such a function can have small $U^2$ norm but large $U^3$ norm. Ordinary Fourier uniformity therefore does not make the four-term progression count pseudorandom, and a large linear Fourier coefficient need not exist when that count is deficient. Quadratic or higher-order Fourier structure is needed.

For $s\in {\mathbb{F}}_p^n$, letThe number $T$ of ordered three-term arithmetic progressions in $A$ isBy the Cauchy-Schwarz inequality,The last sum is the additive energy of $A$, namely the number of additive quadruples. If $T\ge \eta |A{|}^2$, then

Part (iii) gives at least ${\eta }^2|A{|}^3$ additive quadruples. By the Balog-Szemerédi-Gowers theorem, there is $A^{\prime }\subseteq A$ withThe Freiman-Ruzsa theorem places $A^{\prime }$ in a coset progression $P$ whose rank is bounded in terms of $\eta$ and which satisfiesThus $A^{\prime }$ has density at least $C_1(\eta {)}^{-1}$ inside $P$.

The Szemerédi theorem in a bounded-rank coset progression says that, for fixed rank and density, every sufficiently large such progression has a nontrivial four-term progression in every subset of that density. If $|A|\ge C(\eta )$ for a sufficiently large $C(\eta )$, then $|P|\ge |A^{\prime }|\ge c(\eta )|A|$ crosses this threshold. It gives a nontrivial four-term progression in $A^{\prime }$, which is also contained in $A$. This proves the claim with a constant depending only on $\eta$.