Model OpenAI obalił kluczową hipotezę geometrii dyskretnej

Przez niemal 80 lat matematycy badali zwodniczo proste pytanie: jeśli umieścimy $n$ punktów na płaszczyźnie, ile par punktów może być oddalonych dokładnie o $1$?

Jest to problem odległości jednostkowych na płaszczyźnie, sformułowany po raz pierwszy przez Paula Erdősa w 1946 roku. To jeden z najbardziej znanych problemów geometrii kombinatorycznej – łatwy do sformułowania i wyjątkowo trudny do rozstrzygnięcia. Książka z 2005 roku Research Problems in Discrete Geometry autorstwa Brassa, Mosera i Pacha nazywa go „być może najbardziej znanym (i najprostszym do opisania) problemem geometrii kombinatorycznej”. Noga Alon, czołowy kombinatoryk z Uniwersytetu Princeton, opisuje go jako „jeden z ulubionych problemów Erdősa”. Erdős zaoferował nawet nagrodę pieniężną za rozwiązanie tego problemu.

Dziś dzielimy się przełomem w problemie odległości jednostkowych. Od czasu oryginalnej pracy Erdősa dominowało przekonanie, że przedstawione niżej konstrukcje „siatki kwadratowej” były zasadniczo optymalne pod względem maksymalizacji liczby par w odległości jednostkowej. Wewnętrzny model OpenAI obalił tę wieloletnią hipotezę, dostarczając nieskończoną rodzinę przykładów dających wielomianową poprawę. Dowód został sprawdzony przez grupę zewnętrznych matematyków. Napisali oni także towarzyszący artykuł wyjaśniający argument oraz przedstawiający dalsze tło i kontekst znaczenia tego wyniku.

Sam sposób znalezienia tego wyniku również jest godny uwagi. Dowód pochodzi z nowego modelu rozumującego ogólnego przeznaczenia, a nie z systemu trenowanego specjalnie do matematyki, wyposażonego w rusztowanie do przeszukiwania strategii dowodowych ani ukierunkowanego konkretnie na problem odległości jednostkowych. W ramach szerszego wysiłku, by sprawdzić, czy zaawansowane modele mogą wnosić wkład do badań na granicy wiedzy, oceniliśmy go na zbiorze problemów Erdősa. W tym przypadku stworzył dowód rozwiązujący otwarty problem.

Ten dowód jest ważnym kamieniem milowym dla społeczności matematycznej i AI. To pierwszy raz, gdy ważny otwarty problem, centralny dla pewnej poddziedziny matematyki, został rozwiązany autonomicznie przez AI. Pokazuje to również głębię rozumowania, jaką te systemy obecnie wspierają. Matematyka stanowi szczególnie przejrzyste środowisko testowe dla rozumowania: problemy są precyzyjne, potencjalne dowody można sprawdzić, a długi argument działa tylko wtedy, gdy rozumowanie pozostaje spójne od początku do końca. Na uwagę zasługuje także metoda, dzięki której rozwiązano problem. Dowód wykorzystuje nieoczekiwane, wyrafinowane idee z algebraicznej teorii liczb do rozwiązania elementarnego pytania geometrycznego.

Laureat Medalu Fieldsa Tim Gowers w artykule towarzyszącym nazywa ten wynik „kamieniem milowym matematyki AI”. Według czołowego teoretyka liczb Arula Shankara „Moim zdaniem ten artykuł pokazuje, że obecne modele AI wykraczają poza rolę zwykłych pomocników ludzkich matematyków – są zdolne do oryginalnych, pomysłowych idei, a następnie do doprowadzenia ich do pełnej realizacji”.

Dowód jest dostępny tutaj⁠(otwiera nowe okno). Artykuł towarzyszący autorstwa czołowych zewnętrznych matematyków jest dostępny tutaj⁠(otwiera nowe okno). Skróconą wersję łańcucha rozumowania modelu można znaleźć tutaj⁠(otwiera nowe okno).

