Een OpenAI-model heeft een centrale conjectuur in de discrete meetkunde weerlegd

Al bijna 80 jaar bestuderen wiskundigen een bedrieglijk eenvoudige vraag: als je $n$ punten in het vlak plaatst, hoeveel paren punten kunnen dan precies op afstand $1$ van elkaar liggen?

Dit is het probleem van de eenheidsafstanden in het vlak, voor het eerst geformuleerd door Paul Erdős in 1946. Het is een van de bekendste vragen in de combinatorische meetkunde, eenvoudig te formuleren en opmerkelijk moeilijk op te lossen. Het boek Research Problems in Discrete Geometry uit 2005, van Brass, Moser en Pach, noemt het 'mogelijk het bekendste (en het eenvoudigst uit te leggen) probleem in de combinatorische meetkunde'. Noga Alon, een vooraanstaand combinatoricus aan Princeton, beschrijft het als 'een van de favoriete problemen van Erdős.' Erdős loofde zelfs een geldprijs uit voor het oplossen van dit probleem.

Vandaag delen we een doorbraak rond het eenheidsafstandsprobleem. Sinds Erdős’ oorspronkelijke werk was de heersende opvatting dat de verderop afgebeelde constructies met een "vierkant raster" in wezen optimaal waren voor het maximaliseren van het aantal paren op eenheidsafstand. Een intern OpenAI-model heeft deze lang bestaande conjectuur weerlegd en een oneindige familie van voorbeelden geleverd die een polynomiale verbetering opleveren. Het bewijs is gecontroleerd door een groep externe wiskundigen. Zij hebben ook een begeleidend artikel geschreven dat het argument uitlegt en meer achtergrond en context biedt over het belang van het resultaat.

Het resultaat is ook opmerkelijk vanwege de manier waarop het werd gevonden. Het bewijs kwam van een nieuw algemeen redeneermodel, niet van een systeem dat specifiek voor wiskunde was getraind, speciaal was ingericht om bewijsstrategieën te doorzoeken of gericht was op het eenheidsafstandsprobleem. Als onderdeel van een bredere inspanning om te testen of geavanceerde modellen kunnen bijdragen aan grensverleggend onderzoek, evalueerden we het op een verzameling problemen van Erdős. In dit geval produceerde het een bewijs dat dit open probleem oploste.

Dit bewijs is een belangrijke mijlpaal voor de wiskunde- en AI-gemeenschappen. Het is de eerste keer dat een prominent open probleem, centraal in een deelgebied van de wiskunde, autonoom door AI is opgelost. Het laat ook zien hoe diepgaand deze systemen inmiddels kunnen redeneren. Wiskunde biedt een bijzonder helder testbed voor redenering: de problemen zijn precies, mogelijke bewijzen kunnen worden gecontroleerd, en een lang argument werkt alleen als de redenering van begin tot eind standhoudt. Ook de methode waarmee het probleem werd opgelost is opmerkelijk. Het bewijs zet onverwachte, verfijnde ideeën uit de algebraïsche getaltheorie in op een elementaire meetkundige vraag.

Fieldsmedaillewinnaar Tim Gowers noemt het resultaat in het begeleidende artikel "een mijlpaal voor AI in de wiskunde". Volgens de vooraanstaande getaltheoreticus Arul Shankar "laat dit artikel naar mijn mening zien dat huidige AI-modellen meer zijn dan alleen hulpmiddelen voor wiskundigen: ze zijn in staat originele en ingenieuze ideeën te bedenken en die vervolgens succesvol uit te werken".

Het bewijs is hier⁠(opent in een nieuw venster) beschikbaar. Het begeleidende artikel van vooraanstaande externe wiskundigen is hier⁠(opent in een nieuw venster) beschikbaar. Hier⁠(opent in een nieuw venster) vind je een verkorte versie van de chain-of-thought van het model.

