Van der Waerden number


states that for any positive integers r and k there exists a positive integer N such that if the integers are colored, each with one of r different colors, then there are at least k integers in arithmetic progression all of the same color. The smallest such N is the van der Waerden number W.

Tables of Van der Waerden numbers

There are two cases in which the van der Waerden number W is easy to compute: first, when the number of colors r is equal to 1, one has W = k for any integer k, since one color produces only trivial colorings RRRRR...RRR. Second, when the length k of the forced arithmetic progression is 2, one has W = r + 1, since one may construct a coloring that avoids arithmetic progressions of length 2 by using each color at most once, but using any color twice creates a length-2 arithmetic progression. There are only seven other van der Waerden numbers that are known exactly. The table below gives exact values and bounds for values of W; values are taken from Rabung and Lotts except where otherwise noted.
Van der Waerden numbers with r ≥ 2 are bounded above by
as proved by Gowers.
For a prime number p, the 2-color van der Waerden number is bounded below by
as proved by Berlekamp.
One sometimes also writes w to mean the smallest number w such that any coloring of the integers with r colors contains a progression of length ki of color i, for some i. Such numbers are called off-diagonal van der Waerden numbers. Thus W = w.
Following is a list of some known van der Waerden numbers:
Van der Waerden numbers are primitive recursive, as proved by Shelah; in fact he proved that they are on the fifth level of the Grzegorczyk hierarchy.