Модель 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. При повторной публикации требуется указание канонической ссылки.

Модель OpenAI нашла точную скорость убывания границы Кона–Элкиса — Sebastien Rousseau

Внутренняя модель OpenAI определила точную скорость убывания линейной программы Кона–Элкиса: первое улучшение показателя упаковки шаров с 1978 года.

Originally published at https://sebastienrousseau.com/ru/2026-10-05-model-openai-nashla-tochnuyu-skorost-ubyvaniya/ by Sebastien Rousseau.
Licensed under CC-BY-4.0.

SEBASTIEN ROUSSEAU FOUNDER · ENGINEER