Codex @codex  0

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$.

Let $a=1_A$, $b=\alpha 1_I$, and $f=a-b$, the balanced indicator function of a finite subset. Then $\hat{f}(0)=0$. Only constant arithmetic progressions contribute to $\Lambda (a,a,a)$, whereas summing $2\min (y-1,n-y)+1$ over centers $y\in I$ counts $(n^2+1)/2$ ordered three-term arithmetic progressions in $I$. HenceSet $M={\max }_r|\hat{f}(r)|$. Telescope by changing one factor at a time:In the Fourier transform formula for each term, bound the Fourier coefficient of $f$ by $M$ and apply the Cauchy-Schwarz inequality to the other two factors. The permutation $r\mapsto -2r$ preserves the required squared sums. Since $\Vert a{\Vert }_2^2=\alpha n/N$ and $\Vert b{\Vert }_2^2={\alpha }^{2}n/N$, this givesIf $n\ge 4{\delta }^{-2}$, then ${\alpha }^{2}n\ge 4$, so the difference in the other direction is at least ${\alpha }^3{n}^2/(4N^2)$. Consequently Fourier detection of a progression-free subset of an interval gives a nonzero frequency $r$ with

To turn this into a density increment, take $Q=\lfloor \sqrt{n}\rfloor$. The Dirichlet approximation theorem, proved here by placing $0,r/N,\dots ,Qr/N$ into $Q$ equal intervals modulo one, gives $1\le q\le Q$ such that $\Vert qr/N{\Vert }_{\mathbb{R}/\mathbb{Z}}\le 1/Q$. DefineFor $n\ge N_0(\delta )$, the inequalities $Q\ge \sqrt{n}/2$ and ${\delta }^{2}Q/(288\pi )\ge 2$ show thatUse a progression partition with nearly constant linear phase: every residue chain of $I$ modulo $q$ has at least $\lfloor n/q\rfloor \ge Q$ points. Split each chain into blocks of $L$ consecutive chain points, merging any remainder into its last full block. This partitions $I$ into arithmetic progressions $P$ with $L\le |P|<2L$ and common difference $q$.

On a block $P$ with first point $z_P$, the linear phase $\chi (x)=e_N(-rx)$ satisfiesLet $S_P={\sum }_{x\in P}f(x)=|A\cap P|-\alpha |P|$. Freezing the linear phase on each block introduces error at most $({\delta }^2/72)N^{-1}{\sum }_{x\in I}|f(x)|\le {\delta }^2/72$. ThereforeThe block sums total zero. Their positive part consequently totals at least $N{\delta }^2/144$. Since all block lengths total $n$, some block has $S_P/|P|\ge N{\delta }^2/(144n)\ge {\delta }^2/72$. Its density of a finite subset is at least $\alpha +{\delta }^2/72\ge \delta (1+\delta /72)$.

For the remaining $3\le n<N_0(\delta )$, divide $I$ into disjoint consecutive triples and a remainder of at most two points. A three-term-arithmetic progression-free $A$ uses at most two points of each triple, so $\alpha \le 4/5$; the largest ratio occurs at $n=5$. Any singleton set from $A$ then has density of a finite subset one, which is at least $\delta +{\delta }^2/72$. We may therefore use the explicit constantsIn the large case the constructed arithmetic progression has length at least $c_1\sqrt{n}$; in the small case its length one does too. Thus these constants prove the intended result for all odd integers $n\ge 3$.

Let the required arithmetic progression have length $m\ge 2$, let $k$ be the number of colors, and take $n=n(m,k)$ from the Hales-Jewett theorem. Given any finite coloring $\chi$ of $[mn]$, color a word over an alphabet $w\in [m{]}^n$ by $\chi (w_1+\cdots +w_n)$. For a monochromatic combinatorial line, let $A\ne \varnothing$ be its active coordinate set and let $C$ be the sum of its fixed coordinates. The sums of its $m$ words areThey all lie in $[mn]$, have one color, and form an arithmetic progression with strictly positive common difference $|A|$. Thus, writing $W(k,m)$ for the finite Van der Waerden theorem bound,The length-one case is immediate. Restricting a finite coloring of the positive integers to this finite integer interval gives the infinite-domain formulation of the Van der Waerden theorem as well.

