Evolving Local Corrections for Global Constructions in Combinatorics

Dit artikel presenteert drie computationele case studies waarin het algoritme AlphaEvolve wordt gebruikt om lokale correctiestappen te ontdekken die bijdragen aan het oplossen van grote problemen in de combinatoriek, zoals grafreconstructie, het Alon-Tarsi-pariteitsprobleem en de Basisconjectuur van Rota.

De kern

Stel je voor dat je een enorme, ingewikkelde puzzel moet oplossen, maar je mag niet naar het volledige plaatje kijken. Je krijgt alleen duizenden kleine stukjes van de puzzel, elk met één stukje weggehaald. Je taak? Het originele plaatje reconstrueren op basis van die gebroken stukjes. Of denk aan het verdelen van kaarten in een spel waarbij je moet zorgen dat elke speler een perfecte hand krijgt, zonder dat er ooit twee dezelfde kaarten in één hand zitten.

Dit is wat wiskundigen al decennia proberen te doen met complexe problemen in de combinatoriek (de wiskunde van tellen en ordenen). De problemen zijn zo groot dat een computer ze niet "uit kan rekenen" door simpelweg alles te proberen.

In dit artikel beschrijft de auteur, Gergely Berczi, hoe hij een slimme AI genaamd AlphaEvolve heeft gebruikt om niet het antwoord te vinden, maar de regels te vinden om het antwoord te vinden.

Hier is de uitleg in gewone taal, met een paar creatieve vergelijkingen:

1. De Grote Idee: "Kleine Reparaties"

Stel je voor dat je een auto hebt die niet start. Je kunt de hele auto niet in één keer vervangen. In plaats daarvan kijk je naar kleine onderdelen: de bougie, de accu, de brandstofpomp. Als je één klein onderdeel vervangt, start de auto misschien nog niet, maar hij komt dichter bij het doel.

De kern van dit paper is dit principe: Hoe kun je een groot, onoplosbaar probleem oplossen door alleen kleine, lokale correcties toe te passen?
De AI (AlphaEvolve) zoekt niet naar het eindantwoord, maar leert een "reparatieplan". Het is alsof je een robot leert die weet: "Als er een foutje is, doe dan dit kleine dingetje om het een beetje beter te maken."

2. De Drie Puzzels die de AI oplost

De auteur liet de AI aan drie verschillende soorten "puzzels" werken:

A. De "Ontmasker"-Puzzel (Grafen Reconstructie)

• Het probleem: Je hebt een geheim netwerk (een graf) en je krijgt alleen foto's van dat netwerk waarbij telkens één persoon (een punt) is verdwenen. Kun je het oorspronkelijke netwerk reconstrueren?
• De analogie: Stel je voor dat je een groep vrienden hebt. Je krijgt foto's van de groep, maar op elke foto mist één persoon. Kun je op basis van wie er op de foto's staan en wie met wie praat, precies zeggen wie de vrienden van wie waren in het originele groepje?
• Wat de AI deed: De AI bedacht een slimme manier om te tellen: "Als persoon A op deze foto 3 vrienden heeft, en op die foto 4, dan moet de verdwenen persoon waarschijnlijk een vriend zijn van A." De AI leerde een algoritme dat deze kleine aanwijzingen combineert tot een volledig plaatje.

B. De "Pariteit"-Puzzel (Latijnse Vierkanten)

• Het probleem: Een Latijns vierkant is een bord waar je getallen in moet zetten, zodat in elke rij en kolom elk getal precies één keer staat (zoals Sudoku, maar zonder de blokjes). Wiskundigen willen weten of er altijd een oneven of even aantal manieren is om zo'n bord te vullen.
• De analogie: Stel je voor dat je een dansvloer hebt met dansparen. Je wilt weten of je de dansers altijd in paren kunt verdelen die precies tegenover elkaar staan. Soms werkt dat, soms niet. De AI probeerde een trucje te vinden: "Als ik twee rijen verwissel, verandert het even/oneven karakter van het hele bord."
• Wat de AI deed: De AI ontdekte een manier om kleine "ruilacties" (trades) te doen. Het leerde: "Als ik deze specifieke kleine groep getallen verwissel, draait de 'pariteit' (even/oneven) om." Het doel was om bijna alle mogelijke borden in paren te verdelen die elkaar opheffen, zodat alleen een paar "overblijvende" borden overbleven. Als die overblijvers allemaal hetzelfde teken hebben, is het probleem opgelost.

