Problem Statement
Let the van der Waerden number $W(k)$ be such that whenever $N\geq W(k)$ and $\{1,\ldots,N\}$ is $2$-coloured there must exist a monochromatic $k$-term arithmetic progression. Improve the bounds for $W(k)$ - for example, prove that $W(k)^{1/k}\to \infty$.
Categories:
Additive Combinatorics
Progress
When $p$ is prime Berlekamp [Be68] has proved $W(p+1)\geq p2^p$. Gowers [Go01] has proved\[W(k) \leq 2^{2^{2^{2^{2^{k+9}}}}}.\]The best general lower bound is $W(k)\gg 2^k$, due to Kozik and Shabanov [KoSh16].In [Er81] Erdős further asks whether $W(k+1)/W(k)\to \infty$, or $W(k+1)-W(k)\to \infty$.
In [Er80] Erdős asks whether $W(k)/2^k\to \infty$, and offers \$500 for a proof or disproof of $W(k)^{1/k}\to \infty$.
Source: erdosproblems.com/138 | Last verified: January 13, 2026