← All papers
First page of count-catcher: Lean Theorems from Model Counting Certificates

count-catcher: Lean Theorems from Model Counting Certificates

Johannes K. Fichte, Stefan Szeider

cs.LO Oct 26, 2026 · v1 cs.AI
Builds a Lean tool that checks CPOG model-counting certificates in Lean, yielding verified count theorems combined with Mathlib results such as Burnside's lemma.
We present count-catcher, a tool that turns a CPOG certificate of a count by the exact model counter d4 into a Lean theorem that a CNF formula defined in Lean has exactly N models over V variables. With an encoding lemma, this theorem becomes a theorem about the number of combinatorial objects. A CPOG certificate consists of a Boolean circuit equivalent to the formula and a proof of equivalence. count-catcher checks in Lean that the formula implies the circuit (forward check) and the circuit implies the formula (reverse check). For the forward check, lrat-catcher streams a refutation through the LRAT checker of Lean's standard library. The reverse check and the validity check of the circuit are computations proved correct in Lean. Lean runs all three checks as compiled code, so the theorem depends on Lean's kernel, compiler and runtime, as does CPOG's verified checker. We combine the theorem with results from Mathlib, for instance with Burnside's lemma to count graphs up to isomorphism. We prove the number of Latin squares of order 8 as a weighted sum of hundreds of certified counts from about eight terabytes of certificates. We turn about half of the 2022 Model Counting Competition formulas into theorems, with the three checks taking about a quarter of the time of CPOG's verified checker. We found that CPOG's unverified checker reported wrong counts, and removed its verified checker's dependence on two unproved lemmas. End to end, a theorem costs about the same as a checked count.

Exact counts of combinatorial objects are often obtained with unverified model counters, and published counts have historically been wrong. Earlier certified counting either ends in a checked output number rather than a theorem, or relies on enumeration, which does not scale to large counts.

count-catcher turns a CPOG certificate from the d4 model counter into a Lean theorem stating that a CNF formula, given as a Lean term, has exactly N models over V variables. Three checks run in Lean as compiled code: a forward check that streams an LRAT refutation through Lean's standard-library checker, and a reverse check and a circuit validity check, both proved correct in Lean. User-supplied encoding lemmas then turn model counts into theorems about objects. Counts can be composed with Mathlib results, for example Burnside's lemma for counting graphs up to isomorphism.

The tool proves the number of Latin squares of order 8 from 737 certified counts (about 8 TB of certificates), along with Dedekind's number M(7) and several OEIS values. It turns about half of the 2022 Model Counting Competition formulas into theorems, with checks taking about a quarter of the time of CPOG's verified checker. The work also found wrong counts reported by CPOG's unverified checker and removed two unproved lemmas from its verified checker.

TheoremSummandsCountLean (s)
Triangle-free graphs on 10 vertices4212,17274.8
Latin squares of order 746.15e1364.0
Latin squares of order 87371.09e20325,252
Dedekind's number M(7)12.41e1288.8
Selected theorems about mathematical objects