# Quantitative Superexponential Bounds for van der Waerden Numbers

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

---

## 0. Prologue: 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 all of the same color? That threshold is the van der Waerden number $W_r(k)$. The whole paper proves one bound, and its slogan is:

> **van der Waerden numbers grow faster than exponentially: for every fixed number of colors $r$, the quantity $W_r(k)^{1/k}$ tends to infinity as the length $k$ grows.**

More precisely, there are an absolute constant $K_0$ and an absolute constant $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: it is a constant times $k$ times (number of binary digits of $r$). So the bound is roughly "$k$ raised to a quantity proportional to $k$", which is what "superexponential" means here: the $k$-th root $W_r(k)^{1/k}$ 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**, which is the hardest and most famous case. The paper is a research paper. What follows is a map of the entire proof, compressed by roughly a factor of ten. Every step of the argument appears; the deepest lemmas are recorded with their exact statement and the idea behind them, without 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** (or just "progression") is a list

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

all of whose members lie in $[N]$. Here $d$ is the common difference or "step". Van der Waerden's theorem (1927) says that if you color $[N]$ with $r$ colors, then for $N$ large enough some color contains a whole $k$-term progression. The **van der Waerden number** $W_r(k)$ is the smallest $N$ for which this is unavoidable:

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

"Map $[N]\to[r]$" just means an $r$-coloring; a map that uses fewer than $r$ colors is allowed. The content of the definition is a **lower bound problem**: to prove $W_r(k)>N$ you must exhibit a single $r$-coloring of $[N]$ that contains no monochromatic $k$-term progression.

### 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 of combinatorial number theory, explicitly asked whether the two-color numbers satisfy this full limit. The theorem answers that question affirmatively, and quantitatively. It is strictly stronger than the older assertion that $W_2(k)/2^k\to\infty$: it shows the $k$-th root diverges, not merely that $W_2(k)$ beats a fixed multiple of $2^k$.

Three boundary values are worth knowing because they pin down the definition: $W_1(k)=k$ (one color, nothing to avoid), $W_r(1)=1$ (a one-term progression is a single point, so $N=1$), and $W_r(2)=r+1$ (with $r+1$ points and $r$ colors two share a color, and those two form a 2-term progression; $r$ points can be colored injectively).

### 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$.

There is a second, different growth 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 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 of this 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. The goal is to describe an integer coloring directly, but it is far easier to first build a coloring of a **finite cyclic group** and then convert it.

**Step A (reduction 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. Then a **digit product** (Section 8) 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. It has four ingredients:

1. **Setup (Section 3).** Choose 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)$. Each coordinate is cut into small intervals; a point is labeled by the tuple of intervals it lies 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, and the dilation $\lambda$ kills short periods while longer periods give eligible blocks 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 has tiny probability; in an affine progression, the keys are governed by only a quadratic polynomial, whose possible signatures can be counted and beaten by a union bound. 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 and a proof of finiteness appear in Section 9.

The rest of this 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 last point is the whole reason the final bound is uniform.

### 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: control must survive when the dimension grows with $k$, and cannot 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 are "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 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$ and 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 (so it is "stationary": the point wraps exactly) or it moves fast enough that its denominator is large. There is no middle ground. This 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 smallest 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 will be 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)$. Every interval 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)$. The width of an interval sitting at distance $\rho$ from the cut is 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)$ is the interval label containing it (half-open convention as written). 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 $\approx2$, 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

All counts here are counts of literal interval labels. The central idea is that, 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 regions by the induced 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, at most $\binom{s}{d}$ choices; 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)$, and 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 are 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 the bound $\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 step is the sparse perturbation of Section 7, which uses the dichotomy of Section 6.

---

## 6. The outer-color dichotomy

This section proves the bridge between the outer coloring of Section 5 and the perturbation of Section 7. The statement to aim for: **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 still might 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 $\ell$ closest point $z_0$, and unit direction $e$, give $\|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 an 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 above stands on the following works. Entries are given in a plain, readable form; 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}$.*