---

Claim. The answer to Problem 984 is yes: there is a $2$-coloring of $\mathbb{N}$ such that every monochromatic $k$-term arithmetic progression $\{a,a+d,\ldots,a+(k-1)d\}$ satisfies $k\ll_\epsilon a^\epsilon$ for every $\epsilon>0$. The claimed result is the argument Zach Hunter posted on the problem's discussion thread on 10 August 2025, which gives the stronger bound $k\le\exp((\log a)^{1/2+o(1)})$. The argument, as the post gives it: split $\mathbb{N}$ into the intervals $I_t=[100^t,100^{t+1})$; a progression $P$ of $k>10^4$ terms either (i) places a $3$-term subprogression in an odd-indexed interval and another in an even-indexed one, or (ii) has, for some $t$ with $\min P\ge c\cdot100^t$ for an absolute $c>0$, more than $k/100$ of its terms in $I_t$; color each odd-indexed interval by a coloring with no red $3$-term progression and no blue $k_t$-term progression, and each even-indexed interval by a coloring of the same kind with the roles of red and blue exchanged, where $k_t$ is subpolynomial in $\lvert I_t\rvert$. The colorings of the intervals come from Green's construction for the off-diagonal van der Waerden numbers $w(3,k)$ (Forum Math. Pi 10 (2022), Paper No. e18, doi:10.1017/fmp.2022.12; arXiv:2102.01543) as sharpened in Hunter's own paper (Combinatorica 42 (2022), 1231--1252, doi:10.1007/s00493-022-4925-2; arXiv:2111.01099), both journal records checked, which give $k_t\le\exp((\log\lvert I_t\rvert)^{1/2+o(1)})$. A monochromatic progression of the first kind is impossible, since one of its $3$-term subprogressions has the forbidden color, and one of the second kind has fewer than $100k_t$ terms; since $\lvert I_t\rvert=O(\min I_t)=O(a)$ in case (ii), this gives $k<100k_t\le\exp((\log a)^{1/2+o(1)})$, and in particular $k\ll_\epsilon a^\epsilon$. The post adds that the exponent $1/2$ is a barrier for the present constructions. Spencer had shown the analogous statement with three colors and a very slowly growing bound in place of $a^\epsilon$, and Erdős ([Er80], p. 92) reports a $2$-coloring with $k\ll a^{1-c}$ for an absolute $c>0$ and knows no nontrivial lower bound; the source card erdos_1980_survey_problems_combinatorial_number_theory holds that survey.

Submission note. Posted to the site's forum by Zach Hunter on 10 August 2025:

This has a positive answer, using Ben's nice construction for off-diagonal van der Waerden numbers. Let $I_t$ denote the discrete interval $[100^t,100^{t+1})$.

We first observe that if $P$ is any $k$-AP $P$ (with $k>10000$ say), then either: i) there is an odd $t_1$ and an even $t_2$ so that $P\cap I_{t_1}$ and $P\cap I_{t_2}$ both contain a $3$-AP; ii) there is $t$ so that $\min(P) = \Omega(\min(I_t))$, so that $|P\cap I_t|>k/100$.

Now for $t$ odd, we fix some red-blue coloring of $I_t$ with no red monochromatic $3$-AP, and no blue monochromatic $k_t$-AP, where $k_t$ is subpolynomial in $|I_t| = O(\min(I_t))$ (such colorings exist by: this paper). For $t$ even, we use a red-blue coloring of $I_t$ with no blue monochroamtic $3$-AP, and no red monochromatic $k_t$-AP.

Now consider any arithmetic progression $P$ which is allegedly monochromatic under this coloring $C$. If $|P|< 10000=O(1)$, there is nothing to worry about. Otherwise, by our dichotomy we have that either (i) or (ii) holds. If (i) holds, $P$ cannot be monochromatic by design (we have that $I_{t_1} \cap P$ cannot be fully red (as it contains a $3$-AP), while $I_{t_2}\cap P$ cannot be fully blue). And if (ii) holds, then we can find $t$ so that $|P| <100|I_t\cap P|<100k_t$, and with $k_t = |I_t|^{o(1)} = O(\min(P))^{o(1)}$.

QED!

The best upper bound I know for $k_t$ is $\exp(\log^{1/2+o(1)}|I_t|)$ (from my own work), which one might expect to be close to tight when the other color avoids $3$-APs. If we instead forbid $2^{s-1}+1$-APs in the other color, one might expect to get a better off-diagonal bound of $\exp(\log^{1/s+o(1)}|I_t|)$. However it is open to push past the $1/2$-barrier (which I think is a lovely problem that maybe is not as well-known as it should be).

(The site has been updated to address this comment.)

Postings. The thread post of 10 August 2025 is the only write-up by Hunter. Boris Alexeev's lean-proofs repository holds a Lean 4 file src/latest/ErdosProblems/Erdos984.lean, added 2026-08-18 and linked above at the revision of 2026-08-24 that last changed it, whose header declares it a formalization of a solution to Problem 984 with Zach Hunter as informal author and the systems Codex and GPT-5.6 Sol as formal authors. Its theorem erdos_984 states that there is a coloring $\mathbb{N}\to\mathrm{Bool}$ such that for every $\epsilon>0$ some $A>0$ has $k\le A\,a^\epsilon$ for every monochromatic $k$-term progression with $a\ge1$ and $d\ge1$; the construction is assembled from a HunterFamily module of off-diagonal colorings, and the file closes by printing the theorem's axioms. It is not on the lists of Lean the corpus has built and audited, so it gives no formalized evidence and is a formalization link on this page rather than a claim of its own. No formal-conjectures statement exists, and the site's formalization indicator reads No.

Depends on. Nothing in this wiki: the inputs are the two published van der Waerden constructions cited above, neither of which is carded.

Acceptance. Reviewed: the site's curator, Thomas Bloom, replied on the thread on 10 August 2025 asking about the heuristic behind the expected exponent and calling the $1/2$ barrier an open problem, and the problem page labels the problem proved and credits Hunter's proof in its commentary (page last edited 4 April 2026, read 2026-10-07; the proof-claims tab was empty). Not refereed: the proof exists only as the thread post, with no preprint or journal publication found on 2026-10-07; the two papers it draws on are refereed, but they do not state this result. Read status: the argument's steps were checked on the thread; no independent verification is recorded.