Kolejny model OpenAI, Astra, właśnie rozwiązał dziesięć wieloletnich otwartych problemów matematycznych

1 sierpnia OpenAI opublikowało raport, w którym twierdzi, że jego kolejny model, wewnętrznie nazywany Astra (jeszcze niedostępny), uzyskał nowe wyniki dla dziesięciu różnych otwartych problemów z matematyki. (Nie, to nie są problemy Milenijne, ale mimo to mają duże znaczenie.)

Co istotne: te rozwiązania nie są stopniowym postępem w tych problemach — to rzeczywiste rozstrzygnięcia, zweryfikowane w Lean. (Lean to język programowania i asystent dowodzenia, który wymusza zapisanie każdego kroku rozumowania matematycznego w szczegółach zrozumiałych dla maszyny.) 

To dużo naraz. W tym artykule uporządkowałem problemy według dziedziny i opisuję na wysokim poziomie, co się wydarzyło, co to może oznaczać dla matematyki jako dziedziny i czego jeszcze możemy się dowiedzieć o Astrze.

Jakie to są te dziesięć problemów?

Oto każdy wynik w prostych słowach, wraz z dziedziną matematyki lub informatyki teoretycznej, do której należy.

Grupy niesoficzne

Dziedzina: teoria grup

Astra skonstruowała wprost grupę, której nie da się przybliżyć, niezależnie od dokładności, przez duże struktury skończone — zamykając pytanie otwarte od 1999 roku, gdy wprowadzono pojęcie grupy „soficznej”. Konstrukcji towarzyszy dowód, że żaden ciąg skończonych przybliżeń nigdy nie zadziała, sformalizowany w Lean, aby logikę można było mechanicznie sprawdzić.

Wikipedia została już zaktualizowana:

Upakowanie sfer

Dziedzina: geometria wysokowymiarowa

Pytanie brzmi, jak gęsto można upakować identyczne, nieprzenikające się sfery, gdy liczba wymiarów rośnie. Astra udowodniła ciaśniejszy sufit tej gęstości w wysokich wymiarach — pierwszą poprawę tego konkretnego ograniczenia od 1978 roku. Nie podaje lepszej metody upakowania — zawęża, jak dobre może być jakiekolwiek przyszłe upakowanie.

Kody binarne i sferyczne

Dziedzina: teoria kodowania

Kody korekcyjne działają, utrzymując poprawne komunikaty na tyle daleko od siebie, by drobne błędy nie mogły jednego przekształcić w drugi. Astra udowodniła znacznie ciaśniejsze (ekspotencjalnie ulepszone) ograniczenia na liczbę takich komunikatów dla danej minimalnej odległości, z odpowiadającym wynikiem dla punktów rozmieszczonych na wysokowymiarowej sferze.

Hipoteza sztywności Connesa

Dziedzina: algebry operatorowe

Alain Connes przypuszczał, że pewne grupy można zawsze jednoznacznie odtworzyć ze zbudowanej z nich struktury algebraicznej zwanej algebrą von Neumanna. Astra to obaliła, konstruując dwie rzeczywiście różne grupy, które dają tę samą algebrę, pokazując, że odtwarzanie nie zawsze jest jednoznaczne.

Złożoność obwodów arytmetycznych

Dziedzina: teoria złożoności obliczeniowej

„Permanent”, pojedyncza liczba wyliczana z siatki liczb, jest kosztowny w obliczeniach i teoretycy złożoności chcą znać minimalną liczbę kroków arytmetycznych, jakiej może wymagać dowolna metoda. Astra udowodniła nową, silniejszą dolną granicę tego minimum — to rodzaj wyniku, który słynie z tego, że bardzo trudno go w ogóle poprawić.

Kwantowa powtórna równoległość

Dziedzina: teoria złożoności kwantowej

