The canonical van der Waerden number 
is the least positive integer 
such that every coloring of 
, using any finite number of colors, contains
a 
-term
arithmetic progression with positive common difference that is either monochromatic
or rainbow. Monochromatic means that all terms have the same color, while rainbow
means that their colors are pairwise distinct. Here 
.
Erdős and Graham (1979) established the existence of 
using Szemerédi's
theorem. Such intervals give the canonical form of van
der Waerden's theorem. For example, 
,
since any two distinct points have either the same color or different colors.
In the notation 
for the ordinary van
der Waerden number,
 |
(1)
|
since a coloring with at most 
colors cannot contain a rainbow 
-term arithmetic progression.
Erdős and Graham (1979) asked whether
 |
(2)
|
This is problem 190 in the Erdős problems collection.
Bae (2026a) answered the question affirmatively by proving, for all sufficiently large 
,
 |
(3)
|
where 
, 
denotes big-O notation,
and 
is the natural logarithm of 
. Fox and Hunter (2026) independently resolved the question
and obtained the stronger lower bound
 |
(4)
|
where 
uses little-O notation as 
. The precise asymptotic growth of 
remains undetermined.
Bae's (2026b) registered Lean formalization, developed with AI assistance, proves the qualitative growth statement. Its formulation in terms of 
assumes the existence of a canonical interval for every
and does not include the quantitative lower bounds
above.
