Плотнейшая упаковка шаров: два продвижения за год

Задачу принесли в математику снаружи: в 1591 году английский математик считал для флота, сколько ядер помещается в пирамидальной куче, и написал Кеплеру письмо с вопросом, какая укладка самая плотная

Кеплер подошёл к вопросу с неожиданной стороны. Двадцать лет спустя он издал брошюру о шестиугольных снежинках, где вывел их шестиугольность из догадки о том, как устроена плотнейшая укладка шариков, — то есть форма снежинки была для него следствием ответа на нашу задачу

Укладка, которую он имел в виду, знакома всякому, кто видел выложенные пирамидой апельсины: пространство замощено одинаковыми кубами, центры шаров стоят в вершинах кубов и в центрах всех граней. Решётку из таких точек, а с ней и упаковку, называют гранецентрированной кубической. Кеплер утверждал, что плотнее упаковки не бывает, — хотя упаковок той же плотности бесконечно много

Плотность такой упаковки равна $\pi/\sqrt{18} \approx 0{,}7405$. В 1831 году Гаусс доказал утверждение Кеплера для решётчатых упаковок — тех, где центры шаров образуют решётку. Кеплер же спрашивал про все упаковки, а их несравнимо больше

Плоскость закрыл Фейеш Тот в 1940-м. Гипотезу Кеплера целиком закрыл Хейлс в 1998-м — рассуждением, которое рецензенты не смогли проверить до конца. Плотнейшую упаковку в размерности 8 нашла Марина Вязовская, в размерности 24 — она же с соавторами, обе работы в 2016 году

Начнём с контактного числа: сколько единичных шаров могут одновременно касаться одного такого же. На плоскости их шесть. В пространстве Ньютон в 1694 году предположил, что двенадцать, — доказали это Шютте и ван дер Варден только в 1953-м, и доказали геометрически. Техника, о которой дальше, пришла позже и из другой области — из теории кодов

Центры касающихся шаров лежат на сфере радиуса 2; уменьшив расстояния вдвое, считаем их точками $x_1,\dots,x_N$ единичной сферы в $\mathbb{R}^n$, попарные углы между которыми не меньше 60 градусов. Косинус угла есть скалярное произведение $t=\langle x_i,x_j\rangle$, так что условие на угол записывается как $t\le\tfrac12$

Нам понадобятся многочлены Гегенбауэра $P_k$ — в размерности $n$ есть ровно одна последовательность многочленов степени $k$ с двумя свойствами:

$$\int_{-1}^{1} P_k(t)P_m(t)\,(1-t^2)^{\frac{n-3}{2}}\,dt=0\ \ \text{при } k\ne m,\qquad P_k(1)=1$$

Из нормировки, в частности, $P_0\equiv1$. По теореме Шёнберга эти многочлены положительно определены: для любых точек сферы сумма $\sum_{i,j}P_k(\langle x_i,x_j\rangle)$ неотрицательна

Неизвестные здесь — коэффициенты $c_k$, и оба условия линейны по ним: отсюда и название метода, линейное программирование. Отсюда следует такое утверждение. Возьмём числа $c_0=1$ и $c_k\ge0$, положим $f=\sum_k c_kP_k$ и предположим, что $f$ неположительна при $t\le\tfrac12$. Тогда контактное число $k(n)$ не больше $f(1)$:

$$f=\sum_{k\ge 0}c_kP_k,\quad c_0=1,\ c_k\ge 0,\quad f(t)\le 0\ \text{ при } t\le \tfrac12\ \Longrightarrow\ k(n)\le f(1)$$

Доказательство — оценка суммы $S=\sum_{i,j}f(\langle x_i,x_j\rangle)$ по тем же $N$ точкам с двух сторон

• Сверху. Недиагональные слагаемые неположительны: их аргумент не больше $\tfrac12$, а там $f\le0$. Диагональных ровно $N$, каждое равно $f(1)$. Значит $S\le Nf(1)$
• Снизу. Разложим $f$ по $P_k$ и поменяем порядок суммирования. Слагаемое с номером $k$ равно $c_k\sum_{i,j}P_k$ и неотрицательно по Шёнбергу, а слагаемое с $k=0$ даёт $c_0N^2=N^2$ — здесь и работает нормировка $P_0\equiv1$. Значит $S\ge N^2$
• Вместе. $N^2\le S\le Nf(1)$, откуда $N\le f(1)$

Оценка тем сильнее, чем меньшую $f(1)$ удаётся подобрать. В размерности 3 лучшее, что даёт этот метод, — около 13: до двенадцати он не дотягивает, и это его первая осечка. Зато в других размерностях он попадает точно

