🔢 mathematics

The lattice packing problem in dimension 9 by Voronoi's algorithm

本論文は、ヴォロノイのアルゴリズムを用いて9次元における全てのパーフェクト格子（2,237,251,040個）を列挙することで、9次元における最密格子充填がラミネート格子 $\Lambda_9$ であること、およびそのキッシング数（接点数）の集合を特定したものです。

原著者： Mathieu Dutour Sikirić, Wessel van Woerden

公開日 2026-02-10

📖 1 分で読めます🧠 じっくり読む

CC BY 4.0

原著者： Mathieu Dutour Sikirić, Wessel van Woerden

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

1. 問題の核心：究極の「隙間なしパズル」

想像してみてください。あなたは、たくさんの同じ大きさの「ビー玉」を持っています。このビー玉を、箱の中にできるだけ隙間なく、ぎっしりと詰め込みたいと考えています。

2次元（平面）なら： ビー玉を「六角形」の形に並べれば、一番効率よく詰め込めますよね。
3次元（現実の世界）なら： オレンジを積むときのように、少しずらして重ねるのが一番効率的です。

しかし、問題はここからです。もし、この世界が「3次元」ではなく、**「9次元」**という、私たちの想像を絶する複雑な空間だったらどうなるでしょうか？どの方向に、どのように並べれば、最も隙間を少なくできるのか？これがこの論文が挑んだ「球詰め込み問題」です。

2. 解決策：Voronoi（ヴォロノイ）という「全探索アルゴリズム」

この問題を解くために、研究者たちは「ヴォロノイのアルゴリズム」という手法を使いました。これは、例えるなら**「宇宙のすべてのパズルの組み合わせを、一つ残らずチェックする」**という、非常に力技で、かつ緻密な方法です。

数学の世界には「完璧な並び方（完全格子）」という、いわば「パズルの正解候補」がいくつか存在します。ヴォロノイのやり方は、一つの正解候補を見つけたら、その「隣にある別の候補」を次々と探し出し、まるで**「未知の島を一つずつ地図に書き込んでいく探検家」**のように、すべての可能性を網羅していくのです。

3. 驚異的な計算量：22億個の「正解候補」

ところが、次元が上がると、この「島の数」が爆発的に増えます。
これまでの研究では、8次元までしか地図が完成していませんでした。しかし、今回の研究チームは、ついに**「9次元の地図」**を完成させたのです。

その数はなんと、約22億3700万通り！

これは、もしあなたが毎日1枚ずつパズルのピースをチェックしたとしても、数千年はかかるような膨大な作業です。研究チームは、最新のプログラミング技術とスーパーコンピュータを使い、この「22億個の島」をすべて見つけ出し、分類することに成功しました。

4. 結論：9次元の王者は「Λ9（ラムダ・ナイン）」

膨大な探索の結果、彼らはついに答えを見つけました。

9次元空間において、最も隙間なくビー玉を詰め込める最強の並び方は、**「Λ9（ラムダ・ナイン）」**と呼ばれる特別なパターンであることが証明されたのです。

まとめ：この研究のすごさ

この論文の凄さは、単に「答えを見つけた」ことだけではありません。

地図の完成： 9次元における「完璧な並び方」の全リスト（22億個）を作ったこと。
新しい発見： 9次元では、ビー玉が接する数（キッシング・ナンバー）がどのような値を取り得るのか、そのルールも解明したこと。
技術の進歩： 膨大なデータを処理するための、新しい「計算の道具箱」を作り上げたこと。

いわば、**「9次元という未知の宇宙における、最も美しい並び方のルールブック」**を書き上げた、歴史的な大発見なのです。

1. 問題設定 (The Problem)

格子充填問題とは、 $n$ 次元空間において、等しい半径を持つ球を、密度が最大となるように配置する問題です。この問題は非常に困難であり、現在までに解が判明しているのは次元 $n=1, 2, 3, 8, 24$ のみです。

本論文が焦点を当てているのは、その中でも「格子（Lattice）」という規則的な構造に限定した格子充填問題です。この問題は、エルミート定数（Hermite constant） $\gamma_n$ を求めることと同義です。次元9においては、これまでの理論的なアプローチでは密度の上界と既知の充填の間には開きがあり、最適な格子が何であるかは未解明でした。

2. 手法 (Methodology)

著者らは、1908年にヴォロノイが提唱したアルゴリズムを、現代的な計算機科学の技術を用いて次元9まで拡張・実行しました。

ヴォロノイのアルゴリズム: 最適な格子は必ず「完全格子（Perfect Lattice）」であるという性質を利用し、完全格子をグラフ探索のように列挙していく手法です。
計算上の課題と解決策:
- 双対記述問題 (Dual Description Problem): 完全格子の隣接する格子を見つける際、多面体の「頂点表現（V-representation）」から「面表現（H-representation）」への変換が必要になりますが、次元が高くなると面の数が爆発的に増加します。
- 対称性の利用: 著者らは、多面体の対称性（Automorphism group）を考慮した「対称性下での双対記述問題」を解くアルゴリズムを開発しました。これにより、膨大な数の面を「軌道（Orbit）」としてまとめて扱うことが可能になりました。
- 再帰的隣接分解法 (Recursive ADM): 高い「入射数（Incidence）」を持つ複雑な多面体に対し、より低次元の面へと再帰的に分解して処理する手法を導入しました。
- 並列化と実装: MPIを用いた高度な並列化、および数千億のクラスを効率的に識別するための「標準形（Canonical form）」の計算（グラフ同型判定技術の応用）を実装しました。

3. 主要な貢献 (Key Contributions)

完全な列挙: 次元9におけるすべての非同型な完全格子（計 2,237,251,040個）を初めて完全に特定しました。
アルゴリズムの進化: 膨大な計算量を要する双対記述問題を、対称性と再帰的分解、およびメモ化（Saving Bank）を用いることで、実用可能なレベルまで高速化しました。
データの公開: 約150GBに及ぶ膨大な分類データを公開し、今後の研究に資する基盤を提供しました。

4. 結果 (Results)

次元9の最適充填: ラミネート格子 $\Lambda_9$ が、次元9における最も密な格子充填であることを証明しました。
エルミート定数: 次元9のエルミート定数 $\gamma_9$ が正確に 2 であることを示しました。これは、 $\gamma_8 = 2$ であることと合わせ、エルミート定数が次元に対して必ずしも単調増加しないことを示唆しています。
キッシング数 (Kissing Number): 次元9の格子が持ち得るキッシング数（接する球の数）の集合を、正確に $2 \cdot \{1, \dots, 91, 99, 120, \dots, 129, 136\}$ であると特定しました。
その他の発見:
- Coxeterの格子 $A_9^2$ を除き、次元9のすべての完全格子が最小ベクトルによって生成される基底を持つことを示しました。
- Coxeterの格子 $A_5^9$ が、次元9における唯一の「中空（Hollow）」な完全格子であることを証明しました。

5. 意義 (Significance)

本研究は、数学的に極めて困難な「次元9」という壁を、計算機科学的なブレイクスルーによって突破したものです。

理論的進展: 長年未解決であった次元9の格子充填問題に終止符を打ち、エルミート定数の値を確定させました。
計算幾何学への寄与: 膨大な数の多面体の面を対称性を利用して扱う手法は、他の高次元幾何学問題にも応用可能な強力なフレームワークを提供しています。
数学的構造の解明: 完全格子の分類を通じて、キッシング数や基底の性質、中空格子の存在など、格子理論における詳細な構造を明らかにしました。