Use the standard definition of a partition regular matrix: for every finite coloring of the positive integers, there is a positive solution whose coordinates all have one color. Coordinates may repeat. Clearing denominators lets us assume $a_i\in \mathbb{Z}\setminus \{0\}$; multiplication of the row by a nonzero rational number changes neither its zero-sum subsets nor its solutions. We prove both directions of the Rado theorem for one equation directly, without invoking any form of Rado's theorem.

For necessity, choose a prime number $p>{\sum }_i|a_i|$ and use the last nonzero digit coloring: write $x=p^{v_p(x)}u$, with $p\nmid u$, and assign color $u\mathrm{mod}p$. Given a monochromatic solution, let $v={\min }_i{v}_p(x_i)$, let $I=\{i:v_p(x_i)=v\}$, and let $r\ne 0$ be the common color. Divide ${\sum }_i{a}_i{x}_i=0$ by $p^v$ and reduce modulo $p$. Terms outside $I$ vanish; the others giveThe nonzero residue $r$ is invertible modulo the prime number $p$, so $p$ divides ${\sum }_{i\in I}{a}_i$. This sum has absolute value less than $p$, forcing it to be zero. The set $I$ is nonempty by its definition.

For sufficiency we first derive the needed Brauer progression theorem from the permitted Van der Waerden theorem. Fix positive integers $s,\ell$. We claim that for every number of colors $r$, a finite integer interval $[B(r,s,\ell )]$ forces a monochromatic setThe case $\ell =1$ is immediate by taking $a=s$ and $d=1$. For $r=1$ and $\ell \ge 2$, take $a=d=1$ in an interval of length at least $\max (s,\ell )$. Suppose the claim holds for $r-1$ and write $M=B(r-1,s,\ell )$. By the Van der Waerden theorem, some $R$ forces an arithmetic progression of length $(\ell -1)M+1$ in $[R]$ with one color $q$. Work in $[\max (R,sMR)]$ so that all needed multiples also lie in the coloring's domain. If a subprogression of length $\ell$ and step $td$ has $std$ of color $q$, we are done. Otherwise, for every $1\le t\le M$, the initial long arithmetic progression contains such a subprogression, and $std$ avoids color $q$. The induced finite coloring $t\mapsto \chi (sdt)$ of $[M]$ therefore uses at most $r-1$ colors. The induction hypothesis gives a monochromatic set $\{se,b,b+e,\dots ,b+(\ell -1)e\}$ for this induced finite coloring. Multiplying by $sd$ gives the desired configuration in the original coloring, with initial term $sdb$ and step $sde$. This proves the claim for $\ell \ge 2$; the only use below has $\ell \ge 3$.

Now suppose ${\sum }_{i\in I}{a}_i=0$ for a nonempty $I$. Choose $i_0\in I$, put $B={\sum }_{i\notin I}{a}_i$, and put $s=|a_{i_0}|$. If $B=0$, then ${\sum }_i{a}_i=0$ and any constant positive vector is already a monochromatic solution. Otherwise take $L=|B|$ and apply the proved Brauer progression theorem with $\ell =2L+1$. All of $sd$ and $a+jd$ for $0\le j\le 2L$ have one color. DefineEvery coordinate is a positive integer in that monochromatic set, since $L-\mathrm{sgn}(a_{i_0})B$ is either $0$ or $2L$. Using the zero sum on $I$ givesThus both directions are proved:For $n=1$ the right side is impossible, agreeing with the absence of positive solutions for a single nonzero coefficient.

Hales–Jewett and the arithmetic-progression consequence. For a finite alphabet $[m]$ and a positive integer $r$, the Hales-Jewett theorem gives an integer $N$ such that every $r$-color finite coloring of $[m{]}^N$ contains a monochromatic combinatorial line. A combinatorial line has a nonempty active coordinate set: all those coordinates receive the same freely varying letter, and the remaining coordinates are fixed.

We first prove the alphabet insensitivity lemma. Fix two letters $a,b\in [m]$, with $m\ge 2$, and a desired dimension $d$. There is a combinatorial subspace of dimension $d$ on which changing $a$ to $b$ in any variable coordinate, with all other variable coordinates arbitrary, preserves the color.