Laat $u(n)$ het grootst mogelijke aantal paren op eenheidsafstand tussen $n$ punten in het vlak zijn. Voorbeelden die een lineaire groeisnelheid halen zijn eenvoudig te construeren: plaats je $n$ punten op een lijn, dan krijg je $n-1$ paren, terwijl een vierkant raster ongeveer $2n$ paren geeft. De voorheen beste bekende constructie, afkomstig van een herschaald vierkant raster, blijkt nog meer op te leveren: $n^{1 + C / \log \log(n)}$ voor een constante $C$. Omdat $\log \log(n)$ met $n$ naar oneindig gaat, gaat de extra term in de exponent naar $0$, wat betekent dat deze constructies slechts iets sneller dan lineaire groei bereiken. Decennialang werd algemeen aangenomen dat deze groeisnelheid in wezen de best mogelijke was, en dat geen enkele constructie een significante verbetering ten opzichte van het vierkante raster kon opleveren. In technische termen formuleerde Erdős het vermoeden van een bovengrens van $n^{1+o(1)}$, waarbij de extra term $o(1)$ een term aanduidt die met $n$ naar $0$ gaat.

Ons nieuwe resultaat weerlegt dit vermoeden. Preciezer gezegd construeert het bewijs voor oneindig veel waarden van $n$ configuraties van $n$ punten met ten minste $n^{1+\delta}$ paren op eenheidsafstand, voor een vaste exponent $\delta > 0$. (Het oorspronkelijke AI-bewijs geeft geen expliciete $\delta$, maar een komende verfijning van de hand van Princeton-hoogleraar wiskunde Will Sawin heeft laten zien dat men $\delta=0.014$ kan nemen.)

De geschiedenis van het probleem helpt om te begrijpen waarom het resultaat verrassend is. De beste bekende ondergrens was sinds Erdős’ oorspronkelijke constructie uit 1946 in wezen onveranderd gebleven. De beste bekende bovengrens, $O(n^{4/3})$, gaat terug op werk van Spencer, Szemerédi en Trotter uit 1984, en ondanks latere verfijningen en verwant structureel werk van Székely, Katz en Silier, Pach, Raz en Solymosi en anderen is de bovengrens in wezen onveranderd gebleven. Als bewijs ten gunste van het vermoeden bestudeerden Matoušek en Alon-Bucić-Sauermann het probleem met niet-Euclidische afstanden in het vlak, en bewezen ze dat 'de meeste' van deze niet-Euclidische afstanden in zekere zin aan het vermoeden voldoen.

Verrassend genoeg komen de belangrijkste ingrediënten van de constructie uit een heel ander deel van de wiskunde, de algebraïsche getaltheorie, die begrippen bestudeert zoals factorisatie in uitbreidingen van de gehele getallen die algebraïsche getallenlichamen worden genoemd.

Op hoofdlijnen begint het bewijs met een vertrouwd meetkundig idee en duwt het dat in een onverwachte richting.

Erdős’ oorspronkelijke ondergrens kan worden begrepen via de Gaussische gehele getallen: getallen van de vorm $a+bi$, waarbij $a$ en $b$ gehele getallen zijn en $i$ de vierkantswortel van $-1$ is. De Gaussische gehele getallen breiden de gewone gehele getallen uit en hebben, net als die, eigenschappen zoals unieke ontbinding in priemfactoren. Dergelijke uitbreidingen van de gewone gehele getallen of rationale getallen staan bekend als algebraïsche getallenlichamen. Het nieuwe argument vervangt de Gaussische gehele getallen door ingewikkeldere generalisaties uit de algebraïsche getaltheorie met rijkere symmetrieën die veel meer verschillen van eenheidslengte kunnen creëren.

Het precieze argument gebruikt hulpmiddelen zoals oneindige klasseveldtorens en de Golod-Shafarevich-theorie om te laten zien dat de voor het argument vereiste getallenlichamen daadwerkelijk bestaan. Deze ideeën waren goed bekend bij algebraïsche getaltheoretici, maar het kwam als een grote verrassing dat deze concepten implicaties hebben voor meetkundige vragen in het Euclidische vlak.

