← @bgSponge

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.

  1. 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.

  2. 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

  3. 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

  4. 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

  5. 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.

More from @bg

All readings →