# Quantitative Superexponential Bounds for van der Waerden Numbers

*An expository walkthrough, written to be read with high-school mathematics.*

---

## 0. The paper in one sentence

Color the numbers $1,2,\dots,N$ with $r$ colors. How large must $N$ be before
every coloring is forced to contain $k$ equally spaced numbers of one color?
That threshold is the van der Waerden number $W_r(k)$. The paper proves the
slogan:

> **For a fixed number of colors, van der Waerden numbers grow faster than
> exponentially: $W_r(k)^{1/k}\to\infty$ as the length $k$ grows.**

Concretely, there are absolute constants $K_0$ and $c=10^{-5}$ such that for
every integer $k\ge K_0$ and every integer $r\ge2$,

$$ W_r(k) > k^{c\,k\lfloor\log_2 r\rfloor}. $$

Read the exponent: a constant times $k$ times the number of binary digits of
$r$. So $W_r(k)$ is roughly "$k$ raised to a power proportional to $k$". That
is what "superexponential" means here: even after taking the $k$-th root, the
number still grows without bound.

Two features make this the right kind of statement. It is **uniform in the
number of colors** (the threshold $K_0$ does not depend on $r$), and it reaches
**two colors**, the hardest and most famous case. The paper is a research
paper; this document is a map of its entire proof, roughly ten times shorter.
Every step appears, each lemma is stated exactly, and each proof is paired with
the idea behind it -- without the pages of constant-chasing.

---

## 1. The question and the answer

### 1.1 Van der Waerden numbers

Write $[N]=\{1,2,\dots,N\}$. A **$k$-term arithmetic progression** ("progression"
for short) is a list

$$ a,\ a+d,\ a+2d,\ \dots,\ a+(k-1)d,\qquad a\ge1,\ d\ge1, $$

with all terms in $[N]$; $d$ is the step. Van der Waerden's theorem (1927) says
that if you color $[N]$ with $r$ colors and $N$ is large enough, some color
contains a whole $k$-term progression. The **van der Waerden number** $W_r(k)$
is the smallest such $N$:

$$ W_r(k) = \text{least } N \text{ such that every map } [N]\to[r] \text{ is
constant on some } k\text{-term progression}. $$

A map $[N]\to[r]$ is just an $r$-coloring (fewer than $r$ colors is allowed).
The real content is a **lower bound problem**: to prove $W_r(k)>N$ you must
exhibit a single $r$-coloring of $[N]$ with no monochromatic $k$-term
progression.

Three boundary values pin the definition down: $W_1(k)=k$ (one color, nothing
to avoid), $W_r(1)=1$ (a one-term progression is a single point), and
$W_r(2)=r+1$ (among $r+1$ points two share a color and form a 2-term
progression, while $r$ points can be colored injectively).

### 1.2 The result

**Main Theorem.** There is an absolute integer $K_0$ such that, for every
integer $k\ge K_0$ and every integer $r\ge2$,

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

In particular, for each fixed $r\ge2$,

$$ \lim_{k\to\infty} W_r(k)^{1/k} = \infty. $$

Paul Erdos, in his 1980 survey, explicitly asked whether the two-color numbers
satisfy this full limit. The theorem answers yes, and quantitatively. It is
strictly stronger than the older statement $W_2(k)/2^k\to\infty$: it makes the
$k$-th root diverge, not merely $W_2(k)$ beat a fixed multiple of $2^k$.

### 1.3 Where this sits among earlier bounds

Early lower bounds go back to Erdos-Rado (1952) and Schmidt (1962).
Berlekamp's algebraic construction gives $W_2(p+1)>p\,2^p$ for every prime $p$.
The Lovasz local lemma gave another route. Szabo (1990) proved
$W_2(k)\ge 2^k/k^{\varepsilon}$ for every fixed $\varepsilon>0$; Kozik-Shabanov
(2016) proved $W_r(k)\ge\beta\,r^{k-1}$ for an absolute $\beta>0$; Hunter (2025)
improved the exponential base for each fixed $r\ge5$, allowing the threshold to
depend on $r$.

The two closest recent results are Fox-Hunter and Campos-Fox-Schildkraut.
Fox-Hunter (2026) proved $W_3(k)>2^{k\log^* k/4}$ for large $k$, where $\log^*$
counts how many times you take the logarithm to get below $1$; that is
superexponential, but only for three colors and not quantitatively in $r$.
Campos-Fox-Schildkraut (2026) proved $W_2(k)\ge(1-o(1))\,k\,2^{k-1}$, which
settles the size of $W_2(k)/2^k$ but not the divergence of the $k$-th root. The
present theorem gives the full $k$-th-root divergence, uniformly in $r$ and down
to two colors. Fox-Hunter also prove $W_r(k)\ge r^{(1-\varepsilon)k\log k}$
when $k$ is large relative to $\varepsilon$ and $r\ge(\log k)^{3/\varepsilon}$;
the present bound holds uniformly down to $r=2$.

### 1.4 The other growth regime: many colors, short progressions

There is a second, different regime: fix the length $k$ and let the number of
colors $r$ grow. Behrend's and Rankin's dense progression-free sets, used to
cover an interval by translates, already give superpolynomial growth in $r$;
Kelley-Meka (2023) and Leng-Sah-Sawhney (2024) give the state of the art for
the relevant density bounds. Combining this with a companion paper shows that
for each fixed $k\ge3$,

$$ \exp\!\Big(\frac{(\log r)^2}{64\log 2}\Big) < W_r(k) \le
\Big\lceil \exp\big(A_k(2+\log r)^{A_k}\big)\Big\rceil \quad (r\ge256), $$

so growth in the number of colors is superpolynomial but at most
quasipolynomial. The paper proves the lower half directly (Theorem 8.2 below);
the upper half is borrowed from the companion paper.

---

## 2. The architecture of the proof

Here is the whole plan on one page. It is far easier to build a coloring of a
**finite cyclic group** first, and then convert it to a coloring of an interval.

**Step A (reduce to a cyclic coloring).** Build an integer $N$, roughly
$k^{ck}$, and a two-coloring $C:\mathbb Z/N\mathbb Z\to\{0,1\}$ in which no
cyclic progression $n_0,n_0+d,\dots,n_0+(k-1)d$ with nonzero step $d$ is
monochromatic. A **digit product** (Section 8) then turns $C$ into a coloring of
an interval with $2^m$ colors and no monochromatic progression, giving
$W_{2^m}(k)>N^m$; taking $m=\lfloor\log_2 r\rfloor$ handles $r$ colors at once,
because $N^m=k^{ck\,m}$.

**Step B (the cyclic construction).** This is where all the work is. Four
ingredients:

1. **Setup (Section 3).** Take the cyclic group $\mathbb Z/q^D\mathbb Z$ and two
   systems of "circle coordinates": a fine rational system $x(n)$ and a dilated
   system $y(n)=\lambda\,x(n)$. Cut each coordinate circle into small intervals;
   a point is labeled by the tuple of intervals it lands in.

2. **Outer coloring (Section 5).** Color every label (equivalently, every cluster
   of points sharing a label) either $0$ or $1$, using a probabilistic argument
   (the local lemma). The coloring is chosen so that every progression is either
   **balanced** (each color appears a positive fraction of the time) or
   **affine** (in the coarse coordinates the progression lies on a genuine
   straight line).

3. **Dichotomy (Section 6).** Prove that any progression which is not balanced
   must be affine. The engine is a closest-return, or "period", analysis: a
   heavily repeated label forces a small rational period; the dilation $\lambda$
   kills short periods, and longer periods give eligible blocks that the outer
   coloring balances.

4. **Perturbation (Section 7).** Attach an independent, rare random bit to each
   **key** (a coarse box together with an integer "norm band"). In a balanced
   progression, making it monochromatic forces many distinct keys to flip the
   same way, which is very unlikely; in an affine progression the keys are
   governed by a single quadratic polynomial, and a count of the possible
   signatures plus a union bound beats the small flip probability. Choosing the
   randomness completes the cyclic coloring.

