Один сломал, другой потерял

Некоторое время назад на сайте препринтов arXiv.org появилось сразу две работы, посвященные задаче о плотнейшей упаковке шаров в пространствах размерности 8 и 24. До настоящего момента аналогичные результаты были известны только для размерностей 1, 2 и 3 (причем тут не все так просто, но об этом ниже). Прорыв — а речь идет про настоящий революционный прорыв — стал возможен благодаря работам Марины Вязовской, математика украинского происхождения, которая сейчас работает в Германии. Мы расскажем историю этого достижения в десяти коротких сюжетах.

1.

В XVI веке в Англии проживал известный придворный деятель и поэт сэр Уолтер Рэли. Знаменит он был, в первую очередь тем, что, однажды, бросил перед королевой в лужу свой дорогой плащ, чтобы Ее Величество на испачкало ног. Но нам он интересен не поэтому.
Была у сэра Уолтера Рэли страсть — очень он любил грабить испанские суда и искать Эльдорадо. И вот однажды увидел Рэли на корабле кучу сложенных ядер. И подумал (случалось такое с британскими придворными), мол, было бы неплохо, если бы можно было бы узнать, сколько ядер в куче, не пересчитывая их. Польза от такого знания, особенно если тебе нравится грабить испанский флот, очевидна.

Сам Рэли был в математике не очень, поэтому он задал эту задачку своему помощнику Томасу Хэрриоту. Тот, в свою очередь, был в математике силен (Хэрриот, кстати, является изобретателем знаков «>» и «<» для сравнения численных величин), поэтому довольно быстро решил эту задачу. Но Хэрриот был хорошим математиком, поэтому он задался вопросом: а как лучше всего укладывать ядра? Сам он немного подумал, но решить задачу не смог.

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

), почему зерна граната имеют форму додекаэдров (пусть и неправильных) и почему, наконец, снежинки имеют форму шестиугольников.

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

Третий же вопрос породил гипотезу о том, что

гексагональная плотная упаковка

(она на картинке ниже) является плотнейшей (что значит это в математическом смысле тоже ниже). Разумеется, на Хэрриота Кеплер сослаться не посчитал нужным. Поэтому это утверждение получило название гипотезы Кеплера.

 — он же принцип Арнольда — в действии.

Да, через 7 лет после выхода этой брошюрки сэру Уолтеру Рэли отрубили голову. Впрочем, с задачей о плотной упаковке это никак не было связано.

2.

По современным меркам задача, которую решал Хэрриот, была несложной. Поэтому разберем ее подробнее. А заодно и лучше поймем, как устроена гексагональная плотная упаковка.
Итак, главное условие, чтобы куча ядер не раскатилась во время качки. Итак, выкладываем ядра в ряд на палубе. В следующий ряд кладем ядра так, чтобы шары размещались в щелях между сферами первого ряда. Если в первом ряду n шаров, то во втором n — 1 (потому что щелей между шарами на единицу меньше, чем самих шаров). Следующий ряд будет еще на единицу меньше ядер. И так далее, пока мы не получим вот такой треугольник (если смотреть на раскладку сверху):

Те, кто помнит, что такое арифметическая прогрессия, легко сосчитают, что, если в первом ряду было n шаров, то всего в таком треугольнике n(n + 1)/2 шаров. Если смотреть сверху, то между шарами есть удобные выемки. Туда и будем складывать второй слой шаров. Получится треугольник, организованный как первый, только у которого на единицу меньше шаров в стороне. Значит, мы положили в кучу еще n(n — 1)/2 шара.

Продолжим выкладывать слои до тех пор, пока не получим слой из одного шара. Получили треугольную пирамиду из ядер. Чтобы узнать, сколько в ней всего ядер, нужно сложить количества ядер в каждом слое. Если первый слой был со стороной n, то получим n слоев, которые в сумме дадут n(n + 1)(n + 2)/6. Пытливый читатель заметит, что это в точности биномиальный коэффициент C

. Это комбинаторное совпадение тут неспроста, но углубляться мы в него не будем.

Кстати, помимо этой задачи Хэрриот смог определить, какую примерно долю занимают ядра в достаточно большом контейнере, если принять форму последнего за куб. Оказалось, что доля составляет π/(3

) ≈ 0,74048.

3.

