CayleyPy Growth: Efficient growth computations and hundreds of new conjectures on Cayley graphs (Brief version)

Dit artikel introduceert CayleyPy, een snelle open-source Python-bibliotheek voor het berekenen van Cayley-graafgroei, die via AI honderden nieuwe conjectures oplevert over diameters en groeipatronen in groepentheorie.

De kern

CayleyPy: De Digitale Ontdekkingsreizigers die Wiskundige Mysteriën Oplossen

Stel je voor dat je een gigantisch, onmetelijk labyrint hebt. Dit labyrint is niet gemaakt van muren en gangen, maar van wiskundige regels. Elke hoek in dit labyrint is een specifieke situatie (een "toestand"), en elke deur die je kunt openen, is een simpele beweging die je kunt maken (een "generator"). In de wiskunde noemen ze dit een Cayley-grafiek.

Het probleem? Voor sommige van deze labyrinten zijn er meer hoeken dan er atomen in het heelal zijn. Het vinden van de kortste weg van punt A naar punt B (de "diameter" van het grafiek) is zo moeilijk dat het zelfs voor de slimste supercomputers van vandaag onmogelijk lijkt. Het is als proberen de kortste route te vinden door een doolhof van een miljard miljard gangen, terwijl je blindelings rondloopt.

Wat is CayleyPy?
De auteurs van dit paper hebben een nieuwe, slimme tool gebouwd genaamd CayleyPy. Je kunt het zien als een super-snelheidsschip voor computers, aangedreven door kunstmatige intelligentie (AI).

• De Oude Methode (GAP/Sage): Stel je voor dat je dit labyrint probeert te verkennen met een oude fiets. Je rijdt langzaam, je raakt snel moe, en bij grote labyrinten moet je stoppen omdat je fiets het niet meer aankan.
• De CayleyPy Methode: CayleyPy is als een hoge-snelheidstrein op magneetkussens. Het gebruikt krachtige grafische kaarten (zoals die in gaming-computers) om duizenden routes tegelijk te verkennen. Het is tot 1000 keer sneller dan de oude methoden en kan labyrinten aan die voor de oude methoden te groot waren.

Wat hebben ze ontdekt? (De Schat)
Met deze nieuwe trein hebben ze niet alleen snelheid gewonnen, maar ook de kaart van het labyrint beter begrepen. Ze hebben ongeveer 200 nieuwe wiskundige raadsels (vermoedens) opgelost of bedacht. Hier zijn de belangrijkste ontdekkingen, vertaald naar alledaags taal:

1. De "Quasi-Polynoom" Magie:
   Vaak denken wiskundigen dat het vinden van de kortste weg in zo'n labyrint een chaos is. CayleyPy heeft echter ontdekt dat de grootte van deze labyrinten vaak volgt op een heel strak patroon, afhankelijk van het getal $n$ (de grootte van het labyrint).

   • Analogie: Het is alsof je merkt dat de prijs van een huis niet willekeurig is, maar altijd precies $1000 \times$ het aantal kamers plus een klein bedrag, afhankelijk van of het jaar even of oneven is. Dit patroon maakt het mogelijk om de grootte van enorme labyrinten te voorspellen zonder ze helemaal te hoeven verkennen.

2. Het "Vierkant met Snorharen" Patroon:
   Ze zochten naar de slechtst mogelijke labyrinten (die met de langste kortste weg). Ze ontdekten dat de sleutels (de bewegingen) die deze moeilijke labyrinten maken, een heel mooi, herkenbaar patroon hebben: een vierkantje met twee takjes eruit.

   • Analogie: Het is alsof je merkt dat de slechtste puzzels in de wereld allemaal gemaakt zijn met dezelfde specifieke set Lego-blokjes in een bepaalde vorm. Als je die vorm kent, weet je dat je een heel moeilijke puzzel gaat oplossen.

3. Het Glushkov Raadsel (Opgelost na 50 jaar!):
   Er was een oud raadsel uit 1968 van een Sovjet-cyberneticus, V.M. Glushkov. Het ging over een specifieke manier om getallen te schuiven en te verwisselen. Niemand wist hoe groot het labyrint precies was.

   • De Oplossing: CayleyPy heeft berekend dat het antwoord een mooi wiskundig formule is. Het is alsof ze na 50 jaar eindelijk de sleutel vonden voor een deur die al die tijd dicht zat.

4. De "God's Number" voor Puzzels:
   Denk aan de Rubik's Cube. De "God's Number" is het aantal zetten dat je maximaal nodig hebt om elke mogelijke verwarde toestand op te lossen. Voor de standaard Rubik's Cube duurde het 40 jaar om dit te vinden. CayleyPy kan dit nu veel sneller berekenen voor veel andere, nog complexere puzzels.