**Step C (transfer).** Multiply the cyclic coloring into integer intervals
(Section 8), and prove the separate "growth in the number of colors" bound
(Section 8). An elementary recursive upper bound, plus a proof that $W_r(k)$ is
finite, appears in Section 9.

The rest of the document follows this order.

---

## 3. Setup: a cyclic group with two coordinate systems

Throughout the cyclic construction, $k$ is an integer larger than an absolute
threshold. Every constant hidden in an $O(\cdot)$ is absolute unless a subscript
says otherwise, and every limit is as $k\to\infty$. In particular, no threshold
depends on the eventual number of colors $r$. This is the whole reason the final
bound is uniform in $r$.

### 3.1 The parameters

Fix the numbers

$$ c=10^{-5},\quad \delta=\tfrac1{10},\quad \gamma=\tfrac1{100},\quad
D=\lceil k^{1/10}\rceil,\quad M=\lceil k^{1/2}\rceil, $$
$$ h_0=D^2,\quad p=k^{-1/20},\quad H=k^{-2},\quad \eta=\frac1{1000D}. $$

Take $k$ large enough that $h_0<2M<k$. Each parameter has a job:

- $D$ is the number of coordinates. It grows with $k$, but very slowly, like
  $k^{1/10}$. This slow growth is the heart of the quantitative problem: the
  argument must survive when the dimension grows with $k$, and no constant may
  depend arbitrarily on the dimension.
- $M=\lceil k^{1/2}\rceil$ is the largest "short period" the proof treats
  explicitly.
- $h_0=D^2$ is the cutoff below which periods count as "short"; the dilation will
  eliminate them.
- $p$ is the tiny probability of a single random flip, used much later.
- $H=k^{-2}$ is a very small base mesh width; $\eta$ is a truncation scale near
  the representative cut.

### 3.2 The dilation and why it exists

Define the integer **dilation**

$$ \lambda=\prod_{\substack{\ell\le h_0\\ \ell\ \text{prime}}}
\ell^{\lfloor \log(2M)/\log \ell\rfloor}. $$

That is, for every small prime $\ell\le h_0$, include the largest power of
$\ell$ that is at most $2M$, and multiply them all together.

**Lemma 3.1 (dilation of short periods).** $\log\lambda\le h_0\log(2M)$. If
$1\le h\le 2M$, then every prime-power divisor of $h$ whose prime is at most
$h_0$ divides $\lambda$. Consequently $h\mid\lambda$ whenever $h\le h_0$, and
for every integer $t$ the number

$$ s=\frac{h}{\gcd(h,\lambda t)} $$

is either $1$ or greater than $h_0$.

**Idea of proof.** Each factor is at most $2M$ and there are at most $h_0$
factors, giving the size bound. If $\ell^a\mid h\le2M$ with $\ell\le h_0$, then
$a\le\lfloor\log(2M)/\log\ell\rfloor$, so the full $\ell$-power part of $h$
already appears in $\lambda$, hence in $\gcd(h,\lambda t)$. So every prime
divisor of $s$ is bigger than $h_0$.

What this buys: after multiplying the coordinates by $\lambda$, a short rational
motion either becomes a whole number of steps (it is "stationary": the point
wraps exactly) or it moves fast enough that its period has a large denominator.
There is no middle ground. This clean separation is what allows a clean local
test later.

### 3.3 A prime, and the group

**Lemma 3.2 (an elementary prime bound).** For all large $k$ there is a prime
$P$ with $k<P\le 2k^2$.

**Idea of proof.** Put $n=k^2$ and look at the central binomial coefficient
$\binom{2n}{n}$. Its $\ell$-adic valuation is
$\sum_{a\ge1}\lfloor 2n/\ell^a\rfloor-2\lfloor n/\ell^a\rfloor$, each summand
being $0$ or $1$, so $v_\ell\le\lfloor\log_\ell(2n)\rfloor$. If all prime
factors were at most $k$, then $\binom{2n}{n}\le(2n)^k$. But $\binom{2n}{n}$ is
the largest of the $2n+1$ binomial coefficients summing to $2^{2n}$, so
$\binom{2n}{n}\ge 4^n/(2n+1)$. Comparing logarithms, for $n=k^2$ the lower bound
$k^2\log4-\log(2k^2+1)$ eventually beats the upper bound $k\log(2k^2)$. So some
prime divisor exceeds $k$, and it is at most $2n$.

Choose such a prime $P$, and let $q$ be the least power of $P$ that is at least
$k^{ck/D}$. Minimality gives

$$ k^{ck/D}\le q\le 2k^2\,k^{ck/D},\qquad ck\log k\le D\log q\le ck\log
k+D\log(2k^2). $$

Since $h_0<k<P$ and $\gcd(\lambda,q)=1$, the dilation and the group modulus are
coprime. Set

$$ N=q^D,\qquad G=\mathbb Z/N\mathbb Z. $$

Because $q$ is a power of the prime $P>k$, every nonzero element of $G$ has order
at least $P>k$. So in any progression $n_j=n_0+jd$ with nonzero step $d$, the
$k$ terms are distinct: a $k$-term progression really has $k$ points.

### 3.4 The two coordinate systems

On the circle $\mathbb T=\mathbb R/\mathbb Z$ (points modulo one), define for
$1\le i\le D$

$$ x_i(n)=\frac{n}{q^i}\pmod 1,\qquad y_i(n)=\lambda\,x_i(n). $$

These are well defined on $G$ because $q^i\mid N$. Write
$x(n)=(x_1(n),\dots,x_D(n))$ and $y(n)=(y_1(n),\dots,y_D(n))$. Fix
representatives $\hat x(n)\in[0,1)^D$ and $\tilde y(n)\in[-1/2,1/2)^D$.

- The **first system** $x$ has denominators $q,q^2,\dots,q^D$. It is good at
  distinguishing residue classes of a rational period: two distinct residues look
  different in the first system.
- The **second system** $y=\lambda x$ is the dilated copy. Its mesh is finer near
  the representative cut (the point $1/2=-1/2$), and this is what lets us prove a
  *global affine lift* for the surviving progressions.

The cut distance is

$$ \rho(Y)=\operatorname{dist}_{\mathbb T}(Y,1/2), $$

so $0\le\rho\le1/2$, and $\rho$ changes by at most the circle distance (it is
$1$-Lipschitz).

### 3.5 Two meshes

**First mesh $U$.** The intervals $[aH_x,(a+1)H_x)$ for $0\le a<k^2\lambda$,
where $H_x=H/\lambda$. Since $H_x^{-1}=k^2\lambda$ is an integer, these exactly
partition $[0,1)$, and every one has the same width $H_x$.

**Second mesh $V$.** This one is finer near the cut. Put

$$ \alpha=q^{-(D+1)},\quad R=\log\!\Big(1+\frac1{2\alpha}\Big),\quad
m=\lceil k^2R\rceil,\quad a_\ell=\alpha\big(e^{\ell R/m}-1\big)\
(0\le\ell\le m). $$

The intervals of $V$ are

$$ [-1/2+a_\ell,\,-1/2+a_{\ell+1}) \quad\text{and}\quad
[1/2-a_{\ell+1},\,1/2-a_\ell),\qquad 0\le\ell<m. $$

Since $a_0=0$ and $a_m=1/2$, these $2m$ intervals partition the representative
interval $[-1/2,1/2)$. An interval sitting at distance $\rho$ from the cut has
width on the order of $H(\rho+\alpha)$, where $H=k^{-2}$: tiny near the cut
($\sim H\alpha$), ordinary elsewhere. This adaptive mesh is a scaled, modern
echo of the torus-annulus method of Behrend, Green and Wolf. The gain is control
exactly at the representative boundary, where an affine lift could otherwise
break.

