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

For every $x\in B{C}^{-1}$, choose one representation $x=b_x{c}_x^{-1}$. DefineThe image determinesand the chosen representative then determines $a=(a{b}_x^{-1})b_x$. Thus $F$ is injective, and counting its domain and codomain proves the Noncommutative Ruzsa triangle inequality

Choose $a_0\in A$. Right multiplication by $a_0$ injects $A^2$ into $A^3$, soApply part i with anchor $A^{-1}$, $B=A$, and $C=A^2$. Since inversion preserves cardinality,Therefore $|A{A}^{-1}{A}^{-1}|\le K^2|A|$.

Apply part i again, now with anchor $A$, $B=A^2$, and $C=A^{-1}{A}^{-1}$. This givesThus $|A^4|\le K^3|A|$. Since $K\ge 1$, this proves the requested fourfold product bound from small tripling $|A^4|\le K^4|A|$.

Let $H$ be a finite group and form the free product $G=H\ast ⟨x⟩$. Put $A=H\cup \{x\}$. Thenso $|A^2|\le 3|H|+1<3|A|$.

On the other hand, $A^3$ contains the double coset $HxH$. Reduced-word uniqueness in the free product makes the mapinjective, so $|A^3|\ge |H{|}^2$. Taking finite groups $H$ of unbounded order keeps the doubling constant below three while $|A^3|/|A|$ tends to infinity. This realizes the small doubling does not control tripling in a noncommutative group phenomenon.

Take $x_1,x_2,x_3,x_4\in {\varphi }^{-1}(W)$ with $x_1+x_2=x_3+x_4$. Write $x_3=x_1+a$ and $x_4=x_1+b$; then $x_2=x_1+a+b$. Hencebelongs to $X$. All four values of $\varphi$ lie in the same affine subspace $W=V+w$, and their coefficients in $D$ sum to zero, so $D\in V$. The hypothesis $V\cap X=\{0\}$ gives $D=0$, precisely the additive-quadruple identity required of a Freiman homomorphism. This is the second-difference obstruction to a Freiman homomorphism.

Let $G_0={\mathbb{F}}_p^n$ and letFor each fixed first coordinate $d$, the second coordinates occurring in $\Gamma -\Gamma$ are values of $\varphi (x+d)-\varphi (x)$, of which there are at most $C$. ThereforeThe difference-set form of the Plünnecke-Ruzsa inequality now gives

Every $u\in X$ has the formso $\{0\}\times X\subseteq 2\Gamma -2\Gamma$. ConsequentlyThe set on the left has exactly $|X||\Gamma |$ elements, since its fiber over each $x$ is $\varphi (x)+X$. It follows thatand hence $|X|\le C^5$.

Choose $k$ so thatand take a uniformly random codimension-$k$ subspace $V\le {\mathbb{F}}_p^n$. Each fixed nonzero vector lies in $V$ with probability at most $p^{-k}$. The union bound givesThus some $V$ satisfies $V\cap X=\{0\}$.

For a uniformly random coset $W$ of this $V$, every value $\varphi (x)$ lies in $W$ with probability $p^{-k}$. Thereforeso some coset has inverse image $A$ of density at leastPart i says that $\varphi {|}_A$ is a Freiman homomorphism, proving the large Freiman-homomorphic restriction from bounded derivative images.

The finite-field Bogolyubov lemma states that if $A\subseteq G={\mathbb{F}}_p^n$ has density $\alpha$, then $2A-2A$ contains a subspace of codimension at most $2{\alpha }^{-2}$.

Use normalized Fourier analysis on a finite abelian group and put $f=1_A$. DefineBy Parseval identity,so $|S|\le 2{\alpha }^{-2}$. LetThen $V$ is a subspace of codimension at most $|S|$.

The normalized representation function of $2A-2A$ iswhere $\tilde{f}(x)=f(-x)$. For $x\in V$, all terms indexed by $S$ are nonnegative real numbers, whileThe trivial character alone contributes ${\alpha }^4$, so $r(x)>0$. Hence $x\in 2A-2A$, proving the Finite-field Bogolyubov lemma.

