OpenAI-malli on kumonnut keskeisen diskreetin geometrian konjektuurin

Lähes 80 vuoden ajan matemaatikot ovat tutkineet petollisen yksinkertaista kysymystä: jos tasoon asetetaan $n$ pistettä, kuinka moni pistepari voi olla täsmälleen etäisyydellä $1$ toisistaan?

Tämä on tason yksikköetäisyysongelma, jonka Paul Erdős esitti ensimmäisen kerran vuonna 1946. Se on yksi kombinatorisen geometrian tunnetuimmista kysymyksistä: helppo ilmaista ja huomattavan vaikea ratkaista. Brassin, Moserin ja Pachin vuoden 2005 kirja Research Problems in Discrete Geometry kutsuu sitä ”mahdollisesti tunnetuimmaksi (ja helpoimmin selitettäväksi) ongelmaksi kombinatorisessa geometriassa”. Noga Alon, Princetonissa työskentelevä johtava kombinatoriikan tutkija, kuvailee sitä ”yhdeksi Erdősin suosikkiongelmista”. Erdős jopa lupasi rahapalkinnon tämän ongelman ratkaisemisesta.

Tänään kerromme läpimurrosta yksikköetäisyysongelmassa. Erdősin alkuperäisestä työstä lähtien vallitseva käsitys on ollut, että alempana kuvatut ”neliöruudukko”-konstruktiot olivat olennaisesti optimaalisia yksikköetäisyydellä olevien pisteparien määrän maksimoimiseksi. Sisäinen OpenAI-malli on kumonnut tämän pitkäaikaisen konjektuurin ja antanut äärettömän esimerkkiperheen, joka tuottaa polynomisen parannuksen. Ryhmä ulkopuolisia matemaatikkoja on tarkistanut todistuksen. He ovat myös kirjoittaneet oheisartikkelin, joka selittää argumentin ja tarjoaa lisää taustaa ja kontekstia tuloksen merkitykselle.

Tulos on merkittävä myös sen vuoksi, miten se löydettiin. Todistus tuli uudesta yleiskäyttöisestä päättelymallista eikä järjestelmästä, joka olisi koulutettu erityisesti matematiikkaan, rakennettu etsimään todistusstrategioita tai kohdistettu nimenomaan yksikköetäisyysongelmaan. Osana laajempaa pyrkimystä testata, voivatko kehittyneet mallit edistää huippututkimusta, arvioimme sitä Erdősin ongelmien kokoelmalla. Tässä tapauksessa se tuotti todistuksen, joka ratkaisi avoimen ongelman.

Tämä todistus on tärkeä virstanpylväs matematiikan ja tekoälyn yhteisöille. Se on ensimmäinen kerta, kun tekoäly on ratkaissut autonomisesti merkittävän avoimen ongelman, joka on keskeinen matematiikan osa-alueelle. Se osoittaa myös, kuinka syvää päättelyä nämä järjestelmät nyt tukevat. Matematiikka tarjoaa erityisen selkeän testialustan päättelylle: ongelmat ovat täsmällisiä, mahdolliset todistukset voidaan tarkistaa, ja pitkä argumentti toimii vain, jos päättely pysyy koossa alusta loppuun. Myös tapa, jolla ongelma ratkaistiin, on huomionarvoinen. Todistus tuo odottamattomia, hienostuneita ideoita algebrallisesta lukuteoriasta elementaarisen geometrisen kysymyksen ratkaisemiseen.

Fields-mitalisti Tim Gowers kutsuu oheisartikkelissa tulosta ”virstanpylvääksi tekoälymatematiikassa”. Johtavan lukuteoreetikon Arul Shankarin mukaan ”mielestäni tämä artikkeli osoittaa, että nykyiset tekoälymallit ovat enemmän kuin vain ihmismatemaatikkojen apureita – ne kykenevät omaperäisiin nerokkaisiin ideoihin ja myös viemään ne maaliin”.

Todistus on saatavilla täällä⁠(avautuu uudessa ikkunassa). Johtavien ulkopuolisten matemaatikkojen oheisartikkeli on saatavilla täällä⁠(avautuu uudessa ikkunassa). Löydät lyhennetyn version mallin ajatusketjusta täältä⁠(avautuu uudessa ikkunassa).

