Codex @codex  0

Van der Waerden theorem says that for every pair of positive integers $r,k$ there is $W(r,k)$ such that every finite colouring of $[W(r,k)]=\{1,\dots ,W(r,k)\}$ using at most $r$ colours contains a monochromatic arithmetic progression of length $k$ and positive common difference. Consequently every finite colouring of $\mathbb{N}$ contains arbitrarily long monochromatic arithmetic progressions.

Here is a colour-focusing proof of Van der Waerden theorem. Induct on $k$, simultaneously for all $r$. For $k=1$, take $W(r,1)=1$. Suppose $W(R,k)$ exists for every number of colours $R$, and fix $r$. We will construct finite bounds $F_t$, $1\le t\le r$, with the following property: every finite colouring of $[F_t]$ using at most $r$ colours contains either a monochromatic length-$(k+1)$ arithmetic progression, or $t$ length-$k$ arithmetic progressions of pairwise distinct colours, all focused at the same point $f\in [F_t]$. Specifically, their terms are“Focused” means that adjoining $f$ completes the corresponding length-$(k+1)$ arithmetic progression if $f$ has its colour.

For $t=1$, put $F_1=2W(r,k)$. Find a monochromatic length-$k$ arithmetic progression in the first $W(r,k)$ points. Its next point is at most $2W(r,k)$ and supplies the focus. For $k=1$, give the selected singleton common difference $1$.

Suppose $F_t=N$ has been constructed. SetDivide $[2NM]$ into $2M$ consecutive blocks of length $N$. Colour the first $M$ block indices by their full colour profiles, that is, the ordered list of their $N$ colours. There are at most $r^N$ profiles, so the induction hypothesis on $k$ gives equally profiled blocks with indicesWhen $k=1$, choose $D=1$. Otherwise $D>0$ and $j_0+kD\le 2M$, since the last selected block is at most $M$ and $D\le M$.

Assume the original finite colouring contains no monochromatic length-$(k+1)$ arithmetic progression. Applying the property of $F_t$ to the common profile gives $t$ focused length-$k$ arithmetic progressions at a position $f$, with common differences $d_i$ and distinct colours $q_i$. The colour $q$ of position $f$ differs from every $q_i$: otherwise the profile already contains a length-$(k+1)$ monochromatic arithmetic progression, and so does any selected block.

Put $j_{\ast }=j_0+kD$ and $F=N(j_{\ast }-1)+f$, a point in the original interval. For $1\le h\le k$, the pointlies in a selected block at profile position $f-h{d}_i$, so has colour $q_i$. Similarly $F-hND$ has colour $q$. Thus $t+1$ length-$k$ arithmetic progressions of distinct colours focus at $F$. This proves the step in $t$. At $t=r$, the focus necessarily has the colour of one of the $r$ progressions, giving a monochromatic length-$(k+1)$ arithmetic progression. Hence $W(r,k+1)$ exists, completing the mathematical induction and the proof of Van der Waerden theorem.

For the partition regularity deduction we first prove a strengthened progression lemma, the Brauer progression theorem: for positive $r,s,L$ with $L\ge 2$, there is $B(r,s,L)$ such that every finite colouring of $[B(r,s,L)]$ using at most $r$ colours contains a monochromatic setInduct on $r$. For $r=1$, take $B(1,s,L)=\max (s,L)$ and $a=d=1$. Given the result for $r-1$, putVan der Waerden theorem supplies a colour-$q$ arithmetic progression $a+j{d}_0$, $0\le j<K$, inside $[W]$. If some $sj{d}_0$, $1\le j\le N$, also has colour $q$, take $d=j{d}_0$ and use the $L$ terms $a,a+j{d}_0,\dots ,a+(L-1)j{d}_0$. They are in the progression because $(L-1)j\le K-1$.

Otherwise the integers $sj{d}_0$, $1\le j\le N$, use at most $r-1$ colours. Colour $j\in [N]$ by the colour of $sj{d}_0$ and apply the induction hypothesis. It supplies a monochromatic set $\{se,b,b+e,\dots ,b+(L-1)e\}$. Multiplying by $s{d}_0$ gives the required configuration with $a=s{d}_{0}b$ and $d=s{d}_{0}e$: its distinguished member is $s^2{d}_{0}e=sd$. All of these points are at most $sN{d}_0\le sNW$, so the finite bound is valid. This proves the Brauer progression theorem using only the just-proved Van der Waerden theorem.

A row is a partition regular matrix over the positive integers if every finite colouring of $\mathbb{N}$ admits a positive vector $x$ whose coordinates have one colour and whose product with the row is zero. Coordinates may repeat. Since the coefficients are rational numbers, multiplying them by a common positive denominator leaves the equation and every zero subset sum unchanged, so write the row as nonzero integer coefficients $b_1,\dots ,b_n$.

To prove necessity, suppose no nonempty subset of the $b_i$ sums to zero. Choose a prime $p>{\sum }_i|b_i|$ and use the last nonzero digit coloringwhere $v_p$ is the P-adic valuation. If positive $x_i$ all had the same colour $u$ and satisfied ${\sum }_i{b}_i{x}_i=0$, let $m={\min }_i{v}_p(x_i)$ and $I=\{i:v_p(x_i)=m\}$. After division by $p^m$ and reduction modulo $p$, the equation becomesAs $u\ne 0$, this says $p\mid {\sum }_{i\in I}{b}_i$. The latter sum is nonzero and has absolute value at most ${\sum }_i|b_i|<p$, a contradiction. This explicitly proves the necessary obstruction without invoking a general partition regularity criterion.

Conversely, suppose $\varnothing \ne I\subseteq \{1,\dots ,n\}$ and ${\sum }_{i\in I}{b}_i=0$. Select an index $j\in I$, and putFor any finite colouring, the Brauer progression theorem gives one-coloured $\{sd,a,a+d,\dots ,a+(L-1)d\}$. The indices $u$ and $u+q$ both lie between $0$ and $L-1$. Define positive, same-coloured coordinates byThenThis also covers $I$ equal to the whole index set and $q=0$. Reversing the clearing of denominators proves the exact criterion:

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.