OpenAI's volgende model, Astra, loste zojuist tien decennia-oude open wiskundeproblemen op

Op 1 augustus publiceerde OpenAI een rapport waarin werd gesteld dat het volgende model, intern Astra genoemd, nieuwe resultaten had opgeleverd voor tien verschillende open problemen in de wiskunde. (Nee, het zijn niet de Millenniumprijs-problemen, maar ze zijn desondanks significant.)

Wat opvallend is: deze oplossingen zijn geen incrementele vooruitgang op de problemen; het zijn echte oplossingen, geverifieerd met Lean. (Lean is een programmeertaal en bewijshulp die elke stap van een wiskundig argument dwingt om in machineleesbaar detail te worden uitgeschreven.) 

Het is veel om in één keer te verwerken. In dit artikel heb ik de problemen per deelgebied geordend en op hoofdlijnen beschreven wat er is gebeurd, wat dit kan betekenen voor de wiskunde als vakgebied, en wat we verder over Astra kunnen afleiden.

Wat zijn de tien problemen?

Hier is elk resultaat, in gewone taal, samen met het specifieke deelgebied van de wiskunde of informatica waar het bij hoort.

Niet-sofische groepen

Deelgebied: Groepentheorie

Astra gaf een expliciete constructie van een groep die, hoe nauwkeurig ook, niet kan worden benaderd door grote eindige structuren — waarmee een vraag wordt gesloten die openstond sinds het concept van een "sofische" groep in 1999 werd geïntroduceerd. De constructie gaat vergezeld van een bewijs dat geen enkele reeks van eindige benaderingen ooit kan werken, geformaliseerd in Lean zodat de logica mechanisch kan worden gecontroleerd.

Wikipedia is al bijgewerkt:

Bolpakking

Deelgebied: Hoogdimensionale meetkunde

De vraag is hoe dicht identieke, niet-overlappende bollen kunnen worden opgestapeld naarmate het aantal dimensies toeneemt. Astra bewees een strakkere bovengrens voor die dichtheid in hoge dimensies, de eerste verbetering van deze specifieke grens sinds 1978. Het levert geen betere pakmethode op — het verkleint de marge voor hoe goed een toekomstige methode überhaupt kan zijn.

Binaire en sferische codes

Deelgebied: Coderingstheorie

Foutcorrigerende codes werken door geldige berichten ver genoeg uit elkaar te houden zodat kleine fouten het ene niet in het andere kunnen veranderen. Astra bewees aanzienlijk strakkere (exponentieel verbeterde) grenzen aan hoeveel van zulke berichten er kunnen bestaan voor een gegeven minimumafstand, met een overeenkomend resultaat voor punten die over een hoogdimensionale bol zijn verdeeld.

Connes’ rigiditeitsvermoeden

Deelgebied: Operatoralgebra’s

Alain Connes vermoedde dat bepaalde groepen altijd uniek konden worden gereconstrueerd uit een algebraïsche structuur, een von Neumann-algebra, die uit hen wordt opgebouwd. Astra weerlegde dit door twee wezenlijk verschillende groepen te produceren die tot dezelfde algebra leiden, waarmee wordt aangetoond dat de reconstructie niet altijd één-op-één is.

Rekenkundige circuitcomplexiteit

Deelgebied: Theorie van computationele complexiteit

De "permanent", een enkel getal berekend uit een rooster van getallen, is duur om te berekenen, en complexiteitstheoretici willen het minimumaantal rekenstappen weten dat een methode ooit nodig kan hebben. Astra bewees een nieuwe, sterkere ondergrens voor dat minimum — een notoir moeilijk soort resultaat om überhaupt te verbeteren.

Kwantaal parallell herhalen

Deelgebied: Kwantumcomplexiteitstheorie

De klassieke theorie zegt dat twee niet-communicerende spelers een moeilijk spel vele malen parallel laten herhalen, valsspelen exponentieel minder kans van slagen geeft. Astra bewees dat dezelfde garantie geldt zelfs wanneer de spelers kwantumverstrengeling delen, waarmee een fundamenteel klassiek principe naar de kwantumcontext wordt uitgebreid.

Closest vector problem

Deelgebied: Roostergebaseerde cryptografie

Gegeven een herhalend rooster van punten (een rooster) en een doellocatie, vraagt dit probleem om het dichtstbijzijnde roosterpunt — een probleem dat in hoge dimensies als zeer lastig wordt beschouwd, en daarom de basis vormt voor sommige kwantumbestendige versleuteling. Astra bewees dat zelfs het benaderen van het antwoord, binnen een specifieke polynomiale factor, aantoonbaar moeilijk blijft, wat de cryptografie die hierop is gebouwd verder versterkt.

Ehrharts volumevermoeden

Deelgebied: Discrete en convexe meetkunde

Voor een convexe vorm waarvan het enige inwendige roosterpunt precies in het massamiddelpunt ligt, wilden wiskundigen de maximaal mogelijke inhoud weten die zo’n vorm in een gegeven dimensie kan hebben. Astra bepaalde dat maximale volume voor elke dimensie en besliste het vermoeden in volle algemeenheid.

Multikleurige Ramsey-getallen

Deelgebied: Ramsey-theorie / combinatoriek

Met genoeg mensen en genoeg categorieën van relaties tussen hen, vind je uiteindelijk gegarandeerd drie mensen die allemaal verbonden zijn door dezelfde categorie. Astra bewees dat de minimale groepsgrootte die nodig is sneller groeit dan elk vast exponentieel tempo naarmate het aantal categorieën toeneemt, waarmee Erdős’ probleem 183 wordt opgelost.

Extremale getal-vermoedens

Deelgebied: Extremale grafentheorie

