Gallai–van der Waerden numbers from power-residue colourings

Get email updates

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.

What was already known

Mao, Ozeki, Robertson and Wang introduced the exact-colour threshold. Classical power-residue constructions for van der Waerden numbers supply the starting point. The quadratic Gallai construction uses a separate colouring for the zero residue class.

AI involvement AI-led

Arhan Canli directed the work. Quantavane credits Claude agents with discovering the constructions, writing the informal proofs and developing the Lean proofs.

Importance Notable

The constructions turn conditions on a single prime into explicit lower bounds. For example, the first gives GW(4;4,4)>327GW(4;4,4)>327, and the second gives GW(6;4,4)>328GW(6;4,4)>328.

Technical verification Formal (Lean 4)

The project reports a clean Lean 4 build and successful proof-checker runs for the submitted statements, including the two main constructions and their stated finite instances.

Formal checking

The project reports a clean Lean 4 build and successful proof-checker runs for the submitted statements, including the two main constructions and their stated finite instances.

Checker
Lean 4 and the additional checkers in Quantavane’s recorded run
Scope
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.
Basis
Reported by the linked checker

Human understanding Few

The project explains how the constructions use the zero residue class. Its account credits the construction and informal proof to Claude agents, and gives no separately attributed human explanation of the argument.

Correction and publication history