Что значит слово плотнейшая в формулировке задачи? Рэли, Хэрриот, да и сам Кеплер не давали на это точного ответа. Подразумевалась плотнейшая в каком-то разумном смысле. Однако, для математики такая формулировка не подходит. Ее надо уточнить.
Давайте сначала спустимся на размерность ниже и посмотрим, как все устроено на плоскости. Для двумерного случая задача превращается в такую: пусть на плоскости задан бесконечный набор непересекающихся по внутренней части (но, возможно, соприкасющихся — то есть имеющих общую точку на границе) кругов. Нарисуем квадрат. Посчитаем сумму площадей попавших внутрь квадрата кусков кругов. Возьмем отношение этой суммы к площади квадрата, и будем увеличивать сторону квадрата, смотря за изменением соотношения.
Мы получаем функцию f(a), где a — сторона квадрата. Если нам повезло, то эта функция с ростом аргумента будет приближаться асимптотически к некоторому числу. Это число называется плотностью данной упаковки. Важно, что сама функция в какой-то момент может давать значение большее плотности. Действительно, если квадрат маленький, то целиком помещается в круге и определенное отношение равно 1. Но нас интересует плотность в среднем, то есть, говоря неформально «для квадрата с достаточно большой стороной».
Среди всех таких плотностей можно найти максимальную. Именно она, а также упаковка, ее реализующая, и будет называться плотнейшей.

«Плотнейшая упаковка не обязательно единственная (в асимптотическом смысле). Плотнейших упаковок в 3х-мерном пространстве — бесконечно много, и это знал еще Кеплер,» — говорит Олег Мусин из Техасского университета в Браунсвилле. 
После того, как мы определили понятие плотнейшая упаковка, легко понять, что такое определение легко распространить на пространство произвольной размерности n. Действительно, заменим круги на шары соответствующей размерности, то есть множества точек, расстояние от которых до фиксированной (называемой центром) не превосходит некоторой величины, называемой радиусом шара. Снова расположим их так, чтобы любые два в лучшем случае касались, в худшем — вообще не имели общих точек. Определим такую же, как и в предыдущем случае, функцию, взяв объем n-мерного куба и сумму объемов соответствующих n-мерных шаров.

4.

Итак, мы поняли, что гипотеза Кеплера — это задача о плотнейшей упаковке трехмерных шаров в трехмерном пространстве. А что там с плоскостью (раз уж мы с нее начали)? Или даже с прямой? С прямой все просто: шар на прямой — это отрезок. Прямую можно полностью покрыть одинаковыми отрезками, пересекающимися по концам. При таком покрытии функция f(a) постоянна и равна 1.
На плоскости все оказалось несколько сложнее. Итак, пусть для начала на плоскости задано множество точек. Мы говорим, что это множество точек образует решетку, если можно найти пару векторов v и w таких, что все точки получаются как N*v + M*w, где N и М — целые числа. Аналогичным образом решетку можно определить в пространстве сколь угодно большой размерности — просто потребуется больше векторов.
Решетки важны по многим причинам (например, именно в узлах решетки предпочитают располагаться атомы, когда речь идет о твердых материалах), но для математиков они хороши тем, что очень удобны для работы. Поэтому из всех упаковок отдельно выделяют класс, в которых центры шаров располагаются в узлах решетки. Если ограничиться таким случаем, то на плоскости существует всего пять типов решеток. Плотнейшую упаковку из них дает так, в которой точки расставлены в вершинах правильных шестиугольников — как соты у пчел или атомы у графена. Этот факт был доказан Лагранжем в 1773 году. Точнее так: Лагранж не интересовался плотными упаковками, а интересовался квадратичными формами. Уже в XX выяснилось, что из его результатов про формы вытекает результат о плотности упаковки для двумерных решеток.
«В 1831 году Людвиг Зибер написал книгу о тернарных квадратичных формах. В этой книге была выдвинута гипотеза, которая эквивалентна гипотезе Кеплера для решетчатых упаковок. Сам Зибер сумел доказать только слабую форму своей гипотезы и проверить ее для большого числа примеров. Рецензию на эту книгу написал великий Карл Фридрих Гаусс. В этой рецензии Гаусс приводит воистину удивительное доказательство, которое уместилось в 40 строк. Это, как мы сейчас говорим, „олимпиадное“ доказательство доступно для понимания школьнику старших классов. Многие математики пытались найти скрытый смысл в доказательстве Гаусса, но пока никто не преуспел,» — говорит Олег Мусин.
Что будет, однако, если отказаться от условия сетчатости? Здесь все оказывается несколько сложнее. Первую полноценную попытку разобраться с этим случаем предпринял норвежский математик Аксель Туэ. Если заглянуть на страничку, посвященную Туэ в Википедии, то ничего про плотную упаковку мы там не найдем. Оно и понятно — Туэ опубликовал две работы, больше напоминающие эссе, чем нормальные математические работы, в которых, как ему казалось, полностью решил задачу о плотной упаковке. Проблема была только в том, что никого, кроме самого Туэ, его рассуждения не убедили.

