有限球詰め

数学において、有限球充填の理論は、有限個の等しい大きさの球を最も効率的に充填する方法を問うものです。有限個の球を充填するという問題は、ここ数十年でようやく詳細に研究されるようになり、その基礎の多くはLászló Fejes Tóthによって築かれました。

無限に多くの球体に対する同様の問題には、より長い研究の歴史があり、その中で最もよく知られているのがケプラー予想です。結晶構造内の原子は、単純に密に詰まった球体として見ることができ、その数が多いため、無限の球体の詰め込みとして扱うことができます。

球のパッキング問題は、与えられた容器へのパッキングと自由パッキングに区別されます。この記事では主に自由パッキングについて説明します。

一般に、パッキングとは、空間的に連結された、場合によってはサイズや形状が異なるオブジェクトのセットを、重なり合わないように空間に配置することを指します。有限球パッキング問題の場合、これらのオブジェクトは同じサイズの球に制限されます。このような球のパッキングにより、パッキングの凸包と呼ばれる特定の体積が決定されます。凸包は、すべての球を含む最小の凸集合として定義されます。

球体の配置方法は多種多様であり、ソーセージ型、ピザ型、クラスターパッキング型の3つの基本的なグループに分類できます。^[1]

• 
  ソーセージの梱包
• 
  ピザの梱包
• 
  クラスターパッキング

すべての球の中心点が 1 本の直線上にある配置は、凸包がソーセージのような形をしているため、ソーセージ パッキングと呼ばれます。実際の生活でのおおよその例としては、チューブにテニス ボールを詰めることがありますが、チューブが実際の凸包と一致するように、両端を丸くする必要があります。

すべての中点が平面上にある場合、そのパッキングはピザパッキングです。この種のパッキングのおおよその実生活の例には、ビリヤードのボールがセットアップ時に三角形にパッキングされることが含まれます。これは、3 次元ユークリッド空間でのパッキングに当てはまります。

球の中点が 3D 空間全体に配置されている場合、そのパッキングはクラスター パッキングと呼ばれます。現実世界での近似としては、果物が箱の中に複数の層に詰められていることが挙げられます。

与えられた定義によれば、ソーセージの詰め物は技術的にはピザの詰め物でもあり、ピザの詰め物は技術的にはクラスターの詰め物でもある。より一般的な次元の場合、「ソーセージ」は1次元の配置、「クラスター」は-次元の配置、「ピザ」はその中間の数の次元を持つものを指す。^[1]${\displaystyle d}$${\displaystyle d}$

1 個または 2 個の球体では常にソーセージになります。3 個であればピザの詰め合わせ (ソーセージではありません) が可能になり、4 個以上であればクラスター (ピザではありません) が可能になります。

球間の空きスペースは、パッキングの種類によって異なります。空きスペースの量は、パッキング密度で測定されます。これは、球の体積と凸包全体の体積の比率として定義されます。パッキング密度が高いほど、パッキング内の空きスペースが少なくなり、したがって、包の体積は小さくなります (球の数とサイズが同じ他のパッキングと比較して)。

球を効率的に詰めるには、どの詰め方が最も密度が高いかが問われるかもしれません。そのような詰め方は、球が互いに隣り合う、つまり各球が表面で他の球に接するという特性を持つ必要があることは容易にわかります。より正確な言い方は、各球に頂点を割り当て、対応する球の表面が接している場合は常に頂点を辺で接続するグラフを形成することです。すると、最も密度の高い詰め方は、対応するグラフが接続されているという特性を満たす必要があります。

3 個または 4 個の球の場合、ソーセージ パッキングが最適です。これは まで、および の場合に当てはまると考えられています。^{[1] [2]}および の場合、ソーセージ パッキングよりも効率的なクラスター パッキングが存在します。これは 1992 年に Jörg Wills と Pier Mario Gandini によって示されました。^{[2] [3]}これらの最も効率的なクラスター パッキングがどのようなものかは不明です。たとえば の場合、最適なパッキングは砲弾の古典的なパッキングのような四面体パッキングではなく、何らかの八面体形状であることがわかっています。^[1]${\displaystyle n}$${\displaystyle 55}$${\displaystyle n=57,58,63,64}$${\displaystyle n=56,59,60,61,62}$${\displaystyle n\geq 65}$${\displaystyle n=56}$

最適パッキング形状の突然の遷移は、一部の数学者によって冗談めかしてソーセージカタストロフィーと呼ばれています(Wills, 1985)。^[4]カタストロフィーという呼称は、最適なパッキング形状が、ある数から別の数に移るにつれて、整然としたソーセージパッキングから比較的無秩序なクラスターパッキングに突然移行し、その逆もまた同様であるという事実に由来しており、なぜこのようなことが起こるのかについての納得のいく説明はありません。それでも、3次元での遷移は比較的穏やかです。次元では、突然の遷移はおよそ 377000 球で起こると推測されています。^[1]${\displaystyle d=4}$

