Van der Waerden number

From testwiki
Jump to navigation Jump to search

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

W(r,k)≤22r22k+9

as proved by Gowers.[9]

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

p⋅2p≤W(2,p+1),

as proved by Berlekamp.[10]

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 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 ℰ5 of the Grzegorczyk hierarchy.

See also

References

Template:Reflist

Further reading

  1. ↑ Template:Cite journal
  2. ↑ 2.00 2.01 2.02 2.03 2.04 2.05 2.06 2.07 2.08 2.09 2.10 Template:Cite encyclopedia
  3. ↑ 3.0 3.1 3.2 3.3 3.4 3.5 3.6 Template:Cite journal
  4. ↑ 4.0 4.1 4.2 4.3 4.4 4.5 4.6 4.7 Template:Cite journal
  5. ↑ 5.0 5.1 Template:Cite journal
  6. ↑ 6.0 6.1 Template:Cite journal
  7. ↑ 7.0 7.1 Template:Cite journal
  8. ↑ 8.00 8.01 8.02 8.03 8.04 8.05 8.06 8.07 8.08 8.09 8.10 8.11 8.12 8.13 8.14 8.15 8.16 8.17 Template:Cite arXiv
  9. ↑ Template:Cite journal
  10. ↑ Template:Cite journal
  11. ↑ 11.00 11.01 11.02 11.03 11.04 11.05 11.06 11.07 11.08 11.09 11.10 11.11 Template:Cite journal
  12. ↑ 12.0 12.1 12.2 12.3 12.4 12.5 12.6 Template:Cite thesis
  13. ↑ 13.0 13.1 Template:Cite journal
  14. ↑ 14.0 14.1 Template:Cite journal
  15. ↑ 15.0 15.1 15.2 15.3 Template:Cite journal
  16. ↑ Template:Cite journal
  17. ↑ 17.0 17.1 17.2 17.3 Template:Cite journal
  18. ↑ 18.00 18.01 18.02 18.03 18.04 18.05 18.06 18.07 18.08 18.09 18.10 18.11 18.12 18.13 18.14 18.15 18.16 18.17 18.18 18.19 18.20 18.21 18.22 18.23 18.24 18.25 18.26 Template:Cite journal
  19. ↑ 19.00 19.01 19.02 19.03 19.04 19.05 19.06 19.07 19.08 19.09 19.10 Template:Cite journal
  20. ↑ 20.00 20.01 20.02 20.03 20.04 20.05 20.06 20.07 20.08 20.09 20.10 20.11 20.12 20.13 20.14 20.15 20.16 20.17 20.18 20.19 20.20 20.21 20.22 20.23 20.24 20.25 20.26 20.27 20.28 20.29 Template:Cite journal
  21. ↑ Template:Cite thesis
  22. ↑ Template:Cite journal
  23. ↑ Template:Cite journal
Retrieved from "https://en.wiki.beta.math.wmflabs.org/w/index.php?title=Van_der_Waerden_number&oldid=18875"