元記事の一部移転のお知らせ（2026-09-15）
コラッツ予想の証明 － 未解決問題への挑戦（Qiita） で、
ある時点から、それ以上は記事を更新し難くなったので、
該当記事の付録部分をこちらに掲載します。
【論文編 - 付録集（日本語草稿版）】
本稿は、「コラッツ予想の証明 － 未解決問題への挑戦」の付録集です。
必要に応じて、以下の本編を参照願います。
- コラッツ予想の証明（§1）－ 未解決問題への挑戦（Qiita）
- コラッツ予想の証明（§6）－ 未解決問題への挑戦
- コラッツ予想の証明（§9）－ 未解決問題への挑戦
- コラッツ予想の証明（付録I）－ 未解決問題への挑戦
付録目次
第 5 章 コラッツ遷移の基本分類体系
5.1 正規化作用
5.2 正規化有限接頭辞単位
5.3 有限接頭辞列表示
5.4 理論本体に残す構造状態と分枝細分化文脈
5.5 遷移パターンカタログ
5.6 補助内部節点
5.7 (8k + 3) 型開始部分
5.8 (8k + 7) 型連鎖部分
5.9 (8k + 1) 型連鎖部分
5.10 D_9 の初期分解
5.11 D_{96, 31} の分類
5.12 M-core
5.13 基準値起点有限接頭辞の分類
5.14 実シーケンスに対する確認範囲
5.15 実シーケンス確認との関係
5.16 複合パターンカタログ
5.17 S3[11] 型遷移の局所増減判定
5.18 本章の位置付け
第 5 章 コラッツ遷移の基本分類体系
本章では、奇数コラッツ遷移を、分岐テーブルグループの
基準値を起点とする有限接頭辞として捉え、その各位置を
有限個の構造状態・分枝細分化文脈・局所遷移テンプレートへ分類するための枠組みを
与える。
ここで用いるのは、既に本文で確立した、1.2.7 節で与えた各データ型の
奇数遷移パターン、1.2.9 節で整理した $(8k + 7)$ 型遷移の性質、および
「1.4.1 分岐テーブルグループの定義」で与えた分岐テーブルグループの
基準値の位置付けである。
任意の分岐テーブルグループの基準値 $b$ を起点とする
奇数コラッツ遷移列を、
\begin{aligned}
u_0 &= b, \\
u_{j + 1} &= R(u_j)
\qquad (j \ge 0).
\end{aligned}
とする。
任意の有限整数 $r \ge 0$ に対し、
u_j \not \equiv 5 \pmod 8 \qquad (0 \le j \lt r).
を満たす有限列
u^{[r]} = (u_0, u_1, \ldots, u_r).
を、本章では基準値起点有限接頭辞と呼ぶ。
この定義は、$u_r$ が $(8k + 5)$ 型であることを要求しない。
したがって、$(8k + 5)$ 型への到達の有無にかかわらず、
到達前の任意の有限段階に対して、基準値起点有限接頭辞を
考えることができる。
一方、ある有限整数 $q \ge 0$ が存在して、
\begin{aligned}
u_j &\not \equiv 5 \pmod 8
\qquad (0 \le j \lt q), \\
u_q &\equiv 5 \pmod 8.
\end{aligned}
が成立するとき、$u_q$ は当該遷移列で最初に出現する $(8k + 5)$ 型である。
この場合に限り、有限区間
u^{[q]} = (u_0, u_1, \ldots, u_q).
を基準値間シーケンスと呼び、その有限列表示を
基準値間シーケンス列と呼ぶ。
なお、端点シーケンスは、コラッツ遷移端点（３の奇数倍または
$(8k + 5)$ 型）からコラッツ遷移端点（$(8k + 5)$ 型）への列を指し、
本章でいう基準値間シーケンスとは区別する。
すなわち、本章では基準値間シーケンスの存在をあらかじめ仮定せず、
実際に $(8k + 5)$ 型へ到達した場合に、その到達済み有限接頭辞を
基準値間シーケンスとして確定する。
また、$(8k + 5)$ 型へ到達した場合には、その到達値を所属する
分岐テーブルグループの基準値へ正規化し、
その基準値を起点として同じ分類処理を再開する。
この正規化は、$(8k + 5)$ 型への到達が実際に生じた場合に適用する
条件付きの処理であり、すべての基準値が $(8k + 5)$ 型へ到達することを
前提としない。
ここで、本章の分類体系に対して少なくとも次の２点が問題となる。
第１に、$(8k + 7)$ 型はメルセンヌ数型を含み、内部に既知の尾部構造を
持つとはいえ、どのようにして有限分類体系の内部へ還元されるのか？
第２に、$(8k + 1)$ 型は $(8k + 1)$、$(8k + 3)$、$(8k + 5)$、$(8k + 7)$ の
全型へ分岐し得るため、その局所分岐を経ても分類体系が閉じるのか？という点である。
本章の目的は、これらの疑問に対して、任意の基準値起点有限接頭辞を
有限個の構造状態、分枝細分化文脈、および exact token の有限連結へ
還元することで応える点にある。
まず、各基準値起点有限接頭辞の各位置を、
$S_3$、$S_7$、$L_1$、$M\text{-core}$、$C_5^{\mathrm{Norm}}$ という
5 種の構造状態へ正規化する。
これとは別に、$L_1$ の L1[9] 後続枝に対する選別のため、
$D_9$ および $D_{96, 31}$ を分枝細分化文脈として用いる。
これらの文脈は奇数コラッツ遷移を消費せず、後続の exact token を
一意に選択するための判定段階として働く。
次に、実際の奇数コラッツ遷移を有限個の exact token 列として表し、
その有限連結を遷移パターンカタログとして管理する。
これにより、基準値起点有限接頭辞としての被覆と、
その組合せによる閉包性を本文中で明示的に示す。
以下では、まず正規化作用と正規化有限接頭辞単位を定義し、
続いて、構造状態、分枝細分化文脈、および遷移パターンカタログを与える。
その上で、$S_3$、$S_7$、$L_1$、$D_9$、$D_{96, 31}$、$M\text{-core}$ の
各処理と出口を順に記述し、最後に基準値起点有限接頭辞
全体の分類と閉包性を示す。
5.1 正規化作用
本章では、基準値起点有限接頭辞中の各位置に与える構造状態と、
局所枝をさらに選別するための分枝細分化文脈を区別する。
本章で用いる構造状態は、
S_3, \quad S_7, \quad L_1, \quad M\text{-core}, \quad C_5^{\mathrm{Norm}}.
の 5 種である。
ここで、$S_3$ は $(8k + 3)$ 型開始部分、$S_7$ は $(8k + 7)$ 型のうち
新規 $M\text{-core}$ 入口として扱わない連鎖部分、$L_1$ は $(8k + 1)$
型連鎖部分、
$M\text{-core}$ はメルセンヌ数型の決定論的下降部分、
$C_5^{\mathrm{Norm}}$ は $(8k + 5)$ 型到達位置を表す。
一方、$D_9$ および $D_{96, 31}$ は構造状態ではない。
これらは、L1[9] の後続枝を合同条件により選別し、後述する exact token を
一意に決定するための分枝細分化文脈として用いる。
したがって、$D_9$ および $D_{96, 31}$ の文脈移行そのものは、
新たな奇数コラッツ遷移を消費しない。
また、分枝細分化文脈は後述する token 選択において構造状態より優先されるが、
それ自体が正規化作用 $\mathcal{N}$ の値になるものではない。
定義5.1.1 (正規化作用).
奇数コラッツ遷移列の基準値起点有限接頭辞
u = (u_0, u_1, \dots, u_r).
に対し、各位置 $i\ (0 \le i \le r)$ を、その位置が属する構造に応じて
S_3, \quad S_7, \quad L_1, \quad M\text{-core}, \quad C_5^{\mathrm{Norm}}.
のいずれかへ割り当てる写像を正規化作用と呼び、
\mathcal{N}(u, i).
で表す。
正の奇数 $n$ に対し、
m(n) := \mathrm{ord}_2(n + 1) + 1.
とおく。$n + 1 = 2^{m(n) - 1}(2t + 1)$ と一意に書けるので、
n = 2^{m(n)}t + \bigl(2^{m(n) - 1} - 1\bigr) = M_{m(n)}(t).
と一意に表される。
したがって、現在位置が既に開始している $M\text{-core}$ の内部位置でない場合、
新規 $M\text{-core}$ 入口となる条件は
m(n) \ge 6.
であり、これは
n \equiv 31 \pmod {32}.
と同値である。
ここで、$m = 3$ の場合は
M_3(t) = 8t + 3.
であるから $S_3$ に含まれる。
$m = 4$ の場合は
M_4(t) = 16t + 7.
であるから $S_7$ に含まれ、
R(16t + 7) = 24t + 11 = 8(3t + 1) + 3 = M_3(3t + 1).
により次の奇数位置は $S_3$ に入る。さらに、
M_5(t) = 32t + 15.
は 表5.C1 の exact token S7[15] の適用対象であり、
R(32t + 15) = 48t + 23 = 16(3t + 1) + 7.
であるから、外部から直接現れる $m = 5$ は $S_7$ の継続枝として処理できる。
したがって、$M\text{-core}$ の外部から直接現れる $m = 3, 4, 5$ の
メルセンヌ数型を新規入口とはせず、新規入口は $m \ge 6$ に限る。
一度 $m_0 \ge 6$ の $M_{m_0}(t_0)$ から $M\text{-core}$ の処理を開始した場合には、
補題5.12.1 で示す決定論的な階層下降に従い、
M_{m_0}(t_0) \to M_{m_0 - 1}(t_1) \to \cdots \to M_3(t_{m_0 - 3}) \to M_2(K).
を一つの M macro token として追跡する。
このとき、下降途中の $m = 5, 4, 3$ の位置を外部の $S_7, S_3$ として
途中で再 token 化することはしない。
終端値 $M_2(K) = 4K + 1$ は M token の終端値であり、token 完了時に
$K$ が偶数なら $L_1$、奇数なら $C_5^{\mathrm{Norm}}$ へ引き渡す。
したがって、$M_2(K)$ は M token の内部計算では追跡対象に含まれるが、
正規化された処理状態としては token 完了後の出口状態を用いる。
正規化作用は、次の優先順位で定める。
(1) 位置 $i$ が、既に開始している $m_0 \ge 6$ の $M\text{-core}$ 下降列のうち、
入口 $M_{m_0}(t_0)$ から $M_3(t)$ までの位置に属するときは、
$\mathcal{N}(u, i) = M\text{-core}$ とする。
(2) (1) に該当しない位置で、$u_i \equiv 31 \pmod {32}$ のときは、
新規 $M\text{-core}$ 入口として $\mathcal{N}(u, i) = M\text{-core}$ とする。
(3) 上記以外の場合、$u_i \equiv 5 \pmod 8$ のとき、$\mathcal{N}(u, i) = C_5^{\mathrm{Norm}}$ とする。
(4) 上記以外の場合、$u_i \equiv 1 \pmod 8$ のとき、$\mathcal{N}(u, i) = L_1$ とする。
(5) 上記以外の場合、$u_i \equiv 3 \pmod 8$ のとき、$\mathcal{N}(u, i) = S_3$ とする。
(6) 上記以外の場合、$u_i \equiv 7 \pmod 8$ のとき、$\mathcal{N}(u, i) = S_7$ とする。
なお、$D_9$ または $D_{96, 31}$ の分枝細分化文脈が有効な位置では、
$\mathcal{N}(u, i)$ 自体は上記規則で定まるが、exact token の選択では
規則5.5.3 により文脈側の選別を優先する。
特に $D_{96, 31}$ 文脈の現在値 $96k + 31$ は構造状態としては
$M\text{-core}$ に属するが、通常の M token より先に D31 系 token を選択する。
補題5.1.2 (正規化作用の一意性).
任意の基準値起点有限接頭辞 $u = (u_0, \dots, u_r)$ と任意の位置 $i$ に対し、
$\mathcal{N}(u, i)$ は一意に定まる。
証明.
各位置 $i$ に対し、まず既に開始している $M\text{-core}$ 下降列の
$M_{m_0}$ から $M_3$ までへの所属を判定する。
該当するときは (1) により一意に $M\text{-core}$ と定まる。
次に、(1) に該当しない位置について、$u_i \equiv 31 \pmod {32}$ ならば
(2) により一意に新規 $M\text{-core}$ 入口と定まる。
ここまでに該当しない位置は正の奇数であり、
u_i \equiv 1, 3, 5, 7 \pmod 8.
のいずれかに一意に属する。さらに (2) に該当しなかった $(8k + 7)$ 型位置は
$32k + 31$ 型ではないので、(6) の $S_7$ と新規 $M\text{-core}$ 入口が重なることもない。
したがって、(3)～(6) のいずれかが唯一適用される。
分枝細分化文脈は $\mathcal{N}$ の値ではなく、後段の token 選択にのみ作用するため、
$\mathcal{N}$ の一意性を損なわない。
したがって、命題は成り立つ。
$\square$
5.2 正規化有限接頭辞単位
本節では、基準値起点有限接頭辞を同一構造状態が続く最大区間へ分割し、
その単位を定義する。
定義5.2.1 (正規化有限接頭辞単位).
基準値起点有限接頭辞 $u = (u_0, \dots, u_r)$ の連続区間
u[a:b] = (u_a, u_{a + 1}, \dots, u_b) \qquad (0 \le a \le b \le r).
であって、区間内のすべての位置に対して $\mathcal{N}(u, i)$ が同一であり、
かつ、この性質を保ったまま前後に延長できない最大の区間を
正規化有限接頭辞単位と呼ぶ。
ここで用いる $\mathcal{N}$ は構造状態のみを表すので、
$D_9, D_{96, 31}$ の分枝細分化文脈や exact token の境界は、
正規化有限接頭辞単位の境界そのものを定めるものではない。
exact token 化は、構造状態と文脈を併用して 規則5.5.3 で別に定める。
補題5.2.2 (正規化有限接頭辞単位の存在).
任意の基準値起点有限接頭辞
u = (u_0, u_1, \ldots, u_r).
は、有限個の正規化有限接頭辞単位に分割できる。
証明.
補題5.1.2 により、基準値起点有限接頭辞の各位置には
一意なラベル $\mathcal{N}(u, i)$ が付く。
基準値起点有限接頭辞は定義より有限列であるから、
隣接位置でラベルが変化する箇所は有限個しかない。
したがって、同一ラベルが続く最大区間毎に切り分ければ、
有限個の正規化有限接頭辞単位に分割できる。
したがって、命題は成り立つ。
$\square$
5.3 有限接頭辞列表示
本節では、前節で定義した正規化有限接頭辞単位により、
基準値起点有限接頭辞を有限列として表示する。
補題5.3.1 (有限接頭辞列表示の存在).
任意の基準値起点有限接頭辞
u = (u_0, u_1, \ldots, u_r).
は、有限個の正規化有限接頭辞単位の列として表示できる。
証明.
補題5.2.2 により、任意の基準値起点有限接頭辞は
有限個の正規化有限接頭辞単位に分割できる。
これらを出現順に並べれば、基準値起点有限接頭辞は
正規化有限接頭辞単位の有限列として表示される。
したがって、命題は成り立つ。
$\square$
5.4 理論本体に残す構造状態と分枝細分化文脈
本章で理論本体の構造状態として用いるのは、次の 5 種である。
S_3, \quad S_7, \quad L_1, \quad M\text{-core}, \quad C_5^{\mathrm{Norm}}.
それぞれの役割は、次の通りである。
- $S_3$：$(8k + 3)$ 型開始部分。
- $S_7$：$(8k + 7)$ 型の内、新規 $M\text{-core}$ 入口として正規化されない連鎖部分。
- $L_1$：$(8k + 1)$ 型連鎖部分。
- $M\text{-core}$：$m_0 \ge 6$ の新規入口から始まるメルセンヌ数型下降部分。
- $C_5^{\mathrm{Norm}}$：$(8k + 5)$ 型到達位置。
これとは別に、局所枝を exact token へ細分化するための分枝細分化文脈として、
D_9, \quad D_{96, 31}.
を用いる。
$D_9$ は L1[9] の実遷移後に開かれる文脈であり、
$D_{96, 31}$ は $D_9$ の $96k + 31$ 分枝に対して開かれる追加文脈である。
これらの文脈移行自体は奇数コラッツ遷移を消費しない。
実際の処理では、構造状態と分枝細分化文脈を同一階層の状態として扱わない。
構造状態は正規化作用 $\mathcal{N}$ により各位置へ付与され、
分枝細分化文脈は必要な位置で exact token の選択を上書きする。
この三層構造を、図5.1 に示す。
図5.1 (構造状態・分枝細分化文脈・exact token の処理図).
図5.1 において、実線は exact token が 1 回以上の奇数コラッツ遷移を消費する
処理を表し、破線は遷移を消費しない文脈移行または構造状態への引渡しを表す。
なお、$32k + 31$ 型は 定義5.1.1 の新規入口条件により、正規化段階で直接
$M\text{-core}$ に割り当てられるため、$S_7$ から $M\text{-core}$ への token 辺として描かない。
また、$D_{96, 31}$ 文脈の M-core 帰着枝は
(384k + 127) \cup (384k + 319) = 192k + 127.
であるため、exact token D31[M] として一つに扱う。
5.5 遷移パターンカタログ
本章では、奇数コラッツ遷移の局所分類と、再利用する登録複合パターンの
認識を遷移パターンカタログにより管理する。
exact token の辞書を 表5.C1 に与え、複合パターンの厳密な登録形は
表5.C2b を正本とする。表5.C2a は、C2b の exact 正規形から機械的に得られる
比較用の coarse 表記であり、照合の正本とはしない。
ここで用いる各表は、本文中で行う直接の合同計算と奇数コラッツ遷移の計算に
基づいて得た有限分岐表をカタログとして整理したものである。
定義5.5.1 (遷移パターンカタログ).
本章でいう遷移パターンカタログとは、奇数コラッツ遷移に現れる有限個の
登録 token と、それらの有限連結を代表枝とともに一覧化したものである。
カタログは、次の 3 層から成る。
- exact token カタログ：カタログ照合で用いる有限な登録 token の辞書。
- 複合パターンカタログ（exact 版）：exact token 列による厳密な登録形。
-
複合パターンカタログ（coarse 比較表記）：exact
版から定める比較用の射影表記。
ここでいう exact token は、数学的意味での「最小単位」を意味しない。
各 token は、本章の有限分類で再利用する局所遷移テンプレートを
一意に識別するための登録単位であり、1 回の奇数遷移を表すものと、
複数回の奇数遷移をまとめた macro token の双方を含み得る。
複合パターンの mode は、その枝までに継承された合同条件と、
当該 exact token 列および帰着先を一様に確定するために必要な合同条件との
最小公倍数として設定する。以下、この登録値をカタログ登録 modeと呼ぶ。
カタログ登録 mode は、局所遷移だけを単独で記述する最小の法を
意味するものではなく、その枝に至るまでの分類文脈として
必要な合同条件を保持する。
一方、token 統合等により過去の細分化条件が不要になった場合には、
継承文脈を保持できる範囲で不要な細分化を除去する。
本章で用いる exact token は、次の 15 種である。
S3[3], S3[11], S7[7], S7[15],
L1[1], L1[9], L1[17], L1[25],
D55, D79[79], D79[175],
D31[31], D31[223], D31[M], M.
D9 および D_{96,31} は exact token ではなく、
exact token を選別するための分枝細分化文脈である。
また、C5 は終端構造状態であって exact token ではない。
表5.C1 (exact token カタログ).
| ID | exact token | 適用状態／文脈 | 定義的条件 | 一様局所遷移／還元 | coarse alias | 処理先／出口規則 |
|---|---|---|---|---|---|---|
| A01 | S3[3] |
S3 |
$16k + 3$ | $16k + 3 \to 24k + 5$ | S3 |
C5 |
| A02 | S3[11] |
S3 |
$16k + 11$ | $16k + 11 \to 24k + 17$ | S3 |
L1 |
| A03 | S7[7] |
S7 |
$16k + 7$ | $16k + 7 \to 24k + 11$ | S7 |
S3 |
| A04 | S7[15] |
S7 |
$32k + 15$ | $32k + 15 \to 48k + 23$ | S7 |
S7 |
| A05 | L1[1] |
L1 |
$32k + 1$ | $32k + 1 \to 24k + 1$ | L1 |
L1 |
| A06 | L1[9] |
L1 |
$32k + 9$ | $32k + 9 \to 24k + 7$ | L1 |
D9 文脈を開く |
| A07 | L1[17] |
L1 |
$32k + 17$ | $32k + 17 \to 24k + 13$ | L1 |
C5 |
| A08 | L1[25] |
L1 |
$32k + 25$ | $32k + 25 \to 24k + 19$ | L1 |
S3 |
| A09 | D55 |
D9 |
$96k + 55$ | $96k + 55 \to 144k + 83 \to 216k + 125$ | D55 |
C5 |
| A10 | D79[79] |
D9 |
$192k + 79$ | $192k + 79 \to 288k + 119 \to 432k + 179 \to 648k + 269$ | D79[79] |
C5 |
| A11 | D79[175] |
D9 |
$192k + 175$ | $192k + 175 \to 288k + 263 \to 432k + 395 \to 648k + 593$ | D79[175] |
L1 |
| A12 | D31[31] |
D_{96,31} |
$384k + 31$ | $384k + 31 \to 576k + 47 \to 864k + 71 \to 1296k + 107 \to 1944k + 161$ | D31[31] |
L1 |
| A13 | D31[223] |
D_{96,31} |
$384k + 223$ | $384k + 223 \to 576k + 335 \to 864k + 503 \to 1296k + 755 \to 1944k + 1133$ | D31[223] |
C5 |
| A14 | D31[M] |
D_{96,31} |
$192k + 127$ | $192k + 127 \to 288k + 191 = 32(9k + 5) + 31$ | D31[M] |
M |
| A15 | M |
M-core（分枝細分化文脈なし） |
$M_{m_0}(t_0), \ m_0 \ge 6$ | $M_{m_0}(t_0) \to \cdots \to M_2(K)$ | M |
$K$ 偶数なら L1、奇数なら C5
|
D31[M] の定義的条件 $192k + 127$ は、
(384k + 127) \cup (384k + 319) = 192k + 127.
により、従来の 2 分枝を一つに統合したものである。
表5.C1 の適用条件は、構造状態だけでなく分枝細分化文脈を含めて読む。
たとえば D79[79] / D79[175] の根は構造状態としては $S_7$ に属し、
D31 系 token の根は構造状態としては $M\text{-core}$ に属する。
しかし、D9 または D_{96,31} 文脈が有効な場合には、規則5.5.3 により、
文脈固有 token の選択を generic な構造状態 token より優先する。
したがって、C1 の各 token の適用領域は「構造状態または文脈＋定義的条件」により
一意に定まる。
表5.C2a (複合パターンカタログ：coarse 比較表記).
| ID | 種別 | coarse 正規形 | 代表枝 | カタログ登録 mode | 帰着先 |
|---|---|---|---|---|---|
| B01 | 終了型 | S7 → S3 → L1 |
$384k + 7$ | 384 | C5 |
| B02 | 終了型 | S7 → S3 → L1 → D55 |
$12288k + 487, 12288k + 2023, 12288k + 3559, 12288k + 5095, 12288k + 6631, 12288k + 8167, 12288k + 9703, 12288k + 11239$ | 12288 | C5 |
| B03 | 終了型 | S7 → S3 → L1 → S3 |
$768k + 295$ | 768 | C5 |
| B04 | 終了型 | S7 → S3 → L1 → L1 |
$1536k + 199$ | 1536 | C5 |
| B05 | 終了型 | S7 → S3 → L1 → L1 → S3 |
$3072k + 583$ | 3072 | C5 |
| B06 | 終了型 | S7 → S3 → L1 → S7 → S3 → L1 |
$12288k + 4327, 12288k + 10471$ | 12288 | C5 |
| B07 | 終了型 | S7 → S3 → L1 → S3 → L1 → S3 → L1 |
$24576k + 679$ | 24576 | C5 |
| B08 | 転送型 | S7 → S3 → L1 → D31[M] |
$3072k + 871$ | 3072 | M |
| B09 | 終了型 | S7 → S3 → L1 → D31[223] |
$12288k + 2407, 12288k + 8551$ | 12288 | C5 |
| B11 | 転送型 | S7 → S3 → L1 → D31[31] |
$12288k + 5479, 12288k + 11623$ | 12288 | L1 |
| B12 | 転送型 | S7 → S3 → L1 → L1 → D79[175] |
$49152k + 1351$ | 49152 | L1 |
| B13 | 終了型 | S7 → S3 → L1 → L1 → L1 → D55 |
$24576k + 967$ | 24576 | C5 |
| B14 | 終了型 | S7 → S3 → L1 → D79[79] |
$12288k + 1639, 12288k + 4711, 12288k + 7783, 12288k + 10855$ | 12288 | C5 |
| B15 | 終了型 | S7 → S3 → L1 → S7 → S3 → L1 → S3 |
$12288k + 12007$ | 12288 | C5 |
| B16 | 転送型 | S7 → S3 → L1 → D79[175] |
$12288k + 103$ | 12288 | L1 |
B10 は、従来の D31[127] / D31[319] の統合により B08 と同一の
exact 正規形・帰着先となったため B08 へ統合し、本章では欠番として保持する。
これは付録Gの検証結果との追跡可能性を保つためである。
また、B08 の旧 2 登録を統合すると、mode $12288$ における代表剰余
871, \quad 3943, \quad 7015, \quad 10087.
は一つの合同類
3072k + 871.
になる。この合同類は
871 \equiv 103 \pmod {384}, \qquad 871 \equiv 7 \pmod {96}.
を満たすので、旧分類で継承していた $384k + 103$ および $96k + 7$ の文脈を保持する。
一方、mode を $1536$ まで下げると $2407 \equiv 871 \pmod {1536}$ も同じ登録へ入り、
B09 の D31[223] → C5 分枝と混在する。
したがって、統合後 B08 のカタログ登録 mode は $3072$ であり、
継承文脈と一様な exact 正規形・帰着先を同時に保持する最小の登録 mode である。
以下、表5.C2a / C2b の各行について、代表枝をカタログ登録 mode でみた
登録合同類を登録 root congruenceと呼ぶ。
定義5.5.2 (還元カタログの種別).
表5.C2a および 表5.C2b に登録された複合パターンは、
その帰着先により、終了型と転送型に分ける。
終了型とは、帰着先が C5 であるものをいう。
転送型とは、帰着先が S3、S7、L1、M のいずれかであるものをいう。
分枝細分化文脈 D9, D_{96,31} および exact token D31[31],
D31[223], D31[M] は、複合パターンの帰着先そのものとはしない。
規則5.5.3 (exact token 化規則).
基準値起点有限接頭辞の処理位置において、まず現在位置に有効な
分枝細分化文脈の有無を確認し、文脈が有効な場合には、その文脈による token 選択を
通常の構造状態による token 選択より優先する。
D9 文脈では、現在値は互いに素な
96k + 7, \quad 96k + 31, \quad 96k + 55, \quad 96k + 79.
の 4 分枝のいずれかに一意に属する。
$96k + 7$ は遷移を消費せず $S_7$ へ引き渡し、
$96k + 31$ は遷移を消費せず D_{96,31} 文脈へ移る。
$96k + 55$ では D55 を選択し、$96k + 79$ は mod $192$ により
D79[79] または D79[175] のいずれかを一意に選択する。
D_{96,31} 文脈では、
384k + 31, \quad 384k + 223, \quad 192k + 127.
が互いに素で $96k + 31$ 全体を被覆するので、
D31[31], D31[223], D31[M] のいずれかが一意に選択される。
分枝細分化文脈が有効でない場合には 定義5.1.1 の構造状態を用いる。
$S_3$ は S3[3] / S3[11]、$L_1$ は、L1[1] / L1[9] / L1[17] / L1[25] に
それぞれ排他的に分割される。
$S_7$ は新規 $M\text{-core}$ 入口 $32k + 31$ を正規化段階で除いた状態であるため、
S7[7] または S7[15] のいずれかが一意に適用される。
$M\text{-core}$ で分枝細分化文脈が有効でない場合には M を適用する。
L1[9] の実遷移後には D9 文脈を開く。
以上の各分割は排他的かつ被覆的であり、文脈移行には
$D_9 \to D_{96, 31}$ より先へ続く遷移非消費の文脈循環 が存在しない。
したがって、処理が終端 $C_5^{\mathrm{Norm}}$ に達していない限り、
次の exact token または zero-step の文脈移行は一意に定まる。
選択した exact token が複数回の奇数コラッツ遷移を含む場合には、
その token の登録処理先に到達するまでを一つの token として完結させる。
その内部位置にも 定義5.1.1 の構造状態は付与できるが、
token の途中で新しい exact token を重ねて選択することはしない。
M token についても同様に、$M_2(K)$ までの下降を一つの macro token
として完結させる。
選択した exact token を完了した後、その処理先を次の処理位置として、
同じ規則を繰り返す。こうして得られる有限列を exact token 列と呼ぶ。
規則5.5.4 (カタログ照合規則).
規則5.5.3 により独立に生成した exact token 列が表5.C2b の
exact 正規形と一致したとき、その登録枝は同表の帰着先へ還元される。
ここで、C2b の照合は登録 root congruence に属する枝について行い、
C2b 自身を exact token 列の生成には用いない。
帰着先が C5 であればその場で終了し、S3、S7、L1、M の
いずれかであれば、その構造状態の処理へ移る。
規則5.5.5 (C2b から C2a への射影).
表5.C2b の exact 正規形に現れる token に対して、射影 $\pi$ を
\begin{aligned}
\pi(\texttt{S3[3]})&= \pi(\texttt{S3[11]}) = \texttt{S3}, \\
\pi(\texttt{S7[7]})&= \pi(\texttt{S7[15]}) = \texttt{S7}, \\
\pi(\texttt{L1[1]})&= \pi(\texttt{L1[9]})
= \pi(\texttt{L1[17]}) = \pi(\texttt{L1[25]}) = \texttt{L1}.
\end{aligned}
と定める。
D55, D79[79], D79[175], D31[31], D31[223], D31[M], M については、
その記号をそのまま保つ。
exact 正規形へ $\pi$ を項別に適用して得られる列を、表5.C2a の
coarse 比較表記とする。このとき ID は C2b と同一のものを用いる。
規則5.5.6 (複合パターン同一性).
2 つの枝を同一の複合パターン ID に登録してよいのは、
(1) exact 正規形が一致し、(2) 帰着先が一致する場合に限る。
規則5.5.7 (ID 再利用規則).
既存の複合パターン ID を正規形の中で再利用してよいのは、
その ID が表す exact token 列と帰着先が、当該枝の suffix として
完全に一致する場合に限る。
規則5.5.8 (複合パターンの登録規則).
規則5.5.3 により独立に生成できる exact token 列のうち、
ある有限列が継承合同条件の下で一様な exact 正規形と帰着先を持ち、
複合パターンとして再利用することが有用であるときは、
その合同類を 表5.C2b に登録し、規則5.5.5 の射影により
coarse 比較表記を 表5.C2a に反映する。
表5.C2b は、C1 により生成可能な同一 exact token 列の
すべての出現位置を列挙するものではない。
C2b は、有限分類の構築過程で登録した複合パターン合同類について、
その exact 正規形と帰着先を保持するカタログである。
したがって、ある処理位置が C2b の登録 root congruence に一致しないことだけで、
その位置を未分類とはしない。
規則5.5.3 による局所 exact token化が成立する限り、
その処理は分類体系の内部でそのまま継続する。
以上により、本章で実際の枝を処理するときの順序は次のように定まる。
(1) 実際の奇数コラッツ遷移列を確認する。
(2) 規則5.5.3 により、C2b から独立に exact token 列を生成する。
(3) 現在値が 表5.C2b の登録 root congruence に一致する場合には、
その登録 exact 正規形と帰着先を、生成済み exact token 列に対して照合する。
(4) C2b に一致する登録枝は、その登録帰着先を有限 macro として利用できる。
C2b に一致しない位置でも、C1 による局所 exact token 化は継続する。
(5) 表5.C2a は C2b からの射影として生成し、比較・可読性確認に用いる。
なお、将来カタログへ新しい複合パターンを追加する場合には、
有限合同細分化によって一様な exact 正規形と帰着先を確認し、
本規則に従って C2b へ登録する。
このカタログ拡張手続は、現在の C1 による局所分類の完全性とは独立である。
したがって、本章における有限分類の実体は、実際の奇数コラッツ遷移から
C2b と独立に exact token 列を生成し、有限個の構造状態と分枝細分化文脈の間を
処理することにある。
C2b は、そのうち登録済みの複合合同類を有限 macro として、
認識・再利用する層である。
5.6 補助内部節点
本節では、複数遷移をまとめた exact token の内部に現れる補助内部節点を
定義し、その型の有限性を示す。
定義5.6.1 (補助内部節点).
本章において、exact token が複数回の奇数コラッツ遷移をまとめて表す場合に、
その token の始点と登録処理先の間に現れる $mk + v$ 型の中間位置を
当該 token の補助内部節点と呼ぶ。
補助内部節点である各位置にも 定義5.1.1 の構造状態は一意に付与される。
ただし、規則5.5.3 により、その位置で token 化を途中再開するのではなく、
選択済み token の内部位置として登録処理先まで保持する。
したがって、補助内部節点は第 6 の構造状態を追加するものではない。
なお、M token の内部下降は $M\text{-core}$ 自体の階層構造として記述するため、
その各 $M_m(t)$ を補助内部節点とは呼ばない。
補題5.6.2 (補助内部節点型の有限性).
本章で必要となる補助内部節点の合同類型は有限個である。
証明.
表5.C1 のうち、固定長の複数遷移を一つの token としてまとめるものは、
D55, D79[79], D79[175], D31[31], D31[223] である。
これらの内部値は、表5.C1 に明示した有限本数の一次式からなるので、
必要となる中間合同類型は有限個である。
S3[...], S7[...], L1[...], D31[M] は 1 回の奇数遷移を表すため、
内部の補助節点を持たない。
また、M は可変長の macro token であるが、その内部位置は、$M_m(t)$ という
$M\text{-core}$ 自体の構造で記述し、補助内部節点として追加登録しない。
M token の有限性と出口については 補題5.12.1・補題5.12.2 で別に示す。
よって、本章で必要となる補助内部節点の合同類型は有限個である。
したがって、命題は成り立つ。
$\square$
5.7 (8k + 3) 型開始部分
本節では、構造状態 $S_3$ における exact token の分類と処理先を確定する。
補題5.7.1 (S_3 の分類).
構造状態 $S_3$ に属する位置では、exact token S3[3] または S3[11] の
いずれかが一意に適用される。その処理先は、それぞれ $C_5^{\mathrm{Norm}}$、$L_1$ である。
証明.
$(8k + 3)$ 型は、mod $16$ で
8k + 3 = (16k + 3) \cup (16k + 11).
に排他的に分かれる。
$16k + 3$ に対しては
16k + 3 \to 24k + 5 \equiv 5 \pmod 8.
であるから、exact token S3[3] により $C_5^{\mathrm{Norm}}$ に入る。
また、$16k + 11$ に対しては
16k + 11 \to 24k + 17 \equiv 1 \pmod 8.
であるから、exact token S3[11] により $L_1$ に入る。
したがって、$S_3$ に属する各位置では 2 token のいずれかが一意に適用され、
処理先は $C_5^{\mathrm{Norm}}$ または $L_1$ に限られる。
したがって、命題は成り立つ。
$\square$
5.8 (8k + 7) 型連鎖部分
本節では、構造状態 $S_7$ における exact token の分類と有限な処理を示す。
補題5.8.1 (S_7 の分類).
構造状態 $S_7$ に属する位置では、exact token S7[7] または S7[15] の
いずれかが一意に適用される。
S7[7] は 1 回で $S_3$ へ移り、S7[15] は 1 回 $S_7$ を継続した後、
次の S7[7] により $S_3$ へ移る。
したがって、$S_7$ の処理は有限回で $S_3$ へ出る。
証明.
$(8k + 7)$ 型は mod $32$ で
8k + 7 = (32k + 7) \cup (32k + 15) \cup (32k + 23) \cup (32k + 31).
に分かれる。
このうち $32k + 31$ は 定義5.1.1 の新規 $M\text{-core}$ 入口条件
$n \equiv 31 \pmod {32}$ に該当するため、構造状態 $S_7$ には属さず、
正規化段階で $M\text{-core}$ に割り当てられる。
残る $S_7$ の位置について、$32k + 7$ と $32k + 23$ の和集合は
$16k + 7$ である。したがって、
16k + 7 \to 24k + 11 \equiv 3 \pmod 8.
により exact token S7[7] は 1 回で $S_3$ へ移る。
一方、
32k + 15 \to 48k + 23 = 16(3k + 1) + 7.
であるから、exact token S7[15] の処理先は再び $S_7$ であり、
その到達値は必ず S7[7] の適用条件 $16j + 7$ を満たす。
よって、その次の 1 回の奇数コラッツ遷移で $S_3$ へ移る。
以上より、構造状態 $S_7$ では S7[7] または S7[15] が一意に適用され、
高々 2 個の exact token により $S_3$ へ出る。
なお、$32k + 31$ 型は $S_7$ からの出口ではなく、定義5.1.1 により、
最初から $M\text{-core}$ として正規化される。
したがって、命題は成り立つ。
$\square$
5.9 (8k + 1) 型連鎖部分
本節では、構造状態 $L_1$ の局所分類と各 exact token の処理先を示す。
定義5.9.1 (L_1).
$L_1$ とは、$(8k + 1)$ 型のうち、$32k + 1$ 分枝が反復し、
最初に $32k + 1$ でなくなるまで続く連鎖部分をいう。
ただし、ルート値 $1$ では L1[1] が $1 \to 1$ の自明反復となる。
補題5.9.2 (L_1 の token 分類と出口).
構造状態 $L_1$ に属する位置では、
L1[1], L1[9], L1[17], L1[25] のいずれかが一意に適用される。
L1[1] は $L_1$ を継続し、残る 3 token の処理先は、それぞれ
$D_9$ 文脈、$C_5^{\mathrm{Norm}}$、$S_3$ である。
また、初期値 $1$ を除けば L1[1] の連続反復は有限回で終了する。
証明.
$(8k + 1)$ 型は、mod $32$ で
8k + 1 = (32k + 1) \cup (32k + 9) \cup (32k + 17) \cup (32k + 25).
に排他的に分かれる。$32k + 1$ に対しては
32k + 1 \to 24k + 1 \equiv 1 \pmod 8.
であるから、exact token L1[1] により $L_1$ が継続する。
この到達値が再び $32j + 1$ 型であるための条件は $4 \mid k$ である。
$k = 4h \gt 0$ のとき、
32k + 1 \to 24k + 1 = 32(3h) + 1.
であり、L1[1] の parameter は $4h$ から $3h$ へ真に減少する。
したがって、$k \gt 0$ では L1[1] の連続反復は有限回で終了する。
$k = 0$、すなわち値 $1$ の場合だけは $1 \to 1$ の自明反復となる。
$32k + 9$ に対しては
32k + 9 \to 24k + 7 \equiv 7 \pmod 8.
であるから、exact token L1[9] の実遷移後に $D_9$ 文脈を開く。
$32k + 17$ に対しては
32k + 17 \to 24k + 13 \equiv 5 \pmod 8.
であるから、exact token L1[17] により $C_5^{\mathrm{Norm}}$ に入る。
$32k + 25$ に対しては
32k + 25 \to 24k + 19 \equiv 3 \pmod 8.
であるから、exact token L1[25] により $S_3$ に入る。
よって、$L_1$ の各位置では 4 token のいずれかが一意に適用され、
初期値 $1$ を除けば有限個の L1[1] の後に
$D_9$ 文脈、$C_5^{\mathrm{Norm}}$、または $S_3$ へ出る。
したがって、命題は成り立つ。
$\square$
5.10 D_9 の初期分解
本節では、L1[9] の実遷移後に開かれる $D_9$ 文脈を有限分解し、
後続処理を確定する。
補題5.10.1 (D_9 の初期分解).
L1[9] の実遷移後に開かれる $D_9$ 文脈では、奇数遷移を消費しない $S_7$ への引渡し、
奇数遷移を消費しない $D_{96, 31}$文脈への移行、または
exact token D55, D79[79], D79[175] のいずれかが一意に選択される。
したがって、この段階のすべての枝について後続処理が確定する。
証明.
exact token L1[9] は
32k + 9 \to 24k + 7.
を実行し、その到達値で $D_9$ 文脈を開く。文脈移行自体は
追加の奇数コラッツ遷移を消費しない。ここで、$24k + 7$ は mod $96$ で
24k + 7 = (96k + 7) \cup (96k + 31) \cup (96k + 55) \cup (96k + 79).
に分かれる。
まず、$96k + 55$ に対しては
\begin{aligned}
R(96k + 55) &= 144k + 83, \\
R^2(96k + 55) &= 216k + 125.
\end{aligned}
であり、$216k + 125 \equiv 5 \pmod 8$ であるから、
exact token D55 により一様に $C_5^{\mathrm{Norm}}$ へ到達する。
次に、$96k + 79$ 分枝を考える。この分枝は mod $192$ で
96k + 79 = (192k + 79) \cup (192k + 175).
に分かれる。なお、両集合は互いに素である。
$192k + 79$ に対しては、
\begin{aligned}
R(192k + 79) &= 288k + 119, \\
R^2(192k + 79) &= 432k + 179, \\
R^3(192k + 79) &= 648k + 269.
\end{aligned}
であり、$648k + 269 \equiv 5 \pmod 8$ である。
したがって、この枝は exact token D79[79] として $C_5^{\mathrm{Norm}}$ へ
帰着する。
一方、$192k + 175$ に対しては、
\begin{aligned}
R(192k + 175) &= 288k + 263, \\
R^2(192k + 175) &= 432k + 395, \\
R^3(192k + 175) &= 648k + 593.
\end{aligned}
であり、$648k + 593 \equiv 1 \pmod 8$ である。
したがって、この枝は exact token D79[175] として $L_1$ へ帰着する。
これらについては、
\begin{aligned}
192k + 79 &= 32(6k + 2) + 15 = M_5(6k + 2), \\
192k + 175 &= 32(6k + 5) + 15 = M_5(6k + 5).
\end{aligned}
である。したがって、定義5.1.1 の新規入口規則 $m \ge 6$ により、
いずれも新規 $M\text{-core}$ の入口にはならず、構造状態として $S_7$ に属する。
ただし、ここでは $D_9$ 文脈が既に有効であるため、規則5.5.3 により
通常の $S_7$ token より文脈固有 token を優先し、それぞれ
D79[79], D79[175] として個別に扱う。
また、$96k + 7$ に対しては
96k + 7 = 2^4(6k) + (2^3 - 1) = M_4(6k).
であるから、メルセンヌ数型形状そのものは持つ。
しかし、定義5.1.1 直後に述べたように、$M\text{-core}$ の外部から
直接現れる $m = 3, 4, 5$ のメルセンヌ数型は構造状態 $S_3$、$S_7$ に吸収され、
本章で新規 $M\text{-core}$ の入口として採用するのは
m \ge 6.
の場合に限る。したがって、$96k + 7 = M_4(6k)$ は $M\text{-core}$ の新規入口に
属さない。加えて、$96k + 7$ は、
$96k + 31$ 型でも $96k + 55$ 型でも $96k + 79$ 型でもない。
よって、$D_9$ 文脈の選別により、$96k + 7$ では追加の奇数コラッツ遷移を
消費せず、一様に $S_7$ 構造状態へ引き渡す。
一方、$96k + 31$ は $32(3k) + 31$ であるから、構造状態としては新規の
$M\text{-core}$ 入口に属する。
ただし、現在は $D_9$ 文脈が有効であるため、規則5.5.3 により、
通常の M token を直ちに適用せず、追加の奇数コラッツ遷移を消費しないまま、
$D_{96, 31}$ 文脈へ移り、補題5.11.1 で細分化する。
以上より、$D_9$ に現れる $4$ 分枝のうち、
$96k + 55$ は D55 により $C_5^{\mathrm{Norm}}$ へ到達し、
$96k + 79$ は mod $192$ で D79[79] と D79[175] に細分化され、
それぞれ $C_5^{\mathrm{Norm}}$、$L_1$ へ帰着し、
$96k + 7$ は $S_7$ 構造状態へ引き渡され、
$96k + 31$ は $D_{96, 31}$ 文脈へ移る。
よって、この段階では追加の残差候補は残らない。
したがって、命題は成り立つ。
$\square$
表5.1 ($D_9$ の初期分解の要約)
| 分枝 | 処理 | 帰着先 |
|---|---|---|
| $96k + 55$ | exact token D55
|
C5 |
| $192k + 79$ | exact token D79[79]
|
C5 |
| $192k + 175$ | exact token D79[175]
|
L1 |
| $96k + 7$ | 奇数遷移を消費せず S7 へ引渡し |
S7 |
| $96k + 31$ | 奇数遷移を消費せず $D_{96, 31}$ 文脈へ移行 | L1 / M / C5 |
5.11 D_{96,31} の分類
補題5.10.1 および 表5.1 により、$D_9$ 文脈から
追加の細分化を必要とする枝は
96k + 31.
である。本小節では、この枝に対する分枝細分化文脈を
D_{96, 31}.
と表す。
$96k + 31 = 32(3k) + 31$ であるから、この位置の構造状態は
定義5.1.1 により $M\text{-core}$ である。
ただし、$D_{96, 31}$ 文脈が有効な間は 規則5.5.3 により
通常の M token より文脈固有の D31 系 token を優先する。
補題5.11.1 ($D_{96, 31}$ の分類).
$D_{96, 31}$ 文脈から選択される exact token は、
D31[31], D31[223], D31[M] のいずれかに一意に定まり、
その処理先はそれぞれ $L_1$、$C_5^{\mathrm{Norm}}$、$M\text{-core}$ である。
証明.
$96k + 31$ は mod $384$ で
96k + 31 = (384k + 31) \cup (384k + 127) \cup (384k + 223) \cup (384k + 319).
に分かれる。このうち
(384k + 127) \cup (384k + 319) = 192k + 127.
であるから、
384k + 31, \quad 384k + 223, \quad 192k + 127.
の $3$ 集合は互いに素で $96k + 31$ 全体を被覆する。
$384k + 31$ は 表5.C1 の D31[31] により
384k + 31 \to 576k + 47 \to 864k + 71 \to 1296k + 107 \to 1944k + 161.
と進み、$1944k + 161 \equiv 1 \pmod 8$ であるから $L_1$ へ帰着する。
$384k + 223$ は D31[223] により
384k + 223 \to 576k + 335 \to 864k + 503 \to 1296k + 755 \to 1944k + 1133.
と進み、$1944k + 1133 \equiv 5 \pmod 8$ であるから $C_5^{\mathrm{Norm}}$ へ帰着する。
残る $192k + 127$ では、
R(192k + 127) = 288k + 191 = 32(9k + 5) + 31.
である。したがって exact token D31[M] は 1 回の奇数コラッツ遷移により、
一様に次の $M\text{-core}$ 位置へ進む。
よって、$D_{96, 31}$ 文脈では 3 種の exact token のいずれかが一意に選択され、
処理先はそれぞれ $L_1$、$C_5^{\mathrm{Norm}}$、$M\text{-core}$ である。
したがって、命題は成り立つ。
$\square$
5.12 M-core
本節では、新規 $M\text{-core}$ 入口からの階層下降、その有限性および出口を示す。
補題5.12.1 ($M\text{-core}$ の階層下降).
$M\text{-core}$ の内部では、$m \ge 3$ のとき
R(M_m(t)) = M_{m - 1}(3t + 1).
が成り立つ。
証明.
$M_m(t) = 2^m t + (2^{m - 1} - 1)$ より、
\begin{aligned}
3M_m(t) + 1
&= 3\{2^m t + (2^{m - 1} - 1)\} + 1\\
&= 3 \cdot 2^m t + 3 \cdot 2^{m - 1} - 2\\
&= 2\{3 \cdot 2^{m - 1}t + 3 \cdot 2^{m - 2} - 1\}.
\end{aligned}
ここで、
\begin{aligned}
3 \cdot 2^{m - 1}t + 3 \cdot 2^{m - 2} - 1
&= 2^{m - 1}(3t + 1) + (2^{m - 2} - 1)\\
&= M_{m - 1}(3t + 1).
\end{aligned}
右辺は $m \ge 3$ で奇数であるから、$3M_m(t) + 1$ に含まれる $2$ の因子は
上式で取り出した 1 個で尽くされる。
よって、
R(M_m(t)) = M_{m - 1}(3t + 1).
が成り立つ。
したがって、命題は成り立つ。
$\square$
補題5.12.2 (M-core の出口).
$m_0 \ge 6$ の新規入口から開始する M token は有限回で $M_2(K) = 4K + 1$ に到達し、
token 完了時の処理先は $L_1$ または $C_5^{\mathrm{Norm}}$ に限られる。
証明.
補題5.12.1 により、M token の内部では $m$ が 1 ずつ減少する。
したがって、有限回で終端値
M_2(K) = 4K + 1.
に到達する。
$K$ が偶数なら
4K + 1 \equiv 1 \pmod 8.
であるから、token 完了後の処理先は $L_1$ である。
$K$ が奇数なら
4K + 1 \equiv 5 \pmod 8.
であるから、token 完了後の処理先は $C_5^{\mathrm{Norm}}$ である。
したがって、M token は内部計算として $M_2(K)$ までを一括して追跡するが、
同じ終端値を次の処理位置として見るときの構造状態は、$K$ の偶奇により、
$L_1$ または $C_5^{\mathrm{Norm}}$ に一意に定まる。
したがって、命題は成り立つ。
$\square$
5.13 基準値起点有限接頭辞の分類
ここまでの結果により、各処理位置における構造状態、
分枝細分化文脈、および exact token の選択は有限個の排他的な場合分けで
記述できる。
これを用いて、任意の基準値起点有限接頭辞に対する分類を確定する。
定理5.13.1 (コラッツ遷移パターン分類定理). 〇
任意の分岐テーブルグループの基準値 $b$ を起点とする
奇数コラッツ遷移について、その任意の基準値起点有限接頭辞
u = (u_0, u_1, \ldots, u_r), \qquad u_0 = b.
は、5 種の構造状態
S_3, \quad S_7, \quad L_1, \quad M\text{-core}, \quad C_5^{\mathrm{Norm}}.
と、必要に応じて付随する 2 種の分枝細分化文脈
D_9, \quad D_{96, 31}.
および 表5.C1 の 15 種の exact token を用いて有限に記述できる。
複数遷移 token の内部位置は、必要に応じて 定義5.6.1 の補助内部節点として
記述できる。
終点 $u_r$ が最初の $(8k + 5)$ 型である場合には、この有限接頭辞は
基準値間シーケンスとなる。
証明.
基準値起点有限接頭辞 $u = (u_0, \ldots, u_r)$ を任意にとる。
まず $u_0 = b = 1$ の場合には $R(1) = 1$ であり、任意の有限接頭辞は
L1[1] の有限反復として記述できるので、主張は直ちに成り立つ。
以下、$b \ne 1$ とする。
補題5.1.2 により各位置の構造状態は一意に定まり、
規則5.5.3 により各処理位置で次に適用する exact token または
奇数遷移を消費しない文脈移行も一意に定まる。
実際、分枝細分化文脈が有効でない場合には、構造状態ごとに次の処理が成立する。
$S_3$ は 補題5.7.1 により S3[3] / S3[11]、
$S_7$ は 補題5.8.1 により S7[7] / S7[15]、
$L_1$ は 補題5.9.2 により 4 種の L1[...] token に排他的に分かれ、
初期値 $1$ を除けば L1[1] の反復も有限回で終了する。
$M\text{-core}$ では、分枝細分化文脈が有効でない限り M token を適用し、
補題5.12.1・補題5.12.2 により有限回で $L_1$ または
$C_5^{\mathrm{Norm}}$ へ引き渡す。
$C_5^{\mathrm{Norm}}$ は本章の終端構造状態である。
分枝細分化文脈が有効な場合には、補題5.10.1 と
補題5.11.1 により処理が一意に定まる。
D9 文脈は、奇数遷移を消費せず $S_7$ へ引き渡すか D_{96,31} 文脈へ移るか、
または D55, D79[79], D79[175] のいずれかを選択する。
D_{96,31} 文脈では D31[31], D31[223], D31[M] のいずれかを選択する。
奇数遷移を消費しない文脈移行は D9\to D_{96,31} より先へ循環せず、
D_{96,31} は必ず exact token の選択で解消される。
したがって、文脈移行だけが無限に続くことはない。
各 exact token は少なくとも 1 回の奇数コラッツ遷移を消費する。
固定長 token は 表5.C1 に明示された有限遷移列であり、
その内部位置の合同類型も 補題5.6.2 により有限個である。
可変長の M token も、補題5.12.1 により指数 $m$ が 1ずつ減少するので
有限長である。
よって、有限接頭辞 $u$ の左端から処理を繰り返すと、
奇数遷移を消費しない文脈移行を有限回挟みながら、実際の遷移位置を少なくとも
１つずつ前へ進む。
したがって、遷移数 $r$ に関する有限帰納により、$u_0$ から $u_r$ までの
すべての位置を有限個の構造状態・文脈・exact token で記述できる。
有限接頭辞の終点 $u_r$ が固定長の複数遷移 token の途中にある場合には、
その token の型は始点で一意に定まっているので、$u_r$ までに実際に現れた
有限初期部分だけを記録し、その内部位置を 定義5.6.1の補助内部節点で記述する。
M token の途中で終わる場合には、その有限初期部分を
$M\text{-core}$ の有限下降列として記述する。
したがって、$(8k + 5)$ 型への将来の到達を仮定する必要はない。
ここまでの被覆には C2b の一致を必要としない。
C2b は 規則5.5.4 により、独立に生成済みの exact token 列のうち
登録 root congruence に属するものを後置認識するためのカタログであり、
定理5.13.1 の局所被覆そのものは 表5.C1 と上記の排他的分類だけで
成立する。
さらに、$u_r$ が最初の $(8k + 5)$ 型である場合には、
定義5.1.1 により $u_r$ の構造状態は $C_5^{\mathrm{Norm}}$ である。
この場合、導入部の定義により $u$ は基準値間シーケンスである。
したがって、命題は成り立つ。
$\square$
系5.13.2 (理論本体の閉包性).
構造状態、分枝細分化文脈、および 表5.C1 の exact token からなる
本章の各局所処理の処理先は、再び構造状態または分枝細分化文脈に限られる。
複数遷移 token の内部位置を補助内部節点として表す場合にも、
その token は有限回で表5.C1 の登録処理先へ到達する。
証明.
補題5.7.1 より $S_3$ の処理先は $L_1$ または $C_5^{\mathrm{Norm}}$、
補題5.8.1 より $S_7$ の処理先は有限回で $S_3$、
補題5.9.2 より $L_1$ の 1 token 処理先は
$L_1$、$D_9$ 文脈、$S_3$、または $C_5^{\mathrm{Norm}}$ であり、
初期値 $1$ を除けば $L_1$ の自己継続も有限回で終了する。
補題5.10.1 より $D_9$ 文脈は $S_7$、$D_{96, 31}$ 文脈、
$L_1$、または $C_5^{\mathrm{Norm}}$ へ有限処理で接続し、
補題5.11.1 より $D_{96, 31}$ 文脈の token 処理先は
$L_1$、$M\text{-core}$、または $C_5^{\mathrm{Norm}}$ である。
補題5.12.2 より M token の処理先は
$L_1$ または $C_5^{\mathrm{Norm}}$ である。
また、補題5.6.2 により固定長複数遷移 token の内部位置は有限個の型であり、
各固定長 token の処理先は 表5.C1 に明示されている。
以上より、本章の局所処理は同じ有限分類体系の内部で閉じている。
この閉包性は、すべての基準値が $(8k + 5)$ 型へ到達することを前提とせず、
各局所処理の排他的分類と有限出口だけから成立する。
したがって、命題は成り立つ。
$\square$
5.14 実シーケンスに対する確認範囲
§5.14 – 5.15 は、本章で構成した分類枠組みに対する
実シーケンスに対する確認範囲を与える補足であり、
定理5.13.1 および 系5.13.2 を含む本章の本文証明では用いない。
すなわち、これらは理論成立の証明そのものではなく、分類仕様が
実際の奇数コラッツ遷移と対象範囲内で整合することを確認するための補足である
。
定義5.14.1 (実シーケンスに対する確認範囲).
本章でいう 実シーケンスに対する確認範囲 とは、
入力として与えた実際の奇数コラッツ遷移列について、
(1) 入力列自体の隣接遷移、剰余、基準値その他のメタデータが独立に正しいこと、
(2) 第5章の構造状態・分枝細分化文脈・表5.C1だけから C2b を参照せずに
exact token 列と理論奇数値列を生成できること、
(3) その理論奇数値列が入力実シーケンスと値単位で一致すること、
(4) 登録された C2b root congruence に該当する位置では、
生成済み exact token 列と登録帰着先が C2b と一致すること、
(5) C2a の coarse 比較表記が C2b の exact token 列から機械的に射影できること
、
を別途の実装上の確認作業によって確かめた対象範囲をいう。
現行の付録Gでは、odd index
0 \le j \le 262143.
すなわち初期値
1, 3, 5, \ldots, 524287.
の全 262,144 行を対象として、上記の検査を実施している。
なお、初期値 $1$ の入力行については、実装上は自明な $1 \to 1$ の反復を
無限に token 化しないため、TERMINAL_1 という実装専用の終端記号で処理を
停止する。
これは本章の第 6 の構造状態を導入するものではなく、数学的には L1[1] の
自明反復に対応する実装上の停止規約である。
分割実行時には、各区間の行数・先頭 odd index・末尾 odd index を
明示的な coverage contract とし、区間集約時には gap/overlap がないことも
機械的に確認する。
5.15 実シーケンス確認との関係
定理5.13.1 および 系5.13.2 を含む §5.1–5.13 の本文証明は、
§5.14–5.15 の実装上の確認結果を前提とせず、同範囲の本文および、
そこで参照する既出結果だけで成立する。
よって、実装による全件照合は、これらの数学的成立を支える
前提ではない。
一方で、実シーケンス確認は、本章の分類枠組みが実際の
奇数コラッツ遷移と対象範囲内で整合することを確認する補足的作業である。
現行の hardened verifier では、262,144 行すべてについて
入力独立検査、独立 exact token 化、理論列との値単位一致、
C2b 後置照合、C2a 射影、および分割実行時の全件被覆を確認し、
異常 0 件で PASS している。
また、15 種の exact token と、B10 を除く 15 個の active C2b パターンは、
いずれも当該全件確認中に少なくとも 1 回出現している。
したがって、§5.14 – 5.15 は本文命題ではなく、本章の分類仕様に対する
実装上・経験的な整合確認の位置付けを明示する補足である。
実行方法、検証器の掲載コード、SHA-256、区間別 coverage、および集約結果は、
付録G (定理5.13.1：実シーケンス確認) に掲載する。
5.16 複合パターンカタログ
ここでは、複合パターンカタログの正本である exact 版を示す。
本章のカタログ照合は 表5.C2b の exact 正規形に対して行う。
表5.C2a は、規則5.5.5 の射影により C2b から得られる比較用の
coarse 表記である。
表5.C2b (複合パターンカタログ：exact 版).
| ID | 種別 | exact 正規形 | 代表枝 | カタログ登録 mode | 帰着先 |
|---|---|---|---|---|---|
| B01 | 終了型 | S7[7] → S3[11] → L1[17] |
$384k + 7$ | 384 | C5 |
| B02 | 終了型 | S7[7] → S3[11] → L1[9] → D55 |
$12288k + 487, 12288k + 2023, 12288k + 3559, 12288k + 5095, 12288k + 6631, 12288k + 8167, 12288k + 9703, 12288k + 11239$ | 12288 | C5 |
| B03 | 終了型 | S7[7] → S3[11] → L1[25] → S3[3] |
$768k + 295$ | 768 | C5 |
| B04 | 終了型 | S7[7] → S3[11] → L1[1] → L1[17] |
$1536k + 199$ | 1536 | C5 |
| B05 | 終了型 | S7[7] → S3[11] → L1[1] → L1[25] → S3[3] |
$3072k + 583$ | 3072 | C5 |
| B06 | 終了型 | S7[7] → S3[11] → L1[9] → S7[7] → S3[11] → L1[17] |
$12288k + 4327, 12288k + 10471$ | 12288 | C5 |
| B07 | 終了型 | S7[7] → S3[11] → L1[25] → S3[11] → L1[25] → S3[11] → L1[17] |
$24576k + 679$ | 24576 | C5 |
| B08 | 転送型 | S7[7] → S3[11] → L1[9] → D31[M] |
$3072k + 871$ | 3072 | M |
| B09 | 終了型 | S7[7] → S3[11] → L1[9] → D31[223] |
$12288k + 2407, 12288k + 8551$ | 12288 | C5 |
| B11 | 転送型 | S7[7] → S3[11] → L1[9] → D31[31] |
$12288k + 5479, 12288k + 11623$ | 12288 | L1 |
| B12 | 転送型 | S7[7] → S3[11] → L1[1] → L1[9] → D79[175] |
$49152k + 1351$ | 49152 | L1 |
| B13 | 終了型 | S7[7] → S3[11] → L1[1] → L1[1] → L1[9] → D55 |
$24576k + 967$ | 24576 | C5 |
| B14 | 終了型 | S7[7] → S3[11] → L1[9] → D79[79] |
$12288k + 1639, 12288k + 4711, 12288k + 7783, 12288k + 10855$ | 12288 | C5 |
| B15 | 終了型 | S7[7] → S3[11] → L1[9] → S7[7] → S3[11] → L1[25] → S3[3] |
$12288k + 12007$ | 12288 | C5 |
| B16 | 転送型 | S7[7] → S3[11] → L1[9] → D79[175] |
$12288k + 103$ | 12288 | L1 |
B10 は B08 へ統合済みであり、付録G の検証結果との追跡可能性を保つため、
本章では欠番として保持する。
5.17 S3[11] 型遷移の局所増減判定
ここでは、表5.C1 の exact token S3[11] に対し、同じ S3[11] へ
再び到達するまでの有限な奇数コラッツ遷移を取り出し、その始点と終点の
大小関係を判定する。
本節の結果は、定理5.13.1 および 系5.13.2 の成立に必要な前提を
追加するものではなく、S3[11] を繰り返し通過する枝の局所的な性質を
さらに詳しく記述する補足である。
定義5.17.1 (S3[11] 第一帰還区間).
$j \in \mathbb{Z}_{\ge 0}$、$a_j \in \mathbb{Z}_{\ge 0}$ とし、$16a_j + 11$ から始まる
奇数コラッツ遷移を考える。
再び S3[11] に属する奇数へ到達する正整数回の遷移が存在するとき、
その最小遷移回数 $n_j$ を、
n_j := \min \left\{n \in \mathbb{Z}_{\gt 0} \mid R^n(16a_j + 11) \equiv 11 \pmod {16}\right\}.
と定める。
このとき、一意な $a_{j + 1} \in \mathbb{Z}_{\ge 0}$ により、
R^{n_j}(16a_j + 11) = 16a_{j + 1} + 11.
と書ける。
有限遷移区間
16a_j + 11 \to R(16a_j + 11) \to \cdots \to 16a_{j + 1} + 11.
を、$16a_j + 11$ からの S3[11] 第一帰還区間と呼ぶ。
また、この第一帰還区間における $2$ による除算回数の総和 $s_j$ を、
s_j := \sum_{h = 0}^{n_j - 1}\mathrm{ord}_2\!\left(3R^h(16a_j + 11) + 1\right).
と定める。
定義5.17.2 (S3[11] survivor).
$m \in \mathbb{Z}_{\gt 0}$ とし、$a_0, a_1, \ldots, a_m \in \mathbb{Z}_{\ge 0}$ とする。
各 $j = 0, 1, \ldots, m - 1$ について、
$16a_j + 11$ から $16a_{j + 1} + 11$ までが
定義5.17.1 の S3[11] 第一帰還区間であり、かつ、その区間内に
$(8k + 5)$ 型の奇数が一つも現れないとき、
16a_0 + 11 \to 16a_1 + 11 \to \cdots \to 16a_m + 11.
を、長さ $m$ の有限 S3[11] survivor と呼ぶ。
同じ条件をすべての $j \in \mathbb{Z}_{\ge 0}$ について満たす無限列 $(a_j)_{j \ge 0}$ が
存在する場合、その列を無限 S3[11] survivor と呼ぶ。
有限または無限 S3[11] survivor を構成する各S3[11] 第一帰還区間を
survivor 第一帰還枝と呼ぶ。
各 survivor 第一帰還枝について 定義5.17.1 で定めた $n_j, s_j$ は、
定義3.4.2 の観測区間における奇数遷移回数および総除算回数を、
当該 S3[11] 観測区間へ特殊化したものに一致する。
また、補題3.4.4 の適用例で局所的に第一帰還単位と呼んだ区間は、
次の S3[11] が $(8k + 5)$ 型より先に現れる区間であるから、
本節の survivor 第一帰還枝に一致する。
定義5.17.3 (上昇型／下降型第一帰還枝).
survivor 第一帰還枝
16a_j + 11 \to 16a_{j + 1} + 11.
に対し、$a_{j + 1} \gt a_j$ であるものを上昇型第一帰還枝、
$a_{j + 1} \lt a_j$ であるものを下降型第一帰還枝と呼ぶ。
以下では、表5.C1 で S3[11] と表記した $16k + 11$ 型を対象とし、
定義5.17.2 で定めた S3[11] survivor の各 survivor 第一帰還枝の構造を
順に分解して示す。
まず、後続の命題で共通して用いる第一帰還枝の記号と用語を固定する。
定義5.17.4 (survivor 第一帰還枝の共通記号).
定義5.17.2 で定めた有限または無限 S3[11] survivor を一つ固定し、
同定義で用いた記号を以下のとおり使用する。
また、本項で用いる $(8k + \alpha)$ 型のデータ型表記は
「1.2.7 各データ型遷移パターン」の用法を使用し、
$(8k + 1)$ 型連鎖については
「1.2.10 $(8k + 1)$ 型の連鎖」の用語および記号を使用する。
さらに、表5.C1 の記号 S3[3] および S3[11] を、それぞれ
$16k + 3$ 型および $16k + 11$ 型を表す記号として使用する。
第一帰還枝の上昇型第一帰還枝および下降型第一帰還枝という用語は、
定義5.17.3 で定めた意味を使用する。
有限 S3[11] survivor の場合は、同定義の長さ $m$ および
$a_0, a_1, \ldots, a_m$ を用い、$j = 0, 1, \ldots, m - 1$ とする。
無限 S3[11] survivor の場合は、同定義の列 $(a_j)_{j \ge 0}$ を用い、
$j \in \mathbb{Z}_{\ge 0}$ とする。
各第 $j$ survivor 第一帰還枝
16a_j + 11 \to 16a_{j + 1} + 11.
について、定義5.17.1 で定めた第一帰還区間の奇数遷移回数 $n_j$ および
総除算回数 $s_j$ を用いる。また、
z_j := 3a_j + 2, \qquad z_{j + 1} := 3a_{j + 1} + 2.
と定める。さらに、定義1.1.5 の $2$ 進付値関数 $\mathrm{ord}_2(n)$
を用いて、
\nu_j := \mathrm{ord}_2(z_j).
と定める。このとき、一意な $\omega_j \in \mathbb{N}_{\mathrm{odd}}$ により、
z_j = 2^{\nu_j}\omega_j.
と書けるものとし、この奇数を $\omega_j$ と定める。
次に、第一帰還枝の始点から現れる $(8k + 1)$ 型連鎖の長さを決める
$2$ 進付値 $\nu_j$ の偶奇を確定する。
補題5.17.5 (survivor 第一帰還枝始点における $2$ 進付値の偶数性).
定義5.17.4 の設定において、
\nu_j \equiv 0 \pmod 2.
が成り立つ。
証明.
定義5.17.4 の第 $j$ survivor 第一帰還枝の始点 $16a_j + 11$ に対する
最初の奇数コラッツ遷移は、
16a_j + 11 \to 24a_j + 17 = 8z_j + 1.
である。また、定義5.17.4 より、
z_j = 2^{\nu_j}\omega_j.
である。したがって、
24a_j + 17 - 1 = 2^{\nu_j + 3}\omega_j.
である。ここで、「1.2.10 $(8k + 1)$ 型の連鎖」で用いる指数を
$p := \nu_j + 3$ とおく。
$\nu_j$ が奇数であると仮定する。この場合、$p$ は偶数となるため、
§1.2.10 (B-1) により、$(8k + 1)$ 型連鎖は最終的に $(32k + 17)$ 型へ到達し、
その次の奇数コラッツ遷移で $(8k + 5)$ 型へ遷移する。
この連鎖に属する各奇数は $(8k + 1)$ 型であり、
次の S3[11] への帰還より先に $(8k + 5)$ 型へ到達することになる。
これは survivor 第一帰還枝の定義に反する。よって、$\nu_j$ は偶数である。
したがって、命題は成り立つ。
$\square$
補題5.17.5 により、各 survivor 第一帰還枝について
次の補助パラメタを定義できる。
定義5.17.6 (survivor 第一帰還枝の補助パラメタ).
定義5.17.4 の設定を用いる。補題5.17.5 より $\nu_j$ は偶数であるから、
\mu_j := \frac {\nu_j}{2} \in \mathbb{Z}_{\ge 0}.
と定める。定義5.17.4 の $z_j = 2^{\nu_j}\omega_j$ および $\nu_j = 2\mu_j$ より、
z_j = 4^{\mu_j}\omega_j.
である。さらに、
w_j := 3^{\mu_j}\omega_j.
とおく。$w_j \in \mathbb{N}_{\mathrm{odd}}$ であるから $3w_j + 1$ は正の偶数である。
そこで、定義1.1.5 の $2$ 進付値関数 $\mathrm{ord}_2(n)$ を用いて、
\lambda_j := \mathrm{ord}_2(3w_j + 1) \in \mathbb{Z}_{\gt 0}.
と定める。このとき、一意な $y_j \in \mathbb{N}_{\mathrm{odd}}$ により、
3w_j + 1 = 2^{\lambda_j}y_j.
と書ける。
次に、これらの補助パラメタを用いて、第一帰還区間の終点を
具体的に表す。
補題5.17.7 (survivor 第一帰還枝の第一帰還終点).
定義5.17.4 および 定義5.17.6 の設定において、
16a_{j + 1} + 11 = 4 \cdot 3^{\lambda_j - 1}y_j - 1.
が成り立つ。
証明.
§1.2.10 (A) の連鎖式で用いる指数 $p$ に $p := 2\mu_j + 3$ を代入すると、
$24a_j + 17$ から $\mu_j + 1$ 回の $(8k + 1)$ 型遷移を経た値は、
6w_j + 1 = 2^{\lambda_j + 1}y_j - 1.
となる。
$h = 0, 1, \ldots, \lambda_j - 1$ に対して、
B_{j, h} := 2^{\lambda_j - h + 1}3^h y_j - 1.
とおく。$h = 0$ では、
B_{j, 0} = 2^{\lambda_j + 1}y_j - 1 = 6w_j + 1.
である。
$0 \le h \le \lambda_j - 2$ とする。このとき、$\lambda_j - h + 1 \ge 3$ であるから、
B_{j, h} \equiv 7 \pmod 8.
となる。したがって、次の奇数コラッツ遷移における
$2$ による除算回数は $1$ である。
ここで、定義1.1.7 の代表値関数 $R(n)$ を用いると、
\begin{aligned}
R(B_{j, h})
&= \frac {3B_{j, h} + 1}{2} \\
&= 2^{\lambda_j - h}3^{h + 1}y_j - 1 \\
&= B_{j, h + 1}.
\end{aligned}
となる。よって、$0 \le h \le \lambda_j - 1$ において、
B_{j, h} = 2^{\lambda_j - h + 1}3^h y_j - 1.
が成り立つ。
$0 \le h \le \lambda_j - 2$ では $B_{j, h} \equiv 7 \pmod 8$ であるため、
S3[11] にも $(8k + 5)$ 型にも属さない。
なお、$\lambda_j = 1$ の場合、この範囲は空である。
一方、$h = \lambda_j - 1$ では、
B_{j, \lambda_j - 1} = 4 \cdot 3^{\lambda_j - 1}y_j - 1.
となり、$(8k + 3)$ 型である。
$B_{j, \lambda_j - 1}$ が $16k + 3$ 型、すなわち S3[3] である場合、
補題5.7.1 により次の奇数コラッツ遷移で $(8k + 5)$ 型へ到達する。
これは survivor 第一帰還枝の定義に反する。
したがって、$B_{j, \lambda_j - 1}$ は $16k + 11$ 型、すなわち S3[11] である。
また、それ以前の $B_{j, h}$ は S3[11] に属さないため、$B_{j, \lambda_j - 1}$ が
第一帰還区間の終点である。
よって、
16a_{j + 1} + 11 = 4 \cdot 3^{\lambda_j - 1}y_j - 1.
が成り立つ。
したがって、命題は成り立つ。
$\square$
第一帰還終点が確定したので、第一帰還区間における
奇数遷移回数と総除算回数を数える。
系5.17.8 (survivor 第一帰還区間の遷移回数と総除算回数).
定義5.17.4 および 定義5.17.6 の設定において、
それらの定義で定めた $n_j, s_j, \mu_j, \lambda_j$ について、
\begin{aligned}
n_j &= \mu_j + \lambda_j + 1, \\
s_j &= 2\mu_j + \lambda_j + 2.
\end{aligned}
が成り立つ。
証明.
第一帰還区間は、最初の $2$ による除算 $1$ 回を伴う遷移、
$(8k + 1)$ 型連鎖における $2$ による除算 $2$ 回を伴う遷移 $\mu_j + 1$ 回、
その後の $2$ による除算 $1$ 回を伴う遷移 $\lambda_j - 1$ 回から成る。よって、
\begin{aligned}
n_j &= 1 + (\mu_j + 1) + (\lambda_j - 1) = \mu_j + \lambda_j + 1, \\
s_j &= 1 + 2(\mu_j + 1) + (\lambda_j - 1) = 2\mu_j + \lambda_j + 2.
\end{aligned}
となる。
したがって、命題は成り立つ。
$\square$
系5.17.8 から、第一帰還区間における追加除算回数総和を
単一の変数で表すことができる。
系5.17.9 (survivor 第一帰還区間の追加除算回数総和).
定義5.17.4 および 定義5.17.6 の設定において、
第 $j$ survivor 第一帰還枝の第一帰還区間における追加除算回数総和を
$x_j$ と定める。このとき、
x_j := s_j - n_j = \mu_j + 1.
が成り立つ。
証明.
当該第一帰還区間における奇数遷移回数は $n_j$、
$2$ による除算回数の総和は $s_j$ である。
追加除算回数総和の定義より、
x_j = s_j - n_j.
である。さらに、系5.17.8 より、
\begin{aligned}
x_j &= s_j - n_j \\
&= (2\mu_j + \lambda_j + 2) - (\mu_j + \lambda_j + 1) \\
&= \mu_j + 1.
\end{aligned}
となる。
したがって、命題は成り立つ。
$\square$
次に、第一帰還枝の始点と終点を結ぶ恒等式を示す。
補題5.17.10 (survivor 第一帰還枝の始点・終点恒等式).
定義5.17.4 および 定義5.17.6 の設定において、
系5.17.8 の $n_j, s_j$ を用いると、
2^{s_j}z_{j + 1} = 3^{n_j}z_j + 4^{\mu_j}\left(3^{\lambda_j} - 2^{\lambda_j}\right).
が成り立つ。
証明.
補題5.17.7 より、
16a_{j + 1} + 11 = 4 \cdot 3^{\lambda_j - 1}y_j - 1.
である。両辺に $1$ を加えて $4$ で割ると、
4a_{j + 1} + 3 = 3^{\lambda_j - 1}y_j.
となる。定義5.17.4 より $z_{j + 1} = 3a_{j + 1} + 2$ であるから、
4z_{j + 1} = 3^{\lambda_j}y_j - 1.
を得る。
一方、定義5.17.6 より、
2^{\lambda_j}y_j = 3^{\mu_j + 1}\omega_j + 1.
である。したがって、
\begin{aligned}
2^{\lambda_j + 2}z_{j + 1} &= 3^{\lambda_j}\left(2^{\lambda_j}y_j\right) - 2^{\lambda_j} \\
&= 3^{\mu_j + \lambda_j + 1}\omega_j + 3^{\lambda_j} - 2^{\lambda_j}.
\end{aligned}
となる。
両辺に $4^{\mu_j}$ を乗じ、$z_j = 4^{\mu_j}\omega_j$ および 系5.17.8を用いると、
2^{s_j}z_{j + 1} = 3^{n_j}z_j + 4^{\mu_j}\left(3^{\lambda_j} - 2^{\lambda_j}\right).
を得る。
したがって、命題は成り立つ。
$\square$
次に、$3^{n_j} \lt 2^{s_j}$ の場合に現れる二つの冪差の大小関係を示す。
補題5.17.11 ($3^{n_j} \lt 2^{s_j}$ における $2$ 冪・$3$ 冪差の大小関係).
定義5.17.4 および 定義5.17.6 の設定において、
第 $j$ survivor 第一帰還枝が
3^{n_j} \lt 2^{s_j}.
を満たすならば、
2^{s_j} - 3^{n_j} \gt 3^{\lambda_j} - 2^{\lambda_j} \gt 0.
が成り立つ。
証明.
系5.17.8 より、
\begin{aligned}
n_j &= \mu_j + \lambda_j + 1, \\
s_j &= 2\mu_j + \lambda_j + 2.
\end{aligned}
したがって、
\begin{aligned}
2n_j - s_j &= \lambda_j, \\
s_j - n_j &= \mu_j + 1.
\end{aligned}
である。
定義5.17.6 より、
\lambda_j \in \mathbb{Z}_{\gt 0}.
であるから、
s_j \lt 2n_j.
よって、仮定と合わせて、
3^{n_j} \lt 2^{s_j} \lt 4^{n_j}.
を得る。
ここで、補題2.2.5 に、
c := s_j,\qquad d := n_j
を適用する。このとき、
\tau = 2n_j - s_j = \lambda_j.
であるから、
2^{s_j} - 3^{n_j} \gt 3^{\lambda_j} - 2^{\lambda_j}.
を得る。さらに、$\lambda_j \in \mathbb{Z}_{\gt 0}$ より、
3^{\lambda_j} - 2^{\lambda_j} \gt 0.
である。
したがって、命題は成り立つ。
$\square$
同じ設定において、経過比率の $1$ からの乖離を評価する。
系5.17.12 ($3^{n_j} \lt 2^{s_j}$ における経過比率の乖離下界).
定義5.17.4 および 定義5.17.6 の設定において、
第 $j$ survivor 第一帰還枝が
3^{n_j} \lt 2^{s_j}.
を満たすとする。
当該第一帰還区間の経過比率について、
\frac {2^{s_j}}{3^{n_j}} - 1 \gt \frac {1}{3^{\mu_j + 1}} \left\{ 1 - \left(\frac {2}{3}\right)^{\lambda_j} \right\} \gt 0.
が成り立つ。
証明.
系5.17.8 より、
\begin{aligned}
s_j - n_j &= \mu_j + 1, \\
2n_j - s_j &= \lambda_j.
\end{aligned}
である。
また、定義5.17.6 より $\lambda_j \in \mathbb{Z}_{\gt 0}$ であるから、
s_j \lt 2n_j.
したがって、仮定と合わせて、
3^{n_j} \lt 2^{s_j} \lt 4^{n_j}.
を得る。
よって、系2.2.6 に、
n := n_j,\qquad S_n := s_j
を適用すると、
\frac {2^{s_j}}{3^{n_j}} - 1 \gt \frac {1}{3^{s_j - n_j}} \left\{ 1 - \left(\frac {2}{3}\right)^{2n_j - s_j} \right\} \ge 0.
を得る。ここに、
s_j - n_j = \mu_j + 1, \qquad 2n_j - s_j = \lambda_j
を代入すると、
\frac {2^{s_j}}{3^{n_j}} - 1 \gt \frac {1}{3^{\mu_j + 1}} \left\{ 1 - \left(\frac {2}{3}\right)^{\lambda_j} \right\}.
さらに、$\lambda_j \in \mathbb{Z}_{\gt 0}$ より、
1 - \left(\frac {2}{3}\right)^{\lambda_j} \gt 0.
であるから、右辺は正である。
したがって、命題は成り立つ。
$\square$
同じ設定において、逆経過比率の $1$ からの乖離を評価する。
系5.17.13 ($3^{n_j} \lt 2^{s_j}$ における逆経過比率の乖離下界).
定義5.17.4 および 定義5.17.6 の設定において、
第 $j$ survivor 第一帰還枝が
3^{n_j} \lt 2^{s_j}.
を満たすとする。
当該第一帰還区間の逆経過比率について、
1 - \frac {3^{n_j}}{2^{s_j}} \gt \frac {1}{4^{\mu_j + 1}} \left\{ \left(\frac {3}{2}\right)^{\lambda_j} - 1 \right\} \gt 0.
が成り立つ。
証明.
系5.17.8 より、
\begin{aligned}
s_j - n_j &= \mu_j + 1, \\
2n_j - s_j &= \lambda_j.
\end{aligned}
である。
また、定義5.17.6 より $\lambda_j \in \mathbb{Z}_{\gt 0}$ であるから、
s_j \lt 2n_j.
したがって、仮定と合わせて、
3^{n_j} \lt 2^{s_j} \lt 4^{n_j}.
を得る。
よって、系2.2.7 に、
n := n_j,\qquad S_n := s_j
を適用すると、
1 - \frac {3^{n_j}}{2^{s_j}} \gt \frac {1}{4^{s_j - n_j}} \left\{ \left(\frac {3}{2}\right)^{2n_j - s_j} - 1 \right\} \ge 0.
を得る。ここに、
s_j - n_j = \mu_j + 1, \qquad 2n_j - s_j = \lambda_j
を代入すると、
1 - \frac {3^{n_j}}{2^{s_j}} \gt \frac {1}{4^{\mu_j + 1}} \left\{ \left(\frac {3}{2}\right)^{\lambda_j} - 1 \right\}.
さらに、$\lambda_j \in \mathbb{Z}_{\gt 0}$ より、
\left(\frac {3}{2}\right)^{\lambda_j} - 1 \gt 0.
であるから、右辺は正である。
したがって、命題は成り立つ。
$\square$
次に、補題5.17.10 の恒等式を用いて、
冪の大小から第一帰還枝の増減を判定する。
補題5.17.14 ($3^{n_j} \gt 2^{s_j}$ における第一帰還枝の上昇).
定義5.17.4と定義5.17.6 の設定において、第 $j$ survivor 第一帰還枝が、
3^{n_j} \gt 2^{s_j}.
ならば、
a_{j + 1} \gt a_j.
が成り立つ。
証明.
補題5.17.10 の両辺から $2^{s_j}z_j$ を引くと、
2^{s_j}(z_{j + 1} - z_j) = z_j(3^{n_j} - 2^{s_j}) + 4^{\mu_j}(3^{\lambda_j} - 2^{\lambda_j}).
を得る。
仮定より $3^{n_j} - 2^{s_j} \gt 0$ であり、$\lambda_j \ge 1$ より、
$3^{\lambda_j} - 2^{\lambda_j} \gt 0$ である。
したがって、右辺は正であるから、
z_{j + 1} \gt z_j.
となる。定義5.17.4 より、$z_j = 3a_j + 2$ および $z_{j + 1} = 3a_{j + 1} + 2$ なので、
a_{j + 1} \gt a_j.
が成り立つ。
したがって、命題は成り立つ。
$\square$
補題5.17.15 ($3^{n_j} \lt 2^{s_j}$ における第一帰還枝の下降).
定義5.17.4 と定義5.17.6 の設定において、第 $j$ survivor 第一帰還枝が、
3^{n_j} \lt 2^{s_j}.
ならば、
a_{j + 1} \lt a_j.
が成り立つ。
証明.
次の正数をおく。
D_j := 2^{s_j} - 3^{n_j}, \qquad E_j := 3^{\lambda_j} - 2^{\lambda_j}.
補題5.17.11 より、
D_j \gt E_j \gt 0.
である。補題5.17.10 の両辺から $2^{s_j}z_j$ を引き、
$z_j = 4^{\mu_j}\omega_j$ を用いると、
2^{s_j}(z_{j + 1} - z_j) = 4^{\mu_j}(-\omega_jD_j + E_j).
となる。$\omega_j \in \mathbb{N}_{\mathrm{odd}}$ より $\omega_j \ge 1$
なので、
\omega_jD_j \ge D_j \gt E_j.
である。したがって、
-\omega_jD_j + E_j \lt 0.
となり、
z_{j + 1} \lt z_j.
を得る。定義5.17.4 より $z_j = 3a_j + 2$ および
$z_{j + 1} = 3a_{j + 1} + 2$ なので、
a_{j + 1} \lt a_j.
が成り立つ。
したがって、命題は成り立つ。
$\square$
直前の補題２つをまとめると、第一帰還枝の上昇・下降を
完全に判定できる。
系5.17.16 (S3[11] survivor 第一帰還の上昇・下降判定).
定義5.17.4 および 定義5.17.6 の設定において、
第 $j$ survivor 第一帰還枝について、
\begin{aligned}
a_{j + 1} \gt a_j &\Longleftrightarrow 3^{n_j} \gt 2^{s_j}, \\
a_{j + 1} \lt a_j &\Longleftrightarrow 3^{n_j} \lt 2^{s_j}, \\
a_{j + 1} &\ne a_j.
\end{aligned}
が成り立つ。
証明.
補題5.17.14 および 補題5.17.15 により、
\begin{aligned}
3^{n_j} \gt 2^{s_j} &\Longrightarrow a_{j + 1} \gt a_j, \\
3^{n_j} \lt 2^{s_j} &\Longrightarrow a_{j + 1} \lt a_j.
\end{aligned}
が成り立つ。
また、$n_j, s_j \in \mathbb{Z}_{\gt 0}$ であるから、
素因数分解の一意性により、
3^{n_j} \ne 2^{s_j}.
である。よって、$3^{n_j} \gt 2^{s_j}$ または $3^{n_j} \lt 2^{s_j}$ の
何れかが必ず成り立つ。
よって、直前の２補題の含意から、逆向きの含意も従い、
命題の同値関係が成り立つ。また、$a_{j + 1} = a_j$ は生じない。
したがって、命題は成り立つ。
$\square$
下降型第一帰還枝について、平均追加除算回数比率と臨界比率の
関係を示す。
系5.17.17 (下降型第一帰還枝の平均追加除算回数比率の臨界比率超過).
定義5.17.4 および 定義5.17.6 の設定において、
第 $j$ survivor 第一帰還枝が 定義5.17.3 の下降型第一帰還枝
であるとする。
このとき、系5.17.9 で定めた追加除算回数総和 $x_j$ と
第一帰還区間の奇数遷移回数 $n_j$ に対して、
\frac {x_j}{n_j} \gt \alphastar.
が成り立つ。ここで、$\alphastar$ は臨界比率である。
証明.
下降型であるから、系5.17.16 より、
3^{n_j} \lt 2^{s_j}.
である。両辺の底 $2$ の対数を取ると、
n_j \log_2 3 \lt s_j.
となる。両辺から $n_j$ を引くと、
n_j(\log_2 3 - 1) \lt s_j - n_j.
を得る。系5.17.9 より、
x_j = s_j - n_j.
であるから、
n_j(\log_2 3 - 1) \lt x_j.
となる。$n_j \gt 0$ で割り、$\alphastar = \log_2 3 - 1$ を用いると、
\frac {x_j}{n_j} \gt \alphastar.
を得る。
系5.17.9 により、$x_j$ は
当該第一帰還区間における追加除算回数総和であるから、
$x_j / n_j$ は当該区間における平均追加除算回数比率である。
したがって、命題は成り立つ。
$\square$
さらに、系5.17.12 を用いると、平均追加除算回数比率が
臨界比率を上回る幅にも明示的な下界を与えることができる。
すなわち、下降型第一帰還枝における
平均追加除算回数比率と臨界比率との差の下界を規定できる。
系5.17.18 (下降型第一帰還枝の平均追加除算回数比率と臨界比率の差).
定義5.17.4 および 定義5.17.6 の設定において、
第 $j$ survivor 第一帰還枝が 定義5.17.3 の下降型第一帰還枝
であるならば、
平均追加除算回数比率(${x_j} / {n_j}$) と臨界比率 ($\alphastar$)
に関して、
\frac {x_j}{n_j} - \alphastar \gt \frac {1}{n_j} \log_2 \left[ 1 + \frac {1}{3^{\mu_j + 1}} \left\{ 1 - \left(\frac {2}{3}\right)^{\lambda_j} \right\} \right] \gt 0.
が成り立つ。
証明.
下降型であるから、系5.17.16 より、$3^{n_j} \lt 2^{s_j}$ である。
したがって、系5.17.12 より、
\frac {2^{s_j}}{3^{n_j}} \gt 1 + \frac {1}{3^{\mu_j + 1}} \left\{ 1 - \left(\frac {2}{3}\right)^{\lambda_j} \right\}.
を得る。両辺は正であり、底 $2$ の対数関数は正の実数上で
単調増加であるから、
\log_2 \frac {2^{s_j}}{3^{n_j}} \gt \log_2 \left[ 1 + \frac {1}{3^{\mu_j + 1}} \left\{ 1 - \left(\frac {2}{3}\right)^{\lambda_j} \right\} \right].
となる。
一方、系5.17.9 の $x_j = s_j - n_j$ を用いると、
\begin{aligned}
\log_2 \frac {2^{s_j}}{3^{n_j}}
&= s_j - n_j \log_2 3 \\
&= (s_j - n_j) - n_j(\log_2 3 - 1) \\
&= x_j - n_j\alphastar \\
&= n_j \left( \frac {x_j}{n_j} - \alphastar \right).
\end{aligned}
である。$n_j \gt 0$ で割ると、
\frac {x_j}{n_j} - \alphastar \gt \frac {1}{n_j} \log_2 \left[ 1 + \frac {1}{3^{\mu_j + 1}} \left\{ 1 - \left(\frac {2}{3}\right)^{\lambda_j} \right\} \right].
を得る。$\lambda_j \ge 1$ であるから、
1 - \left(\frac {2}{3}\right)^{\lambda_j} \gt 0.
よって、右辺は正である。
したがって、命題は成り立つ。
$\square$
以上により、各 survivor 第一帰還枝の上昇・下降は、
第一帰還区間の奇数遷移回数 $n_j$ と総除算回数 $s_j$ に対する
$3^{n_j}$ と $2^{s_j}$ の大小関係によって完全に判定できる。
さらに、下降型第一帰還枝では、系5.17.9 で定めた
追加除算回数総和 $x_j$ に対する平均追加除算回数比率 $x_j / n_j$ が
臨界比率 $\alphastar$ を上回る。
さらに、系5.17.18 により、その差 ($x_j / n_j - \alphastar$) には
第一帰還枝の構造パラメタ $\mu_j, \lambda_j, n_j$ によって定まる
明示的な正の下界が存在する。
5.18 本章の位置付け
本章で得たものは、奇数コラッツ遷移について、
分岐テーブルグループの基準値を始点とする任意の
基準値起点有限接頭辞を、有限個の構造状態、分枝細分化文脈、
exact token、および補助内部節点の有限合成として読み直すための
有限分類仕様である。
その核心は、以下の事柄を結び付け、任意の基準値起点有限接頭辞を
有限分類体系の内部で記述した点にある。
・$(8k + 7)$ 型に対する $S_7$ / $M\text{-core}$ の優先分類
・$(8k + 1)$ 型分枝の局所分類
・$S_3, S_7, L_1, M\text{-core}, C_5^{\mathrm{Norm}}$ の構造状態
・$D_9, D_{96, 31}$ の分枝細分化文脈
・15 種の exact token と C2b exact 登録形
・$(8k + 5)$ 型へ実際に到達した場合の正規化作用
特に本章では、exact token 列を C2b から独立に生成し、
C2b を登録済み複合パターンの後置照合に用いる形で、
有限分類とカタログ照合の役割を分離した。
C2a は C2b からの機械的射影として位置付け、カタログ照合の独立正本とはしない。
また、従来の S7[31] を exact token から廃止し、$32k + 31$ 型を直接
$M\text{-core}$ の新規入口として扱い、従来の D31[127] と D31[319] を
D31[M] へ統合した。
これにより、構造状態、分枝細分化文脈、exact token の三層の役割が明確になる。
本章の分類体系は、「1 以外の BTG 基準値は必ず $(8k + 5)$ 型へ到達する」
という結論を前提としない。
$(8k + 5)$ 型へ到達した場合には、その到達済み有限接頭辞が
基準値間シーケンスとして確定し、$C_5^{\mathrm{Norm}}$ により、
対応する分岐テーブルグループの基準値へ正規化した上で、
同じ分類処理を再開できる。
一方、$(8k + 5)$ 型へ未到達である限り、任意の有限段階までの接頭辞は
定理5.13.1 と 系5.13.2 により同じ有限分類体系の内部で分類される。
§5.14 – 5.15 および付録Gの実シーケンス確認は、この分類仕様と
実際の奇数コラッツ遷移との整合性を確認する補足であり、
本章の本文証明を支える前提ではない。
現行の hardened verifier では、262,144 個の奇数初期値を対象とする
全件確認で、独立 exact token 化、C2b 後置照合、C2a 射影、および
coverage contract を含む検証が異常 0 件で完了している。
したがって、本章が与えるのは、$(8k + 5)$ 型への
大域的な必達性ではなく、奇数コラッツ遷移の有限接頭辞に対する
完全な局所分類と閉包性である。
////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////