Как не ошибаться. Сила математического мышления - Джордан Элленберг

Впрочем, некоторые современные искусственные языки устроены иначе: в них используют принципы, сформулированные Хэммингом и Шенноном. Один из самых успешных примеров такого подхода – язык ложбан^[230]; в нем действует строгое правило, согласно которому два базовых корня (ginsu) не могут быть фонетически близкими.

Представление Хэмминга о расстоянии соответствует философии Фано: величина, которая крякает как расстояние, имеет право на то, чтобы вести себя как расстояние. Но нужно ли останавливаться на этом? Множество точек, расположенных от заданной центральной точки на расстоянии, меньшем или равном 1, имеет в евклидовой геометрии свое название: круг, или, в большей размерности, сфера^[231]. Таким образом, мы должны обозначить множество строк, расстояние Хэмминга которых от кодового слова не больше 1^[232], термином «сфера Хэмминга», в центре которой находится кодовое слово. Для того чтобы код был кодом с исправлением ошибок, ни одна строка (ни одна точка, если серьезно относиться к этой аналогии) не может находиться на расстоянии 1 от двух разных кодовых слов; другими словами, требуется, чтобы две сферы Хэмминга с соответствующими кодовыми словами в центре не имели общих точек.

Таким образом, задача конструирования кодов с исправлением ошибок имеет такую же структуру, что и классическая геометрическая задача про упаковку сфер: каким образом разместить множество сфер одинакового размера в небольшом пространстве как можно плотнее, при условии что любые две сферы никогда не пересекутся? Проще говоря, сколько апельсинов можно уложить в ящик?

Задача упаковки сфер гораздо старше кодов с исправлением ошибок; этой проблемой занимался в свое время астроном Иоганн Кеплер, в 1611 году написавший на латинском языке трактат Strena, seu de nive sexangula («Новогодний подарок, или О шестиугольных снежинках»)^[233]{196}. Название довольно причудливое, но Кеплер на самом деле обращается к общим вопросам происхождения естественных форм. Почему снежинки и пчелиные соты образуют шестиугольники, тогда как семенная камера яблока состоит из пяти частей? Почему зерна граната имеют, как правило, двенадцать плоских сторон? Кстати последний вопрос имеет самое непосредственное отношение к нашей современной жизни.

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

Следующий слой должен выглядеть аналогично, но зернышки необходимо выложить так, чтобы каждое разместилось в маленьком треугольном углублении, образованном тремя зернами нижнего слоя. Затем необходимо точно так же выкладывать следующие слои зерен граната. При укладке требуется проявлять некоторую осторожность: только половина углублений будет поддерживать сферы следующего уровня, и на каждом этапе предстоит решать, какую именно половину углублений вы хотите заполнить. Традиционное решение, которое называется «гранецентрированная кубическая решетка», имеет одно замечательное свойство: на каждом очередном уровне есть сферы, расположенные непосредственно над сферами тремя уровнями ниже. По мнению Кеплера, не существует способа более плотной упаковки сфер в пространстве^[234]. В гранецентрированной кубической решетке каждая сфера соприкасается ровно с двенадцатью другими сферами. Кеплер считал, что по мере роста зерен граната каждое из них начинает придавливать своих двенадцать соседей, из-за чего поверхность у точки соприкосновения становится плоской и зерна граната превращаются в фигуры с двенадцатью гранями^[235].

Понятия не имею, был ли прав Кеплер насчет граната^[236], но его утверждение, что гранецентрированная кубическая решетка обеспечивает самую плотную упаковку сфер, на целые столетия оказалось в центре пристального интереса математиков. Кеплер не сформулировал доказательство своего утверждения; по всей вероятности, ему просто казалось очевидным, что гранецентрированную кубическую решетку превзойти невозможно. С ним солидарны целые поколения бакалейщиков, пакующие апельсины в соответствии с гранецентрированной кубической конфигурацией. Однако математикам как людям требовательным понадобилось абсолютное подтверждение, причем не только в отношении окружностей и сфер. В мире чистой математики ничто не мешает выйти за рамки окружностей и сфер, устремиться к более высоким размерностям и начать упаковать так называемые гиперсферы в пространство с количеством измерений больше трех. Не позволяет ли геометрическая история об упаковке сфер в пространстве с большей размерностью лучше понять теорию кодов с исправлением ошибок, подобно геометрической истории о проективном плане? В данном случае поток перемещается главным образом в другом направлении^[237]: открытия в области кодирования подстегнули прогресс в области упаковки сфер. Например, в 1960-е годы Джон Лич, применив один из кодов Голея, построил в двадцатичетырехмерном пространстве невероятно плотную упаковку сфер. Конфигурация, известная сегодня как «решетка Лича», представляет собой крайне густонаселенное место, в котором каждая из двадцатичетырехмерных сфер соприкасается с 196 560 соседними сферами. До сих пор неизвестно, обеспечивает ли она самую плотную упаковку сфер в двадцатичетырехмерном пространстве, но в 2003 году Генри Кон^[238] и Абхинав Кумар доказали, что, если более плотная решетка и существует, она обеспечит плотность упаковки сфер больше плотности решетки Лича максимум в