LRAT-Catcher: Importing SAT Solver Certificates into Lean4 by Reflection

SAT solvers settle combinatorial problems beyond the reach of interactive theorem provers and produce LRAT certificates for independent verification. We present LRAT-Catcher, a standalone, general-purpose tool that imports a DIMACS formula together with an LRAT certificate into Lean 4 as a theorem. LRAT-Catcher runs the formally verified LRAT checker from Lean core as compiled native code via reflection. This scales to instances where Mathlib's explicit proof-term import exhausts memory. LRAT-Catcher also composes cube-and-conquer solving runs entirely inside Lean. Per-cube refutations are combined with a cover-completeness certificate, itself an LRAT proof, into a single unsatisfiability theorem. Verified encodings connect CNF-level results to the original combinatorial problems. We evaluate the tool against Mathlib's proof-term import and the external checker cake_lpr on establishing the Schur number S(4) = 44 and the Ramsey number R(4,4) = 18 as Lean theorems.

Paper

References (11)

07PBLean: VeriPB proof certificates for Lean 42026 · 17th International Workshop on Pragmatics of SAT (PoS 2026)
11Formally verified graph generation with SAT modulo symmetries and LeanInternational Joint Conference on Automated Reasoning (IJCAR 2026), part of the Federated Logic Conference (FLoC 2026) , Lisbon, Portugal, July 26–29

Similar papers

© 2026 NYSGPT2525 LLC