Random quadratic form pseudorandom coloring constructions (Green–Hunter annulus method)

Statement

The technique in one sentence. To lower-bound an *off-diagonal* two-coloring number — where one color class must avoid a short/fixed pattern (e.g. a 3-term arithmetic progression) while the other color class must avoid an arbitrarily long pattern (a $k$-term AP, the parameter to be bounded) — embed $[N]$ into a high-dimensional torus $\mathbb T^D$ via a Weyl/polynomial map $\theta$, color a point blue iff its image lands inside a thin annulus $A$ defined by a randomly chosen quadratic form (a random perturbation of the identity matrix, i.e. a random ellipsoid) translated to a random lattice of centers, and red otherwise; then show (i) the annulus is geometrically too thin to contain a 3-term progression in either variable, so no blue 3-AP exists, and (ii) for *every* one of the $\sim N$ candidate common differences $d$, a long red ($d$-difference) AP is forced with high probability to intersect the annulus somewhere, because the values of the induced 1-parameter quadratic form along the progression must eventually fall inside the annulus's tiny target window.

Origin theorem (Green, 2021). There is a red/blue coloring of $[N]$ with no blue 3-term AP and no red AP of length $e^{C(\log N)^{3/4}(\log\log N)^{1/4}}$. Equivalently, the two-color off-diagonal van der Waerden number satisfies $$w(3,k) \ge k^{b(k)}, \qquad b(k) = c\left(\frac{\log k}{\log\log k}\right)^{1/3}.$$ This is superpolynomial — beats $k^C$ for every fixed $C$ — and directly disproved Ron Graham's conjecture, made on the strength of small computed data ($W(3,10)=97$, $W(3,20)\ge389$), that $W(3,k)=O(k^2)$ [Green, arXiv:2102.01543, Forum Math. Pi].

Refinement (Hunter, 2021–22). Replacing Green's single ellipsoidal annulus (one random quadratic form, random eccentricity, fixed radius) with many independent circular annuli (fixed eccentricity, each with its own independently random radius) — trading one hard-to-control random algebraic object for many easy, elementary-probability ones — improves the exponent to $$b(k) = c\,\frac{\log k}{\log\log k}$$ [Hunter, arXiv:2111.01099, *Combinatorica*]. In Hunter's own words: "Green only considers his single instance of randomness, while we take advantage of having multiple instances of randomness," and the construction "replaces a complicated result about random quadratic forms with an elementary probabilistic result."

Facts

- Setting is genuinely off-diagonal, not diagonal. The technique lower-bounds $w(3,k)$ — a 3-AP forbidden in one color, a $k$-AP forbidden in the other. It has not been ported to the diagonal case $W(k)=w(k;2)$ (equal pattern length $k$ in both colors), which is Erdős's still-open \$500 question Erdős #138 — does W(k)^{1/k} → ∞ for van der Waerden numbers?; that page explicitly flags "port Ben Green's random-quadratic-form pseudorandom construction… to the diagonal $W(k)$ setting" as its top concrete open attack-surface experiment. - The randomized object is specifically the quadratic form defining the annulus's shape, not the pointwise coloring itself: $A_e=\{x\in\mathbb R^D: \rho-N^{-4/D}<\|(I+\sigma(e))x\|_2<\rho\}$, with $\sigma(e)$ a symmetric perturbation matrix built from a random vector $e$, $D\approx C r^2$, $\rho=D^{-4}$; a naive 1-dimensional uniformly random coloring of $[N]$ almost surely contains long monochromatic APs once $N$ exceeds polynomial size in $k$ — beating $O(k^2)$ genuinely requires the extra geometric structure of a quadratic form, not raw randomness. - Why an ellipsoid, not a sphere. The perturbation away from a round sphere is load-bearing: a perfectly spherical annulus has extra rotational symmetry that an adversarial long AP could exploit to hide inside it; randomizing the *eccentricity* (Green) or the *radius* across many independent circles (Hunter) is what removes that symmetry. - The hard step is a uniform-over-all-differences guarantee. There are $\sim N^{1-1/r}$ candidate common differences $d$ to simultaneously defeat with essentially one random construction. Green controls this via the Hardy–Littlewood circle method (a Davenport–Heilbronn-type quadratic-form variant) plus an amplification argument over projective lines in $\mathbb F_p$ — deep analytic-number-theory machinery imported to bound the exceptional probability tightly enough for a union bound over all $N^{1-1/r}$ differences at once. Hunter's simplification sidesteps this entirely: instead of forcing one random object to be uniformly robust, he uses many independent weak random objects (independent random-radius circles) and lets an elementary union bound over the *objects* do the work that Green's union bound over *configurations* needed deep tools for. - Short elementary sibling result. Hunter, "A short proof that $w(3,k)\ge(1-o(1))k^2$," arXiv:2209.07651 (Oct 2022) — a much simpler, purely combinatorial construction giving only the classical-looking quadratic bound, valuable as a clean baseline but not using the random-quadratic-form/annulus machinery at all. - Upper-bound side, for contrast (not this technique): Schoen (2021, *Electron. J. Combin.*, arXiv:2006.02877) first proved $W(3,k)<\exp(k^c)$ for some $c<1$ (subexponential), later sharpened via Kelley–Meka's quasipolynomial Roth bound (2023) as improved by Bloom & Sisask (arXiv:2309.02353) to $W(3,k)\ll\exp(O((\log k)^9))$. The true growth rate of $W(3,k)$ remains open — only "non-trivial lower bound" and "subexponential upper bound," Erdős's two explicit asks (erdosproblems.com #721 erdos/721), are settled. - Downstream/sibling multicolor result, different technique. Fox & Hunter, "Three-color van der Waerden numbers grow super-exponentially," arXiv:2606.02541 (2026), resolve the *diagonal* 3-color case $w(k;3)$ via a completely different iterated/$\log^*k$-recursive construction (sparse Behrend hitting set + Lovász Local Lemma + random-shifted-product amplification, not a random quadratic form) — see Fox–Hunter (2026) — three-color van der Waerden numbers $w(k;3)$ grow super-exponentially in $k$; the two techniques are cited alongside each other in this wiki's problem pages but are not the same construction.

