In September 2026, OpenAI released a preprint (OpenAI 2026) claiming to resolve a long-standing problem of Erdős concerning the growth of van der Waerden numbers. The result establishes that these numbers grow faster than any exponential function, even when only two colors are allowed. The preprint also gives a quantitative lower bound, uniform in the number of colors.
Let us recall the problem. One of the fundamental principles of Ramsey theory is that sufficiently large mathematical structures necessarily contain certain regular patterns, no matter how their elements are colored.
For example, in 1916, Schur (Schur 1916) proved that if we color all positive integers using finitely many colors, then there must exist three positive integers of the same color satisfying
In 1927, van der Waerden (van der Waerden 1927) proved another remarkable theorem of this kind. An arithmetic progression of length is a sequence where and are positive integers. A progression is called monochromatic if all its terms have the same color.
Van der Waerden proved that, for any positive integers and , there exists an integer such that every coloring of with colors contains a monochromatic arithmetic progression of length .
The smallest such is denoted by and called the van der Waerden number.
For example, The first equality means that it is possible to color the integers red and blue without creating a monochromatic three-term arithmetic progression, but this becomes impossible if we include the integer .
Van der Waerden’s theorem guarantees that is finite for every and , but it says little about how rapidly these numbers grow.
This leads to a natural question: if we fix the number of colors , how fast does grow as the progression length tends to infinity?
The upper bounds obtained from the classical proofs are enormous. Even the much stronger results following from Gowers’s proof of Szemerédi’s theorem (Gowers 2001) give upper bounds involving several iterated exponentials.
The lower bounds are considerably more difficult to improve. In particular, for a long time it was unknown whether grows faster than every exponential function , where is a fixed constant.
This question was explicitly raised by Erdős (Erdős 1980). More precisely, he asked whether This is equivalent to saying that, for every fixed , we have for all sufficiently large .
Progress towards this problem accelerated dramatically in 2026.
First, Fox and Hunter (Fox and Hunter 2026) proved that Their result established superexponential growth for three colors and, consequently, for every fixed number of colors . However, the two-color case remained open.
Later in 2026, Campos, Fox, and Schildkraut (Campos et al. 2026) proved that Here denotes a quantity tending to zero as . This established another conjecture of Erdős. Nevertheless, the lower bound is still exponential in , multiplied by a polynomial factor, and therefore does not imply superexponential growth.
The new OpenAI preprint (OpenAI 2026) claims to settle the remaining case, and in fact proves a stronger uniform statement.
Taking , we obtain Consequently, which answers Erdős’s question affirmatively.
Notice that the same estimate applies simultaneously to every number of colors . In particular, the threshold does not depend on . Moreover, increasing the number of colors strengthens the lower bound through the factor .
What does the theorem tell us in terms of colorings? To prove that , one must construct a red-blue coloring of containing no monochromatic arithmetic progression of length . The theorem asserts that such a coloring exists even when is as large as .
Let us briefly discuss the proof. The authors begin by constructing a two-coloring of a large cyclic set of integers, where arithmetic is performed modulo a fixed integer . The construction is geometric: integers are represented using several coordinates on circles, and their colors depend on which small intervals contain these coordinates.
The main innovation is to introduce carefully chosen random modifications of this preliminary coloring. The modifications depend partly on sums of squares of the coordinates, an idea related to classical geometric constructions of sets without arithmetic progressions.
The authors show that every sufficiently long arithmetic progression either already contains both colors or is extremely unlikely to become monochromatic after the random modifications. By carefully counting the possible patterns, they prove that there exists a coloring avoiding all monochromatic progressions of the prescribed length.
The extension from two colors to an arbitrary number of colors uses an elegant idea involving the digits of integers. Suppose we have a suitable two-coloring of the integers modulo . We may then write integers in base and color each digit separately. The resulting sequence of digit colors gives a coloring with colors on an interval of length .
If this coloring contained a monochromatic arithmetic progression, then considering the first digit position at which its common difference is nonzero would produce a forbidden monochromatic progression in the original two-coloring. This construction explains the factor in the theorem.
The proof therefore combines geometry, probability, and a simple arithmetic construction. Although the initial coloring uses random choices, the theorem itself is a statement about the existence of a coloring with the required properties.
The OpenAI repository also reports a formalization of the main lower bound in Lean. The work is currently presented as a preprint, and independent mathematical verification remains important.
We have previously discussed arithmetic progressions in connection with the multidimensional Szemerédi theorem. Both subjects illustrate a central theme of combinatorics: large sets or colorings inevitably contain regular patterns. However, van der Waerden numbers measure just how far we can postpone the appearance of these patterns by choosing the coloring carefully.
If the new proof is confirmed, it will settle a question that has remained open for decades. Even with only two colors, we can avoid monochromatic arithmetic progressions of length on intervals whose length grows faster than every fixed exponential in . At the same time, the enormous gap between the known upper and lower bounds shows that the true growth rate of van der Waerden numbers is still far from understood.