The order of long rainbow arithmetic progressions

Abstract

Let $T_k$ be the minimum positive integer $t$ such that, for every positive integer $n$, every equinumerous $t$-coloring of $[tn]$ contains a rainbow $k$-term arithmetic progression. Jungić, Licht, Mahdian, Nešetřil and Radoičić conjectured that $T_k=Θ(k^2)$, while Conlon, Fox and Sudakov proved that $T_k=O(k^2\log k)$. We prove the matching lower bound $T_k=Ω(k^2\log k)$, and hence $T_k=Θ(k^2\log k)$.

Disclosure

“12st = t(12s), this is a counterexample to the defining property of Tk with the positive integer n = 12s. Hence no such t satisfies that property, so Tk > ⌊ck 2 log k⌋. Since Tk is an integer, Tk > ck 2 log k. Acknowledgments Codex with GPT-5.6 and Claude Code with Fable 5 were used for proof exploration, proof criticism, exposition, and revision. References [1] V. Jungić, J. Licht, M. Mahdian, J. Nešetřil and R. Radoičić, Rainbow arithmetic progressions and anti-Ramse”

PDF page 11

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T18:55:50.997077Z

Structural counts