# 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).

## Tables of Van der Waerden numbers

There are two cases in which the van der Waerden number W(r, k) is easy to compute: first, when the number of colors r is equal to 1, one has W(1, k) = k for any integer k, since one color produces only trivial colorings RRRRR...RRR (for the single color denoted R). Second, when the length k of the forced arithmetic progression is 2, one has 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. The table below gives exact values and bounds for values of W(r, k); values are taken from Rabung and Lotts except where otherwise noted.
    k\r 2 colors 3 colors 4 colors 5 colors 6 colors 3 9 27  76  >170  >225  4 35 293  >1,048  >2,254  >9,778  5 178 >2,173  >17,705  >98,741  >98,748  6 1,132 >11,191  >157,209  >786,740  >1,555,549  7 >3,703  >48,811  >2,284,751  >15,993,257  >111,952,799  8 >11,495  >238,400  >12,288,155  >86,017,085  >602,119,595  9 >41,265  >932,745  >139,847,085  >978,929,595  >6,852,507,165  10 >103,474  >4,173,724  >1,189,640,578  >8,327,484,046  >58,292,388,322  11 >193,941  >18,603,731  >3,464,368,083  >38,108,048,913  >419,188,538,043
Some lower bound colorings computed using SAT approach by Marijn J.H. Heule can be found on github project page.
Van der Waerden numbers with r ≥ 2 are bounded above by
    $W(r,k)\leq 2^{2^{r^{2^{2^{k+9}}}}}$
as proved by Gowers.
For a prime number p, the 2-color van der Waerden number is bounded below by
    $p\cdot 2^{p}\leq W(2,p+1),$
