OpenAIs nästa modell, Astra, löste just tio decennier gamla öppna matematikproblem

Den 1 augusti publicerade OpenAI en rapport där de hävdar att deras nästa modell, internt kallad Astra (ännu ej tillgänglig), har tagit fram nya resultat för tio olika öppna problem inom matematik. (Nej, det är inte Millenniumprisen-problemen, men de är ändå betydande.)

Det anmärkningsvärda: Dessa lösningar är inte stegvisa framsteg på problemen; de är egentliga lösningar, verifierade med Lean. (Lean är ett programmeringsspråk och ett bevisassistentverktyg som tvingar varje steg i ett matematiskt resonemang att skrivas ut i maskinläsbar detalj.) 

Det är mycket att ta in på en gång. I den här artikeln har jag ordnat problemen efter område och beskriver på hög nivå vad som hände, vad det kan innebära för matematiken som fält och vad vi i övrigt kan utläsa om Astra.

Vilka är de tio problemen?

Här är varje resultat, i enkla termer, tillsammans med det specifika område inom matematik eller datavetenskap det tillhör.

Icke-sofiska grupper

Område: Gruppteori

Astra tog fram en explicit konstruktion av en grupp som inte kan approximeras, hur nära man än försöker, av stora ändliga strukturer — vilket stänger en fråga som varit öppen sedan begreppet ”sofisk” grupp introducerades 1999. Konstruktionen åtföljs av ett bevis att ingen följd av ändliga approximationer någonsin kan fungera, formaliserat i Lean så att logiken kan kontrolleras maskinellt.

Wikipedia har redan uppdaterats:

Sfärpackning

Område: Högdimensionell geometri

Frågan är hur tätt identiska, icke överlappande sfärer kan packas när antalet dimensioner växer. Astra bevisade ett skarpare tak för den tätheten i höga dimensioner, den första förbättringen av just denna gräns sedan 1978. Det ger inte en bättre packningsmetod — det snävar in hur bra någon framtida metod överhuvudtaget kan bli.

Binära och sfäriska koder

Område: Kodningsteori

Felkorrigerande koder fungerar genom att hålla giltiga meddelanden tillräckligt långt ifrån varandra så att små fel inte kan förvandla ett till ett annat. Astra bevisade dramatiskt skarpare (exponentiellt förbättrade) gränser för hur många sådana meddelanden som kan finnas för ett givet minsta avstånd, med ett motsvarande resultat för punkter spridda över en högdimensionell sfär.

Connes rigiditetsförmodan

Område: Operatoralgebror

Alain Connes förmodade att vissa grupper alltid kunde återskapas entydigt från en algebraisk struktur, kallad en von Neumann-algebra, byggd utifrån dem. Astra motbevisade detta genom att ta fram två genuint olika grupper som ger upphov till samma algebra, vilket visar att återskapandet inte alltid är entydigt.

Aritmetisk kretskomplexitet

Område: Teoretisk datakomplexitet

”Permanenten”, ett enda tal beräknat från ett rutnät av tal, är dyrt att räkna ut, och komplexitetsteoretiker vill veta det minsta antal aritmetiska steg som någon metod överhuvudtaget kan behöva. Astra bevisade en ny, starkare nedre gräns för det minimumet — en ökänd svår typ av resultat att rubba överhuvudtaget.

Kvantparallell upprepning

Område: Kvantkomplexitetsteori

Klassisk teori säger att om två icke-kommunicerande spelare får repetera ett svårt spel många gånger parallellt blir fusk exponentiellt mindre sannolikt att lyckas. Astra bevisade att samma garanti gäller även när spelarna delar kvantintrassling, vilket utvidgar en grundläggande klassisk princip till den kvantmekaniska domänen.

Närmaste vektor-problemet

Område: Gitterbaserad kryptografi

Givet ett upprepat rutnät av punkter (ett gitter) och en målposition, frågar detta problem efter närmaste gitterpunkt — ett problem som anses vara mycket svårt i höga dimensioner, vilket är anledningen till att det ligger till grund för viss kvantresistent kryptering. Astra bevisade att även att approximera svaret, inom en specifik polynomfaktor, förblir bevisligen svårt, vilket stärker kryptografin som byggs på detta.

Ehrharts volymförmodan

Område: Diskret och konvex geometri

För en konvex form vars enda inre gitterpunkt ligger exakt i dess tyngdpunkt ville matematiker veta den största möjliga volym en sådan form kan ha i en given dimension. Astra räknade ut den maximala volymen för varje dimension och avgjorde därmed förmodan i full allmängiltighet.

Flerfärgade Ramsey-tal

Område: Ramseyteori / kombinatorik

Med tillräckligt många personer och tillräckligt många kategorier av relationer mellan dem är du till sist garanterad att hitta tre personer som alla är förbundna av samma kategori. Astra bevisade att den minsta gruppstorlek som krävs växer snabbare än någon fixerad exponentiell takt när antalet kategorier ökar, och löste därmed Erdős problem 183.

Extremala tal-förmodanden

Område: Extremal grafteori

