Greedy Packing of Nested Rings: Placement Rules, a Golden Counterexample, and a Tribonacci Floor

技術要約：入れ子状のリングの強欲なパッキング（Greedy Packing）

問題設定
本論文は、共通の幅 $w$ を持つアニュラス（環状のリング）をコンパクトなコンテナ（「パン」）の中にパッキングする問題を調査している。ここでは、リングがより大きなリングの穴の中に入れ子状に配置されることを許容する。研究の焦点は、配置されるリングの数（カーディナリティ）の最大化と、リングとコンテナとの間の総接触面積の最大化という、二つの競合する目的関数にある。これらの目的は、接触面積が半径に対して超加算的（superadditive）であるのに対し、カーディナリティはそうではないために乖離する。

中心となる問いは、降順強欲アルゴリズム（半径の大きい順にリングを処理する手法）が、利用可能なコンテナを選択するための特定のルール（例：ベストフィット、ワーストフィット、またはランダム選択）に関わらず、辞書式最大となる実行可能なリングの集合を見つけることが保証される条件を決定することである。この性質は**配置無関心性（placement obliviousness）**と呼ばれる。本論文は、強欲アルゴリズムが失敗する閾値 $\rho$（ある半径に対する、より小さい半径の総和の最大比率）を特定し、失敗を引き起こす幾何学的および組合せ論的な構造を特徴付けることを目的としている。

手法
著者は、厳密な幾何学的解析、組合せ最適化、および形式検証を組み合わせたハイブリッド・アプローチを採用している。

1. 幾何学的解析: 本論文は、デカルトの円定理、壁に接する円の角度分離基準、および「行（row）」構成（直径に沿って球をパッキングする手法）を含むディスク・パッキングの特性を利用している。主要なツールには、「行の補題（Lemma 3）」や、3つ以上のディスクのパッキング限界を定義する特定の「ポケット」構成（デカルト・ポケット）が含まれる。
2. 組合せ論的還元: 問題は、幾何学的レイヤー（兄弟関係にあるパッキングの実行可能性）と組合せ論的レイヤー（リングの選択）に分解される。著者は、超増加半径（各半径がそれより小さいすべての半径の総和を超える場合）の下では、組合せ論的レイヤーが自明となり、超加算的な目的関数に対して最適となる選択強欲法へと簡略化されることを証明している。
3. 交換引数（Exchange Arguments）: 配置無関心性を証明するために、著者は「親のアライメント（parent alignment）」技法を用いる。強欲な実行結果が最適な証拠（witness）と異なる場合、最大の不一致を示すリングの配置を交換し、空いたスペースに押し出されたより小さいリングを再挿入することで、実行可能性を維持したまま新しい証拠を構築できることを示す。
4. 形式検証: 本論文は計算による検証に大きく依存している。リポジトリには、代数的恒等式、多項式不等式、および特定の幾何学的証明書を形式化した122個のLean定理が含まれている。数値的なチェックはパラメータ空間の探索や反例の生成に使用されるが、著者は数値的な結果が記述された証明や形式的証明書の代わりにはならないことを明示している。

主要な貢献と結果

