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.

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

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; k1, k2, ..., kr) to mean the smallest number w such that any coloring of the integers {1, 2, ..., w} 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(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 Referencew(2; 3,3)9Chvá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 of the Grzegorczyk hierarchy.

Van der Waerden number

Bron en licentie