В 1694 году в Кембриджском университете Исаак Ньютон и астроном Дэвид Грегори завели разговор о природе звёзд. В ходе беседы они наткнулись на математическую загадку, которая оставалась нерешённой на протяжении веков. Детали их обсуждения сохранились плохо и, возможно, частично вымышлены, но суть сводилась к тому, как звёзды разного размера вращаются вокруг центрального светила. Этот разговор вдохновил на более общий вопрос: если есть центральная сфера, сколько одинаковых сфер можно разместить вокруг неё так, чтобы они касались её, но не пересекались друг с другом?
В трёхмерном пространстве легко расположить 12 сфер вокруг центральной, каждая из которых будет касаться её в одной точке. Однако при таком расположении между сферами остаются зазоры. Возникает вопрос: можно ли добавить 13-ю сферу, чтобы она тоже касалась центральной? Грегори считал, что это возможно, а Ньютон был уверен, что нет.
Эта задача, известная как проблема «поцелуев» (отсылка к касанию шаров, как в бильярде), оказалась важной для многих областей, включая изучение атомных структур и создание кодов с исправлением ошибок. Однако её решение было крайне сложным. Лишь в 1952 году математики смогли доказать, что Ньютон был прав: в трёхмерном пространстве максимальное число сфер, которые могут касаться центральной, равно 12.
Но задачу о поцелуе можно задать для сфер любого размера. В двух измерениях ответ очевиден: положите монетку на стол, и вы увидите, что если вы расположите вокруг неё ещё шесть монеток, они плотно прилегают друг к другу, образуя узор, похожий на ромашку.
В более высоких размерностях задача о «поцелуях» становится значительно сложнее. Она была решена для четырёхмерного, восьмимерного и двадцатичетырёхмерного пространств, где математикам удалось найти оптимальные способы размещения сфер в идеально симметричных решётчатых структурах. Однако для всех остальных размерностей, где между сферами остаётся больше свободного пространства, проблема до сих пор остаётся нерешённой. Вместо точных ответов математики предлагают оценки, вычисляя верхние и нижние границы числа «поцелуев», которые часто сильно различаются. В таких случаях вопрос уже не в том, можно ли добавить одну дополнительную сферу, а в том, можно ли добавить сотни, тысячи или даже миллионы.
Для улучшения этих оценок математики обычно опираются на интуицию, которая помогла им найти решения в размерностях 8 и 24: они ищут способы расположить сферы как можно более симметрично. Однако существует вероятность, что наилучшие конфигурации могут оказаться гораздо менее упорядоченными. Как отметила Габриэле Небе из Рейнско-Вестфальского технического университета Ахена, «могут существовать структуры без какой-либо симметрии, и нет хорошего способа их найти».
Весной 2022 года студентка Массачусетского технологического института Анци Ли решила исследовать более необычные структуры. Работая над учебным проектом, она предложила простую, но эффективную идею, которая позволила ей и её профессору Генри Кону улучшить оценки числа «поцелуев» в сложном диапазоне размерностей — от 17 до 21. Это стало первым значительным прогрессом в этой области с 1960-х годов и показало, что иногда для решения задачи нужно отойти от традиционных подходов и добавить больше «хаоса» в возможные решения.
Олег Мусин из Техасского университета в Рио-Гранде-Вэлли, который в 2003 году доказал оптимальное число «поцелуев» в четырёхмерном пространстве, отметил, что «обычно математики работают с симметричными решётками, но подход Ли и Кона предлагает нечто совершенно иное».
Их работа стала частью серии недавних достижений в задаче упаковки сфер, которые стали возможны благодаря тому, что математики начали отходить от общепринятых методов. Как сказал Кон, «ситуация с проблемой поцелуев застопорилась не потому, что мы приблизились к истине, а потому, что мы просто застряли». Чтобы продвинуться вперёд, им пришлось нарушить несколько негласных правил и взглянуть на задачу под новым углом.
Кодирование и поцелуи
С середины XX века математики начали применять методы теории информации и кодов с исправлением ошибок для решения задач, связанных с упаковкой сфер. Эти методы оказались неожиданно полезными для продвижения в проблеме «поцелуев».
Код с исправлением ошибок — это способ передачи сообщения, который позволяет получателю восстановить исходную информацию, даже если часть данных была искажена или потеряна в процессе передачи. Такой код состоит из набора «кодовых слов» — своеобразного словаря возможных сообщений. Получатель использует этот словарь как ключ для расшифровки и исправления ошибок. Однако кодовые слова должны быть тщательно подобраны: они должны быть достаточно различимыми, чтобы получатель мог точно определить, какое из них использовать для восстановления исходного сообщения.
Математики часто представляют задачу кодирования в виде сфер. Каждое кодовое слово можно представить как точку в центре сферы в многомерном пространстве. Если сообщение с ошибками (представленное как точка) попадает внутрь такой сферы, то кодовое слово в её центре считается правильным сообщением. Важно, чтобы сферы не пересекались — иначе одно и то же сообщение с ошибками может быть интерпретировано как несколько разных кодовых слов. Однако сферы не должны быть и слишком далеко друг от друга, так как плотная упаковка сфер позволяет передавать информацию более эффективно.
Улучшение кодов приводит к улучшению упаковки сфер, и наоборот. Например, в 1967 году математик Джон Лич разработал очень эффективный код, который позже использовался НАСА для связи с зондами «Вояджер». На основе этого кода он построил решётку точек, которая теперь называется решёткой Лича. Пятьдесят лет спустя Генри Кон и другие математики доказали, что эта решётка позволяет максимально плотно упаковать сферы в 24-мерном пространстве. Решётка Лича также обеспечивает оптимальное решение задачи «поцелуев»: каждая сфера в ней касается 196 560 соседних сфер. Как сказал Кон, «решётка Лича — это чудо математики, где всё идеально сочетается друг с другом».
Кроме того, решётка Лича помогла математикам получить наилучшие оценки для чисел «поцелуев» в размерностях от 17 до 23. Они использовали срезы решётки, чтобы перейти к меньшим размерностям, подобно тому, как можно разрезать трёхмерную сферу, чтобы получить двумерный круг.
Однако это также означало, что решётка Лича «отбрасывала огромную тень» на проблему «поцелуев» в этих размерностях, как отметил Кон. Несмотря на все усилия, математики не смогли найти структуру, которая давала бы более точные оценки, хотя и подозревали, что использование фрагментов решётки Лича — не самый лучший способ найти оптимальное решение.
Новый подход
Когда Анци Ли начала работать над своим проектом в 2022 году, она изначально не планировала искать новый подход. Сначала Генри Кон предложил ей сосредоточиться на задаче о «поцелуях» в размерностях выше 24. В этих случаях текущие оценки чисел «поцелуев» были гораздо менее точными, и их улучшение часто сводилось к техническим вычислительным усовершенствованиям, а не к поиску принципиально новых идей. Кон знал, что другие студенты уже добились прогресса в таких многомерных задачах с помощью компьютерных методов, и считал, что Ли сможет сделать то же самое.
Однако работа её разочаровала. «У меня было ужасное чувство, что у меня связаны руки, — сказала она. — Это было невозможно представить». Вместо того чтобы сдаться, она решила действовать более решительно.
Ли сосредоточилась на размерностях с 17 по 23. Кон вспоминал, что сказал ей: «Ты всё равно можешь получить пятёрку, если изучишь возможные улучшения, но ничего существенного не выйдет». Если бы она была его аспиранткой, он бы посоветовал ей выбрать другую тему, так как работа над чем-то бесперспективным могла негативно сказаться на её карьере. Однако результат её усилий, как позже отметил Кон, «оказался гораздо более захватывающим».
Ли начала с 16-го измерения, где наилучшая схема для задачи «поцелуев» была найдена в «решётке Барнса-Уолла». Эта решётка была открыта в 1950-х годах с использованием изящного кода с исправлением ошибок. (Позже выяснилось, что она является частью решётки Лича, которая была открыта только через десять лет.) Код в решётке Барнса-Уолла состоит всего из двух типов точек, каждая из которых соответствует определённому шаблону координат.
То, как определяются эти точки в решётке Барнса-Уолла, приводит к интересному эффекту: в этой решётке (и во всех многомерных срезах решётки Лича) наиболее распространённый тип точек, или центров сфер, всегда имеет чётное количество знаков «минус» в своих координатах. Это обеспечивает достаточное расстояние между точками и создаёт симметричную структуру, с которой удобно работать.
Однако Ли задалась вопросом: что, если использовать точки с нечётным количеством знаков «минус»? Она предположила, что, если действовать осторожно, это не обязательно приведёт к пересечению сфер. Насколько ей было известно, никто раньше не пробовал такой подход. «Не думаю, что кто-то из нас всерьёз считал, что это имеет значение», — сказал Кон. Но Ли подозревала, что, изменив таким образом некоторые точки в решётке, она сможет слегка исказить её структуру, чтобы вместить больше сфер.
Когда она построила свою «странную» версию решётки Барнса-Уолла в 16-мерном пространстве, оказалось, что в ней не осталось места для дополнительных сфер, но и хуже она не стала. Однако, когда Ли склеила копии этой решётки в слои, чтобы получить 17-мерную структуру, в ней появились пробелы, в которые можно было добавить новые точки. Эти «дыры» позволяли разместить дополнительные сферы, что стало ясно после расчёта расстояний между существующими сферами. Сначала Ли не могла поверить своим результатам. Она чувствовала скорее неловкость, чем радость. «Я помню, как говорила своим друзьям, что, наверное, неправильно посчитала в уме», — вспоминала она.
Поначалу Кон разделял её скептицизм. В таких расчётах легко допустить ошибку, особенно если слишком увлечься идеей. Поэтому они решили проверить её новую расстановку точек с помощью компьютера. Результаты подтвердили её расчёты: все сферы встали на свои места, и структура работала. Это стало важным шагом вперёд.
Тем летом Ли начала стажировку у Кона в Microsoft Research, где они вместе продолжили дорабатывать коды исправления ошибок, которые использовали для добавления новых сфер в «странную» 17-мерную структуру Ли. Их совместная работа была кропотливой и требовала тщательной проверки каждого шага, но результаты оказались впечатляющими. В итоге им удалось добавить 384 новые сферы к оценке, полученной Личем в 1967 году, увеличив нижнюю границу числа «поцелуев» в 17-мерном пространстве до 5730.
После успеха в 17-мерном пространстве Ли и Кон применили аналогичные методы для улучшения оценок числа «поцелуев» в размерностях с 18 по 21. Однако в размерностях 22 и 23 их стратегия перестала работать. Казалось, что возможности изменения знаков в координатах точек были исчерпаны, и дальнейшее улучшение оценок требовало новых идей.
Новые конфигурации, которые они получили, скорее всего, не являются оптимальными. Например, в 17-мерном пространстве предполагаемая верхняя граница числа «поцелуев» составляет 10 978. Хотя эта оценка считается грубой и, вероятно, завышенной, она указывает на то, что между текущей нижней границей (5730) и верхней границей остаётся значительный разрыв, который можно попытаться сократить.
Однако для математиков наибольший интерес представляет не столько само улучшение оценок, сколько методы, которые использовали Ли и Кон. Их новые структуры сильно отличаются от традиционных высокосимметричных решёток, вдохновлённых решёткой Лича. Вместо этого они создали более нерегулярные, «странные» конфигурации, используя методы кодирования, которые позволили им добавлять сферы в ранее недоступные места.
Как это работает?
Непонятно, почему изменение знаков в координатах точек создаёт достаточно места для добавления большего количества сфер. Это просто работает. «Меня это до сих пор нервирует», — сказал Кон. Однако их работа демонстрирует, как «кажущееся незначительным изменение может открывать или закрывать возможности», — добавил он. В этом смысле она показывает, как мало математики на самом деле знают о задаче «поцелуев».
При создании новых кодов с исправлением ошибок и упаковок сфер математики обычно полагаются на симметрию. Именно так поступил Лич. Это упрощает процесс построения и делает его более интуитивным. Однако такой подход может ограничивать возможности, затрудняя переход от красивых симметричных решений к другим структурам, которые могут быть более хаотичными или включать менее интуитивные формы симметрии.
«Возможно, мы не приближаемся к истине, потому что у неё просто нет доступного человеку описания», — сказал Кон.
Несколько недавних результатов подтверждают перспективность этих менее доступных возможностей. За последние пару лет математики придумали новые интересные конструкции в размерностях 5, 10 и 11, изменив или нарушив обычные правила симметрии. Кон был особенно поражён работой Ференца Шёллёси, венгерского математика, который намеренно начал с неоптимального расположения сфер в четырёхмерном пространстве и построил на его основе лучшую из существующих оценок в пятимерном пространстве.
На протяжении десятилетий существовало две структуры, которые давали такую оценку; большинство математиков считали, что других быть не может. И вдруг Шёллёси предложил третью (позже он узнал, что другая пара исследователей также открыла эту конфигурацию, но они не осознали её значимость).
«Это доказало, что вас могут застать врасплох», — сказал Кон, который затем вдохновился на совместную работу с другим своим студентом, чтобы найти четвёртую. Каждая необычная структура, которую они обнаруживают, даёт им «маленькие намёки и подсказки о том, какой может быть истина», — добавил он. «Проблема поцелуев по-прежнему полна загадок».
Подборка препринтов с Arxiv.org по "проблеме поцелуев" - здесь.
Всё это и много другое — ТГ «Математика не для всех»