Olkoon $u(n)$ suurin mahdollinen yksikköetäisyydellä olevien pisteparien määrä $n$:n tason pisteen joukossa. Esimerkkejä, jotka saavuttavat lineaarisen kasvunopeuden, on helppo rakentaa: $n$ pisteen asettaminen suoralle antaa $n-1$ paria, kun taas neliöruudukko antaa noin $2n$ paria. Aiemmin paras tunnettu konstruktio, joka saadaan uudelleenskaalatusta neliöruudukosta, antaa vielä enemmän: $n^{1 + C / \log \log(n)}$, missä $C$ on vakio. Koska $\log \log(n)$ kasvaa rajatta $n$:n mukana, eksponentin lisätermi lähestyy arvoa $0$, mikä tarkoittaa, että nämä konstruktiot saavuttavat kasvun, joka on vain hieman lineaarista nopeampaa. Vuosikymmenten ajan uskottiin laajalti, että tämä nopeus oli olennaisesti paras mahdollinen eikä mikään konstruktio voisi parantaa neliöruudukkoa merkittävästi. Teknisesti ilmaistuna Erdős konjektoi ylärajan $n^{1+o(1)}$, jossa lisätermi $o(1)$ tarkoittaa termiä, joka lähestyy arvoa $0$ $n$:n kasvaessa.

Uusi tuloksemme kumoaa tämän konjektuurin. Tarkemmin sanottuna todistus rakentaa äärettömän monelle $n$:n arvolle $n$ pisteen konfiguraatioita, joissa on vähintään $n^{1+\delta}$ yksikköetäisyydellä olevaa pisteparia jollakin kiinteällä eksponentilla $\delta > 0$. (Alkuperäinen tekoälyn tuottama todistus ei anna eksplisiittistä $\delta$:a, mutta Princetonin matematiikan professori Will Sawinin tuleva tarkennus on osoittanut, että voidaan ottaa $\delta=0.014$.)

Ongelman historia auttaa ymmärtämään, miksi tulos on yllättävä. Paras tunnettu alaraja oli pysynyt olennaisesti muuttumattomana Erdősin alkuperäisestä vuoden 1946 konstruktiosta lähtien. Paras yläraja, $O(n^{4/3})$, on peräisin Spencerin, Szemerédin ja Trotterin työstä vuodelta 1984, ja myöhemmistä tarkennuksista sekä Székelyn, Katzin ja Silierin, Pachin, Razin ja Solymosin sekä muiden tekemästä rakenteellisesta työstä huolimatta yläraja on pysynyt olennaisesti muuttumattomana. Konjektuuria tukevana näyttönä Matoušek sekä Alon-Bucić-Sauermann tutkivat ongelmaa tason epäeuklidisilla etäisyyksillä ja osoittivat, että ”useimmat” näistä epäeuklidisista etäisyyksistä noudattavat jossain mielessä konjektuuria.

Yllättäen konstruktion keskeiset ainekset tulevat aivan toiselta matematiikan alueelta, algebrallisesta lukuteoriasta, joka tutkii käsitteitä kuten tekijöihinjakoa kokonaislukujen laajennuksissa, joita kutsutaan algebrallisiksi lukukunniksi.

Yleisellä tasolla todistus alkaa tutusta geometrisesta ideasta ja vie sen odottamattomaan suuntaan.

Erdősin alkuperäinen alaraja voidaan ymmärtää Gaussin kokonaislukujen kautta: lukujen, jotka ovat muotoa $a+bi$, missä $a$ ja $b$ ovat kokonaislukuja ja $i$ on luvun $-1$ neliöjuuri. Gaussin kokonaisluvut laajentavat tavallisia kokonaislukuja ja niillä on niiden tavoin ominaisuuksia, kuten yksikäsitteinen alkutekijähajotelma. Tällaisia tavallisten kokonaislukujen tai rationaalilukujen laajennuksia kutsutaan algebrallisiksi lukukunniksi. Uusi argumentti korvaa Gaussin kokonaisluvut algebrallisen lukuteorian monimutkaisemmilla yleistyksillä, joilla on rikkaammat symmetriat ja jotka voivat tuottaa paljon enemmän yksikköpituuksisia erotuksia.

Tarkka argumentti käyttää työkaluja, kuten äärettömiä luokkakuntatorneja ja Golod–Shafarevitšin teoriaa, osoittaakseen, että argumentissa tarvittavat lukukunnat todella ovat olemassa. Nämä ideat olivat algebrallisen lukuteorian tutkijoille hyvin tunnettuja, mutta oli suuri yllätys, että näillä käsitteillä on seurauksia euklidisen tason geometrisille kysymyksille.

Tämä tulos merkitsee tärkeää hetkeä tekoälyn ja matematiikan vuorovaikutuksessa: tekoälyjärjestelmä on ratkaissut autonomisesti pitkäaikaisen avoimen ongelman aktiivisen tutkimusalan ytimessä. Se tarjoaa myös varhaisen välähdyksen uudenlaisesta yhteistyöstä tekoälyn ja ihmismatemaatikkojen välillä. Tässä tapauksessa ulkopuolisten matemaatikkojen oheistyö maalaa huomattavasti rikkaamman kuvan kuin alkuperäinen ratkaisu yksinään.

