Model OpenAI vyvrátil kľúčovú domnienku v diskrétnej geometrii

Takmer 80 rokov matematici skúmali zdanlivo jednoduchú otázku: ak umiestnite $n$ bodov do roviny, koľko dvojíc bodov môže byť od seba presne vo vzdialenosti $1$?

Toto je problém jednotkových vzdialeností v rovine, ktorý prvýkrát sformuloval Paul Erdős v roku 1946. Je to jedna z najznámejších otázok kombinatorickej geometrie, ľahko formulovateľná a mimoriadne ťažko riešiteľná. Kniha z roku 2005 Research Problems in Discrete Geometry od Brassa, Mosera a Pacha ho označuje za „možno najznámejší (a najjednoduchšie vysvetliteľný) problém v kombinatorickej geometrii“. Noga Alon, popredný kombinatorik pôsobiaci na Princetone, ho opisuje ako „jeden z Erdősových obľúbených problémov“. Erdős dokonca ponúkol finančnú odmenu za vyriešenie tohto problému.

Dnes sa delíme o prelom v probléme jednotkovej vzdialenosti. Od Erdősovej pôvodnej práce prevládalo presvedčenie, že konštrukcie „štvorcovej mriežky“ zobrazené nižšie boli v podstate optimálne na maximalizáciu počtu dvojíc vo vzdialenosti jedna. Interný model OpenAI túto dlhoročnú domnienku vyvrátil a poskytol nekonečnú rodinu príkladov, ktoré prinášajú polynomiálne zlepšenie. Dôkaz skontrolovala skupina externých matematikov. Napísali aj sprievodný článok, ktorý vysvetľuje argument a poskytuje ďalšie pozadie a kontext významu výsledku.

Pozoruhodný je aj spôsob, akým bol výsledok nájdený. Dôkaz pochádza z nového všeobecného uvažovacieho modelu, nie zo systému trénovaného špeciálne na matematiku, vybaveného na prehľadávanie dôkazových stratégií alebo zameraného konkrétne na problém jednotkovej vzdialenosti. V rámci širšieho úsilia otestovať, či pokročilé modely môžu prispieť k špičkovému výskumu, sme ho vyhodnotili na zbierke Erdősových problémov. V tomto prípade vytvoril dôkaz riešiaci otvorený problém.

Tento dôkaz je dôležitým míľnikom pre matematickú aj AI komunitu. Je to prvýkrát, čo AI autonómne vyriešila významný otvorený problém, ústredný pre pododbor matematiky. Zároveň ukazuje hĺbku uvažovania, ktorú tieto systémy dnes podporujú. Matematika poskytuje mimoriadne jasné testovacie prostredie pre uvažovanie: problémy sú presné, možné dôkazy sa dajú overiť a dlhý argument funguje len vtedy, ak uvažovanie drží pohromade od začiatku do konca. Pozoruhodná je aj metóda, ktorou bol problém vyriešený. Dôkaz prináša nečakané, sofistikované myšlienky z algebraickej teórie čísel na elementárnu geometrickú otázku.

Držiteľ Fieldsovej medaily Tim Gowers v sprievodnom článku nazýva výsledok „míľnikom v AI matematike“. Podľa popredného teoretika čísel Arula Shankara „Podľa môjho názoru tento článok ukazuje, že súčasné modely AI presahujú úlohu pomocníkov ľudských matematikov – sú schopné prichádzať s originálnymi dômyselnými nápadmi a potom ich doviesť do úspešného konca“.

Dôkaz je dostupný tu⁠(otvorí sa v novom okne). Sprievodný článok popredných externých matematikov je dostupný tu⁠(otvorí sa v novom okne). Skrátenú verziu reťazca úvah modelu nájdete tu⁠(otvorí sa v novom okne).

