Модель OpenAI знайшла точну швидкість спадання межі Кона–Елкіса

TL;DR. Внутрішня модель OpenAI визначила точну швидкість спадання лінійної програми Кона–Елкіса: перше з 1978 року покращення показника пакування куль.

Ключові висновки

Що являє собою збірка і чому вирізняється один результат. Документ починається скромно.
Програма Кона–Елкіса і те, що вона оцінює. Задача про пакування куль запитує, наскільки щільно кулі, що не перетинаються, можуть заповнити простір.
Чого цей підхід уже досяг. Перш ніж перейти до нової теореми, варто конкретно сказати, що вже дав фур'є-аналітичний підхід лінійного програмування, бо новий результат частково є твердженням про те, наскільки далі він може просунутися.
Головна теорема. Головна теорема документа доводить експоненційну швидкість, передбачену в гіпотезах 3.1 і 3.2 тієї статті 2020 року.

Збірка математичних результатів внутрішньої моделі OpenAI остаточно визначає асимптотичну силу лінійної програми Кона–Елкіса для пакування куль. Вона дає перше з 1978 року покращення загального показника пакування куль, а разом із ним точно відповідну нижню оцінку.

Що являє собою збірка і чому вирізняється один результат #

Документ починається скромно. Він представляє збірку результатів, отриманих внутрішньою моделлю OpenAI, і повідомляє, що вони охоплюють математику й теоретичну інформатику. Це опис походження та охоплення, і в ньому не сказано, як використовували модель і як перевіряли її результати. Ці питання важливі, а джерело в тому вигляді, у якому його тут викладено, залишає їх без відповіді, тож ця стаття не вдаватиме, що відповідь є. Твердження ж підкріплюють перелік заявлених результатів, і цей перелік достатньо довгий, щоб цікавим було не питання, чи вражає якийсь окремий пункт. Цікаво, чому один із них заслуговує на основну увагу.

Причина в тому, що результат про пакування куль єдиний у збірці закриває кількісний розрив у програмі досліджень із довгою та іменною історією. Решта результатів вражають і самі по собі. Явно побудована несофічна група відповідає на давнє питання. Спростування гіпотези Конна розв'язує те, що запропонував відомий математик. Але результат про пакування куль стоїть наприкінці ланцюжка, що веде від фур'є-аналітичного підходу через два знамениті точні розв'язки в окремих вимірностях до питання про високі вимірності, яке залишалося відкритим багато років. Щоб зрозуміти результат, треба зрозуміти цей ланцюжок.

Тому більша частина подальшого тексту присвячена лінійній програмі Кона–Елкіса: що вона собою являє, що про неї було відомо, що стверджує нова теорема і як побудовано частину доведення, пов'язану з невизначеністю знака. Потім коротший розділ оглядає решту результатів збірки, кожен у тому формулюванні, у якому його заявлено, і не більше.

Програма Кона–Елкіса і те, що вона оцінює #

Задача про пакування куль запитує, наскільки щільно кулі, що не перетинаються, можуть заповнити простір. Документ фіксує для цього позначення. Для центрів, віддалених один від одного щонайменше на 1, ∆d є точною верхньою межею верхніх щільностей куль радіуса 1/2 у Rd. Інакше кажучи, ∆d позначає максимальну щільність пакування куль у Rd. Усе в першому розділі збірки вимірюється відносно цієї величини.

Програма Кона–Елкіса дає верхню оцінку для ∆d. Її оптимальний результат позначають LPd і визначають як оптимальну оцінку щільності, яку дає програма. Механізмом слугує оцінка Горбачова–Кона–Елкіса, яка кожній функції f із класу, позначеного Ad, ставить у відповідність верхню оцінку щільності vd f(0)/(2d f̂(0)). Словами: ви обираєте допоміжну функцію f із допустимого класу, обчислюєте її значення в початку координат і значення її перетворення Фур'є в початку координат, складаєте це відношення з множниками об'єму та масштабу, і результат обмежує щільність пакування згори. Лінійна програма шукає таку f, за якої ця оцінка найменша.