Окончательно задачу решил венгерский математик Ласло Фейеш Тот в 1940 году. Оказалось, кстати, что расположение окружностей на плоскости, реализующее наиболее плотную упаковку единственно.

5.

С задачей о плотной упаковке тесно связана задача о контактном числе. Давайте снова рассмотрим круг на плоскости. Сколько вокруг него можно расположить кругов такого же радиуса, чтобы все они касались центрального? Ответ шесть. Действительно, посмотрим на два соседних круга, соприкасающихся с нашим центральным. Посмотрим на расстояние от центра центрального круга до центров этих двух. Оно равно 2R, где R — радиус круга. Расстояние между центрами соседних кругов не превосходит 2R. Вычисляя угол при центре центрального круга по теореме косинусов получаем, что он не меньше 60 градусов. Сумма всех центральных углов должна давать 360 градусов, значит таких углов может быть не больше 6. А расположение кругов с шестью углами мы знаем.
Полученное число называется контактным числом плоскости. Аналогичный вопрос можно задать для пространств любой размерности. Пусть простота решения на плоскости не вводит читателя в заблуждение — задача о контактных числах если и проще задачи о плотной упаковке, то не сильно. Но результатов в этом направлении действительно получено больше.

Для трехмерного пространства контактное число стало предметом публичного спора между самим Исааком Ньютоном и Джеймсом Грегори в 1694 году. Первый считал, что контактное число должно быть 12, а второй — что 13. Штука в том, что 12 шаров вокруг центрального расположить несложно — центры таких шаров лежат в вершинах правильного икосаэдра (их у него как раз 12 штук). Но эти шары не соприкасаются! На первый взгляд кажется, что их можно подвинуть так, чтобы пролез еще един, 13-ый шар. Это почти правда: если шары чуть-чуть раздвинуть, сделав расстояние между их центрами и центром центрального не 

а всего

то 13 шаров уже поместятся. Но для касающихся шаров Грегори был неправ — этот факт доказали ван дер Ваарден и Шютте в 1953 году.

Для размерности 4 эта задача была решена Олегом Мусиным в 2003 году. Там контактное число оказалось равно 24.

6.

Помимо этих размерностей 1, 2, 3 и 4 контактные числа известны еще в размерностях 8 и 24. Почему именно эти размерности? Дело в том, что для них существуют очень интересные решетки, называемые E8 и решетка Лича.
Итак, мы уже выяснили, что такое решетка. Важной характеристикой решетки для математики является ее симметричность. Под симметричностью понимается, конечно, не субъективные ощущения (да и кто эту решетку в размерности, например, четыре и представит?), а количество различных типов движений пространства, которые эту решетку в себя переводят. Поясним на примере.
Возьмем ту самую гексагональную решетку, которая реализует плотнейшую упаковку на плоскости. Легко понять, что решетка переходит в себя, если сдвигать ее на вектора v и w, которые были в определении. Но, помимо этого, решетку можно вращать вокруг центра шестиугольника. И вращений таких целых 6 штук: на 0, 60, 120, 180, 240, 300 градусов. Кроме этого решетку можно отображать симметрично относительно любой оси симметрии составного шестиугольника. Небольшое упражнения показывает, что, не считая сдвигов, мы получаем 12 преобразований. В других решетках таких преобразований меньше, поэтому мы говорим, что они менее симметричные.
Так вот, E8 и решетка Лича — это невероятно симметричные решетки. E8 располагается в 8-мерном пространстве. Эту решетку в 1877 году придумали российские математики Коркин и Золотарев. Она состоит из векторов, все координаты которых целые числа, а их сумма — четная. У такой решетки за вычетом сдвигов 696 729 600 преобразований. Решетка Лича существует в двацатичетырехмерном пространстве. Она состоит из векторов с целыми координатами и условием — сумма координат минус любая координата, помноженная на 4, делится на 8. У нее просто колоссальное количество симметрий — 8 315 553 613 086 720 000 штук.
Так вот, в 8-мерном и 24-мерном пространстве шары, расположенные в вершинах этих самых решеток, касаются 240 и 19650 шаров соответственно. Удивительно, но именно это и есть контактные числа (смотри пункт 5) для пространств соответствующей размерности.

7.

