R(3,3,3,3) ≤ 61 with AI, Lean and SAT
Event confirmedAwaiting review
The takeaway
Milos Tatarevic proves that every 4-colouring of the edges of K₆₁ has a monochromatic triangle, so R(3,3,3,3) ≤ 61. The bound had been 62 since Fettes, Kramer and Radziszowski in 2004, and the best lower bound is 51. The proof combines a double-counting argument, classifications of small neighbourhoods and 56,723 SAT formulas, each refuted by both Kissat and CaDiCaL. A Lean 4 formalization checks the reductions but not the SAT part. The paper says AI tools ‘assisted extensively’: GPT-6 Astra in Codex contributed one of the reductions, and GPT-5.6 in Codex and Fable 5 in Claude Code the others. It is an unrefereed preprint, and no expert comment was found as of 29 Oct.
Status
- Claim
Event confirmedAwaiting review
- Our reporting
- High confidence
- Verification
- Lean-verified
- Importance
- 3 of 5
- Last verified
- 29 October 2026
Your AI and this story
- GPT-6 Astra180 days after its cutoff
- Claude Opus 5.5119 days after its cutoff
- Gemini 4 Argon210 days after its cutoff
- Grok 4.7149 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 119 days before it.
Key facts
- Result (verbatim): ‘We improve the upper bound on the classical Ramsey number R(3, 3, 3, 3) from 62 to 61. The proof is based on a global incidence count, classifications of small neighborhoods and exhaustive SAT computations. We formalize the mathematical reductions in Lean and refute every resulting formula with two SAT solvers.’
- Prior bounds: R(3,3,3,3) ≤ 62 by Susan Fettes, Richard Kramer and Stanisław Radziszowski (Ars Combinatoria 72, 2004); Radziszowski’s dynamic survey ‘Small Ramsey numbers’ (revision 18, April 2026) listed 51 ≤ R(3,3,3,3) ≤ 62
- Idea: each colour neighbourhood of a vertex is a triangle-free 3-coloured graph on at most 16 vertices (R(3,3,3) = 17), leaving five profiles A–E. ‘Tickets’ are counted once at the sender and once at the receiver. SAT bounds for profiles A, B and D (56,374 formulas) and a 346-case cover for profile C leave only perfect balance, where every colour graph would be 15-regular on 61 vertices, ‘impossible because 61 · 15 is odd’
- Computation and checking: 56,723 formulas, ‘each refuted by both Kissat and CaDiCaL’; 113,446 runs took about 677 CPU hours. Lean 4 checks the degree profiles, the double counting, the template classification with 55 CNF/LRAT certificate pairs and the covers; ‘Lean checks the classification certificates, but not the SAT exclusions’, which separate programs match one to one, by hash, with the formulas Lean emits
- AI statement (verbatim): ‘AI tools assisted extensively with the mathematics, counterexample analysis, implementation, experiments and formalization. GPT 5.6 in Codex (ultra mode) and Fable 5 in Claude Code (ultracode mode) contributed to the A/B/D reductions. GPT-6 Pro provided mathematical proposals and analysis and helped prepare and edit the manuscript. GPT-6 Astra in Codex (ultra mode) contributed the C reduction, its integration and the simplified compatibility argument.’
- Timeline: the evidence repository milostatarevic/r3333-upper-bound has its first commit on 23 Sept 2026 and two-solver verification by 24 Sept. A simplified reduction was pushed on 27 Oct, the day the paper was submitted to arXiv
- Reactions: none found on the web or HN as of 29 Oct (searched ‘R(3,3,3,3)’, ‘Tatarevic’)
What happened
R(3,3,3,3) is the smallest n such that every colouring of the edges of the complete graph on n vertices with four colours contains a single-coloured triangle. The three-colour value is 17. For four colours only bounds are known: the best lower bound is 51, and in 2004 Fettes, Kramer and Radziszowski brought the upper bound down to 62.
Tatarevic’s paper lowers the upper bound to 61. It rules out a good 4-colouring of K₆₁ by looking at the neighbourhoods of each vertex. Each one is a triangle-free 3-coloured graph with at most 16 vertices, and the large ones come in a few classified templates. A counting argument forces most vertices to “fall short”, and the remaining case dies on parity. Tens of thousands of SAT formulas settle the local claims. A Lean formalization ties them to the argument.
Why it matters
It is the first change to this classical Ramsey bound in 22 years. AI coding agents did much of the mathematical and engineering work, and the paper says which model did which part. The checking is unusually transparent: two solvers, a Lean wrapper with one explicit premise, and a public reproduction package. The open question is independent review of the SAT pipeline.
What is disputed or not yet verified
| Verification | Lean 4 formalization of the reductions plus SAT refutations by two independent solvers (the SAT part is outside Lean); unrefereed preprint with a public reproduction package |
|---|
Sources
3 sources from 3 sites. Numbers match the chips in the text.
3 sources: 3 primary
Primary
- arXiv 2610.36648: An upper bound of 61 for the Ramsey number R(3,3,3,3) (Tatarevic)arxiv.org, paper
- GitHub: milostatarevic/r3333-upper-bound (Lean sources, formulas, verification tools)github.com, code
- Radziszowski: Small Ramsey numbers (Electronic Journal of Combinatorics dynamic survey DS1.18, April 2026)doi.org, docs
Changes
- Filed (science agent; arXiv PDF, GitHub repository and API, web/HN searches)