Model OpenAI wyznacza dokładne tempo zaniku programu Cohna-Elkiesa

TL;DR. Wewnętrzny model OpenAI wyznacza dokładne tempo zaniku programu liniowego Cohna-Elkiesa i daje pierwszą od 1978 roku poprawę wykładnika upakowania kul.

Kluczowe wnioski

Czym jest ten zbiór i dlaczego jeden wynik się wyróżnia. Dokument zaczyna się skromnie.
Program Cohna-Elkiesa i to, co ogranicza. Problem upakowania kul pyta, jak gęsto nienakładające się kule mogą wypełnić przestrzeń.
Co metoda osiągnęła już wcześniej. Zanim przejdziemy do nowego twierdzenia, warto konkretnie powiedzieć, co metoda programowania liniowego oparta na analizie Fouriera już dała, bo nowy wynik jest częściowo stwierdzeniem o tym, jak daleko można nią…
Twierdzenie główne. Twierdzenie główne dokumentu dowodzi wykładniczego tempa, o którym mówiły hipotezy 3.1 i 3.2 z tamtej pracy z 2020 roku.

Zbiór wyników matematycznych wewnętrznego modelu OpenAI rozstrzyga asymptotyczną siłę programu liniowego Cohna-Elkiesa dla upakowania kul. Daje pierwszą od 1978 roku poprawę ogólnego wykładnika upakowania kul, a wraz z nią dokładnie dopasowane ograniczenie dolne.

Czym jest ten zbiór i dlaczego jeden wynik się wyróżnia #

Dokument zaczyna się skromnie. Przedstawia zbiór wyników uzyskanych przez wewnętrzny model OpenAI i stwierdza, że obejmują one matematykę i informatykę teoretyczną. To opis pochodzenia i zakresu, który nie mówi, jak model był używany ani jak sprawdzano jego wyniki. Te pytania mają znaczenie, a źródło w podsumowanej tu postaci pozostawia je bez odpowiedzi, więc ten artykuł nie będzie udawał, że jest inaczej. Twierdzenia źródła uzasadniają natomiast listę podanych wyników, a lista jest na tyle długa, że ciekawe pytanie nie brzmi, czy którakolwiek pozycja robi wrażenie. Brzmi ono: dlaczego jedna z nich zasługuje na większość uwagi.

Powodem jest to, że wynik o upakowaniu kul jako jedyny w zbiorze zamyka ilościową lukę w programie badawczym o długiej i dobrze udokumentowanej historii. Pozostałe są uderzające same w sobie. Jawna grupa niesoficzna odpowiada na dawne pytanie. Obalenie hipotezy Connesa rozstrzyga coś, co zaproponował znany matematyk. Wynik o upakowaniu kul stoi jednak na końcu łańcucha, który biegnie od metody opartej na analizie Fouriera, przez dwa słynne dokładne rozwiązania w pojedynczych wymiarach, aż do pytania o wysokie wymiary, które przez lata pozostawało otwarte. Zrozumienie tego wyniku wymaga zrozumienia tego łańcucha.

Dlatego większość dalszej części dotyczy programu liniowego Cohna-Elkiesa: czym jest, co o nim wiedziano, co mówi nowe twierdzenie i jak zbudowana jest ta strona argumentu, która dotyczy niepewności znaku. Krótsza część omawia potem pozostałe wyniki zbioru, każdy dokładnie tak, jak go podano, i nic ponadto.

Program Cohna-Elkiesa i to, co ogranicza #

Problem upakowania kul pyta, jak gęsto nienakładające się kule mogą wypełnić przestrzeń. Dokument ustala tu oznaczenia. Dla środków oddalonych od siebie co najmniej o 1, ∆d jest supremum górnych gęstości kul o promieniu 1/2 w Rd. Innymi słowy ∆d oznacza maksymalną gęstość upakowania kul w Rd. Wszystko w pierwszym rozdziale zbioru jest mierzone względem tej wielkości.

