球の充填および接触数の問題は重要な未解決問題であるヒルベルトの第１８問題として取り上げられているものですが，前者は大域的なものであり，後者は局所的な問題と考えられます．そして，半径の等しい球をｎ次元ユークリッド空間Ｒ^nに効率的に詰め込む問題のなかでも３次元空間の球の充填問題は「ケプラー問題」と呼ばれるものですが，この問題は１９９８年にトマス・ヘールズによって証明されました．

　ガウスは球を規則正しく並べるという条件つきでケプラー予想が成り立つことを証明したのですが，不規則な並べ方まで含めてあらゆる場合に成り立つことはそう簡単には証明できないことでした．多くの場合，最密充填は整然とした格子によってもたらされるのですが，次元によっては最大接触数が一見ランダムな配置によって実現する場合もあるので問題は複雑なのです．たとえば１〜８次元では最大接吻数は格子上で起きるのですが，９次元では格子上での最大接吻数が２７２であるのに対して，不規則配置では３０６個の球が接触できるものが知られているのですから．→コラム「ｎ次元最密球配置」参照

　ともあれ，ヘールズの証明により「キャノンボール・パッキングよりも密度の高い３次元パッキングは存在しない」ことになるのですが，ランダムな配置まで含めても，面心立方格子が３次元空間における最密充填構造だというケプラー予想は，４００年近く経ってやっと定理に昇格したことになります．

　　［参］スピーロ「ケプラー予想」新潮社

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【１】ケプラーの球体充填問題

　１６１１年，ケプラーは，物質を構成する粒子は体積を最小とするように自己を組織化するだろうという構成原理を考えました．そこで，粒子が球形だと仮定して，さまざまな配置の空間充填率を計算してみました．ケプラーが最初に試みたのは，それぞれの球が６個の球に囲まれるように第１層を構成し，第２層は第１層のくぼみに球を置くという積み方です．

　これは別の角度からみると，立方体の８個の頂点と６面の中心に球が配置されているところから，面心立方格子と呼ばれている配置ですが，この積み方は八百屋の店先でミカンなどの山を安定に積み上げるために使われている日常的な配置です．この場合の充填率は√２π／６（７４．０４％）になります．

　他の配置と比較してみましょう．たとえば，下の層を正方形配列としその真上に球をのせていく単純立方格子の充填率はたったπ／６（５３％）にすぎません．また，六方格子（第１層は面心立方格子と同じ正三角形配列だが，第２層は球の真上に球をのせる）の充填率は√３π／９（６０％）であり，立方体の８個の頂点と中心に球を配置した体心立方格子の充填率は√３π／８（６８％）です．こうして，さまざまな配置を調べてみたケプラーは，面心立方格子が最密充填構造であるという結論に達しました．

　面心立方格子が最も密な球の充填方法だろうという予想は４００年近く前のケプラーまでさかのぼります．日常の経験からしても，同じ大きさの球の最も効果的な配置問題は自明なものと考えてしまいがちで，直感的に面心立方格子をなす場合が最大に詰め込んだ配置のように思えます．しかしだからといって，無限にある可能性をすべてひっくるめて証明したわけではないので，これは定理ではなく予想にすぎません．ランダムな配置まで含めると，空間充填率が７４．０４％よりも引き上げられるかもしれないからです．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

［補］最密充填は正方形を基礎とする配置と六角形を基礎とする配置から作れます．３個のミカンに対して１つの窪みができるのですが，その窪みにミカンを置いたものが六方最密充填です．一方，４個のミカンに対して１つの窪みができ，その窪みにミカンを置くと面心立方充填になります．正方配置の窪みは六方配置の場合よりも深いので，この２つの配置は充填密度に関してはまったく同じなのです．

　この積み方は八百屋の店先でミカンなどの山を安定に積み上げるために使われている日常的な配置ですが，別の角度からみると，上の層の置き方に

　　(1)第１，２，３層目がすべてずれていて，第１層目の球の真上に第４層目の球がくる（ＡＢＣＡＢＣＡＢＣ・・・）

　　(2)第１層目の球の真上に第３層目の球がくる（ＡＢＡＢＡＢ・・・）

という２種類があります．

　(1)は立方体の８個の頂点と６面の中心に球が配置されているところから面心立方格子と呼ばれている配置，(2)は六方最密充填ですが，いずれの場合の充填率も√２π／６（７４．０４％）になります．以上の２つ以外にも無数の配列が考えられ，たとえば，ＡＢＡＣの４層周期，ＡＢＣＡＣＢの６層周期などの積み重なりなどが見つけだされています．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

　ロジャースは「ケプラー予想が正しいことは多くの数学者が信じ，すべての物理学者が知っている」という名文句でも有名ですが，１９５８年，彼は四面体配置から空間充填率の上限を３√２（ａｒｃｃｏｓ１／３−π／３）＝７７．９６％とはじき出しました．四面体配置は，３次元で相互に接するように球を配置するときの最大数となる配置ですが，全空間を充たすことはできないので，空間充填率の上限と考えられるわけです．

　ちなみに正十二面配置では７５．４６％，正八面体では７２．０９％となるのですが，これらの正多面体も大域的な空間充填はできないのです．１９８８年には，この上限はわずかに改良され，７７．８４％よりも高密度の詰め込みは存在しないことが証明されています（ムーダー）．これを７４．０４％まで引き下げることができれば，面心立方格子が最密充填構造だという証明になるのですが，残念ながら，上限の引き下げは骨の折れる厄介なプロセスであり，遅々として進みませんでした．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【２】ヘールズによるケプラー問題の証明