Waarom is dit belangrijk voor jou?

• Voor de Wiskunde: Het opent de deur naar het begrijpen van groepen en structuren die we voorheen te groot vonden om aan te raken.
• Voor de Biologie: De bewegingen in deze labyrinten lijken op hoe DNA in levende organismen zich herschikt (bijvoorbeeld door stukken DNA om te draaien of te verplaatsen). Door de "routes" in deze wiskundige labyrinten te begrijpen, kunnen biologen beter begrijpen hoe evolutie werkt.
• Voor AI: Dit is een testbaan voor kunstmatige intelligentie. Als een AI kan leren hoe het kortste pad in een wiskundig labyrint vindt, kan diezelfde logica worden gebruikt voor robotica, verkeersstroom optimalisatie of het oplossen van complexe logistieke problemen.

Kortom:
De auteurs hebben een nieuwe, supersnelle motor gebouwd (CayleyPy) om door de diepste wiskundige doolhoven te racen. Ze hebben niet alleen de snelheid vergroot, maar ook nieuwe patronen gevonden die laten zien dat deze doolhoven minder chaotisch zijn dan we dachten. Ze hebben oude raadsels opgelost, nieuwe voorspellingen gedaan en de weg vrijgemaakt voor toekomstige ontdekkingen in zowel wiskunde als biologie.

Het is alsof ze van een fietsje zijn gestapt en een raket hebben gebouwd om de sterren te tellen.

Technische samenvatting

Titel: CAYLEYPY GROWTH: Efficiënte Groeiberekeningen en Honderden Nieuwe Vermoedens over Cayley-graaf

1. Probleemstelling

Cayley-graaf (en de bredere Schreier-coset-graaf) zijn fundamentele structuren in de groepentheorie met toepassingen in bio-informatica, cryptografie, kwantumcomputing en processor-netwerken. Twee centrale problemen in dit domein zijn:

• Diameterschattingsprobleem: Het bepalen van de diameter (de langste kortste pad tussen twee knopen) van een Cayley-graaf is in het algemeen een NP-hard probleem. Voor specifieke groepen, zoals de symmetrische groep $S_n$, zijn de exacte diameters vaak onbekend of slechts beperkt begrepen.
• Groeianalyse: Het begrijpen van de "groei" van een graaf (de verdeling van elementen op basis van hun afstand tot de identiteit) en het vinden van statistische patronen (zoals gemiddelde, modus en verdelingsvorm) is cruciaal, maar computationally zeer intensief voor grote groepen.
• Beperkingen van bestaande tools: Standaard computeralgebrasystemen zoals GAP en Sage zijn vaak te traag of hebben te weinig geheugen om groeiberekeningen uit te voeren voor groepen groter dan $S_{12}$ of $S_{13}$, wat onderzoek naar grotere $n$ en complexere generatoren blokkeert.

2. Methodologie

Het paper introduceert CayleyPy, een open-source Python-bibliothek die kunstmatige intelligentie (AI) en geavanceerde algoritmen combineert om deze beperkingen te overwinnen.

• CayleyPy Bibliotheek:
  • GPU-versnelling: De kern van de bibliotheek maakt gebruik van GPU's voor parallelle verwerking van breedte-voorwaartse zoekalgoritmen (BFS).
  • Efficiënte Datastructures: Gebruik van "bitmask"-representaties (3 bits per staat) om het geheugengebruik drastisch te verlagen, waardoor berekeningen voor groepen tot $S_{15}$ mogelijk worden.
  • Snelheid: CayleyPy is tot 1000 keer sneller dan GAP/Sage voor groeiberekeningen en kan groepen hanteren die orders van grootte groter zijn.
• AI-gebaseerde aanpak:
  • Het project gebruikt een pijplijn van: computationele experimenten $\rightarrow$ patroonherkenning $\rightarrow$ hypothesevorming $\rightarrow$ iteratie.
  • Deep Learning: Hoewel de huidige release zich richt op efficiënte BFS, bevat het ook componenten voor AI-gebaseerde padvinding (zoals beam search en diffusiemodellen) om elementen te ontbinden in generatoren (padvinding), zelfs voor groepen waar traditionele methoden falen.
• Benchmarking: De auteurs hebben meer dan 10 datasets gemaakt als Kaggle-uitdagingen om verschillende padvindingsmethoden te testen en de gemeenschap te betrekken.

3. Belangrijkste Bijdragen en Resultaten

A. Nieuwe Wiskundige Vermoedens (Conjectures)

Met behulp van CayleyPy hebben de auteurs ongeveer 200 nieuwe wiskundige vermoedens gegenereerd op basis van experimenten met bijna 50 verschillende Cayley-graaf. Belangrijkste bevindingen:

1. Quasi-polynoom Diameters:

   • De auteurs vermoeden dat de diameters van veel Cayley-graaf van $S_n$ en $A_n$ quasi-polynomen zijn in $n$ (d.w.z. een verzameling van polynomen die afhangen van $n \mod s$).
   • Dit is verrassend omdat het diametervindingsprobleem NP-hard is; als dit vermoeden klopt, biedt het een efficiënte manier om diameters te schatten door fitting op kleine $n$ waarden.

2. Verfijning van de Babai-vermoeden voor $S_n$:

   • Het klassieke Babai-vermoeden stelt dat de diameter $O(n^2)$ is.
   • De auteurs stellen een scherpere bovengrens voor: $n^2/2 + 4n$ voor standaard ongerichte Cayley-graaf van $S_n$.
   • Ze identificeren expliciete families van generatoren (involutions) die deze maximale diameter lijken te bereiken, gevolgd door een patroon dat ze "square-with-whiskers" (vierkant met snorharen) noemen.

3. Oplossing voor het Glushkov-probleem (1968):

   • Voor de gerichte Cayley-graaf gegenereerd door een linkse cyclische verschuiving ($L$) en de transpositie van de eerste twee elementen ($X$), wordt een exacte formule voor de diameter vermoed:
     • Voor oneven $n$: $(3n^2 - 8n + 9)/4$
     • Voor even $n$: $(3n^2 - 8n + 12)/4$
   • Dit probleem staat al decennia open en is een belangrijk resultaat van het project.

4. Nilpotente Groepen en Unitriangulaire Matrices:

   • Verbetering van resultaten van J.S. Ellenberg voor de diameter van unitriangulaire matrices over $\mathbb{Z}/p\mathbb{Z}$. Er wordt een lineaire afhankelijkheid van de diameter van $p$ vermoed.
   • De groei van nilpotente groepen volgt blijkbaar een Gaussische verdeling (centrale limietstelling), vergelijkbaar met resultaten van P. Diaconis voor $S_n$.

5. Generatoren met Maximaal Diameter:

   • Voor $n \le 15$ hebben ze exhaustive en gerandomiseerde zoektochten uitgevoerd. De generatoren met de grootste diameter blijken vaak involutions te zijn die het "square-with-whiskers" patroon volgen.
   • Specifieke nieuwe generatoren families zijn geïntroduceerd: 'Sheveleva2' (voor gerichte graaf) en 'Koltsov3involutions' (voor ongerichte graaf).

B. Biologische Toepassingen

• Analyse van Reversals (inversies) en Transposons (bloktransposities) op binaire coset-graaf.
• Vermoeden dat de groei van deze processen exact overeenkomt met expliciete formules (binomiale coëfficiënten) en dat de "God's number" (maximale afstand) gelijk is aan $\lfloor n/2 \rfloor$.

C. LLM ResearchArena (CayleyBench)

• De auteurs introduceren een nieuwe benchmark voor Large Language Models (LLM's). Het probleem wordt geformuleerd als een sorteeraalgoritme met beperkte operatoren.
• Resultaat: Huidige LLM's falen om correcte algoritmen te genereren voor niet-standaard generatoren, wat aantoont dat dit een uitdagende test is voor de onderzoeksvaardigheden van AI.

4. Significatie en Impact

• Schaalbaarheid: CayleyPy breekt de schaalbarrières van traditionele algebra-systemen, waardoor onderzoek naar groepen van de orde van $10^{40}$ (zoals $S_{15}$) en groter mogelijk wordt.
• AI voor Wiskunde: Het paper demonstreert succesvol hoe computationele experimenten, aangedreven door AI en GPU's, kunnen leiden tot nieuwe wiskundige inzichten en vermoedens in pure wiskunde, een gebied dat vaak als "te moeilijk" voor brute-force benaderingen werd beschouwd.
• Open Science: Door de code open-source te maken en de resultaten te publiceren via Kaggle, wordt de gemeenschap uitgedaagd om deze vermoedens te bewijzen of te weerleggen.
• Theoretische Vooruitgang: De verfijning van de Babai-vermoeden en de oplossing voor het Glushkov-probleem vormen een aanzienlijke bijdrage aan de groepentheorie en de theorie van Cayley-graaf.

Conclusie:
Het paper markeert een verschuiving in hoe complexe problemen in de groepentheorie worden aangepakt. Door de combinatie van geoptimaliseerde algoritmen, GPU-computing en AI-patronenherkenning, heeft het CayleyPy-project niet alleen de rekenkracht vergroot, maar ook een schat aan nieuwe wiskundige structuren en vermoedens onthuld die de basis kunnen vormen voor toekomstige wiskundige bewijzen.