Is there a simpler proof of Van der Waerden's Theorem when there are only two colors?

http://en.wikipedia.org/wiki/Van_der_Waerden%27s_theorem

The usual approach is to induct on the length of the arithmetic progression, which is difficult to simplify directly to the case of two colors.

Does anyone know a different approach?

Thank you.

-

The case for $k$ colours can be done as an easy induction if the $k=2$ case is available to you.

Indeed, suppose we know that VdW is true for $k-1$. Fix a natural number $M$ and a $k$-colouring of the natural numbers. We seek a monochromatic arithmetic progression of length $M$.

First form a $2$-colouring of the natural numbers as follows: we colour $n$ red if $n$ had colour $k$ and we colour $n$ blue if $n$ had one of the other colours $1,\dots k-1$.

Let $N$ be a Van der Waerden number for $k-1, M$. $N$ exists by the inductive hypothesis.

Now we know from the $k=2$ case that either the red numbers or the blue numbers contain an arithmetic progression of length $N$. If the red numbers do, then we win immediately, since that means that there was an arithmetic progression of length $N>>M$ among colour $k$ in our original colouring. So suppose that there is an arithmetic progression among the blue numbers. In other words, there are natural numbers $a,d$ such that every number of the form $a+md$ (where $m=1,\dots,N$) had one of the colours $1,\dots,k-1$.

Now we form a new $k-1$-colouring of the numbers $1,\dots,N$ as follows: give $m$ the colour that $a+md$ had in the original colouring. By what we have just shown, this is a $k-1$-colouring (not a $k$-colouring). Now, by the definition of $N$ there must be a monochromatic arithmetic progression of length $M$; i.e., there are natural numbers $b,f$ such that $b+jf$ has the same colour (in our new colouring of $\{1,\dots,N\}$) for $j=1,\dots,M$.

We use this arithmetic progression to find a monochromatic arithmetic progression of length $M$ in the original colouring. Namely, we have just shown that the numbers $a+(b+jf)d$, for $j=1,\dots,M$ all have the same colour. But we may write

$$a+(b+jf)d=(a+bd) + j(fd)$$

So this is a monochromatic arithmetic progression for the original colouring. $\Box$

Though the proof is not that short, it uses no clever ideas. Roughly, the strategy of the proof can be summarized as follows:

• Work by induction on the number of colours
• Use the $k=2$ case to find a very long arithmetic progression that only takes values among the first $k-1$ colours.
• Apply Van der Waerden's theorm in the $k-1$ case to find a long arithmetic progression inside this arithmetic progression, and use the fact that an arithmetic progression inside an arithmetic progression is still an arithmetic progression.

What does this mean for your question? It means that there is never going to be a proof of the $2$-colour case that is substantially easier than the general case. Roughly speaking, all of the difficult content of the proof is contained in the $2$-colour case; the arbitrary number of colours is not what makes the proof hard; it is the arbitrary length of the arithmetic progression.

So if there were an easier proof of the $2$-colour case, it would automatically translate into an easier proof of the general case; since no such proof is known to exist, the answer to your question is no.

-

There is Shelah's approach for the Hales Jewett theorem (of which Van der Waerden is a special case). See, http://www.math.unh.edu/~dvf/532/Shelah's_proof

Not sure whether it is simpler, though.

-
The link seems to be that. Here is link to a version saved in Wayback machine. – Martin Sleziak Oct 19 at 17:34