　面心立方格子が３次元空間における最密充填構造だという証明は，わずか数％の差であるにもかかわらず，また，何世紀にもわたる研究にもかかわらず未解決でした．苦々しいほど遅々たる歩みのケプラーの問題については，ロジャーズの名文句のごとく，大半の数学者がまず間違いないだろうと考え，すべての物理学者が当たり前だと思っていた・・・そして欠けているのは証明だけという状況だったのです．

　ケプラー予想は，１９９４年に解決されたフェルマーの最終定理に取って代わる数学上の未解決問題になっていたわけですが，ヘールズはボロノイ分割に加えて，その双対あるドロネーの四面体分割（ドロネー・シンプレックス）を用いました．そして，評価関数を導入して，密度の低い配置は減点（ペナルティー・ポイント）され，密度の高い配置は加点（ポーナス・ポイント）する．

　このとき，何年にもわたってヘールズを悩ませることになった厄介な問題は正二十面体配置（五角反柱配置）でした．六方最密充填でも面心立方充填置でもすべての球はほかの１２個の球に接触しています（どの球も同じ層の中の３つ，すぐ上とすぐ下の層の３つずつ，合計１２個の球と接しています）．

　しかし，１２個の球に接触する配置はこればかりではなく，無限に存在します．たとえば，真ん中の球の真下に１個の球を置き，赤道の少し下に５個の球，赤道の少し上に５個の球，最後に真ん中の球の真上に１２番目の球を置くというのが正二十面体配置（五角反柱配置）です．

　菱形十二面体配列は，たとえどの球も１個だけでは動けなくとも配列全体では動き得るので，五角形十二面体型（正二十面体型）配列に移行することができるのです．

　正二十面体配置（球充填密度：７５．４６％）が１２個の球に接触する局所的な最密球充填密度であることもヘールズ，マクローリンにより証明されています．しかし，３次元空間において正二十面体（正十二面体）は全空間を満たすことのできる敷石立体ではないのです．

　ちなみに，球に外接する正十二面体の体積は

　　１０｛２（６５−２９√５）｝^(1/2)＝５．５５０・・・

菱形十二面体の体積は

　　４√２＝５．６５６・・・

となり，この値は上の値より大きくなります．

［補］アルキメデスの正角柱（上下の底面が正多角形で，側面がすべて正方形であるもの）を少しひねって，側面をすべて正三角形にしたものをアルキメデスの反角柱と呼びます．正２０面体は側面が１０個の正三角形からなる五角反柱の上下の面に正五角錐をつけると構成することができます．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

　また，ヘールズはケプラー問題の証明のためにコンピュータの助けを借りなければなりませんでした．ヘールズによるケプラー問題の証明は，本質的に最適化問題であって，シンプレックス法を繰り返し利用しました．

　ヘールズの証明は美しくエレガントな証明ではなく，しらみ潰しの方法に基づく力ずくの証明だったのですが，この状況は「四色問題」の場合と非常によく似ています．「四色問題」でコンピュータが初めて定理の証明に使われたとき数学界は大揺れに揺れたのですが，ヘールズのケプラー問題の証明はそれから２０年以上経っていたこともあってか，それほどのスキャンダルにはなりませんでした．コンピュータによる証明が数学の進展にとって重要であることが多くの数学者にとって受け入れられるようになってきているためなのでしょう．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【補】最密球充填と最疎球被覆の年表

ｎ　　　ルート　　球充填密度

２　　　Ａ2　　　π／２√３＝０．９０６（ラグランジュ1773，ガウス1831）

３　　　Ａ3　　　π／３√２＝０．７４０（ガウス1831）

４　　　Ｄ4　　　π^2／１６＝０．６１７（Korkine,Zolotareff,1872）

５　　　Ｄ5　　　π^2／１５√２＝０．４６５（Korkine,Zolotareff,1877）

６　　　Ｅ6　　　π^3／４８√３＝０．３７３（Blichfeldt,1925）

７　　　Ｅ7　　　π^3／１０５＝０．２９５（Blichfeldt,1926）

８　　　Ｅ8　　　π^4／３８４＝０．２５４（Blichfeldt,1934）

ｎ　　　ルート　　球被覆密度

２　　　Ａ2~　　　２π／√２７＝１．２０９（Kershner,1939）

３　　　Ａ3~　　　５√５π／２４＝１．４６４（Bambah,1954）

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【補】シンプレックス法

　線形計画法は最小の費用の下で得られるべき利益を最大にすることを目的とした最適化の１つの方法です．商業上重要というだけでなく，数学のいろいろな分野でも使われます．

　線形計画法におけるシンプレックス法は，有限個の線形不等式

　　Ａｘ≧ｂ，　　maximize　ｃｘ

の解の集合から最適解を求めるもので，ダンツィックにより１９４７年から開発が進められました．その手順はまず実行可能な頂点を見つけ，そこから多面体の辺に沿って，線形の目的関数ｃｘが増加するように進んでいくというものです．

　ｄ次元の場合，多面体の各頂点からはｄ本の辺がでているのですが，しかし，目的関数が増加するような次の辺をどうやって選べばよいかは現在でも完全には解決されていない問題となっています（多項式時間アルゴリズムがあるか？）．

　また，一口にシンプレックス法といっても，データが得られた状況によってそれぞれに最適な手法が用意されていて，それらを適宜選択し使い分ける必要が出てきます．シンプレックス法の教科書はこれまで多数出版されていますが，たいていはｘが非負の場合のみを解説しています．変数ｘが非負の値をとるようにした制約条件の場合，非基底変数の値は０ですが，下限Ｌと上限Ｕの間の値をとるようにした制約条件の場合，非基底変数の値はＬかＵのどちらかとなります．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