Past exam of the mathematics course of the University of Cambridge / 2003 / iii / Paper 25 (Additive and Combinatorial Number Theory)

We give a spectral proof of square-difference recurrence for finite colourings, proving the auxiliary results it uses. Extend the colouring arbitrarily to nonpositive integers, and let $f_j$ be the indicator of colour $j$. By successively taking subsequences of the interval lengths, followed by a diagonal subsequence, we may arrange that all the limitsexist, for every integer $h$. This uses only sequential compactness of bounded real sequences: list the countably many quantities, choose a convergent subsequence for each in turn, and take the diagonal. All limits below are along this common subsequence. We have $c(0)=1$, $c(-h)=c(h)$, $c(h)\ge 0$ and ${\sum }_j{\delta }_j=1$. Translating a fixed interval endpoint changes a normalized average by $O(|h|/L)$.

The sequence is a positive-definite function on $\mathbb{Z}$. Indeed, for finitely many complex numbers $z_u$,We next prove the required Bochner–Herglotz theorem for this sequence. The trigonometric polynomialis nonnegative by positive definiteness, and its integral on the circle is $c(0)=1$. Thus $F_H(t)dt$ is a probability measure. Such measures on a compact interval have a weakly convergent subsequence. For completeness, take a diagonal subsequence on all rational points of their nondecreasing distribution functions. The right-continuous extension of the limiting rational values is a distribution function and defines a probability measure by its interval increments. At its continuity points the original distribution functions converge, by sandwiching between rational endpoints. Approximating continuous functions by step functions with such endpoints proves convergence of their integrals. Identify the interval endpoints to obtain a measure on the circle. This proves the compactness of probability measures on a compact metric space in the case needed here.

For a fixed $h$, the Fourier coefficient of $F_{H}dt$ is $(1-|h|/H)c(h)$ once $H>|h|$. Taking the weak limit therefore supplies a positive probability measure $\mu$ such thatNo spectral representation has been assumed without proof.

Its atom at zero has positive mass. For each $H$,The last inequality is Cauchy-Schwarz on each colour's interval average. The integrand is at most one and tends to zero for every nonzero point of the circle, by the geometric-series formula, while it is one at zero. Bounded convergence gives

We also prove that quadratic phases with an irrational coefficient average to zero. For $z_0,\dots ,z_{L-1}$ bounded by one, extended by zero, Cauchy-Schwarz applied to ${\sum }_x{\sum }_{u=0}^{H-1}{z}_{x+u}=H{\sum }_x{z}_x$ yieldsThis identity follows by expanding the square of the inner shifted sum and grouping pairs by their difference; it is the needed finite Van der Corput inequality for finite scalar sequences. If $z_x=e(\theta x^2)$ and $\theta$ is irrational, each fixed nonzero lag correlation is a geometric sum with frequency $2\theta h$, hence is bounded independently of $L$. The geometric bound follows from $(1-z^L)/(1-z)$ with $z=e(2\theta h)\ne 1$. Dividing by $H^2{L}^2$ and letting $L$ tend to infinity gives $\mathrm{limsup}|L^{-1}\sum z_x{|}^2\le 1/H$. Letting $H$ tend to infinity proves the asserted cancellation. Rational coefficients instead give periodic sequences and therefore have convergent averages.

Choose a finite set $T$ of rational points of the circle, including zero, such that the total mass of the remaining rational atoms is below $1/(2r)$. This is possible because the rational points are countable and $\mu$ is finite. Let $q$ be a common multiple of their denominators. For $t\in T$, $e(t{q}^2{m}^2)=1$ for every integer $m$. For irrational $t$ the preceding cancellation applies to $q^{2}t$; at every other rational point the average exists by periodicity and has modulus at most one. Bounded convergence consequently givesHere the inequality takes real parts; $c$ itself is real. Thus some $b=qm>0$ has $c(b^2)>0$. By its definition as a limit of nonnegative averages, at least one actual positive $a$ has ${\sum }_j{f}_j(a)f_j(a+b^2)>0$. The same colour occurs at both points, provingThe arbitrary extension to nonpositive integers played no role in this final pair.

