Superexponential van der Waerden numbers

1 · The essentials

Take a row of numbered positions and give each position one of several colors. Look for positions that all have the same color and are separated by equal steps. The question is how long the row must be before every possible coloring contains such a pattern of a specified length. The main result says that this required row length grows faster than any fixed number raised to the pattern length, as the pattern length increases. This holds even with just two colors. The manuscript also gives an explicit form of a lower bound that accounts for the number of colors, resolving the question attributed in the source to Erdős. The main result has a Lean formalization.

A picture to help (an imperfect image, not to be taken literally)

As an imperfect image, imagine painting fence posts and trying to avoid a chosen number of same-colored posts appearing at regular intervals. The result says that a row must become extraordinarily long before that pattern is unavoidable, regardless of how you paint it; the image is imperfect because the question concerns numbered positions rather than physical distances.

Why it matters

The result gives a quantitative positive resolution of Erdős's superexponential-growth question for van der Waerden numbers, including the two-color case. It provides not just a growth conclusion but a lower bound valid for every number of colors at least two, with a common threshold for the pattern length.

2 · Going further

The van der Waerden number $W_{r} (k)$ is the least interval length such that every coloring of its positions with $r$ colors contains a monochromatic $k$ -term arithmetic progression. The precise result is that there are absolute constants $c > 0$ and $K_{0}$ such that $W_{r} (k) > k^{c k ⌊ l o g_{2} r ⌋}$ for every $k \geq K_{0}$ and every $r \geq 2$ . In particular, neither constant depends on the number of colors.

Taking $k$ th roots gives $W_{r} (k)^{1/ k} > k^{c ⌊ l o g_{2} r ⌋}$ . For each fixed $r \geq 2$ , the exponent on the right is positive, so $W_{r} (k)^{1/ k} \to \infty$ . This is the superexponential-growth conclusion: no fixed exponential base captures the growth. The source identifies it as a quantitative positive resolution of Erdős's question, including for two colors.

The supplied abstract states the bound and its consequence but does not describe the construction or argument establishing the bound. Thus the step from the bound to superexponential growth can be explained here, but the underlying proof strategy cannot be reconstructed from this source. Only the main manuscript, “Quantitative Superexponential Bounds for van der Waerden Numbers,” is supplied; it is marked Lean-formalized, and no companion manuscripts are described.

Useful notions

Colorings of numbered intervals
Equally spaced sequences
Exponential growth and limits
Logarithms and the floor function

What was known before / what is new

Before

The source identifies superexponential growth of van der Waerden numbers as a question posed by Erdős. It does not supply earlier quantitative bounds or describe previous approaches.

New

The main result supplies the lower bound $W_{r} (k) > k^{c k ⌊ l o g_{2} r ⌋}$ with absolute constants and a threshold in $k$ uniform over all $r \geq 2$ . It yields superexponential growth for each fixed number of colors, including two. The main result has a Lean formalization.

Limits and assumptions

The bound requires integer numbers of colors $r \geq 2$ and pattern lengths $k \geq K_{0}$ ; the source gives no numerical values for $c$ or $K_{0}$ . It is a lower bound, not an exact value or a matching upper bound. The main result is identified as Lean-formalized, but the supplied text gives no further breakdown of the formalization's scope. It supplies neither the proof method nor additional remaining open questions.

Mini glossary

Arithmetic progression: A sequence of numbers with the same difference between each pair of consecutive terms.
Monochromatic: Having all selected positions assigned the same color.
Van der Waerden number: $W_{r} (k)$ is the least interval length forcing a same-colored arithmetic progression of length $k$ in every coloring with $r$ colors.
Superexponential growth: Here this means $W_{r} (k)^{1/ k} \to \infty$ for fixed $r$ , so the growth eventually exceeds any fixed-base exponential.
Floor function: $⌊ x ⌋$ is the greatest integer less than or equal to $x$ .
Absolute constants: The constants $c$ and $K_{0}$ are fixed independently of both $r$ and $k$ .

Keywords : van der Waerden numbers · superexponential growth · monochromatic progressions

AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.

3 · Technical details and sources

Claim made in the manuscript (source text)

Resolves Erdős's superexponential-growth question for van der Waerden numbers. If $W_{r} (k)$ is the least interval length forcing a monochromatic k-term progression in every r-coloring, then $W_{r} (k) > k^{c k ⌊ l o g_{2} r ⌋}$ for an absolute c > 0, all r ≥ 2 and sufficiently large k, uniformly in r. In particular, $W_{r} (k)^{1/ k} \to \infty$ for each fixed r.

Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.

Scope of the Lean formalization (source text)

…

lean/docs/160.md

Manuscripts in this family

★

Quantitative Superexponential Bounds for van der Waerden Numbers

23/09/2026

Verified by Lean

We prove that there are absolute constants c > 0 and K₀ such that $W_{r} (k) > k^{c k ⌊ l o g_{2} r ⌋}$ for every $k \geq K_{0}$ and r ≥ 2. Consequently $W_{r} (k)^{1/ k} \to \infty$ for each fixed r ≥ 2, giving a quantitative positive resolution of Erdős's superexponential-growth question, including the two-color case.

PDF GitHub folder Lean formalization