OpenAI model opovrgnuo je središnju pretpostavku u diskretnoj geometriji

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

Ovo je problem jediničnih udaljenosti u ravnini, koji je prvi postavio Paul Erdős 1946. godine. To je jedno od najpoznatijih pitanja u kombinatornoj geometriji, lako za izreći, a iznimno teško za riješiti. Knjiga iz 2005. 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 s Princetona, opisuje ga kao „jedan od Erdősevih omiljenih problema”. Erdős je čak ponudio novčanu nagradu za rješenje ovog problema.

Danas dijelimo proboj u problemu jedinične udaljenosti. Od Erdősova izvornog rada prevladavalo je uvjerenje da su konstrukcije „kvadratne mreže” prikazane niže u biti optimalne za maksimiziranje broja parova na jediničnoj udaljenosti. Interni OpenAI model opovrgnuo je ovu dugotrajnu pretpostavku, dajući beskonačnu familiju primjera koji donose polinomsko poboljšanje. Dokaz je provjerila skupina vanjskih matematičara. Također su napisali popratni rad koji objašnjava argument te pruža dodatnu pozadinu i kontekst o važnosti rezultata.

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

Ovaj dokaz važna je prekretnica za matematičku i AI zajednicu. Označava prvi put da je istaknuti otvoreni problem, središnji za jedno potpodručje matematike, autonomno riješila umjetna inteligencija. Također pokazuje dubinu rasuđivanja koju ti sustavi sada podržavaju. Matematika pruža posebno jasno ispitno okruženje za rasuđivanje: problemi su precizni, potencijalni dokazi mogu se provjeriti, a dugačak argument funkcionira samo ako rasuđivanje ostane dosljedno od početka do kraja. Značajna je i metoda kojom je problem riješen. Dokaz primjenjuje neočekivane, sofisticirane ideje iz algebarske teorije brojeva na elementarno geometrijsko pitanje.

Dobitnik Fieldsove medalje Tim Gowers u popratnom radu rezultat naziva „prekretnicom u AI matematici”. Prema riječima vodećeg teoretičara brojeva Arula Shankara, „Po mom mišljenju ovaj rad pokazuje da današnji AI modeli nadilaze ulogu pukih pomagača 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). Popratni rad vodećih vanjskih matematičara dostupan je ovdje⁠(otvara se u novom prozoru). Skraćenu verziju modelovog lanca misli možete pronaći ovdje⁠(otvara se u novom prozoru).

Neka $u(n)$ bude najveći mogući broj parova na jediničnoj udaljenosti među $n$ točaka u ravnini. Primjere koji postižu linearnu stopu rasta lako je konstruirati: postavljanje $n$ točaka na pravac daje $n-1$ parova, dok kvadratna mreža daje oko $2n$ parova. Ispostavlja se da prethodno najbolja poznata konstrukcija, koja proizlazi iz skalirane kvadratne mreže, daje još više: $n^{1 + C / \log \log(n)}$ za konstantu $C$. Budući da $\log \log(n)$ teži beskonačnosti s $n$, dodatni član u eksponentu teži prema $0$, što znači da te konstrukcije postižu rast tek neznatno brži od linearnog. Desetljećima se široko vjerovalo da je ta stopa u biti 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 s $n$ teži prema $0$.

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

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

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

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

Erdősova izvorna donja granica može se razumjeti preko Gaussovih cijelih brojeva: brojeva oblika $a+bi$, gdje su $a$ i $b$ cijeli brojevi, a $i$ kvadratni korijen iz $-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 poopćenjima iz algebarske teorije brojeva s bogatijim simetrijama koje mogu stvoriti mnogo više razlika jedinične duljine.

Precizan argument koristi alate poput beskonačnih tornjeva klasnih polja i teorije Golod–Shafarevich kako bi pokazao da polja brojeva potrebna za argument doista postoje. Te su ideje bile dobro poznate algebarskim teoretičarima brojeva, ali bilo je veliko iznenađenje da ti koncepti imaju implikacije za geometrijska pitanja u euklidskoj ravnini.

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

Kako Thomas Bloom piše u popratnoj bilješci:

„Kada procjenjujem važnost i utjecaj dokaza koji je generirao AI, pitam se: je li nas to naučilo nečemu novom o problemu? Razumijemo li sada bolje diskretnu geometriju? Mislim da je odgovor umjereno potvrdan: ovo pokazuje da konstrukcije iz teorije brojeva o ovakvim pitanjima imaju mnogo više za reći nego što smo sumnjali; štoviše, da potrebna teorija brojeva može biti vrlo duboka. Nema sumnje da će mnogi algebarski teoretičari brojeva u nadolazećim mjesecima pomno promotriti 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 rezultat čini značajnim. On ne razrješava samo određenu pretpostavku, nego matematičarima može pružiti most za početak istraživanja daljnjih povezanih problema.

Bloom također upućuje na širu mogućnost:

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

Ovaj rezultat pruža obećavajući primjer: AI pridonosi ne samo rješenjem, nego i matematičkim otkrićem čije značenje postaje jasnije i bogatije kroz naknadno ljudsko razumijevanje.

Pouka je veća od ovog konkretnog rezultata. Bolje matematičko rasuđivanje može AI učiniti snažnijim istraživačkim partnerom: nečim što može održati na okupu teške tokove misli, povezivati ideje iz udaljenih područja znanja, iznositi obećavajuće smjerove koje stručnjaci možda nisu stavili u prvi plan i pomagati istraživačima da napreduju na problemima koji bi inače bili previše složeni ili vremenski zahtjevni.

Te su sposobnosti važne i izvan matematike. Ako model može održati složen argument koherentnim, povezivati ideje iz udaljenih područja znanja i proizvesti rad koji izdrži stručnu provjeru, to su korisne sposobnosti i u biologiji, fizici, znanosti o materijalima, inženjerstvu i medicini, a dio su našeg dugoročnijeg puta prema automatiziranijem istraživanju: sustavima koji mogu pomoći znanstvenicima i inženjerima istražiti više ideja i baviti se težim tehničkim pitanjima.

AI će uskoro početi preuzimati vrlo 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 sljedeće faze razvoja AI-ja, izazova usklađivanja vrlo inteligentnih sustava i budućnosti suradnje ljudi i AI-ja.

Ta budućnost i dalje ovisi o ljudskoj prosudbi. Stručnost postaje vrjednija, 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.