OpenAI model opovrgao je ključnu pretpostavku u diskretnoj geometriji

Gotovo 80 godina matematičari proučavaju varljivo jednostavno pitanje: ako postavite $n$ tačaka u ravni, koliko parova tačaka može biti tačno na udaljenosti $1$?

Ovo je problem jedinične udaljenosti u ravni, koji je prvi postavio Paul Erdős 1946. godine. To je jedno od najpoznatijih pitanja u kombinatornoj geometriji, lako za iskazati, a izuzetno teško za riješiti. Knjiga iz 2005. godine Research Problems in Discrete Geometry, autora Brassa, Mosera i Pacha, naziva ga „možda najpoznatijim (i najjednostavnijim za objasniti) problemom u kombinatornoj geometriji“. Noga Alon, vodeći kombinatoričar na Princetonu, opisuje ga kao „jedan od Erdősovih omiljenih problema”. Erdős je čak ponudio novčanu nagradu za rješavanje ovog problema.

Danas dijelimo proboj u problemu jedinične udaljenosti. Od Erdősovog izvornog rada, preovladavalo je uvjerenje da su konstrukcije „kvadratne mreže“ prikazane niže u suštini optimalne za maksimiziranje broja parova na jediničnoj udaljenosti. Interni OpenAI model opovrgao je ovu dugotrajnu pretpostavku, pružajući beskonačnu familiju primjera koji daju polinomsko poboljšanje. Dokaz je provjerila grupa vanjskih matematičara. Oni su također napisali prateći rad koji objašnjava argument i pruža dodatnu pozadinu i kontekst za značaj rezultata.

Rezultat je značajan i po tome kako je pronađen. Dokaz je došao od novog općenamjenskog modela rezonovanja, a ne od sistema posebno treniranog za matematiku, nadograđenog za pretraživanje strategija dokazivanja ili posebno usmjerenog na problem jedinične udaljenosti. Kao dio šireg napora da testiramo mogu li napredni modeli doprinijeti istraživanjima na granici nauke, evaluirali smo ga na zbirci Erdősovih problema. U ovom slučaju proizveo je dokaz koji rješava otvoreni problem.

Ovaj dokaz je važna prekretnica za matematičku i AI zajednicu. Ovo je prvi put da je istaknuti otvoreni problem, centralan za jednu podoblast matematike, autonomno riješila AI. To također pokazuje dubinu rezonovanja koju ovi sistemi sada podržavaju. Matematika pruža posebno jasno testno okruženje za rezonovanje: problemi su precizni, potencijalni dokazi se mogu provjeriti, a dug argument funkcioniše samo ako rezonovanje ostane dosljedno od početka do kraja. Metoda kojom je problem riješen također je značajna. Dokaz primjenjuje neočekivane, sofisticirane ideje iz algebarske teorije brojeva na elementarno geometrijsko pitanje.

Dobitnik Fieldsove medalje Tim Gowers, pišući u pratećem radu, naziva rezultat „prekretnicom u AI matematici“. Prema riječima vodećeg teoretičara brojeva Arula Shankara, „Po mom mišljenju ovaj rad pokazuje da trenutni AI modeli nadilaze puku pomoć ljudskim matematičarima – sposobni su imati originalne domišljate ideje, a zatim ih i dovesti do ostvarenja“.

Dokaz je dostupan ovdje⁠(otvara se u novom prozoru). Prateći rad vodećih vanjskih matematičara dostupan je ovdje⁠(otvara se u novom prozoru). Skraćenu verziju lanca razmišljanja modela možete pronaći ovdje⁠(otvara se u novom prozoru).

Neka je $u(n)$ najveći mogući broj parova na jediničnoj udaljenosti među $n$ tačaka u ravni. Primjere koji postižu linearnu stopu rasta lako je konstruisati: postavljanje $n$ tačaka na pravu daje $n-1$ parova, dok kvadratna mreža daje oko $2n$ parova. Ispostavlja se da ranije najbolja poznata konstrukcija, koja dolazi iz reskalirane kvadratne mreže, daje još više: $n^{1 + C / \log \log(n)}$ za neku konstantu $C$. Budući da $\log \log(n)$ teži beskonačnosti s $n$, dodatni član u eksponentu teži ka $0$, što znači da ove konstrukcije postižu rast samo neznatno brži od linearnog. Decenijama se široko vjerovalo da je ova stopa u suštini najbolja moguća i da nijedna konstrukcija ne može značajno nadmašiti kvadratnu mrežu. Tehnički rečeno, Erdős je pretpostavio gornju granicu $n^{1+o(1)}$, u kojoj dodatni $o(1)$ označava član koji teži ka $0$ s $n$.

Naš novi rezultat opovrgava ovu pretpostavku. Preciznije, za beskonačno mnogo vrijednosti $n$, dokaz konstruiše konfiguracije od $n$ tačaka s najmanje $n^{1+\delta}$ parova na jediničnoj udaljenosti, za neki fiksni eksponent $\delta > 0$. (Izvorni AI dokaz ne daje eksplicitno $\delta$, ali nadolazeće usavršavanje profesora matematike s Princetona Willa Sawina pokazalo je da se može uzeti $\delta=0.014$.)

Historija problema pomaže da se shvati zašto je rezultat iznenađujući. Najbolja poznata donja granica ostala je u suštini nepromijenjena još od Erdősove izvorne konstrukcije iz 1946. godine. Najbolja gornja granica, $O(n^{4/3})$, potiče iz rada Spencera, Szemerédija i Trottera iz 1984. godine, i uprkos kasnijim doradama i povezanim strukturnim radovima Székelyja, Katza i Siliera, Pacha, Raza i Solymosija te drugih, gornja granica je ostala u suštini nepromijenjena. Kao dokaz u prilog pretpostavci, Matoušek i Alon-Bucić-Sauermann proučavali su problem s neeuklidskim udaljenostima u ravni i dokazali da se „većina“ tih neeuklidskih udaljenosti u nekom smislu pokorava pretpostavci.