У цьому підході вся складність полягає у вдалому виборі f. Хитро дібрана функція дає точну оцінку, а невдало дібрана дає слабку оцінку, яка проте правильна. Тому відповідна нижня оцінка в новому результаті така важлива. Вона говорить про всі допустимі функції одразу й перетворює пошук кращих функцій на закрите питання.

Чого цей підхід уже досяг #

Перш ніж перейти до нової теореми, варто конкретно сказати, що вже дав фур'є-аналітичний підхід лінійного програмування, бо новий результат частково є твердженням про те, наскільки далі він може просунутися.

Вязовська застосувала цей підхід, щоб довести, що ґратка E8 дає оптимальне пакування у вимірності вісім. Потім Кон, Кумар, Міллер, Радченко та Вязовська встановили оптимальність ґратки Ліча у вимірності двадцять чотири. Це точні результати в окремих вимірностях, і саме завдяки їм підхід має репутацію, що виходить за межі ролі інструмента для оцінок. У двох конкретних вимірностях він влучає точно в істинну відповідь.

Картина у високих вимірностях була менш ясною. Кон і Чжао довели, що лінійна програма завжди не слабша за сферичну кодову оцінку Кабатянського–Левенштейна. Це корисна гарантія, бо оцінка Кабатянського–Левенштейна давала найкращий відомий загальний показник. Але формулювання «не слабша» залишає відкритими дві можливості: програма може точно збігатися з цим показником, а може його перевершувати. Документ прямо формулює наслідок. Питання про те, чи покращує лінійна програма класичний показник пакування куль у високих вимірностях, залишалося відкритим.

Афхамі-Джедді, Кон, Гартман, де Лаат і Тайдіні висловили гіпотезу про швидкість лінійної програми у високих вимірностях. Ця гіпотеза являє собою обережне твердження, і джерело саме так до неї ставиться. Це була гіпотеза, підкріплена тими даними, які мали автори, і ніхто її не довів. Новий результат змінює її статус.

Головна теорема #

Головна теорема документа доводить експоненційну швидкість, передбачену в гіпотезах 3.1 і 3.2 тієї статті 2020 року. У формулюванні, яке підкріплюють твердження: автори визначають точну експоненційну швидкість спадання лінійної програми Кона–Елкіса для пакування куль. Асимптотичну силу програми, за словами джерела, визначено точно.

Із джерела прямо випливають два наслідки. Перший: покращена загальна оцінка пакування у високих вимірностях. Другий: відповідну задачу про невизначеність знака для перетворення Фур'є розв'язано асимптотично. Це наслідки різного роду. Один стосується геометрії, другий аналізу, і те, що одна теорема дає обидва, є першим натяком на те, що задача про пакування куль і задача про невизначеність являють собою два боки однієї й тієї самої структури.

Джерело також зіставляє досягнення з історією. Воно описує результат як перше з 1978 року покращення загального показника пакування куль. Класичний показник Кабатянського–Левенштейна дорівнював 0,59905576..., і саме це число слугувало еталоном. Документ зазначає, що подальші уточнення через сферичні коди покращували лише множники нижчого порядку. Іншими словами, сам показник, тобто величина старшого порядку, не зрушував.

Я вважаю, що саме така постановка правильна для оцінки результату. Покращення нижчого порядку підправляє константи й поліноміальні множники, залишаючи експоненційну швидкість на місці. Покращення показника змінює саму швидкість. Твердження підкріплюють саме цю відмінність, а також те, що попередні уточнення перебували на боці нижчого порядку.

