Onderzoekers hebben een nieuwe tool genaamd 'count-catcher' ontwikkeld die in staat is om certificaten van modeltellers om te zetten in formeel bewijsbare stellingen binnen de programmeertaal Lean. Hiermee kunnen complexe combinatorische vraagstukken met een hoge mate van wiskundige zekerheid worden aangetoond.
In een wetenschappelijk artikel dat op 26 oktober 2026 werd gepubliceerd via arxiv.org, presenteren Johannes K. Fichte en Stefan Szeider hun tool 'count-catcher'. De software richt zich op het proces van model counting, waarbij bepaald wordt hoeveel verschillende oplossingen (modellen) een specifieke logische formule in Conjunctive Normal Form (CNF) bezit. De tool slaat een brug tussen de output van de exacte modelteller 'd4' en de interactieve stellingbewijzer Lean.
Werking van de technologie
De kern van count-catcher is het vermogen om een zogenaamd CPOG-certificaat te verwerken. Dit certificaat bevat een Booleaanse schakeling die gelijkwaardig is aan de oorspronkelijke formule, samen met een bewijs van die gelijkwaardigheid. De tool voert vervolgens drie specifieke controles uit in Lean om de correctheid te waarborgen:
- Forward check: Hierbij wordt gecontroleerd of de formule de schakeling impliceert. Voor dit proces maakt de tool gebruik van 'lrat-catcher', die een welegging via de LRAT-checker van de standaardbibliotheek van Lean streamt.
- Reverse check: Er wordt geverifieerd of de schakeling de formule impliceert.
- Validiteitscontrole: De correctheid van de schakeling zelf wordt getoetst.
Omdat Lean deze controles uitvoert als gecompileerde code, is de uiteindelijke stelling afhankelijk van de kernel, de compiler en de runtime van de taal. Volgens de auteurs in de publicatie op is dit proces vergelijkbaar met de werking van de geverifieerde checker van CPOG.
Toepassingen en resultaten
De praktische waarde van count-catcher blijkt uit de mogelijkheid om combinatorische objecten te tellen. Door de tool te combineren met resultaten uit Mathlib, zoals het lemma van Burnside, kunnen onderzoekers bijvoorbeeld grafen tellen tot aan isomorfisme.
Een concreet voorbeeld dat in de wordt genoemd, is het berekenen van het aantal Latijnse vierkanten van orde 8. Dit resultaat werd bereikt als een gewogen som van honderden gecertificeerde tellingen, gebaseerd op ongeveer acht terabytes aan certificaten.
Daarnaast hebben de onderzoekers de tool getest op formules uit de Model Counting Competition van 2022. Ongeveer de helft van deze formules kon succesvol worden omgezet in Lean-stellingen. Opvallend is dat de drie controles van count-catcher slechts ongeveer een kwart van de tijd in beslag nemen vergeleken met de geverifieerde checker van CPOG.
Correcties en efficiëntie
Het project heeft niet alleen geleid tot een nieuwe tool, maar ook tot het ontdekken van fouten in bestaande systemen. De auteurs melden dat de niet-geverifieerde checker van CPOG onjuiste tellingen rapporteerde. Bovendien is de afhankelijkheid van twee onbewezen lemma's in de geverifieerde checker van CPOG verwijderd.
Wat betreft de kosten van het proces stellen de onderzoekers dat het genereren van een volledige stelling in Lean ongeveer evenveel middelen kost als een standaard gecontroleerde telling. Hoewel de tool zeer gespecialiseerd is, raakt het aan fundamentele begrippen van het tellen en berekenen, concepten die in algemene zin worden beschreven in bronnen zoals het cambridge.org, waar het tellen van objecten in een groep als basisactiviteit wordt gedefinieerd.
Hoewel andere bronnen zoals collinsdictionary.com geen specifieke technische details over deze software bevatten, onderstreept de publicatie op de verschuiving naar volledig geverifieerde computationele bewijzen in de theoretische informatica.