SOLVED
This has been resolved in some other way than a proof or disproof.
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$.
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]).
View the LaTeX source
This page was last edited 04 April 2026. View history
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #721, https://www.erdosproblems.com/721, accessed 2026-05-22
