Section 18.2 Historical Background and Importance
van der Waerden published his theorem in 1927 where he proves his result using double induction. However, this use of double induction also results in an enormous upper bound of \(W(2;k,k) \leq \text{ACKERMANN}(k)\) where \(k \geq 10\) for these van der Waerden numbers. [18.6.3]
It would take over 60 years for this upper bound to be lowered when in 1988 Israeli mathematician Saharon Shelah proved the Hales–Jewett theorem, which implies van der Waerden's theorem, without double induction. [18.6.5] Using this, Shelah established that \(W(2;k,k)\) was bounded from above by a WOW function.
The next lowering of the upper bound would come over a decade later in a 2001 paper where British mathematician Timothy Growers showed that
and confirmed Ron Graham's 1990 conjecture that
as well. [18.6.3]
As of writing this paper, Grower's bound is currently the lowest known. Perhaps the next breakthrough in lowering the upper bound could be achieved through proving another of Graham's conjectures. A prize of \(\$1000\) has been offered by Graham to anyone that can prove
If any reader has a proof, please contact Dr. Steve Butler, a professor of mathematics at Iowa State University, to claim your prize.
Like Ramsey numbers or Hales–Jewett numbers, determining exact values or even bounds for van der Waerden numbers is notoriously challenging. Currently, the largest known van der Waerden number, computed in 2008, is \(W(2;6,6) = 1132\text{.}\) [18.6.4]
Calculating these numbers generally requires an immense amount of compute resources parallelized over many compute clusters and the time to compute each new number grows exponentially. As such, over 16 years later the exact value of \(W(2;7,7)\) is still yet to be determined.