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.{{cite journal | first1=John | last1=Rabung | first2=Mark | last2=Lotts | title=Improving the use of cyclic zippers in finding lower bounds for van der Waerden numbers | year=2012 | volume=19 | issue=2 | journal=Electron. J. Combin. | doi=10.37236/2363 | mr=2928650 | url=http://www.combinatorics.org/ojs/index.php/eljc/article/view/2363| doi-access=free }}

class="wikitable"

! k\r

! 2 colors

! 3 colors

! 4 colors

! 5 colors

! 6 colors

| 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

| 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

| style="text-align:right;"| 178

| style="text-align:right;"| >2,173

| style="text-align:right;"| >17,705

| style="text-align:right;"| >98,741{{

cite journal

| last = Heule

| first=MarijnJ

| title= Avoiding triples in arithmetic progression

| journal = Journal of Combinatorics

| volume = 8

| year = 2017

| issue=3

| pages = 391–422

| doi=10.4310/JOC.2017.v8.n3.a1

|url=https://www.cs.cmu.edu/~mheule/publications/JOC_08_03_A01.pdf

}}

| style="text-align:right;"| >98,748

| style="text-align:right;"| 1,132

| style="text-align:right;"| >11,191

| style="text-align:right;"| >157,209

{{cite arXiv |last=Monroe |first=Daniel |date=2019 |title=New Lower Bounds for van der Waerden Numbers Using Distributed Computing |class=math.CO |eprint=1603.03301}}

| style="text-align:right;"| >786,740

| style="text-align:right;"| >1,555,549

| 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

| 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

| 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

| 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

| 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 [https://github.com/marijnheule/vdWaerden github project page].

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

: $W(r,k)\le 2^{2^{r^{2^{2^{k+9}}}}}$

as proved by Gowers.{{cite journal|author-link=Timothy Gowers|first=Timothy|last=Gowers|title=A new proof of Szemerédi's theorem|journal=Geom. Funct. Anal.|volume=11|issue=3|pages=465–588|url=https://www.cs.umd.edu/~gasarch/TOPICS/vdw/sz-thm-gowers-proof.pdf|year=2001|mr=1844079|doi=10.1007/s00039-001-0332-9|s2cid=124324198 }}

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

: $p\cdot2^p\le W(2,p+1),$

as proved by Berlekamp.{{cite journal |last=Berlekamp |first=E. |title=A construction for partitions which avoid long arithmetic progressions |journal=Canadian Mathematical Bulletin |volume=11 |issue= 3|year=1968 |pages=409–414 |doi=10.4153/CMB-1968-047-7 | doi-access=free | mr=0232743}}

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(r;k₁, k₂, …, k_r)	Value	Reference
class = "wikitable" \|+ Known van der Waerden numbers
w(2; 3,3)	9	Chvátal {{cite encyclopedia \| last = Chvátal \| first=Vašek \| chapter=Some unknown van der Waerden numbers \| title = Combinatorial Structures and Their Applications. \| pages = 31–33 \| editor1-first=Richard \| editor1-last=Guy \| editor2-first = Haim \| editor2-last = Hanani \| editor3-first = Norbert \| editor3-last = Sauer \| editor4-first = Johanan \| editor4-last = Schönheim\| display-editors = 3 \| location = New York \| publisher = Gordon and Breach \| year = 1970 \| mr = 0266891 }}
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 {{ cite journal \| last1 = Beeler \| first1=Michael D. \| last2 = O'Neil \| first2 = Patrick E. \| title=Some new van der Waerden numbers \| journal = Discrete Mathematics \| volume = 28 \| issue = 2 \| year = 1979 \| pages = 135–146 \| doi=10.1016/0012-365x(79)90090-6 \| mr = 0546646 \| doi-access = free }}
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 {{ cite journal \| last1 = Landman \| first1=Bruce \| last2 = Robertson \| first2 = Aaron \| last3 = Culver \| first3 = Clay \| title=Some New Exact van der Waerden Numbers \| journal = Integers \| volume = 5 \| issue = 2 \| year = 2005 \| pages = A10 \| arxiv=math/0507019 \| bibcode=2005math......7019L \| mr = 2192088 \| url = http://www.emis.de/journals/INTEGERS/papers/a10int2003/a10int2003.pdf }}
w(2; 3,12)	135	Landman, Robertson, and Culver
w(2; 3,13)	160	Landman, Robertson, and Culver
w(2; 3,14)	186	Kouril {{ cite thesis \| last = Kouril \| first=Michal \| title= A Backtracking Framework for Beowulf Clusters with an Extension to Multi-Cluster Computation and Sat Benchmark Problem Implementation \| degree=Ph.D. \| publisher=University of Cincinnati \| year = 2006 \| url = http://rave.ohiolink.edu/etdc/view?acc_num=ucin1163607141 }}
w(2; 3,15)	218	Kouril
w(2; 3,16)	238	Kouril
w(2; 3,17)	279	Ahmed {{ cite journal \| last = Ahmed \| first=Tanbir \| title= Two new van der Waerden numbers w(2;3,17) and w(2;3,18) \| journal = Integers \| volume = 10 \| issue =4 \| year = 2010 \| pages = 369–377 \| doi=10.1515/integ.2010.032 \| mr = 2684128 \| s2cid=124272560 }}
w(2; 3,18)	312	Ahmed
w(2; 3,19)	349	Ahmed, Kullmann, and Snevily {{ cite journal \| last1 = Ahmed \| first1=Tanbir \| last2 = Kullmann \| first2 = Oliver \| last3 = Snevily \| first3 = Hunter \| title= On the van der Waerden numbers w(2;3,t) \| arxiv = 1102.5433 \| journal = Discrete Applied Mathematics \| volume = 174 \| issue = 2014 \| pages = 27–51 \| doi = 10.1016/j.dam.2014.05.007 \| doi-access = free \| mr = 3215454 \| year=2014 }}
w(2; 3,20)	389	Ahmed, Kullmann, and Snevily (conjectured); Kouril {{ cite journal \| last = Kouril \| first=Michal \| title= Leveraging FPGA clusters for SAT computations \| journal = Parallel Computing: On the Road to Exascale \| year = 2015 \| pages = 525–532 }} (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 {{ cite journal \| last = Beeler \| first=Michael D. \| title=A new van der Waerden number \| journal = Discrete Applied Mathematics \| volume = 6 \| issue = 2 \| year = 1983 \| pages = 207 \| doi=10.1016/0166-218x(83)90073-2 \| mr = 0707027 \| doi-access = free }}
w(2; 4,8)	146	Kouril
w(2; 4,9)	309	Ahmed {{ cite journal \| last = Ahmed \| first=Tanbir \| title=On computation of exact van der Waerden numbers \| journal = Integers \| volume = 12 \| year = 2012 \| issue = 3 \| pages = 417–425 \| doi = 10.1515/integ.2011.112 \| mr = 2955523 \| s2cid=11811448 }}
w(2; 5,5)	178	Stevens and Shantaram {{ cite journal \| last1 = Stevens \| first1=Richard S. \| last2 = Shantaram \| first2 = R. \| title= Computer-generated van der Waerden partitions \| journal = Mathematics of Computation \| volume = 32 \| issue =142 \| year = 1978 \| pages = 635–636 \| doi=10.1090/s0025-5718-1978-0491468-x \| mr = 0491468 \| doi-access = free }}
w(2; 5,6)	206	Kouril
w(2; 5,7)	260	Ahmed {{ cite journal \| last = Ahmed \| first = Tanbir \| title= Some More Van der Waerden numbers \| journal = Journal of Integer Sequences \| volume = 16 \| issue = 4 \| year = 2013 \| pages = 13.4.4 \| mr = 3056628 }}
w(2; 6,6)	1132	Kouril and Paul {{ cite journal \| last1 = Kouril \| first1=Michal \| last2 = Paul \| first2 = Jerome L. \| title= The Van der Waerden Number W(2,6) is 1132 \|journal = Experimental Mathematics \| volume = 17 \| issue = 1 \| year = 2008 \| pages = 53–61 \| doi=10.1080/10586458.2008.10129025 \| mr = 2410115 \| s2cid=1696473 \| url=http://projecteuclid.org/euclid.em/1227031896 }}
w(3; 2, 3, 3)	14	Brown {{ cite journal \| last = Brown \| first=T. C. \| authorlink=Tom Brown (mathematician) \| title=Some new van der Waerden numbers (preliminary report) \| journal = Notices of the American Mathematical Society \| volume = 21 \| year = 1974 \| pages = A-432 }}
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 {{ cite journal \| last = Ahmed \| first=Tanbir \| title=Some new van der Waerden numbers and some van der Waerden-type numbers \| journal = Integers \| volume = 9 \| year = 2009 \| pages = A6 \| doi=10.1515/integ.2009.007 \| mr = 2506138 \| s2cid=122129059 }}
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 {{ cite journal \| last = Kouril \| first=Michal \| title= Computing the van der Waerden number W(3,4)=293 \| journal = Integers \| volume = 12 \| year = 2012 \| pages = A46 \| mr = 3083419 }}
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 {{ cite thesis \| last = Schweitzer \| first=Pascal \| title= Problems of Unknown Complexity, Graph isomorphism and Ramsey theoretic numbers \| degree=Ph.D. \| publisher=U. des Saarlandes \| year = 2009 }}
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{{Cite journal \|last=Karki \|first=Sikij \|date=2024 \|title=A New van der Waerden Number \|url=https://utsc.utoronto.ca/ctl/sites/utsc.utoronto.ca.ctl/files/docs/resource-files/U_t__Mathazine_Summer_2024%20%285%29.pdf \|journal=U(t)-Mathazine \|issue=9 \|pages=34–39}}

Van der Waerden numbers are primitive recursive, as proved by Shelah;{{cite journal | first=Saharon | last=Shelah | title=Primitive recursive bounds for van der Waerden numbers | journal=Journal of the American Mathematical Society | volume=1 | year=1988 | pages=683–697 | issue=3 | doi=10.2307/1990952 | mr=929498| jstor=1990952 | doi-access=free }} in fact he proved that they are (at most) on the fifth level $\mathcal{E}^5$ of the Grzegorczyk hierarchy.

References

External links

{{MathWorld|title=Van der Waerden Number|urlname=vanderWaerdenNumber|author=O'Bryant, Kevin|author2=Weisstein, Eric W.|name-list-style=amp}}
{{Cite web|last=Klarreich|first=Erica|author-link=Erica Klarreich|date=2021-12-15|title=Mathematician Hurls Structure and Disorder Into Century-Old Problem|url=https://www.quantamagazine.org/oxford-mathematician-advances-century-old-combinatorics-problem-20211215/|website=Quanta Magazine}}

Category:Ramsey theory

Van der Waerden number

Tables of Van der Waerden numbers

See also

References

Further reading

External links