### 3.6 Labels

For a circle point, $U(X)$ or $V(Y)$ denotes the interval label containing it
(half-open conventions as written above). The full **label** of a point $n\in G$
records every coordinate interval:

$$ \mathcal L=U^D\times V^D,\qquad
L(X,Y)=\big((U(X_i))_{i=1}^D,(V(Y_i))_{i=1}^D\big),\qquad L(n)=L(x(n),y(n)). $$

A label determines the interval itself, including its location on the circle, not
just its index. Two points share a label exactly when, in every coordinate, they
land in the same interval.

### 3.7 Three lemmas that make the mesh usable

**Lemma 3.3 (widths).** For every $I\in V$ and every $Y\in\overline I$,

$$ \tfrac14 H(\rho(Y)+\alpha)\le|I|\le 2H(\rho(Y)+\alpha)\le 2H, $$

and $|V|=2m=O(k^3\log k)$.

*Idea.* With $\theta=R/m\in[H/2,H]$ and $b=\alpha e^{\ell\theta}$, the ratio
$|I|/(\rho+\alpha)$ lies between $1-e^{-\theta}$ and $e^\theta-1$, which for
$0\le\theta\le1$ lie between $\theta/2$ and $2\theta$. The count uses
$R\le(D+1)\log q=O(k\log k)$.

**Lemma 3.4 (uniform neighborhoods).** For $I\in V$ let $w=|I|$ and
$N(I)=\{Y\in\mathbb T:\operatorname{dist}(Y,\overline I)\le w\}$. Every interval
$J\in V$ whose closure meets $N(I)$ satisfies $|J|\ge w/16$, and the arc $N(I)$
contains at most $49$ mesh endpoints.

*Idea.* Moving a distance $2w$ can shrink $\rho+\alpha$ only by a factor about
$2$, so a neighbor cannot be much finer than $I$; then a length-$3w$ arc holds at
most $49$ mesh borders, because borders are at least $w/16$ apart.

**Lemma 3.5 (local complexity after truncation).** Define the truncated label
$V_\eta(Y)=V(Y)$ if $\rho(Y)\ge\eta$ and $V_\eta(Y)=*$ if $\rho(Y)<\eta$, where
$*$ is a fresh symbol. On any arc of length at most $4H$, the map $V_\eta$ is
constant between at most $16004D$ breakpoints.

*Idea.* Away from the cut, mesh borders are at least $H\eta/4$ apart (width
lemma), so a $4H$ arc has at most $16/\eta+2$ borders; add the at most two
threshold points $\rho=\eta$, and $16/\eta+4=16000D+4\le16004D$.

These three lemmas are the only geometric facts used below. Everything is now in
place to start counting.

---

## 4. Counting words and local patterns

Every count in this section counts literal interval labels. The central idea:
even though there are $2D$ coordinates and $D$ grows with $k$, each scalar
coordinate can be counted using an arrangement of lines in just **two real
parameters** (a starting value and a step). This is what keeps the constants
absolute.

### 4.1 The arrangement lemma

**Lemma 4.1 (affine comparisons, including equality).** Let $s$ affine
hyperplanes in $\mathbb R^e$ be given, and for each record the sign in
$\{-,0,+\}$ of a defining affine function. The number of realized joint sign
vectors is at most

$$ \sum_{d=0}^{e}\binom{s}{d}\sum_{j=0}^{e-d}\binom{s}{j}\le
(e+1)^2(s+1)^e. $$

The same bound holds when the parameter space is restricted to any subset of
$\mathbb R^e$.

