„OpenAI“ modelis paneigė pagrindinę diskrečiosios geometrijos hipotezę

Beveik 80 metų matematikai nagrinėjo iš pažiūros paprastą klausimą: jeigu plokštumoje pažymėsime $n$ taškų, kiek taškų porų gali skirti lygiai $1$ atstumas?

Tai plokštumos vienetinio atstumo uždavinys, kurį 1946 m. pirmasis suformulavo Paulas Erdősas. Tai vienas geriausiai žinomų kombinatorinės geometrijos klausimų, kurį lengva suformuluoti, tačiau nepaprastai sunku išspręsti. 2005 m. P. Brasso, W. Moserio ir J. Pacho knygoje Research Problems in Discrete Geometry jis vadinamas „ko gero, geriausiai žinomu (ir paprasčiausiai paaiškinamu) kombinatorinės geometrijos uždaviniu“. Žymus Prinstono kombinatorikos specialistas Noga Alonas jį apibūdina kaip „vieną mėgstamiausių P. Erdőso uždavinių“. Už šio uždavinio išsprendimą P. Erdősas netgi buvo pasiūlęs piniginį prizą.

Šiandien pranešame apie esminį proveržį sprendžiant vienetinio atstumo uždavinį. Nuo pat pradinių P. Erdőso darbų vyravo nuomonė, kad toliau pavaizduotos „kvadratinio tinklelio“ konstrukcijos yra iš esmės optimalios norint gauti didžiausią vienetinio atstumo porų skaičių. Vidinis „OpenAI“ modelis paneigė šią seną hipotezę ir pateikė begalinę pavyzdžių šeimą, užtikrinančią polinominį pagerinimą. Šį įrodymą patikrino nepriklausomų matematikų grupė. Jie taip pat parašė papildomą straipsnį, kuriame paaiškina šį argumentą ir pateikia daugiau informacijos bei konteksto apie šio rezultato reikšmę.

Šis rezultatas išsiskiria ir tuo, kaip jis buvo atrastas. Įrodymą pateikė naujas bendrosios paskirties protavimo modelis, o ne specialiai matematikai išmokyta, įrodymų strategijų paieškai pritaikyta ar konkrečiai vienetinio atstumo uždaviniui sukurta sistema. Vykdydami platesnį tyrimą, ar pažangūs modeliai gali prisidėti prie priešakinių tyrimų, išbandėme šį modelį su P. Erdőso uždavinių rinkiniu. Šiuo atveju modelis pateikė įrodymą, kuris išsprendžia šį atvirąjį uždavinį.

Šis įrodymas – svarbus pasiekimas tiek matematikos, tiek DI bendruomenėms. Tai pirmas kartas, kai garsų, atvirą ir vienai iš matematikos sričių ypač svarbų uždavinį savarankiškai išsprendė DI. Tai taip pat parodo, kokį protavimo gylį dabar pasiekė šios sistemos. Matematika – ypač aiški terpė protavimui išbandyti: uždaviniai yra tikslūs, galimus įrodymus galima patikrinti, o ilgas argumentas tinka tik tada, kai protavimo seka nuosekli nuo pradžios iki galo. Šio uždavinio sprendimo būdas taip pat vertas dėmesio. Šiame įrodyme elementariam geometrijos klausimui spręsti pasitelkiamos netikėtos ir sudėtingos algebrinės skaičių teorijos idėjos.

Fildso premijos laureatas Timas Gowersas papildomame straipsnyje šį rezultatą vadina „lūžiu DI matematikoje“. Žymus skaičių teoretikas Arulas Shankaras teigia: „Mano nuomone, šis straipsnis įrodo, kad dabartiniai DI modeliai yra daugiau nei tik padėjėjai žmonėms matematikams – jie geba pasiūlyti originalių bei išradingų idėjų ir jas sėkmingai įgyvendinti.“

Įrodymą rasite čia⁠(atsidaro naujame lange). Žymių nepriklausomų matematikų parengtą papildomą straipsnį rasite čia⁠(atsidaro naujame lange). Sutrumpintą modelio minčių grandinės versiją rasite čia⁠(atsidaro naujame lange).

