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.

What was already known

Mao, Ozeki, Robertson and Wang defined the thresholds. Quantavane’s earlier quadratic-residue colourings gave lower bounds of 53 for four and five colours.

AI involvement AI-led

Canli directed the project. He credits Claude agents with the search, the certificate checker and its soundness proof, and the Lean development.

Importance Notable

The matching upper bound determines three cases of the four-term monochromatic threshold and adds the three-colour case.

Technical verification Formal (Lean 4)

The submitted Lean proof checks the unsatisfiability certificate for 53 and the three explicit colourings for 52. The certificate checker is proved sound in Lean, so the SAT solver’s output need not be trusted.

Formal checking

The submitted Lean proof checks the unsatisfiability certificate for 53 and the three explicit colourings for 52. The certificate checker is proved sound in Lean, so the SAT solver’s output need not be trusted.

Checker
Lean 4 kernel and Comparator, as reported by Quantavane
Scope
Checked the upper bound via a certified LRAT checker, the three explicit witnesses and the resulting exact thresholds.
Basis
Reported by the linked checker

Human understanding Few

The account describes the SAT encoding but gives no named human explanation of the central certificate construction or proof.

Correction and publication history