Вимір / підхід	Класична база (1978)	Лінійна програма Кона–Елкіса	Нове доведення моделі
Показник пакування куль	Оцінка Кабатянського–Левенштейна: 0,59905576...	Не слабша за сферичні кодові оцінки (Кон–Чжао)	Доведено точну асимптотичну швидкість, передбачену Афхамі-Джедді та ін. (2020)
Остаточність оцінки	Лише уточнення множників нижчого порядку	Відкрите питання про асимптотичний розрив у високих вимірностях	Точно відповідна нижня оцінка: жодна допоміжна функція не перевершить цю швидкість
Невизначеність знака Фур'є	Окремі оцінки знака ($A^+(d) < A^-(d)$)	Пов'язана з антисамодвоїстими за Фур'є пробними функціями	Розв'язано асимптотично; невизначеність знака визначається відбиттям Мелліна
Коди, що виправляють помилки	Класичні оцінки сферичних і двійкових кодів	Асимптотично пов'язані з оцінками пакування	Покращення на експоненційні множники за всіх параметрів фіксованої відстані
Методологічна стеля	Чисельна оптимізація поліноміальних множників	Відкрита оптимізація допоміжних пробних функцій $f \in \mathcal{A}_d$	Доведено математичну стелю: подальший виграш потребує методів поза Коном–Елкісом

Чому відповідна нижня оцінка змінює питання #

Саме лише покращення верхньої оцінки було б доброю новиною. Незвично остаточним цей результат робить друга половина. Відповідна нижня оцінка показує, що жодна допоміжна функція Кона–Елкіса не може покращити цей показник.

Подумайте, що це означає для програми досліджень. До результату дослідник із вдалою ідеєю побудови допоміжної функції мав правдоподібний шлях до ще кращого показника пакування куль. Після нього цей шлях закрито на рівні показників. Будь-який подальший поступ у показнику має прийти ззовні підходу Кона–Елкіса, бо всередині нього швидкість тепер точна.

Я не хочу це перебільшувати. Твердження не кажуть, що новий показник є істинним показником пакування куль, і не кажуть, що саме пакування куль не може бути кращим. Твердження стосується лінійної програми: її показник зафіксовано, і перевершити його, змінюючи допоміжну функцію, неможливо. Чи може його перевершити інша техніка, твердження не обговорюють. Це чітка межа, і саме такі межі підказують галузі, де шукати далі.

Є й прикладне прочитання для тих, кому важливо, куди спрямовуються зусилля. Відома точна стеля методу є корисною інформацією. Вона каже, що оптимізувати всередині цього методу більше не потрібно. Для будь-кого, хто розподіляє дослідницький час, перехід від «це може покращитися» до «це не може покращитися» вартий не менше за скромний позитивний результат.

Сферичні та двійкові коди #

Збірка не обмежується пакуванням. Класичні верхні оцінки для двійкових і сферичних кодів із фіксованою відстанню покращено на експоненційні множники за всіх значень параметрів. У цій фразі стоїть сильний квантор. Покращення йде на експоненційні множники і справджується за всіх параметрів, а це ширше твердження, ніж покращення у сприятливому режимі.

Є й зв'язок із розділом 1. Конструкція сферичного коду також відтворює показник пакування куль із розділу 1. Отже, дві лінії поєднуються: конструкція на боці кодів відтворює показник на боці пакування. Твердження не розкривають механізму цього відтворення, і я не вигадуватиму його. Вони встановлюють, що зв'язок іде саме в цьому напрямку: сферична конструкція дає той самий показник, що й розділ про пакування.

Варто нагадати, чому цей зв'язок важливий з огляду на викладену вище історію. Сферична кодова оцінка Кабатянського–Левенштейна була точкою порівняння для лінійної програми, а теорема Кона і Чжао стверджувала, що програма завжди не слабша. Нові результати покращують як оцінки кодів, так і оцінки пакування, і роблять це за допомогою конструкції, яка повертається до показника пакування. Обидва боки зрушують разом.

Задача про невизначеність знака #

Другий наслідок головної теореми стосується невизначеності знака для перетворення Фур'є, і документ дає достатньо означень, щоб окреслити її форму.

Для функції g величину r(g) означено як точну нижню межу тих R ≥ 0, за яких g(x) ≥ 0 для |x| ≥ R. Простіше кажучи, r(g) є радіусом, за межами якого g усюди невід'ємна. Якщо такого радіуса немає, то r(g) = ∞. Задача про невизначеність запитує, наскільки малим можна зробити цей радіус для функцій із заданим співвідношенням з їхнім власним перетворенням Фур'є.

