■球の充填と格子（その１）
球の充填および接触数の問題は，ヒルベルトの第１８問題として取り上げられているものですが，１９９８年にトマス・ヘールによって
「キャノンボール・パッキングよりも密度の高い３次元パッキングは存在しない」
ことが証明されたと伝えられています．
多くの場合，最密充填は整然とした格子によってもたらされるのですが，次元によっては最大接触数が一見ランダムな配置によって実現する場合もあるので問題は複雑なのです．ランダムな配置まで含めても，面心立方格子が３次元空間における最密充填構造だというケプラー予想は，４００年近く経ってやっと定理に昇格したことになります．→［補］
今回のコラムでは，半径の等しい球をｎ次元ユークリッド空間Ｒ^nに効率的に詰め込む問題（ヒルベルトの第１８問題）についてて触れてみることにしたいと思います．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【１】kissing numberの問題
１つの１０円玉を机の上において，それと触れ合うようにかつお互いに重ならないようにして，６個の１０円玉を置くことができます．１次元の球は区間であり，接触数は１次元のとき２個，２次元のとき６個であることは自明であって，幼稚園児でも解くことができそうです．
平面上で与えられるたいていの問題は，３次元あるいは高次元の空間で考察することができます．一般に，ｎ次元ユークリッド空間において，１つの単位球に同時に接触することのできる単位球の最大個数τn は接吻数（kissing number）あるいは接触数（contact number）と呼ばれていて，最密充填構造「同じ半径の球をできるだけ稠密詰めるにはどうしたらよいか」という空間の球による充填問題と深い関連があります．
１０円玉の例からわかるようにτ2＝６ですが，ｎ≧３のとき，τn はどうなるでしょうか？ まず，３次元の場合，単位球のまわりに面心立方格子状に単位球を置いた場合の接触点
1/√2（±１，±１，０）
1/√2（±１，０，±１）
1/√2（０，±１，±１）
を考えてみると，これら１２個の相異なる２点に対応するベクトルの内積は，−１，±１／２，０のいずれかであり，したがって，その間の角度（球面距離）は６０度以上となりますから，これらの点で接するように１２個の単位球を置くことができます．したがって，τ3≧１２は直ちにわかります．
実際，正２０面体の１２個の頂点に対して，そこで接するように１２個の単位球を置くことができます．この場合，頂点間の角度は約６３゜２６′になり，１２個の球は互いに接触しておりません．少しだけなら自由に動かせるという状況ですから，その隙間を一つに集めたらもう一個球が入るのではないでしょうか？ ところが，これができるかできないかはあまり自明ではありません．というより，３次元になるととたんに問題が難しくなってしまうのです．
３次元の球の最大接触数τ3については，１６９４年にニュートンとグレゴリーの間で議論され，ニュートンは１２を，グレゴリーは１３を主張したといわれています．結局，ニュートンは１２個が最大であるという証明ができず，グレゴリーも１３個並べたわけではないので，「ニュートンの１３球問題」と呼ばれるこの論争は引き和けに終わりました．
１８７４年，ホッペが１２個が最大であることという証明を試みましたが，不備があり，ようやく完全な証明がなされたのは１９５３年，ファン・デル・ヴェルデンとシュッテによってです．つまり，３次元空間内で１つの球には同時に１２個の球しか接することができません．３次元のときは１２個という解が得られるまで非常に長い年月がかかったことになります．
４次元の場合はどうなるでしょうか？ ２４個の面心立方格子状配置の接触点
1/√2（±１，±１，０，０）
1/√2（±１，０，±１，０）
1/√2（±１，０，０，±１）
1/√2（０，±１，±１，０）
1/√2（０，±１，０，±１）
1/√2（０，０，±１，±１）
で重ならないように置けるので，τ4≧２４は明らかです．また，τ4≦２５は示されていますが，現在でもτ4が２４であるか２５であるかは未解決です．
ｎ次元ユークリッド空間において，１つの単位球に同時に接触することのできる単位球の最大個数τnの正確な値を決定する問題は大変難しく，４次元以上の高次元については，高度に対称的な格子状配置になっている８次元（２４０個）と２４次元（１９６５６０個）の場合を除いて未解決であり，現在，正確な値が知られているのは，τ1＝２，τ2＝６，τ3＝１２，τ8＝２４０，τ24＝１９６５６０の５つだけなのです．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
少し詳細に調べていきましょう．４次元，５次元においては面心立方格子の類似品となりますが，６次元以上についてはそのようなことはもはや成立しなくなります．次元の上昇とともに，超球の間の隙間が大きくなっていくからです．８次元になると面心立方格子に十分な隙間ができるので，１１２個の接触点
1/√2（０，・・・，±１，０，・・・，±１，０・・・） （±１の個数は２つ）
と１２８個の隙間の点
1/√8（±１，±１，±１，±１，±１，±１，±１，±１） （＋の個数は偶数）
に同じ大きさの球が詰め込み可能になります．
専門的になりますが，τ8の２４０個の点はＥ8型の単純リー代数の２４０個のルート格子で実現されます．さらに，この詰め込みの断面（部分格子）が６次元と７次元のもっとも効率のいい格子状詰め込みを与えてくれます．
また，１９６５年，リーチは群論と深く結びついた今日リーチ格子として知られるようになったものに基づいて，２４次元空間の格子状詰め込みを構成しました．この詰め込みにおいては，なんと１つの超球に１９６５６０個もの超球が接触しています．τ24の１９６５６０個の点はリーチ格子の原点から一番近い点の集合として得られることが知られています．
こうして，ｎ≦２４のときのすでに知られている上界・下界がオドリズコ，スローンによって与えられています．
ｎ τn
1 2
2 6
3 12
4 24〜25
5 40〜46
6 72〜82
7 126〜140
8 240
9 306〜380
10 500〜595
･･･････････････････
24 196560
つまり，８次元と２４次元は，接吻数が計算できる特殊な次元なのであり，都合のいい格子（８次元の場合，格子にはＥ8，２４次元の場合，リーチ格子という名前が付いている）がひとつに決まるので，格子上に球を配置することによってすぐに接吻数を数えることができるというわけです．
［参］坂内英一・坂内悦子「球面上の代数的組合せ理論」シュプリンガー・フェアラーク東京，ｐ２１４〜２１５
には，τ8＝２４０，τ24＝１９６５６０のゲーゲンバウアー展開を用いた証明が掲載されています（オドリズコ，スローン）．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【２】極大格子
以下では，ｎ＝８，２４の場合について最密充填を与える格子の構成法を略述したいのですが，その前に極大格子についても言及しなければなりません．
単独で空間を充填する平面充填正多角形は３種類（正三角形・正方形・正六角形），空間充填正多面体は１種類（立方体）です．それに対して，４次元空間を１種類の正多胞体で埋めつくす図形は，正８胞体，正１６胞体，正２４胞体の３種類であり，４次元の最密正則胞体充填構造は，正２４胞体で埋めつくされているときであることが知られています．
正２４胞体の頂点は正８胞体と正１６胞体の頂点をなすことより，正２４胞体は３次元の菱形１２面体Ａ3に対応するものであって，（３，４，３，３）は４次元版の菱形１２面体による空間充填形に相当します．すなわち，それは４次元の面心立方格子といってよいものであって，４次元の最密正則胞体充填構造Ｄ4は正２４胞体で埋めつくされているときであることが知られているというわけです．
なお，ｎ次元正単体とｎ次元立方体の対称群は，それぞれＡn-1，Ｂn（Ｃn）で表されるのですが，２４胞体は１つの例外型対称群Ｆ4をもつことが知られています．２４胞体は単体以外の唯一の自己双対な正則胞体であるという事実がＦ4と関係しているらしく，この点もまた注目すべきものです．
そこで「単位格子群の２つの格子点の間の最小距離ｄminを最大にする格子群（極大格子群）を求めよ」というミニマックス問題が設定されます．すなわち，正多角形，正多面体に限らない最密規則的充填構造は何かという問題です．
２次元では，与えられた最小距離をもつすべての格子中で，格子点密度のもっとも高いものは，正三角形格子（Ａ2）ということになります．
３次元では，すべての辺の長さが等しい平行六面体格子（菱形体格子）をつくってみると，辺が互いの６０°の角度をなすようにしたとき，平行六面体の体積は最小値となります．これが面心立方格子状配置であって，その対称性はＣ3（立方体）ではなく，Ａ3で与えられます．
もっとも稠密な格子状球配置を求める問題はより高次元の空間においても考えることができるのですが，高次元空間においては，平面における正三角形格子や３次元空間における面心立方格子はもはや最密球配置を与えてはくれません．４次元のＤ4格子は４次元の体心立方格子であり，正２４胞体による空間充填形に相当します．すなわち，４次元，５次元においては面心立方格子の類似品Ｄ4，Ｄ5となるのですが，６次元についてはそのようなことも成立しなくなり，例外型リー環に属するＥ6となります．
これは次元の上昇とともに，超球の間の隙間が大きくなっていくからなのですが，８次元になると面心立方格子に十分な隙間ができるので，１１２個の面心立方格子状配置の接触点
1/√2（０，・・・，±１，０，・・・，±１，０・・・） （±１の個数は２つ）
と１２８個の隙間の点
1/√8（±１，±１，±１，±１，±１，±１，±１，±１） （＋の個数は偶数）
に同じ大きさの球が詰め込み可能になります．
この詰め込みの断面（部分格子）が６次元と７次元のもっとも効率のいい格子状詰め込みＥ6，Ｅ7を与えてくれるというわけです．こうして，極大格子については，現在のところ，ｎ≦８のみ答えが知られています．
ｎ ルート 格子点間距離 球充填密度
１ １ １
２ Ａ2 4√（４／３） ＝１．０７５ ０．９０６
３ Ａ3 6√２ ＝１．１２２ ０．７４０
４ Ｄ4 8√４ ＝１．１８９ ０．６１９
５ Ｄ5 10√８ ＝１．２３１ ０．４６５
６ Ｅ6 12√（６４／３）＝１．２９０ ０．３７３
７ Ｅ7 14√６４ ＝１．３４６ ０．２９５
８ Ｅ8 √２ ＝１．４１４ ０．２５４
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【３】kissing numberの上界と下界
ここでまた，kissing numberの問題に戻りましょう．
τ1＝２，τ2＝６，τ3＝１２
そして，４次元以上の高次元では，８次元（２４０個）と２４次元（１９６５６０個）の場合を除いて未解決です．
τ8＝２４０，τ24＝１９６５６０
ｎ次元球のkissing numberの上界は，コクセターの方法によって粗雑ながら押さえられます．それは１球面上に大きさの等しい球帽（球面上の円，球面半径φ）を埋め込むときの最密充填の問題に帰着されるのですが，それは単体的密度限界
ｄn＝（２ｎ／（ｎ＋１））^(-n/2)Ｄn
＝（ｎ＋１）^(1/2)（ｎ！）^2／２^(3n/2)・ｖnＦn(1/2arcsec(n)θ)
と類似の方法になっています．
ｎ次元正単体（二面角２θ）の頂点を超球の中心において，（ｎ−１）次元球面上に射影します．球面上には（ｎ−１）次元球面正三角形ができ，その面積は
Σ＝２^(-n)ｎ！ｓnＦn(θ)
で与えられます．これは正単体の１辺の球面距離２φの関数になります．
また，σを球面正三角形の頂角の和とすると，球面上にはｎ個の点が配置され，（ｎ−２）次元球帽が（ｎ−１）次元球面を覆うことになります．そして，１つの頂角は（ｎ−１）次元正単体を（ｎ−２）次元球面上に射影したものに等しくなりますから
σ＝ｎ２^(-n+1)（ｎ−１）！Ｆn-1(θ)
すなわち，上界は
（ｐ，３，・・・，３），θ＝π／ｐ
なる三角形面正多面体（単体的正多面体：ｎ−１次元面が単体）の頂点に（ｎ−２）次元球を配置する問題となるのですが，ここで，球面上にＮ(φ)個の点を配置した場合，不等式
Ｎ(φ)≦σｓn／Σ
が成り立ちますから，最終的に
Ｎ(φ)≦２Ｆn-1(θ)／Ｆn(θ)
ｓｅｃ２θ＝ｓｅｃ２φ＋ｎ−２
を得ることができます．
kissing number（τn）に関しては，φ＝π／６の場合を考えればよいので， τn≦２Ｆn-1(1/2arcsecn)／Ｆn(1/2arcsecn)
となり，
ｎ＝２ → ２Ｆ1(π/6)／Ｆ2(π/6)＝６
ｎ＝３ → ２Ｆ2(1/2arcsecn3)／Ｆ3(1/2arcsecn3)＝6/(3-π/arcsec3)＝１３．３９・・・
ｎ＝４ → ２Ｆ3(1/2arcsecn4)／Ｆ4(1/2arcsecn4)＝5(1+1/(2-2π/arcsec4))＝２６．４４・・・
５次元以上では，数値積分によらなければなりませんが，
ｆn(x)＝Ｆn(1/2arcsecx)
と書くことにすると，
ｆ2(x)＝arcsecx/x
ｆn(x)＝1/π∫(n-1,x)ｆn-2(x-2)/x√(x^2-1)dx
＝ｆn(n)＋1/π∫(n,x)ｆn-2(x-2)/x√(x^2-1)dx
ｆn(x)＝ｆn-1(x)-1/3ｆn-3(x)+2/15ｆn-5(x)-17/315ｆn-7(x)+62/2835ｆn-9(x)-･･･(n:odd)
ｆn(x)＝1/3ｆn-2(x)-2/15ｆn-4(x)+17/315ｆn-6(x)-62/2835ｆn-8(x)+･･･(n:even)
リーチは台形則を用いて数値積分し，
２ｆn-1(n)／ｆn(n)
を求めました．その結果は
２ｆ3(4)／ｆ4(4)=22.44･･･
２ｆ4(5)／ｆ5(5)=48.70･･･
２ｆ5(6)／ｆ6(6)=85.81･･･
２ｆ6(7)／ｆ7(7)=146.57･･･
２ｆ7(8)／ｆ8(8)=244.62･･･
以下，(9)401,(10)648,(11)1035,(12)1637,･･･と続きます．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
ｎ次元球のkissing numberの上界は立体角による評価，すなわち，正四面体配置（相互に接するよう球を配置）の問題でしたが，それに対して，下界は極大格子状配置による評価，すなわち，
Ａ1，Ａ2，Ａ3，Ｄ4，Ｄ5，Ｅ6，Ｅ7，Ｅ8
の問題となります．
たとえば，ｎ＝３のみならず，ｎ＝４，５の場合も面心立方格子状配置
（±１，±１，０）
（±１，±１，０，０）
（±１，±１，０，０，０） （±１の個数は２つ）
では２ｎ（ｎ−１）個の球と接することができます．
ｎ＝６，７，８では面心立方格子状配置の接触点以外にも隙間ができるので，隙間の分が加わって，それぞれ
６０＋１２＝７２
８４＋４２＝１２６
１１２＋１２８＝２４０
個の同じ大きさの球が詰め込み可能になります．（Ｅ6，Ｅ7，Ｅ8格子はそれぞれ接触数７２，１２６，２４０を与える．）
この隙間は，９個の整数に対して法３で合同となるので，
ｘ1＋ｘ2＋ｘ3＝ｘ4＋ｘ5＋ｘ6＝ｘ7＋ｘ8＋ｘ9＝０ （ｎ＝６）
ｘ1＋ｘ2＋ｘ3＋ｘ4＋ｘ5＋ｘ6＝ｘ7＋ｘ8＋ｘ9＝０ （ｎ＝７）
ｘ1＋ｘ2＋ｘ3＋ｘ4＋ｘ5＋ｘ6＋ｘ7＋ｘ8＋ｘ9＝０ （ｎ＝８）
であって，
１２×３＝４２，４２×３＝１２８
という関係にあり，Ｅ8では９個の球によって完全に充填した構造となっています．
第１層 第２層 第３層
Ｅ6 格子 ７２ ２７０ ７２０
Ｅ7 格子 １２６ ７５６ ２０７２
Ｅ8 格子 ２４０ ２１６０ ６７２０
そして，最終的には簡単なグラフ的算法に帰着されるのですが，１≦ｎ≦８では
ｎ １ ２ ３ ４ ５ ６ ７ ８
下界 ２ ６ 12 24 40 72 126 240
となり，ガウス記号を用いて
下界＝ｎ（［２^(n-2)／３］＋ｎ＋１）
の形にまとめられます．→（この式はｎ＞８に対しては成り立ちません．ｎ＝９のとき４６８となるのですが，コクセターの上界４０１よりも大きくなってしまうからです．）
これより
ｎ τn
1 2
2 6
3 12〜13
4 24〜26
5 40〜48
6 72〜85
7 126〜146
8 240〜244
となります．
以下に，現在知られている上界・下界を記しますが，コクセターの方法は，現在知られている上界よりほんの少し大きい方に偏っていることがわかります．このようにτnの知られている上限と下限の間の差はまだ非常に大きいといえます．
ｎ τn ｎ τn
1 2 13 1130〜2233
2 6 14 1582〜3492
3 12 15 2564〜5431
4 24〜25 16 4320〜8313
5 40〜46 17 5346〜12215
6 72〜82 18 7398〜17877
7 126〜140 19 10668〜25901
8 240 20 17400〜37974
9 306〜380 21 27720〜56852
10 500〜595 22 49896〜86537
11 582〜915 23 93150〜128096
12 840〜1416 24 196560
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
［補］kissing numberの漸近評価
kissing numberの漸近評価については
１／ｂ＝ｓｅｃ２θ−ｎ＋１
とおくと，
Ｆn(θ)〜√{(1+nb)/2}･1/(n!e^(1/b))･(2e/πnb)^(n/2)
したがって，
Ｎ(φ)〜2^(1-n/2)√(πcos2φ)n^(3/2)/(e(sinφ)^(n-1))
φ＝π／６のとき
τn 〜 2^((n-1)/2)n^(3/2)√π/e
となります．
また，上限に関しては
τn ≦ 2^(0.401n(1+o(1)))
という式が知られています．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
［補］ケプラー問題
１６１１年，ケプラーは，物質を構成する粒子は体積を最小とするように自己を組織化するだろうという構成原理を考えました．そこで，粒子が球形だと仮定して，さまざまな配置の空間充填率を計算してみました．
ケプラーが最初に試みたのは，それぞれの球が６個の球に囲まれるように第１層を構成し，第２層は第１層のくぼみに球を置くという積み方です．これは別の角度からみると，立方体の８個の頂点と６面の中心に球が配置されているところから，面心立方格子と呼ばれている配置ですが，この積み方は八百屋の店先でミカンなどの山を安定に積み上げるために使われている日常的な配置です．この場合の充填率は√２π／６（７４．０４％）になります．
他の配置と比較してみましょう．たとえば，下の層を正方形配列としその真上に球をのせていく単純立方格子の充填率はたったπ／６（５３％）にすぎません．また，六方格子（第１層は面心立方格子と同じ正三角形配列だが，第２層は球の真上に球をのせる）の充填率は√３π／９（６０％）であり，立方体の８個の頂点と中心に球を配置した体心立方格子の充填率は√３π／８（６８％）です．こうして，さまざまな配置を調べてみたケプラーは，面心立方格子が最密充填構造であるという結論に達しました．
面心立方格子が最も密な球の充填方法だろうという予想は４００年近く前のケプラーまでさかのぼります．日常の経験からしても，同じ大きさの球の最も効果的な配置問題は自明なものと考えてしまいがちで，直感的に面心立方格子をなす場合が最大に詰め込んだ配置のように思えます．しかしだからといって，無限にある可能性をすべてひっくるめて証明したわけではないので，これは定理ではなく予想にすぎません．ランダムな配置まで含めると，空間充填率が７４．０４％よりも引き上げられるかもしれないからです．
ケプラーの問題については，大半の数学者がまず間違いないだろうと考え，すべての物理学者が当たり前だと思っていたのですが，面心立方格子が３次元空間における最密充填構造だという証明は，何世紀にもわたる研究にもかかわらず未解決で，１９９４年に解決されたフェルマーの最終定理に取って代わる数学上の未解決問題になっていたというわけです．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
