Browse › Combinatorics › 160 Superexponential van der Waerden numbers
Quantitative Superexponential Bounds for van der Waerden Numbers
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
We prove that there are absolute constants c > 0 and K0 such that $W_r(k)\gt k^{ck\lfloor\log_2 r\rfloor}$ for every $k\ge K_0$ and r ≥ 2. Consequently $W_r(k)^{1/k}\to\infty$ for each fixed r ≥ 2, giving a quantitative positive resolution of Erdős's superexponential-growth question, including the two-color case.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Follow-up works
- Rohan Arun and repository contributors, van-der-waerden-refinement (Conditional refinements of OpenAI's October 2026 math release) (GitHub research draft, October 2026). Proposes replacing the paper's coefficient $10^{-5}$ by $1/25$, by $1/9$ as the headline value, and more generally any fixed $c<1/8$, conditional on the pinned OpenAI construction and stated additional inputs; the README says the work has had no independent human review or end-to-end formal verification. [AI-generated per source]
- 1337isnot1337, Conditional logarithmic endpoint bound and explicit c=1/9 threshold (GitHub PR #12, 2026-10-16). With disclosed GPT-6 assistance, proposes $W_r(k)>(k^{1/8}/(e^{20}\log k))^{k\lfloor\log_2 r\rfloor}$ for $k\ge2^{1024}$ and $r\ge2$, conditional on the pinned OpenAI geometric counts and subsequent digit-rank refinements.
Comments and discussion
- Thomas Bloom (erdosproblems.com), Erdős problems in the OpenAI proofs (erdosproblems.com blog, 2026-10-08). Lists Problem 138 among the significant claims in the release, notes that Fox and Hunter proved such a bound for $r\ge3$, and says the 25-page PDF "appears to use similar methods to [FoHu26] (and various other earlier work)."
Formalization
- OpenAI, lean/docs/160.md (Lean scope note, mirrored by mathcommunity) (OpenAI math release, 2026-10-06). The release's scope note: the Lean development proves $W(r,k)>k^{k\lfloor\log_2 r\rfloor/100000}$ for all $k\ge K$, $r\ge2$, together with growth limits, finiteness and boundary values, but not the paper's sharper intermediate estimates.
- OpenAI, ProgressionColoring/Main.lean (github.com/openai/math, commit adc7f12). Contains
uniform_lower_bound,exists_uniform_lower_bound,kthRoot_tendsto($W_r(k)^{1/k}\to\infty$ for fixed $r$) andlength_rate_tendsto; this file has nosorry, but it relies on imported modules. - OpenAI, QuantitativeVanDerWaerden.lean (comparator statement) (github.com/openai/math). The standalone statement of
uniform_lower_bound, with $W$ defined as ansInfand the proof left assorry(as a comparator statement); this is the file linked from erdosproblems.com and Bloom's post. - Google DeepMind formal-conjectures, ErdosProblems/138.lean (formal-conjectures repository). Marks
erdos_138($\lim W(k)^{1/k}=\infty$) as solved, cites this paper as [OAI26], and links the OpenAI Lean proof as its formal proof; the quotient variant $W(k+1)/W(k)\to\infty$ is still marked open. - Rohan Arun, Add conditional proof reviews and partial Lean verification (GitHub draft PR #10, 2026-10-13). Reports a Lean package checking selected geometric lemmas, digit identities, coloring transfers and parameter inequalities for the follow-up refinement, with the full lower-bound theorems and major counting and local-lemma arguments explicitly outside its coverage. [AI-generated per source]
Related prior literature mentioned by others
- Jacob Fox and Zach Hunter, Three-color van der Waerden numbers grow super-exponentially (arXiv:2606.02541, 2026-06-01). Proves $W_3(k)>2^{k\log^*k/4}$ for sufficiently large $k$; Bloom's post, erdosproblems.com and the Open Mathematics Courses exposition cite it as the $r\ge3$ precursor whose methods the paper appears to share (already in the paper's bibliography).
- Marcelo Campos, Jacob Fox and Carl Schildkraut, A new lower bound for two-color van der Waerden numbers (arXiv:2608.20824, 2026-08-21). Cited in the formal-conjectures entry, the erdosproblems.com forum and the Open Mathematics Courses exposition for $W_2(k)\ge(1-o(1))k2^{k-1}$, which settles $W_2(k)/2^k\to\infty$ (already in the paper's bibliography).
Possibly relevant literature (found by the agent, not checked)
- Thomas Blankenship, Jay Cummings and Vladislav Taranchuk, A New Lower Bound for van der Waerden Numbers (arXiv:1705.09673, European J. Combin., 2017). Proves the multicolour Berlekamp-type bound $w(r,p+1)>p^{r-1}2^p$ for $r\le p$, relevant to the paper's survey of earlier $r$-colour lower bounds (Berlekamp, Kozik–Shabanov, Hunter).
- Haitao Cao, An improved lower bound for the van der Waerden number $w(3,k)$ (arXiv:2609.31798, 2026-09-25). Claims $w(3,k)\ge k^{\Omega(\log k)}$ for the asymmetric problem the paper places its squared-norm construction alongside (Green 2022, Hunter 2022).
Digests and expositions
- Open Mathematics Courses / Claude Opus 5.5, Superexponential van der Waerden numbers (online course, October 2026). Five lessons on the paper's circle coordinates, adaptive meshes, local-lemma coloring and norm-band perturbation, with exercises and solutions; the text identifies itself as AI-written and self-checked, with independent review incomplete. [AI-generated per source]
News and blogs
- Alex Myers, AI Digest: October 11th 2026 (Substack, 2026-10-11). Reports Rohan Arun's announced coefficient $1/25$ refinement of the van der Waerden bound as one outcome of community work following the OpenAI release.
Elsewhere
- VibeMathed: Problem record
- Emergent Mind: family 160
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:Quantitative-Superexponential-Bounds-for-van-der-Waerden-Numbers-September-23-2026,
author = {{OpenAI}},
title = {{Quantitative Superexponential Bounds for van der Waerden Numbers}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Quantitative-Superexponential-Bounds-for-van-der-Waerden-Numbers-September-23-2026/paper.pdf}{OAI:Quantitative-Superexponential-Bounds-for-van-der-Waerden-Numbers-September-23-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/160.md. The Lean statements have not been checked by people against the paper's claims.
Family 160: Superexponential van der Waerden numbers
Resolves Erdős's superexponential-growth question for van der Waerden numbers. If $W_r(k)$ is the least interval length forcing a monochromatic k-term progression in every r-coloring, then $W_r(k)\gt k^{ck\lfloor\log_2 r\rfloor}$ for an absolute c > 0, all r ≥ 2 and sufficiently large k, uniformly in r. In particular, $W_r(k)^{1/k}\to\infty$ for each fixed r.
This is the only paper in this family.