Це співвідношення задається знаком. Умова ĝ = ςg пов'язує функцію з її перетворенням Фур'є з точністю до знака. Знаки +1 і −1 дають відповідно початкову та доповняльну задачі про невизначеність. Кон і Гонсалвес увели антисамодвоїстий за Фур'є аналог, тобто доповняльну задачу, і пов'язали його з пакуванням куль. Цей зв'язок і є мостом, яким результат про пакування куль асимптотично розв'язує задачу про невизначеність.

Доповняльна задача не є курйозом чистого аналізу. У безспіновому модулярному бутстрапі модулярна S-антисиметрія породжує антисамодвоїсті за Фур'є пробні функції, знак яких на нескінченності керує спектральною щілиною. Джерело посилається тут на Гартмана, Мазача та Растеллі й на статтю Афхамі-Джедді та ін. Тож питання, що почалося як твердження про функції та їхні перетворення, виникає і в задачі з фізичною назвою, спектральною щілиною. Твердження не йдуть далі цього механізму в один рядок, і я теж не піду, але це нагадування, що задача про невизначеність має родичів поза пакуванням куль.

Додаток A додає порівняння двох задач. У ньому зазначено, що A+(d) < A−(d) для всіх d. Це твердження про те, що дві задачі відрізняються в кожній вимірності, причому перша величина строго менша за другу. Твердження не дають подальшого тлумачення, і нерівність варто відзначити просто тому, що вона виконується для всіх d без винятків.

Усередині доведення: усереднення, перетворення на нуль і оцінка маси #

Документ містить кілька технічних тверджень, які дають уявлення про те, як побудовано аналіз невизначеності. Це фрагменти, і я подам їх як фрагменти, але разом вони окреслюють метод.

Почнімо із симетрії. Середнє за обертаннями означено за допомогою нормованої міри Хаара на O(d). Усереднення функції за обертаннями дає радіальну функцію, і сенс цього в тому, що задача спрощується без порушення обмежень. Джерело стверджує, що усереднення за обертаннями зберігає кожну умову на знак зі списку обмежень задачі, позначеного (2). Воно додає, що коли ĝ = ςg, то r(Rg) ≤ r(g), де Rg є середнім функції g за обертаннями. Отже, усереднення ніколи не погіршує радіус знака. Крім того, у формулюванні джерела, Rg ≠ 0, коли g ≠ 0 зрештою невід'ємна, тож усереднення не знищує функцію, яка правильно поводиться за знаком на великих відстанях.

Разом ці три факти виправдовують зведення до радіальних функцій. Зведення нічого не коштує в термінах радіуса, зберігає умови на знак і не перетворює функцію на нуль. Така форма стандартного міркування про симетрію, і твердження підтверджують кожну його складову.

Далі початок координат. Функція g = h − ĥ перетворюється на нуль у початку координат. Це з тих дрібних фактів, що виконують велику роботу в доведенні, бо оцінка Кона–Елкіса безпосередньо використовує значення в початку координат, а функція, що там перетворюється на нуль, поводиться інакше, ніж та, що не перетворюється. Зафіксовано й пов'язаний із цим крок корекції: скоригована функція gn задовольняє умови gn(0) = 0 і gn → g в L1. Отже, послідовність скоригованих функцій, кожна з яких перетворюється на нуль у початку координат, збігається до g у сенсі L1. Це дає змогу міркуванню працювати з функціями, які точно задовольняють умову в початку координат, і водночас наближати цільову функцію.

Потім є кількісне обмеження. Оцінка маси дає 1/a ≥ (1/π − o(1))√d. Твердження не означують a, тому я не можу сказати, що ця величина вимірює, і не вгадуватиму. Можна сказати про форму висновку: це нижня оцінка на 1/a, що зростає як квадратний корінь із вимірності, зі сталою 1/π та зникною поправкою. Масштаб квадратного кореня з вимірності виглядає природно для геометрії високих вимірностей, але це моє спостереження про форму виразу, і твердження не висувають його як механізм.

Картина Мелліна #

