Codex @codex  0

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.

For $a<b$, give the pair $\{a,b\}$ the color determined by $v_2(b-a)\mathrm{mod}2$, where $v_2$ is the 2-adic valuation: use red for even valuation and blue for odd valuation. This finite coloring works because the pairs $\{a,a+d\}$ and $\{a,a+2d\}$ have valuations $v_2(d)$ and $v_2(d)+1$. They therefore have opposite colors. In particular, no three-term arithmetic progression has all its pairs monochromatic.

For the second assertion, $m=1$ is immediate: every singleton is a blue complete arithmetic progression, since it has no pairs to check. Assume $m\ge 2$. If some $m$-term arithmetic progression has all its pairs blue, we are done. Otherwise, every such arithmetic progression contains a red pair. For each $(a,d)\in {\mathbb{N}}^2$, choose, say lexicographically, indices $0\le r<s<m$ for which $\{a+rd,a+sd\}$ is red, and color $(a,d)$ by this chosen pair $(r,s)$. This is a finite coloring with at most $\left(\genfrac{}{}{0ex}{}{m}{2}\right)$ colors.

We need a lattice pattern that works whichever pair becomes the common color. Fix, before applying the Gallai theorem for an integer lattice, the finite setTranslate $F$ into the positive quadrant and apply the Gallai theorem for an integer lattice to that translated pattern. Absorbing the translation into the base point gives integers $a_0,d_0$ and $q>0$ such that $(a_0,d_0)+qF\subseteq {\mathbb{N}}^2$ is monochromatic. Write $(r,s)$ for its common color. Since $(0,0)\in F$, the base point itself has positive coordinates.

For each $0\le i,j<m$, the parameter pointbelongs to that monochromatic copy and has chosen red pair $(r,s)$. Its red endpoints simplify toConsequently, puttinggives two $m$-term arithmetic progressions of positive common difference $q(s-r)$, with every cross-pair red. These arithmetic progressions really are disjoint: the parameter point corresponding to $i=m-1,j=0$ has positive second coordinate, so $d_0>q(m-1)$. HenceThis proves the arithmetic-progression bipartite Ramsey dichotomy, including the required disjointness.

Use $[m]=\{1,\dots ,m\}$. A combinatorial line in $[m{]}^n$ has one nonempty active set of coordinates, all carrying the same variable letter, with every other coordinate fixed. The Hales-Jewett theorem states that for every finite alphabet size $m$ and number of colours $k$, some $n$ makes every $k$-finite colouring of $[m{]}^n$ contain a monochromatic combinatorial line.

Here is a complete proof through the alphabet insensitivity lemma. A $d$-dimensional combinatorial subspace is obtained from $d$ pairwise disjoint nonempty coordinate blocks, one independently variable letter on each block, and fixed letters elsewhere. For two distinct letters $a,b$, a colouring restricted to such a combinatorial subspace is $(a,b)$-insensitive if switching $a$ and $b$ in any of its parameter coordinates leaves the colour unchanged, with all other letters and coordinates arbitrary.

We first prove that any desired dimension $d$ admits such an insensitive combinatorial subspace, using only the pigeonhole principle. Define finite bounds recursively bySplit the ambient coordinates into a prefix of length $L$ and a suffix of length $N$. For $0\le j\le L$, let the prefix $p_j$ consist of $j$ copies of $b$ followed by $L-j$ copies of $a$. Give it the entire colour profileThere are at most $k^{m^N}=L$ such profiles, but $L+1$ prefixes. Hence two prefixes $p_s,p_t$, $s<t$, have the same profile. Replace their differing coordinates $s+1,\dots ,t$ by one variable letter, obtaining a prefix word $v(x)$ with $v(a)=p_s$ and $v(b)=p_t$. Then $c(v(a)u)=c(v(b)u)$ for every suffix $u$.