Dit resultaat markeert een belangrijk moment in de wisselwerking tussen AI en wiskunde: een AI-systeem heeft autonoom een lang bestaand open probleem opgelost dat centraal staat in een actief vakgebied. Het biedt ook een vroege glimp van een nieuw soort samenwerking tussen AI en menselijke wiskundigen. In dit geval schetst het begeleidende werk van externe wiskundigen een aanzienlijk rijker beeld dan de oorspronkelijke oplossing alleen.

Zoals Thomas Bloom in de begeleidende notitie schrijft:

"Wanneer ik het belang en de invloed van een door AI gegenereerd bewijs beoordeel, stel ik mezelf de vraag: heeft dit ons iets nieuws over het probleem geleerd? Begrijpen we discrete meetkunde nu beter? Ik denk dat het antwoord een gematigd ja is: dit laat zien dat getaltheoretische constructies veel meer over dit soort vragen te zeggen hebben dan we vermoedden; bovendien kan de vereiste getaltheorie zeer diepgaand zijn. Ongetwijfeld zullen veel algebraïsche getaltheoretici de komende maanden andere open problemen in de discrete meetkunde nauwkeurig bekijken."

De onverwachte verbinding tussen algebraïsche getaltheorie en discrete meetkunde die door de oplossing wordt onthuld, is een deel van wat het resultaat opmerkelijk maakt. Het beslecht niet simpelweg een specifieke conjectuur, maar kan wiskundigen een brug bieden om verdere verwante problemen te gaan verkennen.

Bloom wijst ook op een bredere mogelijkheid:

"De grenzen van kennis zijn erg grillig, en ongetwijfeld zullen de komende maanden en jaren vergelijkbare successen brengen in veel andere gebieden van de wiskunde, waar lang bestaande open problemen worden opgelost doordat AI onverwachte verbanden onthult en het bestaande technische instrumentarium tot het uiterste drijft. AI helpt ons de kathedraal van de wiskunde die we in de loop der eeuwen hebben gebouwd vollediger te verkennen; welke andere ongeziene wonderen wachten nog achter de schermen?"

Dit resultaat biedt een veelbelovend voorbeeld: AI levert niet alleen een oplossing, maar ook een wiskundige ontdekking waarvan de betekenis door later menselijk begrip duidelijker en rijker wordt.

De les is groter dan dit specifieke resultaat. Betere wiskundige redenering kan AI tot een sterkere onderzoekspartner maken: iets dat moeilijke denklijnen bijeen kan houden, ideeën uit ver uit elkaar liggende kennisgebieden kan verbinden, veelbelovende paden kan blootleggen die experts misschien geen prioriteit gaven, en onderzoekers kan helpen vooruitgang te boeken bij problemen die anders te complex of te tijdrovend zouden zijn om aan te pakken.

Die vermogens zijn ook buiten de wiskunde van belang. Als een model een ingewikkeld argument coherent kan houden, ideeën uit ver uit elkaar liggende kennisgebieden kan verbinden en werk kan produceren dat deskundige toetsing doorstaat, dan zijn dat ook nuttige vermogens in biologie, natuurkunde, materiaalkunde, techniek en geneeskunde, en maken ze deel uit van ons langetermijnpad naar meer geautomatiseerd onderzoek: systemen die wetenschappers en ingenieurs kunnen helpen meer ideeën te verkennen en moeilijkere technische vragen na te streven.

AI staat op het punt een zeer serieuze rol te gaan spelen in de creatieve delen van onderzoek, en vooral in AI-onderzoek zelf. Hoewel deze vooruitgang niet onverwacht is, onderstreept zij de urgentie die wij voelen om deze volgende fase van AI-ontwikkeling te begrijpen, de uitdagingen van het afstemmen van zeer intelligente systemen en de toekomst van samenwerking tussen mens en AI.

Die toekomst hangt nog steeds af van menselijk oordeel. Expertise wordt waardevoller, niet minder waardevol. AI kan helpen zoeken, suggereren en verifiëren. Mensen kiezen de problemen die ertoe doen, interpreteren de resultaten en beslissen welke vragen daarna worden nagestreefd.