У документі є ще один інструмент, і саме він найясніше пояснює, чому радіальний аналіз Фур'є тут піддається дослідженню. Після перетворення Мелліна радіальне перетворення Фур'є відбиває змінну Мелліна. Це стисле твердження про те, як діє перетворення. Перетворення Фур'є радіальної функції, яке зазвичай є інтегральним оператором, про який незручно міркувати безпосередньо, стає відбиттям за змінною Мелліна. Відбиття належать до найпростіших операторів.

У тому самому місці зафіксовано аналітичну умову з іншого боку. Шварцівське спадання g дає швидке спадання Φg при v → +∞. Тут Φg є об'єктом, отриманим в аналізі Мелліна, а v його змінною. Ця пара повчальна: властивість відбиття відповідає за структуру, а шварцівське спадання відповідає за контроль на нескінченності. Доведенню в такому стилі потрібне і те, і те, бо структура без спадання залишає інтеграли, які можуть не збігатися, а спадання без структури не залишає нічого, що можна обчислити.

Документ також зазначає, що Sd є площею одиничної сфери, яка входить як нормувальний множник під час перенесення радіальних інтегралів зі сфери на пряму. Це питання означень, і саме такий облік визначає, чи вийдуть сталі в підсумковій оцінці правильними.

Хочу ясно сказати, чим є ці фрагменти. Вони не є доведенням. Твердження дають формулювання, а не виведення, і жоден читач не повинен відтворювати за ними повне міркування. Вони показують, що аналіз поєднує зведення за симетрією, умову в початку координат, кількісну оцінку маси та перетворення, дія якого спрощується після заміни змінних. Таке поєднання звичайне для фур'є-аналітичних екстремальних задач, і це робить точність підсумкового результату радше більш, ніж менш примітною. Стандартних на вигляд інструментів вистачило, щоб отримати точну відповідь.

Решта збірки #

Розділ про пакування куль становить лише одну частину документа, і решта результатів заслуговує на чесний виклад. Кожен із них наведено тут саме так, як його формулюють твердження.

У теорії груп побудовано явну несофічну групу, що відповідає на давнє питання, чи є софічною кожна зліченна група. Доведення поєднує праці Куна та Куна–Тома з комбінаторним міркуванням про паросполучення в експандерах, реалізованим за допомогою двійкової алгебри Лівітт і групи V Томпсона. Слово «явна» тут вагоме: результат являє собою конструкцію, а не міркування про існування.

В операторних алгебрах побудовано нескінченно багато попарно неізоморфних груп із властивістю (T), що мають одну й ту саму групову алгебру фон Неймана. Це спростовує гіпотезу Конна й відповідає на пов'язане з нею питання Попи про скінченнозначність. Два іменні питання розв'язуються однією конструкцією.

В арифметичній складності документ дає нижні оцінки для перманента. Схемам без ділення потрібно Ω(n² log log n) вентилів, а формулам потрібно Ω(n⁴ / log n) листків. Це дві оцінки для двох моделей обчислень, і документ наводить їх поруч.

У квантовій інформатиці доведено експоненційне паралельне повторення для будь-якої скінченної гри двох гравців зі сплутаністю. Джерело стверджує, що це поширює класичний принцип повторення за межі раніше розглянутих спеціальних класів квантових ігор. Квантор знову вирізняється: будь-яка скінченна гра двох гравців зі сплутаністю, без обмеження спеціальним класом.

У складності апроксимації пряме зведення від 3SAT дає складність із множником n^(1/400) для евклідової задачі про найближчий вектор, із пов'язаними наслідками для двійкового декодування та інших норм на ґратках. Показник 1/400 малий, і я волію навести його як є, а не прикрашати. Твердження називають зведення прямим і пов'язують із ним наслідки для двійкового декодування та інших норм.

В опуклій геометрії точну верхню оцінку об'єму (n + 1)^n / n! доведено в кожній вимірності для опуклих тіл, у яких барицентр є єдиною внутрішньою точкою ґратки. Точність оцінки та справедливість в усіх вимірностях входять до твердження.

У теорії Рамсея нова надекспоненційна нижня оцінка показує, що Rk(3) зростає як k^Θ(k). А в екстремальній теорії графів окремі конструкції двочасткових графів спростовують дві гіпотези: гіпотезу компактності Ердеша й Шимоновича та гіпотезу Ердеша про виродженість.