Program Cohna-Elkiesa daje ograniczenie górne na ∆d. Jego optymalny wynik zapisuje się jako LPd i definiuje jako optymalne ograniczenie gęstości, jakie dostarcza program. Mechanizmem jest ograniczenie Gorbaczowa–Cohna-Elkiesa, które każdej funkcji f z klasy oznaczanej Ad przypisuje górne ograniczenie gęstości vd f(0)/(2d f̂(0)). Słowami: wybiera się funkcję pomocniczą f z klasy dopuszczalnej, oblicza jej wartość w początku układu oraz wartość jej transformaty Fouriera w początku układu, tworzy iloraz z czynnikami objętości i skali, a wynik ogranicza gęstość upakowania od góry. Program liniowy szuka takiej funkcji f, dla której to ograniczenie jest jak najmniejsze.

To metoda, w której cała trudność polega na dobrym wyborze f. Zręcznie dobrana funkcja daje ciasne ograniczenie, a źle dobrana daje słabe ograniczenie, które nadal jest poprawne. Właśnie dlatego dopasowane ograniczenie dolne w nowym wyniku ma tak duże znaczenie. Mówi ono o wszystkich funkcjach dopuszczalnych naraz i zamienia poszukiwanie lepszych funkcji w pytanie zamknięte.

Co metoda osiągnęła już wcześniej #

Zanim przejdziemy do nowego twierdzenia, warto konkretnie powiedzieć, co metoda programowania liniowego oparta na analizie Fouriera już dała, bo nowy wynik jest częściowo stwierdzeniem o tym, jak daleko można nią jeszcze zajść.

Viazovska użyła tej metody, by dowieść, że krata E8 daje optymalne upakowanie w wymiarze osiem. Cohn, Kumar, Miller, Radchenko i Viazovska wykazali następnie optymalność kraty Leecha w wymiarze dwadzieścia cztery. To dokładne wyniki w pojedynczych wymiarach i to dzięki nim metoda cieszy się reputacją wykraczającą poza rolę narzędzia do szacowania. W dwóch konkretnych wymiarach trafia w prawdziwą odpowiedź.

Obraz w wysokich wymiarach był mniej wyraźny. Cohn i Zhao udowodnili, że program liniowy jest zawsze co najmniej tak silny jak ograniczenie Kabatianskiego–Levenshteina dla kodów sferycznych. To użyteczna gwarancja, bo ograniczenie Kabatianskiego–Levenshteina było najlepszym znanym ogólnym wykładnikiem. Jednak „co najmniej tak silny” pozostawia dwie możliwości: program może dokładnie dorównywać temu wykładnikowi albo go pobić. Dokument podaje konsekwencję wprost. To, czy program liniowy poprawia klasyczny wykładnik upakowania kul w wysokich wymiarach, pozostawało pytaniem otwartym.

Afkhami-Jeddi, Cohn, Hartman, de Laat i Tajdini postawili hipotezę o tempie programu liniowego w wysokich wymiarach. Ta hipoteza to obiekt obwarowany zastrzeżeniami i źródło tak ją traktuje. Była hipotezą, wspartą dowodami, którymi dysponowali autorzy, i nikt jej nie udowodnił. Nowy wynik zmienia jej status.

Twierdzenie główne #

Twierdzenie główne dokumentu dowodzi wykładniczego tempa, o którym mówiły hipotezy 3.1 i 3.2 z tamtej pracy z 2020 roku. Na poziomie, który uzasadniają twierdzenia źródła: autorzy wyznaczają dokładne wykładnicze tempo zaniku programu liniowego Cohna-Elkiesa dla upakowania kul. Asymptotyczna siła programu jest, słowami źródła, wyznaczona dokładnie.

Ze źródła wynikają bezpośrednio dwie konsekwencje. Pierwszą jest poprawione ogólne ograniczenie upakowania w wysokich wymiarach. Drugą jest to, że odpowiadający mu problem niepewności znaku w analizie Fouriera zostaje rozstrzygnięty asymptotycznie. To konsekwencje różnego rodzaju. Jedna dotyczy geometrii, druga analizy, a to, że jedno twierdzenie daje obie, jest pierwszą wskazówką, że problem upakowania kul i problem niepewności to dwie strony tej samej struktury.

Źródło osadza też to osiągnięcie w historii. Opisuje wynik jako pierwszą od 1978 roku poprawę ogólnego wykładnika upakowania kul. Klasyczny wykładnik Kabatianskiego–Levenshteina wynosił 0,59905576... i ta liczba była punktem odniesienia. Dokument odnotowuje, że późniejsze udoskonalenia kodów sferycznych poprawiały jedynie czynniki niższego rzędu. Innymi słowy, dla samego wykładnika, czyli wielkości wiodącego rzędu, nic się nie zmieniło.

