Past exam of the mathematics course of the University of Cambridge / 2003 / iii / Paper 25 / 6

We specify the convention for quadratic uniformity of a set. Write $\delta =|A|/N$ and $f=1_A-\delta$ on $[1,N]$, extended by zero elsewhere. Let ${\mathcal{C}}_N$ be the integer cubes $(x,h_1,h_2,h_3)$ with all eight vertices in $[1,N]$, and let $T_N=|{\mathcal{C}}_N|$. In the eighth-power convention, $A$ is $\alpha$-quadratically uniform whenwhere $\mathcal{C}$ means complex conjugation. This quantity is nonnegative and is the eighth power of the normalized Gowers U3 norm on an interval. If uniformity instead means that the norm itself is at most $\alpha$, replace the present parameter by ${\alpha }^8$. Removing the balance would not define density-relative uniformity.

Embed the interval in $G=\mathbb{Z}/M\mathbb{Z}$ with $M=12N+1$, and keep the zero extension of $f$. This group has invertible $2$ and $3$. Every cube with all vertices in the interval is an integer cube: its face relations have magnitude at most $2N<M$, so their modular equalities are ordinary equalities. Conversely every such integer cube gives one modular cube. Thussince $T_N\le M^4$. The cube quantity is nonnegative, for it can be written as an average of squares of two-fold multiplicative-derivative correlations, by expanding the third increment.

We prove the counting estimate needed below. For functions $|u_j|\le 1$, putThree applications of Cauchy-Schwarz giveHere are the elimination steps, to make the generalized von Neumann inequality for four-term progressions explicit. Set ${\Delta }_{h}u(x)=u(x)\overline{u(x+h)}$. Reparametrize by the position $x+3d$, and apply Cauchy-Schwarz in that position to eliminate $u_3$. Pairing the two remaining difference variables produces increments $3h,2h,h$ in $u_0,u_1,u_2$. Reparametrize by the position of $u_2$, apply Cauchy-Schwarz to eliminate it, and average over $h$ using Cauchy-Schwarz again. The remaining increments in $u_0$ are $3h,2k$. Finally reparametrize by the position of $u_1$ and eliminate it in the same way. The resulting bound isIn the last equality $2k$ and $3h$ range freely since their multipliers are units. Each elimination drops only a factor bounded by one; expansion of the squared average gives exactly the stated multiplicative derivative. To target $u_j$ instead, subtract its slope from all four slopes and eliminate the other three factors. The increments are the three nonzero slope differences times independent variables, all among $\pm 1,\pm 2,\pm 3$ and hence invertible. This proves the minimum bound.

Now let $a=1_A$ and $g=\delta 1_{[1,N]}$ on $G$. Telescoping the four factors, the difference ${\Lambda }_4(a,a,a,a)-{\Lambda }_4(g,g,g,g)$ is a sum of four terms with one balanced factor $f$ and three factors bounded by one. ThereforeFor $N\ge 16$, restricting to $1\le x\le \lfloor N/4\rfloor$ and $1\le d\le \lfloor N/8\rfloor$ gives at least $N^2/128$ progressions inside the interval. Since $M\le 13N$, ${\Lambda }_4(I,I,I,I)\ge 1/100000$. Choose, for example,Then ${\Lambda }_4(a,a,a,a)\ge {\delta }^4/200000$. Constant progressions contribute only $|A|/M^2\le 1/N$. For $N>400000{\delta }^{-4}$, this is strictly below the displayed lower bound. A nonconstant progression consequently exists. Its four points are actual integer progression points: the two adjacent three-term relations have magnitude less than $M$, so they do not wrap. HenceThis proves the four-term progressions in a quadratically uniform interval set criterion, with the parameter normalization and the interval boundary both accounted for.

The proof of Szemerédi theorem for four-term progressions follows a uniformity-versus-density-increment iteration. Fix a positive starting density; the quantitative parameters below depend only on that density.

First apply the counting argument in part (i). A sufficiently long set with no nonconstant four-term arithmetic progression cannot have small balanced Gowers U3 norm. Thus its balanced function has a quantitatively large cube average. The Derivative identity for the Gowers U3 norm expresses this as an average of fourth Fourier moments of the multiplicative derivatives $x\mapsto f(x+h)\overline{f(x)}$. Many shifts therefore have a derivative with a large Fourier coefficient.

The next step is the inverse argument. Choose these frequencies as a function of the shifts. The relations between repeated derivatives force a large part of the resulting frequency graph to have many additive quadruples. A Balog-Szemerédi-Gowers theorem extraction followed by Freiman theorem for integer sets organizes this graph on a bounded-complexity additive model. Integrating the organized derivative frequencies yields correlation of $f$ with a locally quadratic phase on a structured region. On integer intervals this is generally a local quadratic phase on a Bohr-type region, or equivalent two-step structure; it need not be one global quadratic polynomial on the entire interval.

The quantitative density-increment lemma obtained from that inverse argument says that either the interval is bounded in size by a function of its density, or there is a nonempty integer progression of length at least $c(\delta )N^{c(\delta )}$ on which the density increases by at least $c(\delta )>0$. The passage from correlation to this increment partitions the structured region into progressions on which the phase varies very little, controls discarded boundaries, and uses the balanced function's zero mean to find a positive-density gain. Both the gain and the size exponent are bounded away from zero for densities above the fixed starting density.

Reidentify the new progression with an interval and repeat. The property of having no nonconstant four-term progression is preserved under this affine identification. Density can increase only finitely many times before it exceeds one. Starting with $N$ sufficiently large ensures that the successive power-type length losses never reach the exceptional bounded-size case during those finitely many steps. This contradiction proves that every fixed positive density has a threshold beyond which a four-term progression must occur. The counting lemma, inverse structural argument, density increment and final iteration are the main steps; the deep inverse step is only outlined here, as permitted by this part of the question.