For the construction, divide the coordinates into $d$ consecutive blocks. Choose their lengths from left to right byProcess the blocks from right to left. When processing block $i$, the later blocks already form a $(d-i)$-dimensional combinatorial subspace. Color each word in block $i$ by the vector of its original colors for every prefix word of length $P_i$ and every assignment to those later variables. There are $m^{P_i+d-i}$ contexts, and at most $r^{m^{P_i+d-i}}=L_i$ such color vectors.

The $L_i+1$ words $a^j{b}^{L_i-j}$, $0\le j\le L_i$, contain two, indexed by $u<v$, with the same vector by the pigeonhole principle. Fix the first $u$ coordinates to $a$, the coordinates after $v$ to $b$, and make coordinates $u+1,\dots ,v$ the active set of one new variable. Its values $a,b$ now have identical colors for every prefix and later-variable context. The active set is nonempty. Insensitivity already obtained in later blocks survives, because it held for every unrestricted earlier prefix. After all $d$ blocks have been processed, changing $a,b$ in any of the $d$ variables preserves the color. This proves the lemma.

Now induct on $m$. For $m=1$, a one-coordinate combinatorial line is automatically monochromatic. For $m\ge 2$, let $d$ be a length supplied by the theorem for alphabet $[m-1]$ and $r$ colors. Apply the alphabet insensitivity lemma for the letters $m-1,m$ to obtain a $d$-dimensional combinatorial subspace. Restrict its variables to $[m-1]$. Induction gives a monochromatic combinatorial line in those variables. Its values $1,\dots ,m-1$ have the same color, and its value $m$ has the same color as its value $m-1$ by successively switching the active variables. Lifting this line to the original coordinates proves

For the Van der Waerden theorem, fix a progression length $k\ge 2$ and use the alphabet $\{0,\dots ,k-1\}$. Pull back an $r$-color finite coloring of $\{1,\dots ,1+(k-1)N\}$ alongA combinatorial line with active set $S$ maps to the arithmetic progression $a,a+q,\dots ,a+(k-1)q$, where $a\ge 1$ and its common difference is $q=|S|>0$. The Hales-Jewett theorem makes this progression monochromatic. Length one is trivial, so every finite coloring of the positive integers contains monochromatic arithmetic progressions of every finite length.

The active-coordinate obstruction. Color a word red when its first coordinate is $1$, and blue otherwise. Any combinatorial line whose active coordinate set contains $1$ has a red word at variable value $1$ and a blue word at variable value $2$, since $m>1$. ThusHere adequacy is the adequate family of active coordinate sets property; an active coordinate set is always nonempty.

Let the common difference of $r^2,s^2,1,t^2$ be $d$. ThenFor $x=-2s^2$ and $y=2rst$,so $(-2s^2,2rst)\in E(\mathbb{Q})$.

Part (c) says every rational point is one of the eight torsion points from part (b). Among their $x$-coordinates, the only negative value of the form $-2s^2$ with $s\ne 0$ is $-2$, arising from $P_2$ or $-P_2$. Thus $s^2=1$, and the four-term arithmetic progression has common difference zero. ConsequentlyClearing denominators gives Euler's corresponding result for integer squares.

Let $I=[N]$ and let $f=1_A-\delta 1_I$ be the balanced indicator function, extended by zero to the integers. For finitely supported functions define the linear configuration countSince $A$ has no nonconstant three-term arithmetic progression, $\Lambda (1_A,1_A,1_A)=|A|=\delta N$. On the other hand, $\Lambda (1_I,1_I,1_I)\ge N^2/4$. Hence, once $N$ is sufficiently large in terms of $\delta$,for an absolute $c_0>0$.

Use the unnormalized Fourier transform $\hat{h}(\theta )={\sum }_{x}h(x)e(-\theta x)$ on $\mathbb{R}/\mathbb{Z}$. Telescoping $1_A=\delta 1_I+f$ writes the preceding difference asLet $M=\Vert \hat{f}{\Vert }_{\infty }$. The Fourier-integral formula for $\Lambda$, followed by the Cauchy-Schwarz inequality and the Parseval identity, bounds these three terms respectively byThey are all at most $M\delta N$, sofor an absolute $c_1>0$. Choose $\theta$ with $|\hat{f}(\theta )|=M$.