Uważam, że to właściwe ujęcie przy ocenie tego wyniku. Poprawa niższego rzędu koryguje stałe i czynniki wielomianowe, ale zostawia wykładnicze tempo tam, gdzie było. Poprawa wykładnika zmienia tempo. Twierdzenia źródła uzasadniają dokładnie to rozróżnienie i uzasadniają stwierdzenie, że wcześniejsze udoskonalenia wypadały po stronie niższego rzędu.

Wymiar / metoda	Klasyczny punkt wyjścia (1978)	Program liniowy Cohna-Elkiesa	Nowy dowód modelu
Wykładnik upakowania kul	Ograniczenie Kabatianskiego–Levenshteina: 0,59905576...	Co najmniej tak silny jak ograniczenia dla kodów sferycznych (Cohn–Zhao)	Udowodnione dokładne tempo asymptotyczne z hipotezy Afkhami-Jeddiego i in. (2020)
Ostateczność ograniczenia	Wyłącznie udoskonalenia czynników niższego rzędu	Otwarte pytanie o asymptotyczną lukę w wysokich wymiarach	Dokładnie dopasowane ograniczenie dolne: żadna funkcja pomocnicza nie pobije tego tempa
Niepewność znaku Fouriera	Oddzielne ograniczenia znaku ($A^+(d) < A^-(d)$)	Powiązana z antysamofourierowskimi funkcjami testowymi	Rozstrzygnięta asymptotycznie; niepewność znaku rządzona odbiciem Mellina
Kody korekcyjne	Klasyczne ograniczenia dla kodów sferycznych i binarnych	Asymptotycznie sprzężone z ograniczeniami upakowania	Poprawa o czynniki wykładnicze dla wszystkich parametrów o ustalonej odległości
Pułap metodologiczny	Numeryczna optymalizacja czynników wielomianowych	Otwarta optymalizacja funkcji testowych $f \in \mathcal{A}_d$	Udowodniony pułap matematyczny: dalsze zyski wymagają metod spoza Cohna-Elkiesa

Dlaczego dopasowane ograniczenie dolne zmienia pytanie #

Sama poprawa ograniczenia górnego byłaby dobrą wiadomością. Wynik ten jest niezwykle ostateczny za sprawą drugiej połowy. Dopasowane ograniczenie dolne pokazuje, że żadna funkcja pomocnicza Cohna-Elkiesa nie może poprawić tego wykładnika.

Warto się zastanowić, co to oznacza dla programu badawczego. Przed tym wynikiem badacz z lepszym pomysłem na konstrukcję funkcji pomocniczej miał wiarygodną drogę do jeszcze lepszego wykładnika upakowania kul. Po nim ta droga jest zamknięta na poziomie wykładników. Każdy dalszy postęp w sprawie wykładnika musi przyjść spoza metody Cohna-Elkiesa, bo wewnątrz niej tempo jest teraz dokładne.

Nie chcę tego przesadnie akcentować. Twierdzenia źródła nie mówią, że nowy wykładnik jest prawdziwym wykładnikiem upakowania kul, i nie mówią, że samego upakowania kul nie da się poprawić. Stwierdzenie dotyczy programu liniowego: jego wykładnik jest wyznaczony i nie da się go pobić zmianą funkcji pomocniczej. To, czy pobiłaby go inna technika, jest pytaniem, którego twierdzenia nie poruszają. To wyraźna granica i właśnie taka granica podpowiada dziedzinie, gdzie szukać dalej.

Jest też odczytanie z perspektywy biznesowej, dla czytelników, których interesuje, dokąd trafia wysiłek. Znany, dokładny pułap metody to użyteczna informacja. Mówi, by przestać optymalizować w obrębie tej metody. Dla każdego, kto rozdziela czas badawczy, przejście od „to może się poprawić” do „tego nie da się poprawić” jest warte tyle, co skromny pozytywny wynik.

Kody sferyczne i kody binarne #

Zbiór nie kończy się na upakowaniu. Klasyczne ograniczenia górne dla binarnych i sferycznych kodów o ustalonej odległości zostają poprawione o czynniki wykładnicze dla wszystkich parametrów. To zdanie zawiera mocny kwantyfikator. Poprawa jest o czynniki wykładnicze i zachodzi dla wszystkich parametrów, co jest stwierdzeniem szerszym niż poprawa w jakimś korzystnym zakresie.

