VibeMathedMath problems solved with AI
Sign in

Erdos Problem #138: do the van der Waerden numbers grow superexponentially, W(k)^(1/k) -> infinity?

Let W(k)W(k) be the least NN such that every two-colouring of {1,…,N}\{1,\dots,N\} contains a monochromatic kk-term arithmetic progression. Classical lower bounds are exponential: Berlekamp gave W(p+1)>p2pW(p+1)>p2^p for primes pp, and the local lemma gives roughly 2k/k2^k/k. Erdos asked whether the growth is in fact superexponential: is it true that W(k)1/k→∞W(k)^{1/k}\to\infty?

Result
Proved(see note)
Status
Candidate (review pending)
AI contribution
AI-discovered
Method
Construction
Field
Ramsey theory, arithmetic progressions
Posed by
Paul Erdos
Year posed
1980
Years open
46y
Solved
2026-09-23
Model
Unreleased internal OpenAI model
Vendor
OpenAI
Collaborators
—
Verification
Lean-checked, statement unaudited
Publication
Announced
Collection
OpenAI math release (October 2026), version adc7f12
Significance
22 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Theorem 1.1: there is an absolute K0K_0 with Wr(k)>kck⌊log⁡2r⌋W_r(k)>k^{ck\lfloor\log_2 r\rfloor}, c=10−5c=10^{-5}, for all k≥K0k\ge K_0 and r≥2r\ge2; hence Wr(k)1/k→∞W_r(k)^{1/k}\to\infty for each fixed rr. Prior work in 2026: Fox-Hunter proved superexponential growth for three colours, and Campos-Fox-Schildkraut proved W2(k)≥(1−o(1))k2k−1W_2(k)\ge(1-o(1))k2^{k-1}, settling W2(k)/2k→∞W_2(k)/2^k\to\infty but not the limit asked here. Not shown: the companion question W(k+1)−W(k)→∞W(k+1)-W(k)\to\infty, or any upper bound improvement.

What the AI did

The release README says every result in it was produced by an unreleased internal OpenAI model following a fixed procedure, on average about three hours of ChatGPT Pro thinking compute per result. This result is not among the README's two exceptions (the Hodge conjecture for CM abelian varieties and the Re(s) > 11/12 zero-free region, whose write-up was human-edited). The manuscripts are authored 'OpenAI' and name no human author. The family is a single manuscript (September 23, 2026) with a Lean formalization of its headline bound listed in the release's formalization catalogue.

Verification

No independent mathematician has checked this yet. Checked here: the introduction and Theorem 1.1 were read against Erdos's question; the theorem implies Wr(k)1/k→∞W_r(k)^{1/k}\to\infty for each fixed r≥2r\ge2, including r=2r=2. Lean: formalization.yaml lists OAI.QuantitativeVanDerWaerden.uniform_lower_bound (OAI/Combinatorics/ProgressionColoring/Main.lean). The comparator statement was read: it asserts an absolute KK with kk⌊log⁡2r⌋/100000<W(r,k)k^{k\lfloor\log_2 r\rfloor/100000}<W(r,k) for all k≥Kk\ge K, r≥2r\ge2, where WW is defined as an infimum without a built-in finiteness proof (the strict inequality forces finiteness). This is the headline bound; the limit is an immediate consequence. Not rebuilt here.

Sources

Changelog1 change

Discussion