Denna gren av matematiken frågar hur många förbindelser ett nätverk kan ha samtidigt som det undviker vissa små, förbjudna mönster. Astra löste två besläktade förmodanden här, motsvarande Erdős problem 146 och 180, och fastställde hur täta sådana nätverk kan bli innan dessa mönster blir oundvikliga.

Var och en av dessa hade varit öppna i minst ett decennium; flera hade stått i trettio år eller mer, inklusive problem som arbetats med av Turingpris-vinnare på den teoretiska datavetenskapssidan av listan.

Vänta, är ett motexempel den ”enkla” typen av bevis?

Vem är jag att säga något negativt här, men jag vet att detta är en vanlig fråga eller reaktion, särskilt från personer som kan något om matematik.

Det vanligaste folk säger som kritik: Flera av dessa resultat är motexempel snarare än ny allmän teori. Denna idé är viktig eftersom ett motexempel besvarar en ja/nej-fråga men inte i sig berättar varför mönstret bryts eller ger dig en familj av liknande objekt att studera härnäst, medan något annat, som en klassifikationssats eller en ny teknik, öppnar fler dörrar.

Jag skulle säga att denna kritik håller i allmänhet, men den fungerar inte som en generell avfärdande av hela denna omgång problem. För det första är resultatet om icke-sofiska grupper inte en liten justering av ett befintligt nästan-resultat — det är den första konstruktionen i sitt slag efter 27 år där ingen hade någon alls, och tekniken bakom den förväntas generalisera till att hitta andra.

För det andra är flera av de övriga nio resultaten, inklusive sfärpackningsgränsen och CVP-svårighetsresultatet, inte motexempel alls; de är direkta förbättringar av gällande gränser. 

Det som återstår olöst

Några saker är värda att följa när detta dissekeras av fältet under de kommande dagarna, veckorna och månaderna:

• Ingen peer review ännu. Dessa är Lean-verifierade och granskade informellt av matematiker som sett preprints, men ingen har ännu gått igenom en referentgranskad tidskriftsprocess. 
• Författarskapet förhandlas fortfarande. OpenAI säger att de tar ansvar för manuskripten och Lean-formaliseringarna, samtidigt som de tillskriver de matematiska argumenten själva modellen. Oberoende replikering av processen (i motsats till verifiering av bevisen) är svår att göra just nu.

Vad detta betyder för matematiken

Den mest omedelbara förändringen gäller vad matematiker faktiskt kan komma att lägga sin tid på. Om ett välformulerat öppet problem kan lämnas till en modell och kontrolleras i Lean, flyttas flaskhalsen från ”kan någon lösa detta” till ”ställde vi rätt fråga och formaliserade den korrekt”. Förmågan att ställa en bra fråga och veta vilken som är värd att angripa är en verklig färdighet som matematiker utvecklar med erfarenhet. 

Det finns också en fråga om finansiering och trovärdighet som puttrar. Forskningsanslag, tillsvidareanställningar och priser har historiskt byggt på knapphet: dessa problem var tillräckligt svåra för att lösningen sa något om lösaren. Om AI-assisterade resultat blir rutin, kommer fältet att behöva nya sätt att signalera vad som verkligen är svårt kontra vad som nu ligger inom räckhåll för några tusen dollar i inference-kostnader. Självklart förstår genomsnittspersonen inte dessa problem fullt ut. De som har verklig utbildning gör det, och det förändras inte. Så matematikkunskap är mer värdefull än någonsin. 

Hur folk reagerar

Reaktionerna i sociala medier delade sig mindre kring huruvida bevisen håller, och mer kring vad de är bevis på.

En del läser tempot i sig som den verkliga nyheten: tio decennier gamla problem som landar på en gång, över obesläktade områden, snabbare än experter ens hinner granska dem. En fråga för framtiden: ”Kommer vi att kunna hinna med att kontrollera allt detta?”

Andra invänder att detta säger mindre om AI i allmänhet än det verkar. Matematik är en sällsynt domän där en modells arbete kan kontrolleras automatiskt och fullständigt. De flesta verkliga problem erbjuder inte den typen av inbyggd, automatisk facit. I den synen är prestationen verklig, men den kan säga mer om att matematiken är ovanligt väl lämpad för AI.

En tredje kommentarslinje: Ett korrekt bevis som ingen fullt ut har granskat eller absorberat har ännu inte riktigt förståtts, bara verifierats. Att upptäcka en sats och förstå vad den betyder är, i denna syn, två olika jobb.

Avslutande tankar

Matematiker säger att resultatet om icke-sofiska grupper ser ut att vara på riktigt: en genuin, decennier gammal öppen fråga i gruppteori, stängd av en explicit konstruktion som matematiker inom fältet tar på allvar. De övriga nio resultaten, sammantaget, utgör en bred och tekniskt betydande omgång framsteg inom ren matematik.

Det som ännu inte har hänt är den långsammare delen: peer review, replikering av sökprocessen och att fältet faktiskt bygger vidare på dessa resultat. Den delen tar längre tid än ett blogginlägg, och det är den som verkligen kommer att berätta hur stort detta var. Vi håller dig uppdaterad.