🔢 mathematics

Automated conjecturing with \emph{TxGraffiti}

Dit artikel presenteert het ontwerp, de kernprincipes en de datagedreven methodologie van \emph{TxGraffiti}, een computerprogramma dat de generatie van wiskundige conjecturen automatiseert—met name binnen de grafentheorie—terwijl het de bijdragen aan de literatuur belicht en een nieuwe interactieve webinterface introduceert.

Oorspronkelijke auteurs: Randy Davila

Gepubliceerd 2026-05-12

📖 4 min leestijd🧠 Diepgaand

CC0 1.0

Oorspronkelijke auteurs: Randy Davila

Oorspronkelijk artikel vrijgegeven aan het publieke domein onder CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je een enorme, digitale bibliotheek voor gevuld met duizenden verschillende soorten puzzels (in dit geval wiskundige vormen die "grafieken" heten). Voor elke puzzel in de bibliotheek hebben wiskundigen al een lange lijst met statistieken berekend: hoeveel stukken het heeft, hoeveel verbindingen het maakt, en of het bepaalde vormen erin bevat.

TxGraffiti is een slim computerprogramma dat fungeert als een super-georganiseerde detective in deze bibliotheek. Zijn taak is niet om de puzzels voor jou op te lossen, maar om naar de statistieken te kijken en de regels te raden die ze beheersen.

Hier is hoe het werkt, opgesplitst in simpele stappen:

1. De "Snapshot"-bibliotheek

In plaats van dat de computer statistieken in de vliegend berekent (wat traag zou zijn), nemen de onderzoekers eerst een "snapshot" van de bibliotheek. Ze maken een gigantisch spreadsheet aan waarbij elke rij een puzzel is en elke kolom een statistiek. Dit spreadsheet is de "evidence base" (bewijsbasis). De computer raadt niet willekeurig; het kijkt alleen naar de feiten die al in dit spreadsheet zijn geschreven.

2. Het "Gokspel" (Het afstemmen van de lijn)

De computer kiest één statistiek die het wil voorspellen (laten we die de "Doel" noemen, zoals het aantal onafhankelijke stukken in een puzzel). Het kijkt vervolgens naar andere statistieken (de "Voorspellers") om te zien of ze kunnen helpen de Doel te raden.

Stel je voor dat je probeert te raden hoe lang een persoon is (Doel) op basis van hun schoenmaat (Voorspeller). De computer tekent een rechte lijn op een grafiek die precies boven alle mensen in het spreadsheet ligt. Het probeert deze lijn zo dicht mogelijk bij de mensen te houden zonder er ooit onder te gaan.

Als de lijn een persoon raakt, is die persoon een "perfect voorbeeld" van de regel.
De computer doet dit wiskundig voor elke mogelijke combinatie van statistieken om de strakste, meest accurate "plafond" (bovengrens) of "vloer" (ondergrens) te vinden.

3. De "Wall of Fame"-filter (De Dalmatiër-heuristiek)

De computer genereert duizenden van deze "lijnen" (regels). De meeste zijn saai of nutteloos. Bijvoorbeeld, het kan een regel vinden die waar is, maar zo losjes is dat het je niets nieuws vertelt.

Om dit op te lossen, gebruikt TxGraffiti een filter genaamd de Dalmatiër-heuristiek. Denk hierbij aan een curator voor een museum:

De computer kijkt naar een nieuwe regel.
Het vraagt zich af: "Legt deze regel een puzzel uit die nog door geen enkele andere regel is uitgelegd?"
Als het antwoord ja is, wordt de regel toegevoegd aan de "Wall of Fame".
Als het antwoord nee is (omdat een andere regel die puzzel al perfect dekt), wordt de nieuwe regel weggegooid als overbodig.

Dit zorgt ervoor dat de uiteindelijke lijst kort, scherp is en alleen de meest interessante ontdekkingen bevat.

4. Van Gok naar Bewijs

De output van TxGraffiti is een lijst van vermoedens. In de wiskunde is een vermoeden een "slimme gok" die waar lijkt op basis van het bewijs, maar nog niet is bewezen.

De Werkwijze: Een menselijke wiskundige kijkt naar de gok van de computer. Ze controleren of het logisch is. Ze proberen het te bewijzen met logica.
Het Succes: Het artikel noemt enkele echte voorbeelden waarbij TxGraffiti een gok deed, en menselijke wiskundigen het later bewezen tot een Stelling (een bewezen feit).
- Voorbeeld 1: De computer gokte dat bij bepaalde regelmatige vormen het aantal onafhankelijke stukken nooit groter is dan het aantal matchende paren. Mensen bewezen dat dit waar is.
- Voorbeeld 2: Het gokte een relatie tussen "zero forcing" (een specifieke manier om vormen in te kleuren) en "klauw-vrije" vormen. Mensen bewezen dit ook.

