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

The Plünnecke-Ruzsa inequality says that if $A,B$ are finite nonempty subsets of an abelian group andthen for all nonnegative integers $m,n$,

Choose a nonempty $X\subseteq A$ minimizingthen $K^{\prime }\le K$. We first prove the Petridis minimal-growth lemmafor every finite $C$, by induction on $|C|$. Remove $c\in C$, write $C^{\prime }=C\setminus \{c\}$, and letThe new points contributed to $X+C$ by $X+c$ are exactly $|X\setminus X^{\prime }|$. Moreover, $X^{\prime }+B+c\subseteq (X+B+c)\cap (X+B+C^{\prime })$, soThe induction hypothesis, the identity $|X+B|=K^{\prime }|X|$, and minimality, which gives $|X^{\prime }+B|\ge K^{\prime }|X^{\prime }|$, yieldIteration with $C=(r-1)B$ gives

Finally, the Ruzsa triangle inequality givesas required.

Construct $X\subseteq B$ greedily. Begin with one element of $B$. While some $b\in B$ satisfiesadjoin $b$ to $X$. The first translate contributes $|A|$ points to $A+X$, and each later translate contributes at least $|A|/2$ new points. Thereforeand hence

When the process stops, every $b\in B$ satisfies $|(A+b)\cap (A+X)|>|A|/2$. Each point in this intersection has the formand therefore gives a triple $(x,a,a^{\prime })\in X\times A\times A$ with $b=a-a^{\prime }+x$. Distinct intersection points give distinct $a^{\prime }$, so there are more than $|A|/2$ such triples.

For $b,b^{\prime }\in B$, the corresponding sets of possible $a^{\prime }\in A$ both have size greater than $|A|/2$ and hence intersect. Using a common $a^{\prime }$ givesso $b-b^{\prime }=a-c+x-y$. Thus

Assume $|A+A|\le K|A|$ and putThis set is symmetric, contains zero, and the Plünnecke-Ruzsa inequality givesIt also contains $A-A$, so for every $x\in A$,

To control $H+H=4A-4A$, observe again by Plünnecke-Ruzsa thatApply the Ruzsa covering lemma with $S=H+H$ and $T=A$. There is a set $Y$ with $|Y|\le K^9$ such thatConsequently $H$ is a $K^9$-approximate group. Taking a sufficiently large absolute constant $C$ gives

Use normalized Fourier analysis on a finite abelian group. If $A\subseteq {\mathbb{F}}_2^n$ has density $\alpha$, its large spectrum at level $\rho >0$ isThe Chang theorem states that this spectrum is contained in a subspace of dimensionEquivalently, it is contained in the span of a dissociated set of that size.

Let $B={\mathbb{F}}_2^n\setminus (A+A)$ have density $\beta$. Since $1_A\ast 1_A$ vanishes on $B$,The zero-frequency contribution is ${\alpha }^2\beta$, soPut $\Gamma ={\mathrm{Spec}}_{\alpha /2}(1_B)$. Outside $\Gamma$, Parseval identity bounds the contribution byThereforebecause $|\widehat{1_B}(t)|\le \beta$. Chang's theorem places $\Gamma$ in a subspace $W$ of dimensionSet $V=W^{\perp }$. Then $V$ has this codimension, $V^{\perp }=W$, and adding the zero-frequency term $|\widehat{1_A}(0){|}^2={\alpha }^2$ gives

Let $H\le {\mathbb{F}}_2^n$ have dimension $k$. The valueis a multiple of $|H{|}^{-1}=2^{-k}$, and its average over $x$ is the density $\beta$ of $B$. If every coset of $H$ met $B$, then every value would be at least $2^{-k}$, forcing $\beta \ge 2^{-k}$. Thus $\beta <2^{-k}$ implies that some coset $x+H$ is disjoint from $B$, and therefore

If $\beta <2^{-k}$, part (iii) gives the first alternative. Otherwise $\log ({\beta }^{-1})\le k\log 2$, so part (ii) gives a subspace $V$ of codimension $O({\alpha }^{-2}k)$ withThe function $1_A\ast {\mu }_V$ is nonnegative and has mean $\alpha$. HenceIt follows that

Iterate part (iv) as a density increment. At a stage with ambient vector space of dimension $n_i$ and relative density ${\alpha }_i$, either the sumset contains a coset of a $k$-dimensional subspace, or there is a subspace of codimension $O({\alpha }_i^{-2}k)$ and a coset on which the density is at least $3{\alpha }_i/2$. Translate that coset back to the subspace. Since the ambient group has characteristic two, this translation does not alter the translated set's sumset.

The densities grow geometrically, so the iteration has $O(\log ({\alpha }^{-1}))$ stages, while the total codimension lost isChoose $k=\lfloor c{\alpha }^{2}n\rfloor$ with a sufficiently small absolute $c>0$. The total codimension is then less than $n-k$, so every stage still has ambient dimension at least $k$. The density cannot increase indefinitely beyond one; therefore the first alternative must occur. When $c{\alpha }^{2}n<1$, take the zero-dimensional subspace; this is the usual integer rounding implicit in the asymptotic dimension bound. Thusfor an absolute $C>0$.

One normalized form of the Croot-Sisask almost-periodicity theorem is as follows. If finite sets $A,S$ in a group satisfy $|A+S|\le K|A|$, $p\ge 2$, and $0<ϵ<1$, then for every function $f$ there is $T\subseteq S$ withsuch that

Apply the Croot-Sisask almost-periodicity theorem with the sampling set $A$, $S=G$, $f=1_{-A}$, and error $ϵ/k$. Since $A+G=G$, the doubling parameter is $K={\alpha }^{-1}$, and $\Vert 1_{-A}{\Vert }_p\le 1$. We obtain $X\subseteq G$ withsuch thatfor every $t\in X-X$. Every $x\in kX-kX$ is a sum of $k$ elements of $X-X$. Telescoping these $k$ shifts and using translation invariance and the triangle inequality for the Lp norm gives

Put $f=1_{-A}\ast {\mu }_A$. The probability measureis supported on $kY-kY$. Convolution by $\mu$ averages translates by points in this support, so convexity of the supremum norm givesThus

Choose $ϵ=1/6$ and a sufficiently large absolute constant $k$. Part (iii)'s size bound givesLetand choose a maximal dissociated set $\Lambda \subseteq \Gamma$. The entropy form of the Chang theorem givesand maximality gives $\Gamma \subseteq \mathrm{Span}(\Lambda )$.

Put $B=B(\Lambda ,1/(6|\Lambda |))$. If $y\in B$ and $\gamma \in \Gamma$, expressing $\gamma$ as a product of characters in $\Lambda$ and their inverses givesFor $f=1_{-A}\ast {\mu }_A$, Parseval identity givesAlso $\hat{\mu }(\gamma )=|\widehat{{\mu }_Y}(\gamma ){|}^{2k}$. Fourier inversion theorem therefore yieldsonce $k$ is large enough.

If $\Lambda$ is empty, interpret $B$ as $G$; the same Fourier estimate, using only the second term, is even stronger.

Part (iii) gives $\Vert f\ast \mu -f{\Vert }_{\infty }\le 1/6$. Applying this at $x$ and $x+y$ and using the last estimate givesFinally $f(0)=1$. Hence $f(y)\ge 1/3>0$ for every $y\in B$, while the support of $f$ is $A-A$. Consequently

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$.