Nech $u(n)$ je najväčší možný počet dvojíc vo vzdialenosti jedna medzi $n$ bodmi v rovine. Príklady dosahujúce lineárnu mieru rastu sa dajú zostrojiť ľahko: umiestnenie $n$ bodov na priamku dáva $n-1$ dvojíc, zatiaľ čo štvorcová mriežka dáva asi $2n$ dvojíc. Predtým najlepšie známa konštrukcia, vychádzajúca zo škálovanej štvorcovej mriežky, sa ukazuje byť ešte silnejšia: dáva $n^{1 + C / \log \log(n)}$ pre konštantu $C$. Keďže $\log \log(n)$ s $n$ smeruje k nekonečnu, dodatočný člen v exponente smeruje k $0$, čo znamená, že tieto konštrukcie dosahujú rast len o málo rýchlejší než lineárny. Po desaťročia sa všeobecne verilo, že táto miera je v podstate najlepšia možná a žiadna konštrukcia nemôže štvorcovú mriežku výrazne prekonať. Technicky povedané, Erdős vyslovil domnienku horného odhadu $n^{1+o(1)}$, kde dodatočné $o(1)$ označuje člen smerujúci k $0$ s $n$.

Náš nový výsledok túto domnienku vyvracia. Presnejšie, pre nekonečne veľa hodnôt $n$ dôkaz konštruuje konfigurácie $n$ bodov s aspoň $n^{1+\delta}$ dvojicami vo vzdialenosti jedna, pre nejaký pevný exponent $\delta > 0$. (Pôvodný dôkaz AI neudáva explicitné $\delta$, ale pripravované spresnenie od profesora matematiky na Princetone Willa Sawina ukázalo, že možno vziať $\delta=0,014$.)

História problému pomáha pochopiť, prečo je výsledok prekvapivý. Najlepší známy dolný odhad zostal v podstate nezmenený od Erdősovej pôvodnej konštrukcie z roku 1946. Najlepší horný odhad, $O(n^{4/3})$, pochádza z práce Spencera, Szemerédiho a Trottera z roku 1984 a napriek neskorším spresneniam a súvisiacim štrukturálnym prácam Székelyho, Katza a Siliera, Pacha, Raza a Solymosiho a ďalších zostal horný odhad v podstate nezmenený. Ako dôkaz v prospech domnienky Matoušek a Alon-Bucić-Sauermann skúmali problém s neeuklidovskými vzdialenosťami v rovine a dokázali, že „väčšina“ týchto neeuklidovských vzdialeností sa v istom zmysle riadi touto domnienkou.

Prekvapivo, kľúčové ingrediencie konštrukcie pochádzajú z veľmi odlišnej časti matematiky známej ako algebraická teória čísel, ktorá skúma pojmy ako faktorizácia v rozšíreniach celých čísel známych ako algebraické číselné telesá.

Na vysokej úrovni sa dôkaz začína známou geometrickou myšlienkou a posúva ju nečakaným smerom.

Erdősov pôvodný dolný odhad možno pochopiť cez Gaussove celé čísla: čísla tvaru $a+bi$, kde $a$ a $b$ sú celé čísla a $i$ je druhá odmocnina z $-1$. Gaussove celé čísla rozširujú obyčajné celé čísla a podobne ako ony majú vlastnosti, ako je jednoznačná faktorizácia na prvočísla. Takéto rozšírenia obyčajných celých čísel alebo racionálnych čísel sú známe ako algebraické číselné telesá. Nový argument nahrádza Gaussove celé čísla zložitejšími zovšeobecneniami z algebraickej teórie čísel s bohatšími symetriami, ktoré môžu vytvoriť oveľa viac rozdielov jednotkovej dĺžky.

Presný argument používa nástroje ako nekonečné veže triednych telies a teóriu Goloda–Šafareviča, aby ukázal, že číselné telesá potrebné pre argument skutočne existujú. Tieto myšlienky boli algebraickým teoretikom čísel dobre známe, no bolo veľkým prekvapením, že tieto pojmy majú dôsledky pre geometrické otázky v euklidovskej rovine.

