Всего за несколько месяцев работы новичок в мире упаковки сфер решил одну из самых больших открытых проблем.

В математике поиск оптимальных моделей никогда не заканчивается. Не является исключением и задача упаковки шаров — как максимально эффективно запихнуть шары в коробку (с большим числом измерений). Она привлекает математиков уже несколько столетий и имеет важные приложения в криптографии, дальней связи и многом другом.

Это обманчиво простая задача оборачивается чрезвычайно сложной. В начале XVII века физик Иоганн Кеплер показал, что, укладывая трёхмерные сферы так, как укладывают апельсины в продуктовом магазине, можно заполнить около 74% пространства. Он предположил, что это наилучшее возможное расположение. Но математикам потребовалось почти 400 лет, чтобы доказать это.

В пространствах более высоких измерений математики до сих пор не знают ответа. (За странным исключением размерностей 8 и 24.) За прошедшие годы они придумывали всё более удачные методы упаковки. Но эти улучшения были небольшими и относительно редкими.

Теперь, в короткой работе, опубликованной в Интернете в апреле, математик Боаз Клартаг превзошёл все предыдущие рекорды со значительным отрывом. Некоторые исследователи даже считают, что его результат может быть близок к оптимальному.

Будучи новичком в этой области исследований, Клартаг добился своего метода упаковки, который работает во всех произвольно высоких измерениях, реанимировав старую технику, от которой специалисты отказались несколько десятилетий назад. Работа затрагивает несколько давних дебатов о природе оптимальных упаковок в высоких измерениях. Должны ли они быть упорядоченными или неупорядоченными? И насколько плотными они могут быть?

«Это действительно удивительный прорыв», — говорит Гил Калай, математик из Еврейского университета в Иерусалиме. «Этот вопрос волновал математиков почти 100 лет».

Картинки-близнецы

В 1905 году математик Герман Минковский придумал интуитивный способ работы с упаковкой сфер. Начните с повторяющегося расположения точек в пространстве, т.н. решётки. Затем нарисуйте сферу вокруг каждой точки. Таким образом, проблема поиска оптимальной упаковки сферы в данном измерении фактически превращается в проблему поиска решётки, точки которой расположены как можно более эффективно. В двух измерениях, например, оптимальная решётка является «шестиугольной» и даёт упаковку, которая выглядит следующим образом:

Но в 1947 году математик по имени Клод Амброуз Роджерс предложил другой подход. Начните с любой решётки, сказал он, даже неоптимальной. Вместо того чтобы рисовать сферу вокруг каждой точки, нарисуйте вокруг одной точки продолговатую фигуру, называемую эллипсоидом, так, чтобы её поверхность касалась других точек решётки, но не выходила за них.

Роджерс придумал алгоритм, который использует этот эллипсоид в качестве отправной точки, чтобы затем построить плотную упаковку сфер. Вот как это работает:

Преимущество метода Роджерса заключалось в том, что для эффективной упаковки сферы не нужно было начинать с особенно эффективной решётки. Нужно было просто выбрать правильный эллипсоид. Но это вносило новое осложнение. В отличие от сферы, которая полностью определяется одним числом — её радиусом, эллипсоид определяется несколькими осями разной длины. Чем выше размерность, тем больше направлений, в которых можно растянуть эллипсоид, и тем больше вариантов того, как может выглядеть начальный эллипсоид.

"В более высоких измерениях сложно придумать, как правильно его рисовать. У вас появляется слишком много свободы", — говорит Клартаг.

В конце концов математики вернулись к подходу Минковского, решив сосредоточиться на поиске правильных решёток. Они стали больше специализироваться на теории решёток и отошли от геометрии Роджерса.

Эта стратегия привела к улучшениям в упаковке высокоразмерных сфер. Но по большей части они улучшили упаковку Роджерса лишь на относительно небольшую величину. Математики все ещё надеялись совершить больший скачок.

В течение десятилетий у них ничего не получалось. Чтобы положить конец застою, нужен был человек со стороны.

Взгляд со стороны

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