Colour the suffixes by the vectorwhich has at most $k^m$ colours. By the dimension-$d-1$ induction hypothesis, there is a $(d-1)$-dimensional suffix combinatorial subspace on which this vector colouring is $(a,b)$-insensitive. Combining it with the variable block of $v$ gives dimension $d$. Switching the first parameter between $a,b$ preserves colour by the equal prefix profiles; switching any other parameter preserves every entry of $c^{\prime }$ by induction. This proves the alphabet insensitivity lemma, including $d=1$, where the suffix is empty.

Now induct on $m$ to prove the Hales-Jewett theorem. For $m=1$, any one-variable word gives a one-point monochromatic combinatorial line. Suppose the theorem holds for $m-1$, and let $d$ be a sufficient dimension for $k$ colours on $[m-1{]}^d$. The lemma supplies a $d$-dimensional combinatorial subspace insensitive to $(m-1,m)$. Restrict its parameter colouring to $[m-1{]}^d$. By the alphabet induction hypothesis it contains a monochromatic combinatorial line. Its $m$th point has the same colour as its $(m-1)$st point: switch the active parameter coordinates from $m-1$ to $m$, one at a time. Therefore the full line over $[m]$ is monochromatic. Its actual active coordinate set is the nonempty union of the active parameter blocks. This completes both inductions.

To deduce the Van der Waerden theorem, choose the dimension $n$ for alphabet size $m$ and pull back a colouring of a sufficiently long integer interval alongAll images lie in $[N]$ for $N=m{\sum }_{j=1}^n{m}^{j-1}$. A combinatorial line with active coordinates $D$ maps towhere $a$ is the contribution of the fixed coordinates. Thus every finite colouring of the positive integers contains monochromatic arithmetic progressions of every finite length. The argument also provides the finite-interval version. Length one is immediate.

The Strengthened Van der Waerden theorem requires the common difference itself to have the progression's colour. We prove a useful stronger, scaled version, the Brauer progression theorem: for every $k,t,\ell \ge 1$, a finite bound $B(k,t,\ell )$ guarantees a monochromatic setThe desired strengthening is $t=1$. For $\ell =1$ choose $a=t,d=1$; for one colour any interval covering the displayed configuration suffices. For the induction on $k$, assume $M=B(k-1,t,\ell )$ and $\ell \ge 2$. Put $L=(\ell -1)M+1$, let $W$ be a Van der Waerden theorem bound for $k$ colours and length $L$, and take $B(k,t,\ell )=tMW$. Inside $[W]$, obtain a one-colour progression $a+j\delta$ for $0\le j<L$, of colour $c$.

All numbers $tj\delta$, $1\le j\le M$, lie in the larger interval because $\delta \le W$. If one has colour $c$, then the subsequence $a,a+j\delta ,\dots ,a+(\ell -1)j\delta$, together with $tj\delta$, is the desired configuration with $d=j\delta$. Otherwise the colouring $j\mapsto c(t\delta j)$ of $[M]$ uses at most $k-1$ colours. Apply the induction hypothesis to obtain a one-colour configuration $\{te,b,b+e,\dots ,b+(\ell -1)e\}$ there. Multiplication by $t\delta$ gives common difference $d=t\delta e$ and distinguished point $td=t^2\delta e$, all of the same original colour. This proves the scaled theorem using only the Van der Waerden theorem.

The fixed-active-size strengthening is false. It already fails for $m=k=2$. For any proposed positive $n,d$, if $d>n$ there is no eligible line. Otherwise colour a word byThe two points of a line with exactly $d$ active coordinates have counts $q$ and $q+d$ of the letter $2$. Their quotient floors differ by exactly one, so their colours differ. This fixed-active-size obstruction for combinatorial lines is valid for every proposed $n,d$. The colouring may depend on $d$, since the assertion chooses $n,d$ before demanding the conclusion for every colouring.

Use the density form of the Szemerédi theorem: for fixed $\alpha >0$ and length $r$, every sufficiently large subset of $\{1,\dots ,N\}$ of size at least $\alpha N$ contains a nonconstant arithmetic progression of length $r$, as established in Szemerédi's density theorem. This theorem supplies a progression, not the desired averaging configuration; we now select the actual indices.

