Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 13 / 3

There is a normalization omission in the printed conclusion: the discrepancy of a count of pairs must be bounded by a small function of the energy excess times $N^2$. We prove this normalized result, then give a counterexample to the literal bound without $N^2$. Write $ϵ$ for the energy excess parameter to avoid confusing it with an element of the third set.

For Fourier analysis on a finite abelian group, use $e_N(t)=e^{2\pi it/N}$ andCharacter orthogonality, ${\mathbb{E}}_x{e}_N(rx)=1$ for $r=0$ and zero otherwise, gives Fourier inversion and the Parseval identity on a finite group:Put $u=1_A$, $v=1_B$, $w=1_C$. Expanding the constraint $a_1+a_2=a_3+a_4$ by the same character orthogonality gives the additive energy identityThus ${\sum }_{r\ne 0}|\hat{u}(r){|}^4\le ϵ$, and every nonconstant Fourier coefficient on a finite abelian group of $u$ has modulus at most ${ϵ}^{1/4}$. Expanding the constraint in the triple count $T$ givesThe Cauchy-Schwarz inequality yieldsThe first squared norm is $\gamma$ by the Parseval identity on a finite group. For the second, multiplication by $2$ on ${\mathbb{Z}}_N$ has kernel size $h=\gcd (2,N)$ and every element of its image has exactly $h$ preimages. HenceThis proves that additive energy controls three-term progression mixing, including for even moduli:Thus the intended density-error function can be $F(ϵ)=\sqrt{2}{ϵ}^{1/4}$, which tends to zero. For odd moduli the factor $\sqrt{2}$ can be replaced by one.

To see why the literal unnormalized conclusion is false, take $N=q^2$ and let all three sets be the subgroup of multiples of $q$. Their densities are $1/q$. Every choice of three entries of that subgroup determines the fourth entry of an additive quadruple, so its energy is $q^3$. The excess parameter isEvery pair $(a,b)$ in the subgroup determines $c=2b-a$ there, giving $T=q^2$, whereas $\alpha \beta \gamma N^2=q$. Their difference is $q^2-q\to \infty$, which cannot be bounded by any function of $ϵ$ tending to zero. The missing $N^2$ is therefore a genuine source defect, not an alternative Fourier transform normalization.

The positive-power length assertion is an asymptotic one: it requires $N$ sufficiently large in terms of the density. Read literally for every $N$, it fails when $N=2$, $\delta =1/2$ and $A=\{1\}$, whose triple sumset is a singleton. We prove the intended result with this necessary qualification and an explicit positive exponent.

Embed the interval into the cyclic group $G=\mathbb{Z}/M\mathbb{Z}$ with $M=8N$, and set $u=1_A$, $\alpha =|A|/M\ge \delta /8$. Since all integer triple sums lie in $[3,3N]$, this embedding introduces no collisions between distinct sums. Use normalized Fourier coefficients on a finite abelian group and normalized convolution on a finite group, and putThe function $F$ is nonnegative and has mean ${\alpha }^3$, so some $t_0$ satisfies $F(t_0)\ge {\alpha }^3$. We show that a whole translated Bohr set is contained in its positive support, hence in the triple sumset.

Put $\theta ={\alpha }^2/8$, $\rho =\alpha /4$, and define the large spectrumThe Parseval identity on a finite group gives ${\sum }_r|\hat{u}(r){|}^2=\alpha$, soAlso $|\hat{u}(r)|\le \alpha$, and therefore ${\sum }_r|\hat{u}(r){|}^3\le {\alpha }^2$. Using Fourier inversion and the convolution theorem on a finite group, for $b\in B$ we obtainConsequently $F(t_0+b)\ge {\alpha }^3/2>0$. This proves the translated Bohr neighborhood in a triple sumset:It remains to produce a long ordinary integer arithmetic progression in this translate; we supply the simultaneous approximation and the lifting argument. SetThus $d=|\Gamma |\le D$. Partition the $d$-dimensional unit cube into $Q^d$ boxes of side $1/Q$. The $Q^d+1$ pointscontain two in the same box by the pigeonhole principle. Their index difference gives an integer $q$ with $1\le q\le Q^d<M$ andIn particular $|e^{2\pi irq/M}-1|\le 2\pi /Q$. The identity $z^j-1=(z-1)(1+\cdots +z^{j-1})$ on the unit circle now shows thatAll residues $t_0+jq$ therefore lie in the triple sumset. Let $s_j\in [3,3N]$ be their actual integer representatives. Their successive differences are congruent to $q$ modulo $M$, and each lies in $[-(3N-3),3N-3]$, which is contained in $(-M/2,M/2)$. There is at most one integer in this interval in any specified residue class, so every difference $s_{j+1}-s_j$ is the same integer. It is nonzero because $0<q<M$. Thus the $s_j$ form an ordinary integer arithmetic progression of distinct elements, even though $M$ is composite. Reversing it if necessary makes the common difference positive.

For sufficiently large $N$, we have $Q\ge \frac{1}{2}{M}^{1/(D+1)}$ and $\rho \ge \delta /32$, whenceAbsorb this fixed prefactor by decreasing the exponent: withthe last lower bound is at least $N^{r_{\delta }}$ once $N$ is sufficiently large in terms of $\delta$. This proves a polynomial-length progression in $A+A+A$ by the polynomial-length progression in a dense triple sumset argument, without replacing the triple sumset by a fourfold difference set.