Superexponential van der Waerden numbers

Proves van der Waerden numbers grow faster than any exponential, answering a question of Erdős for two colors.

1 paper September 23, 2026 Explained by AI

If you color the numbers 1 to N with a few colors and N is large, some long evenly spaced run gets one color. The van der Waerden number is the smallest such N. Erdős asked whether, for two colors, this number grows faster than any fixed number raised to the power k. The paper proves that it does, with an explicit bound valid for every number of colors. A computer proof checker has a formal version of this bound.

First step

1980

Paul Erdős, question on the superexponential growth of W_2(k)

Significance

Major

It settles Erdős's superexponential-growth question for two colors with an explicit, Lean-checked bound.

Trust

Formal proof listed

Field

Combinatorics

1 paper

The explanation

Color the numbers 1 to 8 as red, red, blue, blue, red, red, blue, blue. Look for three numbers in a row with equal gaps, like 2, 5, 8, all the same color. There are none. A run with equal gaps is an arithmetic progression. Now try 1 to 9. A computer search over all 512 two-colorings finds that every one has a three-term progression in one color. So 9 is the least length that forces one. This least length is the van der Waerden number W_2(3), with 2 colors and progressions of length 3.

In general, W_r(k) is the least N where every coloring of 1 to N with r colors has a one-color progression of length k. Van der Waerden proved in 1927 that these numbers are finiteSource 1. How fast they grow is a separate question. Kozik and Shabanov showed W_r(k) is at least a constant times r^(k−1)Source 2. For two colors that is roughly 2^k, an exponential. Erdős asked whether W_2(k)^(1/k) tends to infinity, so that no fixed exponential keeps upSource 3. Recent work pushed past 2^k by a factor of about k/2 for two colorsSource 4.

The paper answers Erdős's question. For every k above a fixed threshold and every r ≥ 2, W_r(k) exceeds k^(ck⌊log₂ r⌋) with c = 10^(−5)Source 5. For two colors the exponent is ck. Taking the k-th root leaves k^c, which grows without limitSource 6. The constant is tiny, though. The bound beats 2^k only once log₂ k exceeds 100,000.

The proof builds a two-coloring of a large cyclic group, then adds independent random flipsSource 7 Source 8. A heavily repeated label pattern along a progression creates a short period. The obstacle is to control these repeats when the number of coordinates grows with kSource 9. The paper handles this with a counting estimate whose constant does not depend on the coordinatesSource 10.

How sure is this? Lean, a computer proof checker, has a formal statement of the main bound with the same constant. So the paper proves it, as far as the Lean statement matches the paper. Its sharper intermediate estimates are outside the Lean scope. No specialist review of the paper is published.

What it doesn't show. This does not give useful numbers for small progressions: the constant is 1/100,000, so the bound beats 2^k only for astronomically long progressions. It also does not find exact van der Waerden numbers.

Where it came from

This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026.

Hype check

Major: it settles a stated Erdős question with a Lean-checked bound. The constant is very small, so the bound says nothing for practical progression lengths. No specialist review is published.

Words used

Arithmetic progression: Numbers with equal gaps, such as 2, 5, 8.
Van der Waerden number: The least length that forces a one-color arithmetic progression of a given length in every coloring.
Exponential growth: Growth like 2^k, where adding one to k multiplies the value by a fixed amount.
Superexponential: Growing faster than every fixed exponential such as 2^k or 100^k.
Cyclic group: Numbers that wrap around after a fixed size, like hours on a clock.
Floor ⌊x⌋: The largest whole number not above x.

The original paper

Quantitative Superexponential Bounds for van der Waerden Numbers (PDF, opens in a new tab)
September 23, 2026 Formal proof listed

Lean notes

All quoted lines (10)

The finiteness of these numbers is van der Waerden's theorem.
Quantitative Superexponential Bounds for van der Waerden Numbers Back to text
Kozik and Shabanov subsequently obtained an absolute $\beta>0$ such that $W_r(k)\ge\beta r^{k-1}$ for all $r\ge2$ and $k\ge3$ .
Quantitative Superexponential Bounds for van der Waerden Numbers Back to text
Erd\Hos explicitly asked for this full limit in the two-color case.
Quantitative Superexponential Bounds for van der Waerden Numbers Back to text
Campos, Fox, and Schildkraut proved $W_2(k)\ge(1-o(1))k2^{k-1}.$
Quantitative Superexponential Bounds for van der Waerden Numbers Back to text
There is an absolute integer $K_0$ such that, for every integer $k\ge K_0$ and every integer $r\ge2$ , $W_r(k)>k^{c k\lfloor\log_2r\rfloor}, \qquad c=10^{-5}.$
Quantitative Superexponential Bounds for van der Waerden Numbers Back to text
Thus Theorem … gives a quantitative positive resolution of his superexponential-growth question.
Quantitative Superexponential Bounds for van der Waerden Numbers Back to text
We first construct a two-coloring of a cyclic group $\Z/q^D\Z$ with $q^D\ge k^{ck}$ , where $q$ is a power of a prime exceeding $k$ .
Quantitative Superexponential Bounds for van der Waerden Numbers Back to text
We attach an independent Bernoulli $(p)$ flip to each key consisting of a $y$ -box and $\lfloor\|q\widetilde y\|_2^2\rfloor$ , where $p=k^{-1/20}$ and $\widetilde y\in[-1/2,1/2)^D$ is the centered representative.
Quantitative Superexponential Bounds for van der Waerden Numbers Back to text
The quantitative obstacle is to control such returns when the dimension grows with $k$ : constants depending arbitrarily on the dimension would not suffice.
Quantitative Superexponential Bounds for van der Waerden Numbers Back to text
A key estimate counts the patterns through one specified label by $(CDh)^{6D}$ , with an absolute $C$ independent of $q$ , $\lambda$ , and the width of the anchor interval.
Quantitative Superexponential Bounds for van der Waerden Numbers Back to text

Other sources

openai/math, Lean scope note for family 160 The formalized result gives an absolute threshold $K$ such that $W(r,k)>k^{k\lfloor\log_2 r\rfloor/100000}$ for all $k\ge K$ and $r\ge2$ .
openai/math release notes (2026): model provenance and review status manuscripts and supporting proof artifacts produced by an internal OpenAI model

171The hypercube Ramsey conjectureCombinatorics
189Cycle–clique Ramsey numbersCombinatorics
184Correspondence coloring with a fixed forbidden subgraphCombinatorics
170Sharp logarithmic exponents for off-diagonal Ramsey numbersCombinatorics
172Classification of finite Euclidean Ramsey configurationsCombinatorics

Browse Combinatorics Erdős problems Ramsey theory Graph theory Open since the 1980s Lean-checked results