How long can a coloring avoid a long arithmetic progression

← All digests

Family 160 · Combinatorics
Importance 4/5 · Provisional editorial rating
Sources consulted 2026-10-11

1. The question

Color the integers red or blue and try to avoid a long monochromatic arithmetic progression. For any fixed desired length, van der Waerden’s theorem says that this game must eventually fail. But “eventually” may require an enormous interval.

Family 160 asks how enormous it can be. Its manuscript claims that the interval needed to force a progression grows faster than every fixed exponential in the progression length, even with only two colors. It supplies a quantitative construction and extends it to every number of colors with one common lower threshold on the length.

This is a lower-bound problem: the source constructs colorings that delay the unavoidable pattern. It complements the density theorem in family 159, which provides conditions strong enough to force a pattern.

2. Background and essential definitions

For positive integers $r,k$, the van der Waerden number $W_r(k)$ is the smallest $N$ such that every coloring of $\{1,\ldots,N\}$ with at most $r$ colors contains a monochromatic progression

$$a,a+d,\ldots,a+(k-1)d,\qquad d\ge1.$$

“Monochromatic” means all terms receive the same color. If one produces a coloring of an interval of length $L$ with no such progression, then $W_r(k)>L$. Conversely, an upper bound must work against every coloring.

The small boundary cases are simple: $W_1(k)=k$, $W_r(1)=1$, and $W_r(2)=r+1$. For the last identity, any two equal-colored integers form a two-term progression, so the pigeonhole principle applies.

Which parameter grows

There are two different questions. One fixes $r$ and lets the length $k$ grow. The other fixes $k$ and increases the available colors $r$. Bounds for one regime need not describe the other.

For fixed $r$, superexponential growth in length means

$$W_r(k)^{1/k}\longrightarrow\infty.$$

Equivalently, $W_r(k)$ eventually exceeds $B^k$ for every fixed base $B>1$. This is stronger than $W_2(k)/2^k\to\infty$: the sequence $k2^k$ satisfies that ratio condition but still has $k$-th root tending to two.

Throughout the displayed bounds, $\log$ denotes the natural logarithm, while $\log_2$ has base two. The floor $\lfloor x\rfloor$ is the greatest integer at most $x$.

3. Development history and previous partial results

Van der Waerden’s 1927 theorem established finiteness, without giving a realistic picture of the numbers’ size. Later constructions sought long intervals that still avoid monochromatic progressions, while quantitative proofs of finiteness supplied upper bounds.

Berlekamp’s 1968 algebraic construction gave

$$W_2(p+1)>p2^p$$

when $p$ is prime. Probabilistic methods, particularly the Lovász local lemma, supplied other exponential lower bounds. These demonstrated that unavoidable patterns can be postponed far beyond naive small examples.

Recent developments clarified two distinct questions of Erdős. Fox and Hunter’s 2026 paper established superexponential growth for three colors. Their bound uses the very slowly growing iterated logarithm, the number of logarithms needed to reduce a quantity to at most one. They also obtained strong multicolor bounds when the number of colors is sufficiently large relative to the progression length.

Campos, Fox and Schildkraut proved $W_2(k)\ge(1-o(1))k2^{k-1}$, extending a Berlekamp-scale bound to all lengths. This settles divergence of $W_2(k)/2^k$, but it does not establish the stronger unbounded-root limit. Here $o(1)$ denotes a quantity tending to zero as $k$ grows.

The new claim’s key contribution is the full superexponential conclusion for two colors, with an explicit $k\log k$ scale in the logarithm. Its uniformity also matters: the threshold for $k$ does not worsen when the number of colors changes. It is not presented as beating every earlier multicolor bound in every possible regime.

4. What the new manuscripts claim

M1’s Theorem 1.1 gives an absolute integer $K_0$ such that, for every $k\ge K_0$ and every $r\ge2$,

$$W_r(k)>k^{c k\lfloor\log_2r\rfloor}, \qquad c=10^{-5}.$$

For two colors this is $W_2(k)>k^{ck}$, whose $k$-th root is $k^c$ and tends to infinity. The small numerical exponent does not change that asymptotic conclusion.

The same manuscript also treats increasing color counts. For every $r\ge256$ and $k\ge3$, it asserts

$$W_r(k)>\exp\!\left(\frac{(\log r)^2}{64\log2}\right).$$

This lower bound is uniform in the progression length and grows faster than any fixed power of $r$.

Combining that construction with the separate upper bound in family 159 gives, for fixed $k\ge3$, constants $A_k$ such that

$$W_r(k)\le \left\lceil\exp\bigl(A_k(2+\log r)^{A_k}\bigr)\right\rceil.$$