Теперь вернемся к трехмерному случаю и гипотезе Кеплера (той самой, о которой мы говорили в самом начале). Эта задача оказалась в разы сложнее своих предшественников.
Начнем с того, что существует бесконечно много упаковок с той же плотностью, что и гексагональная плотная. Мы начинали ее выкладывать, стартуя с шаров, разложенных в узлах гексагональной решетки. Но можно поступить по-другому: например, на первом уровне сложить шары квадратом, то есть так, чтобы вершины шаров располагались в узлах уже квадратной решетки. В таком случае каждый шар касается четырех соседей. Второй слой, как и в случае с гексагональной, будем класть сверху в щели между шарами первого слоя. Такая упаковка называется гранецентрированной кубической упаковкой. Это, кстати, единственная плотнейшая решетчатая упаковка в пространстве.
На первый взгляд, кажется, что эта упаковка должна быть хуже, ведь щели между четырьмя шарами в первом слое сильно больше (по ощущениям), чем щели в гексагональной плотной упаковке. Но, когда мы кладем второй ряд, шары — именно из-за того, что щели больше — погружаются глубже. В результате, как оказывается, плотность оказывается такой же как и раньше. На самом деле, конечно, трюк в том, что такая упаковка получается, если на гексагональнаую посмотреть под другим углом.
Получается, что в трехмерном пространстве нет таких прекрасных уникальных решеток, как, например, гексагональная на плоскости или E8 в 8-мерном пространстве. На первый взгляд, совершенно непонятно, как как искать плотнейшую упаковку в трехмерном пространстве.

8.

Решение гипотезы Кеплера рождалось в несколько этапов.
Сначала Фейеш Тот, тот самый венгр, который решил задачу о плотной упаковке не плоскости, высказал такую вот гипотезу: для того, чтобы понять, плотнейшая упаковка или нет, достаточно рассматривать конечные кластеры шаров. Как мы выяснили, в отличие от плоскости, если центрального шара касается 12 соседей, то между ними есть щели. Поэтому Фейеш Тот предложил изучать кластеры, состоящие из центрального шара, его соседей, и соседей соседей.

Штука в том, что это предположение было сделано в 60-е году прошлого века. А задача о минимизации объема такого кластера — это по сути нелинейная оптимизационная задача на функцию из примерно 150 переменных (у каждого шара есть центр, он задается тремя координатами). Грубо говоря, у такой функции нужно найти минимум при некоторых дополнительных условиях. С одной стороны задача стала конечной, но с другой — совершенно неподъемной с вычислительной точки зрения для человека. Но Фейеш Тот не расстроился и заявил, что очень скоро нужной вычислительной мощностью будут обладать компьютеры. Они-то и помогут.
Гипотеза Фейеша Тота очень понравилась математикам и они начали активно работать в этом направлении. К началу 90-х годов оценки на максимальную плотность упаковки шаров в трехмерном пространстве постепенно снижались. Идея была в том, что в какой-то момент оценка окажется равной плотности гранецентрированной кубической упаковки и, значит, гипотеза Кеплера будет доказана. В это время математик Томас Хейлз опубликовал свои первые работы по упаковке. Для работы он выбрал объект, называемый звездами Делоне (в честь советского математика Бориса Делоне). Это был смелый шаг — в тот момент эффективность таких объектов для изучения задачи об упаковке была сомнительной.
Всего через 8 лет упорного труда, в 1998 году, Хейлз завершил доказательство гипотезы Кеплера. Он свел доказательство к конечному комбинаторному перебору разных структур типа звезд Делоне. Для каждой такой комбинаторной структуры необходимо было максимизировать плотность. Так как компьютер работает нормально только с целыми числами (просто потому что в математике числа — это чаще всего бесконечные дроби), то для каждого случае Делоне автоматически строил приближение сверху с помощью символьных рациональных вычислений (рациональные числа, ведь, если не переводить их в десятичные дроби, просто пара целых). При таком приближении он получал оценку на максимум плотности сверху. В результате все оценки оказались меньше той, которую давала гранецентрированная кубическая упаковка.
Многих математиков, правда, смутила ситуация, в которой для построения приближения строился компьютер. Чтобы доказать, что в компьютерной части доказательства у него нет ошибок, Хейлз занялся формализацией и проверкой, правда, тоже с помощью компьютера. Эта работа, над которой работала довольно большая международная группа, была завершена в августе 2014 года. В доказательстве ошибок найдено не было.

9.