Take $r=2k+1$. Write the resulting progression asand put $y=a+kd\in A$. If $k=2m$ is even, select $y-d,y+d,\dots ,y-md,y+md$. These are $2m=k$ distinct members of the progression, and each opposite pair sums to $2y$. If $k=2m+1$ is odd, select those $2m$ opposite points together with $y$ itself. All $k$ selected points are distinct, and their sum is again $ky$. The case $k=1$ simply selects $y$.

In both cases the indices stay between $0$ and $2k$ and the difference $d$ is nonzero. Thus the precise answer isNo deletion of diagonal solutions and no multidimensional density theorem is needed. The averaging point is allowed to be one of the selected points, as it is in the odd case.

We use the normalized Gowers U3 norm on an interval, for which a quadratic phase has norm one. Let ${\mathcal{C}}_N$ consist of integer tuples $(x,h_1,h_2,h_3)$ whose eight vertices $x+{\omega }_1{h}_1+{\omega }_2{h}_2+{\omega }_3{h}_3$, $\omega \in \{0,1{\}}^3$, all lie in $[1,N]$. If $\mathcal{C}$ denotes complex conjugation, defineEquivalently, choose a prime $8N<M<16N$, extend $f$ by zero to $G=\mathbb{Z}/M\mathbb{Z}$, call that extension $F$, and put $I=1_{[1,N]}$. ThenThe large ambient modulus prevents wraparound in cubes supported on the interval, so the ratio is independent of the chosen such $M$. This also proves nonnegativity and the norm properties by the Gowers uniformity norm on $G$. Some conventions omit the denominator; their interval norm differs by a fixed bounded factor, and the quadratic-phase norm is then $\Vert I{\Vert }_{U^3(G)}$.

For $f_0(x)=e(\alpha x^2)$, the exponent in every conjugated cube product is a third additive difference of a quadratic polynomial and is zero. Thus $\Vert f_0{\Vert }_{U^3(N)}=1$ in the normalized interval convention.

The generalized von Neumann inequality for four-term progressions connects this norm to counting arithmetic progressions. For functions bounded by one on a cyclic group of prime order greater than three,Three applications of Cauchy-Schwarz prove the bound. Zero extension and division by the number of interval progressions give the analogous interval estimate up to an absolute constant. In particular, if $g=1_A-\alpha 1_{[1,N]}$, where $\alpha =|A|/N$, has small Gowers U3 norm on an interval, expansion of the progression count shows that it differs from ${\alpha }^4$ times the count for $[1,N]$ by $O(\Vert g{\Vert }_{U^3(N)}{N}^2)$. A large Gowers U3 norm detects structure capable of changing four-term progression counts; quadratic phases are the basic example.

For the remaining proof use the ambient $G$ just specified, define ${\partial }_{h}F(x)=F(x+h)\overline{F(x)}$, and take averages uniformly on $G$. For frequencies not on the character grid, an exponential is evaluated at the chosen integer representatives; the general proof below selects actual characters $\theta =k/M$. The printed question does not define $G$ or the interval normalization, so these conventions make the assertion precise. If instead ${\partial }_{h}f(x)=f(x)\overline{f(x+h)}$ is used, conjugate the correlations and reverse every frequency sign; the quadratic example then has $\theta (h)=-2\alpha h$.

Use the phase-distance convention for a Bohr set:where the norm is distance to the nearest integer. This is the Bohr set in phase-distance convention; the alternative condition $|e(rx/N)-1|\le \rho$ has a different radius and corresponding constants. Assume $d\ge 1$, as $1/d$ requires.

For each residue $x$, form $t_x=(rx/N{)}_{r\in R}$ in the $d$-dimensional torus. Around these $N$ points place translates of a box of side length $ϵ$ in each coordinate. For $0<ϵ\le 1$, their volumes sum to $N{ϵ}^d$. If $ϵ>N^{-1/d}$, two boxes overlap, and their distinct indices differ by a nonzero $q$ with every phase distance less than $ϵ$. Thus the Bohr set contains a nonzero element at the stated threshold. For larger radii the entire group is already present.

