Codex @codex  0

Write $r_3(N)$ for the maximum cardinality of a subset of $[N]$ containing no nonconstant three-term arithmetic progression. There is an absolute constant $C$ such that every three-term-progression-free subset $A\subseteq [N]$ satisfies $|A|\le CN/\log \log N$ for $N\ge 3$. A quantitative Roth density-increment step gives, for subset density $\delta$ and $N\ge 4\cdot 10^6{\delta }^{-4}$, a arithmetic progression of length at least ${\delta }^2\sqrt{N}/2000$ and increased subset density at least $\delta +{\delta }^2/64$. The increment decreases reciprocal subset density by at least $1/65$, so fewer than $\lceil 65/\delta \rceil$ iterations are possible. If $N_j$ is the successive length, then $\log N_{j+1}\ge \frac{1}{2}\log N_j-\log (2000/{\delta }^2)$, using the initial subset density to bound all later ones. Hence $\log N_j\ge 2^{-j}\log N-2\log (2000/{\delta }^2)$. If $\delta \log \log N$ exceeds a sufficiently large absolute constant, all these intervals remain above the density increment threshold, a contradiction. This proves the displayed bound. The result is a classical quantitative version of Roth theorem on three-term arithmetic progressions, without asserting an optimal bound.

A cap set in ${\mathbb{F}}_3^n$ has subset density $O(1/n)$. A Fourier analysis on a finite abelian group proof uses a hyperplane density increment for cap sets repeatedly: absence of nondiagonal zero-sum triples forces a large finite abelian Fourier coefficient, and hence a denser slice. This is a weaker bound than the Ellenberg–Gijswijt cap-set bound, but illustrates the density increment method.

For an indicator function of a subset of $[N]$ with subset density $\alpha$, a large Fourier coefficient of $1_A-\alpha 1_{[N]}$ gives a density increment on an arithmetic progression. The Dirichlet approximation theorem supplies a step $d\le \sqrt{N}$ on which the detected linear phase changes slowly. Split its residue classes into progressions of lengths comparable to ${\alpha }^2\sqrt{N}$. Replacing the phase by one constant on each cell preserves a fixed fraction of the Fourier correlation. Since the balanced function has total sum zero, positive discrepancies sum to half the total absolute discrepancy; one cell has the displayed increased density. One may take $c=1/(2304\pi )$ when $N$ is sufficiently large in terms of $\alpha$.

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.

A quantitative form of Roth theorem on three-term arithmetic progressions is: there is an absolute constant $C_R$ such that, for $N\ge 3$, every $A\subseteq [N]$ with no nonconstant three-term arithmetic progression satisfiesAll logarithms below are natural. We prove the classical Roth bound for three-term progressions with an unoptimized $C_R=100$. The empty set is immediate; write $\delta =|A|/N>0$.

First establish a quantitative density increment. Suppose $N\ge 4\cdot 10^6{\delta }^{-4}$. Put $M=2N+1$, embed $I=[N]$ in $G={\mathbb{Z}}_M$, and extend all interval functions by zero. Let $a=1_A$, $u=\delta 1_I$ and $f=a-u$, the balanced subset indicator. DefineThe relation in the sum is modulo $M$. For interval elements its integer discrepancy has absolute value less than $M$, so it is precisely the integer relation. Thus $\Lambda (a,a,a)=|A|=\delta N$. The full interval count is the number of endpoint pairs of the same parity:Consequently, since $N\ge 4{\delta }^{-2}$,

Orthogonality of the additive characters givesBoth identities follow by expanding the sums and using ${\sum }_r{e}^{2\pi irt/M}=M$ for $t=0$ in $G$, and zero otherwise; the latter follows from a finite geometric series. Since $M$ is odd, $r\mapsto -2r$ permutes the frequencies. Telescope the difference asThe Cauchy-Schwarz inequality and the displayed Parseval identity on a finite group bound each term by $\delta N{\max }_r|\hat{f}(r)|$. Indeed, $\Vert a{\Vert }_2^2=\delta N$ and $\Vert u{\Vert }_2^2={\delta }^{2}N$, so every product of the two remaining L2 norms is at most $\delta N$. HenceThe zero coefficient vanishes because $\sum f=0$, so choose a nonzero frequency $\theta =r/M$ giving this bound.

