En OpenAI-modell har motbevist en sentral formodning i diskret geometri

I nesten 80 år har matematikere studert et tilsynelatende enkelt spørsmål: Hvis du plasserer $n$ punkter i planet, hvor mange par av punkter kan ha nøyaktig avstand $1$?

Dette er problemet om enhetsavstander i planet, først formulert av Paul Erdős i 1946. Det er et av de mest kjente spørsmålene i kombinatorisk geometri, lett å formulere og bemerkelsesverdig vanskelig å løse. Boken fra 2005 Research Problems in Discrete Geometry, av Brass, Moser og Pach, kaller det «kanskje det mest kjente problemet (og enkleste å forklare) i kombinatorisk geometri». Noga Alon, en ledende kombinatoriker ved Princeton, beskriver det som «et av Erdős’ favorittproblemer». Erdős utlovet til og med en pengepremie til den som kunne løse dette problemet.

I dag deler vi et gjennombrudd i enhetsavstandsproblemet. Siden Erdős’ opprinnelige arbeid har den rådende oppfatningen vært at «kvadratisk rutenett»-konstruksjonene som vises lenger ned i hovedsak var optimale for å maksimere antallet enhetsavstandspar. En intern OpenAI-modell har motbevist denne langvarige formodningen ved å gi en uendelig familie av eksempler som gir en polynomisk forbedring. Beviset er kontrollert av en gruppe eksterne matematikere. De har også skrevet en ledsagende artikkel som forklarer argumentet og gir mer bakgrunn og kontekst for betydningen av resultatet.

Resultatet er også bemerkelsesverdig på grunn av hvordan det ble funnet. Beviset kom fra en ny generell resonneringsmodell, snarere enn fra et system trent spesifikt for matematikk, bygget opp for å søke gjennom bevisstrategier eller rettet spesielt mot enhetsavstandsproblemet. Som del av en bredere innsats for å teste om avanserte modeller kan bidra til banebrytende forskning, evaluerte vi den på en samling av Erdős-problemer. I dette tilfellet produserte den et bevis som løste det åpne problemet.

Dette beviset er en viktig milepæl for matematikk- og KI-miljøene. Det markerer første gang et fremtredende åpent problem, sentralt i et underfelt av matematikken, er blitt løst autonomt av KI. Det viser også dybden i resonneringen disse systemene nå støtter. Matematikk gir en særlig tydelig testarena for resonnering: Problemene er presise, mulige bevis kan kontrolleres, og et langt argument fungerer bare hvis resonneringen henger sammen fra begynnelse til slutt. Metoden problemet ble løst med, er også bemerkelsesverdig. Beviset bringer uventede, sofistikerte ideer fra algebraisk tallteori til anvendelse på et elementært geometrisk spørsmål.

Fieldsmedaljevinner Tim Gowers kaller resultatet «en milepæl i KI-matematikk» i den ledsagende artikkelen. Ifølge den ledende tallteoretikeren Arul Shankar «viser denne artikkelen etter min mening at dagens KI-modeller går utover bare å være hjelpere for menneskelige matematikere – de er i stand til å få originale, geniale ideer og deretter føre dem frem til fullbyrdelse».

Beviset er tilgjengelig her⁠(åpnes i et nytt vindu). Den ledsagende artikkelen av ledende eksterne matematikere er tilgjengelig her⁠(åpnes i et nytt vindu). Du finner en forkortet versjon av modellens tankerekke her⁠(åpnes i et nytt vindu).

La $u(n)$ være det størst mulige antallet enhetsavstandspar blant $n$ punkter i planet. Eksempler som oppnår lineær vekstrate, er enkle å konstruere: Plasserer man $n$ punkter på en linje, får man $n-1$ par, mens et kvadratisk rutenett gir omtrent $2n$ par. Den tidligere beste kjente konstruksjonen, som kommer fra et reskalert kvadratisk rutenett, viser seg å gi enda mer: $n^{1 + C / \log \log(n)}$ for en konstant $C$. Siden $\log \log(n)$ går mot uendelig når $n$ øker, går tilleggstermen i eksponenten mot $0$, noe som betyr at disse konstruksjonene bare oppnår vekst litt raskere enn lineær. I flere tiår var det en utbredt oppfatning at denne raten i hovedsak var den best mulige, og at ingen konstruksjon kunne gi en betydelig forbedring over det kvadratiske rutenettet. I tekniske termer formodet Erdős en øvre grense på $n^{1+o(1)}$, der tilleggstermen $o(1)$ angir et ledd som går mot $0$ med $n$.

Vårt nye resultat motbeviser denne formodningen. Mer presist konstruerer beviset, for uendelig mange verdier av $n$, konfigurasjoner av $n$ punkter med minst $n^{1+\delta}$ enhetsavstandspar, for en fast eksponent $\delta > 0$. (Det opprinnelige KI-beviset gir ikke en eksplisitt $\delta$, men en kommende forbedring av matematikkprofessor Will Sawin ved Princeton har vist at man kan ta $\delta=0.014$.)

Bakgrunnen for problemet gjør det lettere å forstå hvorfor resultatet er overraskende. Den beste kjente nedre grensen hadde vært i hovedsak uendret siden Erdős’ opprinnelige konstruksjon fra 1946. Den beste øvre grensen, $O(n^{4/3})$, stammer fra arbeid av Spencer, Szemerédi og Trotter i 1984, og til tross for senere forbedringer og beslektet strukturelt arbeid av Székely, Katz og Silier, Pach, Raz og Solymosi og andre, har den øvre grensen forblitt i hovedsak uendret. Som støtte for formodningen studerte Matoušek og Alon-Bucić-Sauermann problemet med ikke-euklidiske avstander i planet, og beviste at «de fleste» av disse ikke-euklidiske avstandene i en viss forstand følger formodningen.