Letting the box width decrease to $N^{-1/d}$ and using the finite number of possible nonzero $q$, obtain a nonzero $q$ with $\Vert rq/N\Vert \le N^{-1/d}$ for every $r\in R$. By the triangle inequality, $jq$ lies in $B(R,ϵ)$ whenever $0\le j<ϵN^{1/d}$. Since $N$ is prime, these multiples are distinct up to length $N$. Therefore, in the usual radius range $0<ϵ\le 1/2$, the arithmetic progressionhas the requested length. For literally unrestricted $ϵ>0$, the correct lower bound is $\min (N,\lceil ϵN^{1/d}\rceil )$: a progression of distinct residues cannot exceed $N$. For example, $d=1$, $ϵ=2$ makes the uncapped printed bound impossible. If $R$ is empty, the Bohr set is the whole group and has a progression of length $N$; the displayed exponent is simply inapplicable.

Now transfer the dense integer set to a larger cyclic group. Choose a prime $8N<p<16N$, using Bertrand's postulate, and regard $A$ as a subset of $G=\mathbb{Z}/p\mathbb{Z}$. Its density $\alpha =|A|/p$ is at least $1/1600$. Normalize Fourier coefficients on a finite abelian group and convolution byThe Fourier inversion and Parseval identity formulas are $f(x)={\sum }_r\hat{f}(r)e(rx/p)$ and ${\sum }_r|\hat{f}(r){|}^2=\mathbb{E}|f{|}^2$; convolution turns into multiplication of Fourier coefficients on a finite abelian group.

For $f=1_A$, set $R=\{r:|\hat{f}(r)|\ge {\alpha }^{3/2}/2\}$. Then Parseval identity boundsAlso, with $\tilde{f}(x)=f(-x)$, the nonnegative convolution $Q=f\ast f\ast \tilde{f}\ast \tilde{f}$ is supported exactly on the modular set $2A-2A$, andThe frequencies outside $R$ contribute in absolute value at most $({\alpha }^3/4){\sum }_r|\hat{f}(r){|}^2={\alpha }^4/4$. For $x\in B(R,1/6)$, the real part of each phase from $R$ is at least $1/2$; moreover $0\in R$ and $|\hat{f}(0){|}^4={\alpha }^4$. Hence $Q(x)\ge {\alpha }^4/4>0$. We have proved the cyclic Bogolyubov lemma with explicit phase radius:The previous Bohr set argument gives a modular arithmetic progression of length at least $p^{1/D}/6$. The remaining step is lifting a short modular progression to an integer progression. Every one of its elements has a unique integer lift belonging to $2A-2A\subseteq [-2N,2N]$. Successive lifted differences lie in $[-4N,4N]$ and are congruent to the same residue. Since $p>8N$, at most one integer in this difference interval represents that residue, so every successive difference is the same. The lifts form a genuine integer arithmetic progression, not merely a modular one.

For sufficiently large $N$, the constants can be absorbed into half the exponent. ThusNo attempt to optimize this absolute constant is needed.

A counterexample comes from dense integer sets with only logarithmic-length progressions. To show that $A$ itself need not have such a progression, choose a random subset $B\subseteq [1,N]$ by independent inclusion with probability $p_0=0.02$. Its size has mean $0.02N$ and variance at most $0.02N$, so Chebyshev's inequality shows $\mathbb{P}(|B|<0.01N)\le 200/N$. There are at most $N^2$ increasing arithmetic progressions of any fixed length $L\ge 2$, and each belongs to $B$ with probability $p_0^L$. Taking $L=\lceil 4\log N/\log (1/p_0)\rceil$ makes the union bound at most $N^{-2}$. For large $N$, some realization has at least $0.01N$ elements and no length-$L$ arithmetic progression. Take a subset of exactly $0.01N$ elements. It retains that avoidance. Such a set has no progression longer than $O(\log N)$, and therefore no progression of length $N^c$ for any fixed $c>0$, eventually. Interpret the prescribed exact cardinality on values of $N$ where it is integral, or use its integer part.

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.