OpenAI model je ovrgel osrednjo domnevo v diskretni geometriji

Skoraj 80 let so matematiki preučevali varljivo preprosto vprašanje: če v ravnino postavite $n$ točk, koliko parov točk je lahko med seboj oddaljenih natanko $1$?

To je problem enotskih razdalj v ravnini, ki ga je leta 1946 prvi zastavil Paul Erdős. Gre za eno najbolj znanih vprašanj v kombinatorni geometriji, ki jih je lahko ubesediti in izjemno težko razrešiti. Knjiga iz leta 2005 z naslovom Research Problems in Discrete Geometry avtorjev Brassa, Moserja in Pacha ga označuje za »morda najbolj znan (in najpreprosteje razložljiv) problem v kombinatorni geometriji«. Noga Alon, vodilni kombinatorik na Princetonu, ga opisuje kot »enega od Erdősevih najljubših problemov«. Erdős je celo ponudil denarno nagrado za rešitev tega problema.

Danes predstavljamo preboj pri problemu enotske razdalje. Od Erdősovega izvirnega dela je prevladovalo prepričanje, da so konstrukcije »kvadratne mreže«, prikazane nižje spodaj, v bistvu optimalne za maksimiranje števila parov na enotski razdalji. Interni OpenAI model je ovrgel to dolgoletno domnevo in podal neskončno družino primerov, ki prinašajo polinomsko izboljšavo. Dokaz je preverila skupina zunanjih matematikov. Napisali so tudi spremljevalni članek, ki pojasnjuje argument ter podaja dodatno ozadje in kontekst pomena rezultata.

Rezultat je opazen tudi zaradi načina, kako je bil odkrit. Dokaz je prišel iz novega splošnonamenskega modela sklepanja, ne pa iz sistema, posebej naučenega za matematiko, opremljenega za iskanje strategij dokazovanja ali posebej usmerjenega na problem enotske razdalje. Kot del širšega prizadevanja, da bi preverili, ali lahko napredni modeli prispevajo k vrhunskim raziskavam, smo ga ovrednotili na zbirki Erdősovih problemov. V tem primeru je ustvaril dokaz, ki razreši odprti problem.

Ta dokaz je pomemben mejnik za matematično skupnost in skupnost UI. To je prvič, da je UI samostojno rešila pomemben odprti problem, osrednji za neko podpodročje matematike. Prav tako kaže globino sklepanja, ki jo ti sistemi zdaj podpirajo. Matematika ponuja posebej jasno preizkusno okolje za sklepanje: problemi so natančni, morebitne dokaze je mogoče preveriti, dolg argument pa deluje le, če sklepanje drži skupaj od začetka do konca. Opazna je tudi metoda, s katero je bil problem rešen. Dokaz na nepričakovan način uporabi prefinjene ideje iz algebraične teorije števil pri elementarnem geometrijskem vprašanju.

Dobitnik Fieldsove medalje Tim Gowers v spremljevalnem članku rezultat imenuje »mejnik v matematiki UI«. Po besedah vodilnega teoretika števil Arula Shankarja »ta članek po mojem mnenju kaže, da današnji modeli UI presegajo vlogo zgolj pomočnikov človeškim matematikom – sposobni so izvirnih domiselnih idej in jih nato tudi pripeljati do uspešnega zaključka«.

Dokaz je na voljo tukaj⁠(odpre se v novem oknu). Spremljevalni članek vodilnih zunanjih matematikov je na voljo tukaj⁠(odpre se v novem oknu). Skrajšano različico verige sklepanja modela lahko najdete tukaj⁠(odpre se v novem oknu).

Naj bo $u(n)$ največje možno število parov na enotski razdalji med $n$ točkami v ravnini. Primere z linearno stopnjo rasti je lahko konstruirati: če $n$ točk postavimo na premico, dobimo $n-1$ parov, kvadratna mreža pa da približno $2n$ parov. Prej najbolj znana konstrukcija, ki izhaja iz pomanjšane kvadratne mreže, se izkaže za še boljšo: $n^{1 + C / \log \log(n)}$ za konstanto $C$. Ker $\log \log(n)$ z $n$ teži v neskončnost, dodatni člen v eksponentu teži k $0$, kar pomeni, da te konstrukcije dosegajo rast le malo hitrejšo od linearne. Desetletja je bilo splošno prepričanje, da je ta stopnja v bistvu najboljša možna in da nobena konstrukcija ne more bistveno izboljšati kvadratne mreže. V tehničnem smislu je Erdős domneval zgornjo mejo $n^{1+o(1)}$, kjer dodatni $o(1)$ označuje člen, ki z $n$ teži k $0$.

Naš novi rezultat to domnevo ovrže. Natančneje, za neskončno mnogo vrednosti $n$ dokaz skonstruira konfiguracije $n$ točk z vsaj $n^{1+\delta}$ pari na enotski razdalji za neki fiksni eksponent $\delta > 0$. (Izvirni dokaz UI ne poda eksplicitnega $\delta$, vendar je prihajajoča izpopolnitev profesorja matematike na Princetonu Willa Sawina pokazala, da lahko vzamemo $\delta=0,014$.)

Zgodovina problema pomaga razumeti, zakaj je rezultat presenetljiv. Najboljša znana spodnja meja je od Erdősove izvirne konstrukcije iz leta 1946 ostala v bistvu nespremenjena. Najboljša zgornja meja, $O(n^{4/3})$, izvira iz dela Spencerja, Szemerédija in Trotterja iz leta 1984, in kljub poznejšim izboljšavam ter sorodnemu strukturnemu delu Székelyja, Katza in Silierja, Pacha, Raza in Solymosija ter drugih je zgornja meja ostala v bistvu nespremenjena. Kot dokaz v prid domnevi so Matoušek ter Alon-Bucić-Sauermann preučevali problem z neevklidskimi razdaljami v ravnini in dokazali, da »večina« teh neevklidskih razdalj v nekem smislu sledi domnevi.

