Long rainbow arithmetic progressions

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

For integers $k\geq3$, $t\geq1$ and $n\geq1$, an equinumerous $t$-coloring is a map $c:\{1,\ldots,tn\}\to\{1,\ldots,t\}$ with exactly $n$ integers of each color. A rainbow $k$-term arithmetic progression is a sequence $a,a+d,\ldots,a+(k-1)d$ lying in that interval, with integer $d\geq1$, on which all $k$ colors are distinct. Define $T_k$ to be the least $t$ such that every equinumerous $t$-coloring has a rainbow $k$-term progression for every $n\geq1$.

Statement recorded in the supplied source.

Is $T_k=\Theta(k^2)$ as $k\to\infty$? Explicitly, do constants $c,C>0$ and $k_0$ exist such that $ck^2\leq T_k\leq Ck^2$ for every integer $k\geq k_0$? [S2]

Short English statement

Does the number of equal-size color classes needed to force a long rainbow arithmetic progression grow quadratically with its length?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3038 (OPG-426). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Jesse Geneson, The order of long rainbow arithmetic progressions, arXiv:2607.15116 (2026), §1 and Theorem 1. Theorem 1 gives $T_k=\Theta(k^2\log k)$, refuting the recorded quadratic-order conjecture. https://arxiv.org/abs/2607.15116.