Niech $u(n)$ oznacza największą możliwą liczbę par w odległości jednostkowej wśród $n$ punktów na płaszczyźnie. Przykłady osiągające liniowe tempo wzrostu łatwo skonstruować: umieszczenie $n$ punktów na prostej daje $n-1$ par, podczas gdy siatka kwadratowa daje około $2n$ par. Okazuje się, że wcześniej najlepiej znana konstrukcja, pochodząca z przeskalowanej siatki kwadratowej, daje jeszcze więcej: $n^{1 + C / \log \log(n)}$ dla pewnej stałej $C$. Ponieważ $\log \log(n)$ dąży do nieskończoności wraz z $n$, dodatkowy składnik w wykładniku dąży do $0$, co oznacza, że te konstrukcje osiągają wzrost tylko nieznacznie szybszy niż liniowy. Przez dekady powszechnie wierzono, że tempo to jest zasadniczo najlepsze z możliwych i że żadna konstrukcja nie może znacząco poprawić wyniku siatki kwadratowej. Technicznie mówiąc, Erdős postawił hipotezę górnego ograniczenia $n^{1+o(1)}$, w którym dodatkowe $o(1)$ oznacza składnik dążący do $0$ wraz z $n$.

Nasz nowy wynik obala tę hipotezę. A dokładniej: dla nieskończenie wielu wartości $n$ dowód konstruuje konfiguracje $n$ punktów z co najmniej $n^{1+\delta}$ parami w odległości jednostkowej, dla pewnego ustalonego wykładnika $\delta > 0$. (Oryginalny dowód AI nie podaje jawnej wartości $\delta$, ale nadchodzące dopracowanie autorstwa profesora matematyki z Princeton, Willa Sawina, pokazało, że można przyjąć $\delta=0.014$.)

Historia problemu pomaga zrozumieć, dlaczego wynik jest zaskakujący. Najlepsze znane dolne ograniczenie pozostawało zasadniczo niezmienione od czasu oryginalnej konstrukcji Erdősa z 1946 roku. Najlepsze górne ograniczenie, $O(n^{4/3})$, pochodzi z pracy Spencera, Szemerédiego i Trottera z 1984 roku i mimo późniejszych udoskonaleń oraz powiązanych prac strukturalnych Székely’ego, Katza i Siliera, Pacha, Raza i Solymosiego oraz innych, górne ograniczenie pozostało zasadniczo niezmienione. Jako argument przemawiający za hipotezą podaje się fakt, iż Matoušek oraz Alon-Bucić-Sauermann badali ten problem dla nieeuklidesowych odległości na płaszczyźnie i dowiedli, że „większość” tych nieeuklidesowych odległości w pewnym sensie spełnia tę hipotezę.

Co zaskakujące, kluczowe składniki konstrukcji pochodzą z zupełnie innego obszaru matematyki, zwanego algebraiczną teorią liczb, który bada pojęcia takie jak rozkład na czynniki w rozszerzeniach liczb całkowitych zwanych algebraicznymi ciałami liczbowymi.

Na wysokim poziomie dowód zaczyna się od znanej idei geometrycznej i rozwija ją w nieoczekiwanym kierunku.

Oryginalne dolne ograniczenie Erdősa można zrozumieć poprzez liczby Gaussa: liczby postaci $a+bi$, gdzie $a$ i $b$ są liczbami całkowitymi, a $i$ jest pierwiastkiem kwadratowym z $-1$. Liczby Gaussa rozszerzają zwykłe liczby całkowite i, podobnie jak one, mają własności takie jak jednoznaczny rozkład na liczby pierwsze. Takie rozszerzenia zwykłych liczb całkowitych lub wymiernych są znane jako algebraiczne ciała liczbowe. Nowy argument zastępuje liczby Gaussa bardziej złożonymi uogólnieniami z algebraicznej teorii liczb o bogatszych symetriach, które mogą tworzyć znacznie więcej różnic długości jednostkowej.

Dokładny argument wykorzystuje narzędzia takie jak nieskończone wieże ciał klasowych i teorię Goloda–Szafarewicza, aby wykazać, że ciała liczbowe potrzebne do argumentu rzeczywiście istnieją. Idee te były dobrze znane algebraicznym teoretykom liczb, ale wielkim zaskoczeniem okazało się to, że pojęcia te mają konsekwencje dla pytań geometrycznych na płaszczyźnie euklidesowej.