Tento výsledok predstavuje dôležitý moment v interakcii medzi AI a matematikou: systém AI autonómne vyriešil dlhodobý otvorený problém v centre aktívneho odboru. Zároveň ponúka prvý pohľad na nový druh spolupráce medzi AI a ľudskými matematikmi. V tomto prípade sprievodná práca externých matematikov vykresľuje podstatne bohatší obraz než samotné pôvodné riešenie.

Ako píše Thomas Bloom v sprievodnej poznámke:

„Keď posudzujem dôležitosť a vplyv dôkazu vytvoreného AI, kladiem si otázku: naučilo nás to o probléme niečo nové? Rozumieme teraz diskrétnej geometrii lepšie? Myslím si, že odpoveď je umiernené áno: ukazuje to, že konštrukcie z teórie čísel majú o takýchto otázkach čo povedať oveľa viac, než sme predpokladali; navyše, že potrebná teória čísel môže byť veľmi hlboká. Niet pochýb, že mnohí algebraickí teoretici čísel sa v nasledujúcich mesiacoch podrobne pozrú na ďalšie otvorené problémy diskrétnej geometrie.“

Nečakané prepojenie medzi algebraickou teóriou čísel a diskrétnou geometriou, ktoré riešenie odhalilo, je súčasťou toho, čo robí výsledok pozoruhodným. Neuzatvára len konkrétnu domnienku, ale môže matematikom poskytnúť most na začatie skúmania ďalších súvisiacich problémov.

Bloom tiež poukazuje na širšiu možnosť:

„Hranice poznania sú veľmi členité a niet pochýb, že nasledujúce mesiace a roky prinesú podobné úspechy v mnohých ďalších oblastiach matematiky, kde dlhodobé otvorené problémy vyrieši AI tým, že odhalí nečakané súvislosti a posunie existujúci technický aparát na jeho hranice. AI nám pomáha plnšie skúmať katedrálu matematiky, ktorú sme budovali počas stáročí; aké ďalšie nevidené zázraky čakajú v úzadí?“

Tento výsledok poskytuje sľubný príklad: AI prispieva nielen riešením, ale aj matematickým objavom, ktorého význam sa stáva jasnejším a bohatším vďaka následnému ľudskému pochopeniu.

Poučenie je väčšie než tento konkrétny výsledok. Lepšie matematické uvažovanie môže z AI urobiť silnejšieho výskumného partnera: niečo, čo dokáže udržať pohromade náročné línie myslenia, prepájať myšlienky naprieč vzdialenými oblasťami poznania, odhaľovať sľubné smery, ktoré odborníci nemuseli uprednostniť, a pomáhať výskumníkom napredovať pri problémoch, ktoré by inak boli príliš zložité alebo časovo náročné.

Tieto schopnosti sú dôležité aj mimo matematiky. Ak model dokáže udržať zložitý argument koherentný, prepájať myšlienky naprieč vzdialenými oblasťami poznania a vytvárať prácu, ktorá obstojí pri odbornom skúmaní, sú to užitočné schopnosti aj v biológii, fyzike, materiálových vedách, inžinierstve a medicíne a sú súčasťou našej dlhodobejšej cesty k viac automatizovanému výskumu: systémom, ktoré môžu vedcom a inžinierom pomôcť skúmať viac nápadov a venovať sa ťažším technickým otázkam.

AI sa čoskoro začne ujímať veľmi vážnej úlohy v tvorivých častiach výskumu a najmä v samotnom výskume AI. Hoci tento pokrok nie je nečakaný, posilňuje naliehavosť, ktorú cítime pri potrebe porozumieť tejto ďalšej fáze vývoja AI, výzvam zosúlaďovania veľmi inteligentných systémov a budúcnosti spolupráce človeka a AI.

Táto budúcnosť stále závisí od ľudského úsudku. Odbornosť sa stáva hodnotnejšou, nie menej. AI môže pomáhať hľadať, navrhovať a overovať. Ľudia vyberajú problémy, na ktorých záleží, interpretujú výsledky a rozhodujú, akým otázkam sa venovať ďalej.