元記事の一部移転のお知らせ（2026-06-16）
コラッツ予想の証明 － 未解決問題への挑戦（Qiita） で、
ある時点から、第 9 章の記事を更新できなくなったので、
該当記事の内容をこちらに掲載します。
【論文編 - 第 9 章（日本語草稿版）】
本稿は論文草稿である「コラッツ予想の証明 － 未解決問題への挑戦」の
「第 9 章 無限経路の排除」です。
必要に応じて、以下の本編または付録集を参照願います。
- コラッツ予想の証明 － 未解決問題への挑戦（Qiita）
- コラッツ予想の証明（§6）－ 未解決問題への挑戦
- コラッツ予想の証明（付録）－ 未解決問題への挑戦
- 付録I (周期 lift 構造有限検査証明書)
$$
\def\bm{\boldsymbol}
\def\alphastar{\alpha_\star}
\def\betastar{\beta_\star}
\newcommand\N{\mathbb{N}}
\newcommand\Z{\mathbb{Z}}
\newcommand\Q{\mathbb{Q}}
\newcommand\R{\mathbb{R}}
\newcommand\C{\mathbb{C}}
\newcommand\I{\mathrm{i}}
\newcommand\for[1]{\quad\mathrm{for}\quad #1}
\newcommand\setOne[1]{\left\{#1\right\}}
$$
目次
第 9 章 無限経路の排除
9.1 無限経路の存在可能性
9.1.1 無限経路の追加除算回数総和
9.1.2 無限経路が存在する必要条件
9.1.3 平均追加除算回数比率の定性的下限
9.2 整数点通過 closed-walk 分類と有効 LP 下界
9.2.1 有限状態空間と有限遷移集合
9.2.2 追加除算回数ラベル
9.2.3 LP 実数緩和と closed circulation
9.2.4 整数点通過 closed-walk
9.2.5 整数点通過可能 closed-walk の分類
9.2.6 有効 LP 可行解構造定理
9.3 構造下界と有限検査証明
9.3.1 位置付け
9.3.2 実軌道と有限検査 LP の対象
9.3.3 有効 LP 可行解構造定理と有限検査証明の整合性
9.4 有限検査証明による下界継承
9.4.1 有限状態経験フローによる LP 下界継承原理
9.4.2 有限検査証明への適用
9.4.3 軌道平均追加除算回数比率の下界
9.4.4 付録I との対応
9.5 無限経路に対するスケーリング下界
9.6 無限経路の存在否定
第 9 章 無限経路の排除
コラッツ遷移において、無限経路が存在しないことを示す。
定理8.3.2 より、コラッツ遷移には 自明なループ 以外の
循環経路 は存在しない。本章の議論では、これを前提条件とする。
9.1 無限経路の存在可能性
コラッツ遷移において、無限経路が存在しないことは自明ではない。
すなわち、無限経路は存在する可能性がある。
無限経路が存在する場合、補題1.6.2 より、分岐テーブルの代表値は
際限なく増大する。
最初に、考察対象である分岐テーブルの状況を明示しておく。
仮に、無限に遷移し続ける分岐テーブル系列 $\text{@}u_k$ が存在すると仮定する。
このとき、分岐テーブル系列に含まれる各奇数項 $u_k$ に対して、
分岐テーブル @$u_k$ が対応し、変換規則を定める。
ここで、$\forall n \in \mathbb{N}_{\text{odd}}$ に対して、分岐テーブル @n は一意に定まる。
また、$g(n) = 3n + 1$ は $\mathbb{N}_{\text{odd}}$ 上の単射であるため、
相異なる奇数 $n \neq m$ に対して $g(n) \neq g(m)$ が成り立つ。
よって、@n は各奇数ごとに同型でない（同型類が異なる）。
したがって、分岐テーブル系列が無限長であるならば、それに含まれる
@$u_k\ (k \ge 0)$ は可能性として無限の種類の構造を含む。
「6.5 コラッツ遷移不等式」で定式化されたコラッツ遷移不等式は、
任意の奇数入力に対して適用可能であるため、無限経路のあらゆる
候補系列にコラッツ遷移状態値としての形態に本質的な制限を加える。
コラッツ遷移不等式は、各奇数に対し、その後続の偶数遷移が必ず
$2$ の冪乗で割り切れること、また、その除算回数が十分大きくなる性質に
注目するものである。
これにより、どのような奇数系列であっても、コラッツ遷移が
繰り返されると、ある一定以上の減少傾向が顕在化してくる。
この事実が、無限長の非周期的経路の存在否定に関する適用に繋がる。
9.1.1 無限経路の追加除算回数総和
「6.5 コラッツ遷移不等式」より、以下が成り立つ。
\displaystyle 1 \le {V_n}{Q_n} \lt 2. \tag{1}
ここで、各記号は第 6 章の記法に従う。すなわち、
$V_n$ は第 $n$ 段階のコラッツ遷移状態値、$Q_n$ は初期値相対経過比率である。
初期値 $V_0 \in \mathbb{N}_{\mathrm{odd}}$ を固定し、各 $i = 1, 2, \ldots, n$ に対して、
分岐テーブル 内遷移回数
P_i \in \mathbb{Z}_{\gt 0}.
が定まるものとする。分岐テーブル内遷移回数の総和を
S_n := \sum_{i = 1}^{n}P_i.
とし、
R_n := \frac{2^{S_n}}{3^n}, \qquad
Q_n := \frac{R_n}{V_0}.
と定める。
なお、補題1.1.14 より、奇数に対するコラッツ遷移のリンク対象点の
値は必ず１回、２で割り切れる。この必ず発生する２による除算回数の
１回分がリンク回数と一対一に対応する。よって、$S_n \ge n$ である。
分岐テーブルの代表値は定義より奇数であり、mod 6 による分類では、
そのデータ型は (6k + 1)/(6k + 3)/(6k + 5) 型のいずれかである。
一方、(6k + 3) 型分岐テーブルには、補題1.2.4 よりリンク対象点が
存在しない。すなわち、他の分岐テーブルからのリンクは存在しない。
よって、遷移先の対象となるデータ型は (6k + 1)/(6k + 5) 型に限定される。
分岐テーブルの代表値が (6k + 5) 型の場合、リンク基準点に対する
$2$ による除算回数は $1$ 回、その他のリンク対象点に対する
$2$ による除算回数は $3$ 回以上である。
また、分岐テーブルの代表値が (6k + 1) 型の場合、
リンク基準点に対する $2$ による除算回数は $2$ 回、
その他のリンク対象点に対する $2$ による除算回数は $4$ 回以上である。
以上の結果より、リンク回数と一対一に対応する $2$ による除算回数
以外のコラッツ遷移における $2$ による除算回数の増加分は、
以下の場合に生じる。
・コラッツ遷移が (6k + 1) 型代表値を持つ分岐テーブルにリンクする。
・コラッツ遷移が (6k + 5) 型代表値を持つ分岐テーブルの
リンク対象点インデックス $\gt 1$ であるリンク対象点にリンクする。
よって、$S_n$ は、最低でも分岐テーブル間リンク回数 $n$ 以上なので、
$\exists x_n \in \mathbb{Z}_{\ge 0},\ S_n = n + x_n$ と書くことができる。
ここで、奇数コラッツ遷移における遷移回数 $n$ と
追加除算回数総和 $x_n$ について考える。このとき、
$n \to \infty$ において、$x_n$ に対して、以下の補題が成り立つ。
補題9.1.1 (非循環無限経路における追加除算回数総和の発散). 〇
奇数コラッツ遷移において、非循環無限経路が存在すると仮定する。
非循環無限経路における遷移回数を $n$、追加除算回数総和を $x_n$ とする。
このとき、$n \to \infty$ において、必ず $x_n \to \infty$ となる。
証明.
すべての奇数は、$\pmod 4$ において $(4k + 1)$ 型または $(4k + 3)$ 型の
いずれかに分類される。
補題1.2.7 および 補題1.2.8 より、$(4k + 3)$ 型を構成する
$(8k + 3)$ 型および $(8k + 7)$ 型の奇数コラッツ遷移は永続しない。
したがって、非循環無限経路が存在して奇数遷移回数 $n \to \infty$ と
なる場合、遷移列が $(4k + 3)$ 型のみに留まり続けることは不可能であり、
g(8k + 3) = 24k + 10 = 2(12k + 5) = 2(4(3k + 1) + 1).
なので、 $j = 3k + 1, (4j + 1)$ 型奇数を無限回通過しなければならない。
ここで、$(4k + 1)$ 型奇数に対するコラッツ演算 $g()$ の結果を評価する。
g(4k + 1) = 3(4k + 1) + 1 = 12k + 4 = 4(3k + 1).
上式より、$g(4k + 1)$ は必ず $4$ の倍数となる。すなわち、
奇数コラッツ遷移の直後に最低でも $2$ 回の $2$ による除算が発生する。
奇数コラッツ遷移においては、必ず $1$ 回の $2$ による除算が発生する。
よって、$(4k + 1)$ 型を通過する際、このデフォルト除算の $1$ 回を除いた
追加除算が最低 $1$ 回確実に発生し、追加除算回数総和 $x_n$ に加算される。
非循環無限経路においては、前述の通り $(4k + 1)$ 型を
無限回通過するため、その度に最低 $1$ 回の追加除算が累積され続ける。
ゆえに、$n \to \infty$ の極限において、追加除算回数総和 $x_n$ は
際限なく増大する。よって、$x_n \to \infty$ が成り立つ。
したがって、命題は成り立つ。
$\square$
9.1.2 無限経路が存在する必要条件
「9.1.1 無限経路の追加除算回数総和」、式(1) の各項を
$V_n \gt 0$ で割ると、以下となる。
\displaystyle \frac{1}{V_n} \le {Q_n} \lt \frac{2}{V_n}. \tag{2}
非循環無限経路が存在する場合、補題1.6.2 より、$n \to \infty$ のとき、
$V_n \to \infty$ なので、$\displaystyle \frac{1}{V_n} \to 0,\ \frac{2}{V_n} \to 0$ である。よって、
挟み撃ちの原理より、$n \to \infty$ のとき、式(2) の $Q_n$ の極限は収束する。
よって、$Q_n \to 0$ でなければならない。$Q_n = \frac{R_n}{V_0}$ かつ $V_0$ が定数なので、
これは、$R_n \to 0$ でなければならないことと同値である。
したがって、非循環無限経路が存在しないことを証明するためには、
$R_n \to 0$ となる可能性を排除しなければならない。
$n \to \infty$ のときの $R_n$ の極限状態の可能性を列挙すると、以下である。
(a) $R_n \to \infty$
(b) $\exists \alpha \in \mathbb{R} \ge 0, R_n \to \alpha$ //$\alpha$is a limit value at $n \to \infty$.
(c) $R_n \gt 0$ の極限は振動する。
非循環無限経路が存在する場合、補題1.6.2 より、$V_n \to \infty$ なので、
上記分類の (a), ($\alpha \gt 0$ in (b)) の場合はあり得ない。
何故ならば、それらの場合には、式(1) のコラッツ遷移不等式における
中間項 ${V_n}{Q_n}$ が無限大に発散するので成立しないからである。
また、上記分類上の (c) の場合、
\displaystyle \limsup_{n \to \infty} R_n \gt 0.
が成り立つので、$\exists \delta \gt 0$ が存在し、無数の $n$ に対して $R_n \ge \delta$ となる。
ところが、非循環無限経路が存在する場合は、
補題1.6.2 より $V_n \to \infty$ であるから、これらの $n$ について、
V_n Q_n = \frac{V_n}{V_0}R_n \ge \frac{V_n}{V_0}\delta \to \infty.
となり、式(1) に反する。よって、この場合もあり得ない。
したがって、式(2) の条件を満たして存在する可能性があるのは、
($\alpha = 0$ in (b)) の場合のみである。このとき、$R_n \to 0$ なので、
$Q_n \to 0$ の要請を満たす。
上記の論述を前提条件として、以下の補題が成り立つ。
補題9.1.2 (非循環無限経路が存在する必要条件). 〇
コラッツ遷移に 非循環無限経路 が存在するならば、
\displaystyle \limsup_{n \to \infty} \frac{x_n}{n} \le \alphastar.
が成り立つ。$n$ は奇数コラッツ遷移における遷移回数、
$x_n$ はコラッツ遷移 $n$ 回における 追加除算回数総和である。
証明.
コラッツ遷移に 非循環無限経路 が存在すると仮定する。
直前の議論より、このとき 経過比率
R_n = \frac{2^{S_n}}{3^n}.
は、
R_n \to 0 \qquad (n \to \infty).
を満たす必要がある。
ここで、任意の固定された整数
t \in \mathbb{Z}_{\gt 1}.
を取る。ただし、$t$ は $n$ に依存しない固定値である。
$R_n \to 0$ であるから、
\varepsilon = \frac{1}{2^t}.
に対して、ある自然数 $N_t$ が存在し、すべての $n \ge N_t$ について
\frac{2^{S_n}}{3^n} \lt \frac{1}{2^t}.
が成り立つ。
両辺は正であり、$\log_{2}$ は単調増加関数であるから、
底 $2$ の対数を取ると、すべての十分大きい $n$ に対して
S_n - n\log_{2}3 \lt -t.
である。したがって、
S_n - n\log_{2}3 + t \lt 0.
が成り立つ。
ここで
S_n = n + x_n.
を代入すると、
n + x_n - n\log_{2}3 + t \lt 0.
である。これを整理して、
x_n + t \lt n(\log_{2}3 - 1).
を得る。
記号定義により
\alphastar = \log_{2}3 - 1.
であるから、すべての十分大きい $n$ に対して
\frac{x_n + t}{n} \lt \alphastar.
が成り立つ。
よって、
\limsup_{n \to \infty}\frac{x_n + t}{n} \le \alphastar.
である。
一方、$t$ は $n$ に依存しない固定値であるから、
\frac{t}{n} \to 0 \qquad (n \to \infty).
である。したがって、
\limsup_{n \to \infty}\frac{x_n}{n}
=
\limsup_{n \to \infty}\frac{x_n + t}{n}.
が成り立つ。
以上より、
\limsup_{n \to \infty}\frac{x_n}{n} \le \alphastar.
である。
したがって、命題は成り立つ。
$\square$
9.1.3 平均追加除算回数比率の定性的下限
平均追加除算回数比率をコラッツ遷移の幅広い初期値に対して求めた
グラフを以下に示す。
［図9.1］x/n 分布（初期値：1 ～ 67,108,864）
上図から読み取れるように、コラッツ遷移の広範な初期値に対する
$x/n$ には、明らかに、ある共通の下限域が存在するように見える。
なお、この散布図の傾向として、$x/n$ の最小値はグラフ上で
全体として右肩下がりである。
一方、1 ～ 2,000,000 の奇数（100 万件）に対して下包絡線の
近似式を求めると、
\displaystyle y_{\text{lower}}(a) = 0.685423671497585 +\frac{1.9642698326766267 \times 10^{8}}{\bigl(a + 266145.7005208333\bigr)^{1.833333333333333}}.
である。上式に対するグラフを以下に示す。
この曲線の一般式は、以下である。
\displaystyle y_{\text{lower}}(a) = L + \frac{A}{(a + d)^{p}} \quad (A \gt 0,\ p \gt 0).
ここで、$a$ は初期値を表す変数であり、$L, A, d, p$ は近似式の定数である。
上式の極限を求めると、
\lim_{a \to \infty}y_{\text{lower}}(a) = L.
なので、水平漸近線は $y = L \quad (L \approx 0.6854236715)$ である。
したがって、有限個（$1$～$2,000,000$）の奇数の場合で $x_n/n$ 傾向を
見る限り、「［図9.1］x/n 分布」のグラフ傾向（※全体として右肩下がり）を
勘案すると、定性的に一様な下限が存在し、その理論値は $0.685$ 程度 と
予想できる。
9.2 整数点通過 closed-walk 分類と有効 LP 下界
本節では、奇数コラッツ遷移 を有限状態空間へ射影して得られる
有限有向グラフを考える。さらに、有限有向グラフ上で
線形計画法（LP）による実数緩和（LP 実数緩和）を考える。
ここでいう「LP 実数緩和」とは、本来は有限長の遷移列または
整数回数の辺通過として現れる対象を、各辺への非負実数重みの
割当てとして扱うことである。
すなわち、各辺 $e$ に非負実数重み $q_e$ を割り当て、
各状態で流入重みと流出重みが釣り合うという線形制約を課す。
必要に応じて、全辺重みの総和を $1$ に正規化して考える。
このようにして得られる対象は、個々の整数軌道そのものではなく、
有限状態グラフ上の実数重み付きフローである。
closed-walk とは、グラフ理論上の概念であり、有限状態グラフ上で、
始点と終点が一致する有限長の遷移列をいう。
closed-walk では、途中の状態または辺の重複を許す。
したがって、closed-walk は、一般に「閉路」と呼ばれる、
頂点または辺の重複を許さない循環構造とは区別される。
また、これは有限状態射影上の概念であり、それだけでは、
コラッツ遷移における循環経路を意味しない。
closed circulation とは、有限状態グラフの各辺に
非負の実数重みを割り当て、各状態において、流入重みの総和と
流出重みの総和が一致するような閉じたフローをいう。
したがって、closed circulation は LP 実数緩和上のフローであり、
一本の有限長遷移列そのものではない。
この意味で、closed circulation は closed-walk とも区別される。
ただし、有限有向グラフ上の closed circulation は、
非零重みを持つ辺の集合上で、closed-walk 型の成分に
分解して考えることができる。
したがって、closed circulation も有限状態射影上の概念であり、
それだけでは、コラッツ遷移における循環経路を意味しない。
本節では、奇数コラッツ遷移を有限状態空間へ射影したときに現れる
LP 実数緩和上の closed circulation と、コラッツ整数遷移として
有効な closed-walk 成分との関係を整理する。
LP 実数緩和上には、有限状態空間上では closed-walk に見えるものの、
コラッツ遷移の自然数閉路としては成立しない疑似 closed-walk 成分が
現れ得る。しかし、本稿で扱う対象はコラッツ整数遷移である。
したがって、このような LP 実数緩和上の疑似 closed-walk 成分は、
コラッツ遷移として最初から有効対象外であり、本文で用いる
有効 LP 下界の対象には含めない。
以下では、この当然の整数点通過条件を明示した上で、
コラッツ遷移として有効な closed-walk は、自明なループ
1 \to 4 \to 2 \to 1.
に由来する反復パターンのみに限られることを示す。
9.2.1 有限状態空間と有限遷移集合
法 $M$ を固定する。奇数コラッツ遷移を有限状態空間へ射影するため、
有限状態集合を
S_M.
と書く。ここで $S_M$ は、奇数整数を法 $M$ により分類した
有限個の状態から成るものとする。
有限遷移集合を
E_M.
と書く。各辺
e = (u, v) \in E_M.
は、有限状態 $u$ から有限状態 $v$ への候補遷移を表す。このとき、
\operatorname{src}(e) := u, \qquad
\operatorname{dst}(e) := v.
と書く。
各辺 $e \in E_M$ には、対応する奇数コラッツ遷移 における
$2$ による除算指数
t(e) \in \mathbb{Z}_{\gt 0}.
が付されているものとする。すなわち、具体的な奇数整数 $n$ に対して、
この辺が実現される場合、その一歩の奇数コラッツ遷移は
n \mapsto \frac{3n + 1}{2^{t(e)}}.
で与えられる。
ただし、有限状態グラフ上の辺や closed-walk は、
LP 実数緩和上の候補構造である。
したがって、それがコラッツ遷移として有効であるためには、
実際に整数点を通過する遷移として実現される必要がある。
9.2.2 追加除算回数ラベル
奇数コラッツ遷移において、除算指数 $t(e)$ のうち、
標準的な一回の除算を除いた部分を追加除算回数と呼ぶ。
各辺 $e\in E_M$ に対し、
x_E(e) := t(e) - 1.
と定める。
有限個の遷移列または closed-walk パターン $T$ に対し、
その追加除算回数総和は、含まれる辺の $x_E(e)$ の総和で与えられる。
9.2.3 LP 実数緩和と closed circulation
有限状態グラフ
G_M = (S_M, E_M).
上の LP 実数緩和可行流量を
q = (q_e)_{e \in E_M}.
とする。
LP 実数緩和可行流量とは、
\begin{aligned}
q_e &\ge 0 \qquad(e \in E_M), \\
\sum_{e \in E_M} q_e &= 1.
\end{aligned}
および任意の状態 $s \in S_M$ に対して
\sum_{\operatorname{src}(e) = s}q_e = \sum_{\operatorname{dst}(e) = s}q_e.
を満たす流量である。
この LP 実数緩和可行流量全体の集合を
\mathcal{Q}_M := \left\{
q \in \mathbb{R}_{ \ge 0}^{E_M}
\ \middle |\
\sum_{e \in E_M}q_e = 1, \quad
\sum_{\operatorname{src}(e) = s}q_e = \sum_{\operatorname{dst}(e) = s}q_e
\quad(\forall s \in S_M)
\right\}.
と書く。すなわち、$\mathcal{Q}_M$ は、
有限状態 LP 実数緩和上の closed circulation 集合である。
この LP で実際に求めるものは単なる可行流量の有無ではない。
各辺 $e$ に 追加除算回数 ラベル $x_E(e)$ を与え、可行流量
$q \in \mathcal{Q}_M$ に対して
\sum_{e \in E_M}q_e x_E(e).
を目的関数値とみなす。
その上で、この目的関数値を最小にする可行流量と、その最小値を求める。
すなわち、LP 実数緩和は、有限状態グラフ上の
closed circulation 全体の中で、平均追加除算回数比率が
最も小さくなる構造を探索する操作である。
この条件は、有限有向グラフ上の closed circulation 条件である。
したがって、LP 実数緩和可行流量は有限状態空間上で閉じたフローである。
補題9.2.1 (LP 可行流量の closed circulation 性). 〇
上記の意味での任意の LP 実数緩和可行流量 $q$ は、有限有向グラフ $G_M = (S_M, E_M)$ 上の closed circulation である。
証明.
LP 実数緩和可行流量の定義により、各辺流量は非負であり、
全流量は $1$ に正規化されている。さらに、任意の状態 $s \in S_M$ において、
流出流量の総和と流入流量の総和が一致する。
これは、有限有向グラフ上で、流量が生成も消滅もせず、
閉じたフローとして保存されていることを意味する。
したがって、$q$ は closed circulation である。
したがって、命題は成り立つ。
$\square$
有限有向グラフ上の closed circulation は、
有限個の directed closed-walk flow の非負結合として分解できる。
ただし、この分解は一般には一意ではない。
また、この分解に現れる closed-walk は、有限状態空間上で閉じている
という意味での閉路成分であり、それが直ちにコラッツ整数軌道として
有効な閉路であることを意味しない。
この分解を用いる理由は、LP 実数緩和上の可行流量を、
有限状態空間上の閉じたパターン単位へ分解して評価するためである。
LP は実数流量として closed circulation を許すため、
有限状態空間上では、整数軌道としては閉じていない
closed-walk 成分も非零重みを持つ成分として現れ得る。
したがって、次節以降では、有限状態空間上の closed-walk 成分と、
それがコラッツ整数遷移の正整数閉路として実現可能であることを
区別して扱う。
言い換えると、ここでの closed-walk 分解は LP 側の構造分解であり、
整数点通過条件はその後に課されるコラッツ遷移側の条件である。
この２段階を分けることにより、LP 実数緩和上に現れる
疑似 closed-walk 成分と、実際にコラッツ整数遷移として許される
closed-walk 成分を区別できる。
9.2.4 整数点通過 closed-walk
closed-walk パターンを
T = (t_1, t_2, \ldots, t_L).
とする。ここで、各 $t_i$ は対応する奇数コラッツ遷移の除算指数である。
まず、部分和を
S_0 := 0, \qquad
S_i := \sum_{r = 1}^{i}t_r
\qquad (i = 1, 2, \ldots, L).
とおく。このとき $S_T := S_L$ である。
さらに、$T$ に沿う合成写像の定数項を
C_T
:=
\sum_{j = 1}^{L}3^{L - j}2^{S_{j - 1}}.
と定める。すなわち、$C_T$ は、各段階の $+1$ 項が、
その後に残る $3$ 倍操作と、前段階までの $2$ べき分母を通して
合成写像の分子側へ集約された定数項である。
この定義により、$T$ に沿う形式的な合成写像は
F_T(n) = \frac{3^L n + C_T}{2^{S_T}}.
の形に書ける。
もし $T$ が出発点 $n$ に戻る閉路として成立するならば、形式的には、
F_T(n) = n.
でなければならない。したがって、
(2^{S_T} - 3^L)n = C_T.
であり、
n = \frac{C_T}{2^{S_T} - 3^L}.
が正の奇数整数として成立する必要がある。
特に、分母 $2^{S_T} - 3^L$ の符号および割り切り条件を含め、
上式の右辺が正の奇数整数として成立しなければならない。
これは、closed-walk パターンが整数閉路として実現可能であるための
固定点条件である。
ただし、この固定点条件だけを形式的に満たしても、
それだけで $T$ がコラッツ遷移軌道として有効な閉路であるとは限らない。
何故なら、パターン $T$ に沿う各段階で、対応する分岐条件
\operatorname{ord}_2(3n_{i - 1}+1) = t_i.
および中間値が正の奇数整数であることも同時に
満たさなければならないからである。
したがって、以下で用いる整数点通過条件は、単なる形式的な有理写像の
固定点条件ではなく、パターン $T$ に沿う奇数コラッツ遷移の分岐制約を
含んだ条件である。
コラッツ遷移を扱う以上、有効な closed-walk は整数点のみを
通過しなければならない。したがって、次の状態を導入する。
ある正の奇数整数 $n_0$ が存在し、列
n_0, n_1, \ldots, n_L.
が
n_i = \frac{3n_{i - 1} + 1}{2^{t_i}}, \qquad
\operatorname{ord}_2(3n_{i - 1} + 1) = t_i
\qquad(i = 1, \ldots, L).
を満たし、さらに
n_L = n_0.
となるとき、
integer\_point\_status(T) = allowed.
と書く。
一方、そのような正整数閉路として実現できないとき、
integer\_point\_status(T) = forbidden.
と書く。
ここで $forbidden$ は、追加的に禁止する操作を意味しない。
LP 実数緩和上では closed-walk 成分として現れ得るが、
コラッツ整数遷移の定義域である正の整数点上では閉路成分として
成立しないため、有効対象外である、という状態を表す。
この定義により、次の三つの条件は本稿の用語上は同じ内容を表す。
第一に、$integer_point_status(T) = allowed$ であること。
第二に、$T$ に対応する合成写像 $F_T$ が、パターン $T$ の
各中間分岐条件を満たす正の奇数整数固定点を持つこと。
第三に、$T$ がコラッツ整数遷移における正整数閉路として
成立することである。
以下の補題は、この同値性を定義展開として明示するものである。
補題9.2.2 (整数点通過可能性と実整数閉路の同値性). 〇
closed-walk パターン $T$ について、
integer\_point\_status(T) = allowed.
であることと、$T$ がコラッツ整数遷移における自然数閉路として
成立することは同値である。
証明.
まず、
integer\_point\_status(T) = allowed.
であると仮定する。
定義より、ある自然数である奇数 $n_0$ から出発して、
パターン $T$ に沿う奇数コラッツ遷移を $L$ 回行うと、再び $n_0$ に戻る。
したがって、
n_0 \mapsto n_1 \mapsto \cdots \mapsto n_{L - 1} \mapsto n_L = n_0.
は、コラッツ遷移における正整数閉路である。
逆に、$T$ がコラッツ遷移における正整数閉路として成立すると
仮定する。このとき、ある自然数である奇数 $n_0$ から出発して、
パターン $T$ に沿う奇数コラッツ遷移を $L$ 回行うと、
再び $n_0$ に戻る。したがって、上記の定義を満たし、
integer\_point\_status(T) = allowed.
である。
したがって、命題は成り立つ。
$\square$
9.2.5 整数点通過可能 closed-walk の分類
本節では、整数点通過可能な closed-walk を分類する。
ここで用いる論理は二段階である。まず、補題9.2.2 により、$integer_point_status(T) = allowed$ である closed-walk パターンは、
コラッツ整数遷移における正整数閉路として成立する。
次に、定理1.2.6 および定理8.3.2 により、
コラッツ遷移における正整数閉路は自明なループに限られる。
定理1.2.6 は、単一形態での自己参照型分岐テーブルが
ルートテーブル @1 のみであることを示す基礎結果であり、
循環経路排除論の起点である。
さらに、定理8.3.2 により、コラッツ遷移においては、自明なループ
1 \to 4 \to 2 \to 1.
を除いて循環経路は存在しない。
したがって、定理1.2.6 および定理8.3.2 が担う役割は、
整数点通過可能性の定義そのものではなく、
整数点通過可能な closed-walk を自明なループ由来に
分類する部分である。
定理9.2.3 (整数点通過可能 closed-walk の分類). 〇
closed-walk パターン $T = (t_1,\ldots,t_L)$ について、
integer\_point\_status(T) = allowed.
であるための必要十分条件は、$T$ が自明なループ
1 \to 4 \to 2 \to 1.
に由来する有限反復パターンであることである。
奇数遷移表示では、これは
T = (2)^k
=
(\underbrace{2, 2, \ldots, 2}_{k\ {\mathrm{times}}})
\qquad (k \ge 1).
である。ここで、$(2)^k$ は数値としての $2^k$ を意味するものではなく、
除算指数 $2$ が $k$ 回連続して現れる closed-walk パターンを表す
略記である。
すなわち、
integer\_point\_status(T) = allowed
\quad \Longleftrightarrow \quad
T \in \{(2)^k \mid k \ge 1\}.
証明.
まず、$T = (2)^k$ とする。このとき、正の奇数整数 $n_0 = 1$ に対して
g(1) = 3 \cdot 1 + 1 = 4 = 2^2.
であるから、
\operatorname{ord}_2(g(1)) = 2.
であり、
\frac{g(1)}{2^2} = 1.
が成り立つ。
したがって、$t_i = 2$ である各段階において、奇数コラッツ遷移は
1 \mapsto 1.
となる。これを $k$ 回繰り返しても、常に出発点 $1$ に戻る。
よって、$T = (2)^k$ は整数点通過可能であり、
integer\_point\_status(T) = allowed.
である。
逆に、
integer\_point\_status(T) = allowed.
であると仮定する。補題9.2.2 より、
$T$ はコラッツ整数遷移における正整数閉路を与える。
定理1.2.6 を起点とし、定理8.3.2 により、
コラッツ遷移においては、自明なループ
1 \to 4 \to 2 \to 1.
を除いて循環経路は存在しない。
したがって、$T$ が整数点通過可能であるならば、
その閉路は自明なループに由来するものでなければならない。
奇数遷移表示では、この自明なループは
1 \mapsto \frac{3 \cdot 1 + 1}{2^2} = 1.
であり、その除算指数は $2$ である。
よって、この自明なループを $k$ 回反復する closed-walk パターンは
(2)^k.
である。
したがって、ある $k \ge 1$ が存在して
T = (2)^k.
が成り立つ。
以上より、
integer\_point\_status(T) = allowed
\quad \Longleftrightarrow \quad
T \in \{(2)^k \mid k \ge 1\}.
である。
したがって、命題は成り立つ。
$\square$
系9.2.4 (非自明 closed-walk の無効性). 〇
closed-walk パターン $T$ が $(2)^k$ 型でないならば、
integer\_point\_status(T) = forbidden.
である。
すなわち、
T\notin\{(2)^k \mid k \ge 1\}
\quad \Longrightarrow \quad
integer\_point\_status(T) = forbidden.
である。
証明.
定理9.2.3 より、整数点通過可能な closed-walk パターンは
$(2)^k$ 型に限られる。したがって、$T$ が $(2)^k$ 型でないならば、
$T$ はコラッツ整数遷移として有効な閉路ではない。
よって、
integer\_point\_status(T) = forbidden.
である。
したがって、命題は成り立つ。
$\square$
9.2.6 有効 LP 可行解構造定理
本節では、有限状態 LP 実数緩和における closed-walk 成分のうち、
平均追加除算回数比率の計算対象となる有効 closed-walk 成分を確定し、
それにより有効 LP 可行解上の目的関数値が恒等的に $1$ となることを示す。
この結果より、後述の有効 LP 可行解構造定理が導出される。
LP 実数緩和上には、有限状態空間上では closed-walk に見えるものの、
コラッツ整数遷移の正整数閉路としては成立しない
疑似 closed-walk 成分が、可行解の成分として現れ得る。
しかし、平均追加除算回数比率は正整数上のコラッツ遷移に対して
定義される指標である。
したがって、この指標の計算対象となる closed-walk 成分は、
正整数コラッツ遷移として有効な closed-walk 成分に限られる。
ここで注意すべき点は、有限状態空間上の closed-walk パターンが、
実際の整数軌道中の有限区間として一時的に現れる可能性を
否定しているわけではない、ということである。
本節で有効対象外とするものは、そのような非閉路的な
有限区間ではない。有効対象外となるのは、LP 実数緩和上では
closed circulation の閉路成分として現れ得るが、
正整数上のコラッツ遷移として閉路を構成しないパターン、
すなわち LP 実数緩和上の疑似 closed-walk 成分である。
したがって、疑似 closed-walk 成分を平均追加除算回数比率の
計算対象に含めないことは、恣意的な枝刈りではない。
これは、LP 実数緩和により一時的に広がった対象を、
平均追加除算回数比率というコラッツ整数遷移上の指標の定義域へ
戻す操作である。
有効 closed-walk 成分とは、自然数コラッツ遷移として閉路を構成する
closed-walk 成分をいう。
すなわち、closed-walk パターン $T = (t_1, \ldots, t_L)$ が
有効 closed-walk 成分であるとは、ある正の奇数整数 $n_0$ が存在し、列
n_0, n_1, \ldots, n_L.
が
n_i = \frac{3n_{i - 1} + 1}{2^{t_i}},
\qquad
\operatorname{ord}_2(3n_{i - 1} + 1) = t_i
\qquad (i = 1, \ldots, L).
および
n_L = n_0.
を満たすことをいう。これは、これまでの記法の
integer\_point\_status(T) = allowed.
と同じである。
一方、有限状態空間上では closed-walk として現れていても、
上記の意味で正整数上のコラッツ遷移として閉路を構成しない成分を、
LP 実数緩和上の疑似 closed-walk 成分という。
各有効 closed-walk パターン $T$ に対し、$T$ に沿う一周あたりの
正規化フローを $q^T$ と書く。すなわち、$q^T_e$ は、$T$ の一周において
辺 $e$ が現れる回数を $T$ の長さで割った値である。
有効定常フロー集合を
\mathcal{Q}_M^{\mathrm{valid}} := \operatorname{conv}\{q^T \mid T \text{ は正整数コラッツ遷移として有効な closed-walk 成分}\}.
と定める。ここで $\operatorname{conv}$ は非負重みによる凸包を表す。
すなわち、$\mathcal{Q}_M^{\mathrm{valid}}$ は、正整数コラッツ遷移として有効な
closed-walk 成分のみから構成される正規化定常フロー全体である。
この定義により、$\mathcal{Q}_M^{\mathrm{valid}}$ は LP 実数緩和上の
全 closed circulation 集合 $\mathcal{Q}_M$ そのものではない。
$\mathcal{Q}_M^{\mathrm{valid}}$ は、$\mathcal{Q}_M$ の closed-walk 分解に現れる成分のうち、
正整数コラッツ遷移として有効なものだけから再構成される、
有効化された定常フロー集合である。
構造下界値を
\lambda_x^{\mathrm{str}} := \min_{q \in \mathcal{Q}_M^{\mathrm{valid}}}
\sum_{e\in E_M}q_e x_E(e).
と定義する。
ここでの上付きの $\mathrm{str}$ は「構造的」（structural）であることを表し、
これは有効 LP 可行解構造から得られる値である。
後続節での実軌道へ継承する検査下界値とは、役割を区別して扱う。
定理9.2.5 (有効 LP 可行解構造定理). 〇
任意の $q \in \mathcal{Q}_M^{\mathrm{valid}}$ に対して、
\sum_{e\in E_M}q_e x_E(e) = 1.
が成り立つ。
したがって、有効 LP 可行解に対する平均追加除算回数比率は
常に $1$ であり、構造下界値 $\lambda_x^{\mathrm{str}}$ は $1$ である。
証明.
$q \in \mathcal{Q}_M^{\mathrm{valid}}$ を任意に取る。
$\mathcal{Q}_M^{\mathrm{valid}}$ の定義より、$q$ は、正整数コラッツ遷移として有効な
closed-walk 成分 $T$ に対応する正規化フロー $q^T$ の
非負凸結合として表される。
したがって、まず有効 closed-walk 成分 $T$ を分類すればよい。
$T$ はコラッツ遷移として有効であるから、
ある正の奇数整数 $n_0$ から出発して、パターン $T$ に沿う
奇数コラッツ遷移を有限回行うと、再び $n_0$ に戻る。
すなわち、$T$ はコラッツ遷移における循環経路を与える。
一方、定理1.2.6 および定理8.3.2 により、
コラッツ遷移に存在する循環経路は、自明なループ
1 \to 4 \to 2 \to 1.
に限られる。
したがって、コラッツ遷移として有効な closed-walk 成分 $T$ は、
自明なループに由来する反復パターンでなければならない。
奇数コラッツ遷移では、自明なループは
1 \mapsto \frac{3 \cdot 1 + 1}{2^2} = 1.
であり、その２による除算回数は $2$ である。
よって、有効 closed-walk 成分 $T$ は、ある $k \ge 1$ に対して
T = (2)^k.
の形式である。
逆に、$T = (2)^k$ であれば、自然数の最初の奇数である $1$ から出発して、
各段階で
1 \mapsto \frac{3 \cdot 1 + 1}{2^2} = 1.
が成り立ち、$T$ はコラッツ遷移として有効な closed-walk 成分である。
以上より、有効 closed-walk 成分は、ちょうど
T = (2)^k \qquad (k \ge 1).
に限られる。
次に、この有効成分に対する平均追加除算回数比率を計算する。
$T = (2)^k$ とする。このとき、パターンの長さは $k$ であり、
各段階の除算指数はすべて $2$ である。したがって、総除算指数は
S_T = 2k.
である。
追加除算回数は、各奇数遷移における標準的な一回の除算を
除いた分であるから、$T$ の追加除算回数総和は
X_T = S_T - k = 2k - k = k.
である。
よって、$T = (2)^k$ の平均追加除算回数比率は
\frac{X_T}{k} = 1.
である。
したがって、有効 closed-walk 成分に対応する
任意の正規化フロー $q^T$ について、
\sum_{e \in E_M}q^T_e x_E(e) = 1.
が成り立つ。
任意の $q \in \mathcal{Q}_M^{\mathrm{valid}}$ は、このような $q^T$ の非負凸結合である。
各成分の目的関数値がすべて $1$ なので、その凸結合である $q$ についても
\sum_{e\in E_M}q_e x_E(e) = 1.
が成り立つ。
したがって、任意の有効 LP 可行解に対する平均追加除算回数比率の
計算値は常に $1$ である。
ゆえに、
\lambda_x^{\mathrm{str}} = \min_{q \in \mathcal{Q}_M^{\mathrm{valid}}}\sum_{e \in E_M}q_e x_E(e) = 1.
である。
したがって、命題は成り立つ。
$\square$
以上により、平均追加除算回数比率の計算対象となる有効 LP 可行解の
構造が確定した。すなわち、LP 実数緩和上には疑似 closed-walk 成分が
現れ得るが、コラッツ遷移として有効な closed-walk 成分は
自明なループに由来する自明な反復パターンのみである。
したがって、有効 LP 可行解上の目的関数値は下界として
$1$ を持つだけでなく、恒等的に $1$ となる。
なお、付録I では、この有効 LP 可行解構造定理に対応する
有限検査証明書および再現性資料を与える。
付録I は、本文の有効 LP 可行解構造定理で説明される構造下界値
$\lambda_x^{\mathrm{str}} = 1$ と整合する形で、実軌道から生じる有限状態経験フローに対して、
検査下界 $\lambda_x^{\mathrm{cert}} \ge 1$ が成立することを、
有限検査証明として独立に記録する役割を持つ。
9.3 構造下界と有限検査証明
§9.2では、有限状態 LP 実数緩和上に現れる closed circulation を、
コラッツ整数遷移として有効な closed-walk 成分と、
LP 実数緩和上の疑似 closed-walk 成分に分けた。
その結果、有効 closed-walk 成分は 自明なループ由来のものに
限られ、構造下界値として、
\lambda_x^{\mathrm{str}} = 1.
が得られることを示した。
一方、無限経路の存在排除において直接必要となるのは、
実際の無限軌道に沿う平均追加除算回数比率に対する下界である。
実軌道を有限状態空間へ射影したとき、その経験フローは
有限状態 LP の可行性を満たすが、その closed-walk 分解成分が
直ちに正整数閉路として有効であるとは限らない。
したがって、§9.2 の有効 closed-walk 分類だけを、
実軌道の経験フローへ無条件に適用してはならない。
そこで本章では、役割を次のように分ける。
第一に、有効 LP 可行解構造定理は、有限状態 LP において、
構造下界値 $\lambda_x^{\mathrm{str}} = 1$ が現れる構造的理由を与える。
すなわち、コラッツ整数遷移として有効な closed-walk 成分が
自明なループ由来に限られるため、構造下界値は、
\lambda_x^{\mathrm{str}} = 1.
となる。
第二に、実際の無限経路に対する下界継承は、
付録I の有限検査証明により保証する。
有限検査証明は、実軌道から生じる有限状態経験フローが満たす
可行条件を直接対象とし、その可行領域上で平均追加除算回数比率の
検査下界を与える。
以後、§9.4 以降で無限経路排除に直接用いる下界値を
\lambda_x^{\mathrm{cert}}.
と書く。上付きの $\mathrm{cert}$ は certificate を表し、
付録I の有限検査証明により実軌道へ継承される検査下界値である。
本文の最終的な無限経路排除では、この $\lambda_x^{\mathrm{cert}}$ を用いる。
したがって、本章における論理構成は、
\textbf{有効 LP 可行解構造定理}\text{による } \lambda_x^{\mathrm{str}} = 1 \text{ の理由説明}.
と
\textbf{有限検査証明}\text{による } \lambda_x^{\mathrm{cert}} \ge 1 \text{ の実軌道への下界継承}.
の二層からなる。
なお、ここでいう LP 実数緩和は、コラッツ遷移値そのものを
非整数点へ拡張するものではない。LP で緩和されるのは、
有限状態遷移集合上の経験フロー重み、または有効成分の混合係数である。
したがって、有限検査証明における LP 下界は、
非整数値軌道を評価しているのではなく、
実コラッツ整数軌道から射影される有限状態経験フローを対象とする。
また、有限検査証明による下界継承は、有限検査結果を非循環無限経路へ
直感的に外挿するものではない。任意の非循環無限経路から
有限状態経験フローを構成し、有限次元単体のコンパクト性により
部分列極限を取り、境界項が $N^{-1}$ の次数で消えることから
流量保存条件を得る。その上で、ラベル下界性および LP 下界性を
適用することで、実軌道平均に対する下界を得る。
9.3.1 位置付け
本節以降では、有効 LP 可行解構造定理を本文の説明原理として
採用しつつ、非循環無限経路に対する下界継承については、
付録I の有限検査証明を証明上の保証として用いる。
この構成では、有限検査証明は証明体系から外れるものではない。
むしろ、有効 LP 可行解構造定理が説明する構造下界値 $\lambda_x^{\mathrm{str}} = 1$ と
整合する検査下界 $\lambda_x^{\mathrm{cert}} \ge 1$ が、実軌道に対する
平均追加除算回数比率の下界として用いられることを保証する役割を担う。
ここで注意すべき点は、次である。
有限状態空間上の経験フローが closed circulation 条件を満たすことは、
通常の有限状態 LP 可行性を与える。しかし、それだけでは、
その closed-walk 分解成分が全て $\mathcal{Q}_M^{\mathrm{valid}}$ に属することを意味しない。
したがって、§9.2 の有効 closed-walk 分類と、
実軌道平均への下界継承を混同してはならない。
本章では、構造下界値 $\lambda_x^{\mathrm{str}}$ と検査下界値 $\lambda_x^{\mathrm{cert}}$ を役割上区別する。
両者は別々の目的の量であり、本文の有効 LP 可行解構造定理は
構造下界値 $\lambda_x^{\mathrm{str}} = 1$ を与え、
付録I の有限検査証明は、実軌道に対する検査下界 $\lambda_x^{\mathrm{cert}} \ge 1$ を与える。
すなわち、有効 LP 可行解構造定理は、値 $1$ の構造的理由を
説明し、付録I の有限検査証明は、少なくとも $1$ 以上の検査下界が
実軌道から生じる有限状態経験フローに対して適用可能であることを
保証する。
この役割分担により、有効 LP 可行解構造定理と有限検査証明は
競合せず、相補的に機能する。
9.3.2 実軌道と有限検査 LP の対象
法 $M$ を固定し、非循環無限経路を構成する奇数コラッツ遷移列を
n_0, n_1, n_2, \ldots.
とする。各 $i \ge 0$ に対し、
n_{i+1} = \frac{3n_i + 1}{2^{t_i}},
\qquad
t_i = \operatorname{ord}_2(3n_i + 1).
と書く。
各段階の追加除算回数を
A_i = t_i - 1.
とし、最初の $N$ 回の追加除算回数総和を
x_N := \sum_{i = 0}^{N - 1} A_i.
と定める。
各 $n_i$ を法 $M$ により有限状態空間 $S_M$ へ射影し、有限状態列
s_0, s_1, s_2, \ldots.
を得る。各遷移 $s_i \to s_{i + 1}$ は、有限遷移集合 $E_M$ の
何れかの辺に対応する。
付録I の有限検査証明では、実軌道から生じる、
これらの有限状態遷移列を対象として、次の性質を確認する。
- 有限被覆性：実際の奇数コラッツ遷移が、検査対象となる
有限遷移集合により被覆される。 - ラベル下界性：実際の追加除算回数が、対応する有限遷移ラベル
$x_E(e)$ により保存されるか、少なくとも下から評価される。 - 経験フロー可行性：無限に続く実軌道から得られる極限経験フローが、
有限検査 LP の可行条件を満たす。 - LP 下界性：有限検査 LP の可行領域上で、平均追加除算回数比率の
下界が $\lambda_x^{\mathrm{cert}} \ge 1$ を満たす。
これらは、§9.2 の $\mathcal{Q}_M^{\mathrm{valid}}$ に対する構造分類とは異なる役割を持つ。
§9.2 は、何故、構造下界値 $\lambda_x^{\mathrm{str}} = 1$ が現れるのかを説明する。
一方、付録I は、その下界が実軌道に対して適用可能であることを
有限検査証明として保証する。
9.3.3 有効 LP 可行解構造定理と有限検査証明の整合性
§9.2で得られた有効 LP 可行解構造定理は、LP 実数緩和上の
疑似 closed-walk 成分を除外し、コラッツ整数遷移として有効な
closed-walk 成分だけを考えると、構造下界値が
\lambda_x^{\mathrm{str}} = 1.
となることを示している。
一方、付録I の有限検査証明は、実軌道から生じる有限状態経験フローを
含む検査 LP 可行領域を対象として、
\lambda_x^{\mathrm{cert}} \ge 1.
を確認する。したがって、両者は互いに競合しない。
有効 LP 可行解構造定理は、有限検査証明で確認される検査下界
$\lambda_x^{\mathrm{cert}} \ge 1$ において、値 $1$ が基準として現れる構造的理由を説明し、
付録I の有限検査証明は、その下界が実軌道平均へ継承されることを
保証する。
本章では、以後、無限経路排除に直接用いる下界として $\lambda_x^{\mathrm{cert}}$ を用いる。
ただし、有効 LP 可行解構造定理により、対応する構造下界値は
$\lambda_x^{\mathrm{str}} = 1$ であり、付録I の検査下界 $\lambda_x^{\mathrm{cert}} \ge 1$ と整合する。
さらに、付録I で記録する有限検査証明では、
標準確認範囲 $M = 1024\sim65536$ において、
LP 実数緩和上に現れる非整数点通過パターン、すなわち、
正整数コラッツ遷移由来ではない無効パターンを除去した後、
残存する LP 可行構造が自明なループ由来の成分に限られることを
確認する。
この確認の意義は、特定の最大スケール $M = 65536$ が
単独で成功した点にあるのではなく、また、単に有限個の検査で
$\lambda_x^{\mathrm{cert}} \ge 1$ が得られたという数値的事実だけにあるのでもない。
より本質的には、本文の定理9.2.3 および定理9.2.5 が理論的に導いた
integer\_point\_status(T) = allowed
\quad \Longleftrightarrow \quad
T \in \{(2)^k \mid k \ge 1\}.
という有効 closed-walk 構造が、標準有限検査範囲全体で、
有限検査証明側にも同じ残存構造として確認された点にある。
具体的には、有限状態 LP 実数緩和上には、正整数コラッツ遷移の
閉路ではない疑似 closed-walk が可行構造として現れ得る。
しかし、付録I の有限検査では、これらの非整数点通過パターンを
無効成分として除外した結果、allowed として残る LP 可行構造は
自明なループ由来のものに限られ、非自明 allowed パターンは
検出されなかった。
この流れは、有効 LP 可行解構造定理が示す
「有効 closed-walk 成分は自明なループ由来に限られる」
という構造と一致している。
すなわち、本文定理が理論的に導いた残存構造を、
有限検査が標準範囲 $M = 1024 \sim 65536$ において再現確認した、
という関係になっている。
この有限範囲での再現確認は、有効 LP 可行解構造定理を
有限検査に置き換えるものではない。
本文では、定理1.2.6 および定理8.3.2 に基づく演繹的分類により
有効 LP 可行解構造定理を述べる。
一方、付録I は、その理論的分類が有限検査証明側でも
同じ構造として確認されること、および、実軌道から生じる
有限状態経験フローに対して、検査下界 $\lambda_x^{\mathrm{cert}} \ge 1$ が
成立することを記録する。
したがって、有限検査証明は、単なる数値的下界確認に留まらず、
本文構造と整合する有限範囲での再現確認としても機能する。
これにより、付録I は、
実軌道への下界継承を保証する有限検査証明であると同時に、
本文の有効 LP 可行解構造定理が示す構造の
有限範囲における再現記録としても位置付けられる。
9.4 有限検査証明による下界継承
本節では、付録I の有限検査証明が、なぜ実際の無限経路に沿う
平均追加除算回数比率の下界証明として機能するのかを、
本文側の一般定理として明示する。
ここで用いる有限検査証明は、有限個の計算結果を
未知の巨大整数領域へ経験的に外挿するものではない。
無限軌道から得られる有限状態経験フローを考え、
有限次元単体のコンパクト性により部分列極限を取り、
有限 prefix の始点・終点に由来する境界項が消えることによって
流量保存条件を得る。
そのうえで、有限検査 LP 可行領域上の下界を、実軌道平均へ戻す。
したがって、本節の論証は、有限次元の極限論法と線形最適化の
基本事実に基づく。
付録I は、この一般定理の仮定を、今回の Karp/LP 型有限検査に対して
具体的に確認・記録する資料として位置付けられる。
9.4.1 有限状態経験フローによる LP 下界継承原理
有限状態集合を $S$、有限遷移集合を $E$ とする。無限遷移列
s_0 \to s_1 \to s_2 \to \cdots.
が与えられ、各遷移 $s_i \to s_{i + 1}$ が $E$ の
いずれかの辺 $e_i$ に対応するとする。
各辺 $e \in E$ に実数ラベル $c(e)$ が付されているとする。
また、実際の軌道の各段階で評価したい量を $a_i$ とし、
対応する辺ラベルにより
a_i \ge c(e_i).
と下から評価されるとする。
最初の $N$ 回の遷移に対し、経験フローを
f_N(e) := \frac{1}{N}\#\{0 \le i \lt N \mid e_i = e\}
\qquad(e \in E).
と定める。$E$ は有限集合であるから、各 $f_N$ は有限次元単体
\Delta_E := \left\{
q \in \mathbb{R}_{ \ge 0}^{E}
\ \middle|\
\sum_{e \in E}q(e) = 1
\right\}.
に属する。したがって、任意の部分列に対して、
必要なら、さらに部分列を取ることにより、ある $f$ に対して
f_{N_j} \to f.
と仮定できる。
この極限 $f$ は、有限状態上の流量保存条件を満たす。
実際、任意の状態 $s \in S$ について、有限 prefix における
流出回数と流入回数の差は、始点および終点に由来する境界項だけである。
したがって、その差を $N_j$ で割った量は $N_j^{-1}$ の次数で消える。
よって、極限では、
\sum_{\operatorname{src}(e) = s}f(e) = \sum_{\operatorname{dst}(e) = s}f(e)
\qquad(s \in S).
が成り立つ。
以上より、極限経験フロー $f$ は、少なくとも全 closed circulation 領域
\mathcal{P}_{\mathrm{flow}} = \left\{
q \in \mathbb{R}_{ \ge 0}^{E}
\ \middle |\
\sum_{e \in E}q(e) = 1, \quad
\sum_{\operatorname{src}(e) = s}q(e) = \sum_{\operatorname{dst}(e) = s}q(e)
\quad(\forall s \in S)
\right\}.
に属する。
一方、実際の有限検査証明 で用いる LP 可行領域は、
全 closed circulation 領域そのものとは限らない。
検査対象に応じて、整数点通過条件や無効パターンの除外条件などが、
辺の除去、流量変数の零固定、またはその他の有限個の線形制約として
反映されることがある。そこで、以下では検査 LP 可行領域を
\mathcal{P} \subseteq \mathcal{P}_{\mathrm{flow}}.
と書く。ただし、この $\mathcal{P}$ は有限個の線形条件により定まる
有限次元 LP 可行領域であり、実軌道由来の極限経験フローを含むように
構成・検証されるものとする。
なお、有限被覆性は、検査 LP 可行領域 $\mathcal{P}$ そのものの
追加制約ではない。有限被覆性は、実軌道の各遷移が有限遷移集合 $E$ の
いずれかの辺として表現されることを保証する前提条件である。
この最後の条件を、本稿では経験フロー可行性 と呼ぶ。
すなわち、無限実軌道から得られる任意の極限経験フロー $f$ が
f \in \mathcal{P}.
を満たすことを、経験フロー可行性という。
定理9.4.1 (有限状態 LP 下界継承定理). 〇
上記の状況において、検査 LP 可行領域 $\mathcal{P} \subseteq \mathcal{P}_{\mathrm{flow}}$ が
与えられているとする。さらに、次の二条件を仮定する。
第一に、経験フロー可行性が成り立つ。
すなわち、任意の無限遷移列から得られる極限経験フロー $f$ は
f \in \mathcal{P}.
を満たす。
第二に、ある実数 $\lambda$ に対して、検査 LP 可行領域 $\mathcal{P}$ 上で
\sum_{e \in E}q(e)c(e) \ge \lambda
\qquad(q \in \mathcal{P}).
が成り立つ。
このとき、任意の無限遷移列に対して、
\liminf_{N \to \infty}
\frac{1}{N}\sum_{i = 0}^{N - 1}a_i \ge \lambda.
が成り立つ。
証明.
各 $N$ について、ラベル下界性 $a_i \ge c(e_i)$ より、
\frac{1}{N}\sum_{i = 0}^{N - 1}a_i \ge \frac{1}{N}\sum_{i = 0}^{N - 1}c(e_i) = \sum_{e \in E}f_N(e)c(e).
である。
左辺の $\liminf$ が $+\infty$ である場合、結論は自明である。
したがって、以下では左辺の $\liminf$ が有限値である場合を考える。
左辺の $\liminf$ に収束する部分列 $N_j$ を取る。
有限次元単体 $\Delta_E$ のコンパクト性により、
必要なら、さらに部分列を取り、
f_{N_j} \to f.
とする。上で述べた通り、極限 $f$ は流量保存条件を満たすため、
まず $f \in \mathcal{P}_{\mathrm{flow}}$ である。
さらに、経験フロー可行性の仮定により、
f \in \mathcal{P}.
である。
したがって、検査 LP 下界の仮定より、
\sum_{e \in E}f(e)c(e) \ge \lambda.
である。
また、$E$ は有限集合であり、目的関数
q \mapsto \sum_{e \in E}q(e)c(e).
は有限次元空間上の線形関数であるから、$f_{N_j} \to f$ に対して連続である。
したがって、
\sum_{e \in E}f_{N_j}(e)c(e) \to \sum_{e \in E}f(e)c(e).
が成り立つ。
以上より、
\liminf_{N \to \infty}
\frac{1}{N}\sum_{i = 0}^{N - 1}a_i \ge \sum_{e \in E}f(e)c(e) \ge \lambda.
である。
したがって、命題は成り立つ。
$\square$
9.4.2 有限検査証明への適用
定理9.4.1 を付録I の Karp/LP 型有限検査証明に適用する。
法 $M$ を固定し、奇数コラッツ遷移を有限状態空間 $S_M$ へ射影する。
検査対象となる有限遷移集合を $E_M$ とし、
各辺 $e\in E_M$ に追加除算回数ラベル $x_E(e)$ を付す。
付録I の有限検査証明は、本文の定理9.4.1 に対する
次の４条件を確認する資料である。
| 条件 | 本文定理9.4.1での役割 | 付録I で確認する内容 |
|---|---|---|
| 有限被覆性 | 実際の各奇数コラッツ遷移が有限遷移集合 $E_M$ のいずれかの辺へ対応すること。 | 検査スケール $M$ において、対象遷移が有限遷移集合により被覆されること。 |
| ラベル下界性 | 実際の追加除算回数 $A_i$ が、対応する有限遷移ラベル $x_E(e_i)$ により下から評価されること。 | 各辺ラベル $x_E(e)$ が実軌道上の追加除算回数の下界として妥当であること。 |
| 経験フロー可行性 | 無限実軌道から得られる極限経験フローが、付録I で定義する検査 LP 可行領域 $\mathcal{P}$ に属すること。 | 非負性、正規化条件、流量保存条件、および検査 LP で課す追加の有限制約を満たすこと。 |
| LP 下界性 | 検査 LP 可行領域 $\mathcal{P}$ の任意の可行解に対して、目的関数値が検査下界を下回らないこと。 | 検査下界 $\lambda_x^{\mathrm{cert}} \ge 1$ が成立すること。 |
この４条件により、付録I の有限検査証明は、
本文の有効 LP 可行解構造定理とは別に、実軌道から生じる
有限状態経験フローに対して下界を継承する役割を担う。
系9.4.2 (有限検査証明による平均追加除算回数比率の下界). 〇
付録I の有限検査証明が、有限被覆性、ラベル下界性、
経験フロー可行性、および LP 下界性を満たし、さらに検査下界
\lambda_x^{\mathrm{cert}} \ge 1.
を与えるとする。
このとき、任意の非循環無限コラッツ整数軌道に対して、
\liminf_{N \to \infty}\frac{x_N}{N}
\ge
\lambda_x^{\mathrm{cert}}
\ge 1.
が成り立つ。
証明.
非循環無限経路を構成する奇数コラッツ遷移列を
n_0, n_1, n_2, \ldots.
とする。各遷移は、有限被覆性により、
付録I で定義される有限遷移集合 $E_M$ のいずれかの辺に対応する。
各遷移で実際に発生する追加除算回数を $A_i$ とし、
対応する有限辺を $e_i$ とする。ラベル下界性により、各 $i$ について
A_i \ge x_E(e_i).
が成り立つ。
定理9.4.1 を、
S = S_M, \qquad E = E_M, \qquad c(e) = x_E(e), \qquad a_i = A_i.
として適用する。
経験フロー可行性により、無限実軌道から得られる極限経験フローは
付録I の検査 LP 可行領域 $\mathcal{P}$ に属する。
また、LP 下界性により、その可行領域上で、
\sum_{e\in E_M}q_e x_E(e) \ge \lambda_x^{\mathrm{cert}}.
が成り立つ。
したがって、定理9.4.1 より、
\liminf_{N \to \infty}\frac{x_N}{N}
\ge
\lambda_x^{\mathrm{cert}}.
である。
さらに、付録I の有限検査証明により、
\lambda_x^{\mathrm{cert}} \ge 1.
であるから、
\liminf_{N \to \infty}\frac{x_N}{N}
\ge
\lambda_x^{\mathrm{cert}}
\ge 1.
が従う。
したがって、命題は成り立つ。
$\square$
9.4.3 軌道平均追加除算回数比率の下界
本節では、コラッツ遷移軌道における平均追加除算回数比率に、
下界が存在することを示す。
系9.4.3 (軌道平均追加除算回数比率の下界). 〇
任意の非循環無限経路に対して、
\liminf_{N \to \infty}\frac{x_N}{N} \ge 1.
が成り立つ。
証明.
系9.4.2 より、
\liminf_{N \to \infty}\frac{x_N}{N}
\ge
\lambda_x^{\mathrm{cert}}
\ge 1.
である。
したがって、命題は成り立つ。
$\square$
9.4.4 付録I との対応
以上により、付録I の有限検査証明は、単なる計算記録や
有限範囲での経験的確認ではなく、本文の定理9.4.1 の仮定を
具体的に検査・記録する証明資料として位置付けられる。
本文側では、有限状態経験フローによる LP 下界継承原理を
定理9.4.1 として示した。付録I 側では、その定理を
LP 型有限検査に適用するために必要な有限被覆性、ラベル下界性、
経験フロー可行性、および LP 下界性を、
有限検査証明書、検査結果、および再現性資料により記録する。
この役割分担により、第 9 章本文は、有限検査証明が非循環無限経路への
下界証明として成立する理由を担保し、付録I は
その仮定を具体的検査として確認・記録する。
したがって、付録I の検査結果は、本文の非循環無限経路の
排除論証における $\lambda_x^{\mathrm{cert}} \ge 1$ の根拠として用いられる。
9.5 無限経路に対するスケーリング下界
前節までに、非循環無限経路に沿う平均追加除算回数比率が
$1$ を下回らないことを有限検査証明により確認した。
一方、有効 LP 可行解構造定理により、値 $1$ が現れる理由は、
コラッツ整数遷移として有効な closed-walk 成分が
自明なループ由来のみに限定され、
有効 LP 可行解上の目的関数値が恒等的に $1$ となることにある。
したがって、有限検査証明による下界継承と、
有効 LP 可行解構造定理による下界値の説明は整合している。
定理9.5.1（非循環無限経路に対するスケーリング下界）. 〇
任意の非循環無限経路に対し、その追加除算回数総和を $x_n$ と書く。
このとき、
\liminf_{n \to \infty}\frac{x_n}{n} \ge 1.
が成り立つ。特に、
\beta_{\text{inf}} := 1.
とおけば、
\beta_{\text{inf}} \gt \alphastar,
\qquad
\liminf_{n \to \infty}\frac{x_n}{n} \ge \beta_{\text{inf}}.
が成り立つ。
証明.
系9.4.3 より、任意の非循環無限経路を構成する
奇数コラッツ遷移列に対して、
\liminf_{n \to \infty}\frac{x_n}{n} \ge 1.
が成り立つ。
ここで
\beta_{\text{inf}} := 1.
とおく。記号定義より、
\alphastar = \log_{2}3 - 1 \lt 1.
であるから、
\beta_{\text{inf}} \gt \alphastar.
である。
よって、
\beta_{\text{inf}} \gt \alphastar,
\qquad
\liminf_{n \to \infty}\frac{x_n}{n} \ge \beta_{\text{inf}}.
が成り立つ。
したがって、命題は成り立つ。
$\square$
定理9.5.2（非循環無限経路の存在を排除する十分条件）. 〇
ある実数 $\beta_{\text{inf}}$ が存在し、
\beta_{\text{inf}} \gt \alphastar.
かつ、任意の非循環無限経路に対して、
\liminf_{n \to \infty}\frac{x_n}{n} \ge \beta_{\text{inf}}.
が成り立つならば、コラッツ遷移に非循環無限経路は存在しない。
証明.
背理法で証明する。
コラッツ遷移に非循環無限経路が存在すると仮定する。
このとき、補題9.1.2 より
\limsup_{n \to \infty}\frac{x_n}{n} \le \alphastar.
が必要である。
一方、仮定より
\liminf_{n \to \infty}\frac{x_n}{n} \ge \beta_{\text{inf}} \gt \alphastar.
である。したがって、
\liminf_{n \to \infty}\frac{x_n}{n} \gt \alphastar.
となる。
一般に、任意の実数列について
\liminf_{n \to \infty} a_n \le \limsup_{n \to \infty} a_n.
が成り立つ。ここで
a_n = \frac{x_n}{n}.
とおくと、上記の
\liminf_{n \to \infty}\frac{x_n}{n} \gt \alphastar.
と
\limsup_{n \to \infty}\frac{x_n}{n} \le \alphastar.
は同時に成立しない。したがって、矛盾する。
ゆえに、非循環無限経路は存在しない。
したがって、命題は成り立つ。
$\square$
9.6 無限経路の存在否定
前節の定理9.5.1 および定理9.5.2 より、
コラッツ遷移に非循環無限経路は存在しないことが従う。
定理9.6（非循環無限経路の存在否定）. 〇
コラッツ遷移に非循環無限経路は存在しない。
証明.
定理9.5.1 により、任意の 非循環無限経路 に対して、
\liminf_{n \to \infty}\frac{x_n}{n} \ge 1.
が成り立つ。
一方、
1 \gt \alphastar.
であるから、定理9.5.2 において、
\beta_{\text{inf}} = 1.
と取ることができる。
したがって、定理9.5.2 より、
コラッツ遷移に 非循環無限経路 は存在しない。
したがって、命題は成り立つ。
$\square$
////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////