Tarkime, $u(n)$ žymi didžiausią galimą vienetinio atstumo porų skaičių tarp $n$ taškų plokštumoje. Lengva sukonstruoti pavyzdžių, kurių augimo greitis yra tiesinis: išdėsčius $n$ taškų vienoje tiesėje, gaunama $n-1$ porų, o kvadratiniame tinklelyje – apie $2n$ porų. Paaiškėjo, kad iki šiol geriausia žinoma konstrukcija, gauta iš pakeisto mastelio kvadratinio tinklelio, leidžia gauti dar daugiau: $n^{{1 + C / \log \log(n)}}$ (čia $C$ – konstanta). Kadangi didėjant $n$, reikšmė $\log \log(n)$ artėja į begalybę, papildomas narys laipsnio rodiklyje artėja prie $0$. Vadinasi, šių konstrukcijų augimas tik šiek tiek greitesnis už tiesinį. Dešimtmečius vyravo įsitikinimas, kad šis greitis iš esmės yra geriausias įmanomas ir jokia konstrukcija negali reikšmingai pagerinti kvadratinio tinklelio rezultatų. Techniniais terminais kalbant, P. Erdősas iškėlė hipotezę dėl viršutinio rėžio $n^{{1+o(1)}}$, kur papildomas $o(1)$ reiškia narį, artėjantį prie $0$ didėjant $n$.

Mūsų naujasis rezultatas paneigia šią hipotezę. Tiksliau, be galo daugeliui $n$ reikšmių šis įrodymas sukonstruoja $n$ taškų konfigūracijas su mažiausiai $n^{{1+\delta}}$ vienetinio atstumo porų (čia $\delta > 0$ – fiksuotas rodiklis). (Pradiniame DI įrodyme aiški $\delta$ reikšmė nepateikiama, tačiau būsimame Prinstono matematikos profesoriaus Willo Sawino patikslinime įrodyta, kad galima imti $\delta=0.014$.)Uždavinio istorija padeda suprasti, kodėl šis rezultatas stebina. Geriausias žinomas apatinis rėžis iš esmės nepasikeitė nuo pradinės P. Erdőso 1946 m. konstrukcijos. Geriausias viršutinis rėžis, $O(n^{{4/3}})$, siekia 1984 m. J. Spencerio, E. Szemerédi ir W. Trotterio darbus, ir, nepaisant vėlesnių patobulinimų bei susijusių struktūrinių L. Székely, N. Katzo ir G. Silierio, J. Pacho, O. Razo, J. Solymosi ir kitų mokslininkų darbų, šis viršutinis rėžis iš esmės liko nepakitęs. Kaip įrodymą, pagrindžiantį šią hipotezę, J. Matoušekas, N. Alonas, M. Bucić ir L. Sauermann ištyrė šį uždavinį su neeuklidiniais atstumais plokštumoje ir įrodė, kad „dauguma“ šių neeuklidinių atstumų tam tikra prasme atitinka hipotezę.

Stebėtina, bet pagrindiniai konstrukcijos elementai atėjo iš visai kitos matematikos srities – algebrinės skaičių teorijos, tyrinėjančios tokias sąvokas kaip skaidymas sveikųjų skaičių plėtiniuose, vadinamuose algebriniais skaičių kūnais.

Apibendrintai kalbant, įrodymas pradedamas pažįstama geometrine idėja ir pasukamas netikėta linkme.

Pradinį P. Erdőso apatinį rėžį galima suprasti pasitelkus Gauso sveikuosius skaičius: tai $a+bi$ formos skaičiai, kur $a$ ir $b$ yra sveikieji skaičiai, o $i$ – kvadratinė šaknis iš $-1$. Gauso sveikieji skaičiai praplečia įprastų sveikųjų skaičių aibę ir, kaip ir jie, pasižymi tokiomis savybėmis kaip vienareikšmis skaidymas pirminiais dauginamaisiais. Tokie įprastų sveikųjų ar racionaliųjų skaičių plėtiniai vadinami algebriniais skaičių kūnais. Naujajame įrodyme Gauso sveikieji skaičiai pakeičiami sudėtingesniais algebrinės skaičių teorijos apibendrinimais su gausesnėmis simetrijomis, galinčiomis sukurti kur kas daugiau vienetinio ilgio skirtumų.

Tiksliame įrodyme naudojamos tokios priemonės kaip begaliniai klasių kūnų bokštai bei Golodo ir Šafarevičiaus teorija, siekiant parodyti, kad įrodymui reikalingi skaičių kūnai iš tiesų egzistuoja. Šios idėjos buvo puikiai žinomos algebrinės skaičių teorijos specialistams, tačiau tapo didžiuliu netikėtumu, kad jos turi reikšmės sprendžiant geometrijos klausimus Euklido plokštumoje.