Klasyczna teoria mówi, że zmuszenie dwóch niekomunikujących się graczy do wielokrotnego, równoległego powtarzania trudnej gry sprawia, że oszustwo ma wykładniczo mniejsze szanse powodzenia. Astra udowodniła, że ta sama gwarancja obowiązuje nawet wtedy, gdy gracze dzielą splątanie kwantowe, rozszerzając fundamentalną klasyczną zasadę na ustawienie kwantowe.

Problem najbliższego wektora

Dziedzina: kryptografia kratowa

Mając powtarzalną siatkę punktów (kratę) i punkt docelowy, problem pyta o najbliższy punkt kraty — problem uważany za bardzo trudny w wysokich wymiarach, dlatego stanowi podstawę niektórych szyfrów odpornych na komputery kwantowe. Astra udowodniła, że nawet przybliżenie odpowiedzi w określonym wielomianowym czynniku pozostaje dowodnie trudne, wzmacniając kryptografię na tym opartą.

Hipoteza objętości Ehrharta

Dziedzina: geometria dyskretna i wypukła

Dla wypukłego kształtu, którego jedyny wewnętrzny punkt kratowy leży dokładnie w jego środku masy, matematycy chcieli znać największą możliwą objętość takiego kształtu w danym wymiarze. Astra wyznaczyła tę maksymalną objętość dla każdego wymiaru, ostatecznie rozstrzygając hipotezę w pełnej ogólności.

Wielobarwne liczby Ramseya

Dziedzina: teoria Ramseya / kombinatoryka

Przy wystarczającej liczbie osób i kategoriach relacji między nimi ostatecznie gwarantowanie znajdziesz trzy osoby połączone tą samą kategorią. Astra udowodniła, że minimalna liczebność grupy potrzebna do tego rośnie szybciej niż jakiekolwiek stałe tempo wykładnicze, gdy liczba kategorii rośnie, rozwiązując problem Erdősa nr 183.

Hipotezy liczb ekstremalnych

Dziedzina: ekstremalna teoria grafów

Ta gałąź matematyki pyta, ile połączeń może mieć sieć, unikając jednocześnie pewnych małych, zakazanych wzorców. Astra rozstrzygnęła dwie pokrewne hipotezy — odpowiadające problemom Erdősa nr 146 i 180 — precyzując, jak gęste mogą być takie sieci, zanim te wzorce staną się nieuniknione.

Każdy z tych problemów był otwarty co najmniej dekadę; kilka przetrwało trzydzieści lat lub dłużej, w tym problemy, nad którymi pracowali laureaci Nagrody Turinga po stronie informatyki teoretycznej.

Chwila, czy kontrprzykład to „łatwy” rodzaj dowodu?

Kim jestem, by tu wybrzydzać, ale wiem, że to częste pytanie lub reakcja, zwłaszcza u osób, które coś o matematyce wiedzą.

Najczęstsza uwaga krytyczna: kilka z tych wyników to kontrprzykłady, a nie nowa teoria ogólna. To istotne, bo kontrprzykład odpowiada na pytanie tak/nie, ale sam w sobie nie mówi, dlaczego wzorzec się łamie ani nie daje do ręki rodziny podobnych obiektów do dalszych badań, podczas gdy coś innego, jak twierdzenie klasyfikacyjne czy nowa technika, otwiera więcej drzwi.

Powiedziałbym, że ta krytyka ogólnie się broni, ale nie działa jako blankietowe odrzucenie całej tej partii problemów. Po pierwsze, wynik o grupach niesoficznych nie jest drobną poprawką do istniejącego „prawie” — to pierwsza taka konstrukcja po 27 latach, gdy nikt jej nie miał, a technika za nią stojąca ma się uogólniać na znajdowanie kolejnych.

Po drugie, kilka z pozostałych dziewięciu wyników, w tym ograniczenie upakowania sfer i trudność CVP, w ogóle nie są kontrprzykładami; to bezpośrednie poprawy istniejących ograniczeń. 

Co wciąż pozostaje nierozstrzygnięte

