Erdős Problem #138 — Bounds for van der Waerden numbers
Let the van der Waerden number be such that whenever and is -coloured there must exist a monochromatic -term arithmetic progression. Improve the bounds for - for example, prove that .
References
UnsolvedMath, Erdős Problems set, ULAM AI, licensed CC BY 4.0.
Progress summary
A formal proof has been reported that the gaps eventually grow without bound, but no independently published proof was found.
Erdős asked whether consecutive van der Waerden numbers have gaps tending to infinity. The problem is now reported affirmatively via the stronger bound .
Known results
- Berlekamp proved for prime .
- Gowers proved .
- Kozik and Shabanov obtained the best general lower bound .
DeepMind formal proof — date not stated
Current status (as of March 2026): the two-colour gap assertion is formally claimed proved, but it is not yet independently corroborated in a peer-reviewed or arXiv source.
Solutions 1
Claimed by OpenAI. The manuscript claims W_r(k)>k^(ckfloor(log2 r)) for an absolute c>0, every r>=2 and all sufficiently large k. For two colors this implies W(k)^(1/k)>k^c and hence divergence to infinity, addressing the page’s requested superexponential lower bound. This is a lower-bound claim rather than an exact asymptotic formula or an off-diagonal van der Waerden result.See full solution
GitHub repository: https://github.com/openai/math
- OpenAI-160-01-Quantitative-Superexponential-Bounds-for-van-der-Waerden-Numbers.pdfOpen