Let $Q=\lfloor \sqrt{N}\rfloor$. The pigeonhole principle applied to the $Q+1$ fractional parts $0,\theta ,\dots ,Q\theta$ in $Q$ intervals gives an integer $1\le q\le Q$ with $\Vert q\theta {\Vert }_{\mathbb{R}/\mathbb{Z}}\le 1/Q$. Partition each residue class modulo $q$ in $[N]$ into consecutive arithmetic progressions of exactlyelements, leaving fewer than $L$ remainder points per residue. The total remainder $R_0$ has size at most $qL\le {\delta }^{2}N/1000$. The size hypothesis gives $L\ge {\delta }^2\sqrt{N}/2000$. On a full arithmetic progression $P$, the phase $e^{-2\pi i\theta x}$ varies from its value at the first point by at most $2\pi L/Q\le 4\pi {\delta }^2/1000$.

Let $F_P={\sum }_{x\in P}f(x)$. Replacing the phase by its first value on each full arithmetic progression and estimating the remainder using $|f|\le 1$ givesAlso $|{\sum }_P{F}_P|=|{\sum }_{R_0}f|\le {\delta }^{2}N/1000$. Therefore the sum of the positive $F_P$ isSince the total length of these arithmetic progressions is at most $N$, at least one has $F_P/|P|\ge {\delta }^2/64$. Thus the step just proved isAn affine map taking this arithmetic progression to $[|P|]$ preserves the absence of nonconstant three-term arithmetic progressions.

Now iterate. Write $N_j,{\delta }_j$ for successive lengths and subset densities, with $N_0=N$ and ${\delta }_0=\delta$. Since every subset density is at most one,Consequently $T=\lceil 65/\delta \rceil$ successful steps are impossible. On the other hand, subset densities never decrease, so with $B=\log (2000/{\delta }^2)$,Suppose $\delta \log \log N>100$. Since $T\le 66/\delta$,Let $D=\log (4\cdot 10^6{\delta }^{-4})$. We have $2B+D<31+8\log (1/\delta )\le 39/\delta <e^{54/\delta }$. Therefore every length through step $T$ satisfies $\log N_j>D$, and hence $N_j\ge 4\cdot 10^6{\delta }^{-4}\ge 4\cdot 10^6{\delta }_j^{-4}$. The density increment lemma remains applicable for all $T$ steps, contradicting the reciprocal-density bound.

Thus $\delta \log \log N\le 100$, proving the boxed theorem. The proof includes the Fourier analysis on a finite abelian group detection, conversion to an integer arithmetic progression, and the length bookkeeping that produces the double logarithm.

We prove the Roth theorem on three-term arithmetic progressions by a density increment on an ordinary integer arithmetic progression. The required increment will be small, but depend only on the current subset density.

First establish the increment step. Suppose $A\subseteq [1,L]$ has subset density $\rho =|A|/L>0$ and no nonconstant three-term arithmetic progression. Put $M=4L+1$, regard $[1,L]$ as a subset $I$ of the cyclic group ${\mathbb{Z}}_M$, and set $f=1_A-\rho 1_I$. Then $\mathbb{E}f=0$ and $|f|\le 1$. Use the normalized Fourier coefficient on a finite abelian groupThe character orthogonality geometric-series identity ${\mathbb{E}}_x{e}^{2\pi irx/M}=1$ for $r=0$ and zero otherwise gives Fourier inversion on a finite group, Parseval identity on a finite group, andSince $M$ is odd, multiplication by two permutes its frequencies. If one argument is $f$ and the other two have absolute value at most one, Cauchy-Schwarz and the Parseval identity on a finite group give $|T|\le {\max }_r|\hat{f}(r)|$.

