# Proof of the van der Waerden theorem

The van der Waerden theorem states that given any natural numbers $k$ and $r$, there exists a natural number $W=W(k,r)$ such that if the set $\{1,2\cdots W\}$ is divided into $r$ classes (also called colors) then there exists a $k$-term arithmetic progression in one class.

I am trying to prove the theorem according to the outline given here.

I have understood the proofs for $W(3,2) \le 325$ and $W(3, 3) \le 7(2·3^7+1)(2·3^{7·(2·3^7+1)}+1)$ and on similar lines have worked out a proof for $W(3,4)\le 9(2.4^9+1)(2.4^{9(2.4^9+1)}+1)(2.4^{9(2.4^9+1)(2.4^{9(2.4^9+1)}+1)}+1)$.

What I want to do is to prove the theorem in general on similar lines. The main problem is for me as to what will be the upper bound to start off with and then how to deal with the cumbersome notation.

I understand asking someone to prove the full result is not appropriate here, but if you can give me any help I will greatly appreciate it.

Thanks.

-
Take a look at the book by Graham, Rothschild, and Spencer - Ramsey Theory, which treats Van der Waerden's Theorem. –  Joseph Malkevitch May 4 '12 at 14:31
I have that book. It also just establishes W(3,3) by the same method in the link above and then states that the theorem is proved in general by induction on similar lines. It does not give the proof. My precise problem is to prove it using similar lines. –  Shahab May 4 '12 at 14:34
Terence Tao's article on the arXiv contains a crystal-clear proof of Van der Waerden's theorem (see pages 4 and 5). –  Ewan Delanoy May 31 '12 at 13:09
Thanks, but you misunderstand. I explicitly want a proof on the lines mentioned above since having worked out the examples I understand properly the idea of "focussing the k-1 AP's on one point".(although it may be the essential technique is the same). Tao's proof (which I had seen previously here is rigid but I can't seem to wrap my head around it. –  Shahab May 31 '12 at 13:22
I think Tao's proof is just a different presentation, and yields exactly the same bounds for $W$. –  Ewan Delanoy May 31 '12 at 13:51

Since you already have a proof for $W(3,4)$ and you say you have read the GRS book, I am going to skip any discussion of how the proof actually works, and just focus on the part you say you are missing, which is the induction. This is actually a triple induction, first on the number of colors $c$ for fixed progression length $n$, then on the progression length $n$

Then for particular $(c, n)$ pair, we inductively find, for each $i$, a structure which contains a single "target$^i$" integer which would necessarily completes a progression if it is any of $i$ different colors. Once $i=c$ we are done.

The base cases are that $W(2, c) = c+1$, and $W(n, 1) = 1$, even easier.

Now we want to find a bound for $W(n, c)$. We can assume $n>2$, $c>1$, and we know some $W(n', c')$ for all pairs $(n', c') < (n, c)$, which means that either $n'<n$ or ($n'=n$ and $c'<c$).

I have not edited the following very carefully, and I wrote it rather off-the-cuff, so there may be many errors, especially off-by-one errors. But I think the idea is sound and well-documented. I will be glad to get comments and corrections.

Consider a block $B_1$ of $b_1 = 2W(n-1, c)-1$ elements; we can be sure that the first half of this block (elements $1\ldots W(n-1,c)$) contains a length-$(n-1)$ monochromatic progression of some color $\chi_1$. If the progression is $x_1, x_2, \ldots x_{n-1}$ then $B_1$ also contains a "target element" $2x_{n-1} - x_{n-2}$. If this element is color $\chi_1$ we are done, so assume that it is some other color.