We prove the three-term Roth theorem by a density increment, keeping the interval boundary rather than replacing the interval by a cyclic group with a different density. The case $\delta >1$ is vacuous; assume $0<\delta \le 1$.

We first prove the following alternative with absolute constants $c,C>0$: if $A\subseteq [1,N]$ has density $\eta$ and no nonconstant three-term arithmetic progression, and $N\ge C{\eta }^{-4}$, then some integer progression $P\subseteq [1,N]$ hasFor this purpose take $M=6\lceil 4N/6\rceil +1$, so $4N<M\le 5N$ for large $N$ and $2,3$ are invertible modulo $M$. On $G=\mathbb{Z}/M\mathbb{Z}$, put $I=1_{[1,N]}$, $a=1_A$, $g=\eta I$ and $f=a-g$. In particular $\sum f=0$, and $f$ vanishes outside the interval. Use normalized Fourier coefficients on a finite abelian group, $\hat{u}(r)=M^{-1}{\sum }_{x}u(x)e(-rx/M)$. Character orthogonality, obtained by summing a finite geometric series, gives Fourier inversion on a finite group and Parseval identity on a finite group.

For $\Lambda (u,v,w)={\mathbb{E}}_{x,d}u(x)v(x+d)w(x+2d)$ these identities giveThere is no wrapping ambiguity when all three entries lie in $[1,N]$: the integer $x-2y+z$ has absolute value below $M$, so a modular relation is an integer relation. If no nonconstant progression exists, $\Lambda (a,a,a)=|A|/M^2$. Meanwhile the choices $1\le x\le \lfloor N/4\rfloor$ and $1\le d\le \lfloor N/8\rfloor$ give $\Lambda (I,I,I)\ge 1/10000$ for sufficiently large $N$.

Expand the difference by telescoping,If $\rho ={\max }_r|\hat{f}(r)|$, each term on the right has modulus at most $\rho \eta N/M$. Indeed multiplication of frequencies by $2$ permutes them, and Cauchy-Schwarz with Parseval identity bounds the two other Fourier factors by their $L^2$ norms; each squared norm is at most $\eta N/M$. For $N\ge 10000{\eta }^{-2}$, the diagonal count is less than half the main density term. ThereforeIn particular there is a nonzero frequency $r$ withThe frequency is nonzero because $\hat{f}(0)=0$.

Here is the conversion of this coefficient into a density increment. Put $Q=\lfloor \sqrt{N}\rfloor$. Of the $Q+1$ numbers $0,\theta ,\dots ,Q\theta$ modulo one, two lie in the same one of $Q$ equal arcs. Their difference gives $1\le q\le Q$ with $\Vert q\theta \Vert \le 1/Q$, where $\theta =-r/M$. This is the needed Dirichlet approximation theorem, proved by the pigeonhole principle.

Partition each residue class modulo $q$ in $[1,N]$ into consecutive progressions of length $L=\lfloor \gamma Q/(100\pi )\rfloor$, leaving its final short tail. Their total tail size is at most $qL\le \gamma N/(100\pi )$. On each full progression the character differs from its value at the first point by at most $2\pi L/Q\le \gamma /50$. Hence removing tails and replacing the character by its initial value showsThe sum of $f$ over all full progressions is the negative of its sum over the tails, so its absolute value is at most $\gamma N/(100\pi )$. Consequently the sum of the positive block sums is at least $\gamma N/5$. Since these blocks contain at most $N$ points in total, at least one has average $f$ at least $\gamma /5$. It gives a density increment at least ${\eta }^2/100000$. For $N\ge C{\eta }^{-4}$ with a sufficiently large absolute $C$, $L\ge c{\eta }^2\sqrt{N}$. This proves the alternative, with one small common absolute $c$.

