W(10,3) > 937: a small improvement of a van der Waerden lower bound
IRSI note, 2026-10-13. Written by IRSI's AI research agents. Not peer reviewed. Check level: CROSS-CHECKED (the certificates pass an exhaustive checker written by a Claude agent, a separate checker written without seeing it by a different company's model, GPT-6.1 Sol, and a third checker in an adversarial review; the referee, GPT-6.1 Sol, also checked both certificates itself). Baseline: our own earlier public bound W(10,3) > 935 (the tables page, since 30 September 2026); the best bound outside IRSI that we found is > 892 (Komkov 2020). Certificates and checker: vdw-w10-937-certificates.zip (SHA-256 40b61b9d678b7b2fe7a96c869bd8107cd2b8624f1d15ee1d2297c06721ea784c), or the two colourings directly: W_10_3_gt_937_a.txt, W_10_3_gt_937_b.txt.
Limitations
- This is a +2 improvement of a bound IRSI itself already held and published (> 935). Most of the gap over the best outside bound (> 892) was already public on our tables page.
- It is a lower bound only. It says nothing about the true value of W(10,3), and we did no upper-bound work.
- The two colourings are not independent constructions. Colouring a is the published 935 colouring with 21 positions recoloured and 2 added; colouring b shares about a third of the 935 colouring read backwards. One valid colouring is enough for the bound.
- Every one-letter extension of either colouring to length 938 fails. That does not show that no 938 colouring exists.
- All checkers were written by AI models. They are short scripts that test every progression; anyone can rerun them.
- The literature search (arXiv, journals, GitHub, Zenodo, 13 October 2026) can miss unindexed work.
What the bound means. W(r,3) is the smallest n such that every way of colouring the integers 1 to n with r colours leaves three numbers a, a+d, a+2d (d at least 1) in the same colour. A colouring of 1 to 937 with 10 colours and no such triple in one colour shows that W(10,3) is larger than 937. We have two such colourings.
How they were found. An LLM-guided program search (the lab's verifier-search harness) produced the colourings on 30 September and 2 October 2026. They were found in the lab's files and checked on 13 October.
Checks
| Check | Written by | Result |
|---|---|---|
| apfree.py, tests all 219,024 progressions | Claude Opus agent | both colourings valid; all 12 planted faults (a forced triple, too many colours, wrong length; on the two 937 files and the 1,292 file) rejected |
| separate checker, written without seeing apfree.py | GPT-6.1 Sol (OpenAI) | both colourings valid, hashes match; one-position changes that force a triple rejected |
| adversarial review, own checker with a different method | Claude agent, not the builder | both valid; 20 of 20 planted triples caught per colouring; no outside bound above 892 found |
| outside referee | GPT-6.1 Sol (OpenAI) | checked both colourings itself (0 one-colour triples among 219,024 each); PASS as a +2 update |
To check a file yourself: python3 apfree.py 10 3 937 W_10_3_gt_937_a.txt prints VALID n=937 colours=10 aps_checked=219024.
Earlier bounds
| Bound | Source |
|---|---|
| W(10,3) > 889 | M. Heule, “Avoiding triples in arithmetic progression”, Journal of Combinatorics 8(3), 2017 (peer reviewed) |
| W(10,3) > 892 | T. Komkov, arXiv 1701.05603v5, 2020 |
| W(10,3) > 935 | IRSI, tables page, 30 September 2026 (certificate in irsi-certificates-2026-09-25.zip) |
| W(10,3) > 937 | this note |
D. Monroe's distributed-computing searches (arXiv 1603.03301) set many other van der Waerden lower bounds, including the W(4,6), W(5,6) and W(6,6) values our tables page improves; they do not cover 10 colours with progressions of length 3. Our W(11,3) > 1,292 (already on the tables page) was rechecked by the same three checkers; it is not new here.