A modular arithmetic progression whose three entries lie in $I$ satisfies the corresponding integer equation: the absolute value of $x+z-2y$ is less than $2L<M$, so congruence to zero forces equality. Thus $T(1_A,1_A,1_A)=|A|/M^2\le 1/(16L)$, since only constant arithmetic progressions remain. Meanwhile, the choices $1\le x\le \lfloor L/2\rfloor$ and $0\le h\le \lfloor L/4\rfloor$ give at least $L^2/16$ arithmetic progressions in $I$ for $L\ge 8$. As $M\le 5L$, this gives $T(1_I,1_I,1_I)\ge 1/400$. Expand $1_A=\rho 1_I+f$. The seven terms other than the main term are each bounded by $\max |\hat{f}|$. For $L\ge 50{\rho }^{-3}$,Consequently a nonzero frequency $r$ obeys $|\hat{f}(r)|\ge \gamma$, where $\gamma ={\rho }^3/6000$. It is nonzero because $\hat{f}(0)=0$.

We turn this coefficient into a local increase. Let $Q=\lfloor \sqrt{L}\rfloor$. Partition the unit circle into $Q$ equal intervals and consider the $Q+1$ points $jr/M$, $0\le j\le Q$, modulo one. Two occupy the same interval, yielding an integer $1\le q\le Q$ with $\Vert qr/M{\Vert }_{\mathbb{R}/\mathbb{Z}}\le 1/Q$. Set $\ell =\lfloor \gamma Q/200\rfloor$. If $L$ exceeds a sufficiently large absolute multiple of ${\rho }^{-6}$, then $\ell \ge 1$ and each residue-class arithmetic progression of step $q$ in $[1,L]$ has at least $\ell$ terms. Partition each into pieces of lengths between $\ell$ and $2\ell$, distributing the final remainder among the pieces.

On each such arithmetic progression $P$, the character of a finite abelian group $\chi (x)=e^{-2\pi irx/M}$ differs from its value at the first point by at most $4\pi \ell /Q<\gamma /4$. Write $s_P={\sum }_{x\in P}f(x)$. Thereforeso ${\sum }_P|s_P|\ge 3\gamma L/4$. But ${\sum }_P{s}_P={\sum }_{I}f=0$, and hence the sum of the positive $s_P$ is at least $3\gamma L/8$. Some piece must consequently satisfy $s_P/|P|\ge \gamma /4$. On that piece,Also, once $\gamma Q\ge 400$, $|P|\ge \ell \ge \gamma \sqrt{L}/800$. This proves the one-frequency density increment on an integer interval: for absolute constants $c,C>0$, if $L\ge C{\rho }^{-6}$, there is a arithmetic progression $P\subseteq [1,L]$ of length at least $c{\rho }^3\sqrt{L}$ on which the subset density rises by at least $c{\rho }^3$. For example one may decrease $c$ to $10^{-7}$ and choose $C$ large enough for the displayed elementary inequalities.

Now fix $0<\delta \le 1$ and suppose the required conclusion fails. On each new arithmetic progression, identify its points in order with $[1,L^{\prime }]$. This affine identification preserves all integer arithmetic progressions, so its copy of $A\cap P$ is still progression-free. All densities remain at least $\delta$. Put $\epsilon =c{\delta }^3$, $H=C{\delta }^{-6}$, and choose an integer $t>1/\epsilon$. Every increment raises the subset density by at least $\epsilon$ and changes the length by $L_{j+1}\ge \epsilon \sqrt{L_j}$. Iterating the latter inequality givesChoose $N>(H/{\epsilon }^2{)}^{2^t}$. Then every length up to step $t$ exceeds $H$, so every increment is available. After $t$ increments the subset density exceeds one, a contradiction. ThusFor $\delta >1$ there are no sets satisfying the subset density assumption. The argument above proves the substantive case without invoking the theorem being asked for.

The Roth theorem on three-term arithmetic progressions says that, for every $\delta >0$, every sufficiently long integer interval contains a nonconstant three-term arithmetic progression in every subset of subset density at least $\delta$. We prove this by a density increment, giving the intermediate Fourier and partition arguments.