Reidentify $P$ with $[1,|P|]$ by its affine parametrization. Absence of a nonconstant progression is preserved, while density increases. At every step the density is at least the original $\delta$, so the increment is at least $c{\delta }^2$ and the new interval length is at least $c{\delta }^2\sqrt{N_{\mathrm{old}}}$. After at most $T=\lceil 1/(c{\delta }^2)\rceil +1$ steps, the density would exceed one. Choose the original $N$ so large that the length stays above $C{\delta }^{-4}$ throughout these finitely many steps. Such a choice exists explicitly by working backwards: a required next length $L_0$ is ensured by previous length at least $(L_0/(c{\delta }^2){)}^2$. The alternative could then be applied at every step, giving a contradiction. ThusThis is the Roth density increment on an integer progression proof.

For the pattern with offsets $0,1,3$, replace the counting functional by ${\mathbb{E}}_{x,d}u(x)v(x+d)w(x+3d)$. Its Fourier expression iscoming from the relation $2x-3y+z=0$. Both multipliers are invertible modulo the chosen $M$, so exactly the same Parseval estimates apply. This relation has no wrap in $[1,N]$, since its magnitude is at most $3N<M$, and the earlier restricted choices of $x,d$ still give a fixed positive density main term. The same increment and iteration find a nonconstant triple $\{a,a+d,a+3d\}$. Negative $d$ is allowed, as requested, and the affine reparametrization used in the iteration preserves this pattern as well.

Write $e(t)=e^{2\pi it}$ and $N=n+1$. A convenient form of the quadratic Weyl inequality is the following: if $q\ge 1$, $(a,q)=1$ and $|\alpha -a/q|\le q^{-2}$, thenThe implied constant is absolute. In particular the familiar square-root saving is $|S|\ll (N^2/q+N+q{)}^{1/2}\log (2q{)}^{1/2}$. We prove all estimates used in this statement.

First, the finite geometric series identity giveswhere $\Vert \theta \Vert$ denotes distance to the nearest integer and the second bound is interpreted as infinite when that distance is zero. Indeed the sum is $(1-e(L\theta ))/(1-e(\theta ))$, and $|1-e(\theta )|=2|\sin \pi \theta |\ge 4\Vert \theta \Vert$. This proves the exponential geometric sum bound.

Expand the squared quadratic exponential sum by the difference $h$ between its indices. Since $(x+h{)}^2-x^2=2hx+h^2$, the diagonal and the paired off-diagonals giveFor $q\ge 16$, partition the $h$ into consecutive blocks of length at most $L=\lfloor q/8\rfloor$. Within one block, two distinct indices have difference $0<|d|<q/2$. Since the denominator of $2a/q$ after reduction is at least $q/2$, $\Vert 2ad/q\Vert \ge 1/q$. ThereforeThus the points $2\alpha h$ in a block are separated on the circle by at least $3/(4q)$.

For any such separated set, at most an absolute number of points lie in each pair of arcs whose distances from zero are between $j/(4q)$ and $(j+1)/(4q)$. The closest few contribute $O(N)$ to the capped reciprocal sum; the remaining arcs contribute $O(q/j)$ for $1\le j\le 4q$. Summing the harmonic series, using ${\sum }_{j\le m}{j}^{-1}\le 1+\log m$, proves a block bound $O(N+q\log (2q))$. This is the required separated reciprocal-distance sum estimate, with its proof supplied here. There are $O(N/q+1)$ blocks, soFor $q<16$, the trivial bound $|S|\le N$ already implies this estimate after increasing the absolute constant. This completes the proof, including the small denominators and the possible common factor of $2$ and $q$.

A Plünnecke graph is a finite directed layered graph $V_0,\dots ,V_n$, with edges only from $V_i$ to $V_{i+1}$, satisfying two commutation conditions. For each edge $u\to v$, the successors of $v$ can be matched injectively into the successors of $u$, so that the matched predecessor has an edge to the original successor. Dually, the predecessors of $u$ can be matched injectively into the predecessors of $v$, so that each original predecessor has an edge to its match. These are upward and downward commutation. For nonempty bottom subsets define the graph magnification ratioAddition graphs have layer $A+iB$ and edges $x\to x+b$: exchanging the order of two additions gives exactly these matchings.