*Idea.* Strict sign vectors correspond to regions of an arrangement: the
complement of $s$ hyperplanes has at most $\sum_{j=0}^e\binom{s}{j}$ regions
(each new hyperplane splits existing regions according to a lower-dimensional
arrangement; plus Pascal's identity). A strict sign set is convex, hence
connected, so it is one region. For a sign vector with zeros: if the zero
hyperplanes cut out a set of codimension $d$, then $d$ of those equations with
independent normals already determine it, an at most $\binom{s}{d}$ choice; the
remaining hyperplanes impose strict signs in dimension $e-d$. Summing over $d$
gives the first bound; each summand is at most $(s+1)^e$ and there are at most
$(e+1)^2$ of them. Restricting the parameter space can only remove sign vectors.

### 4.2 Global label words

**Lemma 4.2 (global label words).** Let $T_{\mathrm{glob}}$ be the number of
words $\big(L(n_j)\big)_{0\le j<k}$ arising from the cyclic progressions. Then

$$ \log T_{\mathrm{glob}}=O\big(D(\log k+\log\lambda)\big)
=O\big(k^{3/10}\log k\big)=o(M). $$

*Idea.* Take one circle partition with $F$ endpoints, plus its representative
cut. A scalar coordinate of a progression is $a+jb$ for a free start
$a\in[0,1)$ and step $b\in[0,1)$. For $0\le j<k$ the unreduced value $a+jb$ lies
in $[0,k)$. To read off the interval containing $(a+jb)\bmod1$, compare it with
every endpoint $\tau+z$ for $-1\le z\le k$. This uses at most $3k^2F$ lines in
the two variables $(a,b)$, so by Lemma 4.1 the number of scalar words is at most
$9(3k^2F+1)^2$. Apply this separately in all $2D$ scalar coordinates, letting
their starts and steps vary independently: this only enlarges the set of possible
words, so it is still an upper bound. Now

$$ F=|U|+|V|=k^2\lambda+O(k^3\log k),\qquad \log F=O(\log k+\log\lambda), $$

so $T_{\mathrm{glob}}\le[9(3k^2F+1)^2]^{2D}$. Taking logs and using
$M=\lceil k^{1/2}\rceil$ gives the stated bounds.

### 4.3 Eligible local patterns

Global words count entire progressions. For the outer-coloring argument we need a
*local* count: how many different short-block patterns can pass through one fixed
label. Fix an integer $h$ with $h_0<h\le2M$ and a vector
$t\in\{0,\dots,h-1\}^D$. In coordinate $i$ let

$$ s_i=\frac{h}{\gcd(h,\lambda t_i)}. $$

Call coordinate $i$ **stationary** if $s_i=1$ and **rotating** otherwise. By
Lemma 3.1 a rotating coordinate has $s_i>h_0$. These labels depend only on $h$
and $t$. Note that "stationary" is about the *rational step*; it allows a nonzero
drift, and a period $h>h_0$ may still have only stationary coordinates.

Now enlarge slightly to a family of full return-period blocks whose labels can be
balanced before the outer coloring is even chosen.

**Definition 4.3 (eligible local patterns).** Choose $x,y\in\mathbb T^D$ and
$u,v\in\mathbb R^D$, and form

$$ X_z=x+\frac z h(t+u),\qquad Y_z=y+\frac z h(\lambda t+v)\qquad(0\le z<h)
\quad\text{in }\mathbb T^D. $$

A position $z$ is **regular** if $\rho(Y_{z,i})\ge\eta$ in every rotating
coordinate; if there are no rotating coordinates, every position is regular.
Record $L(X_z,Y_z)$ at a regular position and a dummy symbol $*$ otherwise. The
resulting word in $(\mathcal L\cup\{*\})^h$ is **eligible for $h,t$** if it has a
realization satisfying all of:

1. At least $h/2$ positions are regular, and the full labels at those positions
   are pairwise distinct.
2. $|u_i|\le H_x$ for every $i$, and $|v_i|\le H$ in every rotating coordinate.
3. In every stationary coordinate $i$, $|v_i|\le|V(Y_{z,i})|$ at every regular
   position $z$.

The recorded word is the pattern; different realizations of one word do not
create additional patterns. Condition 3 measures the drift relative to the
interval width, because stationary intervals can be arbitrarily fine.

**Lemma 4.4 (local patterns through a specified label).** There is an absolute
constant $C$ such that, for every $h_0<h\le2M$ and every full label
$\beta\in\mathcal L$, the number of pairs $(t,\text{eligible pattern for }h,t
\text{ containing }\beta)$ is at most

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

with $C$ independent of $q,\lambda,\beta,D$.

*Idea of proof.* Fix $t$ and a position $z_0$ where the pattern equals $\beta$
(it is regular). In each scalar coordinate, re-anchor the path at $z_0$: let $a$
be the real value there, and $b$ the drift variable ($u_i$ or $v_i$). At a target
position $z$ the unreduced value is $a+\tau_z+\frac{z-z_0}{h}b$, where
$\tau_z=\frac{(z-z_0)t_i}{h}$ or $\frac{(z-z_0)\lambda t_i}{h}$. The translation
$\tau_z$ is fixed once $t,z_0,z,i$ are fixed, so it introduces no factor. Then
split into three cases:

- **First-system coordinate.** $a$ ranges over an interval of length $H_x$ and
  $|b|\le H_x$, so the target range lies in a fixed real interval of length at
  most $3H_x$. The real lifts of $U$-endpoints form a lattice of spacing $H_x$,
  so at most four endpoints appear.
- **Stationary second-system coordinate.** Write $I=V(Y_{z_0,i})$. The drift
  bound is $|b|\le|I|$. Since $\lambda t_i/h$ is integral, $\tau_z$ is integral,
  so modulo one every target lies in the neighborhood $N(I)$, which has at most
  $49$ mesh endpoints. The unreduced target range has length at most $3|I|<1$, so
  each circle endpoint lifts at most once.
- **Rotating second-system coordinate.** The anchor interval has width at most
  $2H$, the drift bound is $|b|\le H$, and the target range has length at most
  $4H<1$. By the truncation lemma, at most $16004D$ breakpoints determine the
  truncated output $V_\eta$, and each lifts at most once.

In every case, each comparison with a breakpoint is an affine line in $(a,b)$,
and there are at most $16004Dh$ of them per coordinate. By Lemma 4.1 with $e=2$,
the number of scalar output sequences is at most $9(16004Dh+1)^2\le C_0(Dh)^2$.
Multiplying over the $2D$ coordinates (truncating only rotating ones) determines
the whole recorded pattern. Finally there are $h^D$ choices of $t$ and at most
$h$ choices of $z_0$, so the count is at most

$$ h^{D+1}\big[C_0(Dh)^2\big]^{2D}=C_0^{2D}D^{4D}h^{5D+1}\le(CDh)^{6D}. $$

This is the estimate that makes the outer coloring possible: the number of bad
patterns through any one label is small enough to be overwhelmed by independent
coin flips.

---

## 5. An outer coloring of the labels

We now color the labels $\mathcal L$ themselves, before any randomness built into
the group is used. The goal: whatever the label of a point is, its outer color
should be balanced along progressions and along eligible patterns. Write
$c_*:\mathcal L\to\{0,1\}$ for this outer coloring; the actual coloring of a
point $n$ is the pullback $c_0(n)=c_*(L(n))$.

### 5.1 Light and heavy

Fix a cyclic progression. A full label is **light** if its multiplicity in the
progression is at most $k/M$, and **heavy** otherwise. A position has the same
designation as its label. These labels always refer to the whole progression,
even when we later examine a short block of its positions. The point: if almost
all positions are light, a random label coloring will spread two colors over
them; if some label is heavy, a rational period appears and the analysis of
Section 6 takes over.

### 5.2 The finite local lemma

**Lemma 5.1 (finite asymmetric local lemma).** Let $\mathcal E$ be a finite
family of events. Suppose a graph on $\mathcal E$, with neighbor sets
$\Gamma(E)$, has the property that each $E$ is independent of everything outside
$\{E\}\cup\Gamma(E)$. If numbers $z_E\in(0,1)$ satisfy

$$ \mathbb P(E)\le z_E\prod_{F\in\Gamma(E)}(1-z_F) \qquad (E\in\mathcal E), $$

then $\mathbb P(\bigcap_{E\in\mathcal E}E^c)>0$.

*Idea.* Prove simultaneously by induction on $|T|$ that $\mathbb P(A_T)>0$ and
$\mathbb P(E\mid A_T)\le z_E$ for $E\notin T$, where
$A_T=\bigcap_{F\in T}F^c$. Removing a neighbor and using the conditional bound
gives positivity; conditioning successively on neighbors, and using independence
from the rest, gives $\mathbb P(E\mid A_T)\le
\mathbb P(E)/\prod_{F\in T\cap\Gamma(E)}(1-z_F)\le z_E$. Taking $T=\mathcal E$
gives an outcome in which no event of $\mathcal E$ occurs.

### 5.3 The balanced outer coloring

**Proposition 5.2 (balanced outer coloring).** For all sufficiently large $k$
there is a map $c_*:\mathcal L\to\{0,1\}$ with the following properties.

1. In every cyclic progression having at least $\delta k$ light positions, each
   bit occurs on at least one quarter of its light positions when labels are
   colored by $c_*$.
2. In every eligible recorded pattern, each bit occurs on at least one quarter of
   its regular positions.

The threshold on $k$ is absolute.

*Idea of proof.* Give each label $\beta$ an independent uniform random bit
$\xi_\beta$. Build two finite families of bad events.

**First family: whole progressions.** For each distinct full-label word of a
cyclic progression with $L_0\ge\delta k$ light positions, let $w_{\max}$ be the
largest multiplicity of a light label. Group equal labels together and distribute
the light positions cyclically among $w_{\max}$ rows; then a label appears at
most once per row, and every row has at least

$$ \Big\lfloor\frac{L_0}{w_{\max}}\Big\rfloor\ge\delta M-1 $$

positions, because $w_{\max}\le k/M$. Each row's bad event is "some bit occurs on
strictly fewer than one quarter of its positions". There are at most
$k\,T_{\mathrm{glob}}$ such events.

**Second family: eligible patterns.** One event for each eligible recorded
pattern and its discrete parameters $h,t$ with $h_0<h\le2M$; its bad event is
"some bit occurs on strictly fewer than one quarter of the regular positions".
The tested labels are pairwise distinct (condition 1 of eligibility), and there
are at least $h/2$ of them. Both families are finite because $\mathcal L$, the
word lengths and the choices of $h,t$ are finite.

**Tail bound.** An event $E$ tests $l(E)$ distinct independent label bits. If
$X$ is the number of ones, then $\mathbb E e^{\pm(X-l/2)}=(\cosh(1/2))^l\le
e^{l/8}$ because $\cosh t\le e^{t^2/2}$. Markov at the two deviations from $l/2$
gives

$$ \mathbb P(E)\le \mathbb P(X-l/2\le -l/4)+\mathbb P(X-l/2\ge l/4)\le
2e^{-l(E)/8}. $$

This weak form also covers the strict inequalities, regardless of divisibility.

**Weights.** Give $E$ the weight $z_E=e^{-l(E)/32}$. The total weight of
first-family events is at most
$kT_{\mathrm{glob}}e^{-(\delta M-1)/32}=o(1)$. For a fixed label $\beta$, the
total second-family weight of events using $\xi_\beta$ is at most

$$ \sum_{h>D^2}(CDh)^{6D}e^{-h/64}=o(1), $$

because $\sup_{h>D^2}6D\log(CDh)/h\le 6\log(CD^3)/D=o(1)$, so each summand is at
most $e^{-h/128}$ for large $D$. Hence, uniformly over $\beta$,

$$ \sum_{E:\ \xi_\beta\text{ used by }E}z_E\le\frac1{500}. $$

**Applying the local lemma.** Join two events whenever their supports share a
label variable; since the label bits are independent, this is a valid dependency
graph. Summing the incident bound over the $l(E)$ labels of $E$ gives
$\sum_{F\in\Gamma(E)}z_F\le l(E)/500$. Since $l(E)\ge100$ eventually, $z_E<1/2$
and $\log(1-z)\ge-2z$, so

$$ z_E\prod_{F\in\Gamma(E)}(1-z_F)\ge
\exp\!\Big[-\Big(\tfrac1{32}+\tfrac2{500}\Big)l(E)\Big]\ge2e^{-l(E)/8}\ge
\mathbb P(E), $$

the middle inequality because $(1/8-1/32-2/500)\cdot100>\log2$. Lemma 5.1 then
gives a choice of all bits avoiding every bad event; fix it as $c_*$. Summing the
balanced row counts over the partition of the light positions proves (1); the
second event family gives (2).

Finally, pull back to the group:

$$ c_0(n)=c_*(L(n))\qquad(n\in G). $$

This $c_0$ is the "outer coloring". It is already close to our target; the
remaining work is the sparse perturbation of Section 7, which uses the dichotomy
of Section 6.

---

## 6. The outer-color dichotomy

This section is the bridge between the outer coloring of Section 5 and the
perturbation of Section 7. The target statement: **every cyclic progression
either sees many occurrences of each outer color, or it admits one affine lift in
the centered second coordinates.** A "balanced" progression is destroyed by
random flips; an "affine" one, which lives on a straight line, is destroyed by a
counting argument. The dichotomy says these two cases exhaust everything.

### 6.1 Affinity inside a small box

**Lemma 6.1 (affinity inside a small box).** Let $z_j=a+jb$ in $\mathbb T^e$ for
$0\le j<k$, and let $J\subseteq\{0,\dots,k-1\}$. Suppose real representatives
$Z_j\in\mathbb R^e$ for $j\in J$ lie in one box whose coordinate intervals have
length at most $2H$. If $2kH<1$, then there are $A,B\in\mathbb R^e$ with
$Z_j=A+jB$ for every $j\in J$.

*Idea.* For any $j_1<j_2<j_3$ in $J$, affinity modulo one implies
$(j_3-j_2)(Z_{j_2}-Z_{j_1})-(j_2-j_1)(Z_{j_3}-Z_{j_2})\in\mathbb Z^e$. In each
coordinate its absolute value is at most $2H(j_3-j_1)\le 2kH<1$, hence zero. So
every triple uses the same affine interpolation, and interpolating between the
smallest and largest index pins down $A,B$.

Now fix a cyclic progression $n_j=n_0+jd$, $0\le j<k$, with a heavy label.
"Light" and "heavy" below always refer to this fixed progression.

### 6.2 The closest return

**Lemma 6.2 (closest return and drift).** Let a heavy label have occurrence set
$J$, with $m_*=|J|>k/M$. Let $h$ be the smallest positive gap between two
occurrences, attained at $j'$ and $j'+h$. Set
$u=\hat x(n_{j'+h})-\hat x(n_{j'})$ and
$v=\tilde y(n_{j'+h})-\tilde y(n_{j'})$. Then, for large $k$,

$$ 1\le h\le 2M,\qquad |u_i|\le\frac{H_x}{m_*-1}\le\frac{2MH_x}{k},\qquad
|v_i|\le\frac{2H}{m_*-1}\le\frac{4MH}{k}, $$

for every $i$, and $v=\lambda u$ as real vectors.

*Idea.* With $m_*-1\ge k/(2M)$ and $j_-=\min J$, $j_+=\max J$, the smallest of the
$m_*-1$ consecutive gaps is at most $(k-1)/(m_*-1)\le2M$. All representatives at
the occurrences lie in one full-label box of width at most $2H$. By Lemma 6.1 the
differences are proportional to index differences; the difference at the gap $h$
is $h/(j_+-j_-)$ times the difference between the two extreme visits, which is
bounded by $H_x$ and $2H$. Finally, $v-\lambda u\in\mathbb Z^D$ on the torus while
$|v_i-\lambda u_i|\le 6MH/k<1$, so it is zero.

### 6.3 The rational path

**Lemma 6.3 (rational path and separated residues).** With $h,u,v$ as above, there
is $t\in\{0,\dots,h-1\}^D$ such that, in $\mathbb T^D$,

$$ x(n_j)=x(n_0)+\frac jh(t+u),\qquad y(n_j)=y(n_0)+\frac jh(\lambda t+v),
\qquad 0\le j<k. $$

Moreover $\gcd(t_1,\dots,t_D,h)=1$, and indices incongruent modulo $h$ have
distinct full labels. Consequently, all occurrences of any one full label lie in
a single residue class modulo $h$.

*Idea.* Since $h\,x(d)=u\pmod{\mathbb Z^D}$, the vector $t'=h\hat x(d)-u$ is
integral; reduce it coordinatewise modulo $h$ to get $t$. The first identity
follows, and multiplying by $\lambda$ using $v=\lambda u$ gives the second. For
the gcd: if a common divisor $e>1$ divided $h$ and all $t_i$, then the torus
displacements over the gap $h/e$ would be $u/e$ and $v/e$, whose middle point is a
convex combination of the representatives at the ends of a half-open box, hence
inside the same box: a closer visit, contradicting minimality of $h$. The vector
$t/h$ then has order exactly $h$. Finally, for incongruent $j_1,j_2$ some
coordinate has rational displacement of circle distance at least $1/h$; the drift
is at most $2MH/h$, so the actual distance is at least $(1-2MH)/h>H\ge H_x$, too
far to share a $U$-interval.

### 6.4 Drift relative to any heavy interval

**Lemma 6.4 (drift relative to every heavy interval).** For every heavy index
$j_*$ of the fixed progression and each coordinate $i$,

$$ |v_i|\le\frac{2M}{k}\,|V(y_i(n_{j_*}))|. $$

Here the heavy label at $j_*$ need not be the one used to choose $h$.

*Idea.* The label at $j_*$ has multiplicity $m'>k/M$, with extreme indices
differing by $a h$ for an integer $a$ in $[m'-1,k/h)$. Let
$L_i=|V(y_i(n_{j_*}))|$; the real representative difference between the extremes
has absolute value $\Delta_i$ with $|\Delta_i|\le L_i\le2H$ and is congruent to
$a v_i$ modulo one. Since $|a v_i|\le4MH/h$ and $|\Delta_i-a v_i|\le
2H+4MH/h<1$, the integer $\Delta_i-a v_i$ is zero, so
$|v_i|\le L_i/a\le L_i/(m'-1)\le 2M L_i/k$. This uses only the two endpoint
representatives; no path across a cut is assumed.

### 6.5 The dichotomy

**Theorem 6.5 (outer-color dichotomy).** For every sufficiently large $k$, the
coloring $c_0$ has the following property. Every cyclic progression
$n_j=n_0+jd$, $0\le j<k$, with $d\ne0$ in $G$, satisfies at least one of:

1. each bit occurs among $c_0(n_0),\dots,c_0(n_{k-1})$ at least $\gamma k$ times;
2. there are $A,B\in\mathbb R^D$ with $\tilde y(n_j)=A+jB$ for all $0\le j<k$.

The threshold on $k$ is absolute.

*Idea of proof.* If the progression has at least $\delta k$ light positions,
Proposition 5.2(1) supplies at least $\delta k/4\ge\gamma k$ of each bit. So assume
fewer than $\delta k$ positions are light; then a heavy label exists, and Lemmas
6.2-6.4 give $h,t,u,v$.

**Short periods ($h\le h_0$).** The dilation gives $h\mid\lambda$, so the second
path has real step $w=v/h$ modulo one (because $\lambda t/h$ is integral). Its
total coordinate motion is $k|w_i|\le4MH/h<1/2$. The congruence
$w_i=y_i(d)\pmod1$ puts $w_i$ in $q^{-i}\mathbb Z$, so
$w_i\ne0\Rightarrow|w_i|\ge q^{-i}\ge q^{-D}\ge\alpha$. If the sampled
representatives failed to equal $\tilde y(n_0)+jw$, some coordinate with $w_i\ne0$
would make the real segment meet a cut point, putting every sample within
$k|w_i|$ of a cut; the width lemma then gives
$|V(y_i(n_j))|\le2H(k+1)|w_i|<|w_i|$, while distinct samples are at distance
$\ge|w_i|$ and cannot share an interval that fine. That would make all labels
distinct, contradicting "heavy". So every sample equals $\tilde y(n_0)+jw$:
alternative 2.

**Longer periods ($h_0<h\le2M$).** Partition the first $h\lfloor k/h\rfloor$
indices into full blocks of length $h$ (the tail has fewer than $h$ indices). Each
block has exactly the form of Definition 4.3 with the same $h,t,u,v$. For a
rotating coordinate, the undrifted values form an equally spaced grid of $s_i$
circle points, and the drift is below $\eta$; the fraction of nonregular positions
is at most $D(4\eta+1/h_0)=4/1000+1/D<1/2$, so each block has at least $h/2$
regular positions. Labels are distinct by Lemma 6.3. By Lemma 6.4, every block
containing a heavy index satisfies the stationary drift condition at every regular
position. So every such block is **eligible**, and Proposition 5.2(2) gives it at
least $h/8$ occurrences of each bit. A full block that is not used this way
consists entirely of light positions; since fewer than $\delta k$ positions are
light and the tail has fewer than $h$ indices, the used blocks cover at least
$k-h-\delta k\ge\tfrac45k$ positions. Hence each bit occurs at least
$k/10\ge\gamma k$ times: alternative 1.

All inequalities imposed only absolute lower bounds on $k$.

---

## 7. The sparse perturbation: the cyclic two-coloring

The outer coloring $c_0$ is close, but a balanced progression could still be
monochromatic by accident. This section fixes that with a sparse random
perturbation indexed by a clever geometric key. At the end we get a genuine
two-coloring of $G$ with no monochromatic progression.

### 7.1 Keys: boxes plus norm bands

For $n\in G$ define

$$ f(n)=\|q\tilde y(n)\|_2^2,\qquad
\kappa(n)=\Big((V(y_i(n)))_{i=1}^D,\ \lfloor f(n)\rfloor\Big),\qquad
\mathcal K=\{\kappa(n):n\in G\}. $$

So a **key** records a specific second-system box (the tuple of $V$-intervals)
together with the integer part of the scaled squared norm of the centered
representative. The set $\mathcal K$ is finite.

**Lemma 7.1 (bounded multiplicity of a key).** For every progression
$n_j=n_0+jd$ with $d\ne0$, $0\le j<k$, every key occurs at most four times among
the $\kappa(n_j)$.

*Idea.* Fix one second-system box, and let $J$ be the indices whose centered
representatives lie in that box. Each coordinate interval has width at most $2H$,
so Lemma 6.1 gives $\tilde y(n_j)=A+jB$ for $j\in J$: those scaled points lie on
an affine line. Any two distinct terms of the progression are separated by
Euclidean distance at least $1$ after scaling by $q$. Indeed, since $\lambda$ is a
unit modulo $q^D$, the residue $\lambda(n_j-n_{j'})$ is nonzero; write a
representative $z=q^a u$ with $q\nmid u$, and coordinate $a+1$ has displacement
$u/q\bmod1$, of circle distance at least $1/q$.

Now a line with closest point $z_0$ and unit direction $e$ gives
$\|z_0+te\|_2^2=t^2+C'$ with $C'=\|z_0\|_2^2\ge0$. The band of one key is
$m\le t^2+C'<m+1$. On each half-line $t\ge0$ and $t\le0$ this band occupies an
interval of length at most one (the difference of the two square roots of numbers
differing by one is at most one). By the separation, each such interval holds at
most two sampled points. So the key occurs at most four times.

(A small picture helps: a line cutting the annulus $m\le\|z\|_2^2<m+1$ enters and
leaves on each side of the nearest point $z_0$, and each of those two crossings is
short, so only a few spaced-out points fit.)

### 7.2 Affine progressions and signatures

Call a progression **affine** when its whole sequence $\tilde y(n_j)$ is affine in
$j$ as a sequence in $\mathbb R^D$; its **signature** is the literal word

$$ \sigma=\big((c_0(n_j),\kappa(n_j))\big)_{0\le j<k}. $$

Entries keep the actual boxes and band indices; keys are not renamed across
progressions.

**Lemma 7.2 (counting affine signatures).** If $T_{\mathrm{aff}}$ is the number
of signatures realized by affine progressions, then for an absolute $C$,

$$ T_{\mathrm{aff}}\le C\,T_{\mathrm{glob}}\big(k(Dq^2+2)\big)^3, $$

and hence

$$ \log\max\{1,T_{\mathrm{aff}}\}\le O(k^{3/10}\log k)+6\log q+O(\log k)
=O(k^{9/10}\log k)=o(pk). $$

*Idea.* On an affine progression $\tilde y(n_j)=A+jB$, so
$f(n_j)=q^2\|A+jB\|_2^2=\theta_0+\theta_1 j+\theta_2 j^2$ is a quadratic in $j$
with three coefficients. Also $0\le f(n_j)\le Dq^2/4$. To determine the word
$(\lfloor f(n_j)\rfloor)_{j<k}$ it suffices to know, for each $j$ and each integer
$b\in\{0,\dots,\lfloor Dq^2/4\rfloor+1\}$, the sign of
$\theta_0+\theta_1 j+\theta_2 j^2-b$. These are at most $k(Dq^2+2)$ affine
hyperplanes in the three variables $(\theta_0,\theta_1,\theta_2)$; by Lemma 4.1 in
dimension three the number of realized sign words is at most
$C(k(Dq^2+2))^3$. The full-label word fixes the boxes and (since $c_*$ is fixed)
each $c_0(n_j)$; multiplying gives the count. The estimate uses
$\log q\le \frac{ck}{D}\log k+O(\log k)=O(k^{9/10}\log k)$ and $pk=k^{19/20}$, so
$k^{9/10}\log k=o(pk)$.

### 7.3 The cyclic two-coloring theorem

**Theorem 7.3 (a cyclic two-coloring).** There is an absolute integer $K_0$ such
that, for every integer $k\ge K_0$, the construction gives an integer
$N=q^D\ge k^{ck}$ with $c=10^{-5}$ and a coloring $C:\mathbb Z/N\mathbb Z\to\{0,1\}$
for which no progression $n_0,n_0+d,\dots,n_0+(k-1)d$ with $d\ne0$ in
$\mathbb Z/N\mathbb Z$ is monochromatic.

*Idea of proof.* For each key $\kappa\in\mathcal K$ take an independent Bernoulli
bit $E_\kappa$ with $\mathbb P(E_\kappa=1)=p=k^{-1/20}$, and set

$$ C(n)=c_0(n)+E_{\kappa(n)}\pmod 2. $$

**Balanced case.** Suppose a progression has at least $\gamma k$ of each outer
color $c_0$. Fix a target color $b\in\{0,1\}$. Every position with $c_0=1-b$ must
have $E_\kappa=1$ for the progression to be entirely color $b$. By Lemma 7.1 these
positions specify at least $\gamma k/4$ distinct keys, so this has probability at
most $p^{\gamma k/4}$ (and is zero if a key is forced both ways). There are fewer
than $|G|^2=q^{2D}$ choices of $(n_0,d)$, so a union bound over these and the two
colors gives

$$ R_k\le 2q^{2D}p^{\gamma k/4}\le
\exp\!\Big[\Big(2c-\frac{\gamma}{80}\Big)k\log k+2D\log(2k^2)+\log2\Big]. $$

The leading coefficient is
$2c-\gamma/80=\frac1{50000}-\frac1{8000}=-\frac{21}{200000}<0$, and the other terms
are $O(k^{1/10}\log k)=o(k\log k)$, so $R_k=o(1)$.

**Affine case.** Fix a signature realized by an affine progression, and a target
color $b$. For each entry $(c_j,\kappa_j)$ monochromaticity prescribes
$E_{\kappa_j}=b-c_j\pmod2$. Inconsistent prescriptions give an empty event;
otherwise, if there are $s$ distinct keys, the probability is $p^u(1-p)^{s-u}$ for
some $u$, at most $(1-p)^s$ because $p\le1-p$. By Lemma 7.1, $s\ge k/4$, so the
probability is at most $(1-p)^{k/4}$. Two progressions with the same signature
impose the same prescriptions and define the same event, so it is counted once.
Hence

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

By the dichotomy (Theorem 6.5), every nonzero-step progression is covered by the
balanced case or the affine case. The cases may overlap, which only helps. So the
probability that any progression is monochromatic is at most $R_k+A_k<1$ for large
$k$; a choice of the bits gives the asserted coloring. Finally $N=q^D\ge k^{ck}$.

---

## 8. Transfers: integer intervals and the two growth regimes

The cyclic coloring of Theorem 7.3 lives on $\mathbb Z/N\mathbb Z$. This section
converts it into a coloring of an ordinary interval with many colors, proving the
Main Theorem, then proves the separate "growth in the number of colors" bound.

### 8.1 The digit product

**Proposition 8.1 (digit product).** Let $N,k\ge2$. Suppose a coloring
$C:\mathbb Z/N\mathbb Z\to\{0,1\}$ has no monochromatic progression
$a,a+d,\dots,a+(k-1)d$ with $d\ne0$ in $\mathbb Z/N\mathbb Z$. Then, for every
positive integer $m$,

$$ W_{2^m}(k)>N^m. $$

Consequently $W_r(k)>N^{\lfloor\log_2 r\rfloor}$ for every integer $r\ge2$.

*Idea.* Write $0\le n<N^m$ in base $N$: $n=\sum_{i=0}^{m-1}n_iN^i$, $0\le n_i<N$,
and color $n$ by the tuple $(C(n_0),\dots,C(n_{m-1}))\in\{0,1\}^m$. Suppose a
monochromatic progression $a,a+d,\dots,a+(k-1)d$ with $d>0$ exists. Since $k\ge2$,
$d<N^m$; let $i$ be the largest index with $N^i\mid d$, and write $e=d/N^i$, so
$N\nmid e$. For every $j$ the exact identity
$\lfloor(a+jd)/N^i\rfloor=\lfloor a/N^i\rfloor+je$ holds. Reducing modulo $N$ shows
the $i$-th digits form a cyclic progression with nonzero step $e\bmod N$, which the
coloring cannot be constant on. Translating gives a coloring of $[N^m]$ with $2^m$
colors; embed the $\le2^m$ colors into $[r]$ with $m=\lfloor\log_2 r\rfloor$.

**Proof of the Main Theorem.** Theorem 7.3 supplies, for every $k$ above an
absolute threshold, a cyclic coloring with $N=q^D\ge k^{ck}$, $c=10^{-5}$.
Proposition 8.1 then gives, for every $r\ge2$ with $m=\lfloor\log_2 r\rfloor$,

$$ W_r(k)>N^{\lfloor\log_2 r\rfloor}\ge k^{ck\lfloor\log_2 r\rfloor}. $$

The threshold on $k$ was fixed before $r$ was introduced, so it is absolute and
uniform in the number of colors. That is the Main Theorem.

### 8.2 Growth in the number of colors

The next bound uses a different construction, and only three-term progressions, so
it needs no large threshold on $k$. It records a coarse interval for each base-$b$
digit (to force midpoint relations coordinatewise) together with a squared norm (to
exclude nonconstant midpoints): the digit-and-sphere geometry of Behrend, used to
cover the whole interval by progression-free color classes.

**Theorem 8.2.** For every pair of integers $r\ge256$ and $k\ge3$,

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

*Idea.* Set $b=\lfloor r^{1/4}\rfloor\ge2$ and $s=\lfloor\log r/(4\log2)\rfloor$.
Partition the digits $\{0,\dots,b-1\}$ into the lower and upper halves $H_0,H_1$,
with $h(u)\in\{0,1\}$ recording the half. For $0\le n<b^s$ with digits
$x=(x_0,\dots,x_{s-1})$, color $n$ by

$$ \big(h(x_0),\dots,h(x_{s-1}),\ x_0^2+\dots+x_{s-1}^2\big). $$

The number of colors is at most $2^s(1+s(b-1)^2)\le2^s(1+sb^2)$. Since $s+1\le2^s$,
$2^s\le r^{1/4}$ and $b^2\le r^{1/2}$, this is at most $r^{1/4}(s+1)r^{1/2}\le r$.

Now suppose three equally spaced integers have digit vectors $x,y,z$ and the same
color. The midpoint relation is $\sum_i(x_i-2y_i+z_i)b^i=0$. Digits in one half
satisfy $|x_i-2y_i+z_i|\le2(\lceil b/2\rceil-1)<b$. Reducing mod $b$ forces the
zeroth coefficient to be a multiple of $b$ whose absolute value is below $b$, hence
zero; dividing by $b$ and repeating gives $x_i-2y_i+z_i=0$ for all $i$, i.e.
$x+z=2y$. Equality of the squared-norm entries gives $\|x\|^2=\|y\|^2=\|z\|^2$, so
$\|x-z\|^2=2\|x\|^2+2\|z\|^2-4\|y\|^2=0$, hence $x=z$, and then $x=y=z$. So every
three-term progression is constant, which already excludes any longer nonconstant
progression. Counting colors, $W_r(k)>b^s$. Finally with $L=\log r\ge8\log2$:
$s\ge L/(8\log2)$ and $\log b\ge L/4-\log2\ge L/8$, so
$\log(b^s)\ge L^2/(64\log2)$.

### 8.3 The uniform growth statements

**Corollary 8.3.** With integer parameters in both infima,

$$ \lim_{k\to\infty}\inf_{r\ge2}\frac{\log W_r(k)}{k\log r}=\infty,\qquad
\lim_{r\to\infty}\inf_{k\ge3}\frac{\log W_r(k)}{\log r}=\infty. $$

In particular, for each fixed $r\ge2$, $W_r(k)^{1/k}\to\infty$, and for each fixed
$k\ge3$ and real $A>0$, $W_r(k)/r^A\to\infty$ as $r\to\infty$.

*Idea.* Since $\lfloor\log_2 r\rfloor\ge(\log r)/(2\log2)$, the Main Theorem gives
$\inf_{r\ge2}\log W_r(k)/(k\log r)\ge\frac{c}{2\log2}\log k$, which tends to
infinity. Theorem 8.2 gives $\inf_{k\ge3}\log W_r(k)/\log r\ge\log r/(64\log2)$,
also tending to infinity. For fixed $r$, $W_r(k)^{1/k}>k^{c\lfloor\log_2 r\rfloor}
\to\infty$; for fixed $A$,
$\log(W_r(k)/r^A)>(\log r)^2/(64\log2)-A\log r\to\infty$.

The restrictions on the parameters matter: the exact boundary values $W_1(k)=k$,
$W_r(1)=1$, $W_r(2)=r+1$ are proved along with finiteness in the next section.

---

## 9. An elementary finite upper bound

For completeness we sketch a coarse proof that $W_r(k)$ is finite, with an explicit
recursion. This is the classical block-and-focus argument of van der Waerden, with
the quantitative bookkeeping made explicit. It matters because it shows $W_r(k)$
exists for all $r,k$ and pins the boundary values; the lower bounds of the previous
sections are what make the numbers large.

**Theorem 9.1 (finite upper bound).** Define $F(r,1)=1$ and $F(r,2)=r+1$ for every
integer $r\ge1$. For $k\ge3$, with $r$ and $k$ fixed, define

$$ m_0=1,\qquad m_{t+1}=2\,m_t\,F(r^{m_t},k-1)\ \ (0\le t<r),\qquad F(r,k)=m_r. $$

Then, for all positive integers $r,k$,

$$ W_r(k)\le F(r,k)<\infty. $$

The boundary values are exactly $W_r(1)=1$, $W_r(2)=r+1$, $W_1(k)=k$.

*Idea.* The recursion is well founded: build all $F(r,k)$ at a given length $k$
after building $F(\cdot,k-1)$ for every color count, so each of the $r$ steps uses
finite positive integers.

**Boundary cases.** A one-term progression is a singleton, so $W_r(1)=1$. Any
$r$-coloring of $[r+1]$ has two equal colors, and those two points form a 2-term
progression; an injective coloring of $[r]$ avoids this, so $W_r(2)=r+1$. In one
color, $[k]$ contains a $k$-term progression and $[k-1]$ does not, so $W_1(k)=k$.

**Induction.** Prove, by induction on $k$ simultaneously for all $r$, that every
$r$-coloring of an interval of $F(r,k)$ consecutive integers contains a monochromatic
$k$-term progression. Fix $k\ge3$, assume the statement at length $k-1$ for every
color count, and fix $r\ge1$.

A **focus with $t$ colors** in a colored interval is a point $f$ together with
positive integers $d_1,\dots,d_t$ such that all points $f-sd_i$ for $1\le s\le k-1$
and $1\le i\le t$ lie in the interval, and for each $i$ those $k-1$ points have a
common color $a_i$, with $a_1,\dots,a_t$ pairwise distinct. If the interval contains
no monochromatic $k$-term progression, the focus itself must have a color different
from every $a_i$; otherwise $f$ together with the arm of difference $d_i$ forms such
a progression.

**Inner induction.** Claim: every $r$-coloring of an interval of length $m_t$ with
no monochromatic $k$-term progression has a focus with $t$ colors. For $t=0$, take
the single point of $m_0=1$. Assume the claim for $t<r$, put $m=m_t$,
$B=F(r^m,k-1)$, $m_{t+1}=2mB$, and work with an avoiding coloring $\chi$ of $[2mB]$.
Partition into $2B$ consecutive blocks of length $m$ and record the word $w_j$ of
block $j$; there are at most $r^m$ words. By the outer induction at length $k-1$
with $r^m$ colors applied to the block-index coloring of the first $B$ blocks, there
are $b,\Delta\ge1$ with

$$ w_b=w_{b+\Delta}=\dots=w_{b+(k-2)\Delta},\qquad b+(k-2)\Delta\le B. $$

Since $k-2\ge1$, $\Delta\le B-1$, so the next index $q=b+(k-1)\Delta\le2B-1$ is
still one of the blocks.

The common word of the matching blocks, viewed as a coloring of $[m]$, contains no
monochromatic $k$-term progression (such a progression would occur inside block $b$).
By the inner induction it has a focus $f\in[m]$ with differences $d_1,\dots,d_t$ and
arm colors $a_1,\dots,a_t$; let $a_0$ be its own color, which differs from all $a_i$.
Take position $f$ in block $q$ as the new focus $f'=(q-1)m+f$. For each arm,

$$ f'-s(m\Delta+d_i)=\big(b+(k-1-s)\Delta-1\big)m+(f-sd_i), $$

whose block is one of the matching blocks and whose within-block position is in
$[m]$ (color $a_i$); and one more arm
$f'-sm\Delta=(b+(k-1-s)\Delta-1)m+f$ has color $a_0$. So $f'$ is a focus with $t+1$
colors, completing the inner induction.

**Finish.** At $t=r$, an avoiding coloring of $[m_r]$ would have a focus using $r$
distinct arm colors, and its own color could equal none of them, impossible with
only $r$ colors. So every $r$-coloring of $[m_r]$ contains a monochromatic $k$-term
progression, proving $W_r(k)\le F(r,k)$.

---

## 10. References

The proof stands on the following works; full bibliographic data is in the paper's
reference list.

- B. L. van der Waerden (1927). Beweis einer Baudetschen Vermutung. The original
  proof that $W_r(k)$ is finite.
- B. L. van der Waerden (1998). Wie der Beweis der Vermutung von Baudet gefunden
  wurde (reprint of the 1965 account). The block-and-focus argument of Section 9.
- R. P. Stanley (2007). An introduction to hyperplane arrangements. The
  region/sign-vector counts behind Lemma 4.1.
- P. Erdos (1980). A survey of problems in combinatorial number theory. The question
  answered by the Main Theorem.
- P. Erdos and L. Lovasz (1975). Problems and results on 3-chromatic hypergraphs and
  some related questions. The local lemma of Lemma 5.1.
- J. Fox and Z. Hunter (2026). Three-color van der Waerden numbers grow
  super-exponentially. Prior superexponential bound in three colors, and related
  estimates.
- M. Campos, J. Fox, and C. Schildkraut (2026). A new lower bound for two-color van
  der Waerden numbers. The result on $W_2(k)/2^k$.
- R. Shi and Y. Dong (2026). An improved upper bound for colorings without
  symmetrically colored $k$-term arithmetic progressions. Related digit and
  finite-field norm colorings.
- P. Erdos and R. Rado (1952). Combinatorial theorems on classifications of subsets
  of a given set. Early lower bounds.
- W. M. Schmidt (1962). Two combinatorial theorems on arithmetic progressions. Early
  lower bounds.
- E. R. Berlekamp (1968). A construction for partitions which avoid long arithmetic
  progressions. $W_2(p+1)>p\,2^p$.
- Z. Szabo (1990). An application of Lovasz' local lemma: a new lower bound for the
  van der Waerden number. $W_2(k)\ge2^k/k^\varepsilon$.
- J. Kozik and D. Shabanov (2016). Improved algorithms for colorings of simple
  hypergraphs and applications. $W_r(k)\ge\beta r^{k-1}$.
- Z. Hunter (2025). Lower bounds for multicolor van der Waerden numbers. Improved
  exponential base for fixed $r\ge5$.
- S. Shelah (1988). Primitive recursive bounds for van der Waerden numbers.
  Quantitative upper bounds.
- W. T. Gowers (2001). A new proof of Szemeredi's theorem. Quantitative upper bounds.
- F. A. Behrend (1946). On sets of integers which contain no three terms in
  arithmetical progression. The progression-free set construction behind the mesh and
  Theorem 8.2.
- B. Green and J. Wolf (2010). A note on Elkin's improvement of Behrend's
  construction. The torus-annulus viewpoint.
- B. Green (2022). New lower bounds for van der Waerden numbers. Asymmetric annulus
  constructions.
- Z. Hunter (2022). Improved lower bounds for van der Waerden numbers. Annulus radii
  at many centers.
- R. A. Rankin (1961). Sets of integers containing not more than a given number of
  terms in arithmetical progression. Long progression-free sets.
- Z. Kelley and R. Meka (2023). Strong bounds for 3-progressions. Density bound
  behind the quasipolynomial upper side.
- J. Leng, A. Sah, and M. Sawhney (2024). Improved bounds for Szemeredi's theorem.
  Density bounds for fixed length at least five.
- OpenAI (2026). Quasipolynomial bounds for arithmetic progressions. Companion paper
  supplying the upper half of the two-regime statement.

---

*This walkthrough restates every step of the paper, including the constants that
make the argument quantitative. The single idea to remember: a periodic dilation
$\lambda$ turns a short rational return into an affine motion, and a random bit
keyed by a norm band then kills whatever is left. Those two mechanisms, applied
uniformly over all color counts, give $W_r(k)>k^{ck\lfloor\log_2 r\rfloor}$.*