次元の場合、最適なパッキングは常にソーセージかクラスターのいずれかであり、ピザにはなりません。これがすべての次元に当てはまるかどうかは未解決の問題です。この結果は球にのみ関係し、他の凸体には関係しません。実際、グリッツマンとアーヘルガーは、どの次元でも、最もよく詰められたものがピザである凸形状が存在することを観察しました。^[1]${\displaystyle d\leq 10}$${\displaystyle d\geq 3}$

次のセクションでは、455 個の球体の場合、ソーセージ パッキングは最適ではなく、代わりに、より小さな体積を占める特殊なクラスター パッキングが存在することが示されます。

半径 の球を詰めたソーセージの凸包の体積は、初等幾何学で計算できます。 包の中央部分は長さ の円筒で、端のキャップは半径 の半球です。 したがって、全体の体積は次のように求められます。 ${\displaystyle n}$${\displaystyle r}$${\displaystyle h=2r\cdot (n-1)}$${\displaystyle r}$${\displaystyle V_{W}}$

${\displaystyle {\begin{aligned}V_{W}&=V_{\text{円柱}}+2\cdot V_{\text{半球}}\\&=V_{\text{円柱}}+V_{\text{球}}\\&=\pi hr^{2}+{\frac {4}{3}}\pi r^{3}\\&=\pi 2r\cdot (n-1)\cdot r^{2}+{\frac {4}{3}}\pi r^{3}\\&=2\cdot \left(n-{\frac {1}{3}}\right)\pi r^{3}\end{aligned}}}$

同様に、球が四面体形状を形成するように配置されている四面体充填の凸包の体積を求めることも可能であり、特定の数の球に対してのみ完全に充填された四面体が得られる。四面体の1辺に沿って球がある場合、球の総数は次のように与えられる。 ${\displaystyle x}$${\displaystyle n}$

${\displaystyle n=\sum _{i=1}^{x}\sum _{j=1}^{i}j=\sum _{i=1}^{x}{\frac {i\cdot (i+1)}{2}}={\frac {x\cdot (x+1)\cdot (x+2)}{6}}}$。

四面体の内接円の半径 と辺の長さは ${\displaystyle r}$${\displaystyle a}$

${\displaystyle r={\frac {\sqrt {6}}{12}}\cdot a}$。

このことから、

${\displaystyle a=2{\sqrt {6}}\cdot r}$。

四面体の体積は次の式で与えられる。 ${\displaystyle V_{T}}$

${\displaystyle V_{T}={\frac {\sqrt {2}}{12}}\cdot a^{3}={\sqrt {192}}\cdot r^{3}}$

四面体の中に多数の球が配置されている場合、各層ごとに辺の長さは球の半径の2倍ずつ増加し、層ごとに辺の長さは ${\displaystyle a}$${\displaystyle x}$

${\displaystyle a=2\cdot \left(x-1+{\sqrt {6}}\right)\cdot r}$。

この値を四面体の体積の公式に代入すると、凸包の体積は四面体自体の体積よりも小さくなければならないこと がわかります。${\displaystyle V}$

${\displaystyle V<{\frac {2\cdot \left(x-1+{\sqrt {6}}\right)^{3}\cdot {\sqrt {2}}\cdot r^{3}}{3}}}$。

四面体の層に含まれる球の数を先ほどの式に代入して、同じ数の球を詰めたソーセージの凸包の 体積を求めると、次の式が得られます。${\displaystyle n}$${\displaystyle V_{\text{W}}}$

${\displaystyle V_{\text{W}}={\frac {x\cdot (x+1)\cdot (x+2)-2}{3}}\cdot \pi r^{3}}$。

の場合、これは球に変換されますが、 の前の係数は、四面体充填の場合は約 2845、ソーセージ充填の場合は 2856 です。これは、この数の球の場合、四面体がより密に充填されていることを意味します。 ${\displaystyle x=13}$${\displaystyle n=455}$${\displaystyle r^{3}}$

もう少し努力すれば、四面体凸包の体積の正確な式を導くことも可能です。これには、四面体の角と辺の余分な体積を減算することが含まれます。これにより、およびの値が小さい場合、ソーセージの詰め込みが最適ではないことが証明されます。 ${\displaystyle V}$${\displaystyle x}$${\displaystyle n}$