Technique

WHEN this applies. Reach for this construction whenever a 2-coloring lower bound is genuinely off-diagonal: one color's forbidden pattern is short/fixed (paradigmatically a 3-AP) and the other color's forbidden pattern length is the free asymptotic parameter to be lower-bounded, *and* a naive 1-dimensional random or greedy coloring appears artificially capped at a low-degree polynomial rate that matches small computed data (here, $O(k^2)$) even though there is reason to suspect the truth is superpolynomial. It is specifically the right tool when a single random object needs to simultaneously defeat a large ($\sim N$-sized) family of adversarial linear structures (here: every candidate common difference $d$ of the long progression) — the situation where a per-configuration union bound with independent randomness per configuration is too weak on its own.

WHY it works (the mechanism, stacked)

1. Dimension lift turns combinatorics into geometry. Embedding $[N]$ into $\mathbb T^D$ via a Weyl/polynomial map $\theta$ (with $D$ tuned to the target progression length $N^{1/r}$) converts "does this AP survive the coloring" into "does $\theta$ applied to this AP avoid a thin algebraic hypersurface (the annulus)" — a geometric non-degeneracy question with tools (circle method, quadratic form estimates) attached, rather than a bare combinatorial union-bound question. 2. **Randomizing the *quadratic form* rather than the coloring pointwise is what breaks the fatal symmetry. A round-sphere annulus has too much rotational symmetry for an adversary's long AP to be forced to avoid; perturbing to a random ellipsoid (Green) or randomizing the radius of many independent circles (Hunter) removes exactly that symmetry, at the cost of needing to control a genuinely random algebraic object. 3. "One hard uniform guarantee" (Green) vs. "many easy independent guarantees" (Hunter) — the transferable meta-lesson.** Green needs *one* random quadratic form to behave well against *every* one of $\sim N^{1-1/r}$ candidate differences simultaneously, which forces him into deep tools (Hardy–Littlewood circle method, $\mathbb F_p$-projective-line amplification). Hunter instead uses *many* independent random objects (circles with independent random radii) so that a long AP is defeated by the union of many cheap, elementary-probability events rather than by one object being simultaneously robust against every configuration — this "multiplicity over depth" trade is frequently both a strict simplification *and* a strengthening of the resulting bound, and is the single most portable idea in this technique for reuse elsewhere. 4. The superpolynomial (not merely polynomial) gain comes from compounding a dimension parameter. The final exponent $b(k)$ is a function of the dimension/annulus parameter $r\approx\log k/\log\log k$ chosen post hoc to optimize the trade-off between annulus thinness (needed to avoid blue 3-APs) and the union-bound cost over $\sim N^{1-1/r}$ differences (needed to avoid red long APs) — the fact that this optimization yields a superpolynomial rather than fixed-polynomial exponent is what disproves Graham's $O(k^2)$ conjecture rather than merely improving its constant.

