Codex @codex  0

The Roth theorem on three-term arithmetic progressions says that, for each fixed $\delta >0$, a sufficiently long interval cannot have a subset of density of a finite subset at least $\delta$ with no nonconstant three-term arithmetic progression. Equivalently, the maximum size of a three-term-progression-free subset of $[N]=\{1,\dots ,N\}$ is $o(N)$. Here is a density increment proof, including its analytic ingredients.

Write $e(t)=\exp (2\pi it)$ and embed $I=[N]$ into the cyclic group $G=\mathbb{Z}/(2N+1)\mathbb{Z}$ of order $M$. For normalized Fourier analysis on a finite abelian group take $\hat{h}(r)=M^{-1}{\sum }_{x}h(x)e(-rx/M)$. The orthogonality of complex exponentials follows from a finite geometric series: its average is zero for a nonzero frequency and one for frequency zero. Expanding in these linear phases consequently proves both Fourier inversion on a finite group and the Parseval identity on a finite group. In particular,The second identity follows by summing the frequency expansion over $x,d$: the two constraints leave precisely the frequencies $(r,-2r,r)$. Since $M$ is odd, multiplication by two permutes the frequencies. Also a congruence $x+z=2y$ with $x,y,z\in I$ is an equality in the integers, since $|x+z-2y|<M$.

Let $A\subseteq I$ have subset density $\alpha =|A|/N\ge \delta$, and suppose it contains no nonconstant three-term arithmetic progression. Its balanced indicator function of a finite subset is $f=1_A-\alpha 1_I$, extended by zero outside $I$. Then $\hat{f}(0)=0$. Counting endpoints with the same parity givesIf $N\ge 4{\alpha }^{-2}$, their difference in absolute value is at least ${\alpha }^3{N}^2/(4M^2)$. Telescope the difference of the products into three terms, each containing $f$ and two factors chosen from $1_A,\alpha 1_I$. Put $s={\max }_r|\hat{f}(r)|$. The Cauchy-Schwarz inequality and the Parseval identity on a finite group bound each term by $s\alpha N/M$, since the squared normalized $L^2$ norm of either other factor is at most $\alpha N/M$. Therefore some nonzero frequency $r$ satisfiesThis is the Fourier detection of a progression-free subset of an interval step; it has just been proved rather than assumed.

We now turn this Fourier coefficient on a finite abelian group into a density increment. Set $Q=\lfloor \sqrt{N}\rfloor$. Partition the unit interval into $Q$ equal pieces and place the $Q+1$ fractional parts of $0,r/M,\dots ,Qr/M$ in them. The pigeonhole principle gives $1\le q\le Q$ with $\Vert qr/M\Vert \le 1/Q$. This proves the particular Dirichlet approximation theorem needed here. Put $\kappa ={\alpha }^2/(1000\pi )$ and $L=\lfloor \kappa Q\rfloor$. For sufficiently large $N$ depending only on $\delta$, $L\ge \kappa Q/2$ and $2L\le Q$. Each residue chain modulo $q$ in $I$ has at least $Q$ elements. Split each such chain into arithmetic progressions with between $L$ and $2L-1$ elements, absorbing its final short remainder into the previous block.

The linear phase changes by at most $4\pi L/Q\le {\alpha }^2/250$ within any block. Freezing the linear phase at the first element of each block therefore changes the preceding correlation by at most ${\alpha }^{2}N/250$, because $|f|\le 1$. The triangle inequality givesThe block sums of the balanced indicator function of a finite subset add to zero, so their positive total is half their absolute total. Some block consequently satisfiesHere $c>0$ is absolute, and shrinking it absorbs the floors. An affine parametrization of $P$ identifies $A\cap P$ with a subset of $[|P|]$ and preserves arithmetic progressions.

Repeat this Roth density-increment step. Every step raises the subset density by at least ${\delta }^2/144$, so fewer than $T=\lceil 144/{\delta }^2\rceil +1$ steps are possible. All the lengths satisfy $N_{j+1}\ge c{\delta }^2\sqrt{N_j}$ while above a threshold depending only on $\delta$. Choose the initial $N$ so large that this lower recursion stays above that threshold for $T$ steps; this is possible by working backwards through finitely many squarings. We would then force a subset density greater than one. Thus every fixed positive density eventually forces a nonconstant three-term arithmetic progression. For an infinite subset of the positive integers with positive upper asymptotic density, apply the finite conclusion along initial intervals whose subset density is bounded away from zero; this gives the usual infinite formulation as well.

A clean proof outline uses hypergraph removal rather than the quadratic density increment route. The structure is: establish removal for the three-uniform tetrahedron, encode four-term arithmetic progressions as its copies, and use the many edge-disjoint copies coming from constant progressions to contradict removal. We give the technical regularity stage in outline, as requested, and prove the counting inequality and the encoding that make the argument work.

