Superexponential growth of van der Waerden numbers

Source and verification

This article explains family 160 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Monochromatic arithmetic progressions

Let $W_r(k)$ be the least positive integer $N$ such that every coloring of $\{1,\dots ,N\}$ with at most $r$ colors contains a monochromatic arithmetic progression of length $k$ and positive common difference. Finiteness is the content of van der Waerden’s theorem. A lower bound requires constructing a coloring of a long interval that avoids such a progression.

Manuscript claim

There is an absolute threshold $K_0$ such that, for every $k\ge K_0$ and every $r\ge 2$,

$$W_r(k)>k^{10^{-5}k\lfloor {\log }_{2}r\rfloor }.$$

The threshold is independent of the number of colors. (OpenAI, 2026)

For each fixed $r\ge 2$, taking $k$th roots yields a lower bound tending to infinity. Thus the claimed growth is superexponential in $k$: it eventually exceeds $A^k$ for every fixed $A>1$. This is stronger than exceeding any particular exponential base.

The small cases have different behavior. Directly from the definition,

$$\begin{array}{c}{W}_1(k)=k,W_r(1)=1,\\ W_r(2)=r+1.\end{array}$$

The last identity is the pigeonhole principle, because any two distinct integers form a two-term progression. The large-$k$ hypothesis cannot simply be removed.

🏷️ Why random independent colors are insufficient

For a uniformly random two-coloring, a fixed $k$-term progression is monochromatic with probability $2^{1-k}$. There are at most $N^2$ candidate progressions in an interval of length $N$. A direct union bound therefore only reaches an exponential scale for $N$.

The manuscript introduces geometric dependence into the coloring. Integer positions are represented through several cyclic coordinates, schematically

$$\begin{array}{c}{x}_i(n)=\frac{n}{q^i}(\mathrm{mod}1),\\ y_i(n)=\lambda x_i(n),\end{array}$$

where $q$ is a prime power and the multiplication is on the circle. Boxes in the coordinate space give an initial coloring. A progression either already visits sufficiently different outer colors or has coordinate representatives with a rigid affine description.

The latter case is the one that needs additional randomization. Its advantage is that many progressions share a much smaller family of descriptions. The union bound is applied to these descriptions rather than directly to all progressions in the long interval.

🏷️ Short periods and anchor patterns

Small cyclic periods can cause a progression to revisit the same random data many times. The parameter $\lambda$ is chosen to absorb the relevant small prime-power factors. After this adjustment, the remaining return periods are either trivial or larger than a controlled threshold.

An anchor pattern records enough geometric information to describe the points of a progression relative to selected reference positions. The source bounds the number of such patterns by an expression of the form

$$(CDh{)}^{6D},$$

with $D$ the coordinate dimension and $h$ a controlled return parameter. Crucially, this count is uniform in the fine mesh, the multiplier, and the large cyclic modulus. Otherwise the enormous interval length would reappear in the counting estimate and destroy the advantage.

The construction adds random flips indexed by a box and by discretized quadratic information about its coordinates. Its geometric separation ensures that a progression encounters any one random key only a bounded number of times. Repeated visits therefore cannot make all the nominal random trials identical.

🏷️ The quantitative balance

Representative parameters in the argument are

$$D=\lceil k^{1/10}\rceil ,p=k^{-1/20},$$

where $p$ is the flip probability. The logarithm of the number of relevant descriptions is controlled at a scale $O(k^{9/10}\log k)$, whereas the useful number of random trials has scale $pk=k^{19/20}$. Since

$$\frac{k^{9/10}\log k}{k^{19/20}}=\frac{\log k}{k^{1/20}}⟶0,$$

the random failure estimates can beat the description count. The manuscript combines these bounds with local dependency control to obtain the two-color construction. A deterministic product construction then amplifies it to the factor $\lfloor {\log }_{2}r\rfloor$ in the exponent.

The numerical coefficient $10^{-5}$ is part of the stated theorem, not a fitted experimental constant. The proof does not claim it is optimal, and these notes do not construct or test a coloring at the very large threshold required by the theorem.

🏷️ Comparison with density upper bounds

If an $r$-coloring has no monochromatic $k$-term progression, its largest color class is a progression-free set of density at least $1/r$. The quantitative result in Arithmetic progressions and reciprocal sums therefore gives an upper bound at a quasipolynomial scale in $r$, for fixed $k$.

There is no conflict with the present lower bound. The two estimates concern different growth regimes, and the constants in the density upper bound can depend strongly on $k$. Keeping track of which parameter is fixed is indispensable when comparing Ramsey bounds.

🏷️ Key steps and proof outlines

A geometric key can occur only four times

