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.^[1]

k\r	2 colors	3 colors	4 colors	5 colors	6 colors
3	9[2]	27[2]	76[3]	>170	>225
4	35[2]	293[4]	>1,048	>2,254	>9,778
5	178[5]	>2,173	>17,705	>98,741[6]	>98,748
6	1,132[7]	>11,191	>157,209[8]	>786,740[8]	>1,555,549[8]
7	>3,703	>48,811	>2,284,751[8]	>15,993,257[8]	>111,952,799[8]
8	>11,495	>238,400	>12,288,155[8]	>86,017,085[8]	>602,119,595[8]
9	>41,265	>932,745	>139,847,085[8]	>978,929,595[8]	>6,852,507,165[8]
10	>103,474	>4,173,724	>1,189,640,578[8]	>8,327,484,046[8]	>58,292,388,322[8]
11	>193,941	>18,603,731	>3,464,368,083[8]	>38,108,048,913[8]	>419,188,538,043 [8]

Some lower bound colorings computed using SAT approach by Marijn J.H. Heule ^[6] can be found on github project page.

Van der Waerden numbers with r ≥ 2 are bounded above by

${\displaystyle W(r,k)\leq 2^{2^{r^{2^{2^{k+9}}}}}}$

as proved by Gowers.^[9]

For a prime number p, the 2-color van der Waerden number is bounded below by

${\displaystyle p\cdot 2^{p}\leq W(2,p+1),}$

as proved by Berlekamp.^[10]

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:

Known van der Waerden numbers

