---

Claim. There is an absolute constant $c>0$ such that

$$W(3,k)\ge k^{c(\log k/\log\log k)^{1/3}} =\exp\Bigl(c\frac{(\log k)^{4/3}}{(\log\log k)^{1/3}}\Bigr),$$

where $W(3,k)$ is the least $n$ such that every red/blue coloring of $\{1,\ldots,n\}$ has a red three-term or a blue $k$-term arithmetic progression (Green states it with the colors exchanged, a blue three-term or a red $k$-term progression; the colors are names). Equivalently, for large $N$ some two-coloring of $\{1,\ldots,N\}$ keeps every blue progression below three terms and every red progression shorter than $e^{C(\log N)^{3/4}(\log\log N)^{1/4}}$. The bound is superpolynomial in $k$, the first such bound, and it refutes the conjecture $W(3,k)=O(k^2)$, which Green (p. 2) attributes to Ahmed, Kullmann and Snevily, noting that Li and Shu posed proving or disproving $W(3,k)\ge ck^2$ as an open problem and that Green had also suggested a quadratic bound as plausible; Green writes of first hearing the question whether $W(3,k)=O(k^2)$ from Graham around 2004, and the site's commentary calls the refuted statement Graham's conjecture. The previous lower bounds were of order $k^{2-1/\log\log k}$ (Brown, Landman and Robertson) and $(k/\log k)^2$ (Li and Shu). The theorem is paged at Theorem 1.1 of the library's source card, whose locators are the published article's.

Covers. The lower-bound challenge of Problem 721, a non-trivial lower bound for $W(3,k)$, which the Formulation reads, as the site does, as a superpolynomial one. Hunter's improvement to $k^{c\log k/\log\log k}$ has its own claim page, and the upper-bound challenge is met by Schoen on Schoen's claim page. The open-ended request for reasonable bounds is not covered: Green expects the truth to lie between the paper's bound and about $k^{c\log k}$, and the order of magnitude is open.

Depends on. Nothing in this wiki; the result is the paper's own theorem.

Acceptance. Reviewed: the site's curator, T. F. Bloom, labels the problem SOLVED and credits the superpolynomial lower bound to this paper in the problem's commentary (page last edited 4 April 2026, accessed 2026-09-18). Refereed: Forum of Mathematics, Pi 10 (2022), e18, 1--51, received 23 February 2021 and accepted 8 March 2022 (the article's first page); the published version records Hunter's improvement in a June 2022 update note. The arXiv preprint 2102.01543v1 of 2 February 2021 is the first posting and names this page.

Read depth. Claims checked: the basis is Theorem 1.1 (p. 2) and its equivalent Theorem 2.1 (p. 5), with the identity between the two forms of the bound checked on the problem page; the proof is not covered, and nothing is independently reviewed in this corpus.