Дискретная геометрия

Как упаковать апельсины максимально плотно? Кеплер знал ответ в 1611 году, но доказательство потребовало 387 лет и 250 страниц компьютерных вычислений. Этот же вопрос в 24 измерениях защищает наши банковские транзакции от квантовых компьютеров.

• **Post-Quantum Cryptography:** NIST-стандарт 2024 (ML-KEM, ML-DSA) основан на сложности задач на решётках - устойчив к квантовым атакам
• **Коды с исправлением ошибок:** решётка Лича (24D) обеспечивает оптимальные коды - используется в глубоководных кабелях и космической связи
• **Кристаллография:** FCC и HCP упаковки - реальные структуры металлов (медь, алюминий, золото используют FCC)

Предварительные знания

• Polyhedra
• Vector Geometry

Упаковка шаров и проблема Кеплера

Как наиболее плотно упаковать одинаковые сферы в 3D-пространстве? Кеплер в 1611 году предположил, что гранецентрированная кубическая (FCC) упаковка даёт максимальную плотность π/(3√2) ≈ 74.05%. Это было доказано только в 1998 году Хейлзом - с помощью компьютера.

В 2D: гексагональная упаковка (плотность π/(2√3) ≈ 90.69%) - оптимальна, доказал Тот в 1940. В 3D: FCC и HCP дают одинаковую плотность 74.05% - проблема Кеплера (1998). В 8D и 24D существуют исключительные упаковки E8 и решётка Лича с необычными плотностями.

Решётки и геометрия чисел

Решётка - дискретная подгруппа R^n, порождённая набором линейно независимых векторов. Геометрия чисел (Минковский, 1890-е) изучает связь между геометрическими свойствами решётки и арифметическими свойствами чисел.

Если выпуклое, симметричное относительно начала координат тело имеет объём > 2^n * det(L), то оно содержит ненулевую точку решётки L. Это фундаментальный результат, связывающий геометрию и теорию чисел.

Редукция базиса: алгоритм LLL

Задача кратчайшего вектора (SVP): найти ненулевой вектор минимальной длины в решётке. В высоких размерностях SVP предположительно NP-трудна. Алгоритм LLL (Lenstra-Lenstra-Lovász, 1982) находит 'почти кратчайший' вектор за полиномиальное время.

LLL работает за O(n^5 log B) и находит вектор не длиннее чем 2^((n-1)/2) * lambda1, где lambda1 - истинный минимум. LLL применяется в криптоанализе (взлом некоторых криптосистем), факторизации многочленов и приближённых алгоритмах.

Дискретная геометрия: комбинаторные результаты

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

Теорема Хелли (1923): если есть n выпуклых множеств в R^d, и любые d+1 из них имеют общую точку, то все n множеств имеют общую точку. В 2D: если любые 3 из n выпуклых множеств пересекаются, то все n имеют общую точку.

Ключевые идеи

• **Проблема Кеплера:** FCC/HCP упаковка с плотностью 74.05% оптимальна - доказано Хейлзом в 1998
• **Решётка** = дискретная подгруппа R^n; определитель = объём фундаментальной области
• **Теорема Минковского:** выпуклое симметричное тело объёма > 2^n * det(L) содержит ненулевую точку L
• **SVP трудна** и для квантовых компьютеров - основа post-quantum cryptography

Связанные темы

Дискретная геометрия объединяет пространственную геометрию, векторы и алгоритмы:

• Многогранники — Решётки и упаковки шаров тесно связаны с многогранниками
• Векторная геометрия — Базис решётки-это набор линейно независимых векторов
• Вычислительная геометрия — Алгоритмы на решётках (LLL) применяются в вычислительных задачах

Вопросы для размышления

• Почему задача кратчайшего вектора (SVP) становится тяжелее в высоких измерениях, и как это связано с 'проклятием размерности'?
• Как теорема Минковского о выпуклых телах доказывает, что каждое простое p ≡ 1 (mod 4) является суммой двух квадратов?
• Почему решётки E8 и Лича в 8 и 24 измерениях исключительны - что делает их особенными среди всех решёток?

Связанные уроки

• prob-02-combinatorics