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

Choose a nonempty $X\subseteq A$ for which $|X+A|/|X|$ is minimal, and write this minimum as $K^{\prime }$. Since $X=A$ is an available choice, $K^{\prime }\le K$. The Petridis minimal-growth lemma givesfor every finite $C$. Taking $C=(t-1)A$ and iterating yieldsfor every integer $t\ge 1$.

Starting with $y_1=0$, choose $y_j\in A+A$ for as long asThe union of these translates lies in $X+2A$, whose size is at most $K^2|X|$ by part a. The first translate contributes $|X|$, and every later translate contributes at least $|X|/2$, soLet $Y=\{y_1,\dots ,y_m\}$. Maximality says that, for each $z\in A+A$, more than half of the elements $x\in X$ satisfyfor some $y_i\in Y$. Given $z,z^{\prime }\in A+A$, the two corresponding subsets of $X$ each have more than $|X|/2$ elements, so they intersect. For an $x$ in their intersection there are $x_i,x_j\in X$ and $y_i,y_j\in Y$ such thatSubtracting givesAs every element of $A+A-A-A$ is some $z-z^{\prime }$, this proves

In the vector space ${\mathbb{F}}_2^n$, addition and subtraction agree. Put $V=⟨Y⟩$, the vector subspace spanned by $Y$, andPart b gives $4A\subseteq 2A+V=H$. Conversely $2A\subseteq 4A$, because two copies of any fixed element of $A$ sum to zero. Henceand $0\in H$, so $H$ is a subgroup. For any $a_0\in A$, every $a\in A$ satisfies $a-a_0=a+a_0\in H$, and therefore $A\subseteq a_0+H$.

Because $y_1=0$, the dimension of a vector space $V$ is at most $|Y|-1\le 2K^2-2$. Consequentlywhere the last inequality uses $K\ge 1$. This is the requested bound.

Let $e_1,\dots ,e_m$ be the standard basis of ${\mathbb{F}}_2^m$ and takeIts sumset consists of zero, the $m$ basis vectors, and the $\left(\genfrac{}{}{0ex}{}{m}{2}\right)$ sums of two distinct basis vectors. ThusIf a coset $x+H$ contains $A_m$, then every difference of two elements of $A_m$ lies in $H$. In particular every $e_i$ lies in $H$, so $H={\mathbb{F}}_2^m$ andSince $m=2K_m+O(1)$, this ratio is eventually much larger than $K_m^{-1}{2}^{K_m}$. Hence no bound valid for all $K$ can replace the factor in part c by a function smaller than $K^{-1}{2}^K$.

Writing $\hat{G}$ for the character group of a finite abelian group, the Bohr set with frequency set $\Gamma \subseteq \hat{G}$ and width $0\le \rho \le 2$ isIts rank is $|\Gamma |$.

For $B=B(\Gamma ,\rho )$ write $B_{1+\kappa }=B(\Gamma ,(1+\kappa )\rho )$. It is a Regular Bohr set whenwhenever $d=|\Gamma |$ and $|\kappa |\le c/d$, with absolute constants in the $O$-term and in $c$.

Not every width is regular. In $G=\mathbb{Z}/3\mathbb{Z}$, let $\gamma (x)=e^{2\pi ix/3}$ and take $\rho =\sqrt{3}$. Then $B(\{\gamma \},\rho )=G$, but every arbitrarily small decrease of the width leaves only $0$. The size jumps from three to one, contradicting the required linear control as $\kappa \to 0^{-}$.

Choose a Regular Bohr set $B^{\prime }=B_{\lambda }\subseteq B$ with $1/2\le \lambda \le 1$. Standard Bohr-set size estimates give $|B^{\prime }|\ge 2^{-O(d)}|B|$. Set $\eta =c_0/d$ with $c_0$ small enough that regularity givesFor each $z\in B_{\eta }^{\prime }$ and $y\in B_{1-\eta }^{\prime }$, the triangle inequality in every frequency givesBecause $|G|$ is odd, multiplication by two is a bijection, and the pair $(z,y)$ determines the ordered three-term arithmetic progression uniquely. The lower size bound for a Dilate of a Bohr set givesThe number of progressions in $B$ is therefore at least