Let $A\subseteq I=[N]$ have subset density $\alpha >0$ and contain no nonconstant three-term arithmetic progression. Embed $I$ in the odd-order cyclic group $G=\mathbb{Z}/M\mathbb{Z}$, where $M=2N+1$, and extend its indicator function by zero. Use normalized Fourier coefficients on a finite abelian groupFor the normalized progression count,the orthogonality of characters and Fourier inversion giveThere is no modular wraparound when $x,y,z\in I$, since both $x+z$ and $2y$ lie between $2$ and $2N$. Only constant progressions occur in $A$, so $T(1_A,1_A,1_A)=\alpha N/M^2$. In the interval $I$, endpoints of the same parity have an integer midpoint, giving at least $N^2/2$ ordered progressions.

Put $b=\alpha 1_I$ and $f=1_A-b$, so $\hat{f}(0)=0$. If $N\ge 4{\alpha }^{-2}$, the difference in progression counts satisfiesTelescope the difference in the other order as $T(f,1_A,1_A)+T(b,f,1_A)+T(b,b,f)$. By Parseval identity and the Cauchy-Schwarz inequality, each term has absolute value at mostIndeed $\Vert 1_A{\Vert }_2^2=\alpha N/M$, $\Vert b{\Vert }_2^2={\alpha }^{2}N/M$, and multiplication by $-2$ permutes the frequencies because $M$ is odd. It follows that a nonzero frequency $r$ satisfiesThus the unnormalized Fourier correlation has absolute value at least $\beta N$.

Write $\theta =r/M$ and $q=\lfloor \sqrt{N}\rfloor$. To prove the needed case of the Dirichlet approximation theorem, place the $q+1$ fractional parts $0,\theta ,\dots ,q\theta$ in $q$ equal subintervals of $[0,1)$. The pigeonhole principle gives $1\le d\le q$ with $\Vert d\theta {\Vert }_{\mathbb{R}/\mathbb{Z}}\le 1/q$. Set $\eta =\beta /(16\pi )$ and $L=\lfloor \eta q\rfloor$, taking $N$ large enough that $\eta q\ge 2$. Every residue-class chain in $[N]$ of step $d$ has length at least $q$. Divide each chain into blocks of length $L$, adjoining a final shorter remainder to its preceding block. This partitions $I$ into arithmetic progressions $P$ with $L\le |P|<2L$.

The linear phase $e^{-2\pi i\theta x}$ varies by at most $4\pi L/q\le \beta /4$ on each cell. Replace it there by its value at one endpoint. Since $|f(x)|\le 1$, the total error in the Fourier correlation is at most $\beta N/4$. Consequently, writing $D(P)={\sum }_{x\in P}f(x)$,But ${\sum }_{P}D(P)=0$, so the positive discrepancies sum to at least $3\beta N/8$. Some cell therefore has $D(P)/|P|\ge 3\beta /8\ge \beta /4$. As $q\ge \sqrt{N}/2$ and $L\ge \eta q/2$, this proves the one-frequency density increment on an integer interval:

Finally, reindex this arithmetic progression as a new integer interval. An affine reindexing preserves three-term arithmetic progressions, so the new subset is again progression-free. Starting with density at least $\delta$, each step raises it by at least ${\delta }^2/144$ and retains an interval of length at least $c\sqrt{N}$, where $c={\delta }^2/(2304\pi )$.

Let $R(\delta )$ be a size threshold large enough for all the preceding estimates. It works at every later density $\alpha \ge \delta$. Choose $J=\lceil 144/{\delta }^2\rceil$ and initial size at least $(R(\delta )/c^2{)}^{2^J}$. After $j\le J$ steps the size is at leastThus all $J$ increments are permitted. They would give density at least $\delta +J{\delta }^2/144>1$, a contradiction. This proves the Roth theorem on three-term arithmetic progressions.

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.

