Model OpenAI vyvrátil ústřední hypotézu diskrétní geometrie

Téměř 80 let matematici zkoumají zdánlivě jednoduchou otázku: když umístíte $n$ bodů do roviny, kolik dvojic bodů může být od sebe přesně ve vzdálenosti $1$?

Toto je problém jednotkových vzdáleností v rovině, který poprvé formuloval Paul Erdős v roce 1946. Je to jedna z nejznámějších otázek kombinatorické geometrie, kterou je snadné zformulovat, ale mimořádně obtížné vyřešit. Kniha Research Problems in Discrete Geometry z roku 2005 autorů Brasse, Mosera a Pacha jej označuje za „možná nejznámější (a nejsnadněji vysvětlitelný) problém v kombinatorické geometrii“. Noga Alon, přední kombinatorik působící na Princetonu, jej popisuje jako „jeden z Erdősových oblíbených problémů“. Erdős dokonce vypsal finanční odměnu za vyřešení tohoto problému.

Dnes sdílíme průlom v problému jednotkové vzdálenosti. Od Erdősovy původní práce převládalo přesvědčení, že konstrukce „čtvercové mřížky“ zobrazené níže byly v podstatě optimální pro maximalizaci počtu dvojic v jednotkové vzdálenosti. Interní model OpenAI tuto dlouholetou domněnku vyvrátil a poskytl nekonečnou rodinu příkladů, které přinášejí polynomiální zlepšení. Důkaz zkontrolovala skupina externích matematiků. Napsali také doprovodný článek, který vysvětluje argument a poskytuje další pozadí a kontext významu výsledku.

Pozoruhodné je i to, jak bylo k výsledku dospěno. Důkaz vzešel z nového univerzálního modelu s uvažováním, nikoli ze systému trénovaného speciálně pro matematiku, vybaveného strukturou pro prohledávání důkazových strategií nebo zaměřeného konkrétně na problém jednotkové vzdálenosti. V rámci širšího úsilí otestovat, zda pokročilé modely mohou přispět k hraničnímu výzkumu, jsme jej vyhodnotili na souboru Erdősových problémů. V tomto případě vytvořil důkaz řešící otevřený problém.

Tento důkaz je důležitým milníkem pro matematickou komunitu i komunitu AI. Jde o první případ, kdy byl významný otevřený problém, ústřední pro jednu podoblast matematiky, autonomně vyřešen AI. Zároveň ukazuje hloubku uvažování, kterou tyto systémy nyní podporují. Matematika poskytuje obzvlášť jasné testovací prostředí pro uvažování: problémy jsou přesné, možné důkazy lze ověřit a dlouhý argument funguje jen tehdy, když uvažování drží pohromadě od začátku do konce. Pozoruhodná je i metoda, kterou byl problém vyřešen. Důkaz přináší nečekané, sofistikované myšlenky z algebraické teorie čísel do otázky z elementární geometrie.

Držitel Fieldsovy medaile Tim Gowers v doprovodném článku označuje výsledek za „milník v AI matematice“. Podle předního teoretika čísel Arula Shankara „tento článek podle mého názoru ukazuje, že současné modely AI přesahují roli pouhých pomocníků lidských matematiků – jsou schopné přicházet s původními důmyslnými nápady a pak je dovést do úspěšného konce“.

Důkaz je k dispozici zde⁠(otevře se v novém okně). Doprovodný článek předních externích matematiků je k dispozici zde⁠(otevře se v novém okně). Zkrácenou verzi řetězce úvah modelu najdete zde⁠(otevře se v novém okně).

Nechť $u(n)$ je největší možný počet dvojic ve vzdálenosti jedné jednotky mezi $n$ body v rovině. Příklady dosahující lineárního tempa růstu lze snadno sestrojit: umístění $n$ bodů na přímku dává $n-1$ dvojic, zatímco čtvercová mřížka dává asi $2n$ dvojic. Dříve nejlepší známá konstrukce, vycházející z přepočítané čtvercové mřížky, dává ještě více výsledků: $n^{1 + C / \log \log(n)}$ pro konstantu $C$. Protože $\log \log(n)$ s $n$ směřuje k nekonečnu, dodatečný člen v exponentu směřuje k $0$, což znamená, že tyto konstrukce dosahují růstu jen nepatrně rychlejšího než lineárního. Po desetiletí se široce věřilo, že tato míra je v podstatě nejlepší možná a že žádná konstrukce nemůže čtvercovou mřížku výrazně překonat. Technicky vzato Erdős vyslovil domněnku horní meze $n^{1+o(1)}$, kde dodatečné $o(1)$ označuje člen směřující k $0$ s $n$.

Náš nový výsledek tuto domněnku vyvrací. Přesněji řečeno: pro nekonečně mnoho hodnot $n$ důkaz konstruuje konfigurace $n$ bodů s alespoň $n^{1+\delta}$ dvojicemi v jednotkové vzdálenosti pro nějaký pevný exponent $\delta > 0$. (Původní důkaz AI neudává explicitní $\delta$, ale připravované zpřesnění od profesora matematiky na Princetonu Willa Sawina ukázalo, že lze vzít $\delta=0.014$.)

Historie problému pomáhá pochopit, proč je výsledek překvapivý. Nejlepší známá dolní mez zůstávala v podstatě nezměněna od Erdősovy původní konstrukce z roku 1946. Nejlepší horní mez, $O(n^{4/3})$, pochází z práce Spencera, Szemerédiho a Trottera z roku 1984. A navzdory pozdějším zpřesněním a související strukturální práci Székelyho, Katze a Siliera, Pacha, Raze a Solymosiho i dalších zůstala horní mez v podstatě nezměněna. Jako důkaz ve prospěch domněnky studovali Matoušek a Alon–Bucić–Sauermann problém s neeukleidovskými vzdálenostmi v rovině a dokázali, že „většina“ těchto neeukleidovských vzdáleností v jistém smyslu hypotézu splňuje.

