==== TABLE OF CONTENTS ====
Quantitative-Superexponential-Bounds-for-van-der-Waerden-Numbers//figures/norm-band.tex
Quantitative-Superexponential-Bounds-for-van-der-Waerden-Numbers//paper.tex
Quantitative-Superexponential-Bounds-for-van-der-Waerden-Numbers//preamble.tex
Quantitative-Superexponential-Bounds-for-van-der-Waerden-Numbers//sections/01-introduction.tex
Quantitative-Superexponential-Bounds-for-van-der-Waerden-Numbers//sections/02-setup.tex
Quantitative-Superexponential-Bounds-for-van-der-Waerden-Numbers//sections/03-counting.tex
Quantitative-Superexponential-Bounds-for-van-der-Waerden-Numbers//sections/04-outer.tex
Quantitative-Superexponential-Bounds-for-van-der-Waerden-Numbers//sections/05-dichotomy.tex
Quantitative-Superexponential-Bounds-for-van-der-Waerden-Numbers//sections/06-perturbation.tex
Quantitative-Superexponential-Bounds-for-van-der-Waerden-Numbers//sections/07-transfers.tex
Quantitative-Superexponential-Bounds-for-van-der-Waerden-Numbers//sections/08-upper.tex
Quantitative-Superexponential-Bounds-for-van-der-Waerden-Numbers//references.bib
===========================
==== BEGIN Quantitative-Superexponential-Bounds-for-van-der-Waerden-Numbers//figures/norm-band.tex ====
\begin{tikzpicture}[scale=1.05,>=Latex,
every node/.style={font=\small}]
\path[fill=blue!9,even odd rule]
(0,0) circle[radius={sqrt(2)}] (0,0) circle[radius=1];
\draw[gray!75] (0,0) circle[radius=1];
\draw[gray!75,dashed] (0,0) circle[radius={sqrt(2)}];
\draw[gray!75,->] (-2.0,0.6)--(2.12,0.6);
\node[above left] at (-1.82,0.6) {$\ell$};
\node[above] at (2.02,0.6) {$t$};
\draw[blue!70!black,line width=2pt]
({-sqrt(1.64)},0.6)--(-0.8,0.6);
\draw[blue!70!black,line width=2pt]
(0.8,0.6)--({sqrt(1.64)},0.6);
\fill[blue!70!black] (-0.8,0.6) circle[radius=1.6pt];
\fill[blue!70!black] (0.8,0.6) circle[radius=1.6pt];
\draw[blue!70!black,fill=white,line width=0.7pt]
({-sqrt(1.64)},0.6) circle[radius=1.6pt];
\draw[blue!70!black,fill=white,line width=0.7pt]
({sqrt(1.64)},0.6) circle[radius=1.6pt];
\draw[densely dotted] (0,0)--(0,0.6);
\draw[gray!75] (0,0.46)--(0.14,0.46)--(0.14,0.6);
\fill (0,0) circle[radius=1pt];
\node[below left] at (0,0) {$0$};
\node[above] at (0,0.6) {$z_0$};
\node[align=left,anchor=west,text width=6.1cm] at (2.65,0.1)
{$\norm{z_0+te}_2^2=t^2+C'$\par\medskip
Each half-line contributes a piece\par
of length at most $1$.\par\medskip
Sampled points are at least $1$ apart:\par
at most $2$ points per piece.};
\end{tikzpicture}
==== END Quantitative-Superexponential-Bounds-for-van-der-Waerden-Numbers//figures/norm-band.tex ====
==== BEGIN Quantitative-Superexponential-Bounds-for-van-der-Waerden-Numbers//paper.tex ====
\documentclass[11pt]{article}
\input{preamble}
\title{Quantitative Superexponential Bounds\\for van der Waerden Numbers}
\author{OpenAI}
\date{September 23, 2026}
\begin{document}
\maketitle
\begin{abstract}
We prove that there are absolute constants $c>0$ and $K_0$ such that
$W_r(k)>k^{ck\lfloor\log_2 r\rfloor}$ for every $k\ge K_0$ and $r\ge2$.
Consequently $W_r(k)^{1/k}\to\infty$ for each fixed $r\ge2$, giving a
quantitative positive resolution of Erd\H{o}s's superexponential-growth
question, including the two-color case.
\end{abstract}
\input{sections/01-introduction}
\input{sections/02-setup}
\input{sections/03-counting}
\input{sections/04-outer}
\input{sections/05-dichotomy}
\input{sections/06-perturbation}
\input{sections/07-transfers}
\appendix
\input{sections/08-upper}
\clearpage
\bibliographystyle{plain}
\bibliography{references}
\end{document}
==== END Quantitative-Superexponential-Bounds-for-van-der-Waerden-Numbers//paper.tex ====
==== BEGIN Quantitative-Superexponential-Bounds-for-van-der-Waerden-Numbers//preamble.tex ====
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{lmodern,amsmath,amssymb,amsthm,mathtools}
\input{glyphtounicode.tex}
\input{glyphtounicode-cmex.tex}
\ifdefined\pdfglyphtounicode
\pdfglyphtounicode{tfm:rm-lmr10/Delta}{0394}
\pdfglyphtounicode{tfm:rm-lmr8/Delta}{0394}
\pdfglyphtounicode{tfm:lmsy10/E}{2130}
\pdfglyphtounicode{tfm:lmsy10/K}{1D4A6}
\pdfglyphtounicode{tfm:lmsy10/L}{2112}
\pdfglyphtounicode{tfm:lmsy8/E}{2130}
\pdfglyphtounicode{tfm:msbm10/E}{1D53C}
\pdfglyphtounicode{tfm:msbm10/P}{2119}
\pdfglyphtounicode{tfm:msbm10/R}{211D}
\pdfglyphtounicode{tfm:msbm10/T}{1D54B}
\pdfglyphtounicode{tfm:msbm10/Z}{2124}
\pdfglyphtounicode{tfm:lmsy10/bardbl}{2016}
\pdfglyphtounicode{tfm:lmsy10/backslash}{2216}
\pdfglyphtounicode{tfm:lmsy8/backslash}{2216}
\pdfglyphtounicode{tfm:lmex10/vextenddouble}{2016}
\pdfglyphtounicode{tfm:lmex10/parenleftbig}{0028}
\pdfglyphtounicode{tfm:lmex10/parenrightbig}{0029}
\pdfglyphtounicode{tfm:lmex10/bracketleftbig}{005B}
\pdfglyphtounicode{tfm:lmex10/bracketrightbig}{005D}
\pdfglyphtounicode{tfm:lmex10/floorleftbig}{230A}
\pdfglyphtounicode{tfm:lmex10/floorrightbig}{230B}
\pdfglyphtounicode{tfm:lmex10/parenleftBig}{0028}
\pdfglyphtounicode{tfm:lmex10/parenrightBig}{0029}
\pdfglyphtounicode{tfm:lmex10/parenleftbigg}{0028}
\pdfglyphtounicode{tfm:lmex10/parenrightbigg}{0029}
\pdfglyphtounicode{tfm:lmex10/bracketleftbigg}{005B}
\pdfglyphtounicode{tfm:lmex10/bracketrightbigg}{005D}
\pdfglyphtounicode{tfm:lmex10/floorleftbigg}{230A}
\pdfglyphtounicode{tfm:lmex10/floorrightbigg}{230B}
\pdfglyphtounicode{tfm:lmex10/parenleftBigg}{0028}
\pdfglyphtounicode{tfm:lmex10/parenrightBigg}{0029}
\pdfglyphtounicode{tfm:lmex10/braceleftBigg}{007B}
\pdfglyphtounicode{tfm:lmex10/summationtext}{2211}
\pdfglyphtounicode{tfm:lmex10/producttext}{220F}
\pdfglyphtounicode{tfm:lmex10/intersectiontext}{22C2}
\pdfglyphtounicode{tfm:lmex10/summationdisplay}{2211}
\pdfglyphtounicode{tfm:lmex10/productdisplay}{220F}
\pdfglyphtounicode{tfm:lmex10/tildewide}{02DC}
\pdfglyphtounicode{tfm:lmex10/ceilingleftBig}{2308}
\pdfglyphtounicode{tfm:lmex10/ceilingrightBig}{2309}
\pdfglyphtounicode{tfm:lmex10/radicalBig}{221A}
\fi
\pdfgentounicode=1
\usepackage[a4paper,margin=28mm]{geometry}
\usepackage{microtype,enumitem,booktabs,graphicx,xcolor}
\usepackage{needspace}
\usepackage{tikz}
\usetikzlibrary{arrows.meta,calc,positioning}
\usepackage{xurl}
\usepackage[colorlinks=true,linkcolor=blue!45!black,citecolor=blue!45!black,urlcolor=blue!45!black]{hyperref}
\usepackage[nameinlink,capitalise,noabbrev]{cleveref}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\Z}{\mathbb Z}
\newcommand{\R}{\mathbb R}
\newcommand{\T}{\mathbb T}
\newcommand{\N}{\mathbb N}
\newcommand{\Pp}{\mathbb P}
\newcommand{\E}{\mathbb E}
\newcommand{\norm}[1]{\left\lVert#1\right\rVert}
\newcommand{\dist}{\operatorname{dist}}
\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil#1\right\rceil}
\newcommand{\cO}{\mathcal O}
\newcommand{\cU}{\mathcal U}
\newcommand{\cV}{\mathcal V}
\newcommand{\cL}{\mathcal L}
\newcommand{\cK}{\mathcal K}
\newcommand{\cB}{\mathcal B}
\newcommand{\eps}{\varepsilon}
\newcommand{\id}{\mathrm{id}}
\DeclareMathOperator{\lcm}{lcm}
\setlist{itemsep=2pt,topsep=5pt}
\numberwithin{equation}{section}
\hypersetup{pdfauthor={OpenAI},pdftitle={Quantitative Superexponential Bounds for van der Waerden Numbers}}
==== END Quantitative-Superexponential-Bounds-for-van-der-Waerden-Numbers//preamble.tex ====
==== BEGIN Quantitative-Superexponential-Bounds-for-van-der-Waerden-Numbers//sections/01-introduction.tex ====
\section{Introduction}
\label{sec:introduction}
For positive integers $r$ and $k$, let $W_r(k)$ be the least positive
integer $N$ such that every map $[N]\to[r]$ is constant on some
arithmetic progression
\[
a,a+d,\ldots,a+(k-1)d,\qquad a,d\ge1,\quad a+(k-1)d\le N.
\]
Here $[N]=\{1,\ldots,N\}$, and using fewer than $r$ colors is allowed.
The finiteness of these numbers is van der Waerden's theorem
\cite{vanDerWaerden1927}.
The lower-bound problem asks how long an interval can be colored while
avoiding a monochromatic progression of a prescribed length. We prove
a bound with one threshold on the length, valid for every number of
colors.
\begin{theorem}
\label{main:intro}
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_2r\rfloor},
\qquad c=10^{-5}.
\]
\end{theorem}
In particular, for each fixed $r\ge2$,
\[
\lim_{k\to\infty}W_r(k)^{1/k}=\infty.
\]
Erd\H{o}s explicitly asked for this full limit in the two-color case
\cite[p.~90, (2)]{erdos1980}.
Thus Theorem~\ref{main:intro} gives a quantitative positive resolution
of his superexponential-growth question.
It is stronger than the assertion that $W_2(k)/2^k$ tends to infinity.
\paragraph{Earlier bounds.}
Early lower bounds were obtained by Erd\H{o}s and Rado
\cite{erdosRado1952} and by Schmidt~\cite{schmidt1962}.
Berlekamp's algebraic construction gives
$W_2(p+1)>p2^p$ for every prime $p$ \cite[Theorem~2]{berlekamp1968}.
The local lemma of Erd\H{o}s and Lov\'asz~\cite{erdosLovasz1975}
provided another route to strong coloring bounds.
Szab\'o~\cite[Theorem~2]{szabo1990} proved
$W_2(k)\ge 2^k/k^\varepsilon$ for every fixed $\varepsilon>0$
and all sufficiently large $k$.
Kozik and Shabanov~\cite[Theorem~2]{kozikShabanov2016}
subsequently obtained an absolute $\beta>0$ such that
$W_r(k)\ge\beta r^{k-1}$ for all $r\ge2$ and $k\ge3$.
Hunter~\cite[Theorem~1]{hunter2025} improved the exponential base
for each fixed $r\ge5$, with a threshold allowed to depend on $r$.
Recent results distinguish the two questions posed by Erd\H{o}s.
Fox and Hunter \cite[Theorem~1]{foxHunter2026} proved
$W_3(k)>2^{k\log^*k/4}$ for all sufficiently large $k$, where
$\log^*k$ counts the iterations of the natural logarithm needed to
reach a value at most one.
Campos, Fox, and Schildkraut \cite[Theorem~1]{camposFoxSchildkraut2026}
proved
\[
W_2(k)\ge(1-o(1))k2^{k-1}.
\]
They credit ChatGPT 5.6 Sol Pro with the coloring and an initial proof.
Their result settles the question about $W_2(k)/2^k$, whereas
Theorem~\ref{main:intro} gives the full superexponential limit.
For every fixed $\varepsilon\in(0,1)$, Fox and Hunter also prove
$W_r(k)\ge r^{(1-\varepsilon)k\log k}$ when $k$ is sufficiently
large in terms of $\varepsilon$ and
$r\ge(\log k)^{3/\varepsilon}$ \cite[Theorem~2]{foxHunter2026}.
For example, taking $\varepsilon=1/2$ gives a stronger lower bound
when $r\ge(\log k)^6$ and $k$ is sufficiently large. The bound here
holds uniformly down to two colors.
Growth in the number of colors, with the progression length fixed,
has a different history. Behrend's construction and Rankin's extension
to longer progressions supply dense progression-free sets
\cite{behrend1946,rankin1961}; covering an interval by translates of such
sets already gives superpolynomial growth in the number of colors
\cite[pp.~2--3]{foxHunter2026}. For three-term progressions, the density
bound of Kelley and Meka gives a quasipolynomial coloring upper bound
\cite[Theorems~1.1--1.2]{kelleyMeka2023}. For each fixed length at least
five, Leng, Sah, and Sawhney obtained further density bounds, improving
the earlier general coloring upper bounds
\cite[Theorem~1.1]{lengSahSawhney2024}.
For completeness, Theorem~\ref{transfer:large-r} gives a direct elementary
lower bound with an explicit constant uniform over all lengths $k\ge3$.
Combining it with the coloring upper bound in the
companion paper~\cite[Equation~(1.3)]{openaiArithmeticProgressions2026}
gives, for each integer $k\ge3$, a constant $A_k\ge1$ such that
for every integer $r\ge256$,
\[
\exp\!\left(\frac{(\log r)^2}{64\log2}\right)
0$, while
the upper bound has logarithm at most a fixed power of $\log r$.
The upper constant and exponent may depend on $k$; no uniform bound
on that dependence or matching logarithmic exponent is asserted.
Appendix~\ref{sec:upper} gives an elementary recursive upper bound,
including a proof of finiteness.
This is a coarse version of the classical argument; quantitative upper
bounds include Shelah's primitive-recursive bound~\cite{shelah1988}
and the bounds following from Gowers's proof of Szemer\'edi's
theorem~\cite{gowers2001}.
The boundary cases are $W_1(k)=k$, $W_r(1)=1$, and $W_r(2)=r+1$.
\paragraph{The construction and its quantitative ingredient.}
We first construct a two-coloring of a cyclic group $\Z/q^D\Z$ with
$q^D\ge k^{ck}$, where $q$ is a power of a prime exceeding $k$.
Let $\lambda$ be an integer dilation, to be chosen below.
The homomorphisms
\[
x_i(n)=n/q^i\pmod1,\qquad y_i(n)=\lambda x_i(n),
\qquad 1\le i\le D,
\]
supply two systems of circle coordinates.
Partition each coordinate circle into small intervals, and label a point
by the tuple of intervals containing its coordinates.
An outer color is assigned to each such label.
The intervals for $y$ become finer near the cut used to select real
representatives.
We arrange that every $k$-term cyclic progression with nonzero step
either contains a positive proportion of each outer color or has
globally affine real representatives in the $y$ coordinates.
A heavily repeated label determines a short rational period $h$.
The quantitative obstacle is to control such returns when the dimension
grows with $k$: constants depending arbitrarily on the dimension would
not suffice.
The quantitative choice is to let $D$ grow and to make $\lambda$
contain the full primary part, at every prime at most $D^2$, of
every possible period $h\le2\lceil k^{1/2}\rceil$.
After dilation, each scalar rational period is either one or exceeds
$D^2$.
This separation permits a local test on entire period blocks.
A key estimate counts the patterns through one specified label by
$(CDh)^{6D}$, with an absolute $C$ independent of $q$, $\lambda$,
and the width of the anchor interval.
It follows by anchoring at one visit and counting affine comparisons
in two scalar parameters at a time.
This form of counting remains useful even when some intervals are
arbitrarily small.
We attach an independent Bernoulli$(p)$ flip to each key consisting
of a $y$-box and $\lfloor\|q\widetilde y\|_2^2\rfloor$, where
$p=k^{-1/20}$ and $\widetilde y\in[-1/2,1/2)^D$ is the centered
representative. Here $\|\cdot\|_2$ is the Euclidean norm.
Every occurrence of a key uses the same flip, and each key occurs
at most four times along a progression.
Making a progression rich in both outer colors monochromatic
therefore requires many rare flips.
In the possibly overlapping affine case, monochromaticity prescribes
values for many distinct flip variables. The global label-word count,
together with the three coefficients of the quadratic squared norm,
gives only a small family of words of outer colors and actual keys;
identical words prescribe the same event.
With $D=\lceil k^{1/10}\rceil$, their logarithmic count is
$O(k^{9/10}\log k)=o(pk)$.
The two resulting probability estimates eliminate every progression.
A deterministic digit product then gives all $r\ge2$.
The squared-norm geometry continues the tradition of
Behrend's construction~\cite{behrend1946}; Green and Wolf
\cite{greenWolf2010} give a torus-annulus proof of Elkin's refinement.
For the asymmetric problem of excluding a red three-term progression
and a blue long progression, Green~\cite{green2022} uses translates
of a randomly perturbed ellipsoidal annulus, while
Hunter~\cite{hunter2022} chooses annulus radii independently at many centers.
Here the randomness is attached to coordinate boxes and integer
squared-norm bands. Least-common-multiple dilations in cyclic groups
appear in Fox and Hunter~\cite{foxHunter2026}; digit carry control and
finite-field norm colorings for a related symmetric-progression problem
appear in Shi and Dong~\cite{shiDong2026}.
We prove all geometric, counting, and probabilistic ingredients needed
here, including the finite local lemma.
\paragraph{Organization.}
Section~\ref{sec:setup} fixes the cyclic group and the two meshes.
Section~\ref{sec:counting} proves the global and anchored pattern counts,
and Section~\ref{sec:outer} uses them to construct the outer coloring.
Section~\ref{sec:dichotomy} turns its local tests into the balanced-or-affine
alternative. Section~\ref{perturb:section} introduces the norm-indexed
perturbation and proves the cyclic two-color theorem.
Section~\ref{sec:transfers} transfers that theorem to integer intervals
and all color counts, and proves the additional growth statements.
Appendix~\ref{sec:upper} supplies the elementary finite upper bound.
==== END Quantitative-Superexponential-Bounds-for-van-der-Waerden-Numbers//sections/01-introduction.tex ====
==== BEGIN Quantitative-Superexponential-Bounds-for-van-der-Waerden-Numbers//sections/02-setup.tex ====
\section{The cyclic model and its coordinate meshes}\label{sec:setup}
We now choose the cyclic group and the two coordinate partitions on
which the two-color construction will be built.
All logarithms without an indicated base are natural. Throughout the cyclic
construction, $k$ is an integer exceeding an absolute threshold. Every
constant implicit in $O(\cdot)$ is absolute unless an explicit subscript
indicates otherwise, and every limiting assertion is as $k\to\infty$.
In particular, no threshold in the construction depends on the eventual
number of colors $r$.
Set
\begin{equation}\label{setup:parameters}
\begin{gathered}
c=10^{-5},\qquad \delta=\frac1{10},\qquad \gamma=\frac1{100},\qquad
D=\ceil{k^{1/10}},\qquad M=\ceil{k^{1/2}},\\
h_0=D^2,\qquad p=k^{-1/20},\qquad H=k^{-2},\qquad
\eta=\frac1{1000D}.
\end{gathered}
\end{equation}
We take $k$ large enough that $h_0<2M2n$.
If every prime factor of $\binom{2n}{n}$ were at most $k$, its value
would consequently be at most $(2n)^k$. On the other hand, the central
binomial coefficient is the largest of the $2n+1$ coefficients in
$(1+1)^{2n}$, so
\[
\binom{2n}{n}\ge\frac{4^n}{2n+1}.
\]
For $n=k^2$, the logarithm of this lower bound is
$k^2\log4-\log(2k^2+1)$, whereas that of $(2n)^k$ is
$k\log(2k^2)$. The former is larger for all sufficiently large $k$.
There is therefore a prime divisor $P>k$; it is at most $2n$ because it
divides $(2n)!$.
\end{proof}
Choose such a prime $P$, and let $q$ be the least power of $P$ that is
at least $k^{ck/D}$. Minimality gives
\begin{equation}\label{setup:q-bounds}
k^{ck/D}\le q\le2k^2 k^{ck/D},\qquad
ck\log k\le D\log q\le ck\log k+D\log(2k^2).
\end{equation}
Here $q$ is a prime power, and need not itself be prime. Since
$h_0k$, so the $k$ displayed terms are distinct. On the circle
$\T=\R/\Z$, equipped with its usual distance and circumference one,
use the homomorphisms
\begin{equation}\label{setup:coordinates}
x_i(n)=\frac n{q^i}\pmod1,\qquad
y_i(n)=\lambda x_i(n)\qquad(1\le i\le D).
\end{equation}
They are well defined on $G$ since $q^i\mid N$. Write
$x(n)=(x_i(n))_{i=1}^D$ and $y(n)=(y_i(n))_{i=1}^D$, and fix their
representatives
\[
\hat x(n)\in[0,1)^D,\qquad \tilde y(n)\in[-1/2,1/2)^D.
\]
The first coordinates will distinguish residue classes of a rational
return period. The dilation in the second coordinates removes rational
motion for periods at most $h_0$; the mesh near their representative
cut will then allow us to prove a global affine lift in that case.
The cut for the second representative system is the circle point
$1/2=-1/2$. Its distance function is
\begin{equation}\label{setup:cut-distance}
\rho(Y)=\dist_{\T}(Y,1/2).
\end{equation}
Thus $0\le\rho\le1/2$, and $\rho$ is $1$-Lipschitz.
The first partition, denoted $U$, consists of the intervals
\[
[aH_x,(a+1)H_x),\qquad 0\le ah_0$. These descriptions depend only on $h,t$.
Stationarity concerns the rational step and permits nonzero drift;
even a period $h>h_0$ may have only stationary second coordinates.
We now define an enlarged family of full return-period blocks whose
labels can be balanced before the outer coloring is chosen.
\Cref{sec:dichotomy} will verify membership for every actual full
block with $h>h_0$ containing a position whose full label occurs more
than $k/M$ times in the whole progression.
\begin{definition}[Eligible local patterns]\label{count:eligible}
Choose $x,y\in\T^D$ and $u,v\in\R^D$, and form
\begin{equation}\label{count:local-paths}
X_z=x+\frac z h(t+u),\qquad
Y_z=y+\frac z h(\lambda t+v)\qquad(0\le z0$.
\end{lemma}
\begin{proof}
For $T\subseteq\mathcal E$, write $A_T=\bigcap_{F\in T}F^c$.
We prove simultaneously, by induction on $|T|$, that
\begin{equation}\label{outer:conditional}
\Pp(A_T)>0,
\qquad
\Pp(E\mid A_T)\le z_E\quad\text{for every }E\notin T.
\end{equation}
For $T=\varnothing$, positivity is immediate and the conditional bound
follows from \Cref{outer:lll-condition}. Suppose the assertions are
known for smaller sets. Removing any $F\in T$ and applying the
conditional bound gives
\[
\Pp(A_T)=\Pp(A_{T\setminus\{F\}})
\bigl(1-\Pp(F\mid A_{T\setminus\{F\}})\bigr)>0.
\]
To prove the conditional bound for $E\notin T$, put
$T_1=T\cap\Gamma(E)$ and $T_2=T\setminus T_1$.
If $T_1=\varnothing$, independence gives
$\Pp(E\mid A_T)=\Pp(E)\le z_E$ directly.
Otherwise, order the members of $T_1$ and condition successively on
their complements, starting with $A_{T_2}$. Each conditioning set has
size at most $|T|-1$, so the induction hypothesis yields
\[
\Pp(A_{T_1}\mid A_{T_2})
\ge\prod_{F\in T_1}(1-z_F).
\]
Using independence from $T_2$ in the numerator, we obtain
\[
\Pp(E\mid A_T)
\le\frac{\Pp(E\mid A_{T_2})}
{\Pp(A_{T_1}\mid A_{T_2})}
\le\frac{\Pp(E)}{\prod_{F\in T_1}(1-z_F)}
\le z_E.
\]
The last inequality uses \Cref{outer:lll-condition} and
$T_1\subseteq\Gamma(E)$. This completes the induction; take
$T=\mathcal E$ for the conclusion.
\end{proof}
\begin{proposition}[Balanced outer coloring]\label{outer:coloring}
For all sufficiently large $k$, there is a map
$c_*:\cL\to\{0,1\}$ with the following properties.
\begin{enumerate}[label=\textup{(\roman*)}]
\item 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_*$.
\item In every eligible recorded pattern of \Cref{count:eligible},
each bit occurs on at least one quarter of its regular positions.
\end{enumerate}
The threshold on $k$ is absolute.
\end{proposition}
\begin{proof}
Assign to every $\beta\in\cL$ an independent uniform random bit
$\xi_\beta$. We introduce two finite families of bad events.
For the first family, take 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. Order the light positions
by grouping equal labels together, with all choices fixed as functions
of the word. Distribute the resulting list cyclically among
$w_{\max}$ rows. A group has at most $w_{\max}$ positions, so a label
occurs at most once in each row. Every row has at least
\begin{equation}\label{outer:row-size}
\floor{\frac{L_0}{w_{\max}}}
\ge\delta M-1
\end{equation}
positions, because $w_{\max}\le k/M$.
For each row let its bad event be that some bit occurs on strictly
fewer than one quarter of its positions. There are at most
$kT_{\mathrm{glob}}$ such events in total, where
$T_{\mathrm{glob}}$ is the number in \Cref{count:global}.
For the second family, take one event for each eligible recorded
pattern and its discrete parameters $h,t$, where $h_0D^2}(CDh)^{6D}e^{-h/64}=o(1).
\end{equation}
To see the last estimate uniformly, take $C\ge1$. The function
$\log(CDh)/h$ is decreasing for $h\ge D^2$ once $D$ is large,
and hence
\[
\sup_{h>D^2}\frac{6D\log(CDh)}{h}
\le\frac{6\log(CD^3)}{D}=o(1).
\]
For all sufficiently large $k$, each summand in the infinite sum in
\Cref{outer:second-weight} is therefore at most $e^{-h/128}$.
Its tail tends to zero as $D\to\infty$.
It follows from \Cref{outer:first-weight,outer:second-weight} that,
uniformly over all labels $\beta$,
\begin{equation}\label{outer:incident-weight}
\sum_{E:\,\xi_\beta\text{ is used by }E}z_E\le\frac1{500}
\end{equation}
for all sufficiently large $k$. Join two distinct events whenever
their supports share a label variable. Since all label bits are
independent, this is a dependency graph of the kind required in
\Cref{outer:lll}; independence holds from the joint sigma-algebra of
all nonneighbors. By summing \Cref{outer:incident-weight} over the
$l(E)$ labels used by $E$, we have
\[
\sum_{F\in\Gamma(E)}z_F\le\frac{l(E)}{500}.
\]
The lower bounds $l(E)\ge\delta M-1$ in the first family and
$l(E)\ge h/2>D^2/2$ in the second ensure that $l(E)\ge100$
eventually. In particular $z_E<1/2$. Since
$\log(1-z)\ge-2z$ for $0\le z\le1/2$, we obtain
\begin{align}
z_E\prod_{F\in\Gamma(E)}(1-z_F)
&\ge\exp\!\left[-\left(\frac1{32}+\frac2{500}\right)l(E)\right]
\notag\\
&\ge2e^{-l(E)/8}\ge\Pp(E).
\label{outer:criterion}
\end{align}
For the second inequality, the positive difference
$1/8-1/32-2/500$ multiplied by $100$ exceeds $\log2$.
Thus \Cref{outer:lll} gives a choice of all label bits avoiding every
bad event. Fix that choice as $c_*$. Summing the balanced row counts
over the partition of the light positions proves part~\textup{(i)};
the second event family gives part~\textup{(ii)}.
All estimates used absolute constants and depended only on $k$, so
the threshold is absolute.
\end{proof}
Fix such a coloring from now on, and define its pullback to the group by
\begin{equation}\label{outer:pullback}
c_0(n)=c_*(L(n))\qquad(n\in G).
\end{equation}
==== END Quantitative-Superexponential-Bounds-for-van-der-Waerden-Numbers//sections/04-outer.tex ====
==== BEGIN Quantitative-Superexponential-Bounds-for-van-der-Waerden-Numbers//sections/05-dichotomy.tex ====
\section{Repeated labels and the outer-color dichotomy}
\label{sec:dichotomy}
We show that every cyclic progression either receives many occurrences
of each outer bit or admits one affine lift in the centered second
coordinates. The issue is repeated labels: a closest return to a heavy
label identifies a rational period and a small drift. Short periods
disappear under the dilation, while longer periods supply the eligible
patterns tested in \Cref{outer:coloring}.
\begin{lemma}[Affinity inside a small box]\label{dichotomy:affinity}
Let $z_j=a+jb$ in $\T^e$, for $0\le jk/M$. Let $h$ be the smallest positive difference
between two members of $J$, attained at $j'$ and $j'+h$.
Set
\[
u=\hat x(n_{j'+h})-\hat x(n_{j'}),\qquad
v=\tilde y(n_{j'+h})-\tilde y(n_{j'}).
\]
Then, for sufficiently large $k$,
\begin{equation}\label{dichotomy:drift-bounds}
\begin{gathered}
1\le h\le2M,\\
|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}
\quad(1\le i\le D),
\end{gathered}
\end{equation}
and $v=\lambda u$ as real vectors.
\end{lemma}
\begin{proof}
For large $k$, the inequality $m_*>k/M$ gives
$m_*-1\ge k/(2M)$. Write $j_-=\min J$ and $j_+=\max J$.
The smallest of the $m_*-1$ consecutive gaps in $J$ satisfies
\[
h\le\frac{j_+-j_-}{m_*-1}\le\frac{k-1}{m_*-1}\le2M.
\]
All vectors $(\hat x(n_j),\tilde y(n_j))$, $j\in J$, lie in
one full-label box, whose coordinate widths are at most $2H$ by
\Cref{mesh:width}. By \Cref{dichotomy:affinity}, their differences
are proportional to differences of indices. In particular the
difference at the chosen gap $h$ is $h/(j_+-j_-)$ times the difference
between the two extreme visits. The latter has first-coordinate
absolute differences at most $H_x$ and second-coordinate absolute
differences at most $2H$. This proves \Cref{dichotomy:drift-bounds}.
The identity $y=\lambda x$ on the torus implies
$v-\lambda u\in\Z^D$. Since $\lambda H_x=H$,
\[
|v_i-\lambda u_i|\le\frac{6MH}{k}<1
\]
for large $k$. Every coordinate of this integer vector is therefore
zero.
\end{proof}
\begin{lemma}[Rational path and separated residues]\label{dichotomy:path}
With $h,u,v$ as in \Cref{dichotomy:drift}, there is
$t\in\{0,\ldots,h-1\}^D$ such that
\begin{equation}\label{dichotomy:path-equations}
\begin{aligned}
x(n_j)&=x(n_0)+\frac jh(t+u),\\
y(n_j)&=y(n_0)+\frac jh(\lambda t+v)
\end{aligned}
\qquad\text{in }\T^D\quad(0\le j1$ divides $h$ and every $t_i$. It also divides
every $t'_i$, because $t'-t\in h\Z^D$. Hence the torus
displacements from index $j'$ to index $j'+h/e$ are $u/e$ and
$v/e$ in the first and second systems. The vector
\[
(\hat x(n_{j'}),\tilde y(n_{j'}))+\frac1e(u,v)
\]
is a convex combination of the representatives at $j'$ and $j'+h$.
Their common full-label box is a product of half-open real intervals
and is convex. This vector therefore lies in that same box and is
the chosen representative of the sample at $j'+h/e$.
It gives an additional visit to the label at a strictly smaller
positive gap $h/e$, a contradiction. This proves the gcd assertion.
The torus vector $t/h$ has order exactly $h$: if $h$ divides all
$a t_i$, the gcd assertion and B\'ezout's identity imply $h\mid a$.
Take any $j_1,j_2\in\{0,\ldots,k-1\}$ incongruent modulo $h$.
In at least one coordinate the rational displacement
$(j_1-j_2)t_i/h$ has circle distance at least
$1/h$ from zero. The drift in that coordinate has absolute value at
most
\[
\frac{k|u_i|}{h}\le\frac{2MH_x}{h}\le\frac{2MH}{h}.
\]
By the triangle inequality on the circle the actual displacement has
distance at least
\[
\frac{1-2MH}{h}\ge\frac{1-2MH}{2M}>H\ge H_x
\]
for sufficiently large $k$. Two samples in the same $U$ interval
have circle distance at most $H_x$, so these samples cannot have
the same full label.
\end{proof}
\begin{lemma}[Drift relative to every heavy interval]
\label{dichotomy:heavy-width}
For every heavy index $j_*$ of the fixed progression and each
$1\le i\le D$,
\begin{equation}\label{dichotomy:relative-width}
|v_i|\le\frac{2M}{k}\,|V(y_i(n_{j_*}))|.
\end{equation}
The heavy label here need not be the one used to choose $h$.
\end{lemma}
\begin{proof}
Let the full label at $j_*$ have multiplicity $m'>k/M$, and let
$j_-$ and $j_+$ be its extreme occurrence indices. By
\Cref{dichotomy:path}, $j_+-j_-=a h$ for an integer
$m'-1\le ah_0$. Without the drift, the $h$
values
\[
y_i(n_{j_0})+\frac{z\lambda t_i}{h},\qquad0\le z0$, and on the half-line $t\ge0$ it
is contained in the closed interval with endpoints
\[
\sqrt{\max\{0,m-C'\}},\qquad \sqrt{m+1-C'}.
\]
The difference of the quantities under these square roots is at most
one. For $0\le u\le v$, the inequality
$(\sqrt v-\sqrt u)^2\le v-u$ therefore shows that this interval has
length at most one. Reflection gives the same bound on $t\le0$.
By \Cref{perturb:separation}, each of these intervals contains at most
two sampled points: three points in an interval of length at most one
would have total separation at least two. Thus the key occurs at most
four times. If the band reaches the nearest point $z_0$, counting
$t=0$ in both halves only enlarges this upper bound. Replacing the
half-open band by closed intervals also covers equality at either
boundary, and the case of exactly two points needs no additional
argument.
\end{proof}
\begin{figure}[htbp]
\centering
\input{figures/norm-band.tex}
\caption{A line meeting the band $m\le\norm{z}_2^2N^m.
\]
Consequently $W_r(k)>N^{\lfloor\log_2r\rfloor}$ for every integer
$r\ge2$.
\end{proposition}
\begin{proof}
For $0\le n0$. Since $k\ge2$, we have $dN^{\lfloor\log_2r\rfloor}
\ge k^{ck\lfloor\log_2r\rfloor}.
\]
The threshold on $k$ was fixed before $r$ was introduced, so it is
absolute and uniform in the number of colors.
\end{proof}
\subsection{Growth in the number of colors}
For fixed progression length, a separate construction gives a useful
bound with a threshold independent of the length. The construction
records a coarse interval for each digit, to force midpoint relations
to hold coordinate by coordinate, and a squared norm, to exclude
nonconstant midpoints. This is the digit-and-sphere geometry of
Behrend~\cite{behrend1946}, used here to partition the entire interval
into progression-free color classes.
\begin{theorem}
\label{transfer:large-r}
For every pair of integers $r\ge256$ and $k\ge3$,
\[
W_r(k)>\exp\!\left(\frac{(\log r)^2}{64\log2}\right).
\]
\end{theorem}
\begin{proof}
Set
\[
b=\lfloor r^{1/4}\rfloor,\qquad
s=\left\lfloor\frac{\log r}{4\log2}\right\rfloor.
\]
Both are positive, and $b\ge2$. Partition the digit set
$\{0,\ldots,b-1\}$ into
\[
H_0=\{0,\ldots,\lceil b/2\rceil-1\},\qquad
H_1=\{\lceil b/2\rceil,\ldots,b-1\},
\]
and let $h(u)\in\{0,1\}$ record the half containing $u$.
An integer $0\le nb^s$.
Finally let $L=\log r\ge8\log2$. Since
$\lfloor u\rfloor\ge u/2$ for $u\ge1$, the parameter choices give
\[
s\ge\frac{L}{8\log2},\qquad
\log b\ge\frac L4-\log2\ge\frac L8.
\]
Consequently $\log(b^s)\ge L^2/(64\log2)$, proving the stated bound
for every $r\ge256$, independently of $k\ge3$.
\end{proof}
\subsection{Uniform growth statements}
\begin{corollary}
\label{transfer:limits}
With integer parameters in both infima,
\[
\lim_{k\to\infty}
\inf_{\substack{r\in\Z\\r\ge2}}
\frac{\log W_r(k)}{k\log r}=\infty,
\qquad
\lim_{r\to\infty}
\inf_{\substack{k\in\Z\\k\ge3}}
\frac{\log W_r(k)}{\log r}=\infty.
\]
In particular, $W_r(k)^{1/k}\to\infty$ for every fixed integer
$r\ge2$, and $W_r(k)/r^A\to\infty$ as $r\to\infty$ for every fixed
integer $k\ge3$ and every fixed real $A>0$.
\end{corollary}
\begin{proof}
For $r\ge2$, the inequality
$\lfloor\log_2r\rfloor\ge(\log r)/(2\log2)$ and
Theorem~\ref{main:intro} give, for all $k\ge K_0$,
\[
\inf_{\substack{r\in\Z\\r\ge2}}
\frac{\log W_r(k)}{k\log r}
\ge\frac{c}{2\log2}\log k.
\]
Theorem~\ref{transfer:large-r} gives, for all $r\ge256$,
\[
\inf_{\substack{k\in\Z\\k\ge3}}
\frac{\log W_r(k)}{\log r}
\ge\frac{\log r}{64\log2}.
\]
The right-hand sides tend to infinity. For fixed $r\ge2$,
Theorem~\ref{main:intro} also gives
$W_r(k)^{1/k}>k^{c\lfloor\log_2r\rfloor}\to\infty$.
For fixed $A>0$, Theorem~\ref{transfer:large-r} gives
\[
\log\frac{W_r(k)}{r^A}
>\frac{(\log r)^2}{64\log2}-A\log r\longrightarrow\infty,
\]
uniformly for integers $k\ge3$.
\end{proof}
The restrictions on the parameters are necessary: the exact values
$W_1(k)=k$, $W_r(1)=1$, and $W_r(2)=r+1$ are established along with
finiteness in Appendix~\ref{sec:upper}.
==== END Quantitative-Superexponential-Bounds-for-van-der-Waerden-Numbers//sections/07-transfers.tex ====
==== BEGIN Quantitative-Superexponential-Bounds-for-van-der-Waerden-Numbers//sections/08-upper.tex ====
\section{An elementary finite upper bound}
\label{sec:upper}
We record a coarse quantitative form of the classical block-and-focus
induction; see van der Waerden~\cite[pp.~142--145]{vanDerWaerden1998}.
The recursion below proves finiteness directly, involves only previously
defined integers, and applies to every positive number of colors.
\begin{theorem}
\label{upper:finite}
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
\begin{equation}
m_0=1,\qquad
m_{t+1}=2m_tF(r^{m_t},k-1)\quad(0\le t0$.
We claim, by induction on $t\in\{0,\ldots,r\}$, that every
$r$-coloring of an interval of length $m_t$ containing no monochromatic
$k$-term progression has a focus with $t$ colors. For $t=0$ this just
means choosing the single point in an interval of length $m_0=1$.
Assume the claim for $t