as proved by Berlekamp.
One sometimes also writes w(r; k$_1$, k$_2$, ..., 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:
Known van der Waerden numbers :
| w(r;k$_1$, k$_2$, …, k$_r$) | Value | Reference |
| w(2; 3,3) | 9 | Chvátal |
| w(2; 3,4) | 18 | Chvátal |
| w(2; 3,5) | 22 | Chvátal |
| w(2; 3,6) | 32 | Chvátal |
| w(2; 3,7) | 46 | Chvátal |
| w(2; 3,8) | 58 | Beeler and O'Neil |
| w(2; 3,9) | 77 | Beeler and O'Neil |
| w(2; 3,10) | 97 | Beeler and O'Neil |
| w(2; 3,11) | 114 | Landman, Robertson, and Culver |
| w(2; 3,12) | 135 | Landman, Robertson, and Culver |
| w(2; 3,13) | 160 | Landman, Robertson, and Culver |
| w(2; 3,14) | 186 | Kouril |
| w(2; 3,15) | 218 | Kouril |
| w(2; 3,16) | 238 | Kouril |
| w(2; 3,17) | 279 | Ahmed |
| w(2; 3,18) | 312 | Ahmed |
| w(2; 3,19) | 349 | Ahmed, Kullmann, and Snevily |
| w(2; 3,20) | 389 | Ahmed, Kullmann, and Snevily (conjectured); Kouril (verified) |
| w(2; 4,4) | 35 | Chvátal |
| w(2; 4,5) | 55 | Chvátal |
| w(2; 4,6) | 73 | Beeler and O'Neil |
| w(2; 4,7) | 109 | Beeler |
| w(2; 4,8) | 146 | Kouril |
| w(2; 4,9) | 309 | Ahmed |
| w(2; 5,5) | 178 | Stevens and Shantaram |
| w(2; 5,6) | 206 | Kouril |
| w(2; 5,7) | 260 | Ahmed |
| w(2; 6,6) | 1132 | Kouril and Paul |
| w(3; 2, 3, 3) | 14 | Brown |
| w(3; 2, 3, 4) | 21 | Brown |
| w(3; 2, 3, 5) | 32 | Brown |
| w(3; 2, 3, 6) | 40 | Brown |
| w(3; 2, 3, 7) | 55 | Landman, Robertson, and Culver |
| w(3; 2, 3, 8) | 72 | Kouril |
| w(3; 2, 3, 9) | 90 | Ahmed |
| w(3; 2, 3, 10) | 108 | Ahmed |
| w(3; 2, 3, 11) | 129 | Ahmed |
| w(3; 2, 3, 12) | 150 | Ahmed |
| w(3; 2, 3, 13) | 171 | Ahmed |
| w(3; 2, 3, 14) | 202 | Kouril |
| w(3; 2, 4, 4) | 40 | Brown |
| w(3; 2, 4, 5) | 71 | Brown |
| w(3; 2, 4, 6) | 83 | Landman, Robertson, and Culver |
| w(3; 2, 4, 7) | 119 | Kouril |
| w(3; 2, 4, 8) | 157 | Kouril |
| w(3; 2, 5, 5) | 180 | Ahmed |
| w(3; 2, 5, 6) | 246 | Kouril |
| w(3; 3, 3, 3) | 27 | Chvátal |
| w(3; 3, 3, 4) | 51 | Beeler and O'Neil |
| w(3; 3, 3, 5) | 80 | Landman, Robertson, and Culver |
| w(3; 3, 3, 6) | 107 | Ahmed |
| w(3; 3, 4, 4) | 89 | Landman, Robertson, and Culver |
| w(3; 4, 4, 4) | 293 | Kouril |
| w(4; 2, 2, 3, 3) | 17 | Brown |
| w(4; 2, 2, 3, 4) | 25 | Brown |
| w(4; 2, 2, 3, 5) | 43 | Brown |
| w(4; 2, 2, 3, 6) | 48 | Landman, Robertson, and Culver |
| w(4; 2, 2, 3, 7) | 65 | Landman, Robertson, and Culver |
| w(4; 2, 2, 3, 8) | 83 | Ahmed |
| w(4; 2, 2, 3, 9) | 99 | Ahmed |
| w(4; 2, 2, 3, 10) | 119 | Ahmed |
| w(4; 2, 2, 3, 11) | 141 | Schweitzer |
| w(4; 2, 2, 3, 12) | 163 | Kouril |
| w(4; 2, 2, 4, 4) | 53 | Brown |
| w(4; 2, 2, 4, 5) | 75 | Ahmed |
| w(4; 2, 2, 4, 6) | 93 | Ahmed |
| w(4; 2, 2, 4, 7) | 143 | Kouril |
| w(4; 2, 3, 3, 3) | 40 | Brown |
| w(4; 2, 3, 3, 4) | 60 | Landman, Robertson, and Culver |
| w(4; 2, 3, 3, 5) | 86 | Ahmed |
| w(4; 2, 3, 3, 6) | 115 | Kouril |
| w(4; 3, 3, 3, 3) | 76 | Beeler and O'Neil |
| w(5; 2, 2, 2, 3, 3) | 20 | Landman, Robertson, and Culver |
| w(5; 2, 2, 2, 3, 4) | 29 | Ahmed |
| w(5; 2, 2, 2, 3, 5) | 44 | Ahmed |
| w(5; 2, 2, 2, 3, 6) | 56 | Ahmed |
| w(5; 2, 2, 2, 3, 7) | 72 | Ahmed |
| w(5; 2, 2, 2, 3, 8) | 88 | Ahmed |
| w(5; 2, 2, 2, 3, 9) | 107 | Kouril |
| w(5; 2, 2, 2, 4, 4) | 54 | Ahmed |
| w(5; 2, 2, 2, 4, 5) | 79 | Ahmed |
| w(5; 2, 2, 2, 4, 6) | 101 | Kouril |
| w(5; 2, 2, 3, 3, 3) | 41 | Landman, Robertson, and Culver |
| w(5; 2, 2, 3, 3, 4) | 63 | Ahmed |
| w(5; 2, 2, 3, 3, 5) | 95 | Kouril |
| w(6; 2, 2, 2, 2, 3, 3) | 21 | Ahmed |
| w(6; 2, 2, 2, 2, 3, 4) | 33 | Ahmed |
| w(6; 2, 2, 2, 2, 3, 5) | 50 | Ahmed |
| w(6; 2, 2, 2, 2, 3, 6) | 60 | Ahmed |
| w(6; 2, 2, 2, 2, 4, 4) | 56 | Ahmed |
| w(6; 2, 2, 2, 3, 3, 3) | 42 | Ahmed |
| w(7; 2, 2, 2, 2, 2, 3, 3) | 24 | Ahmed |
| w(7; 2, 2, 2, 2, 2, 3, 4) | 36 | Ahmed |
| w(7; 2, 2, 2, 2, 2, 3, 5) | 55 | Ahmed |
| w(7; 2, 2, 2, 2, 2, 3, 6) | 65 | Ahmed |
| w(7; 2, 2, 2, 2, 2, 4, 4) | 66 | Ahmed |
| w(7; 2, 2, 2, 2, 3, 3, 3) | 45 | Ahmed |
| w(8; 2, 2, 2, 2, 2, 2, 3, 3) | 25 | Ahmed |
| w(8; 2, 2, 2, 2, 2, 2, 3, 4) | 40 | Ahmed |
| w(8; 2, 2, 2, 2, 2, 2, 3, 5) | 61 | Ahmed |
| w(8; 2, 2, 2, 2, 2, 2, 3, 6) | 71 | Ahmed |
| w(8; 2, 2, 2, 2, 2, 2, 4, 4) | 67 | Ahmed |
| w(8; 2, 2, 2, 2, 2, 3, 3, 3) | 49 | Ahmed |
| w(9; 2, 2, 2, 2, 2, 2, 2, 3, 3) | 28 | Ahmed |
| w(9; 2, 2, 2, 2, 2, 2, 2, 3, 4) | 42 | Ahmed |
| w(9; 2, 2, 2, 2, 2, 2, 2, 3, 5) | 65 | Ahmed |
| w(9; 2, 2, 2, 2, 2, 2, 3, 3, 3) | 52 | Ahmed |
| w(10; 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) | 31 | Ahmed |
| w(10; 2, 2, 2, 2, 2, 2, 2, 2, 3, 4) | 45 | Ahmed |
| w(10; 2, 2, 2, 2, 2, 2, 2, 2, 3, 5) | 70 | Ahmed |
| w(11; 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) | 33 | Ahmed |
| w(11; 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4) | 48 | Ahmed |
| w(12; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) | 35 | Ahmed |
| w(12; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4) | 52 | Ahmed |
| w(13; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) | 37 | Ahmed |
| w(13; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4) | 55 | Ahmed |
| w(14; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) | 39 | Ahmed |
| w(15; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) | 42 | Ahmed |
| w(16; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) | 44 | Ahmed |
| w(17; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) | 46 | Ahmed |
| w(18; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) | 48 | Ahmed |
| w(19; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) | 50 | Ahmed |
| w(20; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) | 51 | Ahmed |
| w(21; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) | 52 | Karki |
Van der Waerden numbers are primitive recursive, as proved by Shelah; in fact he proved that they are (at most) on the fifth level ${\mathcal {E}}^{5}$ of the Grzegorczyk hierarchy.