Gallai–van der Waerden numbers
Colour the integers from 1 to n using exactly r colours. How large must n be before every such colouring contains either a k-term arithmetic progression with all its colours distinct or an l-term arithmetic progression of a single colour? The Gallai–van der Waerden number is the threshold beyond which this always happens.
Why it matters and what counts as progress
Why it matters: The problem asks how a single colouring can avoid two opposite kinds of order, one that repeats a colour and one that uses a different colour at every term.
What counts as progress: To raise a lower bound, construct a colouring that avoids both patterns at a larger n. To lower an upper bound, prove that every exact r-colouring must contain one of the two patterns. A matching pair gives the exact threshold.
How the problem developed
- 2023 · Problem definition [4]
Yaping Mao, Kenta Ozeki, Aaron Robertson and Zhao Wang Introduced the Gallai–van der Waerden numbers for exact colourings and gave bounds and exact cases.
- October 2026 · Exact thresholds [5]
Yuan Si Determined the thresholds when both progressions have three terms.
Arhan Canli and Claude agents Extended the quadratic residue idea to general power classes and proved new lower bounds for several four-term monochromatic cases.
Arhan Canli and Claude agents The registered Lean proof gives the threshold 53 for three, four and five colours when the rainbow progression has length three and the monochromatic progression has length four.
AI contributions 2
Exact Gallai–van der Waerden numbers: GW(r; 3, 4) = 53 for , 4, 5
For exactly three, four or five colours and every interval from 1 to n with n at least 53, any colouring contains a three-term progression in three different colours or a four-term progression in one colour. Explicit colourings of 1 to 52 avoid both patterns, giving the exact threshold 53 in all three cases.
Gallai–van der Waerden numbers from power-residue colourings
Let and with prime and . Assume no consecutive nonzero residues share an th-power class and that for each index from 0 to , the nonzero differences among those indices use fewer than classes. Quantavane’s constructions give and, given an exact -colouring of points with no rainbow -term progression, .
Sources
- Quantavane’s general power-residue constructions
- Lean build and checker results
- The earlier quadratic-residue construction
- Mao, Ozeki, Robertson and Wang, Arithmetic progressions, quasi progressions, and Gallai-Ramsey colorings
- Yuan Si, Complete Determination of the Gallai–van der Waerden Number GW(r;3,3)
- Quantavane’s exact Gallai–van der Waerden thresholds
- Exact theorem statements and provenance
- Lean challenge statements
Publication history
Exact Gallai–van der Waerden numbers: GW(r; 3, 4) = 53 for , 4, 5
Gallai–van der Waerden numbers from power-residue colourings
Daily emails by default, only when there’s an update.