Problem Statement
Let $W(3,k)$ be the van der Waerden number defined as the minimum $n$ such that in any red/blue colouring of $\{1,\ldots,n\}$ there exists either a red $3$-term arithmetic progression or a blue $k$-term arithmetic progression.
Give reasonable bounds for $W(3,k)$. In particular, give any non-trivial lower bounds for $W(3,k)$ and prove that $W(3,k) < \exp(k^c)$ for some constant $c<1$.
Give reasonable bounds for $W(3,k)$. In particular, give any non-trivial lower bounds for $W(3,k)$ and prove that $W(3,k) < \exp(k^c)$ for some constant $c<1$.
Categories:
Number Theory Additive Combinatorics Ramsey Theory
Progress
While we do not have a full understanding of the growth of $W(3,k)$, both of the specific challenges of Erdős have been met.Green [Gr22] established the superpolynomial lower bound\[W(3,k) \geq \exp\left( c\frac{(\log k)^{4/3}}{(\log\log k)
^{1/3}}\right)\]for some constant $c>0$ (in particular disproving a conjecture of Graham that $W(3,k)\ll k^2$). Hunter [Hu22] improved this to\[W(3,k) \geq \exp\left( c\frac{(\log k)^{2}}{\log\log k}\right).\]The first to show that $W(3,k) < \exp(k^c)$ for some $c<1$ was Schoen [Sc21]. The best upper bound currently known is\[W(3,k) \ll \exp\left( O((\log k)^9)\right),\]which follows from the best bounds known for sets without three-term arithmetic progressions (see [BlSi23] which improves slightly on the bounds due to Kelley and Meka [KeMe23]).
Source: erdosproblems.com/721 | Last verified: January 16, 2026