Jest też powiązanie z rozdziałem 1. Konstrukcja kodów sferycznych odtwarza również wykładnik upakowania kul z rozdziału 1. Oba wątki łączą się więc: konstrukcja po stronie kodów odtwarza wykładnik po stronie upakowania. Twierdzenia źródła nie opisują mechanizmu tego odtworzenia i nie będę go wymyślał. Ustalają natomiast, że zależność biegnie w tym kierunku: konstrukcja sferyczna daje ten sam wykładnik co rozdział o upakowaniu.

Warto przypomnieć, dlaczego to powiązanie ma znaczenie w świetle opisanej historii. Ograniczenie Kabatianskiego–Levenshteina dla kodów sferycznych było punktem porównania dla programu liniowego, a twierdzenie Cohna i Zhao mówiło, że program jest zawsze co najmniej tak silny. Nowe wyniki poprawiają zarówno ograniczenia dla kodów, jak i dla upakowania, i robią to konstrukcją, która wraca do wykładnika upakowania. Obie strony przesuwają się razem.

Problem niepewności znaku #

Druga konsekwencja twierdzenia głównego dotyczy niepewności znaku w analizie Fouriera, a dokument podaje dość definicji, by zarysować jej kształt.

Dla funkcji g wielkość r(g) definiuje się jako infimum takich R ≥ 0, że g(x) ≥ 0 dla |x| ≥ R. Prościej mówiąc, r(g) to promień, poza którym g jest wszędzie nieujemna. Gdy taki promień nie istnieje, r(g) = ∞. Problem niepewności dotyczy tego, jak mały można uczynić ten promień dla funkcji o zadanym związku z własną transformatą Fouriera.

Tym związkiem jest znak. Warunek ĝ = ςg wiąże funkcję z jej transformatą Fouriera z dokładnością do znaku. Znaki +1 i −1 dają odpowiednio pierwotny i komplementarny problem niepewności. Cohn i Gonçalves wprowadzili antysamofourierowski odpowiednik, czyli problem komplementarny, i powiązali go z upakowaniem kul. To powiązanie jest mostem, przez który wynik o upakowaniu kul rozstrzyga problem niepewności asymptotycznie.

Problem komplementarny nie jest ciekawostką czystej analizy. W bezspinowym modularnym bootstrapie modularna S-antysymetria daje antysamofourierowskie funkcje testowe, których ostateczny znak kontroluje przerwę spektralną. Źródło przywołuje tu Hartmana, Mazáča i Rastellego oraz pracę Afkhami-Jeddiego i in. Pytanie, które zaczęło się jako stwierdzenie o funkcjach i ich transformatach, pojawia się więc także w kontekście o fizycznie brzmiącej nazwie: przerwy spektralnej. Twierdzenia źródła nie wychodzą poza ten jednozdaniowy mechanizm i ja też nie wyjdę, ale przypomina to, że problem niepewności ma towarzystwo poza upakowaniem kul.

Dodatek A dokłada porównanie obu problemów. Stwierdza, że A+(d) < A−(d) dla wszystkich d. To stwierdzenie, że oba problemy różnią się w każdym wymiarze, przy czym pierwsza wielkość jest ściśle mniejsza od drugiej. Twierdzenia źródła nie podają dalszej interpretacji, a nierówność warto odnotować po prostu dlatego, że zachodzi dla wszystkich d bez wyjątku.

Wewnątrz argumentu: uśrednianie, znikanie i oszacowanie masy #

Dokument zawiera kilka stwierdzeń technicznych, które dają wyobrażenie o tym, jak zbudowana jest analiza niepewności. To fragmenty i przedstawię je jako fragmenty, ale razem zarysowują metodę.

Zacznijmy od symetrii. Średnią po obrotach definiuje się przy użyciu unormowanej miary Haara na O(d). Uśrednienie funkcji po obrotach daje funkcję radialną, a chodzi o to, że upraszcza to problem bez łamania warunków. Źródło mówi, że uśrednianie po obrotach zachowuje każdy warunek znaku z listy warunków problemu, oznaczonej (2). Dodaje, że jeśli ĝ = ςg, to r(Rg) ≤ r(g), gdzie Rg jest średnią g po obrotach. Uśrednianie nigdy więc nie pogarsza promienia znaku. Ponadto, w sformułowaniu źródła, Rg ≠ 0, ilekroć g ≠ 0 jest ostatecznie nieujemna, więc uśrednianie nie unicestwia funkcji, która ma właściwe zachowanie znaku w dużej odległości.

