Van der Waerden's theorem

Van der Waerden's theorem is a theorem of the branch of mathematics called Ramsey theory. The theorem is about the basic structure of the integers.

Related Topics:
Mathematics - Ramsey theory - Integer

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

It is named for Dutch mathematician B. L. van der Waerden.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Van der Waerden's theorem states that for any given positive integers C and N, there is some number V(C, N) such that if

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

the integers {1, 2, ..., V(C, N)} are colored, each with one of C

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

different colors, then there are at least N integers in arithmetic progression all of the same color.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

For example, when C=2, you have two colors of paint, say red and blue. V(2, 3) is bigger than 8, because you can color the integers from {1,...,8} like this:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

1 2 3 4 5 6 7 8

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

B R R B B R R B

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

and no three integers of the same color form an arithmetic progression. But you can't add a ninth integer to the end without creating such a progression. If you color the number 9 red, you get

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

1 2 3 4 5 6 7 8 9

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

B R R B B R R B R

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

and if you color it blue you get

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

1 2 3 4 5 6 7 8 9

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

B R R B B R R B B

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Of course, this doesn't prove that there is no way to color the integers {1,...,9} so that there is no single-colored arithmetic progression.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

It is an open problem to determine the values of V(C, N) for various C and N. The proof of the theorem provides only an

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

upper bound. For the case of C=2 and N=3, for example, van der Waerden's theorem says it is sufficient to color the integers

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

For C=3 and N=3, the bound given by the theorem is 7(2·37+1)(2·37·(2·37+1)+1), or approximately 4.22·1014616.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

But actually, you don't need that many integers to guarantee a single-colored progression of length 3; you only need 27. (It is possible to color {1,...,26} with three colors so that there is no single-colored arithmetic progression of length 3; for example, RRYYRRYBYBBRBRRYRYYBRBBYBY.)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Anyone who can reduce the general upper bound to any 'reasonable' function can win a large cash prize. The current record

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

is due to Timothy Gowers , who establishes

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: V(C,N) ≤ 2^(2^(C^(-2^(2N+9)))),

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

by first establishing a similar result for Szemerédi's theorem, which is a stronger version of van der Waerden's theorem.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The previously best known bound was due to Saharon Shelah and proceeded via first proving a result for the Hales-Jewett theorem, which is another strengthening of van der Waerden's theorem.

Related Topics:
Saharon Shelah - Hales-Jewett theorem

~ ~ ~ ~ ~ ~ ~ ~ ~ ~