Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 129 / 3

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

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

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