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.

For fixed $\theta >0$, a sufficiently large finite set of integers with additive energy at least $\theta |A{|}^3$ has a nonconstant three-term arithmetic progression. The Balog-Szemerédi-Gowers theorem and Ruzsa modelling lemma reduce the problem to the Roth theorem on three-term arithmetic progressions in a dense cyclic model.

Fix $C$ and write $m=|A|$. Choose the permitted prime $N$ with $Cm<N<2Cm$. Part (ii) gives a subset $A^{\prime }$ of size at least $m/2$ and its cyclic group model $B\subseteq {\mathbb{Z}}_N$. ThusTo apply the interval form of Roth theorem on three-term arithmetic progressions, represent $B$ in $\{0,\dots ,N-1\}$ and split this interval into two consecutive intervals of length at most $\lceil N/2\rceil$. One has at least $|B|/2\ge m/4$ points. After translation, this is an integer subset $B_0$ of an interval of length at most $Cm+1$ and subset density bounded below in terms of $C$ only. Pad the interval to length $L=\lceil N/2\rceil$ if necessary. If $B_0$ had no nonconstant three-term arithmetic progression, part (i) would giveSince $L\to \infty$ with $m$, this is impossible once $m$ is sufficiently large depending only on $C$.

Thus $B$ contains distinct elements $b_1,b_2,b_3$ with $b_1+b_3=2b_2$ modulo $N$. Their distinct preimages $a_1,a_2,a_3\in A^{\prime }$ satisfy $a_1+a_3=2a_2$ in the integers by the Freiman 2-isomorphism. Reordering the endpoints if necessary givesThe required size threshold depends on the fixed constant $C$; it is not a claim uniform in an arbitrarily growing $C$.

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.

First derive the triangle removal lemma from the Szemerédi regularity lemma. Given an allowed deletion fraction $0<\eta <1$, take $d=\eta /10$, $m_0=\lceil 10/\eta \rceil$, and $0<\epsilon \le \min (d/4,\eta /100,1/8)$. Apply part (i), with upper class bound $M$. Delete edges incident with $V_0$, inside each nonexceptional class, between irregular pairs, and between regular pairs of subset density less than $d$. Their total number is at mostThese four terms are bounded respectively by $\epsilon n^2$, $n^2/(2m_0)$, $\epsilon n^2$, and $d{n}^2/2$.

If a triangle in a graph remains, its three vertices lie in three distinct equal classes, all three regular pairs with subset density at least $d$. The permitted regular triangle counting lemma gives at least $(d^3/4)t^3$ triangles in a graph in the original graph, where $t$ is the class size. This lower bound can also be checked directly: all but $2\epsilon t$ vertices of the first class have at least $(d-\epsilon )t$ neighbors in each of the other two. Those neighborhoods are large enough to use the regular pair condition on the remaining pair, giving at least $(d-\epsilon {)}^3{t}^2$ edges between them. Hence the total is at least $(1-2\epsilon )(d-\epsilon {)}^3{t}^3\ge (d^3/4)t^3$.

Since $t\ge n/(2M)$, a surviving triangle in a graph forces at least $d^3{n}^3/(32M^3)$ original triangles in a graph. Thus a graph with fewer than $\xi n^3$ triangles in a graph, where $\xi =d^3/(64M^3)>0$, can be made triangle-free by deleting fewer than $\eta n^2$ edges, for all sufficiently large $n$. This proves the removal lemma needed here.

Now use the triangle-removal proof of Roth theorem. Fix a subset density lower bound $\delta >0$ and suppose $A\subseteq [N]$, $|A|\ge \delta N$, has no nonconstant three-term arithmetic progression. Set $m=2N+1$ and $G={\mathbb{Z}}_m$. Use three disjoint copies $X,Y,Z$ of $G$ and put edges according toDivision by two is valid because $m$ is odd. A triangle in a graph corresponds to $a=y-x$, $b=z-y$, $c=(z-x)/2$ with $a,b,c\in A$ and $a+b=2c$. Since $A\subseteq [N]$ and $|a+b-2c|<m$, this congruence is an integer equality. Progression-freeness therefore forces $a=b=c$.