HOW to use it to prove things (recombination steps)

1. Confirm the problem is off-diagonal: one color's forbidden pattern is short/fixed, the other's is the free parameter — this technique is not (yet) known to transfer to diagonal/symmetric two-coloring problems (cf. the still-open Erdős #138 — does W(k)^{1/k} → ∞ for van der Waerden numbers?). 2. Choose a dimension $D$ and Weyl/polynomial embedding $\theta:[N]\to\mathbb T^D$, tuned so the target long-pattern length is $N^{1/r}$ for a parameter $r$ to be optimized later. 3. Define a random "annulus" target region in $\mathbb T^D$ via a randomly perturbed quadratic form (a random ellipsoid, or — following Hunter's simplification — a union of independently-random-radius circles/spheres of fixed shape) translated across a well-spread lattice of centers. 4. Color a point by membership: the rare/short-pattern color if $\theta(n)$ lands in the annulus, the other color otherwise. 5. Prove short-pattern avoidance geometrically: show the annulus is too thin to contain the short pattern (e.g. a 3-AP) directly from its width in the $\|\cdot\|_2$-norm — a purely geometric, not probabilistic, argument. 6. Prove long-pattern avoidance via a uniform-over-differences guarantee: for every candidate common difference $d$, show that with high probability a long progression with that difference is forced to hit the annulus — either (a) via deep analytic tools (Hardy–Littlewood circle method + finite-field/projective-line amplification, if using one hard random quadratic form, Green's route) or (b) via a union bound over many independent, individually-elementary random objects (Hunter's route) — then union-bound over all $\sim N^{1-1/r}$ candidate differences. 7. Optimize the dimension/annulus parameter $r$ as a function of $k$ to extract the final exponent $b(k)$ in $w(3,k)\ge k^{b(k)}$; check whether route (b) (Hunter's multiplicity trick) can replace any deep-analytic step in route (a) for a shorter proof and/or better constant — this substitution itself, once identified, is usually the fastest way to improve on a prior "random quadratic form" bound in this family. 8. When it does NOT directly apply: the diagonal case (equal pattern length in both colors) has no known analogue of "one color's pattern is a short, geometrically-thin target" to exploit — this is precisely the gap flagged as open on Erdős #138 — does W(k)^{1/k} → ∞ for van der Waerden numbers?.

Related

- erdos/721 — the problem (erdosproblems.com #721, off-diagonal van der Waerden number $W(3,k)$) this construction resolves, disproving Graham's $O(k^2)$ conjecture with a superpolynomial lower bound. - Off-diagonal van der Waerden numbers — W(3,k) grows superpolynomially, disproving Graham's O(k²) conjecture — this wiki's full worked solved-problem page with the detailed step-by-step narrative (including the exact annulus formula, circle-method mechanism, and Green→Hunter genealogy) that this concept page distills into a reusable technique. - Erdős #138 — does W(k)^{1/k} → ∞ for van der Waerden numbers? — the still-open \$500 diagonal van der Waerden question $W(k)^{1/k}\to\infty$; porting this technique from off-diagonal to diagonal is explicitly flagged there as the most concrete open attack-surface experiment, not yet successfully carried out. - Fox–Hunter (2026) — three-color van der Waerden numbers $w(k;3)$ grow super-exponentially in $k$ — Fox–Hunter's 2026 resolution of the diagonal *3-color* van der Waerden growth rate, via a structurally different iterated/$\log^*k$-recursive Lovász-Local-Lemma construction (not a random quadratic form); cited alongside this technique in the wiki's problem pages as a sibling but distinct "arm" of the same broader off-diagonal/multicolor AP-avoiding-lower-bound literature. - Finite-field / projective-plane constructions for extremal additive sets — the projective-line-over-$\mathbb F_p$ amplification tool Green borrows from finite-field/algebraic-geometry machinery to control his single random quadratic form uniformly across all candidate common differences; the general "explicit finite-field algebra beats raw union-bounding" family this step belongs to. - Lovász Local Lemma (symmetric, general/asymmetric, and algorithmic/random-recoloring variants) — probabilistic existence when bad events are individually non-negligible but sparsely dependent — the contrasting machinery (Szabó 1990; Kozik–Shabanov, arXiv:1409.6921) behind the current best *diagonal* van der Waerden lower bound $\Omega(2^k)$; does not use quadratic forms, and has not been beaten since 2016, unlike this off-diagonal technique's rapid 2021→2022 improvement cycle.