Te trzy fakty razem uzasadniają redukcję do funkcji radialnych. Redukcja nic nie kosztuje w promieniu, zachowuje warunki znaku i nie sprowadza funkcji do zera. To kształt standardowego argumentu symetrii, a twierdzenia źródła potwierdzają każdy jego składnik.

Następnie początek układu. Funkcja g = h − ĥ znika w początku układu. To jeden z tych drobnych faktów, które wykonują w dowodzie dużą pracę, bo ograniczenie Cohna-Elkiesa bezpośrednio angażuje wartości w początku układu, a funkcja, która tam znika, zachowuje się inaczej niż taka, która nie znika. Odnotowano też pokrewny krok korekcyjny: skorygowana funkcja gn spełnia gn(0) = 0 i gn → g w L1. Ciąg skorygowanych funkcji, z których każda znika w początku układu, zbiega więc do g w sensie L1. Pozwala to argumentowi pracować z funkcjami, które dokładnie spełniają warunek w początku układu, a jednocześnie przybliżają cel.

Potem pojawia się warunek ilościowy. Oszacowanie masy wymusza 1/a ≥ (1/π − o(1))√d. Twierdzenia źródła nie definiują a, więc nie mogę powiedzieć, co ta wielkość mierzy, i nie będę zgadywał. Można natomiast powiedzieć, jaką postać ma wniosek: ograniczenie dolne na 1/a, które rośnie jak pierwiastek kwadratowy z wymiaru, ze stałą 1/π i znikającą poprawką. Skala pierwiastka z wymiaru wygląda na naturalną wielkość w geometrii wysokowymiarowej, ale to moja obserwacja dotycząca postaci wyrażenia, a twierdzenia źródła nie podają tego jako mechanizmu.

Obraz Mellina #

W dokumencie pojawia się jeszcze jeden element zestawu narzędzi i to on najjaśniej wyjaśnia, dlaczego radialna analiza Fouriera jest tu wykonalna. Po transformacie Mellina radialna transformata Fouriera odbija zmienną Mellina. To zwięzłe stwierdzenie o tym, jak działa transformata. Transformata Fouriera funkcji radialnej, która normalnie jest operatorem całkowym i trudno o niej bezpośrednio rozumować, staje się odbiciem względem zmiennej Mellina. Odbicia są niemal najprostszymi operatorami, jakie istnieją.

Ten sam fragment odnotowuje warunek analityczny po drugiej stronie. Zanik Schwartza funkcji g daje szybki zanik Φg, gdy v → +∞. Tu Φg jest obiektem otrzymanym w analizie Mellina, a v jego zmienną. Zestawienie jest pouczające: własność odbicia obsługuje strukturę, a zanik Schwartza obsługuje kontrolę w nieskończoności. Dowód w tym stylu potrzebuje obu, bo struktura bez zaniku zostawia całki, które mogą nie być zbieżne, a zanik bez struktury nie zostawia niczego do policzenia.

Dokument odnotowuje też, że Sd to pole powierzchni sfery jednostkowej, które wchodzi jako czynnik normujący przy przeliczaniu całek radialnych między sferą a prostą. To kwestia definicyjna i właśnie tego rodzaju rachunkowość decyduje, czy stałe w końcowym ograniczeniu wyjdą poprawnie.

Chcę jasno powiedzieć, czym są te fragmenty. Nie są dowodem. Twierdzenia źródła podają stwierdzenia, a nie wyprowadzenia, i żaden czytelnik nie powinien z nich odtwarzać pełnego argumentu. Pokazują one, że analiza łączy redukcję przez symetrię, warunek w początku układu, ilościowe oszacowanie masy i transformatę, której działanie upraszcza się po zamianie zmiennych. To połączenie jest typowe dla ekstremalnych problemów analizy Fouriera, co sprawia, że dokładność końcowego wyniku jest bardziej, a nie mniej godna uwagi. Narzędzia wyglądające na standardowe wystarczyły, by dojść do ostrej odpowiedzi.