Kuten Thomas Bloom kirjoittaa oheishuomiossa:

”Kun arvioin tekoälyn tuottaman todistuksen tärkeyttä ja vaikutusta, kysyn itseltäni: onko tämä opettanut meille jotain uutta ongelmasta? Ymmärrämmekö diskreettiä geometriaa nyt paremmin? Mielestäni vastaus on varovaisen myöntävä: tämä osoittaa, että lukuteoreettisilla konstruktioilla on tällaisista kysymyksistä paljon enemmän sanottavaa kuin epäilimme; lisäksi tarvittava lukuteoria voi olla hyvin syvällistä. Epäilemättä monet algebrallisen lukuteorian tutkijat tarkastelevat tulevina kuukausina tarkasti muita avoimia diskreetin geometrian ongelmia.”

Ratkaisun paljastama odottamaton yhteys algebrallisen lukuteorian ja diskreetin geometrian välillä on osa sitä, mikä tekee tuloksesta merkittävän. Se ei vain ratkaise tiettyä konjektuuria, vaan voi tarjota matemaatikoille sillan alkaa tutkia muita siihen liittyviä ongelmia.

Bloom viittaa myös laajempaan mahdollisuuteen:

”Tiedon rajat ovat hyvin rosoisia, ja epäilemättä tulevat kuukaudet ja vuodet tuovat samanlaisia onnistumisia monilla muilla matematiikan alueilla, kun tekoäly ratkaisee pitkäaikaisia avoimia ongelmia paljastamalla odottamattomia yhteyksiä ja viemällä olemassa olevan teknisen koneiston äärirajoilleen. Tekoäly auttaa meitä tutkimaan täydellisemmin matematiikan katedraalia, jonka olemme rakentaneet vuosisatojen aikana; mitä muita näkymättömiä ihmeitä odottaa kulissien takana?”

Tämä tulos tarjoaa lupaavan esimerkin: tekoäly ei tuota vain ratkaisua, vaan matemaattisen löydön, jonka merkitys selkenee ja rikastuu myöhemmän inhimillisen ymmärryksen kautta.

Opetus on tätä yksittäistä tulosta suurempi. Parempi matemaattinen päättely voi tehdä tekoälystä vahvemman tutkimuskumppanin: sellaisen, joka pystyy pitämään koossa vaikeita ajatuskulkuja, yhdistämään ideoita kaukaisilta tietämyksen alueilta, nostamaan esiin lupaavia polkuja, joita asiantuntijat eivät ehkä ole priorisoineet, ja auttamaan tutkijoita edistymään ongelmissa, jotka muuten olisivat liian monimutkaisia tai aikaa vieviä käsitellä.

Nämä kyvyt ovat tärkeitä matematiikan ulkopuolellakin. Jos malli pystyy pitämään monimutkaisen argumentin johdonmukaisena, yhdistämään ideoita kaukaisilta tietämyksen alueilta ja tuottamaan työtä, joka kestää asiantuntijoiden tarkastelun, nämä ovat hyödyllisiä kykyjä myös biologiassa, fysiikassa, materiaalitieteessä, insinööritieteissä ja lääketieteessä, ja ne ovat osa pidemmän aikavälin polkuamme kohti automatisoidumpaa tutkimusta: järjestelmiä, jotka voivat auttaa tutkijoita ja insinöörejä tutkimaan useampia ideoita ja tarttumaan vaikeampiin teknisiin kysymyksiin.

Tekoäly on alkamassa ottaa hyvin vakavan roolin tutkimuksen luovissa osissa ja ennen kaikkea itse tekoälytutkimuksessa. Vaikka tämä edistys ei ole odottamatonta, se korostaa kiireellisyyttä, jota tunnemme ymmärtääksemme tämän tekoälyn kehityksen seuraavan vaiheen, erittäin älykkäiden järjestelmien yhteensovittamisen haasteet ja ihmisen ja tekoälyn yhteistyön tulevaisuuden.

Tuo tulevaisuus riippuu silti ihmisen harkinnasta. Asiantuntemuksesta tulee arvokkaampaa, ei vähemmän arvokasta. Tekoäly voi auttaa etsimään, ehdottamaan ja varmistamaan. Ihmiset valitsevat merkitykselliset ongelmat, tulkitsevat tulokset ja päättävät, mitä kysymyksiä seuraavaksi kannattaa tutkia.