Iznenađujuće, ključni sastojci konstrukcije dolaze iz sasvim drugog dijela matematike poznatog kao algebarska teorija brojeva, koja proučava pojmove poput faktorizacije u proširenjima cijelih brojeva poznatim kao algebarska polja brojeva.

Na visokom nivou, dokaz počinje poznatom geometrijskom idejom i gura je u neočekivanom smjeru.

Erdősova izvorna donja granica može se razumjeti kroz Gaussove cijele brojeve: brojeve oblika $a+bi$, gdje su $a$ i $b$ cijeli brojevi, a $i$ kvadratni korijen od $-1$. Gaussovi cijeli brojevi proširuju obične cijele brojeve i, poput njih, imaju svojstva kao što je jedinstvena faktorizacija na proste brojeve. Takva proširenja običnih cijelih ili racionalnih brojeva poznata su kao algebarska polja brojeva. Novi argument zamjenjuje Gaussove cijele brojeve složenijim generalizacijama iz algebarske teorije brojeva s bogatijim simetrijama koje mogu stvoriti mnogo više razlika jedinične dužine.

Precizan argument koristi alate kao što su beskonačni tornjevi klasnih polja i Golod–Šafarevičeva teorija kako bi pokazao da polja brojeva potrebna za argument zaista postoje. Ove ideje bile su dobro poznate algebarskim teoretičarima brojeva, ali je bilo veliko iznenađenje da ti koncepti imaju implikacije za geometrijska pitanja u euklidskoj ravni.

Ovaj rezultat označava važan trenutak u interakciji između AI-ja i matematike: AI sistem je autonomno riješio dugotrajan otvoreni problem u središtu aktivnog polja. To također nudi rani uvid u novu vrstu saradnje između AI-ja i ljudskih matematičara. U ovom slučaju, prateći rad vanjskih matematičara daje znatno bogatiju sliku nego samo izvorno rješenje.

Kako Thomas Bloom piše u pratećoj bilješci:

„Kada procjenjujem važnost i utjecaj dokaza koji je generisala AI, pitanje koje sebi postavljam glasi: je li nas ovo naučilo nečemu novom o problemu? Razumijemo li sada diskretnu geometriju bolje? Mislim da je odgovor umjereno da: ovo pokazuje da konstrukcije iz teorije brojeva imaju mnogo više toga za reći o ovakvim pitanjima nego što smo pretpostavljali; štaviše, da potrebna teorija brojeva može biti veoma duboka. Nema sumnje da će mnogi algebarski teoretičari brojeva u narednim mjesecima pažljivo pogledati druge otvorene probleme u diskretnoj geometriji.“

Neočekivana veza između algebarske teorije brojeva i diskretne geometrije koju je rješenje otkrilo dio je onoga što ovaj rezultat čini značajnim. On ne razrješava samo određenu pretpostavku, već matematičarima može pružiti most za početak istraživanja daljnjih povezanih problema.

Bloom također ukazuje na širu mogućnost:

„Granice znanja vrlo su nazubljene i nema sumnje da će naredni mjeseci i godine donijeti slične uspjehe u mnogim drugim oblastima matematike, gdje će dugotrajni otvoreni problemi biti riješeni tako što AI otkriva neočekivane veze i gura postojeći tehnički aparat do njegovih granica. AI nam pomaže da potpunije istražimo katedralu matematike koju smo gradili kroz stoljeća; koja još neviđena čuda čekaju iza kulisa?“

Ovaj rezultat pruža obećavajući primjer: AI doprinosi ne samo rješenjem, već i matematičkim otkrićem čiji značaj postaje jasniji i bogatiji kroz naknadno ljudsko razumijevanje.

Pouka je veća od ovog konkretnog rezultata. Bolje matematičko rezonovanje može učiniti AI snažnijim istraživačkim partnerom: nečim što može održati na okupu teške tokove misli, povezivati ideje kroz udaljene oblasti znanja, iznositi obećavajuće pravce kojima stručnjaci možda nisu dali prioritet i pomagati istraživačima da napreduju na problemima koji bi inače bili previše složeni ili vremenski zahtjevni za rješavanje.

Te sposobnosti su važne i izvan matematike. Ako model može održati složen argument koherentnim, povezivati ideje kroz udaljene oblasti znanja i proizvesti rad koji izdrži stručnu provjeru, to su korisne sposobnosti i u biologiji, fizici, nauci o materijalima, inženjerstvu i medicini, i dio su našeg dugoročnijeg puta ka automatizovanijem istraživanju: sistemima koji mogu pomoći naučnicima i inženjerima da istraže više ideja i bave se težim tehničkim pitanjima.

AI će uskoro početi preuzimati veoma ozbiljnu ulogu u kreativnim dijelovima istraživanja, a najvažnije i samog AI istraživanja. Iako ovaj napredak nije neočekivan, on pojačava hitnost koju osjećamo u vezi s razumijevanjem ove naredne faze razvoja AI-ja, izazova usklađivanja veoma inteligentnih sistema i budućnosti saradnje ljudi i AI-ja.

Ta budućnost i dalje zavisi od ljudske prosudbe. Stručnost postaje vrednija, a ne manje vrijedna. AI može pomoći u pretraživanju, predlaganju i provjeri. Ljudi biraju probleme koji su važni, tumače rezultate i odlučuju koja pitanja dalje slijediti.