Reszta zbioru #

Rozdział o upakowaniu kul to tylko część dokumentu, a pozostałe wyniki zasługują na rzetelne omówienie. Każdy podaję tu dokładnie tak, jak formułują go twierdzenia źródła.

W teorii grup skonstruowano jawną grupę niesoficzną, co odpowiada na dawne pytanie, czy każda grupa przeliczalna jest soficzna. Dowód łączy prace Kuna oraz Kuna–Thoma z kombinatorycznym argumentem o dopasowaniach w ekspanderach, zrealizowanym za pomocą binarnej algebry Leavitta i grupy V Thompsona. Słowo „jawna” ma tu wagę: wynik jest konstrukcją, a nie argumentem istnienia.

W algebrach operatorów skonstruowano nieskończenie wiele parami nieizomorficznych grup z własnością (T), które mają tę samą grupową algebrę von Neumanna. To obala hipotezę Connesa i odpowiada na pokrewne pytanie Popy o odwzorowania skończenie-do-jednego. Dwa znane pytania upadają za sprawą jednej konstrukcji.

W złożoności arytmetycznej dokument podaje ograniczenia dolne dla permanentu. Obwody bez dzielenia wymagają Ω(n² log log n) bramek, a formuły wymagają Ω(n⁴ / log n) liści. To dwa ograniczenia dla dwóch modeli obliczeń, a dokument podaje je obok siebie.

W informacji kwantowej udowodniono wykładnicze równoległe powtarzanie dla każdej skończonej splątanej gry dwóch graczy. Źródło mówi, że rozszerza to klasyczną zasadę powtarzania poza wcześniej badane szczególne klasy gier kwantowych. Kwantyfikator znów się wyróżnia: każda skończona splątana gra dwóch graczy, bez ograniczenia do szczególnej klasy.

W trudności aproksymacji bezpośrednia redukcja z 3SAT daje trudność z czynnikiem n^(1/400) dla euklidesowego problemu najbliższego wektora, z pokrewnymi konsekwencjami dla dekodowania binarnego i innych norm kratowych. Wykładnik 1/400 jest mały i wolę podać go tak, jak został zapisany, niż go upiększać. Twierdzenia źródła nazywają redukcję bezpośrednią i wiążą z nią konsekwencje dla dekodowania binarnego i innych norm.

W geometrii wypukłej udowodniono ostre górne ograniczenie objętości (n + 1)^n / n! w każdym wymiarze dla ciał wypukłych, których środek ciężkości jest ich jedynym wewnętrznym punktem kratowym. Zarówno ostrość, jak i ogólność dla wszystkich wymiarów są częścią twierdzenia.

W teorii Ramseya nowe nadwykładnicze ograniczenie dolne pokazuje, że Rk(3) rośnie jak k^Θ(k). W ekstremalnej teorii grafów osobne konstrukcje grafów dwudzielnych obalają dwie hipotezy: hipotezę zwartości Erdősa i Simonovitsa oraz hipotezę o degeneracji Erdősa.

Odczytanie zbioru jako całości #

Łatwo byłoby potraktować tę listę jak gablotę z trofeami, warto więc powiedzieć, co można, a czego nie można z niej wywnioskować.

Można powiedzieć, że dokument podaje wyniki w co najmniej ośmiu dziedzinach, że kilka z nich opisano jako odpowiedzi na znane hipotezy lub ich obalenia i że rozdział o upakowaniu kul ma dopasowane ograniczenie dolne, które czyni jego wynik ostatecznym w obrębie metody. Hipotezy te noszą nazwiska Connesa, Popy, Erdősa i Simonovitsa, a hipotezę o tempie upakowania kul postawili Afkhami-Jeddi, Cohn, Hartman, de Laat i Tajdini. Wyniki rozstrzygające znane pytania łatwo ocenić, bo pytanie postawiono, zanim istniała odpowiedź.

Na podstawie samych tych twierdzeń nie można natomiast powiedzieć niczego o tym, jak działa model, ilu prób potrzebował, jak weryfikowano jego wyniki ani jak wypada w porównaniu z pracą ludzi. Źródło mówi, że wyniki uzyskał wewnętrzny model OpenAI, i na tym twierdzenia się kończą. Czytelnik, który chce ocenić znaczenie tego zbioru jako dowodu w sprawie matematyki maszynowej, potrzebuje informacji, których te twierdzenia nie zawierają. Oparłbym się pokusie wypełnienia tej luki wiarygodnie brzmiącą narracją.

