Episode 160, October 2026

Faster than exponential?

A preprint claims that van der Waerden numbers outgrow every exponential, already with two colours and uniformly in the number of colours

Covers result 160 in OpenAI’s catalog: its one paper. See its connections to other results and the work it cites.

Play Episode 160: Faster than exponential? An 11 by 11 grid in four colours, the digit-product colouring of 0 to 120, below the formula W 2 of k to the 1 over k tends to infinity.

6:28. English captions available. The video loads from YouTube when you press play.

Chapters

The claim, in plain words

Colour the numbers from 1 to N with r colours and try to avoid k evenly spaced numbers of one colour. Van der Waerden proved in 1927 that a long enough interval always contains such a progression; W_r(k) is the first length where it is forced. By our exhaustive search, W₂(3) = 9 (the colouring red, red, blue, blue, red, red, blue, blue of 1 to 8 works), W₂(4) = 35 and W₃(3) = 27; none of these values is in the paper. As the paper recounts, the known lower bounds were exponential: Szabó’s W₂(k) ≥ 2^k/k^ε, Kozik and Shabanov’s βr^k−1, and Berlekamp’s W₂(p+1) > p·2^p for primes p. “Recent results distinguish the two questions posed by Erdős”: Fox and Hunter (2026) proved superexponential growth with three colours, and Campos, Fox and Schildkraut (2026) proved W₂(k) ≥ (1 − o(1))k·2^k−1, settling whether W₂(k)/2^k → ∞; “They credit ChatGPT 5.6 Sol Pro with the coloring and an initial proof.”

Result 160 is a single OpenAI preprint, Quantitative Superexponential Bounds for van der Waerden Numbers (25 pages, dated September 23, 2026). Theorem 1.1: there is an absolute K₀ such that W_r(k) > k^{c·k·⌊log₂ r⌋}, with c = 10⁻⁵, for every k ≥ K₀ and every r ≥ 2. For two colours that is W₂(k) > k^k/100,000, so W₂(k)^1/k → ∞: “a quantitative positive resolution of Erdős’s superexponential-growth question, including the two-color case.” One threshold works for every number of colours.

What it doesn’t claim

The proven growth is superexponential, but barely: the k-th root of the bound is k^1/100,000, about 1.0023 at k = 10¹⁰⁰, and by our arithmetic the bound overtakes 2^k only when k has more than 30,000 digits, so for k of any practical size the older exponential bounds are larger. K₀ is never computed, there is no matching upper bound (Appendix A is “a coarse version of the classical argument”), and the colouring is shown to exist by probability rather than written down. The paper notes that Fox and Hunter’s bound is stronger when the number of colours is large compared with log k. In the number of colours, for a fixed length k ≥ 3, growth beats every power of r, as was already known and the paper reproves (Theorem 7.2); with the companion paper (result 159) it is at most quasipolynomial. The paper calls Erdős’s problem a question, not a conjecture, and mentions no prize.

Where it stands

Posted as a preprint: OpenAI, 25 pages, dated September 23, 2026
Peer reviewed: Not yet
Checked in Lean: Exactly the main theorem, with c = 1/100,000. We have not rebuilt it

Last checked October 19, 2026. The preprint has not been revised since it was added to the repository in its initial commit on October 6, 2026. OpenAI published a Lean formalization of exactly the main theorem (comparator: c = 1/100,000, every r ≥ 2, colourings with at most r colours), in 115 files and 14,837 lines excluding Mathlib (development); we found no unproved steps, and we have not rebuilt it. The threshold is shown to exist but not computed, and, as the scope note says, the paper’s sharper intermediate estimates are not part of the formalization. The paper is not among those OSVerify reviewed, and we have seen no expert review. We could not check the 2026 papers it cites.

How the proof goes

Dials and labels. Work in the integers modulo q^D, with q a power of a prime larger than k and D about k^1/10. Each number gets D dials reading its last digits in base q as a fraction, plus a second set turning a fixed whole number of times faster; along a progression every dial turns at a constant speed. The tiny arcs a number’s dials point to form its label, and labels are coloured red or blue at random, with the Lovász local lemma ruling out bad cases, so that progressions whose labels seldom repeat see both colours often.
Repetition, keys and bands. A progression whose labels keep repeating is nearly periodic. Long periods are balanced by the same random colouring; for short ones, a dilation removes the period, leaving a straight line in the second coordinates. Rare random flips (probability k^−1/20) share one coin per key, a box of coordinates plus a band of squared distance, in the spirit of Behrend’s construction; a line meets such a band in at most two short pieces, so a key repeats at most four times. Rich progressions would need many rare flips at once, and straight ones have few possible shapes; the union bound forces c below 1/16,000, and 10⁻⁵ is safe.
Digit product. Write numbers in base N and colour each by the list of its digits’ colours. In the place of the step’s lowest nonzero digit, the numbers’ digits run through a cyclic progression, which is never one colour; so 2^m colours reach length N^m, and m = ⌊log₂ r⌋ gives the main bound.

The numbers in the video

Our exhaustive search: 6 two-colourings of 1 to 8 with no one-coloured 3-term progression and none of 1 to 9; 28 of 1 to 34 for four terms and none of 1 to 35; 48 three-colourings of 1 to 26 and none of 1 to 27.
Our digit-product check: the colouring 00010010111 of the integers modulo 11 has no one-coloured cyclic 4-term progression; lifted to 16 colours on 0 to 14,640, it has none either (brute force).
Our arithmetic: k^k/100,000 exceeds 2^k exactly when log₂ k > 100,000; k^1/100,000 is 1.00014, 1.00101, 1.00231 and 1.02329 at k = 10⁶, 10⁴⁴, 10¹⁰⁰, 10¹⁰⁰⁰.
The Lean counts: 115 files and 14,837 lines, our count of the import closure.