В 1978 году Кабатянский и Левенштейн перенесли схему с контактного числа на плотность упаковки — перенос не автоматический и составляет содержание их работы. Результат: плотность не больше $2^{-(0{,}5990558\ldots+o(1))n}$, и сорок восемь лет этот показатель никто не улучшал

Через год та же техника дала не оценку, а точный ответ — снова для контактного числа, но в размерностях 8 и 24, где оно равно 240 и 196560. Здесь удалось то, что не удалось в размерности 3: подобранная функция даёт оценку сверху, решётки $E_8$ и Лича — пример снизу, и числа совпали. Результат независимо получили Левенштейн и Одлыжко со Слоаном в 1979 году, за тридцать семь лет до Вязовской

У критерия из второго раздела есть аналог для плотности упаковки, и роль разложения по многочленам Гегенбауэра играет в нём преобразование Фурье $\hat f$. Его выписали Кон и Элкис в 2003 году. Пусть $r>0$ и функция $f$ на $\mathbb{R}^n$ зависит только от расстояния до нуля. Если

$$f(0)=\hat f(0)>0,\qquad f(x)\le 0\ \text{ при } |x|\ge r,\qquad \hat f(y)\ge 0\ \text{ всюду,}$$

то плотность любой упаковки не больше объёма шара радиуса $r/2$. Оценка тем сильнее, чем меньше $r$

По численным данным в размерностях 8 и 24 такая оценка, судя по всему, точна. Но самой функции Кон и Элкис не построили, и задача свелась к одному вопросу: где её взять

Ответ нашла Марина Вязовская, и на поиски у неё ушло, по её словам, около двух месяцев. Работу она выложила 14 марта 2016 года одна и про все упаковки в размерности 8, а не только решётчатые. Через неделю вышла вторая статья, про размерность 24, — уже впятером, с Коном, Кумаром, Миллером и Радченко; там та же техника закрыла решётку Лича. Обе напечатали подряд, в одном томе Annals, а Вязовская получила за это Филдсовскую медаль

Восьмимерное доказательство с тех пор формализуют в Lean; последние шаги довела модель Gauss компании Math, Inc. — за пять дней

Её удалось взять из модулярных форм. Устройство самих форм выходит за пределы рассказа; работает здесь одно их свойство: интегральным преобразованием из них получаются собственные функции преобразования Фурье — такие $g$, что $\hat g=g$ или $\hat g=-g$. Для такой функции $\hat f=\pm f$, и условие на $\hat f$ превращается в условие на саму $f$: следить надо не за двумя функциями, а за одной

Именно здесь задача и стояла тринадцать лет: свойство есть у целого семейства функций, а нужна была одна конкретная, и её поиск оказался делом отдельной работы

В той же работе 2003 года Кон и Элкис улучшили верхние оценки в размерностях с 4 по 36, но в размерности 3 линейным методом не удалось ничего: лучшей осталась геометрическая оценка Мьюдера 1993 года, $0{,}7731$ против истинных $0{,}7405$. Речь только о бессилии метода: сам случай размерности 3 не открыт, ответ известен и получен иначе

В 1953 году Фейеш Тот показал, как свести гипотезу Кеплера к задаче конечной. Каждому шару приписывается число — его вклад, — зависящее только от того, как стоят ближайшие к нему соседи; подобрано оно так, что плотность всей упаковки не больше среднего вкладов. Тогда достаточно оценить число у одного шара при любом возможном окружении

Окружений континуум, но для оценки важны не точные координаты соседей, а только то, кто из них с кем соседствует. Близких соседей у шара ограниченное число, схем «кто с кем рядом» на них конечное число, и внутри одной схемы оценка одна и та же. Значит, неравенство надо проверить конечное число раз — и гипотеза Кеплера станет теоремой. Схем вышло очень много, и в 1953 году перебирать их было нечем

Программу выполнил Хейлс: в 1998 году объявил доказательство, последний случай закрыл его студент Фергюсон

Коллегия рецензентов работала четыре года и сообщила: уверена на 99 процентов, но сертифицировать полностью не может. Тогда доказательство стали проверять формально, в HOL Light и Isabelle: проект Flyspeck завершился 10 августа 2014 года. Шестнадцать лет от объявления до сертификата, и машина понадобилась не ради скорости, а потому что люди не смогли дочитать

Пакет из десяти результатов OpenAI, которые, по заявлению компании, получила модель Astra, открывается главой про асимптотику задачи Кона — Элкиса. Пусть $LP_d$ — самая сильная оценка плотности, какую вообще можно получить из критерия Кона — Элкиса в размерности $d$. Заявлено, что

