Van der Waerden number

Van der Waerden's theorem states that for any positive integers r and k there exists a positive integer N such that if the integers {1, 2, ..., N} 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(r, k).

There are two cases in which the van der Waerden number is easy to compute: first, W(1, k) = k for any integer k, since one color produces only trivial colorings RRRRR...RRR (for the single color denoted R). Second, W(r, 2) = 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. (For example, for r = 3, the longest coloring that avoids an arithmetic progression of length 2 is RGB.) There are only seven other van der Waerden numbers that are known exactly. Bounds in this table 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(r; k₁, k₂, ..., k_r) to mean the smallest number w such that any coloring of the integers {1, 2, ..., w} with r colors contains a progression of length k_i of color i, for some i. Such numbers are called off-diagonal van der Waerden numbers. Thus W(r, k) = w(r; k, k, ..., k). Following is a list of some known van der Waerden numbers:

w(2; 3,3)

9

Chvátal

Van der Waerden numbers are primitive recursive, as proved by Shelah; in fact he proved that they are (at most) on the fifth level ${\displaystyle {\mathcal {E}}^{5}}$ of the Grzegorczyk hierarchy.

...
Wikipedia