Як читати збірку загалом #

Цей перелік легко сприйняти як вітрину трофеїв, тому варто сказати, які висновки з нього можна зробити, а які ні.

Можна сказати, що документ повідомляє про результати щонайменше у восьми галузях, що кілька з них описано як відповіді на іменні гіпотези або їх спростування і що розділ про пакування куль супроводжується відповідною нижньою оцінкою, яка робить його результат остаточним у межах свого підходу. Зачеплені гіпотези мають імена Конна, Попи, Ердеша й Шимоновича, а швидкість для пакування куль передбачили Афхамі-Джедді, Кон, Гартман, де Лаат і Тайдіні. Результати, що закривають іменні питання, легко оцінювати, бо питання поставили до того, як з'явилася відповідь.

Не можна сказати, спираючись лише на ці твердження, нічого про те, як працює модель, скільки спроб їй знадобилося, як перевіряли її результати і як вони співвідносяться з людськими зусиллями. Джерело каже, що результати отримала внутрішня модель OpenAI, і на цьому твердження закінчуються. Читачеві, який хоче зважити значення збірки як свідчення про машинну математику, потрібна інформація, якої у твердженнях немає. Я б не піддавався спокусі заповнити цю прогалину правдоподібною розповіддю.

Проте певну позицію зайняти варто. Результати неоднорідні за технікою: несофічна група використовує двійкову алгебру Лівітт і групу V Томпсона, результат про пакування куль використовує аналіз Фур'є та перетворення Мелліна, а складність задачі про найближчий вектор використовує зведення від 3SAT. Збірка, що охоплює таку широку технічну територію, не є плодом одного прийому, застосованого багато разів. Те, що отримало ці результати, працювало кількома математичними діалектами, і твердження підкріплюють щонайменше це.

Що це означає для галузей #

Точне визначення швидкості спадання Кона–Елкіса у високих вимірностях і супутні математичні результати впливають на низку теоретичних і прикладних обчислювальних галузей.

Чиста математика та дискретна геометрія #

Для математиків, які працюють у геометрії високих вимірностей і гармонічному аналізі, точне визначення швидкості спадання Кона–Елкіса змінює ландшафт досліджень. Оскільки відповідна нижня оцінка доводить, що жодна допоміжна функція з $\mathcal{A}_d$ не може перевершити новий показник, дослідники можуть припинити пошук кращих радіальних пробних функцій у межах класичного підходу лінійного програмування. Поступ до щільніших пакувань куль або точніших універсальних оцінок тепер має спиратися на методи нелінійного програмування, напіввизначені ієрархії вищих порядків або радикально інші геометричні конструкції.

Криптографія та безпека на основі ґраток #

Криптографія на ґратках, що становить основу постквантових стандартів, таких як ML-KEM і ML-DSA, значною мірою спирається на припущену складність пошуку найкоротших або найближчих векторів в евклідових ґратках високої вимірності. Пряме зведення від 3SAT, що встановлює складність із множником $n^{1/400}$ для евклідової задачі про найближчий вектор (CVP), разом із жорсткішими експоненційними стелями для пакувань куль і сферичних кодів зміцнює теоретичні основи зведень на ґратках від найгіршого випадку до середнього, не послаблюючи конкретних параметрів безпеки.

Автоматичне доведення теорем і базові моделі #

Для дослідницьких груп, які розробляють системи міркувань і автоматичні засоби доведення теорем, широта й технічна глибина збірки задають помітний орієнтир. Замість синтетичних варіацій відомих доведень внутрішня модель узялася за відкриті задачі з теорії груп (побудова явної несофічної групи через групу V Томпсона), операторних алгебр (спростування гіпотези Конна) та арифметичної складності (нижні оцінки перманента). Це показує, що нейромережеві архітектури здатні орієнтуватися в глибокому аналізі Фур'є та комбінаторних паросполученнях за умови, що перевірка й формальна верифікація доведень залишаються суворими.

Висновок #

