En OpenAI-modell har motbevisat en central hypotes inom diskret geometri.

I nästan 80 år har matematiker studerat en bedrägligt enkel fråga: om du placerar $n$ punkter i planet, hur många punktpar kan då ligga på exakt avstånd $1$ från varandra?

Detta är problemet med enhetsavstånd i planet, som först formulerades av Paul Erdős 1946. Det är en av de mest kända frågorna inom kombinatorisk geometri, lätt att formulera och anmärkningsvärt svår att lösa. Boken Research Problems in Discrete Geometry från 2005 av Brass, Moser och Pach kallar det ”möjligen det mest kända problemet (och det enklaste att förklara) inom kombinatorisk geometri”. Noga Alon, en ledande kombinatoriker vid Princeton, beskriver det som ”ett av Erdős favoritproblem”. Erdős utlovade till och med en penningsumma för att lösa problemet.

I dag delar vi ett genombrott kring problemet om enhetsavstånd. Sedan Erdős ursprungliga arbete har den rådande uppfattningen varit att de ”kvadratiska rutnätskonstruktioner” som visas längre ned i huvudsak var optimala för att maximera antalet par på enhetsavstånd. En intern OpenAI-modell har motbevisat denna sedan länge etablerade hypotes genom att ge en oändlig familj av exempel som ger en polynomiell förbättring. Beviset har granskats av en grupp externa matematiker. De har också skrivit en kompletterande artikel som förklarar argumentet och ger ytterligare bakgrund och kontext till resultatets betydelse.

Resultatet är också anmärkningsvärt med tanke på hur det togs fram. Beviset kom från en ny generell resonemangsmodell, snarare än från ett system som tränats specifikt för matematik, byggts upp för att söka igenom bevisstrategier eller riktats mot just problemet med enhetsavstånd. Som en del av ett bredare arbete med att undersöka om avancerade modeller kan bidra till banbrytande forskning testade vi modellen på en samling Erdős-problem. I det här fallet producerade den ett bevis som löste det olösta problemet.

Detta bevis utgör en viktig milstolpe inom både matematik och AI. Det är första gången ett framstående öppet problem, centralt inom ett delområde av matematiken, har lösts autonomt av AI. Det visar också hur avancerade resonemang dessa system nu klarar av. Matematik ger en särskilt tydlig testmiljö för resonemang: problemen är precisa, möjliga bevis kan kontrolleras, och ett långt argument fungerar bara om resonemanget håller ihop från början till slut. Metoden genom vilken problemet löstes är också anmärkningsvärd. Beviset använder oväntade, sofistikerade idéer från algebraisk talteori på en elementär geometrisk fråga.

Fieldsmedaljören Tim Gowers kallar i den kompletterande artikeln resultatet för ”en milstolpe inom AI-matematik”. Enligt den ledande talteoretikern Arul Shankar visar artikeln enligt hans mening att dagens AI-modeller går längre än att bara vara hjälpmedel för mänskliga matematiker – de kan få originella, geniala idéer och sedan fullfölja dem.”

Beviset finns tillgängligt här⁠(öppnas i ett nytt fönster). Den kompletterande artikeln av ledande externa matematiker finns tillgänglig här⁠(öppnas i ett nytt fönster). Du hittar en förkortad version av modellens tankekedja här⁠(öppnas i ett nytt fönster).

Låt $u(n)$ vara det största möjliga antalet par på enhetsavstånd bland $n$ punkter i planet. Exempel som uppnår linjär tillväxttakt är lätta att konstruera: att placera $n$ punkter på en linje ger $n-1$ par, medan ett kvadratiskt rutnät ger ungefär $2n$ par. Den tidigare bästa kända konstruktionen, som kommer från ett omskalat kvadratiskt rutnät, visar sig ge ännu fler: $n^{1 + C / \log \log(n)}$ för en konstant $C$. Eftersom $\log \log(n)$ går mot oändligheten när $n$ växer, går den extra termen i exponenten mot $0$, vilket betyder att dessa konstruktioner bara uppnår en tillväxt som är något snabbare än linjär. I årtionden trodde man allmänt att denna takt i huvudsak var den bästa möjliga och att ingen konstruktion kunde ge någon betydande förbättring jämfört med det kvadratiska rutnätet. I tekniska termer förmodade Erdős en övre gräns på $n^{1+o(1)}$, där den extra $o(1)$-termen anger en term som går mot $0$ med $n$.

Vårt nya resultat motbevisar denna hypotes. Mer precist konstruerar beviset, för oändligt många värden på $n$, konfigurationer av $n$ punkter med minst $n^{1+\delta}$ par på enhetsavstånd, där (\delta > 0\) är en fast exponent. (Det ursprungliga AI-beviset ger inte något explicit $\delta$, men en kommande förfining av Princetons matematikprofessor Will Sawin har visat att man kan ta $\delta=0.014$.)

Problemets historia hjälper till att förklara varför resultatet är överraskande. Den bästa kända undre gränsen hade i stort sett varit oförändrad sedan Erdős ursprungliga konstruktion från 1946. Den bästa övre gränsen, $O(n^{4/3})$, formulerades av Spencer, Szemerédi och Trotter 1984, och trots senare förfiningar och relaterat strukturellt arbete av Székely, Katz och Silier, Pach, Raz och Solymosi samt andra, har den övre gränsen i stort sett förblivit oförändrad. Som stöd för förmodan studerade Matoušek och Alon-Bucić-Sauermann problemet med icke-euklidiska avstånd i planet och visade att "de flesta" av dessa icke-euklidiska avstånd i någon mening följer hypotesen.