Every triangle in a graph is consequently of the form $(x,x+a,x+2a)$ with $x\in G,a\in A$, so there are exactly $m|A|$ triangles in a graph. These triangles in a graph are edge-disjoint: an $XY$ edge determines $(x,a)$; a $YZ$ edge determines $a$ and then $x$; and an $XZ$ edge determines $a=(z-x)/2$ and $x$. Eliminating them all requires at least $m|A|$ edge deletions.

The graph has $3m$ vertices but only $m|A|\le mN=O(m^2)$ triangles in a graph. Take $\eta =\delta /100$. For large enough $N$ its triangle in a graph count is below $\xi (3m{)}^3$, so removal requires fewer than $\eta (3m{)}^2=9\delta m^2/100$ deletions. Yeta contradiction. Therefore every fixed positive-density subset of a sufficiently long interval contains a nonconstant three-term arithmetic progression.

This proves the qualitative Roth theorem on three-term arithmetic progressions. The quantitative bound from part 2(i) came from the explicit Fourier iteration; the regularity-removal argument gives a density-dependent threshold without that double-logarithmic estimate.

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 high-energy Roth theorem concludes that, for fixed $\theta >0$, a sufficiently large finite set of integers with additive energy at least $\theta |A{|}^3$ contains a nonconstant three-term arithmetic progression. The size threshold depends on $\theta$, and there is no assumption about the diameter of $A$.

Here is why additive energy replaces interval subset density. The Balog-Szemerédi-Gowers theorem in the small-difference set form proved in Question 3 supplies $B\subseteq A$ with $|B|\ge c_{\theta }|A|$ and $|B-B|\le K_{\theta }|B|$. The Petridis minimal-growth lemma, the Ruzsa triangle inequality, and the Ruzsa modeling lemma, all proved there, then give a subset $B^{\prime }\subseteq B$ of size at least $|B|/16$ and a Freiman s-isomorphism of order eight onto $D\subseteq \mathbb{Z}/q\mathbb{Z}$, whereRepresent $D$ by residues in $\{0,\dots ,q-1\}$. One of the two consecutive half-intervals has subset density bounded below by a positive constant depending only on $\theta$; their lengths tend to infinity with $|A|$. Apply the Roth theorem on three-term arithmetic progressions proved in part (i) to this interval. The resulting three distinct residues satisfy $d_0+d_2=2d_1$ modulo $q$. The inverse Freiman homomorphism preserves that equality and distinctness, so its preimages form a nonconstant three-term arithmetic progression in $B^{\prime }$, hence in $A$.

Large additive energy therefore gives the same three-term progression conclusion after passing to a dense finite model. A forward reference to the detailed lemmas in Question 3 avoids reproving them here.

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.

Embed $A\subseteq [N]$ in the odd cyclic group $G=\mathbb{Z}/(2N+1)\mathbb{Z}$, so additive three-term relations in $A$ cannot wrap around. Form three copies of $G$, putting edges $x\sim y$ when $y-x\in A$, $y\sim z$ when $z-y\in A$, and $x\sim z$ when $(z-x)/2\in A$. A triangle in a graph encodes $a+b=2c$ in $A$. If $A$ has no nonconstant arithmetic progression, every triangle in a graph has $a=b=c$; there are exactly $|G||A|$ triangles in a graph, and they are edge-disjoint. Thus at least $|G||A|$ edges must be removed to eliminate them. For fixed positive subset density of $A$, this is a positive fraction of the squared vertex count, whereas the triangle in a graph count is only quadratic. The triangle removal lemma permits deletion of an arbitrarily small quadratic fraction when the cubic triangle in a graph subset density is sufficiently small. This contradiction establishes Roth theorem on three-term arithmetic progressions.