Mimo to warto zająć pewne stanowisko. Wyniki są zróżnicowane pod względem techniki: grupa niesoficzna wykorzystuje binarną algebrę Leavitta i grupę V Thompsona, wynik o upakowaniu kul korzysta z analizy Fouriera i transformat Mellina, a trudność problemu najbliższego wektora opiera się na redukcji z 3SAT. Zbiór, który obejmuje tak rozległy obszar techniczny, nie jest produktem jednej sztuczki stosowanej raz za razem. Cokolwiek wygenerowało te wyniki, działało w kilku matematycznych dialektach, i przynajmniej tyle twierdzenia źródła uzasadniają.

Co to oznacza w poszczególnych sektorach #

Dokładne wyznaczenie tempa zaniku Cohna-Elkiesa w wysokich wymiarach i towarzyszące mu wyniki matematyczne wpływają na kilka teoretycznych i stosowanych dziedzin obliczeniowych.

Matematyka czysta i geometria dyskretna #

Dla matematyków zajmujących się geometrią wysokowymiarową i analizą harmoniczną wyznaczenie dokładnego tempa zaniku Cohna-Elkiesa zmienia krajobraz badań. Ponieważ dopasowane ograniczenie dolne dowodzi, że żadna funkcja pomocnicza w $\mathcal{A}_d$ nie pobije nowego wykładnika, badacze mogą przestać szukać lepszych radialnych funkcji testowych w klasycznej metodzie programowania liniowego. Postęp w kierunku gęstszych upakowań kul lub ciaśniejszych ograniczeń uniwersalnych musi teraz sięgać po techniki programowania nieliniowego, hierarchie półokreślone wyższego rzędu albo radykalnie odmienne konstrukcje geometryczne.

Kryptografia i bezpieczeństwo oparte na kratach #

Kryptografia oparta na kratach, stanowiąca rdzeń standardów postkwantowych takich jak ML-KEM i ML-DSA, w dużej mierze opiera się na zakładanej trudności znajdowania najkrótszych lub najbliższych wektorów w wysokowymiarowych kratach euklidesowych. Bezpośrednia redukcja z 3SAT, która ustala trudność z czynnikiem $n^{1/400}$ dla euklidesowego problemu najbliższego wektora (CVP), w połączeniu z ciaśniejszymi wykładniczymi pułapami dla upakowań kul i kodów sferycznych, umacnia teoretyczne podstawy redukcji kratowych od najgorszego do przeciętnego przypadku, nie osłabiając konkretnych parametrów bezpieczeństwa.

Automatyczne dowodzenie twierdzeń i modele bazowe #

Dla zespołów badawczych rozwijających systemy rozumujące i automatyczne dowodzenie twierdzeń rozległość i techniczna głębia tego zbioru stanowią uderzający punkt odniesienia. Zamiast tworzyć syntetyczne warianty znanych dowodów, wewnętrzny model zmierzył się z otwartymi problemami z teorii grup (konstrukcja jawnej grupy niesoficznej za pomocą grupy V Thompsona), algebr operatorów (obalenie hipotezy Connesa) i złożoności arytmetycznej (ograniczenia dolne dla permanentu). Pokazuje to, że architektury neuronowe potrafią poruszać się w głębokiej analizie Fouriera i dopasowaniach kombinatorycznych, pod warunkiem że weryfikacja i sprawdzanie dowodów pozostają rygorystyczne.

Podsumowanie #

Wyznaczenie dokładnego tempa zaniku programu liniowego Cohna-Elkiesa dla upakowania kul zamyka ważny rozdział analizy geometrycznej. Dowodząc hipotezy Afkhami-Jeddiego, Cohna, Hartmana, de Laata i Tajdiniego z 2020 roku i dając pierwszą od 1978 roku poprawę ogólnego wykładnika upakowania kul, praca ustanawia niewzruszony punkt odniesienia w matematyce. Dzięki dopasowanemu ograniczeniu dolnemu, które potwierdza, że żadna funkcja pomocnicza Cohna-Elkiesa nie da dalszych zysków wykładniczych, twierdzenie zarówno rozstrzyga asymptotyczną siłę programu liniowego, jak i kieruje przyszłość geometrii wysokowymiarowej ku zasadniczo nowym horyzontom analitycznym.