Warto śledzić kilka kwestii, gdy środowisko będzie to rozkładać na czynniki pierwsze w najbliższych dniach, tygodniach i miesiącach:

• Brak recenzji naukowej. Dowody są zweryfikowane w Lean i nieformalnie przejrzane przez matematyków, którzy widzieli preprinty, ale żaden nie przeszedł jeszcze przez proces recenzji w czasopiśmie. 
• Autorstwo jest w trakcie ustalania. OpenAI mówi, że bierze odpowiedzialność za manuskrypty i formalizacje w Lean, przypisując same argumenty matematyczne modelowi. Niezależna replikacja procesu (w odróżnieniu od weryfikacji dowodów) jest teraz trudna do przeprowadzenia.

Co to oznacza dla matematyki

Najbardziej bezpośrednia zmiana dotyczy tego, na co matematycy mogą faktycznie poświęcać czas. Jeśli dobrze postawiony otwarty problem można przekazać modelowi i sprawdzić w Lean, wąskie gardło przesuwa się z „czy ktokolwiek to rozwiąże” na „czy zadaliśmy właściwe pytanie i poprawnie je sformalizowaliśmy”. Umiejętność stawiania dobrych problemów i wiedza, który warto zaatakować, to realna kompetencja, którą matematycy rozwijają z doświadczeniem. 

Pojawia się też pytanie o finansowanie i wiarygodność. Granty, awanse i nagrody historycznie opierały się na niedoborze: te problemy były na tyle trudne, że ich rozwiązanie mówiło coś o rozwiązującym. Jeśli wyniki wspomagane przez AI staną się rutyną, środowisko będzie potrzebowało nowych sposobów sygnalizowania, co jest naprawdę trudne, a co jest w zasięgu kilku tysięcy dolarów kosztu inferencji. Oczywiście przeciętny odbiorca nie rozumie tych problemów w pełni. Rozumieją je osoby z rzeczywistym przygotowaniem — i to się nie zmienia. Więc wiedza matematyczna jest cenniejsza niż kiedykolwiek. 

Jak ludzie reagują

Reakcje w mediach społecznościowych mniej dzielą się co do tego, czy dowody się zgadzają, a bardziej co do tego, czego są dowodem.

Niektórzy widzą w samym tempie główną historię: dziesięć wieloletnich problemów spada naraz, w niepowiązanych dziedzinach, szybciej, niż eksperci są w stanie je zrecenzować. Pytanie na przyszłość: „Czy nadążymy z weryfikacją tego wszystkiego?”

Inni odpowiadają, że to mówi mniej o AI ogólnie, niż się wydaje. Matematyka to rzadkie pole, gdzie prace modelu można sprawdzić automatycznie i kompletnie. Większość realnych problemów nie daje takiej wbudowanej, automatycznej kart odpowiedzi. W tym ujęciu osiągnięcie jest realne, ale może bardziej mówić o tym, że matematyka jest wyjątkowo dobrze dopasowana do AI.

Trzeci wątek komentarzy: poprawny dowód, którego nikt jeszcze w pełni nie zAuditował ani nie przyswoił, nie został tak naprawdę zrozumiany — tylko zweryfikowany. Odkrycie twierdzenia i zrozumienie, co ono znaczy, to w tym ujęciu dwa różne zadania.

Na koniec

Matematycy mówią, że wynik o grupach niesoficznych wygląda na prawdziwą rzecz: autentyczny, wieloletni otwarty problem w teorii grup, zamknięty przez jawną konstrukcję, którą matematycy z tej dziedziny traktują poważnie. Pozostałe dziewięć wyników razem reprezentuje szeroki i technicznie znaczący pakiet postępu w matematyce czystej.

To, czego jeszcze nie było, to wolniejsza część: recenzja naukowa, replikacja procesu wyszukiwania oraz faktyczne budowanie na tych wynikach przez środowisko. To trwa dłużej niż wpis na blogu — i to właśnie pokaże, jak duże to było. Będziemy cię informować.