Fox–Hunter (2026) — three-color van der Waerden numbers $w(k;3)$ grow super-exponentially in $k$

Statement

For positive integers $k$ and $r$, the multicolor van der Waerden number $w(k;r)$ is the least $N$ such that every $r$-coloring of $\{1,\ldots,N\}$ contains a monochromatic $k$-term arithmetic progression (van der Waerden's theorem, 1927, guarantees such an $N$ exists for every $k,r$). Erdős offered \$500 to prove or disprove that the two-color diagonal case grows super-exponentially: $$\limsup_{k\to\infty} w(k;2)^{1/k} = \infty \quad\text{?}$$ (this exact two-color question is Erdős #138 — does W(k)^{1/k} → ∞ for van der Waerden numbers?, and remains open). The natural three-color analogue — does $w(k;3)$ grow faster than any exponential function of $k$? — is the question this page answers.

A closely related second question, posed by Erdős and Graham: the canonical van der Waerden number $H(k)$ is the least $N$ such that every (arbitrary, unboundedly-many-color) coloring of $\{1,\ldots,N\}$ contains either a monochromatic or a "rainbow" (all-distinct-colors) $k$-term arithmetic progression. Erdős and Graham asked whether $H(k)^{1/k}/k\to\infty$.

Facts

- Source: Jacob Fox, Zach Hunter, "Three-color van der Waerden numbers grow super-exponentially," arXiv:2606.02541 (submitted 1 June 2026). - Main theorem (Theorem 1): for $k$ sufficiently large, $$w(k;3) > 2^{k(\log^* k)/4},$$ where $\log^* k$ is the (very slowly growing) iterated logarithm. Since this beats $2^{ck}$ for every constant $c$ once $k$ is large enough ($\log^* k\to\infty$, however slowly), this proves $w(k;3)$ grows faster than any exponential in $k$ — i.e. it answers, for three colors, the exact shape of question Erdős asked (and offered money for) about the two-color case in Erdős #138 — does W(k)^{1/k} → ∞ for van der Waerden numbers?. - Prior best known lower bound: Hunter (arXiv:2301.06212 / *Israel J. Math.* 2025) had $w(k;r) \geq (3^{r/3})^{(1-o(1))k}$ for $r\geq6$ a multiple of 3 — a genuinely *exponential*-in-$k$ bound (with base growing in $r$), the first exponential improvement over the plain Lovász-local-lemma bound for $r\geq5$, but still only exponential, not super-exponential, and only for $r\geq5$ or $6$ colors, not $r=3$. - This is the first proof, at any fixed color count $r\geq2$, that a multicolor van der Waerden number grows faster than exponentially. The two-color case ($r=2$, Erdős #138 — does W(k)^{1/k} → ∞ for van der Waerden numbers?'s \$500 question) remains open; the authors' own construction is explicitly three-color — the third color is the resource the recursive construction consumes at each step (see Solution below), and it is exactly the ingredient a 2-color proof would need to find a substitute for. - Second main result (Theorem 3), resolving the Erdős–Graham canonical-vdW problem: $H(k) \geq k^{(1-o(1))k\log k}$, a bound of shape $k^{k\log k}$ — since this is $\gg (ck)^k$ for any constant $c$, it gives $H(k)^{1/k}/k\to\infty$, resolving the Erdős–Graham question in the affirmative. (Independently and essentially simultaneously, Bae, arXiv:2604.20588 (2026), proved the related but slightly weaker $H(k)\geq k^{(2-o(1))k}$ via a different route — the Erdős–Lovász LLL bound $W(r,k)\gg r^{k-1}/k$ applied with the number of colors $r_0=\lfloor k/\log k\rfloor$ *growing with* $k$, combined with a Blankenship–Cummings–Taranchuk recurrence and the Baker–Harman–Pintz prime-gap theorem; per this wiki's Erdős #138 — does W(k)^{1/k} → ∞ for van der Waerden numbers? page, §6 of Fox–Hunter gets the stronger bound independently.) - Not yet in a peer-reviewed venue as of this search (2026-07-02) — a roughly one-month-old arXiv preprint; flagged as an open provenance gap. - Formal statement/paper structure: 19 pages, §1 Introduction (with canonical-vdW and "further applications" subsections), §2 Very dense sets without long arithmetic progressions, §3 Lower bounds on van der Waerden numbers, §4 Concluding remarks.

Solution

Answer: yes — $w(k;3)$ grows super-exponentially, via an explicit recursively-built 3-coloring of $\{1,\ldots,2^{k(\log^*k)/4}\}$ with no monochromatic $k$-AP.

**The transferable technique — trade one color as "recursion fuel": use a sparse Behrend-type hitting set plus a Lovász-local-lemma coloring to color a *small* group well, then iteratively square the group size via a randomly-shifted product construction, feeding the previous round's coloring back in as raw material, for as many rounds as the (extremely slowly growing) function $\log^* k$ allows.**

1. Build a sparse "hitting set" gadget inside a cyclic group (Lemma 2.8). For a small $\varepsilon>0$, construct $S\subseteq\mathbb Z_N$ of density at most $\varepsilon$ that nonetheless contains at least a $\delta$-fraction of *every* $k$-term arithmetic progression in $\mathbb Z_N$ — a Behrend/Sidon-flavored sparse-yet-AP-robust set. This is the raw combinatorial gadget: a set small enough to be "spent" as one of three colors, but dense enough along every long AP that no $k$-AP can dodge it. 2. Turn the gadget into a genuine 3-coloring via the Lovász Local Lemma (Corollary 3.3). Assign color-subsets to elements of an abelian group $G$ so that for every $k$-AP and every color $i$, at most a $(1-\delta)$-fraction of the AP's elements carry color $i$ — i.e. no single color can ever dominate ($=$ monochromatically fill) a long progression. This step converts the existence of a sparse hitting structure into a genuine local (per-AP, per-color) anti-domination guarantee, using the LLL to handle the dependency structure between overlapping APs. 3. Amplify by a "random shifted product" construction (Lemmas 4.2–4.3): color the fibers of a projection independently. Given a good coloring of a smaller group, build a coloring of a *much larger* group (roughly its square, or an exponential jump) by treating the larger group as fibered over the smaller one, and independently — via a random shift — recoloring each fiber using (a shifted copy of) the smaller coloring. This keeps the total number of colors fixed at 3 while the ambient group/interval size grows multiplicatively (indeed, doubly-exponentially per step), at the cost of a controlled degradation in the "no-monochromatic-$k$-AP" density parameter. 4. **Iterate roughly $(\log^*k)/2$ times, and stop exactly when the degrading parameters would otherwise collapse.** Each round of step 3 squares (or exponentiates) the achievable interval length while eating into the density slack purchased in steps 1–2. The number of times this can be repeated before the accumulated parameter loss destroys the "no mono $k$-AP" guarantee is governed by $\log^*k$ — the very slowly growing "how many times must you take $\log$ before reaching a constant" function. Because $\log^*k\to\infty$ (however slowly), running the iteration for $\Theta(\log^*k)$ rounds, each contributing roughly a doubling in the exponent, ultimately produces an interval of length $2^{k(\log^*k)/4}$ — beating $2^{ck}$ for every fixed $c$, i.e. super-exponential, even though *each individual iteration step* only ever achieves a bounded, exponential-type gain. 5. The canonical-vdW bound (Theorem 3, resolving Erdős–Graham) reuses the same LLL/hitting-set machinery but lets the number of colors itself grow with $k$, in the spirit of Bae's independent proof — this is the structural move that is available for the *canonical* (unboundedly-many-colors) problem and for the $r\geq3$-color diagonal problem, but is explicitly not available for the fixed-$r=2$ question Erdős #138 — does W(k)^{1/k} → ∞ for van der Waerden numbers? still open at \$500 (per this wiki's Erdős #138 — does W(k)^{1/k} → ∞ for van der Waerden numbers? page: "the key trick — grow the number of colours with $k$ — is exactly what is unavailable for #138, which is fixed at $r=2$ colours").

Why this is the reusable part. The general architecture — (i) a sparse Behrend/hitting-set gadget that is dense along every long AP despite being globally sparse; (ii) an LLL step converting that gadget into a genuine local no-domination coloring; (iii) a *self-similar amplification step* (random shifted product / fiber-independent recoloring) that holds the color budget fixed while blowing up the domain size multiplicatively; (iv) iterating the amplification step for as many rounds as a slowly-growing control function ($\log^*k$) permits before parameter-degradation catches up — is a general recipe for turning "one good bounded-size construction" into "a construction on a domain of towering size," at the structural cost of consuming one extra color as recursion fuel. This is exactly the kind of technique the still-open two-color case Erdős #138 — does W(k)^{1/k} → ∞ for van der Waerden numbers? would need either to replicate without a third color to spend, or to find a genuinely different substitute for; per Erdős #138 — does W(k)^{1/k} → ∞ for van der Waerden numbers?'s own attack-surface notes, checking "whether Fox–Hunter's technique has *any* 2-colour residue" is flagged as the single most promising concrete next experiment on that \$500 question.

Related

- Erdős #138 — does W(k)^{1/k} → ∞ for van der Waerden numbers? — the fixed-\$500, still-open two-color ($r=2$) diagonal question $w(k;2)^{1/k}\to\infty$, whose exact three-color analogue this page's Theorem 1 resolves; #138's own page documents in detail why this technique does not (yet) transfer down to $r=2$, and flags reading this paper's full construction for a possible "2-colour residue" as the most promising open attack surface. - Log*-depth iterated/recursive lower-bound constructions (self-similar amplification budgeted by the inverse tower function) *(forward link — not yet written)* — the $\Theta(\log^*k)$-round self-similar amplification recipe (sparse hitting set → LLL local coloring → random-shifted-product fiber recoloring, iterated) this page documents as the transferable technique; also cited from Erdős #138 — does W(k)^{1/k} → ∞ for van der Waerden numbers? as the newest, most powerful machinery in this problem family. - Lovász Local Lemma (symmetric, general/asymmetric, and algorithmic/random-recoloring variants) — probabilistic existence when bad events are individually non-negligible but sparsely dependent *(forward link — not yet written)* — the probabilistic tool (Corollary 3.3 here) converting a sparse global hitting-set gadget into a genuine local no-monochromatic-domination coloring; also the tool behind the older Szabó (1990) and Kozik–Shabanov (2016, arXiv:1409.6921) $\Omega(2^k)$ lower bounds for the still-open two-color case. - Random quadratic form pseudorandom coloring constructions (Green–Hunter annulus method) *(forward link — not yet written)* — Ben Green's (arXiv:2102.01543) and Hunter's (arXiv:2111.01099) sibling pseudorandom-construction technique family for the *off-diagonal* $w(3,k)$ problem; a structurally different "arm" of AP-avoiding lower-bound constructions in the same broader literature, not the one used here. - Erdős–Graham canonical van der Waerden problem — resolved as this page's Theorem 3, $H(k)\geq k^{(1-o(1))k\log k}$; see also the independent near-simultaneous proof by Bae, arXiv:2604.20588 (2026), $H(k)\geq k^{(2-o(1))k}$, via letting the color count grow with $k$ in the Erdős–Lovász LLL bound. - Hunter, "Lower bounds for multicolor van der Waerden numbers," arXiv:2301.06212 / *Israel J. Math.* (2025) — the immediate predecessor result this paper beats: $w(k;r)\geq(3^{r/3})^{(1-o(1))k}$ for $r\geq6$ a multiple of 3, the previous best (merely exponential) multicolor bound.