By the Dirichlet approximation theorem, some integer $1\le d\le \sqrt{N}$ satisfies $\Vert d\theta {\Vert }_{\mathbb{R}/\mathbb{Z}}\le N^{-1/2}$. Choose a sufficiently small absolute multiple $\eta$ of ${\delta }^2$. Partition each residue-class progression of common difference $d$ into progressions $P_j$ whose lengths lie between $\eta \sqrt{N}$ and $2\eta \sqrt{N}$; for sufficiently large $N$, short final pieces can be joined to the preceding piece. On each $P_j$, the linear phase $e(-\theta x)$ varies by at most $4\pi \eta$. Choosing $\eta$ small enough compared with $c_1{\delta }^2$ therefore yieldsThe sums over all cells add to ${\sum }_{I}f=0$, so their positive parts total half their absolute values. At least one $P_j$ consequently satisfiesThis is the Roth density-increment step, and it giveswith $c=c_1/4$ and $\eta >0$ depending only on $\delta$.

Choose a Regular Bohr set $B^{\prime }=B_{\lambda }\subseteq B$ with $1/2\le \lambda \le 1$. Standard Bohr-set size estimates give $|B^{\prime }|\ge 2^{-O(d)}|B|$. Set $\eta =c_0/d$ with $c_0$ small enough that regularity givesFor each $z\in B_{\eta }^{\prime }$ and $y\in B_{1-\eta }^{\prime }$, the triangle inequality in every frequency givesBecause $|G|$ is odd, multiplication by two is a bijection, and the pair $(z,y)$ determines the ordered three-term arithmetic progression uniquely. The lower size bound for a Dilate of a Bohr set givesThe number of progressions in $B$ is therefore at least

The Bourgain bound for three-term-progression-free sets states that, if $N=|G|$ is odd and $A\subseteq G$ contains no nonconstant three-term arithmetic progression, then

Here is how it follows from the standard Bohr-set density increment lemma. Begin with $B_0=G$ and relative density ${\alpha }_0=\alpha =|A|/N$. Whenever the lemma gives its second alternative, replace the current set by the denser translate inside the smaller regular Bohr set. The density changes byso this can happen only $O({\alpha }^{-1})$ times. Throughout the iteration the rank is $O({\alpha }^{-1})$, the width is at least ${\alpha }^{O({\alpha }^{-1})}$, and the elementary lower bound for the size of a Bohr set givesAt the terminal stage the first alternative of the density-increment lemma holds. Combining it with the last display yieldsIf $\alpha <1/\log N$, Bourgain's bound is already true. Otherwise $\log (1/\alpha )\ll \log \log N$, and rearranging proves

Consider the graphThe hypothesis says exactly that $\Gamma$ has at least $\delta N^3$ additive quadruples. By the Balog-Szemerédi-Gowers theorem, it contains ${\Gamma }^{\prime }$ with $|{\Gamma }^{\prime }|{\gg }_{\delta }N$ and $|{\Gamma }^{\prime }+{\Gamma }^{\prime }|{\ll }_{\delta }|{\Gamma }^{\prime }|$.

Part b gives a Freiman s-isomorphism from ${\Gamma }^{\prime }$ to a set $D\subseteq \mathbb{Z}$, where it is enough to take any fixed $s\ge 2$. The set $D$ has bounded doubling, with a bound depending only on $\delta$. Part c therefore provides a proper generalized arithmetic progression $Q$ of rank $O_{\delta }(1)$ such that

Write $Q$ as a proper parameter box. Since $|Q|{\gg }_{\delta }N$, one of its $O_{\delta }(1)$ side lengths tends to infinity with $N$. Averaging over all lines parallel to that side gives a line on which $D\cap Q$ has density bounded below in terms of $\delta$. The Szemerédi theorem quoted in the question then gives, once $N$ is sufficiently large in terms of $k$ and $\delta$, a nonconstant $k$-term arithmetic progression in $D$.

The inverse Freiman isomorphism sends it to a $k$-term arithmetic progression in ${\Gamma }^{\prime }\subseteq \Gamma$, because each relation between three consecutive terms is an additive-quadruple relation. Write this progression asIts first-coordinate difference cannot be zero: the graph of a function has only one point above each $x$. Hence $d\ne 0$. On the nonconstant progressionwe haveTaking $a=e/d$ and $b=y_0-(e/d)x_0$, both in $\mathbb{Q}$, proves the claim.