Presenetljivo ključne sestavine konstrukcije prihajajo iz zelo drugačnega dela matematike, znanega kot algebraična teorija števil, ki preučuje pojme, kot je faktorizacija v razširitvah celih števil, znanih kot algebraična številska polja.

Na visoki ravni se dokaz začne z znano geometrijsko idejo in jo potisne v nepričakovano smer.

Erdősovo izvirno spodnjo mejo lahko razumemo prek Gaussovih celih števil: števil oblike $a+bi$, kjer sta $a$ in $b$ celi števili, $i$ pa kvadratni koren iz $-1$. Gaussova cela števila razširjajo običajna cela števila in imajo tako kot ta lastnosti, kot je enolična faktorizacija na praštevila. Takšne razširitve običajnih celih ali racionalnih števil so znane kot algebraična številska polja. Novi argument Gaussova cela števila zamenja z bolj zapletenimi posplošitvami iz algebraične teorije števil z bogatejšimi simetrijami, ki lahko ustvarijo veliko več razlik enotske dolžine.

Natančen argument uporablja orodja, kot so neskončni stolpi razrednih polj in teorija Goloda–Šafareviča, da pokaže, da številska polja, potrebna za argument, dejansko obstajajo. Te ideje so bile algebraičnim teoretikom števil dobro znane, vendar je bilo veliko presenečenje, da imajo ti pojmi posledice za geometrijska vprašanja v evklidski ravnini.

Ta rezultat pomeni pomemben trenutek v interakciji med UI in matematiko: sistem UI je samostojno razrešil dolgo odprt problem v središču aktivnega področja. Ponuja tudi zgodnji vpogled v novo vrsto sodelovanja med UI in človeškimi matematiki. V tem primeru spremljevalno delo zunanjih matematikov zariše bistveno bogatejšo sliko kot sama izvirna rešitev.

Kot v spremljevalni opombi piše Thomas Bloom:

»Ko presojam pomembnost in vpliv dokaza, ki ga je ustvarila UI, si zastavim vprašanje: nas je to o problemu naučilo kaj novega? Ali zdaj bolje razumemo diskretno geometrijo? Mislim, da je odgovor zmerni da: to kaže, da imajo konstrukcije iz teorije števil o tovrstnih vprašanjih povedati veliko več, kot smo domnevali; poleg tega je lahko potrebna teorija števil zelo globoka. Nedvomno si bodo številni algebraični teoretiki števil v prihodnjih mesecih podrobno ogledali druge odprte probleme v diskretni geometriji.«

Del tega, zaradi česar je rezultat opazen, je nepričakovana povezava med algebraično teorijo števil in diskretno geometrijo, ki jo je razkrila rešitev. Ne razreši le določene domneve, temveč lahko matematikom ponudi most za začetek raziskovanja nadaljnjih sorodnih problemov.

Bloom nakaže tudi širšo možnost:

»Meje znanja so zelo nazobčane in nedvomno bodo prihodnji meseci in leta prinesli podobne uspehe na številnih drugih področjih matematike, kjer bo UI z razkrivanjem nepričakovanih povezav in potiskanjem obstoječega tehničnega aparata do skrajnih meja razrešila dolgo odprte probleme. UI nam pomaga celoviteje raziskovati katedralo matematike, ki smo jo gradili skozi stoletja; katera druga še nevidna čudesa čakajo v ozadju?«

Ta rezultat ponuja obetaven primer: UI prispeva ne le rešitev, temveč matematično odkritje, katerega pomen postane jasnejši in bogatejši z naknadnim človeškim razumevanjem.

Sporočilo je širše od tega konkretnega rezultata. Boljše matematično sklepanje lahko UI naredi za močnejšega raziskovalnega partnerja: nekaj, kar lahko ohranja skupaj zahtevne miselne niti, povezuje ideje med oddaljenimi področji znanja, izpostavi obetavne poti, ki jih strokovnjaki morda niso postavili v ospredje, in pomaga raziskovalcem napredovati pri problemih, ki bi bili sicer preveč zapleteni ali časovno zahtevni.

Te zmožnosti so pomembne tudi zunaj matematike. Če lahko model ohrani zapleten argument skladen, povezuje ideje med oddaljenimi področji znanja in ustvari delo, ki prestane strokovni pregled, so to uporabne sposobnosti tudi v biologiji, fiziki, znanosti o materialih, inženirstvu in medicini, ter del naše dolgoročnejše poti k bolj avtomatiziranemu raziskovanju: sistemom, ki lahko znanstvenikom in inženirjem pomagajo raziskati več idej in se lotiti težjih tehničnih vprašanj.

UI bo kmalu začela prevzemati zelo resno vlogo v ustvarjalnih delih raziskovanja, predvsem pa v samih raziskavah UI. Čeprav ta napredek ni nepričakovan, krepi občutek nujnosti, ki ga imamo glede razumevanja te naslednje faze razvoja UI, izzivov usklajevanja zelo inteligentnih sistemov in prihodnosti sodelovanja med človekom in UI.

Ta prihodnost je še vedno odvisna od človeške presoje. Strokovnost postaja bolj dragocena, ne manj. UI lahko pomaga iskati, predlagati in preverjati. Ljudje izbirajo probleme, ki so pomembni, razlagajo rezultate in odločajo, katerim vprašanjem se bodo posvetili naslednje.