← All problems

Erdős Problem #138 — Bounds for van der Waerden numbers

45 years old · traced to

Let the van der Waerden number W(k)W(k) be such that whenever N≥W(k)N\geq W(k) and {1,…,N}\{1,\ldots,N\} is 22-coloured there must exist a monochromatic kk-term arithmetic progression. Improve the bounds for W(k)W(k) - for example, prove that W(k)1/k→∞W(k)^{1/k}\to \infty.

References

Progress summary

Refreshed
Open · solution reported

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 W(k+1)≥W(k)+kW(k+1)\geq W(k)+k.

Known results

  • Berlekamp proved W(p+1)≥p2pW(p+1)\geq p2^p for prime pp.
  • Gowers proved W(k)≤22222k+9W(k)\leq 2^{2^{2^{2^{2^{k+9}}}}}.
  • Kozik and Shabanov obtained the best general lower bound W(k)≫2kW(k)\gg 2^k.

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.

Sources

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 solutionHide full solution