球充填

球充填（きゅうじゅうてん、英語: sphere packing）とは、互いに重なり合わない球を並べて空間を充填することである。通常は同一の大きさの球と3次元ユークリッド空間を扱う。しかし、球の大きさが一様ではない場合や、2次元空間（その場合の球は円）や高次元空間（その場合の球は超球）、さらには双曲空間のような非ユークリッド空間にも適用できる。
典型的な球充填問題とは、ある空間について最も稠密に球を詰め込む配置を見出す問題である。空間全体に対する球によって占められた空間の比率を充填密度（英: density of arrangement）と呼ぶ。無限に広い空間への充填では、測定する体積によって局所的な充填密度が変わるため、通常は密度の平均を最大化するか、十分大きな体積を測定するときの漸近的な密度を最大化することを問題とする。
3次元空間の充填では、等しい大きさの球による最密充填は空間の74%を占める。等しい大きさの球によるランダム充填は一般に64%前後の密度を持ち、最も緩い充填は55％ぐらいになることが実験によって確かめられている。

球充填の分類

球面の中心が格子と呼ばれる極めて対称的なパターンとなる配置を、正規 (regular) 配置（または周期 (periodic) 配置、あるいは格子 (lattice) 配置と呼ぶ。格子状に配置されていない場合は、非正規 (irregular) 配置または非周期 (aperiodic) 配置と呼ぶ。正規配置は非正規配置よりも扱いやすく、対称性の高さのおかげで分類や密度測定が容易に行える。

その他の一般的な格子充填

物理系ではほかの種類の格子充填もよくみられる。例として、 の密度を持つ立方格子や、 の密度を持つ六方格子、 の密度を持つ正方格子がある。またもっとも疎な格子充填では密度は0.0555である。

密度の低いジャミング充填

球充填において、隣接する球同士が押さえつけあって互いを拘束している状態をジャミングという。ジャミングしている球充填で最も疎なものは、密度が0.49365しかない希薄な面心立方格子である。

非正規充填

球を稠密に配置しようとすると、3個の球を互いに接するように配置して、4つ目をその凹みに配置することになる。このようにして作られる配置は、5個目の球までは上述した正規配置のいずれかと一致する。しかし、6個目の球を配置するといかなる正規配置とも一致しなくなる。さらにこの手順を続けることで、圧縮に対して安定なランダム稠密配置を構築できる可能性がある。
球を1つずつ無作為に追加していって圧縮すると、一般にそれ以上圧縮できない「非正規」充填もしくは「ジャミング」充填配置に行きつく。非正規充填の充填密度は約64%となる。2008年の研究では、63.4%が密度の上限であることが解析的に予想されている。1次元や2次元では事情が異なり、1次元球（線分）または2次元球（円盤）を圧縮すると正規充填が生じる。

超球充填

3次元より高次元では、8次元までの超球の最密正規充填が知られている。超球の非正規充填についてはほとんど何も知られていない。次元によっては最密充填が非正規である可能性もある。この予想を補強する事実として、いくつかの次元（例えば10次元）では、既知の最も密な非正規充填の方が既知の最も密な正規充填よりも密度が高い。
2016年、マリナ・ヴィヤゾフスカは8次元空間において正規・非正規を問わない最適充填がE₈格子だと証明した。さらにその直後、共同研究者とともに、24次元における最適充填がリーチ格子だという証明を発表した。どちらの格子もその次元における既知の配置の中でもっとも稠密なものであった。ヴィヤゾフスカの証明では、慎重に選ばれたモジュラー関数のラプラス変換を用いて球対称な関数  を構築する。  はそれ自身およびフーリエ変換  がどちらも原点で1となるように構築される。さらに、充填の中央にある球の外では  が負となる一方、は常に正となるようにすることで、原点以外のすべての格子点で  および  がゼロになることを示せる。その上で  に関するポアソン和公式を用い、想定される最適格子の密度をほかのあらゆる格子の密度と比較する。査読論文の中ではないが、ピーター・サルナックはこの証明を「驚くほど簡潔」と評し、「論文の冒頭を読むだけで証明が正しいと分かるだろう」と述べた。
高次元に関する別のアプローチとして、最密充填の密度の下界を漸近的に求めようとする研究がある。現在までに得られた最大の成果は、n 次元ではある数 c について cn2⁻ⁿ 以上の密度を持つ格子が存在するというものである。