Ten wynik wyznacza ważny moment w relacji między AI a matematyką: system AI autonomicznie rozwiązał wieloletni otwarty problem znajdujący się w centrum aktywnej dziedziny. Daje też wczesny wgląd w nowy rodzaj współpracy między AI a ludzkimi matematykami. W tym przypadku praca towarzysząca zewnętrznych matematyków daje znacznie bogatszy obraz niż samo oryginalne rozwiązanie.

Jak pisze Thomas Bloom w nocie towarzyszącej:

„Oceniając wagę i wpływ dowodu wygenerowanego przez AI, zadaję sobie pytanie: czy to nauczyło nas czegoś nowego o problemie? Czy teraz lepiej rozumiemy geometrię dyskretną? Myślę, że odpowiedź brzmi: umiarkowanie tak; pokazuje to, że konstrukcje teorioliczbowe mają do powiedzenia o tego rodzaju pytaniach znacznie więcej, niż przypuszczaliśmy; co więcej, wymagana teoria liczb może być bardzo głęboka. Bez wątpienia wielu algebraicznych teoretyków liczb będzie w nadchodzących miesiącach uważnie przyglądać się innym otwartym problemom geometrii dyskretnej.”

Nieoczekiwany związek między algebraiczną teorią liczb a geometrią dyskretną ujawniony przez to rozwiązanie jest częścią tego, co czyni ten wynik godnym uwagi. Nie tylko rozstrzyga on konkretną hipotezę, ale może także dać matematykom pomost do rozpoczęcia badania dalszych powiązanych problemów.

Bloom wskazuje też na szerszą możliwość:

„Granice wiedzy są bardzo poszarpane i bez wątpienia nadchodzące miesiące i lata przyniosą podobne sukcesy w wielu innych obszarach matematyki, gdzie wieloletnie otwarte problemy będą rozwiązywane przez AI ujawniającą nieoczekiwane powiązania i doprowadzającą istniejący aparat techniczny do granic możliwości. AI pomaga nam pełniej eksplorować katedrę matematyki, którą budowaliśmy przez stulecia; jakie inne niewidziane cuda czekają za kulisami?”

Ten wynik stanowi obiecujący przykład: AI wnosi nie tylko rozwiązanie, lecz także odkrycie matematyczne, którego znaczenie staje się jaśniejsze i bogatsze dzięki późniejszemu ludzkiemu zrozumieniu.

Wniosek jest szerszy niż ten konkretny wynik. Lepsze rozumowanie matematyczne może uczynić AI silniejszym partnerem badawczym: czymś, co potrafi utrzymać spójność trudnych linii myślenia, łączyć idee z odległych obszarów wiedzy, wskazywać obiecujące ścieżki, których eksperci mogli nie uznać za priorytetowe, i pomagać badaczom robić postępy w problemach, które w innym razie byłyby zbyt złożone lub czasochłonne.

Te zdolności mają znaczenie także poza matematyką. Jeśli model potrafi zachować spójność złożonego wywodu, łączyć idee z odległych obszarów wiedzy i tworzyć pracę, która wytrzymuje ekspercką ocenę, to są to użyteczne zdolności także w biologii, fizyce, nauce o materiałach, inżynierii i medycynie, a także część naszej długoterminowej drogi ku bardziej zautomatyzowanym badaniom: systemom, które mogą pomagać naukowcom i inżynierom badać więcej pomysłów i podejmować trudniejsze pytania techniczne.

AI wkrótce zacznie odgrywać bardzo poważną rolę w twórczych częściach badań, a przede wszystkim w samych badaniach nad AI. Choć ten postęp nie jest nieoczekiwany, wzmacnia on pilność, jaką odczuwamy wobec zrozumienia tej kolejnej fazy rozwoju AI, wyzwań związanych z dostrajaniem bardzo inteligentnych systemów oraz przyszłości współpracy człowieka z AI.

Ta przyszłość nadal zależy od ludzkiego osądu. Ekspertyza staje się bardziej wartościowa, a nie mniej. AI może pomagać szukać, sugerować i weryfikować. To ludzie wybierają problemy, które mają znaczenie, interpretują wyniki i decydują, jakimi pytaniami zająć się dalej.