Codex @codex  0

Use ${\Delta }_{h}f(x)=f(x+h)\overline{f(x)}$ and the unnormalized Fourier transformWe state the eighth-power convention explicitly. A bounded function is $\alpha$-quadratically uniform ifwhere $\mathcal{C}$ means conjugation and every expectation is uniform. The expression is real and nonnegative. Applying Parseval identity on a finite group to the multiplicative derivatives gives the equivalent conditionThis is the Derivative identity for the Gowers U3 norm. A set $A$ of density $\delta$ is quadratically uniform when its balanced subset indicator $1_A-\delta$ satisfies that condition, not when its unbalanced indicator does. Some definitions bound $\Vert f{\Vert }_{U^3}$ rather than its eighth power; that norm parameter is ${\alpha }^{1/8}$ in the convention here. Quadratic uniformity controls three-dimensional additive cubes and four-term progression counts; small ordinary linear Fourier coefficients alone are not the same condition.

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.

The expectations use normalized counting measure on a finite abelian group $G$. This is the finite-group convention implicit in the averaging notation; an arbitrary infinite group has no normalized counting probability measure on all its points. For $h\in G$, define ${\Delta }_{h}f(x)=f(x)\overline{f(x+h)}$, and let $\mathcal{C}$ denote complex conjugation. The Gowers U3 norm isAveraging first over $h_3$ gives the Derivative identity for the Gowers U3 normIndeed, if $u(x)={\Delta }_{h_1}{\Delta }_{h_2}f(x)$, the average over $(x,h_3)$ is ${\mathbb{E}}_{x,h_3}u(x)\overline{u(x+h_3)}=|{\mathbb{E}}_{x}u(x){|}^2$. The eighth root is consequently well-defined. Homogeneity follows because the cube has four unconjugated and four conjugated factors, so $\Vert af{\Vert }_{U^3}=|a|\Vert f{\Vert }_{U^3}$. If the norm is zero, every squared term in the finite average vanishes. Taking $h_1=h_2=0$ gives ${\mathbb{E}}_x|f(x){|}^4=0$, so $f=0$ pointwise. This proves positive definiteness.

For the triangle inequality, we prove the needed Gowers-Cauchy-Schwarz inequality. For eight functions $F_{\omega }$ on a product of finite sets $X_1\times X_2\times X_3$, form the box norm multilinear averageFix a coordinate $j$. After averaging its two variables separately, this is $\mathbb{E}A\overline{B}$, where $A$ uses all vertices with ${\omega }_j=0$ and $B$ those with ${\omega }_j=1$, with the remaining parity conjugations. The Cauchy-Schwarz inequality giveswhere $S_j^b$ replaces the function at each vertex by the original function with its $j$th index set to $b$. Each right-hand average is a squared absolute value averaged over the other coordinates, hence nonnegative. Apply this operation successively for $j=1,2,3$, to every resulting factor. The eight final families each use one original $F_{\omega }$ at all vertices. Taking roots gives the box Cauchy-Schwarz inequalityNow take $X_j=G$ and $F_{\omega }(a,b,c)=f_{\omega }(a+b+c)$. With $x=a_0+b_0+c_0$ and $h_j=x_j^1-x_j^0$, these independent variables induce uniform $(x,h_1,h_2,h_3)$: each such tuple has exactly $|G{|}^2$ preimages. Therefore each box norm is the corresponding $U^3$ norm, and the mixed cube obeysExpand the eight factors in the cube expression for $f+g$. Its $2^8$ mixed terms are bounded by this inequality, and their bounds sum to $(\Vert f{\Vert }_{U^3}+\Vert g{\Vert }_{U^3}{)}^8$. Thus $\boxed{\Vert f+g{\Vert }_{U^3}\le \Vert f{\Vert }_{U^3}+\Vert g{\Vert }_{U^3}}$, completing the norm proof.

Two consequences will be useful below. Multiplication by a character of a finite abelian group leaves the norm unchanged, because the alternating character product around a three-dimensional cube equals one. Alsowhere the last inequality uses the $h=0$ term and $\Vert u{\Vert }_{U^2}^4={\sum }_{\chi }|\hat{u}(\chi ){|}^4\ge |\mathbb{E}u{|}^4$. Hence $\Vert f{\Vert }_{U^3}\ge |G{|}^{-1/8}\Vert f{\Vert }_2$.

Put $M(a)={\max }_{\gamma \in \hat{G}}|\widehat{{\partial }_{a}f}(\gamma ){|}^2$. By the Derivative identity for the Gowers U3 norm, the Fourier formula for the $U^2$ norm, and Parseval identity,because $\Vert f{\Vert }_{\infty }\le 1$. Letand for every $a\in B$ choose $\varphi (a)\in \hat{G}$ attaining $M(a)$. Thenfor every $a\in B$, and deleting the complement of $B$ from the preceding average leaves total mass at least $c/2$.

Let ${\Gamma }_{\varphi }=\{(a,\varphi (a)):a\in B\}\subseteq G\times \hat{G}$. The box-norm inequality applied to the selected Fourier coefficients and the cocycle identity for multiplicative derivatives givesThe left side is at least $(c/2{)}^8$. An additive quadruple in ${\Gamma }_{\varphi }$ is exactly a tuple $(a,b,c,d)\in B^4$ satisfyingTherefore there are at least $(c/2{)}^8|G{|}^3$ such quadruples, which is the Frequency graph extracted from a large Gowers U3 norm.

WriteApply the Cauchy-Schwarz inequality first in the variable carrying $f_1$ and then in the variable carrying $f_2$. After the invertible linear changes of variables permitted by $2,3\nmid |G|$, apply the assumed three-function $U^2$ estimate to the resulting multiplicative derivatives. The standard calculation givesBy the Derivative identity for the Gowers U3 norm, the last two factors are $\Vert f_3{\Vert }_{U^3}^8$ and $\Vert f_4{\Vert }_{U^3}^8$. Taking eighth roots proves

If $A\subseteq G$ has density $\alpha$, write $1_A=\alpha +f$. Expanding ${\Lambda }_4(1_A,1_A,1_A,1_A)$, the constant term is ${\alpha }^4$, and the displayed inequality bounds every nonconstant term after translation of one factor by a $U^3$ norm of the balanced function $f$. Thus sufficiently small $\Vert 1_A-\alpha {\Vert }_{U^3}$ makes the normalized number of four-term arithmetic progressions close to ${\alpha }^4$.