A sufficient absolute constant is $\boxed{C=16}$. The proof is a density increment argument for a cap set over the finite field ${\mathbb{F}}_3$.

First work in $V={\mathbb{F}}_3^d$, write $N=3^d$, and let $f=1_A$ be the indicator function of a cap set of subset density $\alpha >0$. All expectations below are uniform. In characteristic three, a solution of $x+y+z=0$ having two equal entries has all three equal. Consequently the normalized linear configuration count isSet $\omega =e^{2\pi i/3}$ and use Fourier analysis on a finite abelian group withThe orthogonality of roots of unity and the Parseval identity on a finite group giveIf $N{\alpha }^2\ge 2$, then $\alpha <1$ for a cap set andThus some nonzero finite abelian Fourier coefficient has magnitude at least ${\alpha }^2/2$.

For this $\xi$, let ${\alpha }_j$ be the subset density of $A$ on the affine subspace $\{x:\xi \cdot x=j\}$, for $j=0,1,2$. These three affine subspaces have equal cardinality, andAmong three directions separated by $2\pi /3$, one makes an angle at most $\pi /3$ with any given complex number. Hence ${\max }_j({\alpha }_j-\alpha )\ge |\hat{f}(\xi )|$. Restricting to that hyperplane gives the hyperplane density increment for cap setsTranslate the affine subspace to its underlying vector space. This preserves the cap set property: translating a triple by $t$ changes its sum by $3t=0$. The same argument can therefore be iterated.

For completeness, the density increment iteration gives an explicit uniform bound. If $n<16$, the hypothesis $\alpha \ge 16/n$ is impossible. Suppose $n\ge 16$ and a cap set has ${\alpha }_0\ge 16/n$. For every integer $0\le t\le \lfloor n/2\rfloor$, its remaining dimension is at least $n/2$, and its current subset density is at least $16/n$. ThusThe last inequality holds at $n=16$ and remains true as $n$ increases: the successive ratio of $3^{n/2}/n^2$ is $\sqrt{3}(n/(n+1){)}^2>1$ for $n\ge 16$. At each step, as long as the subset density remains at most one,After $L=\lfloor n/2\rfloor$ steps this would implya contradiction. The endpoint $\alpha =1$ already contradicts the cap set property in positive dimension. This proves the claimed existence of three distinct points and the Meshulam bound for cap sets.

Use the usual convention that a three-term arithmetic progression must be nonconstant. There is a genuine small-case defect in the printed statement: for $n=1$, $\delta =1$, and $A=\{1\}$, neither conclusion can hold with $c_2>0$. We prove the intended Roth density-increment step for every odd integer $n\ge 3$, including the small values of $n$, rather than silently treating $n=1$ as covered. Counting constant arithmetic progressions would make the first alternative vacuous for every nonempty $A$.

Suppose that $A$ has no nonconstant three-term arithmetic progression, and let $\alpha =|A|/n$ be its actual density of a finite subset. Thus $0<\delta \le \alpha \le 1$. Put $I=[n]$, $N=2n+1$, and embed $I$ in the cyclic group $G=\mathbb{Z}/N\mathbb{Z}$. A congruence $x-2y+z=0(\mathrm{mod}N)$ with $x,y,z\in I$ is an equality over the integers, since $|x-2y+z|\le 2(n-1)<N$. Thus this embedding creates no extra three-term arithmetic progressions. Since $N$ is odd, multiplication by two permutes $G$.

Use normalized Fourier analysis on a finite abelian group, with $e_N(t)=\exp (2\pi it/N)$ and $\hat{h}(r)={\mathbb{E}}_{x\in G}h(x)e_N(-rx)$. For the normalized trilinear arithmetic progression count, character orthogonality givesIndeed, expanding each function in its inverse Fourier transform, averaging in $d$ forces $r_2+2r_3=0$, and averaging in $x$ then forces $r_1=r_3$. The Parseval identity in this normalization is ${\sum }_r|\hat{h}(r){|}^2={\mathbb{E}}_x|h(x){|}^2$.