Thus the stated fixed-length growth is superpolynomial but at most quasipolynomial in the number of colors. The upper bound here uses the companion manuscript; it is not an independent consequence of M1’s lower-bound construction.

5. Why the advance matters

Importance: 4/5. The claimed two-color theorem would settle a longstanding quantitative question in Ramsey theory. Finiteness alone leaves huge freedom in the growth rate; showing that every fixed exponential is eventually too small is a qualitative change within that quantitative problem.

The construction’s uniformity adds value. Many arguments work after fixing the number of colors and allow constants or thresholds to depend on that choice. Here a single two-color construction can be reused to cover all $r\ge2$.

The result is a major advance rather than a determination of the full growth rate. Large gaps between lower and upper estimates remain, and its explicit constant is not claimed to be optimal. The distinction from the earlier three-color theorem is essential to assessing what is new.

6. The main idea

Encode integers by coordinates on circles

The source first colors a finite cyclic group, where addition is performed modulo a large integer. It uses a group of order $q^D$, with the dimension $D$ growing slowly with $k$. An integer is represented by several circle coordinates obtained from fractions such as $n/q^i$ modulo one.

Each circle is divided into small intervals, so a point receives a finite coordinate label. A second coordinate system applies an integer dilation before recording labels. This dilation is chosen to eliminate small prime-power factors from troublesome short periods.

The goal is a useful alternative for every nonconstant cyclic progression: either its preliminary coloring contains substantial amounts of both colors, or its coordinates admit particularly regular affine representatives in ordinary Euclidean space. The latter means that wraparound has been controlled well enough to see a straight arithmetic pattern.

Use randomness at the right level

The source then makes rare random color flips. A flip is assigned to a key consisting of a coordinate box and an integer band for a squared Euclidean norm. Repeated occurrences of the same key always use the same flip.

A progression already rich in both colors can become monochromatic only through many unlikely flips. In the affine alternative, the squared norm varies quadratically along the progression. This supplies many distinct constraints on flip variables and gives a different small-probability estimate.

The difficult counting issue is that the dimension grows. It is not enough to say there are finitely many possible patterns with a constant depending arbitrarily on dimension. The manuscript obtains explicit pattern counts strong enough to compare with the small probabilities. It groups progressions sharing the same relevant word so they describe the same bad event.

Together these estimates give a two-color cyclic coloring with no forbidden progression and with group order at least $k^{ck}$.

Reuse the two-color construction digit by digit

To obtain more colors, write integers in base $N$, where $N$ is the size of the cyclic construction, and color each digit using the same two-color rule. A tuple of $m$ binary colors gives at most $2^m$ colors on an interval of length $N^m$.

The least digit at which the progression’s step is nonzero supplies a nonconstant cyclic progression. If the original progression had one color tuple, this digit progression would violate the two-color construction. Taking $m=\lfloor\log_2r\rfloor$ gives the claimed dependence on $r$.

The separate fixed-length lower bound uses a related geometric idea: digit vectors with the same squared norm cannot form a nonconstant midpoint triple once carries are controlled. This is the sphere-based mechanism familiar from Behrend-type constructions.

7. Scope, limitations, and open questions

The main bound is asymptotic in $k$: the theorem supplies an absolute threshold, not a practical numerical estimate for small lengths. It does not compute particular van der Waerden numbers.

A universal lower bound can coexist with stronger bounds in special ranges. M1 explicitly notes earlier estimates that are stronger when $r$ grows sufficiently quickly with $k$. Its novelty includes uniform validity down to two colors.

The theorem does not show that $k^{\Theta(k)}$ is the exact two-color growth rate. An upper estimate of comparable form would require additional work. Likewise, the fixed-length inequalities do not determine the optimal power of $\log r$ in the exponent.

The coloring construction is probabilistic at an intermediate stage. Its existence conclusion should not be read as an efficient algorithm for producing a coloring at every stated size without the source’s further construction details.

8. Sources and further reading

M1’s Theorem 1.1 states the uniform superexponential bound. Sections 2–6 develop the cyclic construction, Proposition 7.1 gives the digit product, and Theorem 7.2 handles increasing color counts. Its comparison with family 159 appears in the introduction and Section 7.

The Fox–Hunter and Campos–Fox–Schildkraut papers linked above explain why the recent three-color and two-color milestones answer different questions. Wikipedia’s van der Waerden number is optional background for examples and conventions.

Source manuscripts

• M1. OpenAI, Quantitative Superexponential Bounds for van der Waerden Numbers (September 23, 2026).

Sources consulted on 11 October 2026 at repository revision fd4aeeb. Download the manuscript citations.