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.
Best Answer
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.