Off-diagonal van der Waerden numbers — W(3,k) grows superpolynomially, disproving Graham's O(k²) conjecture

Statement

For a positive integer $k$, the off-diagonal (two-color) van der Waerden number $W(3,k)$ is the least $n$ such that every red/blue coloring of $\{1,\dots,n\}$ contains either a red 3-term arithmetic progression or a blue $k$-term arithmetic progression. (Van der Waerden's theorem guarantees $W(3,k)$ is finite; the question is its growth rate in $k$.)

Erdős asked (Er80, p.91; Er81 — this is erdosproblems.com #721) for reasonable bounds on $W(3,k)$: in particular (a) any non-trivial *lower* bound, and (b) a proof that $W(3,k) < \exp(k^c)$ for some constant $c<1$ (i.e. a genuinely *subexponential* upper bound, ruling out the tower-type bounds that generic van der Waerden arguments give). Separately, Ron Graham had conjectured, on the strength of small computed values ($W(3,10)=97$, $W(3,20)\ge 389$, etc., which look roughly quadratic in $k$), that

$$W(3,k) = O(k^2).$$

Both parts of Erdős's #721 have now been met, and Graham's $O(k^2)$ conjecture is disproved: $W(3,k)$ grows *superpolynomially* in $k$ — faster than $k^C$ for every fixed $C$ — while still being subexponential ($< \exp(k^c)$ for some $c<1$).

Facts

- Trivial/earlier lower bounds were $\Theta(k^2)$-flavored and matched the shape of Graham's conjecture, which is why the conjecture looked plausible from data; Green himself had at one point considered a quadratic bound plausible (per Hunter's arXiv:2209.07651 remark that this quadratic-order bound is "still of interest" as a clean, short, self-contained construction even after superpolynomial bounds were known). - Green's breakthrough (2021, published Forum of Math. Pi), arXiv:2102.01543: constructs a red/blue coloring of $[N]$ with no blue 3-AP and no red AP of length $e^{C(\log N)^{3/4}(\log\log N)^{1/4}}$, giving $$W(3,k) \ge \exp\!\left(c\,\frac{(\log k)^{4/3}}{(\log\log k)^{1/3}}\right) = k^{\,c(\log k/\log\log k)^{1/3}}.$$ This is superpolynomial (grows faster than any fixed power of $k$) and directly disproves Graham's $O(k^2)$ conjecture — confirmed as the disproof in erdosproblems.com #721's official summary. - Hunter's improvement (2021–22), arXiv:2111.01099 (Combinatorica): pushes the exponent up to $$W(3,k) \ge \exp\!\left(c\,\frac{(\log k)^{2}}{\log\log k}\right) = k^{\,c\log k/\log\log k},$$ a genuinely larger superpolynomial bound, obtained by simplifying Green's construction (see Solution below). - Hunter's short paper (Oct 2022), arXiv:2209.07651, separately gives a clean, self-contained proof of the weaker but very simple bound $W(3,k)\ge(1-o(1))k^2$ — valuable for its brevity/elementariness, not for beating the superpolynomial bounds above. - Upper-bound side: Schoen (2021, *Electron. J. Combin.* 28(2), #P2.34, arXiv:2006.02877) was first to prove $W(3,k) < \exp(k^c)$ for some $c<1$ (subexponential), settling the second half of Erdős's #721, via a sumset/Freiman-type argument building on Green's approach to Roth-type sets. The best upper bound currently known is $$W(3,k) \ll \exp\!\big(O((\log k)^9)\big),$$ which follows as a corollary of the best known bounds for 3-AP-free sets — Kelley–Meka's quasipolynomial Roth bound (2023) as sharpened by Bloom & Sisask, arXiv:2309.02353 (giving 3-AP-free density $\le \exp(-c(\log N)^{1/9})\,N$). - The gap remains wide and open: lower $\exp(c(\log k)^2/\log\log k)$ vs. upper $\exp(O((\log k)^9))$ — pinning down the true order of growth of $W(3,k)$ is *not* resolved; only Erdős's two specific, weaker asks (non-trivial lower bound; subexponential upper bound) are met. erdosproblems.com marks #721 "SOLVED" in the site's technical sense ("resolved in some other way than a proof or disproof [of the exact stated targets]"), not as a closed-form asymptotic determination. - Direct descendant: Fox & Hunter, "Three-color van der Waerden numbers grow super-exponentially" (2026, arXiv:2606.02541) prove the *three-color diagonal* van der Waerden number $w(k;3)$ grows faster than any exponential — a structurally related but distinct multicolor result from the same authorship lineage, resolving a separate Erdős–Graham question on canonical/multicolor van der Waerden numbers.

Solution

Answer: $W(3,k)$ is superpolynomial, not $O(k^2)$. Best bounds known: $\exp(c(\log k)^2/\log\log k) \le W(3,k) \le \exp(O((\log k)^9))$ (Green 2021 / Hunter 2021–22 for the lower bound; Schoen 2021, Kelley–Meka 2023, Bloom–Sisask 2023 for the upper bound).

**The transferable technique — replace a 1-D probabilistic coloring with a *high-dimensional structured-random* coloring, pulled back through a norm/quadratic form, so that "avoiding long monochromatic APs" becomes a geometric non-degeneracy statement instead of a union-bound-over-all-APs statement:**

1. Why naive random colorings fail. A uniformly random 2-coloring of $[N]$ almost surely contains long monochromatic APs once $N$ is more than polynomial in $k$ — the union bound over the $\sim N^2$ candidate $k$-APs is far too weak to beat quadratic $N$. Beating $O(k^2)$ requires *structure*, not raw randomness.

2. Lift to a torus and color by distance to a random ellipsoidal annulus (Green, arXiv:2102.01543). Map $[N]$ into a high-dimensional torus $\mathbb{T}^D$ via a Weyl-type / polynomial embedding, and color a point blue iff its image lands inside a thin random annulus $\{x : \|(I+E)x\|_2 \in [\rho-\varepsilon,\rho]\}$, where $E$ is a random $D\times D$ perturbation matrix (giving $D(D+1)/2$ random degrees of freedom) and $D\approx C\,r^2$ is tuned to the target progression length $N^{1/r}$. The point of the *ellipsoidal* (as opposed to spherical) annulus is that it breaks the extra symmetry a round sphere would have, which is exactly the symmetry that would let an adversary hide a long progression. 3. Force every long progression to intersect the annulus, via arithmetic geometry, not counting. The hard step is showing that for *every* candidate common difference (there are $\sim N^{1-1/r}$ of them to defeat, simultaneously, with one random object), the values of the associated quadratic form $q_E$ along the progression must land in the tiny target interval with high enough probability that a union bound over all differences still succeeds. Green does this with the Hardy–Littlewood circle method plus an amplification argument over projective lines in $\mathbb{F}_p$ — i.e. he imports finite-field/arithmetic-geometry tools to control a family of random quadratic forms uniformly, rather than treating each progression's probability of avoidance independently. 4. Simplify: trade one hard random object for many easy ones (Hunter, arXiv:2111.01099). Hunter's key insight is that the entire heavy machinery of step 3 — "prove one random quadratic form behaves well against every progression at once" — can be replaced by using many independent random annuli (fixed eccentricity, independently random *radius* each) instead of one annulus with fixed radius and random eccentricity. With many independent centers, a long AP is virtually guaranteed to pass near *some* center purely by a union bound over the independent trials — an elementary probabilistic argument — rather than needing a single object to be simultaneously well-behaved against every progression via deep quadratic-form estimates. This is a "multiplicity over depth" trade: instead of engineering one maximally-robust random structure, throw many independently-weak random structures at the problem and let elementary probability (not arithmetic geometry) do the union-bound work. It shortens the proof by roughly a third and *improves* the bound. 5. Portable takeaway for open problems in this cluster. (i) When a 1-D combinatorial-number-theory lower bound looks capped at a "natural" polynomial rate matching small computational data, suspect that the true obstruction is a low-dimensional artifact — try lifting to a torus/lattice of dimension tied to the target scale, and color by proximity to a random algebraic hypersurface (sphere/ellipsoid/quadric) rather than coloring points directly. (ii) When the resulting construction needs one random object to defeat *every* adversarial choice simultaneously (here: every common difference), first try the cheap fix of using many independent copies of a simpler random object instead of one highly-engineered object — this is frequently a strict simplification *and* strengthening, as it was here (Hunter over Green). (iii) The genealogy Green (single ellipsoidal annulus, quadratic-form circle-method control) → Hunter (many independent circular annuli, elementary probability) is itself the template other off-diagonal/multicolor Ramsey-type lower bounds should try first before reaching for deep analytic number theory.

Related

- erdos/721 — the originating Erdős problem (erdosproblems.com #721) this page fully answers on both of its explicit asks (non-trivial lower bound; subexponential upper bound), while leaving the exact growth rate of $W(3,k)$ open. - Finite-field / projective-plane constructions for extremal additive sets — the projective-line-over-$\mathbb{F}_p$ amplification step Green uses to control random quadratic forms uniformly across all candidate common differences; a recurring tool whenever a single random object must be shown robust against an entire adversarial family at once. - concept/ellipsoidal-annulus-construction — (new concept, seeded here) the "color by proximity to a random quadric on a high-dimensional torus" technique underlying both Green's and Hunter's constructions; the natural first thing to try for other off-diagonal/mixed Ramsey lower bounds that look artificially capped at a low-degree polynomial. - concept/random-greedy-algorithm — a structurally different but philosophically related "trade one hard global random object for many independent easy ones" move, also seen in the Kahn–Kalai threshold proof; useful cross-reference for when *multiplicity beats depth* as a simplification strategy. - Kahn–Kalai conjecture — threshold vs. expectation-threshold for monotone properties — nearest sibling in the "replace an intricate single random/analytic argument with an elementary multiplicity-based one" technique family, despite living in a totally different problem domain (thresholds vs. Ramsey numbers) — useful contrast on how the same meta-technique (many independent weak random objects > one strong one) recurs across additive/probabilistic combinatorics. - Downstream/related but *not* the same result: Fox & Hunter's three-color diagonal van der Waerden super-exponential growth (arXiv:2606.02541) — same authorship lineage and construction family, different (multicolor, diagonal) parameter regime; not yet given its own wiki page.