C. De "Rainbow"-Puzzel (Rota's Basis Conjecture)

• Het probleem: Je hebt $n$ groepen van $n$ vectoren (wiskundige pijlen). Elke groep is een perfecte set. Je wilt ze herschikken in een rooster van $n$ kolommen, zodat elke nieuwe kolom ook een perfecte set is, maar dan "regenboogkleurig" (één uit elke oorspronkelijke groep).
• De analogie: Stel je hebt 5 dozen met 5 verschillende kleuren sokken. In elke doos zit precies één sok van elke kleur. Je wilt de sokken herschikken in 5 nieuwe dozen, zodat in elke nieuwe doos ook precies één sok van elke kleur zit.
• Wat de AI deed: Dit is heel lastig omdat je soms een "perfecte" kolom moet opofferen om een vastgelopen situatie (een "valstrik") op te lossen. De AI leerde een strategie die zegt: "Als we vastlopen, durf dan een kleine stap terug te doen (een kolom op te breken) om een grotere valstrik te ontsnappen." Het leerde een balans tussen voorzichtig zijn en risicovol spelen.

3. Wat heeft dit ons opgeleverd?

De AI heeft geen wiskundige bewijzen gevonden. In de wiskunde moet je bewijzen dat iets altijd werkt, niet alleen dat het werkt op de 1000 voorbeelden die je hebt getest.

Maar wat de AI wel deed, is hypothese genereren.

• Het heeft ons laten zien hoe een oplossing eruit zou kunnen zien.
• Het heeft ons concrete regels gegeven die wiskundigen nu kunnen nemen en proberen te bewijzen met traditionele methoden.
• Het heeft laten zien dat deze enorme problemen vaak oplosbaar zijn door kleine, slimme stapjes, in plaats van door alles tegelijk te bekijken.

Conclusie: De AI als Ontdekkingsreiziger

Je kunt deze AI zien als een ontdekkingsreiziger in een dicht woud. De wiskundige (de auteur) zegt: "Er moet een pad zijn naar de top." De AI loopt niet direct naar de top, maar hij loopt rond, probeert paden, valt in putten, en leert: "Ah, als ik hier een tak opzij duw, kom ik een stukje verder."

Op het einde van de reis heeft de AI geen kaart van de hele berg getekend, maar hij heeft wel een stap-voor-stap routebeschrijving gevonden die er heel veelbelovend uitziet. De taak van de menselijke wiskundige is nu om die routebeschrijving te nemen en te bewijzen dat hij echt naar de top leidt.

Kortom: De AI is de uitvinder van de strategie, en de mens is de bewijzer dat die strategie werkt. Samen maken ze de wiskunde een stukje verder.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Evolving Local Corrections for Global Constructions in Combinatorics" van Gergely Berczi, in het Nederlands.

Titel: Het Evolueren van Lokale Correcties voor Globale Constructies in Combinatoriek

1. Het Probleem

Het artikel richt zich op drie beroemde open problemen in de combinatoriek die allemaal een gemeenschappelijke structuur delen: het bewijzen van het bestaan van objecten die voldoen aan strenge globale constraints, waarbij brute-force zoektochten computationeel onhaalbaar zijn. De drie specifieke problemen zijn:

1. Het Graph Reconstruction Conjecture (Ulam-Kelly): Kan een eindige simpele graaf uniek worden gereconstrueerd (tot op isomorfisme) uit de multiset van zijn subgrafieken die ontstaan door het verwijderen van één vertex (het "deck")? De focus ligt hier op bipartiete en planaire grafen.
2. De Alon-Tarsi Vermoeden: Voor een even getal $n$, is het verschil tussen het aantal even en oneven Latijnse vierkanten van orde $n$ ongelijk aan nul? Dit is een fundamenteel probleem dat verband houdt met het kleuren van grafen en determinanten.
3. Het Rota Basis Conjecture: Gegeven $n$ disjuncte bases van een matroid van rang $n$, kunnen deze worden herschikt in een $n \times n$ rooster zodat elke kolom ook een basis vormt? De experimenten focussen op lineaire matroiden over het veld $\mathbb{F}_2$.

De kernuitdaging is dat deze problemen vaak vereisen dat men een "globale constructie" vindt, maar dat de zoekruimte te groot is voor directe methoden.

2. Methodologie: AlphaEvolve

In plaats van traditionele wiskundige bewijzen te zoeken, gebruikt de auteur AlphaEvolve, een evolutionair zoekmodel ontwikkeld door Google DeepMind.

• Principe: In plaats van een numerieke parameter te optimaliseren, optimaliseert AlphaEvolve een Python-programma (een "evolvable block").
• Werking:
  • Een evaluatieroutine (harness) definieert de wiskundige regels en berekent een score voor een kandidaat-oplossing.
  • Het systeem genereert iteratief kleine wijzigingen in het programma dat de oplossing probeert te vinden.
  • De zoekstrategie is gebaseerd op het idee van lokale correcties: een globale constructie wordt opgebouwd door een reeks kleine, lokale stappen (correcties) die de "energie" of "defect" van de huidige configuratie verlagen.
• Rol van AI: De AI fungeert als een generator van expliciete hypothesen en algoritmen. Het levert geen bewijzen, maar produceert concrete algoritmen en structurele patronen die door wiskundigen kunnen worden geanalyseerd en geformaliseerd.
• Validatie: De auteurs benadrukken dat de resultaten experimenteel zijn. De AI-summarisies helpen bij het identificeren van patronen, maar de wiskundige conclusies en conjectures zijn het resultaat van menselijke analyse van de gegenereerde code.

3. Belangrijkste Bijdragen en Resultaten

A. Graph Reconstruction (Grafische Reconstructie)

• Bipartiete Grafen: AlphaEvolve ontdekte een algoritme dat bipartiete grafen perfect reconstrueert uit hun deck. Het algoritme werkt door:
  1. Het reconstrueren van globale graden en "neighbor-degree profiles" (de verdeling van de graden van buren).
  2. Het groeperen van vertices in "types" gebaseerd op deze profielen.
  3. Het oplossen van een toewijzingsprobleem (min-cost flow) binnen deze type-blokken, gebruikmakend van compatibiliteitsscores van subgrafieken met twee verwijderde vertices.
  • Resultaat: Perfecte reconstructie op een benchmark van 1420 gevallen.
  • Conjecture: Voor generieke, 2-verbonden, niet-reguliere bipartiete grafen met hoge minimale graad, bepaalt het deck de graaf uniek via deze lage-orde invarianten.
• Planaire Grafen: Voor planaire grafen (minimale graad $\ge 3$, niet-maximaal planair) vond de AI een snelle exacte verificatie-algoritme.
  • Methode: Gebruikmakend van de eigenschap dat planaire grafen altijd een vertex met graad $\le 5$ hebben, enumerateert het algoritme kleine sets van kandidaat-buren en verifieert deze via exacte deck-gelijkheid.
  • Resultaat: Perfecte reconstructie op een geharde testset.

B. Alon-Tarsi Vermoeden (Pariteit van Latijnse Vierkanten)

• Aanpak: De zoektocht richtte zich op het vinden van een teken-omkerende involutie (sign-reversing involution) op de meeste Latijnse vierkanten, zodat de resterende verzameling (residual set) een dominant teken heeft.
• Ontwikkeling:
  • Experiment 1 vond een map die bijna perfect werkt: het paar bijna alle vierkanten met een tegengesteld teken, met een zeer kleine restverzameling die volledig uit één tekenklasse bestaat.
  • Experiment 2 en 3 verfijnden dit door lokale "trades" (cyclische verwisselingen) te gebruiken die gebaseerd zijn op oneven cycli in permutaties van rijen/kolommen/symbolen.
  • De AI ontdekte strategieën die "stabiliteit" garanderen (zodat $F(F(L)) = L$) en gebruikte isotopieën (permutaties van rijen/kolommen/symbolen) om overfitting te voorkomen.
• Resultaat: Voor $n \ge 10$ werd een map gevonden die een teken-omkerende involutie is op de volledige dataset, met een residual set die een niet-nul som heeft.
• Conjecture: Er bestaat een deterministische scan volgorde van "two-line cycle trades" die een involutie vormt met een residual set die de Alon-Tarsi conjectuur bewijst.

C. Rota Basis Conjecture

• Aanpak: De zoektocht was gericht op het vinden van een greedy local-exchange policy (een scoring-functie) die een reeks lokale verwisselingen (inserts en repairs) leidt naar een volledige set van transversale bases.
• Resultaten:
  • Voor rang 5 en 7 (over $\mathbb{F}_2$) vond de AI policies die 100% succes behaalden op uitdagende "trap" instances (met veel korte afhankelijkheidscircuits).
  • De policies gebruiken een dynamische scoring die "trap energy" (gebaseerd op circuitgrootte) en "pressure" (gebaseerd op voortgang) combineert. Ze staan "heroic sacrifices" toe: het opzettelijk breken van een volledige kolom om een diep structureel probleem (trap) op te lossen.
  • Experiment C toonde aan dat een schaalbewuste policy werkt voor variabele rangen (5 tot 13).
• Conjecture: Er bestaat een deterministische de-randomisatie van deze policies die werkt voor alle rangen op circuit-rijke pools.

4. Significatie en Conclusie

Dit artikel vertegenwoordigt een paradigmaverschuiving in de experimentele wiskunde:

1. Van Bewijs naar Constructie: Het doel is niet direct het leveren van een bewijs, maar het genereren van expliciete algoritmen en structurele patronen die als uitgangspunt dienen voor traditionele wiskundige analyse.
2. Lokale Correcties als Heuristiek: Het paper toont aan dat complexe globale constructies vaak kunnen worden benaderd door het evolueren van lokale correctiestrategieën (zoals het oplossen van kleine conflicten in plaats van het oplossen van het hele probleem in één keer).
3. AI als Wiskundige Partner: AlphaEvolve fungeert als een krachtig instrument om de "energielandschappen" van combinatorische problemen te verkennen, waardoor nieuwe conjectures en bewijsstrategieën (zoals specifieke involuties of reconstructie-algoritmen) aan het licht komen die voor de mens misschien niet direct zichtbaar waren.

De auteurs concluderen dat hoewel de AI geen theorema's bewijst, het wel een "generator van expliciete hypothesen" is die de weg effent voor toekomstige wiskundige doorbraken in deze moeilijke gebieden.