$$LP_d^{1/d}\xrightarrow[d\to\infty]{}\sqrt{e/2\pi},\qquad \text{то есть}\quad \alpha^*=\tfrac12\log_2(2\pi/e)=0{,}6044\ldots$$

вместо показателя $0{,}5990558\ldots$ Кабатянского и Левенштейна — то есть заявлена более сильная оценка

Утверждение асимптотическое: к размерностям 8 и 24 оно не относится, там задача решена точно и метод Вязовской ни в какой предел не упирается

Рекорд здесь не главное: в той же главе заявлено и обратное неравенство — никакая допустимая функция Кона — Элкиса показателя лучше $0{,}6044$ не даёт. Если это верно, рекорд оказался и пределом метода: брать у такой функции больше нечего. Отсюда ничего не следует про верхние границы вообще: предел доказан для одного метода, а не для всех, и другим способом границу двигать по-прежнему можно

Независимой математической проверки на середину августа нет; есть Lean-репозиторий самой OpenAI с пометками «zero sorry» и «agent-reviewed». Что он удостоверяет и чего не удостоверяет — разные вещи:

• удостоверено: формальный терм имеет заявленный тип при заданных определениях и аксиомах;
• не удостоверено: что формулировка в анонсе совпадает с этой формальной теоремой и что определения описывают ту задачу, которую имеют в виду математики

Оценки снизу устроены иначе: из них следует, что упаковка нужной плотности существует, но не видно, как её построить. Первую доказал Главка в 1943 году усреднением по решёткам, четырьмя годами позже Роджерс добавил линейный множитель — плотность не меньше $c\,n\,2^{-n}$. Дальше десятилетиями улучшали только константу $c$: сверхлинейный множитель во всех размерностях сразу не давался никому

В 2023 году Кампос, Йенссен, Мишелен и Сахасрабудхе довели множитель до $n\log n$, но их упаковка не решётчатая. В апреле 2025-го Клартаг получил сразу $n^2$ и для решёток: в любой размерности существует центрально-симметричный эллипсоид $E$ объёма $c n^2$ без ненулевых точек решётки $\mathbb{Z}^n$ внутри. Отсюда до упаковки два шага

• Сжать вдвое. Сдвиги $E/2$ по точкам решётки не пересекаются: иначе разность двух сдвигов была бы разностью двух точек $E/2$, а она лежит в самом $E$ — тело выпукло и центрально-симметрично. Внутри $E$ нашлась бы ненулевая точка решётки, которой там нет. Объём при сжатии падает в $2^n$ раз, а на каждую точку $\mathbb{Z}^n$ приходится единичный объём: занятая доля и есть $c\,n^2 2^{-n}$
• Перейти к шарам. Линейное отображение, переводящее $E/2$ в шар, переводит решётку в решётку, непересекающиеся сдвиги — в непересекающиеся, а долю занятого объёма не меняет

Метод вероятностный. Эллипсоид без точек решётки внутри случайно меняют, понемногу увеличивая в объёме (запускают броуновское движение на пространстве эллипсоидов). Когда его граница доходит до точки решётки, дальше в эту сторону расти нельзя: на форму накладывается ещё одно ограничение, и свободы остаётся на единицу меньше. Форма центрально-симметричного эллипсоида задаётся $n(n+1)/2$ числами — столько же у него и степеней свободы, то есть порядка $n^2$, и ровно столько ограничений набирается, прежде чем расти станет некуда. Отсюда и множитель $n^2$; как из этого счёта получается сама оценка, и составляет содержание работы

Клартаг занимается геометрией выпуклых тел, а в теории решёток был новичком: на вход в область ушло несколько месяцев, на доказательство — пара недель. Его слова в Quanta: «Мне сорок семь, всю жизнь я хотел заниматься решётками; если не сделаю этого сейчас, то не сделаю никогда»

Если заявленное верно, сверху плотность не больше $2^{-(0{,}6044\ldots+o(1))n}$, снизу — не меньше $c\,n^2 2^{-n}$: разрыв между оценками примерно в $2^{0{,}4n}$ раз. Пять тысячных к показателю сверху и квадрат вместо линейного множителя снизу его не закрыли

Задачу полвека считают прикладной — коды, связь, криптография, — но ни одной теоремы за пределами теории упаковок, которая опиралась бы на новые оценки, пока не названо; про работу Клартага Quanta пишет «not immediately useful». Криптография на решётках держится на сложности задач о решётках, а не на плотности упаковок

Машина появилась в сюжете трижды и каждый раз в другой роли: Flyspeck дочитал за рецензентами, Gauss закрыл формализацию за людьми, которые доказательство уже знали, а за Astra заявлено утверждение, которого до неё не было, — и по существу его пока никто не разобрал