Šis rezultatas – svarbus DI ir matematikos sąveikos momentas: DI sistema savarankiškai išsprendė ilgai neišspręstą atvirą uždavinį, esantį aktyviai tiriamos srities centre. Tai taip pat leidžia iš anksto pažvelgti į naujo pobūdžio bendradarbiavimą tarp DI ir žmonių matematikų. Šiuo atveju nepriklausomų matematikų parengtas papildomas darbas atskleidžia kur kas platesnį vaizdą nei vien tik pradinis sprendimas.

Kaip papildomame tekste teigia Thomas Bloomas:

„Vertindamas DI sukurto įrodymo svarbą bei įtaką, savęs klausiu: ar tai išmokė mus kažko naujo apie šį uždavinį? Ar dabar geriau suprantame diskrečiąją geometriją? Manau, kad atsakymas yra nuosaikus „taip“: paaiškėjo, kad skaičių teorijos konstrukcijos gali gerokai daugiau pasakyti apie tokio pobūdžio klausimus, nei mes manėme; be to, reikiama skaičių teorija gali būti itin gili. Neabejoju, kad ateinančiais mėnesiais daugelis algebrinės skaičių teorijos specialistų atidžiai išnagrinės ir kitus atvirus diskrečiosios geometrijos uždavinius.“

Šio sprendimo atskleistas netikėtas ryšys tarp algebrinės skaičių teorijos ir diskrečiosios geometrijos – viena iš priežasčių, dėl kurių šis rezultatas toks reikšmingas. Jis ne tik išsprendžia konkrečią hipotezę, bet ir gali tapti tiltu, padėsiančiu matematikams pradėti tyrinėti kitus susijusius uždavinius.

T. Bloomas taip pat atkreipia dėmesį į platesnę perspektyvą:

„Pažinimo ribos – labai netolygios, ir neabejotina, kad ateinančiais mėnesiais bei metais sulauksime panašios sėkmės daugelyje kitų matematikos sričių, kur ilgai neišspręstus atvirus uždavinius išspręs DI, atskleisdamas netikėtus ryšius ir maksimaliai išnaudodamas esamas technines priemones. DI padeda mums dar išsamiau tyrinėti per šimtmečius pastatytą matematikos katedrą; kokie dar neregėti stebuklai slypi užkulisiuose?“

Šis rezultatas – daug žadantis pavyzdys: DI pateikia ne tik sprendimą, bet ir matematinį atradimą, kurio reikšmė tampa aiškesnė ir gilesnė žmonėms toliau jį analizuojant ir geriau suprantant.

Pagrindinė išvada – kur kas platesnė nei šis konkretus rezultatas. Geresni matematinio protavimo gebėjimai gali paversti DI stipresniu tyrimų partneriu, galinčiu nuosekliai išlaikyti sudėtingas minčių sekas, sujungti idėjas iš skirtingų mokslo sričių, atskleisti daug žadančias kryptis, kurioms ekspertai galbūt neteikė prioriteto, ir padėti tyrėjams pasistūmėti sprendžiant uždavinius, kurie antraip būtų per daug sudėtingi arba reikalautų per daug laiko.

Šie gebėjimai svarbūs ne tik matematikoje. Jei modelis gali išlaikyti sudėtingo argumento nuoseklumą, sujungti idėjas iš skirtingų mokslo sričių ir sukurti ekspertų patikrinimą išlaikantį darbą, tokie gebėjimai taip pat naudingi biologijoje, fizikoje, medžiagotyroje, inžinerijoje bei medicinoje. Tai – mūsų ilgalaikio kelio link labiau automatizuotų tyrimų dalis: sistemos, galinčios padėti mokslininkams ir inžinieriams nagrinėti daugiau idėjų bei spręsti sudėtingesnius techninius klausimus.

DI netrukus ims atlikti labai svarbų vaidmenį kūrybiniuose tyrimų etapuose ir, kas svarbiausia, pačiuose DI tyrimuose. Nors šis progresas nėra netikėtas, jis skatina dar skubiau siekti perprasti šį kitą DI plėtros etapą, labai intelektualių sistemų suderinimo iššūkius ir žmogaus bei DI bendradarbiavimo ateitį.

Ši ateitis vis dar priklauso nuo žmogaus vertinimo. Ekspertinės žinios tampa tik dar vertingesnės. DI gali padėti ieškoti, siūlyti ir tikrinti. Žmonės pasirenka svarbiausius uždavinius, interpretuoja rezultatus ir sprendžia, kokius klausimus nagrinėti toliau.