Editing Van der Waerden's theorem (section)

==Open problem==
It is an open problem to determine the values of ''W''(''r'', ''k'') for most values of ''r'' and ''k''. The proof of the theorem provides only an upper bound.  For the case of ''r'' = 2 and ''k'' = 3, for example, the argument given below shows that it is sufficient to color the integers {1, ..., 325} with two colors to guarantee there will be a single-colored arithmetic progression of length 3. But in fact, the bound of 325 is very loose; the minimum required number of integers is only 9.  Any coloring of the integers {1, ..., 9} will have three evenly spaced integers of one color.

For ''r'' = 3 and ''k'' = 3, the bound given by the theorem is 7(2·3<sup>7</sup>&nbsp;+&nbsp;1)(2·3<sup>7·(2·3<sup>7</sup>&nbsp;+&nbsp;1)</sup>&nbsp;+&nbsp;1), or approximately 4.22·10<sup>14616</sup>. But actually, you don't need that many integers to guarantee a single-colored progression of length 3; you only need 27. (And it is possible to color {1, ..., 26} with three colors so that there is no single-colored arithmetic progression of length 3; for example:
{|class="wikitable"
|&nbsp;1&nbsp;
|&nbsp;2&nbsp;
|&nbsp;3&nbsp;
|&nbsp;4&nbsp;
|&nbsp;5&nbsp;
|&nbsp;6&nbsp;
|&nbsp;7&nbsp;
|&nbsp;8&nbsp;
|&nbsp;9&nbsp;
|&nbsp;10&nbsp;
|&nbsp;11&nbsp;
|&nbsp;12&nbsp;
|&nbsp;13&nbsp;
|&nbsp;14&nbsp;
|&nbsp;15&nbsp;
|&nbsp;16&nbsp;
|&nbsp;17&nbsp;
|&nbsp;18&nbsp;
|&nbsp;19&nbsp;
|&nbsp;20&nbsp;
|&nbsp;21&nbsp;
|&nbsp;22&nbsp;
|&nbsp;23&nbsp;
|&nbsp;24&nbsp;
|&nbsp;25&nbsp;
|&nbsp;26&nbsp;
|-
|&nbsp;'''<span style="color:red;">R</span>'''&nbsp;
|&nbsp;'''<span style="color:red;">R</span>'''&nbsp;
|&nbsp;'''<span style="color:limegreen;">G</span>'''&nbsp;
|&nbsp;'''<span style="color:limegreen;">G</span>'''&nbsp;
|&nbsp;'''<span style="color:red;">R</span>'''&nbsp;
|&nbsp;'''<span style="color:red;">R</span>'''&nbsp;
|&nbsp;'''<span style="color:limegreen;">G</span>'''&nbsp;
|&nbsp;'''<span style="color:blue;">B</span>'''&nbsp;
|&nbsp;'''<span style="color:limegreen;">G</span>'''&nbsp;
|&nbsp;'''<span style="color:blue;">B</span>'''&nbsp;
|&nbsp;'''<span style="color:blue;">B</span>'''&nbsp;
|&nbsp;'''<span style="color:red;">R</span>'''&nbsp;
|&nbsp;'''<span style="color:blue;">B</span>'''&nbsp;
|&nbsp;'''<span style="color:red;">R</span>'''&nbsp;
|&nbsp;'''<span style="color:red;">R</span>'''&nbsp;
|&nbsp;'''<span style="color:limegreen;">G</span>'''&nbsp;
|&nbsp;'''<span style="color:red;">R</span>'''&nbsp;
|&nbsp;'''<span style="color:limegreen;">G</span>'''&nbsp;
|&nbsp;'''<span style="color:limegreen;">G</span>'''&nbsp;
|&nbsp;'''<span style="color:blue;">B</span>'''&nbsp;
|&nbsp;'''<span style="color:red;">R</span>'''&nbsp;
|&nbsp;'''<span style="color:blue;">B</span>'''&nbsp;
|&nbsp;'''<span style="color:blue;">B</span>'''&nbsp;
|&nbsp;'''<span style="color:limegreen;">G</span>'''&nbsp;
|&nbsp;'''<span style="color:blue;">B</span>'''&nbsp;
|&nbsp;'''<span style="color:limegreen;">G</span>'''&nbsp;
|}

An open problem is the attempt to reduce the general upper bound to any 'reasonable' function. [[Ronald Graham]] offered a prize of [[US$]]1000 for showing ''W''(2, ''k'') &lt; 2<sup>''k''<sup>2</sup></sup>.<ref>{{cite journal |author-link=Ronald Graham |first=Ron |last=Graham |title=Some of My Favorite Problems in Ramsey Theory |journal=INTEGERS: The Electronic Journal of Combinatorial Number Theory |url=http://www.integers-ejcnt.org/vol7-2.html |volume=7 |issue=2 |year=2007 |pages=#A15 }}</ref> In addition, he offered a [[US$]]250 prize for a proof of his conjecture involving more general ''off-diagonal'' [[van der Waerden number|van der Waerden numbers]], stating ''W''(2; 3, ''k'') ≤ ''k''<sup>''O(1)''</sup>, while mentioning numerical evidence suggests ''W''(2; 3, ''k'') = ''k''<sup>2 + ''o(1)''</sup>. [[Ben_Green_(mathematician)|Ben Green]] disproved this latter conjecture and proved super-polynomial counterexamples to ''W''(2; 3, ''k'') &lt; ''k''<sup>r</sup> for any ''r''.<ref>{{cite web |last1=Klarreich |first1=Erica |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 |year=2021}}</ref> The best upper bound currently known is due to [[Timothy Gowers]],<ref>{{cite journal |author-link=Timothy Gowers |first=Timothy |last=Gowers |title=A new proof of Szemerédi's theorem |journal=Geometric and Functional Analysis |volume=11 |issue=3 |pages=465–588 |year=2001 |url=http://www.dpmms.cam.ac.uk/~wtg10/papers.html |doi=10.1007/s00039-001-0332-9 | doi-access=|s2cid=124324198 }}</ref> who establishes

: <math>W(r,k) \leq 2^{2^{r^{2^{2^{k + 9}}}}},</math>

by first establishing a similar result for [[Szemerédi's theorem]], which is a stronger version of Van der Waerden's theorem.  The previously best-known bound was due to [[Saharon Shelah]] and proceeded via first proving a result for the [[Hales&ndash;Jewett theorem]], which is another strengthening of Van der Waerden's theorem.

The best lower bound currently known for <math>W(2, k)</math> is that for all positive <math>\varepsilon</math> we have <math>W(2, k) > 2^k/k^\varepsilon</math>, for all sufficiently large <math>k</math>.<ref>{{cite journal |author-link=Zoltán Szabó (mathematician)|first=Zoltán |last=Szabó |title=An application of Lovász' local lemma-a new lower bound for the van der Waerden number |journal=Random Structures & Algorithms |volume=1 | issue = 3 |pages=343–360 |year=1990 |doi=10.1002/rsa.3240010307 }}</ref>