• 超加算性の二分法 (Theorem 6): 超増加半径の下では、選択強欲アルゴリズムは、あらゆる正の、厳密に増加する、超加算的な目的関数（接触面積を含む）に対して最適である。しかし、カーディナリティ（超加算的ではない）については、超増加半径であっても反例が存在する。
• 超増加半径における配置無関心性 (Theorem 9): 半径が超増加している場合、実行可能なコンテナを選択するあらゆるルールは、辞書式最大となる実行可能な集合をもたらす。これは、任意のコンテナの形状および寸法に対して成立する。
• $n=4$ における鋭利性 (Theorem 13): 配置無関心性は3つのリングまでは無条件で成立するが、4つのリングでは失敗する。本論文は、観測可能な状態（コンテナの容量、占有物、流入するリング）が2つの異なる問題インスタンス間で同一であるが、決定的なリングに対する最適な配置が異なる「ツイン・インスタンス（twin instances）」（Theorem 14）を構築している。これにより、いかなる決定論的な状態ベースのルールも普遍的に成功することはできず、ランダム化されたルールも少なくとも $1/2$ の確率で失敗することが証明される。
• 黄金の閾値 ($\tau = \phi$):
  • 加法的モデル: 加法的サロゲートモデルの閾値は、正確に $\rho = 1$ である。
  • 幾何学的モデル (ディスク): 本論文は、ディスク・コンテナにおける正確なグローバル閾値が黄金比 $\phi \approx 1.618$ であることを証明している。
  • 反例: $\rho = \phi + 3\varepsilon$ で配置無関心性が失敗する、4つのリングからなる「黄金のファミリー（golden family）」のインスタンスを構築している。これは、閾値がトリボナッチ定数 $T \approx 1.839$ であるという自然な予想を覆すものである。
  • 普遍的な保証 (Theorem 22): ディスクの有限の在庫に対し、$\rho \le \phi$ であれば、実行可能なコンテナを選択するいかなるルールを用いても、降順強欲な実行は辞書式最大となる集合を返す。これは、穴の半径が独立している場合でも成立する。
• トリボナッチの床（Tribonacci Floor）: グローバルな閾値は $\phi$ であるが、本論文は、特定の剛体的な幾何学的構成に関連するブロックされた交換を含む、4つのリングの「硬いサブファミリー（rigid subfamily）」において、$\rho$ の下限が正確にトリボナッチ定数 $T$ であることを特定している。これは、特定のクラスの入れ子状交換において、$\rho$ の下限がまさに $T$ であることを示している。
• 正方形のパン (Square Pans): 正方形のコンテナについては、特定の代数的なファミリーから導出された閾値の上限 $\tau_{\square} \le Y \approx 1.6845$ を確立している。正方形における正確なグローバル閾値は依然として未解決の問題である。
• 次元性: 次元 $d \ge 2$ の球状コンテナに関する結果は、次元削減補題を通じて平面の場合から転移される。配置無関心性は、あらゆる次元において最大3つのリングまで成立するが、4つで失敗する。また、別の議論により、最大5つのリングまでであれば、あらゆる次元において黄金の閾値による保証が成立する。
• 独立した穴と面積: 独立した穴の半径について、$\rho \le \kappa < 1$ の条件下で、正確な面積保証係数が $\min(1, \kappa^{-2} - 1)$ であることを証明しており、その鋭利な最適化閾値は $1/\sqrt{2}$ である。

意義と主張
本論文は、ヒューリスティックなアプローチを超え、正確な閾値と不可能性の結果を提供することで、入れ子状のリングの強欲なパッキングに関する構造的な問題を解決したと主張している。

• 強欲法の最適性: $\rho \le \phi$ という条件下では、降順強欲な実行が辞書式最大となる集合を返すことが保証される。ただし、面積最大化の最適性は、共通の幅と超増加半径という別途の仮定の下で成立する。
• 幾何学的 vs 組合せ論的: 本論文は、問題の困難さを、幾何学的レイヤー（一般にはNP困難）と、超増加条件によって解決される組合せ論的レイヤーへと切り離している。
• 予想の反駁: トリボナッチ定数が普遍的な閾値であるという予想を明確に否定し、代わりに黄金比が一般的なケースにおける正しい境界であり、トリボナッチは特定の硬いサブファミリーにおける床（下限）であることを示している。
• 厳密な検証: 著者は、彼らの結果が、記述された幾何学的証明とLeanによる形式化された代数的証明書の組み合わせによって裏付けられていることを強調しており、これを円充填（circle packing）の文献における純粋な数値的またはヒューリスティックな研究と区別している。

本論文は、ディスクの場合のグローバルな閾値は $\phi$ で確定しているものの、正方形のパンに関する正確な閾値、特定の硬い入れ子状交換ファミリーにおける詳細な下限、および完全な入力アクセスが許される場合の最適配置を見つけるための計算複雑性については、依然として未解決の問題が残っていると結論付けている。