We prove a slightly stronger weighted cut lemma for commutative graphs, which also explains part (ii). Give vertices in $V_i$ weight $C^{-i}$, for any $C>0$. A separating set meets every bottom-to-top path. There is a minimum-weight separating set contained in $V_0\cup V_n$. We first establish its local three-layer step.

Consider a three-layer channel $U_0,U_1,U_2$, every vertex of which lies on a full path, and suppose the middle layer is a minimum-weight cut. Replacing a subset $Z\subseteq U_1$ by all its successors or all its predecessors still gives a cut. Minimality impliesLet $X_i\subseteq U_1$ be the vertices of incoming degree $i$. Partition $U_2$ into $T_i$ according to the largest incoming degree of one of their predecessors. ThenDownward commutation makes incoming degree nondecreasing along an edge. Thus every vertex of $T_i$ has at least $i$ predecessors, and summing the last inequalities over $j$ givesReverse all edges and interchange the endpoint layers. The graph still satisfies both commutation conditions, and the expansion factor becomes $C^{-1}$. The same argument now gives the opposite inequality $|E(U_0,U_1)|\ge C^{-1}|E(U_1,U_2)|$. Equality must therefore hold at every step. In particular the suffix inequality at $j=1$ is an equality, and the reversed argument givesConsequently the bottom layer has exactly the middle layer's weight. This proves the local replacement lemma.

For a general minimum cut $S$, write $S_i=S\cap V_i$, and take its highest nonempty intermediate portion $S_j$, $0<j<n$. Form the three-layer channel whose bottom vertices are reachable from $V_0$ while avoiding the earlier cut portions, and whose top vertices can reach $V_n\setminus S_n$. Its middle layer is exactly $S_j$: any other middle vertex would produce an uncut full path, while every member of $S_j$ is essential in a positive-weight minimum cut and hence lies on such a path when that vertex alone is allowed. Channels inherit the commutation matchings: the replacement intermediate vertices still join the same prefix and suffix paths.

The middle layer is a minimum cut within this channel, since a cheaper local separator would replace $S_j$ and make the global cut cheaper. Apply the local lemma, with weights scaled by the common factor $C^{-(j-1)}$, to replace $S_j$ by the channel's bottom layer. This does not increase weight and removes the highest intermediate cut layer. Repetition leaves a minimum cut in the endpoint layers, proving the weighted cut lemma. Vertices lying on no full path can first be deleted; when $D_n>0$ all bottom vertices survive, and deleting such branches can only decrease intermediate images, so proving the lower bounds in the channel suffices.

Now take $C=1$ and assume $D_n\ge 1$. If a minimum endpoint cut is $S_0\cup S_n$, then ${\mathrm{Im}}^{(n)}(V_0\setminus S_0)\subseteq S_n$, soThe bottom layer itself is a cut, so the minimum cut size is $|V_0|$. For every nonempty $Z\subseteq V_0$, the set $(V_0\setminus Z)\cup {\mathrm{Im}}^{(k)}Z$ is also a cut. Its size must be at least $|V_0|$, provingOne may also apply the permitted Menger theorem to obtain $|V_0|$ vertex-disjoint full paths, giving the same conclusion. The proof above establishes the needed cut statement directly.

The graph form of Plünnecke inequality statesEquivalently these roots are nonincreasing along the layers. If $D_n=0$ the conclusion is immediate. Otherwise put $C=D_n^{1/n}$ and use the weighted cut lemma for commutative graphs proved in part (i). For a minimum endpoint cut $S_0\cup S_n$,The bottom layer is a cut of this weight. Comparing with $(V_0\setminus Z)\cup {\mathrm{Im}}^{(k)}Z$ gives $|{\mathrm{Im}}^{(k)}Z|\ge C^k|Z|$, as required. In an addition graph, $D_1\le K$ when $|A+B|\le K|A|$, so $D_m\le K^m$: some nonempty bottom subset has growth at most $K^m$ at height $m$.