В ноябре прошлого года, завершив крупный проект в своей обычной области исследований, он заметил, что его календарь нехарактерно чист. Я подумал: «Мне 47 лет, всю жизнь я хотел изучать решётки, и если я не сделаю этого сейчас, то этого никогда не произойдёт», — сказал он. Он попросил своего друга, Барака Вайса из Тель-Авивского университета, стать его наставником в этом новом начинании.

Вайс организовал небольшой семинар, в котором Клартаг и ещё несколько человек изучали соответствующую литературу. Домашнее задание Клартага включало внимательное прочтение рецептов Минковского и Роджерса по упаковке сфер.

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

Он начал с хорошо известного ему метода увеличения и уменьшения границ эллипсоида вдоль каждой из его осей в рамках случайного процесса. Всякий раз, когда граница расширялась настолько, что касалась новой точки в решётке, он замораживал рост эллипсоида в этом направлении. Это гарантировало, что точка никогда не попадёт внутрь эллипсоида. Но форма продолжала раздуваться во всех остальных направлениях, пока не сталкивалась с другой точкой. Таким образом, эллипсоид менял форму отрывистыми, почти нерешительными движениями, постепенно «исследуя» пространство вокруг себя. В конце концов, граница задевала достаточное количество точек, чтобы эллипсоид не мог расти дальше.

Со временем, в среднем, техника приводила к тому, что эллипсоид увеличивался в объёме. Но увеличился ли он настолько, чтобы превзойти интуитивный эллипсоид Роджерса?

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

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

Он немедленно сообщил Вайсу о своём результате. «Давайте встретимся на следующей неделе, и я расскажу вам, в чем была моя ошибка», — сказал Клартаг своему наставнику. Но к тому времени Клартаг стал ещё более уверенным в своём доказательстве.

Приближение к истине

Доказательство подтвердилось. Новый начальный эллипсоид Клартага, превращённый в упаковку сферы, дал самое значительное улучшение эффективности упаковки со времён работы Роджерса 1947 года. Для выбранной размерности d Клартаг может упаковать в d раз больше сфер, чем это удавалось в большинстве предыдущих результатов. То есть в 100-мерном пространстве его метод упаковывает примерно в 100 раз больше сфер, а в миллионно-мерном — примерно в 1 миллион раз больше.

Клартаг взломал центральную задачу в мире решёток и упаковки сфер всего лишь после нескольких месяцев изучения и нескольких недель написания доказательств. "Это кажется почти несправедливым, — говорит он. Но так часто бывает в математике: Иногда все, что нужно для решения сложной проблемы, — это несколько свежих идей, и выход за пределы какой-то области может принести пользу". Знакомство Клартага с выпуклой геометрией, которая обычно является отдельной областью изучения, оказалось как раз тем, что требовалось для решения проблемы. «Эта идея пришла мне в голову в связи с моей работой», — сказал он. «Для меня было очевидно, что это то, что я могу попробовать».

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

Теперь работа Клартага подтверждает мысль о том, что порядок и симметрия, возможно, и будут наиболее подходящим путём.

Более того, ведутся споры о том, насколько плотной может быть упаковка сфер. Некоторые математики считают, что упаковка Клартага лишь на волосок меньше оптимальной — практически настолько, насколько это возможно. Другие считают, что ещё есть куда стремиться. «Я понятия не имею, чему верить на данный момент», — говорит Маркус Мишелен, математик из Иллинойского университета в Чикаго. «Я думаю, что все реальности все ещё в игре».

Ответ имеет значение для потенциальных приложений к криптографии и коммуникациям. Поэтому результат Клартага, хотя и не пригодившийся моментально на практике, вызвал некоторый предварительный энтузиазм. «Эта проблема для инженеров весьма важна, а прогресса в ней практически нет», — говорит Ор Ордентлих, теоретик информации из Еврейского университета. «Так что это нас воодушевляет».

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

«Моя цель — сделать эти две области более связанными, чем они есть сейчас», — добавил он. «Таков был мой план, и я по-прежнему хочу его реализовать».