Överraskande nog kommer de centrala delarna i konstruktionen från ett helt annat område inom matematiken, nämligen algebraisk talteori, som studerar begrepp som faktorisering i utvidgningar av heltalen som kallas algebraiska talkroppar.

På en hög nivå börjar beviset med en välbekant geometrisk idé och driver den i en oväntad riktning.

Erdős ursprungliga undre gräns kan förstås genom de gaussiska heltalen: tal av formen $a+bi$, där $a$ och $b$ är heltal och $i$ är kvadratroten ur $-1$. De gaussiska heltalen utvidgar de vanliga heltalen och har, liksom dem, egenskaper som unik faktorisering i primtal. Sådana utvidgningar av de vanliga heltalen eller rationella talen kallas algebraiska talkroppar. Det nya argumentet ersätter de gaussiska heltalen med mer komplexa generaliseringar från algebraisk talteori med rikare symmetrier som kan ge upphov till betydligt fler punktpar på enhetsavstånd.

Det precisa argumentet använder verktyg som oändliga klasskroppstorn och Golod–Shafarevich-teori för att visa att de talkroppar som krävs för argumentet faktiskt existerar. Dessa idéer var välkända för algebraiska talteoretiker, men det kom som en stor överraskning att dessa begrepp har implikationer för geometriska frågor i det euklidiska planet.

Detta resultat utgör en viktig milstolpe i samspelet mellan AI och matematik: ett AI-system har autonomt löst ett långvarigt öppet problem inom ett aktivt forskningsfält. Det ger också en tidig inblick i en ny sorts samarbete mellan AI och mänskliga matematiker. I det här fallet ger det kompletterande arbetet av externa matematiker en betydligt rikare bild än den ursprungliga lösningen.

Som Thomas Bloom skriver i den tillhörande kommentaren:

”När jag bedömer betydelsen och inflytandet av ett AI-genererat bevis ställer jag mig frågan: har detta lärt oss något nytt om problemet? Förstår vi diskret geometri bättre nu? Jag tror att svaret är ett försiktigt ja: detta visar att talteoretiska konstruktioner har mycket mer att säga om den här typen av frågor än vi misstänkte, och dessutom att den talteori som krävs kan vara mycket djupgående. Utan tvekan kommer många algebraiska talteoretiker att titta noga på andra öppna problem inom diskret geometri under de kommande månaderna.”

Den oväntade kopplingen mellan algebraisk talteori och diskret geometri som lösningen avslöjar är en del av det som gör resultatet anmärkningsvärt. Det löser inte bara en specifik hypotes, utan kan också ge matematiker en väg in till vidare utforskning av närliggande problem.

Bloom pekar också mot en bredare möjlighet:

”Kunskapens gränser är mycket ojämna, och de kommande månaderna och åren kommer utan tvekan att bjuda på liknande framgångar inom många andra områden av matematiken, där långvariga öppna problem löses genom att AI upptäcker oväntade samband och utvecklar befintliga matematiska metoder på nya sätt. AI hjälper oss att utforska det enorma matematiska arv som byggts upp under århundradena mer fullständigt; vilka andra oupptäckta underverk väntar bakom kulisserna?”

Detta resultat är ett lovande exempel på hur AI kan bidra inte bara med en lösning, utan med en matematisk upptäckt vars betydelse blir tydligare och rikare genom efterföljande mänsklig förståelse.

Lärdomen är större än just detta resultat. Bättre matematisk resonemangsförmåga kan göra AI till en starkare forskningspartner: något som kan hålla ihop komplexa tankeled, knyta samman idéer från avlägsna kunskapsområden, lyfta fram lovande spår som experter kanske inte prioriterat och hjälpa forskare att göra framsteg i problem som annars hade varit alltför komplexa eller tidskrävande att ta sig an.

Dessa förmågor spelar roll även utanför matematiken. Om en modell kan hålla samman komplexa resonemang, knyta ihop idéer från vitt skilda kunskapsområden och producera resultat som klarar expertgranskning, så är det också användbara förmågor inom biologi, fysik, materialvetenskap, ingenjörsvetenskap och medicin. Sådana förmågor är också en viktig del av vår långsiktiga satsning på mer automatiserad forskning: system som kan hjälpa forskare och ingenjörer att utforska fler idéer och ta sig an svårare tekniska frågor.

AI är på väg att börja ta en mycket mer central roll i de kreativa delarna av forskning, och viktigast av allt i AI-forskningen själv. Även om den här utvecklingen inte är oväntad gör den det ännu viktigare att förstå nästa fas i AI-utvecklingen, utmaningarna med att anpassa mycket intelligenta system och framtiden för samarbetet mellan människor och AI.

Den framtiden beror fortfarande på mänskligt omdöme. Expertis blir mer värdefull, inte mindre. AI kan hjälpa till att söka, föreslå och verifiera. Människor väljer de problem som är viktiga, tolkar resultaten och avgör vilka frågor som ska följas upp härnäst.