Proving at Scale for Universal Algebra
Summary
SEMIBASE uses LLM-guided agents and a Lean kernel to formally certify finite identity bases for all 15,973 semigroups of order 6.
Agents automate proof search.
Codex agents perform approximately 2,260 sessions to find proofs, which a Claude referee agent rebuilds before the Lean kernel performs a final audit.
Family proofs reduce size.
Most semigroups use a shared basis and subdirect decomposition, keeping family proofs under 10,000 lines, whereas individual generated proofs can exceed 100,000 lines.
Family proofs, written by agents, are much shorter
Proof difficulty is long-tailed.
The majority of order 6 semigroups were sealed quickly, but the final 390 required 23 additional days and significant structural analysis.
The hardness of the proofs is strongly long-tailed
Nonfinitely based proofs use word properties.
For the four known nonfinitely based semigroups, proofs show that a specific property of words survives any derivation step using identities with at most k variables.
a property of words that separates u from v
Certified bases settle inclusion orders.
By evaluating certified bases on variety generators, the project confirmed 13,321 inclusions and established the complete inclusion order for 505 varieties.
The complete order has 13,325 strict inclusions
Read the original ↗Save to your Sponge
Summarized with Sponge. Quotes are the author’s own words.