Waarom dit belangrijk is

Voordat systemen zoals deze bestonden, moesten wiskundigen jarenlang naar data staren om patronen te vinden. TxGraffiti automatiseert het deel van het "patroon spotten". Het vervangt de menselijke wiskundige niet; in plaats daarvan fungeert het als een krachtige telescoop, die de data scant om de mens te wijzen in de richting van de meest veelbelovende nieuwe wetten van het universum.

Kortom: TxGraffiti is een tool die een spreadsheet met wiskundige feiten neemt, de best mogelijke lijnen erdoorheen tekent, de saaie eruit filtert, en de resterende "slimme gissen" aan mensen overhandigt om ze om te zetten in bewezen wetten.

Technische Samenvatting van "Automated Conjecturing with TxGraffiti"

Probleemstelling
Het artikel behandelt de uitdaging van geautomatiseerd conjectureren: het genereren van wiskundig nuttige, niet-redundante en interpreteerbare ongelijkheden tussen numerieke invarianten van wiskundige objecten (specifiek grafen). Waar geautomatiseerd bewijzen van stellingen een volwassen veld is, heeft geautomatiseerde generatie van conjecturen historisch gezien te kampen gehad met het "te-veel-stellingen"-probleem, waarbij systematische enumeratie enorme aantallen database-waar maar triviale of redundante stellingen produceert. Het doel is om deze stellingen te filteren om die te identificeren die echte nieuwe informatie bieden (informativiteit) en geschikt zijn voor menselijke scrutiny en bewijs.

Methodologie
Het artikel introduceert TxGraffiti (Texas Graffiti), een op heuristiek en optimalisatie gebaseerd systeem dat werkt op een finite, versie-gemaakte snapshot-tabel van wiskundige objecten. In tegenstelling tot zijn voorgangers (Graffiti en Graffiti.pc), die invarianten dynamisch berekenen tijdens de zoektocht, behandelt TxGraffiti de bewijsbasis als een statisch artefact.

De conjecturele pijplijn bestaat uit de volgende fasen:

Data Curation (Snapshot Tabel):
- Er wordt een tabel geconstrueerd waarbij rijen objecten (grafen) vertegenwoordigen en kolommen vooraf berekende numerieke invarianten (bijv. onafhankelijkheidsgetal $\alpha$ , matching-getal $\mu$ ) en Booleaanse predicaten (bijv. "is connected", "is regular").
- De curatiestrategie prioriteert dekking boven willekeur, met name door het opnemen van extremale constructies, gelijkheidswitnesses (scherpe gevallen) en tegenvoorbeelden om ervoor te zorgen dat de tabel diagnostisch rijk is.
Kandidaatgeneratie via Optimalisatie:
- Voor een gekozen doel-invariante $\alpha$ en een Booleaans predicaat $P$ (hypothese), zoekt het systeem naar affiene grenzen van de vorm $\alpha \le mx + b$ of $\alpha \ge mx + b$ , waarbij $x$ een voorspellende invariante is.
- In plaats van complexe expressiebomen te enumereren, fixeert TxGraffiti een eenvoudige parametrische hypotheseklasse (univariate affiene grenzen) en past coëfficiënten aan door Lineaire Programma's (LP's) op te lossen.
- Bovenste Grens LP: Minimaliseert totale slack $\sum (mx_i + b - \alpha_i)$ onderworpen aan $\alpha_i \le mx_i + b$ voor alle rijen die voldoen aan $P$ .
- Onderste Grens LP: Maximaliseert totale slack (of minimaliseert negatieve slack) onderworpen aan $\alpha_i \ge mx_i + b$ .
- Het systeem ondersteunt ook multivariate grenzen en niet-lineaire relaties door het schema uit te breiden met afgeleide kolommen (bijv. $n-\mu$ , $\Delta^2$ ), hoewel de standaard webinterface prioriteit geeft aan modellen met één voorspeller voor interpreteerbaarheid.
Filtering (Static-Dalmatian Heuristiek):
- Om redundantie te beheren, hanteert TxGraffiti een static-Dalmatian heuristiek.
- Touch Number: Gedefinieerd als het aantal objecten in de snapshot waarbij de ongelijkheid geldt met gelijkheid (scherpe instanties).
- Selectielogica: Kandidaten worden gesorteerd op touch number. Een kandidaat wordt geaccepteerd als een "vertegenwoordiger" als deze ten minste één object raakt dat nog niet is gedekt door de scherpe sets van eerder geaccepteerde vertegenwoordigers. Als de scherpe set van een kandidaat identiek is aan die van een geaccepteerde vertegenwoordiger, wordt deze behouden als een "alias" (een verschillende syntactische vorm van dezelfde gelijkheidslocus). Kandidaten die geen nieuwe scherpe instanties toevoegen, worden verworpen.