Překvapivě klíčové složky konstrukce pocházejí ze zcela jiné části matematiky známé jako algebraická teorie čísel, která studuje koncepty jako rozklad na činitele v rozšířeních celých čísel známých jako algebraická číselná tělesa.

Na vysoké úrovni důkaz začíná známou geometrickou myšlenkou a posouvá ji nečekaným směrem.

Erdősovu původní dolní mez lze chápat pomocí Gaussových celých čísel: čísel tvaru $a+bi$, kde $a$ a $b$ jsou celá čísla a $i$ je druhá odmocnina z $-1$. Gaussova celá čísla rozšiřují běžná celá čísla a stejně jako ona mají vlastnosti, jako je jednoznačný rozklad na prvočinitele. Taková rozšíření běžných celých nebo racionálních čísel jsou známá jako algebraická číselná tělesa. Nový argument nahrazuje Gaussova celá čísla složitějšími zobecněními z algebraické teorie čísel s bohatšími symetriemi, které mohou vytvářet mnohem více rozdílů jednotkových délek.

Přesný argument používá nástroje jako nekonečné věže třídních těles a teorii Goloda–Šafareviče, aby ukázal, že číselná tělesa potřebná pro argument skutečně existují. Tyto myšlenky byly algebraickým teoretikům čísel dobře známé, ale bylo velkým překvapením, že mají důsledky pro geometrické otázky v eukleidovské rovině.

Tento výsledek představuje důležitý okamžik ve vzájemném působení AI a matematiky: systém AI autonomně vyřešil dlouhodobě otevřený problém v centru aktivního oboru. Zároveň nabízí raný pohled na nový druh spolupráce mezi AI a lidskými matematiky. V tomto případě doprovodná práce externích matematiků vykresluje podstatně bohatší obraz než samotné původní řešení.

Jak píše Thomas Bloom v doprovodné poznámce:

„Když posuzuji důležitost a vliv důkazu vytvořeného AI, kladu si otázku: naučilo nás to o problému něco nového? Rozumíme teď diskrétní geometrii lépe? Myslím, že odpověď je umírněné ano: ukazuje to, že konstrukce z teorie čísel mohou k těmto typům otázek říci mnohem více, než jsme předpokládali; navíc že potřebná teorie čísel může být velmi hluboká. Není pochyb, že se v příštích měsících mnoho algebraických teoretiků čísel podrobně podívá na další otevřené problémy diskrétní geometrie.“

Nečekané propojení mezi algebraickou teorií čísel a diskrétní geometrií, které řešení odhalilo, je součástí toho, co činí výsledek pozoruhodným. Nejde jen o vyřešení konkrétní hypotézy, ale možná i o most, který matematikům umožní začít zkoumat další související problémy.

Bloom také poukazuje na širší možnost:

„Hranice poznání jsou velmi členité a není pochyb, že v příštích měsících a letech uvidíme podobné úspěchy v mnoha dalších oblastech matematiky, kde budou dlouhodobě otevřené problémy vyřešeny díky tomu, že AI odhalí nečekané souvislosti a posune existující technický aparát na jeho hranice. AI nám pomáhá plněji prozkoumávat katedrálu matematiky, kterou jsme vybudovali během staletí; jaké další dosud netušené zázraky čekají na své odhalení?“

Tento výsledek poskytuje slibný příklad: AI přispívá nejen řešením, ale i matematickým objevem, jehož význam se stává jasnějším a bohatším díky následnému lidskému porozumění.

Můžeme si z toho odnést víc než jen tento konkrétní výsledek. Lepší matematické uvažování může z AI udělat silnějšího partnera pro výzkum: partnera, který dokáže udržet pohromadě obtížné směry myšlení, propojovat nápady napříč vzdálenými oblastmi poznání, odhalovat slibné směry, jejichž význam si odborníci neuvědomovali, a pomáhat výzkumníkům dosáhnout pokroku na problémech, které by jinak byly příliš složité nebo časově náročné.

Tyto schopnosti jsou důležité i mimo matematiku. Pokud model dokáže udržet soudržnost složitého argumentu, propojovat myšlenky napříč vzdálenými oblastmi poznání a produkovat práci, která obstojí při prověřování odborníky, pak jsou tyto schopnosti užitečné i v biologii, fyzice, materiálových vědách, inženýrství a medicíně a jsou součástí naší dlouhodobější cesty k více automatizovanému výzkumu: k systémům, které mohou vědcům a inženýrům pomoci probádat více myšlenek a věnovat se obtížnějším technickým otázkám.

AI se brzy začne ujímat velmi vážné role v kreativních částech výzkumu, a především ve výzkumu samotné AI. I když tento pokrok není nečekaný, podtrhuje, jak naléhavé je, abychom porozuměli této další fázi vývoje AI – výzvám spojeným se slaďováním velmi inteligentních systémů a budoucnosti spolupráce člověka a AI.

Tato budoucnost stále závisí na lidském úsudku. Odbornost nedevalvuje, stává se hodnotnější. AI může pomáhat hledat, navrhovat a ověřovat. Lidé vybírají problémy, na kterých záleží, interpretují výsledky a rozhodují, jakým otázkám se věnovat dál.