w(r;k1, k2, …, kr)	Value	Reference
w(2; 3,3)	9	Chvátal [2]
w(2; 3,4)	18	Chvátal [2]
w(2; 3,5)	22	Chvátal [2]
w(2; 3,6)	32	Chvátal [2]
w(2; 3,7)	46	Chvátal [2]
w(2; 3,8)	58	Beeler and O'Neil [3]
w(2; 3,9)	77	Beeler and O'Neil [3]
w(2; 3,10)	97	Beeler and O'Neil [3]
w(2; 3,11)	114	Landman, Robertson, and Culver [11]
w(2; 3,12)	135	Landman, Robertson, and Culver [11]
w(2; 3,13)	160	Landman, Robertson, and Culver [11]
w(2; 3,14)	186	Kouril [12]
w(2; 3,15)	218	Kouril [12]
w(2; 3,16)	238	Kouril [12]
w(2; 3,17)	279	Ahmed [13]
w(2; 3,18)	312	Ahmed [13]
w(2; 3,19)	349	Ahmed, Kullmann, and Snevily [14]
w(2; 3,20)	389	Ahmed, Kullmann, and Snevily [14] (conjectured); Kouril [15] (verified)
w(2; 4,4)	35	Chvátal [2]
w(2; 4,5)	55	Chvátal [2]
w(2; 4,6)	73	Beeler and O'Neil [3]
w(2; 4,7)	109	Beeler [16]
w(2; 4,8)	146	Kouril [12]
w(2; 4,9)	309	Ahmed [17]
w(2; 5,5)	178	Stevens and Shantaram [5]
w(2; 5,6)	206	Kouril [12]
w(2; 5,7)	260	Ahmed [18]
w(2; 6,6)	1132	Kouril and Paul [7]
w(3; 2, 3, 3)	14	Brown [19]
w(3; 2, 3, 4)	21	Brown [19]
w(3; 2, 3, 5)	32	Brown [19]
w(3; 2, 3, 6)	40	Brown [19]
w(3; 2, 3, 7)	55	Landman, Robertson, and Culver [11]
w(3; 2, 3, 8)	72	Kouril [12]
w(3; 2, 3, 9)	90	Ahmed [20]
w(3; 2, 3, 10)	108	Ahmed [20]
w(3; 2, 3, 11)	129	Ahmed [20]
w(3; 2, 3, 12)	150	Ahmed [20]
w(3; 2, 3, 13)	171	Ahmed [20]
w(3; 2, 3, 14)	202	Kouril [4]
w(3; 2, 4, 4)	40	Brown [19]
w(3; 2, 4, 5)	71	Brown [19]
w(3; 2, 4, 6)	83	Landman, Robertson, and Culver [11]
w(3; 2, 4, 7)	119	Kouril [12]
w(3; 2, 4, 8)	157	Kouril [4]
w(3; 2, 5, 5)	180	Ahmed [20]
w(3; 2, 5, 6)	246	Kouril [4]
w(3; 3, 3, 3)	27	Chvátal [2]
w(3; 3, 3, 4)	51	Beeler and O'Neil [3]
w(3; 3, 3, 5)	80	Landman, Robertson, and Culver [11]
w(3; 3, 3, 6)	107	Ahmed [17]
w(3; 3, 4, 4)	89	Landman, Robertson, and Culver [11]
w(3; 4, 4, 4)	293	Kouril [4]
w(4; 2, 2, 3, 3)	17	Brown [19]
w(4; 2, 2, 3, 4)	25	Brown [19]
w(4; 2, 2, 3, 5)	43	Brown [19]
w(4; 2, 2, 3, 6)	48	Landman, Robertson, and Culver [11]
w(4; 2, 2, 3, 7)	65	Landman, Robertson, and Culver [11]
w(4; 2, 2, 3, 8)	83	Ahmed [20]
w(4; 2, 2, 3, 9)	99	Ahmed [20]
w(4; 2, 2, 3, 10)	119	Ahmed [20]
w(4; 2, 2, 3, 11)	141	Schweitzer [21]
w(4; 2, 2, 3, 12)	163	Kouril [15]
w(4; 2, 2, 4, 4)	53	Brown [19]
w(4; 2, 2, 4, 5)	75	Ahmed [20]
w(4; 2, 2, 4, 6)	93	Ahmed [20]
w(4; 2, 2, 4, 7)	143	Kouril [4]
w(4; 2, 3, 3, 3)	40	Brown [19]
w(4; 2, 3, 3, 4)	60	Landman, Robertson, and Culver [11]
w(4; 2, 3, 3, 5)	86	Ahmed [20]
w(4; 2, 3, 3, 6)	115	Kouril [15]
w(4; 3, 3, 3, 3)	76	Beeler and O'Neil [3]
w(5; 2, 2, 2, 3, 3)	20	Landman, Robertson, and Culver [11]
w(5; 2, 2, 2, 3, 4)	29	Ahmed [20]
w(5; 2, 2, 2, 3, 5)	44	Ahmed [20]
w(5; 2, 2, 2, 3, 6)	56	Ahmed [20]
w(5; 2, 2, 2, 3, 7)	72	Ahmed [20]
w(5; 2, 2, 2, 3, 8)	88	Ahmed [20]
w(5; 2, 2, 2, 3, 9)	107	Kouril [4]
w(5; 2, 2, 2, 4, 4)	54	Ahmed [20]
w(5; 2, 2, 2, 4, 5)	79	Ahmed [20]
w(5; 2, 2, 2, 4, 6)	101	Kouril [4]
w(5; 2, 2, 3, 3, 3)	41	Landman, Robertson, and Culver [11]
w(5; 2, 2, 3, 3, 4)	63	Ahmed [20]
w(5; 2, 2, 3, 3, 5)	95	Kouril [15]
w(6; 2, 2, 2, 2, 3, 3)	21	Ahmed [20]
w(6; 2, 2, 2, 2, 3, 4)	33	Ahmed [20]
w(6; 2, 2, 2, 2, 3, 5)	50	Ahmed [20]
w(6; 2, 2, 2, 2, 3, 6)	60	Ahmed [20]
w(6; 2, 2, 2, 2, 4, 4)	56	Ahmed [20]
w(6; 2, 2, 2, 3, 3, 3)	42	Ahmed [20]
w(7; 2, 2, 2, 2, 2, 3, 3)	24	Ahmed [20]
w(7; 2, 2, 2, 2, 2, 3, 4)	36	Ahmed [20]
w(7; 2, 2, 2, 2, 2, 3, 5)	55	Ahmed [17]
w(7; 2, 2, 2, 2, 2, 3, 6)	65	Ahmed [18]
w(7; 2, 2, 2, 2, 2, 4, 4)	66	Ahmed [18]
w(7; 2, 2, 2, 2, 3, 3, 3)	45	Ahmed [18]
w(8; 2, 2, 2, 2, 2, 2, 3, 3)	25	Ahmed [20]
w(8; 2, 2, 2, 2, 2, 2, 3, 4)	40	Ahmed [17]
w(8; 2, 2, 2, 2, 2, 2, 3, 5)	61	Ahmed [18]
w(8; 2, 2, 2, 2, 2, 2, 3, 6)	71	Ahmed [18]
w(8; 2, 2, 2, 2, 2, 2, 4, 4)	67	Ahmed [18]
w(8; 2, 2, 2, 2, 2, 3, 3, 3)	49	Ahmed [18]
w(9; 2, 2, 2, 2, 2, 2, 2, 3, 3)	28	Ahmed [20]
w(9; 2, 2, 2, 2, 2, 2, 2, 3, 4)	42	Ahmed [18]
w(9; 2, 2, 2, 2, 2, 2, 2, 3, 5)	65	Ahmed [18]
w(9; 2, 2, 2, 2, 2, 2, 3, 3, 3)	52	Ahmed [18]
w(10; 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)	31	Ahmed [18]
w(10; 2, 2, 2, 2, 2, 2, 2, 2, 3, 4)	45	Ahmed [18]
w(10; 2, 2, 2, 2, 2, 2, 2, 2, 3, 5)	70	Ahmed [18]
w(11; 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)	33	Ahmed [18]
w(11; 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4)	48	Ahmed [18]
w(12; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)	35	Ahmed [18]
w(12; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4)	52	Ahmed [18]
w(13; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)	37	Ahmed [18]
w(13; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4)	55	Ahmed [18]
w(14; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)	39	Ahmed [18]
w(15; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)	42	Ahmed [18]
w(16; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)	44	Ahmed [18]
w(17; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)	46	Ahmed [18]
w(18; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)	48	Ahmed [18]
w(19; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)	50	Ahmed [18]
w(20; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)	51	Ahmed [18]
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[22]

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

See also

• Ramsey number
• Graph coloring