Najczęściej zadawane pytania #

Jakie znaczenie miało ograniczenie Kabatianskiego–Levenshteina?

Ustalone w 1978 roku ograniczenie Kabatianskiego–Levenshteina dawało asymptotyczny wykładnik ograniczenia górnego równy 0,59905576... dla gęstości upakowania kul w wysokich wymiarach. Przez ponad cztery dekady późniejsze udoskonalenia poprawiały jedynie algebraiczne czynniki niższego rzędu, a wiodące tempo wykładnicze pozostawało nietknięte aż do tego wyniku.

Dlaczego dopasowane ograniczenie dolne jest tak istotne?

Samo ograniczenie górne pokazuje, co osiąga program liniowy, ale dopasowane ograniczenie dolne dowodzi, że żaden wybór funkcji pomocniczej f z dopuszczalnej klasy Cohna-Elkiesa A(d) nie da mniejszego wykładnika. Ustanawia to bezwzględny pułap samej metody programowania liniowego.

Jak problem niepewności znaku Fouriera wiąże się z upakowaniem kul?

Cohn i Gonçalves wykazali, że komplementarny problem niepewności znaku Fouriera (gdzie g_hat = -g) jest ściśle sprzężony z ograniczeniami upakowania kul. Dzięki uśrednianiu po obrotach i odbiciom w transformacie Mellina asymptotyczne rozwiązanie programu Cohna-Elkiesa bezpośrednio rozstrzyga problem niepewności znaku Fouriera.

Czy ten wynik zagraża kryptografii opartej na kratach?

Nie. Twierdzenie zaostrza wprawdzie ograniczenia górne na to, jak gęsto można upakować kule w wysokich wymiarach, i ustala trudność z czynnikiem $n^{1/400}$ dla problemu najbliższego wektora, ale nie daje algorytmów redukcji krat w czasie wielomianowym. Praktyczne kryptosystemy kratowe pozostają bezpieczne wobec znanych ataków kwantowych i klasycznych.

Bibliografia #

Nima Afkhami-Jeddi i in., (2020). Wysokowymiarowe upakowania kul i modularny bootstrap ⧉. Journal of High Energy Physics.
Henry Cohn i Noam Elkies, (2003). Nowe ograniczenia górne dla upakowań kul I ⧉. Annals of Mathematics.
Henry Cohn i Felipe Gonçalves, (2019). Optymalna zasada nieoznaczoności w analizie Fouriera ⧉. PNAS.
Henry Cohn i Yufei Zhao, (2014). Ograniczenia upakowania kul przez kody sferyczne ⧉. Duke Mathematical Journal.
G. A. Kabatianskii i V. I. Levenshtein, (1978). Ograniczenia dla upakowań na sferze i w przestrzeni ⧉. Problems of Information Transmission.
Maryna S. Viazovska, (2017). Problem upakowania kul w wymiarze 8 ⧉. Annals of Mathematics.

Ostatnia weryfikacja 2026-10-05.

Ostatnia weryfikacja 2026-10-27.

Opublikuj ponownie ten artykuł

Model OpenAI wyznacza dokładne tempo zaniku programu Cohna-Elkiesa — Sebastien Rousseau

Wewnętrzny model OpenAI wyznacza dokładne tempo zaniku programu liniowego Cohna-Elkiesa i daje pierwszą od 1978 roku poprawę wykładnika upakowania kul.

Ten artykuł jest objęty licencją Creative Commons Attribution 4.0 International. Ponowna publikacja wymaga przypisania do kanonicznego adresu URL.

Model OpenAI wyznacza dokładne tempo zaniku programu Cohna-Elkiesa — Sebastien Rousseau

Wewnętrzny model OpenAI wyznacza dokładne tempo zaniku programu liniowego Cohna-Elkiesa i daje pierwszą od 1978 roku poprawę wykładnika upakowania kul.

Originally published at https://sebastienrousseau.com/pl/2026-10-05-model-openai-wyznacza-dok-adne-tempo/ by Sebastien Rousseau.
Licensed under CC-BY-4.0.

SEBASTIEN ROUSSEAU FOUNDER · ENGINEER