Now consider a superblock $B_2$ consisting of $b_2 = 2W(n-1, c^{b_1})-1$ blocks of size $b_1$. (I have $W(n-1, c^{b_1}$) by the induction hypothesis.) I will imagine that this is a sequence of blocks each of which is colored with one of $c^{b_1}$ colors. I can assume that the first half of this sequence (elements $1\ldots W(n-1, c^{b_1})$) contains a progression of $n-1$ identically-colored blocks. Each of these contains a "target element" which by the previous paragraph cannot be colored with color $\chi_1$; say they are all color $\chi_2$. By the construction is GRS, the target elements themselves form a monochromatic arithmetic progression of length $n-1$ and they point to a "target² element" which cannot be color $\chi_1$ or $\chi_2$. Then say that the target² element is color $\chi_3$.

Now we are going to jump to the induction step. I have an super$^{d-1}$-block consisting of $b_{d+1} = 2W(n-1, c^{b_d})-1$ blocks of size $b_d$. I can assume that the first half of this sequence (elements $1\ldots W(n-1, c^{b_d})$) contains a progression of $n-1$ identically-colored blocks. Each of these contains a "target$^{d-1}$ element" which cannot be color $\chi_1\ldots\chi_{d-1}$, and the $n-1$ target$^{d-1}$ elements form a monochromatic arithmetic progression of some color, say $\chi_d$, whose next element therefore becomes a "target$^d$ element" which cannot be color $\chi_1\ldots\chi_d$.

It suffices to apply this induction step $c$ times, so the final block is the super$^{c-1}$-block consisting of $b_c = 2W(n-1, c^{b_{c-1}})-1$ super$^{c-2}$ blocks of size $b_{c-1}$

This is enough to prove that $W(n, c)$ actually exists. But we might like to know how big it is. We have $b_{d} = 2W(n-1, c^{b_{d-1}})-1$ and $W(n, c) = \prod_1^c{b_i}$ which gives a recurrence for a bound on the size of $W$. I have to get back to work now so I will leave that for you.

I expect this to contain many errors, so I have made it community-Wiki, and I cheerfully invite everyone to edit the answer without consulting me.

-
@MD:I was going through your proof again today and found that this sentence is unclear: The target$^d$ element cannot be color $\chi_1\chi_2\cdots\chi_d$. The cumbersome notation that was my problem originally was precisely in focusing various (k-1)AP's part and it is talked of precisely in this sentence. Can you clarify why each $\chi_i$ (not just $\chi_d$) will be avoided by the target$^d$ element? –  Shahab May 31 '12 at 12:15
I will try to get back to this in a couple of days. –  MJD Jun 2 '12 at 20:19

In addition to the two parameters $k$ and $r$, you must introduce another parameter $j$ corresponding to the depth of your groups-inside-groups-inside-groups in the proof.

This leads to the following (complicated but unavoidably so) definition of a function $V(k,r,j)$ for $k\geq 2, r\geq 1, j \geq 0$ :

$$V(2,r,j)=2j+1 \ (j\geq 0)$$

$$V(k,r,0)=1 \ (k\geq 2,r \geq 1)$$

$$V(k,r,j+1)=V(k,r,j)V(k-1,r^{V(k,r,j)},r^{V(k,r,j)}) \ (k\geq 2,r \geq 1,j\geq 0)$$

Then we have by double induction on $j$ and $k$ :

THEOREM. Any integer interval of size $V(k,r,j)$, colored with $r$ colors, contains a nested $k-1$-progression of $k-1$-progressions of $(k-1)$-progressions ... (with depth $j$) where any nested progression $P$ focuses on some integer $x_P$ after it, and the next nested progression is formed of $k-1$ reguarly spaced translates of $P \cup \lbrace x_P \rbrace$.

When we take $j=r$ in the theorem, there are $r+1$ focused endpoints $x_P$ so at least two of them must have the same color, so there is a monochromatic $k$-progression. We deduce

COROLLARY. $W(k,r) \leq V(k,r,r)$.

You can check as an exercice that $$V(3, 3,3)= 7(2·3^7+1)(2·3^{7·(2·3^7+1)}+1)$$ and $$V(3,4,4)= 9(2.4^9+1)(2.4^{9(2.4^9+1)}+1)(2.4^{9(2.4^9+1)(2.4^{9(2.4^9+1)}+1)}+1)$$

-