ソーセージという用語は、 1975年にソーセージ予想^[5]を提唱した数学者ラスロー・フェイェシュ・トートに由来しており、これは球、凸包、および高次元の体積に対する問題の一般化バージョンに関するものです。次元の一般化された球とは、すべての境界点が中点から等距離にある次元の物体です。フェイェシュ・トートのソーセージ予想は、上から見たときに球を直線に沿って配置することが常に最適であると述べています。つまり、4次元を超えるとソーセージカタストロフィーは発生しなくなります。全体的な予想は未解決のままです。これまでのところ、最も優れた結果はウルリッヒ・ベトケとマーティン・ヘンクによるもので、^[6] 42次元以上でこの予想を証明しました。 ${\displaystyle d}$${\displaystyle d}$${\displaystyle d=5}$

ソーセージパッキングは 56 個の球に対して最適ではなく、他の最適なパッキングが存在するはずであることが証明されているが、最適なパッキングがどのようなものかはわかっていない。任意の形状のクラスターの体積に対する「単純な」式がないため、最適なパッキングを見つけることは困難である。最適性 (および非最適性) は、ブルン・ミンコフスキー不等式、混合ミンコフスキー体積、シュタイナーの公式などの凸幾何学の方法を使用して、体積を適切に推定することで示される。有限および無限 (格子および非格子) 球パッキングの統一理論に向けた重要なステップは、1992 年に Jörg Wills がパラメトリック密度を導入したことだ。パラメトリック密度は、パッキングのエッジの影響を考慮に入れている。^[7]

先ほど使用した密度の定義は、球（または凸体）の凸包の体積に関するものです。 ${\displaystyle K}$

${\displaystyle \delta (K,C_{n})={\frac {nV(K)}{V(C_{n}+K)}}}$

ここで、 は球の中点の凸包です(球の代わりに、 の任意の凸体を取ることもできます)。線形配置 (ソーセージ) の場合、凸包は球のすべての中点を通る線分です。式のプラス記号はミンコフスキーの集合の加算を表し、 は球の凸包の体積を表します。 ${\displaystyle C_{n}}$${\displaystyle n}$${\displaystyle c_{i}}$${\displaystyle K_{i}}$${\displaystyle K}$${\displaystyle V(C_{n}+K)}$

この定義は 2 次元では機能し、Laszlo Fejes-Toth、Claude Rogersらはこれを用いて有限および無限パッキングの統一理論を定式化しました。3 次元では、Wills は、この定義に基づくとこのような統一理論は不可能であるという単純な議論を示しています。3 次元で最も密なコインの有限配置は、 のソーセージです。しかし、最適な無限配置は の六角形配置であるため、有限値の極限として無限値を得ることはできません。この問題を解決するために、Wills は正のパラメーター を追加することで定義に修正を加えています。 ${\displaystyle \delta =1}$${\displaystyle \delta \approx 0.9}$${\displaystyle \rho}$

${\displaystyle \delta (K,C_{n})={\frac {nV(K)}{V(C_{n}+\rho K)}}}$

${\displaystyle \rho}$エッジの影響を考慮することができます（凸包に特定の厚さを与えます）。これは、ヘルマン・ミンコフスキーの混合体積理論と数幾何学の手法と組み合わせられます。

各次元には、ソーセージの場合が最も密なパッキングとなるパラメータ値とがあり(すべての整数 の場合)、および が十分に大きい場合、クラスターが最も密になります。これらのパラメータは次元固有です。2 次元では、ソーセージからクラスターへの移行が発生します (ソーセージ カタストロフィー)。 ${\displaystyle d\geq 2}$${\displaystyle \rho _{s}(d)}$${\displaystyle \rho _{c}(d)}$${\displaystyle \rho \leq \rho _{s}(d)}$${\displaystyle n}$${\displaystyle \rho \geq \rho _{c}(d)}$${\displaystyle n}$${\displaystyle \rho _{c}(2)=\rho _{s}(2)={\frac {\sqrt {3}}{2}}}$

不等式が存在する：^[7]

${\displaystyle {\frac {V(B^{d})}{2V(B^{d-1})}}{\rho _{c}(d)}^{1-d}\leq \delta (B^{d})\leq {\frac {V(B^{d})}{2V(B^{d-1})}}{\rho _{s}(d)}^{1-d}}$

ここで、単位球の次元における体積は です。 については、 となり、これはすべての次元で成り立つと予測され、その場合、 の値はの値から求めることができます。 ${\displaystyle B^{d}}$${\displaystyle d}$${\displaystyle V(B^{d})}$${\displaystyle d=2}$${\displaystyle \rho _{s}(d)=\rho _{c}(d)}$${\displaystyle \rho _{c}(d)}$${\displaystyle \delta (B^{d})}$