The Bourgain bound for three-term-progression-free sets states that, if $N=|G|$ is odd and $A\subseteq G$ contains no nonconstant three-term arithmetic progression, then

Here is how it follows from the standard Bohr-set density increment lemma. Begin with $B_0=G$ and relative density ${\alpha }_0=\alpha =|A|/N$. Whenever the lemma gives its second alternative, replace the current set by the denser translate inside the smaller regular Bohr set. The density changes byso this can happen only $O({\alpha }^{-1})$ times. Throughout the iteration the rank is $O({\alpha }^{-1})$, the width is at least ${\alpha }^{O({\alpha }^{-1})}$, and the elementary lower bound for the size of a Bohr set givesAt the terminal stage the first alternative of the density-increment lemma holds. Combining it with the last display yieldsIf $\alpha <1/\log N$, Bourgain's bound is already true. Otherwise $\log (1/\alpha )\ll \log \log N$, and rearranging proves

For the counting-measure Lp norm, defineThis is the set of Lp almost periods of $f$ with exponent $p=2m$ and error $X$.

Put $N=p^n$, $\alpha =|A|/N$, and use normalized Fourier analysis on a finite abelian group. If $F=1_A\ast 1_A$ denotes unnormalized convolution and $h=N^{-1}F$, thenby the Parseval identity.

Sample $k=O(m{\epsilon }^{-2})$ characters independently, choosing $\gamma$ with probability $|\hat{h}(\gamma )|/\alpha$, and attach the phase of $\hat{h}(\gamma )$ to the sampled character. The Marcinkiewicz–Zygmund inequality, followed by averaging over $x$, shows that some sampled Fourier sum $g$ satisfiesThis is the sampling argument recorded in the finite-field character approximation principle.

Let $V$ be the intersection of the kernels of the sampled characters. It is a vector subspace of codimension at most $k$, and ${\tau }_{t}g=g$ for every $t\in V$. The triangle inequality therefore givesReturning from normalized convolution and normalized norm to $F$ and the counting norm multiplies the right side by $N^{1+1/(2m)}$. Hencefor every $t\in V$, proving the finite-field convolution almost-periodicity theorem.

Let $T=1_A\ast 1_A$ and chooseApply part b with its error parameter replaced by a sufficiently small absolute multiple of $\epsilon$. This produces a vector subspace $V$ of codimensionwith the evident harmless modification when $\alpha =1$.

For $t\in V$, $x\in {\mathbb{F}}_p^n$, and $q=2m$, Hölder's inequality givesSince ${\alpha }^{-1/q}\le e^{1/2}$ by the choice of $m$, the bound from part b is at mostafter absorbing the absolute factor into the chosen error parameter. This is the required uniform estimate for $1_A\ast 1_A\ast 1_A$.

The sum over all $x$ of the threefold-convolution representation function is $|A{|}^3$. Some $x_0$ therefore satisfiesUse part c with $\epsilon =\alpha /2$. There is a vector subspace $V$ of codimension $O({\alpha }^{-2}\log (1/\alpha ))$ such that, for every $t\in V$,Positivity means that $x_0+t$ has a representation as a sum of three elements of $A$. Thuswhich is the desired translate of a low-codimension subspace.

A bijection $\varphi :A\to B$ is a Freiman s-isomorphism when, for every $a_1,\dots ,a_s,a_1^{\prime },\dots ,a_s^{\prime }\in A$,holds if and only if