Overraskende nok kommer nøkkelingrediensene i konstruksjonen fra en helt annen del av matematikken, kjent som algebraisk tallteori, som studerer begreper som faktorisering i utvidelser av heltallene kjent som algebraiske tallkropper.

På et høyt nivå begynner beviset med en kjent geometrisk idé og driver den i en uventet retning.

Erdős’ opprinnelige nedre grense kan forstås gjennom de gaussiske heltallene: tall av formen $a+bi$, der $a$ og $b$ er heltall og $i$ er kvadratroten av $-1$. De gaussiske heltallene utvider de vanlige heltallene og har, som dem, egenskaper som entydig faktorisering i primtall. Slike utvidelser av de vanlige heltallene eller de rasjonale tallene er kjent som algebraiske tallkropper. Det nye argumentet erstatter de gaussiske heltallene med mer kompliserte generaliseringer fra algebraisk tallteori med rikere symmetrier som kan skape mange flere forskjeller med enhetslengde.

Det presise argumentet bruker verktøy som uendelige klassetårn og Golod–Shafarevich-teori for å vise at tallkroppene som kreves for argumentet, faktisk eksisterer. Disse ideene var velkjente for algebraiske tallteoretikere, men det kom som en stor overraskelse at disse begrepene har implikasjoner for geometriske spørsmål i det euklidiske planet.

Dette resultatet markerer et viktig øyeblikk i samspillet mellom KI og matematikk: Et KI-system har autonomt løst et langvarig åpent problem i sentrum av et aktivt fagfelt. Det gir også et tidlig glimt av en ny type samarbeid mellom KI og menneskelige matematikere. I dette tilfellet tegner det ledsagende arbeidet fra eksterne matematikere et vesentlig rikere bilde enn den opprinnelige løsningen alene.

Som Thomas Bloom skriver i den ledsagende kommentaren:

«Når jeg vurderer betydningen og innflytelsen til et KI-generert bevis, er et spørsmål jeg stiller meg selv: Har dette lært oss noe nytt om problemet? Forstår vi diskret geometri bedre nå? Jeg mener svaret er et moderert ja: Dette viser at tallteoretiske konstruksjoner har mye mer å si om denne typen spørsmål enn vi mistenkte, dessuten at tallteorien som kreves, kan være svært dyp. Det er ingen tvil om at mange algebraiske tallteoretikere vil se nøye på andre åpne problemer i diskret geometri i månedene som kommer.»

Den uventede forbindelsen mellom algebraisk tallteori og diskret geometri som løsningen avdekker, er en del av det som gjør resultatet bemerkelsesverdig. Det avgjør ikke bare en spesifikk formodning, men kan også gi matematikere en bro til å begynne å utforske flere beslektede problemer.

Bloom peker også mot en bredere mulighet:

«Kunnskapens grenser er svært taggete, og det er ingen tvil om at de kommende månedene og årene vil by på lignende suksesser i mange andre områder av matematikken, der langvarige åpne problemer løses av en KI som avdekker uventede forbindelser og presser det eksisterende tekniske apparatet til dets grense. KI hjelper oss med å utforske matematikkens katedral, som vi har bygget gjennom århundrene, mer fullstendig. Hvilke andre usette underverker venter i kulissene?»

Dette resultatet gir et lovende eksempel: KI bidrar ikke bare med en løsning, men med en matematisk oppdagelse hvis betydning blir klarere og rikere gjennom påfølgende menneskelig forståelse.

Lærdommen er større enn dette konkrete resultatet. Bedre matematisk resonnering kan gjøre KI til en sterkere forskningspartner: noe som kan holde sammen vanskelige tankerekker, knytte ideer på tvers av fjerne kunnskapsområder, løfte frem lovende spor eksperter kanskje ikke har prioritert, og hjelpe forskere med å gjøre fremskritt på problemer som ellers ville vært for komplekse eller tidkrevende å ta fatt på.

Disse evnene betyr noe også utover matematikken. Hvis en modell kan holde et komplisert argument sammenhengende, knytte ideer på tvers av fjerne kunnskapsområder og produsere arbeid som tåler gransking fra eksperter, er dette også nyttige evner i biologi, fysikk, materialvitenskap, ingeniørfag og medisin, og de er en del av vår langsiktige vei mot mer automatisert forskning: systemer som kan hjelpe forskere og ingeniører med å utforske flere ideer og forfølge vanskeligere tekniske spørsmål.

KI er i ferd med å få en svært alvorlig rolle i de kreative delene av forskning, og viktigst av alt i selve KI-forskningen. Selv om denne fremgangen ikke er uventet, forsterker den hvor viktig det er for oss å forstå denne neste fasen av KI-utviklingen, utfordringene ved å samordne svært intelligente systemer og fremtiden for samarbeid mellom mennesker og KI.

Den fremtiden avhenger fortsatt av menneskelig dømmekraft. Ekspertise blir mer verdifull, ikke mindre. KI kan hjelpe med å søke, foreslå og verifisere. Mennesker velger problemene som betyr noe, tolker resultatene og avgjør hvilke spørsmål som skal forfølges videre.