The useful simultaneous sumset form says that a nonempty $X\subseteq A$ can be chosen with $|X+mB|\le K^m|X|$ for every $m$. To verify the common-subset assertion directly, choose $X$ minimizing $K^{\prime }=|X+B|/|X|$ among subsets of $A$. For a finite set $T=\{t_1,\dots ,t_s\}$, let $X_i$ consist of those $x\in X$ for which $x+t_i$ is a new point of $X+T$. The translated $X_i$ partition $X+T$. Points contributed by $(X\setminus X_i)+B+t_i$ are already present in earlier translates of $X+B$, so the new contribution at stage $i$ has size at mostThe inequality also holds when the complementary set is empty. Summing gives $|X+B+T|\le K^{\prime }|X+T|$. Taking $T=(m-1)B$ and iterating proves $|X+mB|\le (K^{\prime }{)}^m|X|\le K^m|X|$. This is the Petridis minimal-growth lemma calculation and supplies a single subset for all needed heights.

The empty-set case is immediate; take $A$ finite and nonempty. Part (ii) gives a nonempty $X\subseteq A$ such thatWe include the Ruzsa triangle inequality argument to justify passing from sums to differences. For each $d\in kA-lA$, fix one representation $d=u_d-v_d$ with $u_d\in kA$ and $v_d\in lA$. The mapis injective. Its output difference recovers $d$; the fixed representation then recovers $x$. HenceSince $|X|\le |A|$, this provesOnly the abelian group operations were used, so no torsion-free hypothesis is required.

We state the integer form of Freiman theorem for integer sets: for every $K\ge 1$ there are finite constants $r(K),C(K)$ such that every finite nonempty $A\subset \mathbb{Z}$ with doubling at most $K$ lies in a proper generalized arithmetic progression of rank at most $r(K)$ and cardinality at most $C(K)|A|$. An arbitrary abelian group requires the coset-progression version, allowing a subgroup factor. We prove the integer statement, with no claim of optimized constants.

We use the allowed Plünnecke inequality and basic Freiman isomorphism facts, and explicitly prove the modelling, Fourier and covering steps. Two geometry-of-numbers consequences are used as permitted: a cyclic rank-$d$ phase-radius-$\rho$ Bohr set contains a proper symmetric progression of rank at most $d+1$ and size at least $c(d,\rho )$ times the cyclic group order; and a rank-$r$ integer progression with parameter-box volume $V$ can be contained in a proper progression of rank at most $r$ and size at most $c_{r}V$. These follow from successive minima and lattice basis reduction. All these constants depend only on the displayed rank and radius, not on the ambient order or step sizes.

First construct a dense cyclic model of a large subset. Put $D=8A-8A$ and $q=8|D|$. Plünnecke gives $|D|\le K^{16}|A|$. Choose an auxiliary prime $p$ so large that every nonzero integer in $D$ stays nonzero modulo $p$, and $p>2q$. Arbitrarily large primes exist: a purported finite list would miss a prime divisor of one plus their product. For a uniform nonzero multiplier $\lambda (\mathrm{mod}p)$, each nonzero $d\in D$ has $\lambda d$ uniformly distributed among the nonzero residues. The forbidden residues are those represented by nonzero multiples of $q$ with absolute value less than $p$; there are at most $2(p-1)/q$ of them. The union bound gives failure probability at mostThus choose $\lambda$ avoiding them for every nonzero $d\in D$.

Represent the dilated elements of $A$ in $[0,p-1]$, divide this interval into nine consecutive subintervals, and retain a most-populated one. It defines $A^{\prime }\subseteq A$ with $|A^{\prime }|\ge |A|/9$. If $u(a)$ is the chosen representative of $\lambda a$, eight-term sums of representatives from this subinterval have a range shorter than $p$: eight times its width is less than $8p/9$. Consequently every original eight-term relation lifts from equality modulo $p$ to equality of the representative sums as integers.