Because $A\subseteq {\mathbb{Z}}^2$ is finite, choose $R$ with $A\subseteq [-R,R{]}^2$ and an integer $M>2sR$. DefineAn equality of $s$-term sums in ${\mathbb{Z}}^2$ plainly gives equality after applying this linear map. Conversely, equality of the images giveswhere $|{\Delta }_x|\le 2sR<M$. Therefore ${\Delta }_x=0$, and then ${\Delta }_y=0$. The same estimate with one term on each side shows that $\varphi$ is injective on $A$. Hence $\varphi$ is a Freiman s-isomorphism from $A$ to the subset $\varphi (A)\subseteq \mathbb{Z}$.

The Dense Bogolyubov-Ruzsa lemma says that, for every $\alpha >0$, if $S$ has density at least $\alpha$ in a cyclic group of prime order, then $2S-2S$ contains a proper generalized arithmetic progression of rank $O_{\alpha }(1)$ and size ${\Omega }_{\alpha }(|G|)$.

Now suppose $A\subseteq \mathbb{Z}$ and $|A+A|\le K|A|$. The Ruzsa modelling lemma, taken at a sufficiently high fixed Freiman order, supplies $A^{\prime }\subseteq A$ with $|A^{\prime }|\ge |A|/2$ and a Freiman isomorphism from $A^{\prime }$ to a subset $S\subseteq \mathbb{Z}/q\mathbb{Z}$, where $q$ is prime, $q=O_K(|A|)$, and $|S|/q{\gg }_{K}1$. Apply the dense Bogolyubov-Ruzsa lemma to $S$ and transfer the resulting progression back through the Freiman model. We obtain a proper progressionof rank $O_K(1)$ and size $|P_0|{\gg }_K|A|$.

The Plünnecke-Ruzsa inequality givesThere are $|A||P_0|$ pairs $(a,p)$ with $a\in A$ and $p\in P_0$, distributed among the sums in $A+P_0$. Some $x$ therefore has at least $K^{-5}|P_0|{\gg }_K|A|$ representations $x=a+p$. Equivalently,Set $P=x-P_0$. Translation and negation preserve properness and rank. Moreover $P_0\subseteq 2A-2A$ and another use of Plünnecke gives $|P|\le K^4|A|$. Thusas required.

The Balog-Szemerédi-Gowers theorem states that if a finite set $A$ has at least $\delta |A{|}^3$ additive quadruples, then it has a subset $A^{\prime }\subseteq A$ such thatwhere $C$ is an absolute constant.

Consider the graphThe hypothesis says exactly that $\Gamma$ has at least $\delta N^3$ additive quadruples. By the Balog-Szemerédi-Gowers theorem, it contains ${\Gamma }^{\prime }$ with $|{\Gamma }^{\prime }|{\gg }_{\delta }N$ and $|{\Gamma }^{\prime }+{\Gamma }^{\prime }|{\ll }_{\delta }|{\Gamma }^{\prime }|$.

Part b gives a Freiman s-isomorphism from ${\Gamma }^{\prime }$ to a set $D\subseteq \mathbb{Z}$, where it is enough to take any fixed $s\ge 2$. The set $D$ has bounded doubling, with a bound depending only on $\delta$. Part c therefore provides a proper generalized arithmetic progression $Q$ of rank $O_{\delta }(1)$ such that

Write $Q$ as a proper parameter box. Since $|Q|{\gg }_{\delta }N$, one of its $O_{\delta }(1)$ side lengths tends to infinity with $N$. Averaging over all lines parallel to that side gives a line on which $D\cap Q$ has density bounded below in terms of $\delta$. The Szemerédi theorem quoted in the question then gives, once $N$ is sufficiently large in terms of $k$ and $\delta$, a nonconstant $k$-term arithmetic progression in $D$.

The inverse Freiman isomorphism sends it to a $k$-term arithmetic progression in ${\Gamma }^{\prime }\subseteq \Gamma$, because each relation between three consecutive terms is an additive-quadruple relation. Write this progression asIts first-coordinate difference cannot be zero: the graph of a function has only one point above each $x$. Hence $d\ne 0$. On the nonconstant progressionwe haveTaking $a=e/d$ and $b=y_0-(e/d)x_0$, both in $\mathbb{Q}$, proves the claim.