🔢 mathematics

Three-color van der Waerden numbers grow super-exponentially

This paper establishes that the three-color van der Waerden number $w(k;3)$ grows super-exponentially by constructing a three-coloring of integers up to $2^{k (\log^* k)/4}$ free of monochromatic $k$ -term arithmetic progressions, while also providing a new lower bound that resolves a longstanding problem of Erdős and Graham regarding canonical van der Waerden numbers.

Original authors: Jacob Fox, Zach Hunter

Published 2026-06-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jacob Fox, Zach Hunter

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a very long line of numbered tiles, from 1 up to some huge number $N$ . You want to paint each tile with one of three colors (let's say Red, Blue, and Green).

The big question mathematicians have been asking for nearly a century is: How long does the line have to be before you are forced to create a "monochromatic arithmetic progression"?

An arithmetic progression is just a sequence of numbers that go up by the same amount, like 5, 10, 15, 20. If you paint 5, 10, 15, and 20 all Red, you've made a "monochromatic" (all one color) progression.

The number $w(k; 3)$ is the length of the line where, no matter how cleverly you paint it, you cannot avoid creating a sequence of $k$ tiles in a row (with equal spacing) that are all the same color.

The Old Mystery

For a long time, mathematicians knew these numbers existed, but they didn't know how fast they grew as $k$ got bigger.

Some thought the numbers grew like a standard exponential function (like $2^k$ ).
Others, including the famous mathematician Paul Erdős, guessed that for three or more colors, the numbers grow super-exponentially. This means they grow so fast they dwarf even the most powerful exponential functions. It's like comparing a snail to a rocket that accelerates faster than light.

Erdős offered a $500 prize to anyone who could prove this super-exponential growth for three colors.

The New Discovery

In this paper, Jacob Fox and Zach Hunter finally prove that Erdős was right.

They show that for three colors, the line of tiles needs to be astronomically long before you are forced to make a monochromatic sequence. Specifically, they prove the number is larger than $2^{k(\log^* k)/4}$ .

To understand how big this is, imagine the "iterated logarithm" ( $\log^* k$ ). This is a number that grows so slowly it's almost flat. Even for a number as huge as the number of atoms in the universe, $\log^* k$ is only about 5.

The Analogy: If standard exponential growth is like a rabbit population doubling every day, this new result is like a rabbit population that doubles, then the speed of the doubling doubles, then the speed of that speed doubles, and so on, but only after you wait for a number that barely changes. The result is a number so massive it defies imagination.

How Did They Do It? (The Magic Tricks)

The authors didn't just guess; they built a "construction" (a specific way of painting the tiles) that avoids the pattern for as long as possible. They used a few clever mathematical tricks:

The "Sparse Net" (Finding the Holes):
First, they found a way to pick a huge group of numbers that are very "dense" (packed together) but somehow avoid forming arithmetic progressions. Think of it like a fishing net with very large holes. You can catch a lot of fish (numbers), but the holes are arranged so perfectly that you never catch a specific pattern of fish swimming in a straight line.
The "Random Shift" (The Shuffle):
They took two of these special groups and combined them. But instead of just stacking them, they used a "random shift." Imagine you have two decks of cards. You shuffle one deck, then slide it slightly over the other deck. This random movement breaks up any patterns that might have formed if you just stacked them neatly.
The "Ladder" (Iterating the Process):
The real magic is that they can repeat this shuffling and combining process over and over.
- Start with a small group.
- Shuffle and combine to get a bigger group that still avoids the pattern.
- Do it again to get an even bigger group.
- They can do this roughly $\log^* k$ times.

Because they can repeat this process so many times, the final number of tiles they can paint without making a pattern becomes incredibly huge.

The Bonus: Solving an Old Puzzle

While proving this for three colors, they also solved a related puzzle posed by Erdős and Graham about "Canonical" van der Waerden numbers.

In this version, you aren't just looking for a sequence of one color. You are looking for a sequence that is either all one color OR all different colors (like Red, Blue, Green, Red, Blue, Green... wait, no, just all distinct colors).

The Result: They proved that the number of tiles needed to force this pattern is also super-huge. It grows faster than any simple power of $k$ . This settles a decades-old question about whether these numbers grow fast enough to be considered "super-exponential."

Summary

The Problem: How long is the line of numbers before you must see a straight-line pattern of the same color?
The Answer: For three colors, the line must be unimaginably long. It grows much faster than anyone previously proved.
The Method: They built a mathematical "shield" using random shuffles and layered combinations that keeps the patterns away for a record-breaking amount of time.
The Impact: This confirms a famous guess by Paul Erdős and closes a major chapter in the history of combinatorics.

Technical Summary: Three-color van der Waerden numbers grow super-exponentially

Problem Statement
The paper addresses the growth rate of van der Waerden numbers, denoted $w(k; r)$ . This number is defined as the minimum integer $N$ such that every $r$ -coloring of the set $\{1, 2, \dots, N\}$ contains a monochromatic arithmetic progression of length $k$ . While the existence of these numbers is guaranteed by van der Waerden's theorem, their precise asymptotic growth remains a fundamental open problem.

Historically, the growth of $w(k; r)$ has been a subject of intense speculation. For fixed $r$ , it was conjectured by Erdős that $w(k; 2)$ grows super-exponentially (i.e., $\limsup_{k \to \infty} w(k; 2)^{1/k} = \infty$ ). Conversely, other conjectures suggested linear exponential growth, specifically $\lim_{k \to \infty} w(k; r)^{1/k} = r$ . Prior to this work, the best known lower bounds for $w(k; r)$ were largely derived from the Lovász Local Lemma or specific algebraic constructions, yielding bounds of the form $w(k; r) \geq r^{k-1}/(4k)$ or, for fixed $r \geq 5$ , bounds of the form $(3r/3)^{(1-o(1))k}$ . The authors note that while a previous result by Hunter [20] disproved the linear exponential conjecture for $r \geq 5$ , the case for $r=3$ (and the general behavior for small fixed $r$ ) remained unresolved.

Methodology
The authors develop a novel probabilistic construction to establish lower bounds for $w(k; r)$ . The methodology relies on three primary components:

Dense Progression-Free Sets in Cyclic Groups:
The authors construct very dense subsets of cyclic groups $\mathbb{Z}_N$ that contain no $k$ -term arithmetic progressions (k-APs). They utilize an extension of the Erdős-Turán construction (sets of integers with no digit equal to $p-1$ in base $p$ ) adapted to cyclic groups. Crucially, they prove the existence of "hitting sets" (Lemma 2.8) that are sparse (density $\leq \epsilon$ ) yet intersect every $k$ -AP in a cyclic group with a constant fraction of its elements. This is achieved by selecting random congruence classes modulo a set of primes.
Lovász Local Lemma (LLL) Consequences:
The paper employs the symmetric version of the Lovász Local Lemma to demonstrate the existence of colorings where no color class contains a "large" fraction of any $k$ -AP. Specifically, Corollary 3.3 establishes that for groups of order $N$ with no small prime factors, one can assign subsets of colors to vertices such that no $k$ -AP is monochromatic or nearly monochromatic.
Random Shifted Product Constructions:
The core technical innovation is a refined "random shifted product" construction (Lemmas 4.2 and 4.3). Unlike standard product colorings which multiply the number of colors, this method allows the authors to combine colorings of smaller groups into a larger group while keeping the number of colors fixed (or increasing them in a controlled manner).
- Mechanism: Given a coloring $c_1$ of $H_1$ and $c_2$ of $H_2$ , the construction defines a coloring on $H_1 \times H_2$ by independently shifting the fibers of the projection onto $H_2$ and permuting colors based on the color of the base element in $H_1$ .
- Iterative Process: The authors iterate this construction. In each step, they combine a coloring of a group $Z_{n_{j-1}}$ with a coloring of a cyclic group of prime order $Z_{q_j}$ . The construction increases the size of the group by a factor exponential in $k$ , while incurring a "double exponential" loss in the density parameter of the "good" color class. By carefully balancing these parameters, the process can be iterated roughly $(\log^* k)/2$ times.

Key Contributions and Results

Super-exponential Growth for Three Colors:
The primary result (Theorem 1) proves that for sufficiently large $k$ , the three-color van der Waerden number satisfies:
$w(k; 3) > 2^{k(\log^* k)/4}$
This establishes that $w(k; 3)$ grows faster than any exponential function of $k$ , thereby disproving the conjecture that $\lim_{k \to \infty} w(k; r)^{1/k} = r$ for $r \geq 3$ .
Lower Bounds for Many Colors:
Theorem 2 provides a lower bound for the regime where the number of colors $r$ is large relative to $k$ (specifically $r \geq (\log k)^{3/\epsilon}$ ):
$w(k; r) \geq r^{(1-\epsilon)k \log k}$
This improves upon previous bounds in the "many color" regime.
Resolution of the Erdős-Graham Problem:
The authors address the canonical van der Waerden number $H(k)$ , defined as the minimum $N$ such that every coloring of $[N]$ contains a monochromatic or rainbow $k$ -AP. Erdős and Graham conjectured whether $H(k)^{1/k}/k \to \infty$ . Using their improved lower bound on $w(k; k-1)$ , the authors prove (Theorem 3) that:
$H(k) \geq k^{(1-o(1))k \log k}$
This confirms that $H(k)$ grows super-exponentially, resolving the open problem posed by Erdős and Graham.

Significance
The paper claims that the growth of van der Waerden numbers for three or more colors is super-exponential, a result that fundamentally alters the understanding of these combinatorial numbers. The significance lies in:

Disproving the Linear Exponential Conjecture: It definitively shows that $w(k; r)$ does not behave like $r^k$ for $r \geq 3$ .
Methodological Advancement: The introduction of the "random shifted product" construction allows for the iteration of probabilistic arguments while maintaining a fixed number of colors, a technique the authors note is more efficient than previous versions used for $r \geq 5$ .
Canonical Ramsey Theory: The results provide a strong resolution to the Erdős-Graham problem regarding canonical van der Waerden numbers, showing that even when allowing for rainbow progressions, the required $N$ is vastly larger than previously established lower bounds.

The authors note that while their techniques are general, the specific application here focuses on establishing these lower bounds. They suggest that these constructions may be applicable to obtaining new bounds for other arithmetic Ramsey numbers, a topic they intend to explore in a companion note. The paper does not claim to determine the exact growth rate or provide upper bounds, but rather establishes a significantly stronger lower bound than previously known.