Доказательства для размерности 8 и 24 не требуют компьютера и, отчасти, проще. Некоторое время назад для оценки максимальной плотности упаковок в этих размерностях были получены очень хорошие оценки. Это сделали математики Кон и Элкиес в 2003 году. Кстати, эту оценку (ее еще называют границу Кона — Элкиеса) за пару лет до самих Кона и Элкиеса нашел российский математик Дмитрий Горбачев из Тулы. Однако, он опубликовал эту работу на русском и в тульском журнале. Кон и Элкиес об этой работе не знали, а когда им сказали, то они, кстати, на нее сослались.

«Граница Кона — Элкиеса появилась на основе работ Жан Фредерика Дельсарта и наших замечательных математиков Григория Кабатянского и Владимира Левенштейна. Асимптотическая (по размерности пространства) оценка плотности упаковок шаров в n-мерном пространстве, полученная Кабатянским и Левенштейна, „держится“ с 1978 года. Кстати, это Левенштейн и независимо американцы Одлыжко и Слоэн решили задачу контактных чисел в размерности 8 и 24 в 1979 году. Они напрямую использовали метод Дельсарта — Кабатянского — Левенштейна» — говорит Олег Мусин.

Оценки Кона и Элкиеса, на самом деле, верны для всех упаковок, но вот в размерности 8 и 24 они дают очень хорошее приближение. Например, полученная математиками оценка всего примерно на 0,0001 процента больше, чем плотность E8 в восьмимерном пространстве. Поэтому возникла задача улучшить эту оценку — ведь решение, казалось бы, уже рядом. Более того, в 2012 году тот же Дмитрий Горбачев

(и выиграл) на грант фонда «Династия». В заявке он прямо заявлял, что планирует доказать плотность упаковки E8 в восьмимерном пространстве.

Говорят, что на столь смелое заяление Горбачева подтолкнул другой математик, Андрей Бондаренко, по сути — наставник, один из научных руководителей Марины Вязовской, той самой, которая решила задачу для 8-мерного пространства (и в соавторстве, для 24-мерного). Именно Бондаренко она благодарит в конце своей прорывной работы. Так вот, у Бондаренко и Горбачева не получилось, а у Вязовской получилось. Почему же?

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

. Это довольно симметричный объект, который постоянно возникает в самых разных разделах математики. Именно этот инструментарий и позволил найти нужную функцию.

В 24-мерном пространстве оценка была получена тем же способом. У этой работы больше авторов, но в основе лежит то же самое достижение Вязовской (пусть, конечно, и немного адаптированное). Кстати, в работе доказан еще один замечательный факт: решетка Лича реализует единственную периодическую плотнейшую упаковку. То есть все остальные периодические упаковки имеют плотность меньше этой. По мнению Олега Мусина, аналогичный результат для периодических упаковок может быть верен в размерностях 4 и 8.

10.

С точки зрения приложений задача о плотной упаковке в пространствах большой размерности — это задача, в первую очередь, об оптимальном кодировании с исправлением ошибок.
Представим, что Алиса и Боб пытаются наладить общение, используя радиосигналы. Алиса говорит, что будет слать Бобу сигнал, состоящий из 24 различных частот. Боб будет измерять амплитуду каждой частоты. В результате у него получится набор из 24 амплитуд. Они, конечно, задают точку в 24-мерном пространстве — ведь их 24 штуки. Боб и Алиса берут, скажем, словарь Даля и присваивают каждому слову свой набор из 24 амплитуд. Получается, что мы закодировали слова из словаря Даля точками 24-мерного пространства.
В идеальном мире больше ничего и не нужно. Но реальные каналы передачи данных добавляют шумов, а, значит, во время раскодировки Боб может получить набор амплитуд, который не соответствует ни одному слову. Но тогда он может посмотреть на ближайшее к расшифрованному варианту слово. Если таковое одно, то, значит, скорее всего это оно и есть. Чтобы всегда можно было такое сделать, нужно, чтоб точки пространства располалаглись как можно дальше друг от друга. То есть, например, если уровень шума таков, что вносится искажение, сдвигающее результат на вектор длины не больше один, то две точки кода должны быть точно на расстоянии не меньше двух. Тогда, даже с искажениями, результат у Боба всегда будет близок к одному единственному слову — тому, которое и нужно.
При этом раздувать множество слов тоже не очень хочется — у нас довольно ограниченные диапазон, в котором мы можем передавать информацию. Скажем, будет странно (да и не очень эффективно), если Алиса и Боб начнут общаться в рентгеновском диапазоне. Поэтому в идеале, расстояние между соседними словами кода должно быть в точности два. А это и означает, что слова располагаются в вершинах шаров, радиуса 1, плотно упакованных в 24-мерном пространстве.