Визначення точної швидкості спадання лінійної програми Кона–Елкіса для пакування куль закриває важливий розділ геометричного аналізу. Довівши гіпотезу 2020 року Афхамі-Джедді, Кона, Гартмана, де Лаата й Тайдіні та отримавши перше з 1978 року покращення загального показника пакування куль, робота встановлює непохитну математичну базу. Оскільки відповідна нижня оцінка підтверджує, що жодна допоміжна функція Кона–Елкіса не дасть подальшого експоненційного виграшу, теорема водночас визначає асимптотичну силу лінійної програми та спрямовує майбутнє геометрії високих вимірностей до принципово нових аналітичних обріїв.

Часті запитання #

У чому було значення оцінки Кабатянського–Левенштейна?

Встановлена 1978 року, оцінка Кабатянського–Левенштейна дала асимптотичний верхній показник 0,59905576... для щільності пакування куль у високих вимірностях. Понад сорок років подальші уточнення покращували лише алгебраїчні множники нижчого порядку, не зачіпаючи головної експоненційної швидкості аж до цього результату.

Чому відповідна нижня оцінка така важлива?

Сама лише верхня оцінка показує, чого досягає лінійна програма, а відповідна нижня оцінка доводить, що жоден вибір допоміжної функції f із допустимого класу Кона–Елкіса A(d) не може дати менший показник. Це встановлює абсолютну стелю для самого підходу лінійного програмування.

Як задача про невизначеність знака Фур'є пов'язана з пакуванням куль?

Кон і Гонсалвес встановили, що доповняльна задача про невизначеність знака Фур'є (де g_hat = -g) тісно пов'язана з оцінками пакування куль. Через усереднення за обертаннями та відбиття перетворення Мелліна асимптотичний розв'язок програми Кона–Елкіса безпосередньо розв'язує задачу про невизначеність знака Фур'є.

Чи загрожує цей результат криптографії на ґратках?

Ні. Теорема уточнює верхні оцінки того, наскільки щільно кулі можуть пакуватися у високих вимірностях, і встановлює складність із множником $n^{1/400}$ для задачі про найближчий вектор, але не дає поліноміальних алгоритмів редукції ґраток. Практичні криптосистеми на ґратках залишаються стійкими до відомих квантових і класичних атак.

Джерела #

Nima Afkhami-Jeddi et al., (2020). Пакування куль у високих вимірностях і модулярний бутстрап ⧉. Journal of High Energy Physics.
Henry Cohn and Noam Elkies, (2003). Нові верхні оцінки для пакувань куль I ⧉. Annals of Mathematics.
Henry Cohn and Felipe Gonçalves, (2019). Оптимальний принцип невизначеності в аналізі Фур'є ⧉. PNAS.
Henry Cohn and Yufei Zhao, (2014). Оцінки пакування куль через сферичні коди ⧉. Duke Mathematical Journal.
G. A. Kabatianskii and V. I. Levenshtein, (1978). Оцінки для пакувань на сфері та в просторі ⧉. Problems of Information Transmission.
Maryna S. Viazovska, (2017). Задача про пакування куль у вимірності 8 ⧉. Annals of Mathematics.

Останній перегляд 2026-10-05.

Останній перегляд 2026-10-27.

Перевидати цю статтю

Модель OpenAI знайшла точну швидкість спадання межі Кона–Елкіса — Sebastien Rousseau

Внутрішня модель OpenAI визначила точну швидкість спадання лінійної програми Кона–Елкіса: перше з 1978 року покращення показника пакування куль.

Ця стаття поширюється за ліцензією Creative Commons Attribution 4.0 International. Перевидання вимагає посилання на канонічну URL-адресу.

Модель OpenAI знайшла точну швидкість спадання межі Кона–Елкіса — Sebastien Rousseau

Внутрішня модель OpenAI визначила точну швидкість спадання лінійної програми Кона–Елкіса: перше з 1978 року покращення показника пакування куль.

Originally published at https://sebastienrousseau.com/uk/2026-10-05-model-openai-znayshla-tochnu-shvydkist-spadannya/ by Sebastien Rousseau.
Licensed under CC-BY-4.0.

SEBASTIEN ROUSSEAU FOUNDER · ENGINEER