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

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