The sparse perturbation uses one random bit per key, not one per integer. A key records a small coordinate box together with the integer part of a squared Euclidean norm. Reusing a bit is safe only if one key cannot control too many terms of a progression. The “Sparse perturbation” section proves a uniform four-occurrence bound. (OpenAI, 2026)

Inside a fixed box, the centered coordinate representatives of the relevant terms have an affine lift $A+jB$. After the source’s scaling, distinct progression terms have Euclidean distance at least one. This separation follows by taking the first nonzero base-$q$ digit of their difference; it requires that digit to be nonzero modulo $q$, not invertible modulo $q$.

Parametrize the resulting line as $z_0+te$, with $e$ a unit vector and $z_0\perp e$. Its squared norm is $\Vert z_0{\Vert }^2+t^2$. A norm band

$$m\le \Vert z_0{\Vert }^2+t^2<m+1$$

occupies an interval of length at most one on each half-line $t\ge 0$ and $t\le 0$. Indeed, $(\sqrt{v}-\sqrt{u}{)}^2\le v-u$ for $0\le u\le v$. Each interval contains at most two points separated by at least one. Hence at most four progression terms share the same box and norm band. This also explains the geometry behind the illustration: the line meets a thin spherical shell in two short pieces.

Two probability estimates pay for different families

Write $c_0$ for the already fixed outer coloring and set

$$C(n)=c_0(n)+E_{\kappa (n)}(\mathrm{mod}2),\mathbb{P}(E_{\kappa }=1)=p=k^{-1/20},$$

with independent bits for distinct keys. The structural dichotomy says that a progression either has at least $\gamma k$ terms of each outer color, with $\gamma =1/100$, or has a fully affine lift. These cases call for different counting arguments.

For a progression rich in both colors, becoming monochromatic in a specified color requires flips at at least $\gamma k/4$ distinct keys. Its probability is therefore at most $p^{\gamma k/4}$. If a repeated key simultaneously demands a flip and no flip, the event is impossible, which only helps. There are fewer than $N^2=q^{2D}$ progressions, so the total failure probability is at most

$$2q^{2D}{p}^{\gamma k/4}=o(1).$$

The manuscript checks the leading exponent explicitly: with its constant $c=10^{-5}$, the coefficient of $k\log k$ is $2c-\gamma /80<0$.

For affine progressions, that global union bound is too expensive. Instead, record the literal word of outer colors and key identities. Two equal words prescribe exactly the same random bits and define the same bad event. The squared norms along an affine lift form a quadratic polynomial ${\theta }_0+{\theta }_{1}j+{\theta }_2{j}^2$. Comparing its values with integer thresholds is a hyperplane-arrangement problem in only three coefficient variables. Combined with the source’s box-word count, it gives a number $T_{\mathrm{aff}}$ of signatures satisfying

$$\log T_{\mathrm{aff}}=O(k^{9/10}\log k)=o(pk).$$

Every signature uses at least $k/4$ keys. Any consistent prescription has probability at most $(1-p{)}^{k/4}$, since $p<1/2$. Thus

$$2T_{\mathrm{aff}}(1-p{)}^{k/4}\le \exp (-pk/4+o(pk))=o(1).$$

Neither union bound assumes independence between progressions. Their combined failure probability is below one, proving the existence of a successful coloring.

The digit transfer preserves the progression length

Suppose the resulting cyclic two-coloring works on $\mathbb{Z}/N\mathbb{Z}$. Write an integer $0\le n<N^m$ in base $N$ and color it by the vector of its $m$ digit colors. This uses $2^m$ colors.

Proof outline. If $a,a+d,\dots ,a+(k-1)d$ were monochromatic, choose the largest $i$ for which $N^i\mid d$, and write $d=N^{i}e$ with $N\nmid e$. Then

$$\lfloor \frac{a+jd}{N^i}\rfloor =\lfloor \frac{a}{N^i}\rfloor +je.$$

Reducing modulo $N$ shows that the $i$th digits form a nonzero-step cyclic progression. Their common digit color contradicts the cyclic construction. The argument handles carries by choosing the first changing digit, and works for composite $N$. Taking $m=\lfloor {\log }_{2}r\rfloor$ proves the advertised many-color transfer with the same threshold on $k$. The separate norm-sphere construction in “Transfers” supplies the complementary large-$r$ regime; the two mechanisms address different parameter ranges.

See Also

• Off-diagonal Ramsey numbers also obtains a lower bound by controlling the descriptions of potential forbidden configurations.
• Hypercube Ramsey numbers treats a graph whose degree grows with its size, producing a different uniformity problem.

🏷️ Manuscripts and verification scope

• Quantitative Superexponential Bounds for van der Waerden Numbers — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The page selects the uniform lower bound, growth limits, finiteness, and boundary values; sharper intermediate estimates are outside its described scope. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. Quantitative Superexponential Bounds for van der Waerden Numbers.