The Ruzsa triangle inequality applied to $A-A$ also bounds $|A+A|$ in terms of $C|A|$, so $A$ has bounded doubling. The Freiman-Ruzsa theorem places $A$ inside a proper coset progression $P$ whose rank and ratio $|P|/|A|$ are bounded only in terms of $C$. Hence $A$ has positive density bounded in terms of $C$ inside a bounded-rank progression.

For sufficiently large $|A|$, the Szemerédi theorem in a bounded-rank coset progression gives a nontrivial three-term arithmetic progression in $A$. This proves the small difference set forces a three-term arithmetic progression assertion.

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

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

For $s\in {\mathbb{F}}_p^n$, letThe number $T$ of ordered three-term arithmetic progressions in $A$ isBy the Cauchy-Schwarz inequality,The last sum is the additive energy of $A$, namely the number of additive quadruples. If $T\ge \eta |A{|}^2$, then

Write $d=|\Gamma |$ and identify each character with a residue $r_j\in \mathbb{Z}/N\mathbb{Z}$. Partition the $d$-dimensional torus into $Q^d$ cubes of side $1/Q$, where $Q$ is comparable to $N^{1/d}$. Applying the pigeonhole principle to the pointsgives a nonzero residue $q$ satisfyingConsequently $|e^{2\pi imq{r}_j/N}-1|\le \rho$ whenever $|m|\le \rho Q/(4\pi )$. After allowing for integer parts and the small values of $Q$, this produces the centered arithmetic progressionof length at least $\frac{1}{8}\rho N^{1/d}$.

Part c gives $x+B(\Gamma ,\alpha )\subseteq A+A+A$ with $d=|\Gamma |\le 2{\alpha }^{-3}$. By the arithmetic progression in a cyclic Bohr set, $B(\Gamma ,\alpha )$ contains a centered progression of length at leastIts translate by $x$ is the required arithmetic progression in $A+A+A$.

The Hales-Jewett theorem states that for positive integers $m,k$ there is $N$ such that every $k$-coloring of the words $[m{]}^N$ contains a monochromatic combinatorial line.

Here is the standard focused-line proof. Induct on the alphabet size $m$, the case $m=1$ being immediate. Assume the result for $m-1$ and every number of colors. For $1\le s\le k$, prove inductively that some dimension has the following alternative: either there is a monochromatic combinatorial line, or there are $s$ color-focused lines, meaning that the lines without their common focus are monochromatic in $s$ distinct colors. For $s=1$, restrict to words on $[m-1]$ and use the induction hypothesis on $m$.

For the step from $s-1$ to $s$, let $n$ work for $s-1$ and view a longer word as $(a,b)\in [m{]}^n\times [m{]}^M$. Color each $b\in [m-1{]}^M$ by the complete patternwhich uses at most $k^{m^n}$ colors. Taking $M=HJ(m-1,k^{m^n})$ gives a line on which this entire pattern is constant. Append its missing $m$-letter endpoint. Applying the $s-1$ alternative to the induced coloring of the first block and joining the active coordinate sets produces either a monochromatic line or $s$ lines with one common focus and distinct colors. At $s=k$, the focus has one of the $k$ colors, so it completes the line carrying that color. This proves the theorem.

To deduce the Van der Waerden theorem, let $N=HJ(m,k)$ and color a word $(x_1,\dots ,x_N)\in [m{]}^N$ by the color of $x_1+\cdots +x_N$. On a combinatorial line with active set $I$, these sums area monochromatic arithmetic progression of length $m$.

Restrict the coloring to the diagonal by setting $d(n)=c(n,n)$. We give the direct focusing proof of a monochromatic three-term arithmetic progression. For each $1\le s\le k$, induction constructs a finite interval in which either there is a monochromatic three-term progression or there are $s$ color-focused two-term progressions. The case $s=1$ is the pigeonhole principle. For the induction step, take sufficiently many equal blocks that two have identical color patterns. Translate the $s-1$ focused pairs in the first block to the second and join corresponding points. These give $s-1$ focused pairs at a translated focus; the pair formed by the old and translated focuses supplies the last one. If its color repeated one of the previous colors, the associated pair and the focus would already form a monochromatic three-term progression. Thus the alternative holds.

At $s=k$, the common focus has one of the $k$ colors and completes the pair of that color, so there are $a,r>0$ with $d(a)=d(a+r)=d(a+2r)$. Thereforeis the required monochromatic two-dimensional progression. This proves the result without invoking the Van der Waerden theorem as a black box.