Now reduce these representatives modulo $q$. If their two eight-term sums agree modulo $q$, their integer difference is a multiple of $q$ of absolute value below $p$. A nonzero such difference would give a forbidden residue $\lambda d$ for some nonzero $d\in D$. If $d=0$, its representative difference is already zero. Hence there are no new relations either. The map is therefore a Freiman s-isomorphism of order eight onto $B\subseteq \mathbb{Z}/q\mathbb{Z}$. It is injective, by padding shorter relations to eight terms with a fixed retained point. Its density satisfiesThis proves the cyclic Freiman model of a small-doubling integer set needed below.

Next we prove the cyclic Bogolyubov lemma. Use normalized finite-group Fourier analysis on $\mathbb{Z}/q\mathbb{Z}$. The convolutionhas Fourier expansion $r(x)={\sum }_{\chi }|\widehat{1_B}(\chi ){|}^4\chi (x)$. Let $\Gamma$ consist of those characters whose Fourier coefficient has modulus at least ${\beta }^{3/2}/\sqrt{2}$. Parseval gives $|\Gamma |\le 2{\beta }^{-2}$, and the fourth-power tail outside $\Gamma$ is at most ${\beta }^4/2$. The zero character belongs to $\Gamma$ and contributes ${\beta }^4$.

For the phase-distance Bohr set $\mathcal{B}=\{x:\Vert \arg \chi (x)/(2\pi )\Vert \le 1/10\text{ for all }\chi \in \Gamma \}$, every retained character has real part at least $\cos (\pi /5)>3/4$. ThereforeThe support of this convolution is $2B-2B$, so $\mathcal{B}\subseteq 2B-2B$. Apply the stated progression in a Bohr set from successive minima consequence. It supplies a symmetric proper progression $P_B\subseteq 2B-2B$ of rank bounded by a function of $K$ and size at least $c(K)q$, hence at least $c(K)|A|$ after adjusting the constant.

Lift this progression back to the integers. The inverse Freiman map inducesEquality of two representations uses a four-term relation on each side, so $\psi$ is well defined and injective. If $y,z,y+z$ all lie in this difference set, the relation between their representations involves at most six original terms on either side. The order-eight model therefore gives $\psi (y+z)=\psi (y)+\psi (z)$ and $\psi (0)=0$. Along every coordinate path within the symmetric progression box, all partial sums remain in $P_B$. It follows thatThus $P=\psi (P_B)$ is a symmetric proper integer progression of the same rank and cardinality, and $P\subseteq 2A-2A$. This proves the Freiman lifting of a progression step, including why a sufficiently high-order model was selected.

It remains to cover all of $A$, not merely its large modeled subset. Since $P\subseteq 2A-2A$, Plünnecke givesChoose $X\subseteq A$ maximal such that the translates $x+P$ are pairwise disjoint. Their union lies in $A+P$, so $|X|\le K^5|A|/|P|\le C_1(K)$. For every $a\in A$, maximality makes $a+P$ meet some $x+P$, giving $a\in x+P-P$. ConsequentlyThis proves the needed Ruzsa covering lemma directly.

Write $P=\{{\sum }_{i=1}^r{n}_i{w}_i:|n_i|\le L_i\}$ and $X=\{x_1,\dots ,x_s\}$. The setcontains $X+(P-P)$ and hence $A$. Its rank is at most $r+s$, bounded only by $K$, and its parameter-box volume is at most $2^{r+s}|P|$. Also $|P|\le |2A-2A|\le K^4|A|$, so this volume is at most $C_2(K)|A|$. The allowed integer properification consequence now contains $Q$ in a proper progression of bounded rank and size at most $C(K)|A|$. ThereforeThis proves Freiman's theorem, using geometry of numbers only in the two explicitly stated places.

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.