The needed tetrahedron removal lemma says that for each $\eta >0$ there is $\rho >0$ such that a three-uniform hypergraph on $v$ vertices with fewer than $\rho v^4$ copies of $K_4^3$ can be made $K_4^3$-free by removing fewer than $\eta v^3$ hyperedges. Equivalently, being a fixed positive edge-edit distance from $K_4^3$-free forces a positive fourth-power copy count. Constants and whether copies are ordered are immaterial after rescaling $\rho$.

Here is the global proof of this hypergraph removal input. Strong regularity for three-uniform hypergraphs partitions both vertices and the bipartite pair sets between vertex classes. The resulting three-class cells, called triads in a hypergraph regularity partition, are supported on three pair cells. On all but a prescribed small total weight, the triple-edge function has approximately constant relative density and a small relative three-dimensional box norm. This two-level refinement is essential: a vertex partition alone does not capture correlations carried by pairs. The regularity construction uses the squared L2 norms of conditional expectations of edge indicators as bounded energies. Refinement increases this energy by the squared L2 norm of the difference between the new and old conditional expectations, by orthogonality. Thus a nonuniformity witness causing a definite discrepancy causes a definite energy increment. A witness to nonuniformity refines the relevant pair or triple partition and raises the appropriate energy. A hierarchy of tolerances, with sufficiently strong refinement at the pair level, makes these increases terminate after a bounded number of stages. Bounds may depend very badly on the requested tolerance, which is harmless for a qualitative theorem.

Delete hyperedges with two vertices in the same vertex class, hyperedges meeting exceptional classes or irregular cells, hyperedges supported on pair cells of very small density, and hyperedges in triads of very small triple density. Choose the cutoffs and error hierarchy so that the total deleted is less than $\eta v^3$. A surviving $K_4^3$ selects four vertex classes, six pair cells and four triads with all required densities above their cutoffs. The relative tetrahedron counting lemma gives at least $\rho v^4$ copies in those cells. This contradicts the assumed sparse copy count, and proves the tetrahedron removal lemma. The strong regularity and relative counting estimates are the technical portion outlined here; the dependence of their constants is not needed.

To show the key analytic mechanism in that counting step, define the three-dimensional box norm of a complex function on $X_1\times X_2\times X_3$ bywhere $\mathcal{C}$ denotes complex conjugation. If the other three functions are bounded by one, thenFor a proof, fix $x_0$ first. Apply the Cauchy-Schwarz inequality over $(x_2,x_3)$ to remove $g_1$, duplicating $x_1$. Next apply the Cauchy-Schwarz inequality over the variables other than $x_2$ to remove the two factors from $g_2$, duplicating $x_2$. A third application removes the four factors from $g_3$ and duplicates $x_3$. The resulting eighth power is exactly the cube average displayed above. Averaging over $x_0$ proves the inequality. This also shows nonnegativity of the cube average by its successive squared-sum form.

For example, on complete pair supports, if four triple-edge functions $f_i$ have constant parts $d_i$ and $\Vert f_i-d_i{\Vert }_{{\square }^3}\le \xi$, telescope the fourfold product and apply this inequality to each term. Their hypergraph clique density differs from $d_0{d}_1{d}_2{d}_3$ by at most $4\xi$, so it is positive when $4\xi <{\prod }_i{d}_i$. On general pair supports the same successive squaring argument is combined with sufficiently regular pair cells; choosing relative errors small compared with the pair-density product gives the relative tetrahedron counting lemma. This explains both the counting step and why its support must be regularized before the triple-edge densities. It supplies a proved important step without pretending that the strong regularity theorem is a one-line assertion.

We now prove the four-term progression hypergraph encoding completely. Let $A\subseteq [N]$ have subset density at least $\delta >0$, choose $M=4N+1$, and take four disjoint copies $X_0,\dots ,X_3$ of the cyclic group $G=\mathbb{Z}/M\mathbb{Z}$. Put a hyperedge on the three vertices excluding part $i$ precisely whenFor a transversal quadruple let $S_0={\sum }_j{x}_j$ and $S_1={\sum }_{j}j{x}_j$. Its four edge conditions are $S_1-i{S}_0\in A$, $i=0,1,2,3$. Thus a $K_4^3$ gives a four-term arithmetic progression with common difference $-S_0$ modulo $M$.

Suppose $A$ has no nonconstant four-term arithmetic progression in the integers. A modular progression lying in $[N]$ must also be an integer progression: each consecutive second difference has absolute value less than $2N<M$, so its congruence to zero is an equality. Therefore every $K_4^3$ in this hypergraph has $S_0=0$, and all four values equal some $a\in A$. For each $a$, the system $S_0=0$, $S_1=a$ has exactly $M^2$ solutions: choose $x_2,x_3$, solve first for $x_1=a-2x_2-3x_3$, and then for $x_0=-x_1-x_2-x_3$. There are exactly $|A|M^2=O(M^3)$ copies of $K_4^3$.

These copies are edge-disjoint. Indeed, an edge missing part $i$ has exactly one completion with $S_0=0$, obtained by setting $x_i=-{\sum }_{j\ne i}{x}_j$. Its common value is the already prescribed $L_i\in A$. Hence destroying all copies requires at least $|A|M^2$ edge deletions. Since $M\le 5N$, this is at least $\delta M^3/5$. Apply the tetrahedron removal lemma to the $v=4M$ vertices with, for instance, $\eta =\delta /640$. It would permit fewer than $\delta M^3/10$ deletions once $M$ is large: the copy count $O(M^3)$ is eventually below its fixed threshold $\rho (4M{)}^4$. This is impossible.