The hypothesis says that the additive energy satisfies $E(A)\ge c|A{|}^3$. The Balog-Szemerédi-Gowers theorem supplies $A^{\prime }\subseteq A$ withBy the Freiman-Ruzsa theorem over a finite field, $A^{\prime }$ lies in a subspace $H$ withThus $A^{\prime }$ has density at least $C_2^{-1}$ in $H$. Applying the Finite-field Bogolyubov lemma inside $H$ gives a subspaceof codimension bounded in terms of $c,p$ alone. Thereforewhich is the additive energy produces a large subspace in a fourfold difference set result.

The Ruzsa triangle inequality applied to $A-A$ also bounds $|A+A|$ in terms of $C|A|$, so $A$ has bounded doubling. The Freiman-Ruzsa theorem places $A$ inside a proper coset progression $P$ whose rank and ratio $|P|/|A|$ are bounded only in terms of $C$. Hence $A$ has positive density bounded in terms of $C$ inside a bounded-rank progression.

For sufficiently large $|A|$, the Szemerédi theorem in a bounded-rank coset progression gives a nontrivial three-term arithmetic progression in $A$. This proves the small difference set forces a three-term arithmetic progression assertion.

With normalized averages on the finite abelian group $G$, the Gowers U2 norm is defined byThe Gowers U3 norm is defined bywhere $\mathcal{C}$ denotes complex conjugation.

WriteApply the Cauchy-Schwarz inequality first in the variable carrying $f_1$ and then in the variable carrying $f_2$. After the invertible linear changes of variables permitted by $2,3\nmid |G|$, apply the assumed three-function $U^2$ estimate to the resulting multiplicative derivatives. The standard calculation givesBy the Derivative identity for the Gowers U3 norm, the last two factors are $\Vert f_3{\Vert }_{U^3}^8$ and $\Vert f_4{\Vert }_{U^3}^8$. Taking eighth roots proves

If $A\subseteq G$ has density $\alpha$, write $1_A=\alpha +f$. Expanding ${\Lambda }_4(1_A,1_A,1_A,1_A)$, the constant term is ${\alpha }^4$, and the displayed inequality bounds every nonconstant term after translation of one factor by a $U^3$ norm of the balanced function $f$. Thus sufficiently small $\Vert 1_A-\alpha {\Vert }_{U^3}$ makes the normalized number of four-term arithmetic progressions close to ${\alpha }^4$.

Put $M(a)={\max }_{\gamma \in \hat{G}}|\widehat{{\partial }_{a}f}(\gamma ){|}^2$. By the Derivative identity for the Gowers U3 norm, the Fourier formula for the $U^2$ norm, and Parseval identity,because $\Vert f{\Vert }_{\infty }\le 1$. Letand for every $a\in B$ choose $\varphi (a)\in \hat{G}$ attaining $M(a)$. Thenfor every $a\in B$, and deleting the complement of $B$ from the preceding average leaves total mass at least $c/2$.

Let ${\Gamma }_{\varphi }=\{(a,\varphi (a)):a\in B\}\subseteq G\times \hat{G}$. The box-norm inequality applied to the selected Fourier coefficients and the cocycle identity for multiplicative derivatives givesThe left side is at least $(c/2{)}^8$. An additive quadruple in ${\Gamma }_{\varphi }$ is exactly a tuple $(a,b,c,d)\in B^4$ satisfyingTherefore there are at least $(c/2{)}^8|G{|}^3$ such quadruples, which is the Frequency graph extracted from a large Gowers U3 norm.

Let $A\subseteq {\mathbb{F}}_5^n$ have density at least $\delta$ and put $f=1_A-\mathbb{E}{1}_A$. If $A$ has too few four-term progressions, part ii forces $\Vert f{\Vert }_{U^3}$ to be large. Part iii then produces a frequency graph with large additive energy. The Balog-Szemerédi-Gowers theorem extracts a large piece with small doubling, and a finite-field Freiman theorem makes the frequency selection approximately affine-linear there. Integrating these approximately linear derivative frequencies produces correlation of $f$ with a quadratic phase, as in the inverse theorem for the Gowers U3 norm over a finite field.

Restricting to a suitable level set of that quadratic phase produces a density increment on a structured affine subspace. Iterating these increments cannot continue indefinitely because density is at most one. Once $n$ is sufficiently large in terms of $\delta$, the iteration must instead terminate with the expected nontrivial four-term progression. This is the density-increment proof of the finite-field four-term progression theorem.