多種球充填

球充填と関連する化学や物理の問題には、球サイズが一つと見なせないものが多い。異なる種類の球で稠密充填を作るには、サイズごとに別の領域に分かれてそれぞれ最密充填を作るか、あるいは異なる種類の球が混合して侵入型化合物のような配置を取るかの選択肢がある。球のサイズの種類が増えると（あるいは連続分布すると）問題は急速に扱いづらくなるが、二通りのサイズの剛球に関する研究はいくつか存在する。
二種類の球のサイズに開きがある場合には、大球が最密充填配置を取った上で、小球が格子間の空隙（八面体型もしくは四面体型）に収まることができる。このような侵入型充填の密度は半径比に強く依存するが、半径比が小さい極限では大球の充填密度を下げずに小球が空隙に侵入することができる。大球が最密配置ではない場合も含め、半径比0.29099以下の小球ならばいかなる配置にも侵入可能である。
小球の半径が大球の0.41421倍を超えると、最密構造の八面体格子間位置にさえ収まることができなくなる。このときホスト格子は膨張して空隙を広げるか（全体の密度は低下する）、より複雑な結晶化合物構造へと再配置するかの選択を迫られる。半径比0.659786以下では最密構造よりも充填率の高い配置が知られている。
また、二種球充填において可能な充填密度の上界も得られている。
化学の分野では、イオン結晶をはじめとして、成分イオンの電荷のため化学量論を保たなければならない状況が多く、これが充填問題に対する拘束条件となる。さらに、電荷間の静電相互作用のエネルギーを最小化する必要もある。これらの影響で最適な充填は多種多様なものになる。

双曲空間

円や球の概念は双曲空間にも拡張可能だが、最密充填を探すのはユークリッド空間よりはるかに難しい。双曲空間では1つの球を取り囲む球の個数には制限がない（たとえば、フォードの円は、同等な双曲円がそれぞれ互いに無限個の円と接しているような配置と考えられる）し、平均密度の概念も正確に定義することすら難しい。いかなる双曲空間においても、最密充填はほぼ常に非正規充填である。
このような困難にもかかわらず、K. Böröczkyは n ≥ 2 である n 次元双曲空間における球充填の密度の普遍的な上界を得た。3次元において Böröczky の上界はおよそ85.327613%で、 シュレーフリ記号 {3,3,6} で表されるホロ球面充填（en:order-6 tetrahedral honeycomb）がこの値を取る。3次元双曲空間の密度の上界を与えるホロ球面充填はこれ以外に少なくとも3つ知られている。

互いに接する球の組

単位球による任意の有限充填についての接触グラフとは、ノードが球を表し、二つのノードがエッジで結ばれていれば二球が互いに接していることを表すようなグラフである。接触グラフに含まれるエッジの集合の濃度は互いに接する球の二つ組の数を与える。同様に3閉路の数は三つ組の数を、四面体の数は四つ組の数を与える（一般に、n 次元の球充填と関連付けられる接触グラフについて、グラフに含まれる n 単体集合の濃度は、球充填に含まれる互いに接する (n + 1) 組の数を表す）。3次元ユークリッド空間における、互いに接する二つ組、三つ組、四つ組それぞれの数に対する非自明な上界がカルガリー大学のKároly BezdekとSamuel Reidによって発見された。

その他の空間

超立方体の角を球で充填する問題は、誤り検出訂正符号の設計に対応している（この場合の球はハミング距離で定義される）。充填する球の半径が d であるとき、それらの中心は 2t + 1-誤り訂正符号の符号語となる。格子充填は線型符号に対応する。これ以外にもユークリッド空間の球充填は誤り訂正符号といくぶん関連性がある。例えば、2元ゴレイ符号は24次元のリーチ格子と密接に関連している。詳しくはConway J.H., Sloane N.J.H. (1998) を参照のこと。

ポップカルチャーでの言及

カート・ヴォネガットの小説『猫のゆりかご』には、アイス・ナインという物質が登場する。その特性の説明として球の様々な充填方法があることが説明される。アイス・ナインは架空の水分子であり、それに触れた他の水分子をアイス・ナインの状態に変化させる性質がある。