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

  1. 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.

  2. October 2026 · Exact thresholds [5]

    Yuan Si Determined the thresholds when both progressions have three terms.

  3. 12 Nov 2026 · Power-residue lower bounds [1][2][3]

    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.

  4. 13 Nov 2026 · Exact thresholds [6][7]

    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 r=3r = 3, 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.

AI involvementAI-led
ImportanceNotable
Technical verificationFormal (Lean 4)
Human understandingFew
Reported

Gallai–van der Waerden numbers from power-residue colourings

Let m≥2m \geq 2 and p>l≥2p>l \geq 2 with pp prime and p≡1(modm)p \equiv 1 \pmod m. Assume no ll consecutive nonzero residues share an mmth-power class and that for each index ii from 0 to mm, the nonzero differences j−ij-i among those indices use fewer than mm classes. Quantavane’s constructions give GW(m+1;m+1,l)>(l−1)pGW(m+1;m+1,l)>(l-1)p and, given an exact ss-colouring of ll points with no rainbow (m+1)(m+1)-term progression, GW(m+s;m+1,l)>(l−1)p+1GW(m+s;m+1,l)>(l-1)p+1.

AI involvementAI-led
ImportanceNotable
Technical verificationFormal (Lean 4)
Human understandingFew
Reported

Sources

  1. Quantavane’s general power-residue constructions
  2. Lean build and checker results
  3. The earlier quadratic-residue construction
  4. Mao, Ozeki, Robertson and Wang, Arithmetic progressions, quasi progressions, and Gallai-Ramsey colorings
  5. Yuan Si, Complete Determination of the Gallai–van der Waerden Number GW(r;3,3)
  6. Quantavane’s exact Gallai–van der Waerden thresholds
  7. Exact theorem statements and provenance
  8. Lean challenge statements
Publication history