Hamilton decompositions of all directed tori at odd modulus

技術的サマリー：奇数法における有向トーラスのハミルトン分解のためのプレフィックス数閉包定理

問題定義
本論文は、サイクルの有向直積に関するハミルトン分解の問題、特に向き付けられた等辺 $d$-トーラス $D_d(m) = \text{Cay}((\mathbb{Z}/m\mathbb{Z})^d, \{e_0, \dots, e_{d-1}\})$ について取り扱う。ハミルトン分解とは、グラフの $d|V|$ 個の弧を、ちょうど $d$ 個の互いに素な有向ハミルトン閉路に分割することを要求する。このようなグラフにおけるハミルトン性（単一の全域閉路の存在）はよく研究されているが、すべての次元 $d \ge 2$ および奇数法 $m \ge 3$ に対するより強力な弧分割問題は未解決であった。本論文は、すべての整数 $d \ge 2$ およびすべての奇数整数 $m \ge 3$ に対して、$D_d(m)$ が有向ハミルトン分解を許容することを証明することを目的としている。

手法
証明戦略は、「解決済み」の基底次元の集合に基づいて任意の次元の分解を構築することを可能にする、2 つの主要な閉包メカニズムに依存している。手法は、法 $m$ と次元 $d$ の関係に基づいて 2 つの枝に分けられる。

1. 高法数枝 ($m \ge d$):

   • ルートフラット証明書: 著者は「ルートフラット証明書」を導入する。これは層和 $S(x) = \sum x_i = 0$ 上で定義される構造であり、大域的な分解問題を、ルートフラット切片 $A_{d,m}$ 上の局所的な写像の構築に帰着させる。
   • プレフィックス座標と単一層因数分解: ルートフラット空間は、三角双射を介してプレフィックス座標に写像される。分解は、記号集合 $\{0, \Delta, 2, \dots, d-1\}$ に基づいてプレフィックス座標を置換する写像 $M^\sigma_c$ を用いて、層ごとに構築される。
   • プレフィックス数原始性: 重要な基準（定理 4.4）は、これらの層写像の合成が単一の閉路を形成することを保証する。これには、列で使用される記号に関する特定の数の条件が必要である：$\gcd(N_0, m) = 1$ および $k \ge 2$ に対して $\gcd(N_k - N_\Delta, m) = 1$。
   • 符号付き二進層: これらの数条件を $m \ge d$（ここで $d$ は奇数）に対して満たすため、著者は「プレフィックス許容数行列」を構築する。$q \ge 2$（ここで $m = (d-1)q + r$）の場合、行和と列和をバランスさせつつ必要な法単位を維持するために、符号付き二進層（要素が $\{-2, -1, 1, 2\}$ である行列）を利用する。制限された場合 $q=1$ については、別のマッチング補正が処理を行う。

2. 基底テール法交換枝 ($m < d$):

   • 基底テールリフト: 法が次元に対して小さい場合、本論文は「基底テール」構成を採用する。解決済みの基底次元 $b$（$D_b(m)$ が分解可能であるもの）を、次元 $T = d-b$ のテールと組み合わせる。
   • 円筒分解: 基底多重グラフは円筒に分解される。基底における活性弧には、テールアルファベットからの記号が割り当てられ、「局所記号交換」をスケジュールする。
   • 活性剰余スケジューリング: 「円筒交換貯水池」を用いて、著者は色間の記号の局所的な交換を実行するための特定の頂点を予約する。これにより、テール次元に必要なプレフィックス数原始性条件を満たすために、色記号数の剰余を調整することが可能となり、実質的に基底分解を完全な次元 $d$ へリフトする。

主要な貢献

• 2 つの閉包メカニズム: 本論文は、解決済み次元の集合 $S$ に対する 2 つの異なる閉包規則を確立する。
  • 積閉包: $a, b \in S$ ならば、$ab \in S$。
  • 後者閉包: $b \in S$ かつ $b \ge 5$ ならば、$2b + 1 \in S$。
• 高法数構成: 任意の事前解決済み基底次元に依存せず、符号付き二進層とプレフィックス数行列を用いた、奇数 $d \ge 5$ および $m \ge d$ に対する均一な構成。
• 基底テール法交換定理: 解決済みの基底 $b$ が与えられ、$d$ が法 $m$ における単位の和に分解可能であり、かつ特定のサイズ不等式（$T > b$ および $mb > m \cdot d \cdot T$）が成り立つ場合、$m < d$ に対する $D_d(m)$ を解く一般定理（定理 1.3）。
• 形式化: 結果には、すべての次元定理および証明の特定の依存構造を検証する Lean 形式化（Lean 4）が伴う。

結果
本論文は定理 1.5を証明する：すべての整数 $d \ge 2$ およびすべての奇数整数 $m \ge 3$ に対して、有向基底ケイリートーラス $D_d(m)$ は有向ハミルトン分解を許容する。

証明は、最小の基底次元の集合を特定することから始まる。

• 次元 2 と 3: 付録 B で証明済み（次元 2 は古典的；次元 3 は奇数 $m$ に対して証明済み）。
• 次元 5 と 7: 引用された外部定理（[22], [23]）から得られる。

閉包規則を用いると：

• 積閉包は次元 $4, 6, 8, 9, 10, \dots$ を生成する。
• 後者閉包（$b=5$ から開始）は $11$ を生成し、その後さらに高い奇数次元を生成する。
• 「2 進 -3 進間隔到達」論法（補題 10.3）は、任意の奇数 $d \ge 29$ に対して、基底テール条件を満たす解決済み基底 $b \in \langle 2, 3 \rangle$ が存在することを示す。
• 強い帰納法により、すべての $d \ge 2$ がカバーされることが確認される。

意義と主張
本論文は、奇数法を持つ等辺有向トーラスの全クラスに対するハミルトン分解問題を解決すると主張している。この研究は、先行文献（Trotter–Erdős、Curran–Witte など）で扱われたハミルトン性問題よりも強力な弧分割問題に対する解決策として位置づけられている。

著者は証明の構造的性質を強調する。

• 異なるが相補的なメカニズム（数行列対法交換）を通じて、高法数ケースと低法数ケースを統一している。
• 全次元の無限の問題を、有限の基底入力（2, 3, 5, 7）と 2 つの代数閉包演算に帰着させている。
• 機械検証可能な形式化の組み込みは、特に基底テール枝における複雑な数え上げとマッチング条件を含む、複雑な組合せ論的議論の検証アーティファクトとして機能する。

本論文は、偶数法や非等辺トーラスに対する問題の解決を主張するものではなく、またこの特定の分解問題の理論的解決を超えた新たな応用を提案するものでもない。その意義は、指定されたグラフクラスに対する結果の完全性と、提供された厳密な形式的検証にある。