Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 11 / 3

We use the normalized Gowers U3 norm on an interval, for which a quadratic phase has norm one. Let ${\mathcal{C}}_N$ consist of integer tuples $(x,h_1,h_2,h_3)$ whose eight vertices $x+{\omega }_1{h}_1+{\omega }_2{h}_2+{\omega }_3{h}_3$, $\omega \in \{0,1{\}}^3$, all lie in $[1,N]$. If $\mathcal{C}$ denotes complex conjugation, defineEquivalently, choose a prime $8N<M<16N$, extend $f$ by zero to $G=\mathbb{Z}/M\mathbb{Z}$, call that extension $F$, and put $I=1_{[1,N]}$. ThenThe large ambient modulus prevents wraparound in cubes supported on the interval, so the ratio is independent of the chosen such $M$. This also proves nonnegativity and the norm properties by the Gowers uniformity norm on $G$. Some conventions omit the denominator; their interval norm differs by a fixed bounded factor, and the quadratic-phase norm is then $\Vert I{\Vert }_{U^3(G)}$.

For $f_0(x)=e(\alpha x^2)$, the exponent in every conjugated cube product is a third additive difference of a quadratic polynomial and is zero. Thus $\Vert f_0{\Vert }_{U^3(N)}=1$ in the normalized interval convention.

The generalized von Neumann inequality for four-term progressions connects this norm to counting arithmetic progressions. For functions bounded by one on a cyclic group of prime order greater than three,Three applications of Cauchy-Schwarz prove the bound. Zero extension and division by the number of interval progressions give the analogous interval estimate up to an absolute constant. In particular, if $g=1_A-\alpha 1_{[1,N]}$, where $\alpha =|A|/N$, has small Gowers U3 norm on an interval, expansion of the progression count shows that it differs from ${\alpha }^4$ times the count for $[1,N]$ by $O(\Vert g{\Vert }_{U^3(N)}{N}^2)$. A large Gowers U3 norm detects structure capable of changing four-term progression counts; quadratic phases are the basic example.

For the remaining proof use the ambient $G$ just specified, define ${\partial }_{h}F(x)=F(x+h)\overline{F(x)}$, and take averages uniformly on $G$. For frequencies not on the character grid, an exponential is evaluated at the chosen integer representatives; the general proof below selects actual characters $\theta =k/M$. The printed question does not define $G$ or the interval normalization, so these conventions make the assertion precise. If instead ${\partial }_{h}f(x)=f(x)\overline{f(x+h)}$ is used, conjugate the correlations and reverse every frequency sign; the quadratic example then has $\theta (h)=-2\alpha h$.

The Gowers U3 norm derivative identity isLet $\kappa =\Vert F{\Vert }_{U^3(G)}^8$. Since $\Vert I{\Vert }_{U^3(G)}\ge \mathbb{E}I=N/M\ge 1/16$, by repeated Cauchy-Schwarz, the interval hypothesis gives $\kappa \ge 16^{-8}{\delta }^8$. Also $\Vert {\partial }_{h}F{\Vert }_{U^2}^4\le 1$. Therefore the sethas density at least $\kappa /2$ in $G$.

Use normalized Fourier coefficients on a finite abelian group $\hat{g}(k)={\mathbb{E}}_{x}g(x)e(-kx/M)$. The Gowers U2 norm and Parseval identity giveFor $g={\partial }_{h}F$, the final mean is at most one. Thus each $h\in H$ has a frequency $\theta (h)=k_h/M$ withThe derivative is identically zero unless $h$ is represented by an integer in $[-N+1,N-1]$, so $H$ lies in the requested interval of shifts. Its size is $\gg {\delta }^{8}M\gg {\delta }^{8}N$. Keep one such frequency for each shift; these same choices will satisfy the energy conclusion below.

Write $\beta =|H|/M\gg {\delta }^8$ and $\eta =(\kappa /2{)}^{1/2}\gg {\delta }^4$. Choose unit complex numbers $b_h$ so thatis real and nonnegative. Cauchy-Schwarz, using $|F|\le 1$, bounds $T^2$ byAfter setting $y=x+k$, each summand is a unit phase times the Fourier coefficient on a finite abelian group of ${\partial }_{h-k}F$ at frequency $\theta (h)-\theta (k)$.

Let $r(d,\xi )$ count pairs $(h,k)\in H^2$ with $h-k=d$ and $\theta (h)-\theta (k)=\xi$. Grouping terms, another Cauchy-Schwarz and the Parseval identity yieldwhere $E_{\theta }(H)=\sum r(d,\xi {)}^2$ is the additive energy of a frequency graph. The last inequality uses ${\sum }_{\xi }|\widehat{{\partial }_{d}F}(\xi ){|}^2=\mathbb{E}|{\partial }_{d}F{|}^2\le 1$ for each $d$.

ThusThe bound proves that derivative correlations force additive frequency energy. This energy counts exactly the ordered quadruples satisfying the two requested additive relations, after relabelling the difference equality as a sum equality. Shift equalities initially hold modulo $M$, but the shifts lie in $[-N,N]$ and $M>8N$, so they are also integer equalities. Frequency equalities hold in $\mathbb{R}/\mathbb{Z}$, as required. Consequently a common exponent $C=48$ works for both conclusions, after adjusting absolute implicit constants and using $0<\delta \le 1$.

For the quadratic phase, the multiplicative derivative on the overlap is ${\partial }_h{f}_0(x)=e(2\alpha hx+\alpha h^2)$. Hence an explicit choice isTake $|h|\le \lfloor N/2\rfloor$. The correlation magnitude is $(N-|h|)/M\ge 1/32$, and every additive quadruple of shifts satisfies the frequency relation. The interval of shifts has $\gg N^3$ such quadruples by Cauchy-Schwarz. These particular real frequencies need not belong to the grid used to prove existence for general $f$; evaluating them at the interval's integer coordinates gives the stated exact formula.

A genuinely nonlinear example is the bracket-linear frequency functionIt has $\gg N^3$ exact additive quadruples, yet agrees with any affine function $ah+b(\mathrm{mod}1)$ at only $o(N)$ shifts, uniformly in the affine function. The question permits giving this example without proof, but the mechanism is useful. For a pair with sum $s$, the value $\lfloor \sqrt{2}{h}_1\rfloor +\lfloor \sqrt{2}{h}_2\rfloor$ has only two possibilities, $\lfloor \sqrt{2}s\rfloor$ or $\lfloor \sqrt{2}s\rfloor -1$. There are $O(N)$ pair classes, so Cauchy-Schwarz produces $\gg N^3$ collisions with both additive relations.

To see why no long affine agreement occurs, three agreement points force the corresponding lattice points $(h,\lfloor \sqrt{2}h\rfloor )$ to be collinear: eliminating the affine slope gives $\sqrt{3}$ times an integer determinant equal to an integer, and irrationality makes that determinant zero. A rational line of slope $p/q$ contains agreement shifts in one residue class modulo $q$, and closeness of $\lfloor \sqrt{2}h\rfloor$ to $\sqrt{2}h$ bounds their span by $1/|\sqrt{2}-p/q|$. Lines with $q$ large have arbitrarily small possible density; for bounded $q$, irrationality of $\sqrt{2}$ bounds the number uniformly. Thus the maximum agreement is $o(N)$.