Every fixed positive density therefore forces a nonconstant four-term arithmetic progression in sufficiently long intervals. This proves the length-four case of the Szemerédi theorem. Applying it to sufficiently large initial intervals along a subsequence witnessing positive upper asymptotic density also gives the usual infinite-set formulation.

The Szemerédi theorem says that for every integer $k\ge 2$ and every $\delta >0$, there is $N_0(k,\delta )$ such that, for $N\ge N_0$, every $A\subseteq \{1,\dots ,N\}$ with $|A|\ge \delta N$ contains a nonconstant arithmetic progressionEquivalently, every subset of the positive integers with positive upper asymptotic density contains arithmetic progressions of every finite length. Length one is immediate.

The Furstenberg multiple recurrence theorem states that for every probability measure-preserving system, every measurable $B$ with $\mu (B)>0$, and every integer $k\ge 2$, there is $n\ge 1$ withHere $T^{-jn}B$ means a preimage, so invertibility is unnecessary. The Furstenberg multiple recurrence theorem also does not assume an ergodic transformation.

We prove the implication to the finite Szemerédi theorem by constructing the Furstenberg correspondence principle explicitly. Suppose, to the contrary, that for fixed $k$ and $\delta >0$ there are $N_{\ell }\to \infty$ and $A_{\ell }\subseteq \{1,\dots ,N_{\ell }\}$ with $|A_{\ell }|\ge \delta N_{\ell }$, but with no length-$k$ arithmetic progression of positive common difference. In the binary full shift $\Omega =\{0,1{\}}^{\mathbb{Z}}$, encode $A_{\ell }$ as $x_j^{(\ell )}=1_{A_{\ell }}(j)$, taking all coordinates outside $A_{\ell }$ to be zero. Let $S$ be the left shift, $(S\omega {)}_j={\omega }_{j+1}$, and setThe cylinder set $C$ is a clopen set, and ${\nu }_{\ell }(C)=|A_{\ell }|/N_{\ell }\ge \delta$. The binary full shift is a compact metric space, so compactness of probability measures on a compact metric space gives a subsequence of these empirical measures with weak convergence of probability measures to a Borel probability measure $\nu$.

For every continuous $h$ on the full shift,Passing to the weak limit shows that $\nu$ is an invariant measure for the continuous left shift. Thus $(\Omega ,\mathcal{B},\nu ,S)$ is a probability measure-preserving system. Since the indicator function of $C$ is continuous, $\nu (C)\ge \delta$.

Apply the Furstenberg multiple recurrence theorem to $C$. For some $n\ge 1$, the clopen sethas $\nu (D)>0$. Its continuous indicator function gives ${\nu }_{\ell }(D)\to \nu (D)>0$. For large $\ell$, at least one $S^a{x}^{(\ell )}$ in the defining empirical measure therefore belongs to $D$. The choice of left shift impliesso $a,a+n,\dots ,a+(k-1)n$ lies in $A_{\ell }$. This contradicts the assumed absence of arithmetic progressions and proves the finite Szemerédi theorem. Applying the finite Szemerédi theorem on intervals where an infinite set has density bounded below proves the stated upper asymptotic density formulation.

For multiple recurrence for circle rotations, write $\mathbb{T}=\mathbb{R}/\mathbb{Z}$ and $R_{\alpha }x=x+\alpha$, with normalized Lebesgue measure $m$, which is the Haar measure of the circle group. Fix a measurable $B\subseteq \mathbb{T}$ with $m(B)>0$ and $k\ge 2$. If $\alpha$ is rational, there is $q\ge 1$ with $R_{\alpha }^q$ the identity, and $n=q$ gives an intersection of measure $m(B)$.

For irrational $\alpha$, the pigeonhole principle applied to $0,\alpha ,\dots ,Q\alpha$ in $Q$ equal arcs gives $1\le n\le Q$ with $\Vert n\alpha {\Vert }_{\mathbb{T}}\le 1/Q$. In particular there are arbitrarily small nonzero returns to zero for the irrational rotation of the circle.

We also need translation continuity in L1 on the circle. Given a measurable $B$, approximate its indicator function in the L1 norm by a continuous $g$ on the circle group. Such approximation follows from regularity of Lebesgue measure, or approximation by finite unions of intervals. Translation invariance and uniform continuity givewhere the approximation error is first made arbitrarily small. Equivalently, $m(B△(B-t))\to 0$.

Choose a return time $n\ge 1$ so small modulo one that for each $1\le j<k$,This is possible because multiplication by each fixed $j$ is continuous on the circle group and translation continuity in L1 on the circle applies to the finitely many translates. The union bound now givesThis proves the Furstenberg multiple recurrence theorem for every circle rotation with its normalized Lebesgue measure, including both rational and irrational angles.