Deze tak van de wiskunde vraagt hoeveel verbindingen een netwerk kan hebben terwijl bepaalde kleine, verboden patronen toch worden vermeden. Astra besliste twee gerelateerde vermoedens hier, overeenkomend met Erdős’ problemen 146 en 180, en legde vast hoe dicht zulke netwerken kunnen worden voordat die patronen onvermijdelijk opduiken.

Elk van deze problemen stond al minstens tien jaar open; verschillende al dertig jaar of langer, waaronder problemen waar Turing Award-winnaars aan hebben gewerkt aan de theoretische CS-kant van de lijst.

Wacht, is een tegenvoorbeeld het “makkelijke” soort bewijs?

Wie ben ik om hier iets negatiefs over te zeggen, maar ik weet dat dit een veelgestelde vraag of reactie is, vooral van mensen die iets van wiskunde weten.

Het meest gehoorde punt van kritiek: meerdere van deze resultaten zijn tegenvoorbeelden in plaats van nieuwe algemene theorie. Dat punt is belangrijk, omdat een tegenvoorbeeld een ja/nee-vraag beantwoordt maar op zichzelf niet vertelt waarom het patroon faalt of je een familie vergelijkbare objecten aanreikt om daarna te bestuderen, terwijl zoiets als een classificatiestelling of een nieuwe techniek meer deuren opent.

Ik zou zeggen dat deze kritiek in het algemeen overeind blijft, maar het is geen blanket-ontslag van deze hele reeks problemen. Ten eerste is het resultaat over niet-sofische groepen geen kleine aanpassing aan een bestaande bijna-treffer — het is de eerste constructie in zijn soort na 27 jaar waarin niemand er ook maar één had, en de techniek erachter zal naar verwachting generaliseren om er meer te vinden.

Ten tweede zijn verschillende van de andere negen resultaten, waaronder de bolpakkingsgrens en de CVP-moeilijkheidsresultaten, helemaal geen tegenvoorbeelden; het zijn directe verbeteringen van bestaande grenzen. 

Wat nog onopgelost is

Een paar zaken zijn het volgen waard terwijl het veld dit in de komende dagen, weken en maanden fileert:

• Nog geen peerreview. Deze resultaten zijn Lean-geverifieerd en informeel beoordeeld door wiskundigen die preprints hebben gezien, maar geen is door een gerefereerd tijdschriftproces gegaan. 
• Auteurschap wordt nog onderhandeld. OpenAI zegt verantwoordelijkheid te nemen voor de manuscripten en Lean-formalisaties, terwijl de wiskundige argumenten zelf aan het model worden toegeschreven. Onafhankelijke reproductie van het proces (in tegenstelling tot verificatie van de bewijzen) is op dit moment lastig uit te voeren.

Wat dit betekent voor de wiskunde

De meest directe verschuiving zit in waar wiskundigen hun tijd daadwerkelijk aan kunnen besteden. Als je een goed afgebakend open probleem aan een model kunt voorleggen en het in Lean kunt checken, verschuift de bottleneck van "kan iemand dit oplossen" naar "hebben we de juiste vraag gesteld en correct geformaliseerd". Het vermogen om een goede vraag te formuleren en te weten welke de moeite waard is om aan te pakken, is een echte vaardigheid die wiskundigen met ervaring ontwikkelen. 

Er suddert ook een financierings- en geloofwaardigheidsvraag. Onderzoeksbeurzen, tenure-cases en prijzen waren historisch gebouwd rond schaarste: deze problemen waren moeilijk genoeg dat het oplossen ervan iets zei over de oplosser. Als door AI ondersteunde resultaten routine worden, zal het veld nieuwe manieren moeten vinden om te signaleren wat echt moeilijk is versus wat nu binnen bereik ligt van een paar duizend dollar aan inference. Natuurlijk begrijpt de gemiddelde persoon deze problemen niet volledig. De mensen met echte scholing wel, en dat verandert niet. Dus wiskundige kennis is waardevoller dan ooit. 

Hoe mensen reageren

De reactie op sociale media was minder verdeeld over of de bewijzen kloppen, en meer over waar ze bewijs van zouden zijn.

Sommigen lazen het tempo zelf als het echte verhaal: tien decennia-oude problemen die tegelijk landen, over niet-verwante deelgebieden heen, sneller dan experts ze überhaupt kunnen beoordelen. Een vraag voor de toekomst: "Gaan we dit allemaal kunnen bijbenen met controleren?"

Anderen werpen tegen dat dit minder zegt over AI in het algemeen dan het lijkt. Wiskunde is een zeldzaam domein waar het werk van een model automatisch en volledig kan worden gecontroleerd. De meeste real-world problemen bieden niet zo’n ingebouwde, automatische antwoordsleutel. Vanuit dat perspectief is de prestatie reëel, maar zegt ze misschien meer over wiskunde als uitzonderlijk geschikt voor AI.

Een derde lijn van commentaar: een correct bewijs dat nog niemand volledig heeft geaudit of doorgrond, is nog niet echt begrepen, slechts geverifieerd. Een stelling ontdekken en begrijpen wat die betekent, zijn in deze visie twee verschillende klussen.

Slotgedachten

Wiskundigen zeggen dat het resultaat over niet-sofische groepen eruitziet als het echte werk: een echt, decennia-oud open vraagstuk in de groepentheorie, gesloten door een expliciete constructie die wiskundigen in het veld serieus nemen. De andere negen resultaten vormen samen een brede en technisch substantiële tranche vooruitgang in de zuivere wiskunde.

Wat nog niet is gebeurd, is het langzamere deel: peerreview, reproductie van het zoekproces, en het veld dat hier daadwerkelijk op voortbouwt. Dat deel duurt langer dan een blogpost, en het is het deel dat ons echt zal vertellen hoe groot dit was. We houden je op de hoogte.