Read the source

Quantitative Superexponential Bounds for van der Waerden Numbers (PDF), 25 pages.
The Lean scope note.
The collection’s catalog, where this is result 160.

The paper

OpenAI groups related papers into one result; this one has a single paper.

Quantitative Superexponential Bounds for van der Waerden Numbers

Transcript

Read the full script

0:00The game

Colour the numbers from one to N red or blue, and try to avoid k evenly spaced numbers of the same colour. For three-term progressions you can get to eight, for example red, red, blue, blue, red, red, blue, blue, but not to nine. In our exhaustive check, six colourings of one to eight work, and none of one to nine. Van der Waerden proved in 1927 that for any number of colours r and any length k, a long enough interval always contains a progression of one colour. The van der Waerden number, W_r(k), is the first length where that is forced. Our search also gives 35 for two colours and length four, and 27 for three colours and length three. How fast does it grow with k? As the paper recounts, the known lower bounds were exponential. Szabó proved 2^k divided by any small power of k, for two colours; Kozik and Shabanov, a constant times r^(k−1); and Berlekamp’s algebraic construction gives more than p times 2^p for lengths one more than a prime p. Erdős asked two questions about two colours: does W_2(k) divided by 2^k tend to infinity? And, stronger, does its k-th root tend to infinity, so that it eventually beats every exponential? The paper cites two 2026 results on these questions. Fox and Hunter proved superexponential growth with three colours, and so, as we read it, with any larger number. Campos, Fox and Schildkraut proved that W_2(k) is at least about k times 2^(k−1), settling the first question; the paper notes that they credit ChatGPT 5.6 Sol Pro with the colouring and an initial proof. The paper presents the full limit, for two colours, as its contribution.

1:52The claim

Result 160 is a 25-page OpenAI preprint, dated September 23. It claims a threshold K₀ such that, for every k at least K₀ and every number of colours r at least two, W_r(k) is greater than k^(c·k·⌊log₂ r⌋), with c equal to 1/100,000. For two colours, that is k^(k/100,000), so the k-th root grows without bound. The paper calls this a quantitative positive resolution of Erdős’s superexponential-growth question, including the two-colour case. One threshold works for every number of colours. The proven growth is superexponential, but barely. The k-th root of the bound is k^(1/100,000): about 1.002 at k equal to a googol. By our arithmetic, it overtakes 2^k only when k has more than 30,000 digits, so for every k of any practical size, the older exponential bounds are larger. The threshold K₀ is never computed, there is no matching upper bound, and the colouring is shown to exist by probability rather than written down. For a fixed length of three or more, growth in the number of colours is a different story: it beats every power of r, as was already known and the paper reproves, and, with the companion paper, it is at most quasipolynomial.

3:20How the proof goes

The construction lives in a huge cyclic group, the integers modulo q^D, where q is a power of a prime larger than k, and D is about the tenth root of k. Each number gets D dials that read its last digits in base q as a fraction, plus a second set turning a fixed whole number of times faster, and along any progression every dial turns at a constant speed. Chop the dials into tiny arcs; the arcs a number points to form its label. The labels are coloured red or blue at random, with the Lovász local lemma ruling out the bad cases, so that every progression whose labels seldom repeat sees both colours often. A progression that keeps returning to the same labels must be nearly periodic. Long periods are balanced by the same random colouring; for short ones, a carefully chosen dilation removes the period, leaving a straight line in the second set of coordinates. Now flip colours at random, rarely, with one shared coin for each key: a box of coordinates together with a band of squared distance from the centre, the geometry of Behrend’s construction. A straight line crosses such a band in at most two short pieces, so a key repeats at most four times along a progression. A progression rich in both colours would need many rare flips at once; straight ones have few possible shapes, and each would need many coins to cooperate. Both failure probabilities are below one half, so a good choice exists. Balancing the first against the number of progressions is what forces c to be small: below 1/16,000, so 1/100,000 is safe. To reach more colours, write the numbers in base N and colour each by the list of its digits’ colours. The step of a progression has a lowest nonzero digit, and in that place the numbers’ digits run through a progression in the cyclic group, which is never one colour. So 2^m colours reach length N^m; with m the whole part of log base two of r, that gives the main bound. In our small example, a two-colouring of the integers modulo 11 with no one-coloured four-term progression, lifted this way, gives sixteen colours on 14,641 numbers with none, by brute force.

5:38Where it stands

The paper is not peer reviewed and has not been revised. OpenAI’s Lean formalization states exactly the main theorem, with c equal to 1/100,000 and every number of colours from two up, in 115 files and about 15,000 lines. We found no unproved steps, and we have not rebuilt it. The threshold is shown to exist but not computed, and the formal proof uses weaker intermediate counts than the paper. The paper is not among those OSVerify reviewed, and we have seen no expert review; we also could not check the 2026 papers it cites. If it holds, two colours already make van der Waerden numbers outgrow every exponential, though the proven margin grows at a glacial rate.

Spot a mistake?

This episode simplifies on purpose, but it shouldn’t be wrong. If something is, open an issue on GitHub or leave a comment on YouTube. Corrections are noted here with a date.