Belangrijkste Bijdragen

Systeemarchitectuur: TxGraffiti wordt gepresenteerd als een modulair systeem dat beschikbaar is als een interactieve webapplicatie en een open-source Python-pakket (txgraffiti). Het ontkoppelt de berekening van invarianten van de generatie van conjecturen, waardoor snelle iteratie op vaste datasets mogelijk is.
Op Optimalisatie Gebaseerde Aanpassing: Het artikel verschuift het paradigma van grammatica-gebaseerde enumeratie (formules genereren en testen) naar optimalisatie-gebaseerde aanpassing (LP's oplossen om de strakste grenzen te vinden voor specifieke voorspellers). Dit zorgt ervoor dat gegenereerde kandidaten per constructie "table-true" zijn en geoptimaliseerd zijn voor strakheid.
Static-Dalmatian Filtering: De aanpassing van de Dalmatian-heuristiek aan een vaste snapshot maakt een single-pass, deterministisch filterproces mogelijk dat grenzen met hoge "touch" (veel scherpe witnesses) prioriteert terwijl redundantie wordt geëlimineerd.
Interpreteerbaarheid: Door de hypotheseklasse te beperken tot eenvoudige affiene templates en coëfficiënten te rationaliseren, produceert het systeem conjecturen die beknopt en menselijk leesbaar zijn.

Resultaten
Het artikel demonstreert de effectiviteit van het systeem via verschillende voorbeelden:

Workflow Illustratie: Met behulp van het totale domineringsgetal $\gamma_t$ genereerde het systeem een grens $\gamma_t(G) \ge \frac{2}{3}R(G)$ voor grafen met $\Delta(G) \le 3$ . Dit werd snel gegeneraliseerd tot een stelling die $\Delta(G)$ omvatte en bewezen werd met standaard schattingen.
Gestimuleerde Publicaties: Het artikel catalogiseert verschillende graph-theoretische resultaten die zijn ontstaan als TxGraffiti-conjecturen en vervolgens zijn bewezen:
- Onafhankelijkheid vs. Matching: De conjecture dat $\alpha(G) \le \mu(G)$ voor $r$ -regular grafen is bewezen in [51].
- Zero Forcing Grenzen: Verschillende ongelijkheden die zero forcing-getallen ( $Z, Z_t, Z_+$ ) relateren aan dominerings- en onafhankelijkheidsparameters, zijn geconjectureerd en bewezen, waaronder $Z(G) \le \beta(G)$ voor claw-free grafen en grenzen voor cubic grafen.
- Open Problemen: Het systeem identificeerde de conjecture $Z(G) \le \alpha(G) + 1$ voor connected grafen met $\Delta \le 3$ , wat een centraal open probleem blijft, hoewel er gedeeltelijke resultaten bestaan.

Betekenis en Claims
Het artikel positioneert TxGraffiti niet als een tool voor het autonoom ontdekken van diepe stellingen, maar als een gestructureerde bewijsgenerator die menselijk wiskundig onderzoek faciliteert.

Empirische Validiteit: Het systeem produceert "table-true" stellingen, wat betekent dat ze gelden voor alle instanties in de gecurateerde snapshot. De auteurs reserveren de term "stelling" expliciet voor stellingen die zijn vastgesteld door formeel bewijs, en onderscheiden de output van het systeem als conjecturen.
Filosofische Standpunt: Resonerend met het empirische perspectief van Fajtlowicz (die Graffiti ontwierp), betoogt het artikel dat het vermogen van machines om plausibele, diepe conjecturen te produceren een empirisch feit is dat het standpunt ondersteunt dat machines zinvolle deelnemers zijn in open-ended wiskundige ontdekking.
Schaalbaarheid en Reproduceerbaarheid: Door de snapshot-tabel te behandelen als een versie-gemaakt, auditabel artefact, adresseert TxGraffiti de robuustheidsproblemen van data-corruptie en zorgt ervoor dat conjecturen kunnen worden gereproduceerd en verfijnd naarmate de bewijsbasis groeit.

De auteurs concluderen dat, hoewel de huidige implementatie zich richt op graf-invarianten, het "snapshot-table paradigma" en de optimalisatie-en-filtering pijplijn breed toepasbaar zijn op elk domein waar objecten berekenbare kenmerken en predicaten toelaten.