Collatz heavy cheap LP フレーム周期排除のための条件付き下限構造数値抜き ver.1.1 ドラフト
要約 Abstract
[メモ]
本稿では Collatz 写像に対して、heavy cheap LP フレームと呼ぶ一次不等式ベースの証明フレームを定式化する
[メモ]
目的は、次の四つを統合することである
1
[定義] 奇数版 Collatz 写像における O_3 型ステップの平均指数 \mu_3
2
[定義] O_3 内部の cheap と heavy の分解
3
[定義] O₁ パターンブロックの危険集合と heavy capacity
4
[定義] cheap log LP による \mu_3 の上限
[メモ]
本稿で示すのは、ある有限個のスカラー定数が与えられれば、非自明周期の存在を一次不等式だけで判定できるという条件付き定理である
[事実]
本稿内の論理から直接得られる中心構造は、次の形である
\mu_3\ge 3+\delta_0
ただし \delta_0 は、危険長さ率、O₁頻度、heavy capacity、O₃頻度上界から定まる
[推測]
本稿では、次の対象は外部解析または後続計算に委ねる
\gamma_{\mathcal K}^{len}\ge\varepsilon_0>0
p_1\ge p_{\min}>0
u\le u_{\max}
\mu_3\le3+\delta_1
[事実]
これらが与えられ、さらに
\delta_0>\delta_1
が成立するなら、非自明 Collatz 周期は存在しない
[メモ]
本稿では数値計算そのものは行わない
数値を入れる前の論理構造だけを確定する
0. ラベリング規則
[定義]
以下では、主張を次のように分類する
[定義]
記号、集合、関数、パラメータの導入
[事実]
このテキスト内の論理だけで証明されたもの、または単純な代数計算に還元できるもの
[推測]
未証明の主張、外部計算、LP、オートマトン、有限探索に依存する仮定
[数値実験]
実際の計算結果
本稿では扱わない
[メモ]
方針、直感、補足、今後の作業
[定義]
フレームの芯とは、このドラフト内の論理だけで導かれる構造、不等式、条件付き定理を指す
[メモ]
外部論文、未実装オートマトン、未実行 LP の出力は、すべて [推測] 側に置く
1. 基本設定
1.1 通常 Collatz 写像
[定義]
通常の Collatz 写像 C:\mathbb N\to\mathbb N を
C(n)=
\begin{cases}
n/2 & n\equiv0\pmod2,\\
3n+1 & n\equiv1\pmod2
\end{cases}
と定める
[定義]
Collatz 予想とは、任意の自然数 n から始めた反復列が最終的に 1 に到達するという主張である
1.2 奇数版 Collatz 写像
[定義]
奇数 m に対して
3m+1=2^{a(m)}F(m)
と書く
ここで
a(m)=v_2(3m+1)
であり、F(m) は奇数である
したがって
F(m)=\frac{3m+1}{2^{a(m)}}
と定義する
[定義]
本稿では、この F を奇数版 Collatz 写像と呼ぶ
[定義]
奇数列
m_0,m_1,\ldots,m_{T-1}
が
F(m_t)=m_{t+1}
m_T=m_0
を満たすとき、これを奇数版 Collatz 写像の周期と呼ぶ
[定義]
すべての t について
m_t>1
が成り立つ周期を、非自明周期と呼ぶ
[定義]
各時刻 t に対して
a_t:=a(m_t)=v_2(3m_t+1)
と置く
2. 型分類と頻度
2.1 型 \tau
[定義]
各奇数ステップを、指数 a_t によって三種類に分類する
O_1:\quad a_t=1
O_2:\quad a_t=2
O_3:\quad a_t\ge3
[定義]
型を
\tau_t\in\{1,2,3\}
で表す
\tau_t=1 \Longleftrightarrow a_t=1
\tau_t=2 \Longleftrightarrow a_t=2
\tau_t=3 \Longleftrightarrow a_t\ge3
[定義]
O_3 のうち
a_t=3
を cheap O_3 と呼び、
a_t\ge4
を heavy O_3 と呼ぶ
2.2 型頻度
[定義]
周期長 T に対して型頻度を
p_i:=\frac{1}{T}\#\{t:\tau_t=i\}
と定める
特に
u:=p_3
と書く
[事実]
定義から
p_1+p_2+p_3=1
p_i\ge0
が成り立つ
2.3 型遷移頻度
[定義]
型遷移頻度を
q_{ij}:=\frac{1}{T}\#\{t:\tau_t=i,\ \tau_{t+1}=j\}
と定義する
[事実]
周期性から
\sum_j q_{ij}=p_i
\sum_i q_{ij}=p_j
が成り立つ
[メモ]
これは単なる流量保存であり、オートマトンを必要としない
3. O_3 の分解と平均指数 \mu_3
[定義]
O_3 の指数分布を
u_k:=\frac{1}{T}\#\{t:\tau_t=3,\ a_t=k\}
\qquad k\ge3
と定める
[定義]
cheap と heavy の頻度を
u_3:=\frac{1}{T}\#\{t:a_t=3\}
u_{4+}:=\sum_{k\ge4}u_k
と定める
[事実]
定義から
u=p_3=\sum_{k\ge3}u_k=u_3+u_{4+}
が成り立つ
[定義]
u>0 のとき、O_3 上の平均指数を
\mu_3:=\frac{1}{u}\sum_{k\ge3}ku_k
と定める
[導出]
\mu_3
=
\frac{1}{u}\sum_{k\ge3}(3+(k-3))u_k
=
3+\frac{1}{u}\sum_{k\ge4}(k-3)u_k
したがって
\mu_3
\ge
3+\frac{1}{u}\sum_{k\ge4}u_k
=
3+\frac{u_{4+}}{u}
[事実]
よって
\mu_3-3\ge \frac{u_{4+}}{u}
\tag{3.1}
が成り立つ
[事実]
さらに u\le1 より
\mu_3-3\ge u_{4+}
\tag{3.2}
も成り立つ
[メモ]
鋭い下界には式 3.1 を使い、粗い下界には式 3.2 を使う
4. O₁ パターンブロックと危険集合
4.1 最大連続区間ではなく、パターンブロックとして定義する
[メモ]
ここが重要である
O₁ ブロックを連続する \tau=1 の最大区間として定義すると、ブロック内部に現れる 1\to3 遷移は高々 1 本になる
その場合、(2,2) や (3,3) のような危険型は出現できない
したがって、本稿では O₁ ブロックを最大連続区間ではなく、有限長の O₁ パターンブロックとして定義する
[定義]
O₁ パターンブロックとは、周期上から選ばれた有限個の O₁ 行からなる局所パターンであり、その長さを
\ell(B)
とする
[定義]
ブロック B 内に含まれる指定危険遷移の本数を
r(B)
とする
[定義]
(\ell,r) をブロック型と呼ぶ
\ell(B)=\ell,\qquad r(B)=r
を満たすブロックを型 (\ell,r) のブロックと呼ぶ
[メモ]
この定義により、(2,2) や (3,3) も許される
つまり、長さ \ell のパターン内部に危険遷移が r 回現れる、という意味である
4.2 O₁ log 係数
[定義]
O₁ 行の log 係数を
L_{11}=\log\frac{11}{7}
L_{12}=\log\frac{17}{11}
L_{13}=\log\frac{5}{3}
と置く
[事実]
単純な大小比較から
L_{13}>L_{11}>L_{12}>0
が成り立つ
[定義]
ブロック B 内の 1\to1、1\to2、指定危険遷移の本数を
n_{11}(B),\quad n_{12}(B),\quad r(B)
とし、
n_{11}(B)+n_{12}(B)+r(B)=\ell(B)
とする
[定義]
ブロック B の O₁ log 収支を
S_{O1}(B)
=
n_{11}(B)L_{11}
+n_{12}(B)L_{12}
+r(B)L_{13}
と定義する
[定義]
型 (\ell,r) の最大 O₁ log 利得を
\Phi_{\ell,r}
:=
\max_{B:\ell(B)=\ell,\ r(B)=r}S_{O1}(B)
と定める
[導出]
L_{13}>L_{11}>L_{12} であるため、固定された (\ell,r) に対して S_{O1}(B) を最大化するには、n_{11} を最大化し、n_{12} を最小化すればよい
したがって
\Phi_{\ell,r}
=
\ell L_{11}+r(L_{13}-L_{11})
\tag{4.1}
を得る
[事実]
特に
\Phi_{\ell,r}\le \ell L_{13}
が成り立つ
4.3 危険集合
[定義]
危険集合を
\mathcal K
=
\{(1,1),(2,1),(2,2),(3,1),(3,3)\}
と定める
[定義]
高危険集合を
\mathcal K^*
=
\{(1,1),(2,2),(3,3)\}
と定める
[メモ]
これらは有限集合であり、各 (\ell,r) に対する \Phi_{\ell,r} は有限回の計算で確定する
5. 危険長さ率
[定義]
周期上で選ばれた危険 O₁ パターンブロックの集合を
\mathcal B_{\mathcal K}
とする
[推測]
\mathcal B_{\mathcal K} は、後続のオートマトンまたはパターン抽出規則によって、重なりがないように選ばれるものとする
[メモ]
重なりを許すと、危険長さや heavy 割当の二重計上が発生するため、ここでは非重複選択を前提とする
[定義]
O₁ の総長さを
N_1:=\#\{t:\tau_t=1\}
とする
[定義]
危険ブロックに属する O₁ 長さを
N_1(\mathcal K)
:=
\sum_{B\in\mathcal B_{\mathcal K}}\ell(B)
と定める
[定義]
危険長さ率を
\gamma_{\mathcal K}^{len}
:=
\frac{N_1(\mathcal K)}{N_1}
と定める
[事実]
周期全体に対する危険 O₁ 長さの比率は
p_1\gamma_{\mathcal K}^{len}
\tag{5.1}
である
[メモ]
ここが重要である
\gamma_{\mathcal K}^{len} は O₁ 内比率であり、周期全体の比率ではない
したがって heavy 下限には必ず p_1 が現れる
6. heavy capacity
6.1 cheap と heavy
[定義]
cheap 側の資源を
O_2,\qquad cheap\ O_3\ (a_t=3)
とする
[定義]
heavy 側の資源を
heavy\ O_3\ (a_t\ge4)
とする
[定義]
cheap 総頻度を
u_{\mathrm{cheap}}:=p_2+u_3
とする
[推測]
後続の LP 解析から
u_{\mathrm{cheap}}\le U_{\mathrm{cheap}}
のような budget 制約が得られると期待する
6.2 局所 heavy 補題
[定義]
ブロック B に付随する cheap と heavy の本数を
N_2(B)
N_3^{(3)}(B)
N_3^{(4+)}(B)
と書く
[定義]
それぞれの log 上界を
L_{2,\max}<0
L_3^{(3),\max}<0
L_3^{(4+),\max}<0
とする
[定義]
ブロック B の補正後 log 収支を
S(B)
=
\Phi_{\ell,r}
+
N_2(B)L_{2,\max}
+
N_3^{(3)}(B)L_3^{(3),\max}
+
N_3^{(4+)}(B)L_3^{(4+),\max}
とする
[推測]
局所 heavy 補題
任意の危険ブロック B\in\mathcal B_{\mathcal K} に対して、周期条件と log 収支を保つには、少なくとも 1 本の heavy O_3 が必要である
すなわち
N_3^{(4+)}(B)\ge1
\tag{6.1}
が成り立つ
[メモ]
これは本稿内では証明しない
有限ケースチェック、LP、またはオートマトン解析で証明されるべき補題である
6.3 heavy 下限の代数的帰結
[推測]
危険ブロックの長さには共通上界
\ell(B)\le L_{\max}
があるとする
[メモ]
危険集合 \mathcal K の長さだけを見るなら L_{\max}=3 だが、実際の抽出規則で拡張ブロックを使う場合は L_{\max}=6 などになりうる
本稿では記号 L_{\max} のまま扱う
[事実]
局所 heavy 補題 6.1 を仮定すると、各危険ブロック B について
N_3^{(4+)}(B)\ge1
である
また
\ell(B)\le L_{\max}
なので
N_3^{(4+)}(B)
\ge
\frac{\ell(B)}{L_{\max}}
が成り立つ
[導出]
非重複に選ばれた危険ブロック全体で和を取ると
\#\{heavy\ O_3\}
\ge
\frac{1}{L_{\max}}
\sum_{B\in\mathcal B_{\mathcal K}}\ell(B)
両辺を周期長 T で割ると
u_{4+}
\ge
\frac{1}{L_{\max}}
\frac{N_1(\mathcal K)}{T}
ここで
\frac{N_1(\mathcal K)}{T}
=
p_1\gamma_{\mathcal K}^{len}
なので
u_{4+}
\ge
\frac{p_1}{L_{\max}}\gamma_{\mathcal K}^{len}
\tag{6.2}
を得る
[定義]
c_H:=\frac{1}{L_{\max}}
と置く
[事実]
局所 heavy 補題と非重複選択を仮定すれば
u_{4+}
\ge
c_Hp_1\gamma_{\mathcal K}^{len}
\tag{6.3}
が成り立つ
[メモ]
修正前の
u_{4+}\ge c_H\gamma_{\mathcal K}^{len}
は、\gamma_{\mathcal K}^{len} を周期全体比率として定義した場合にのみ成立する
本稿の定義では O₁ 内比率なので、正しくは p_1 が必要である
7. heavy 側からの \mu_3 下限
[事実]
式 3.1 より
\mu_3-3\ge\frac{u_{4+}}{u}
である
[事実]
式 6.3 より
u_{4+}\ge c_Hp_1\gamma_{\mathcal K}^{len}
である
[導出]
したがって
\mu_3-3
\ge
\frac{c_Hp_1}{u}\gamma_{\mathcal K}^{len}
\tag{7.1}
を得る
[推測]
後続解析により
\gamma_{\mathcal K}^{len}\ge\varepsilon_0>0
p_1\ge p_{\min}>0
u\le u_{\max}
が得られると仮定する
[事実]
このとき
\mu_3-3
\ge
\frac{c_Hp_{\min}}{u_{\max}}\varepsilon_0
が成り立つ
[定義]
heavy 側の下限幅を
\delta_0
:=
\frac{c_Hp_{\min}}{u_{\max}}\varepsilon_0
\tag{7.2}
と定義する
[事実]
すると
\mu_3\ge3+\delta_0
\tag{7.3}
が従う
[メモ]
粗い形として u\le1 のみを使えば
\delta_0^{rough}:=c_Hp_{\min}\varepsilon_0
でもよい
ただし、鋭い判定には式 7.2 を使う
8. cheap log LP による \mu_3 上限
8.1 log 収支
[定義]
各型の平均 log 利得を
\mathbb E[L_1],\quad
\mathbb E[L_2],\quad
\mathbb E[L_3]
とする
[定義]
周期一周の平均 log 収支を
S
=
p_1\mathbb E[L_1]
+
p_2\mathbb E[L_2]
+
u\mathbb E[L_3]
と置く
[事実]
周期では元の値に戻るため、log 収支は
S=0
である
[推測]
外部解析により
\mathbb E[L_1]\le L_{1,\max}
\mathbb E[L_2]\le L_{2,\max}
\mathbb E[L_3]\le \log4-\mu_3\log2
が得られると仮定する
[導出]
S=0 と上界を合わせると
0
=
S
\le
p_1L_{1,\max}
+
p_2L_{2,\max}
+
u(\log4-\mu_3\log2)
したがって u>0 の範囲で
\mu_3
\le
\frac{
p_1L_{1,\max}
+
p_2L_{2,\max}
+
u\log4
}{
u\log2
}
\tag{8.1}
[定義]
右辺を
\operatorname{UB}(p_1,p_2,u)
:=
\frac{
p_1L_{1,\max}
+
p_2L_{2,\max}
+
u\log4
}{
u\log2
}
と書く
[事実]
条件付きで
\mu_3\le\operatorname{UB}(p_1,p_2,u)
が成り立つ
8.2 LP 領域 P
[推測]
q 遷移 LP、危険構造、log 制約から、(p_1,p_2,u) の可解領域 P が得られると仮定する
[推測]
さらに P は有界多面体であり、ある
u_{\min}>0
を用いて
u\ge u_{\min}
を満たすと仮定する
[メモ]
この仮定は重要である
u\to0 が許されると、\operatorname{UB} が発散し、\delta_1 が有限に定まらない可能性がある
[定義]
可解領域を形式的に
P=
\left\{
(p_1,p_2,u):
p_1+p_2+u=1,\quad
p_i\ge0,\quad
u\ge u_{\min},\quad
\text{LP 制約}
\right\}
と書く
8.3 \delta_1 の定義
[定義]
cheap 側の最大許容値を
\mu_3^{\max}
:=
\max_{(p_1,p_2,u)\in P}
\operatorname{UB}(p_1,p_2,u)
と定める
[定義]
cheap 側のオフセットを
\delta_1:=\mu_3^{\max}-3
\tag{8.2}
と定義する
[事実]
P 上で
\mu_3\le3+\delta_1
\tag{8.3}
が成り立つ
[メモ]
本稿では \delta_1 の数値評価は行わない
LP の頂点列挙と log 係数の代入は後続フェーズに回す
9. 統合判定定理
9.1 条件
[推測]
以下を仮定する
A
危険長さ率の下限
\gamma_{\mathcal K}^{len}\ge\varepsilon_0>0
B
O₁ 頻度の下限
p_1\ge p_{\min}>0
C
O₃ 頻度の上限
u\le u_{\max}
D
局所 heavy 補題と非重複危険ブロック選択により
u_{4+}\ge c_Hp_1\gamma_{\mathcal K}^{len}
E
cheap log LP により
\mu_3\le3+\delta_1
F
c_H=1/L_{\max}>0
[定義]
\delta_0
:=
\frac{c_Hp_{\min}}{u_{\max}}\varepsilon_0
と置く
9.2 定理
[事実]
条件付きメイン定理
上記 A から F が成立すると仮定する
もし
\delta_0>\delta_1
ならば、非自明 Collatz 周期は存在しない
9.3 証明
[導出]
非自明周期が存在すると仮定する
A, B, C, D と式 3.1 から
\mu_3-3
\ge
\frac{u_{4+}}{u}
\ge
\frac{c_Hp_1\gamma_{\mathcal K}^{len}}{u}
\ge
\frac{c_Hp_{\min}\varepsilon_0}{u_{\max}}
したがって
\mu_3\ge3+\delta_0
\tag{9.1}
一方、E より
\mu_3\le3+\delta_1
\tag{9.2}
よって周期が存在するなら
3+\delta_0\le\mu_3\le3+\delta_1
が必要である
しかし
\delta_0>\delta_1
ならこれは矛盾である
したがって、非自明周期は存在しない
\square
10. 閾値表現
[定義]
必要な危険長さ率の閾値を
\gamma_{\mathrm{crit}}
:=
\frac{\delta_1u_{\max}}{c_Hp_{\min}}
と定義する
[事実]
条件
\delta_0>\delta_1
は
\frac{c_Hp_{\min}}{u_{\max}}\varepsilon_0>\delta_1
すなわち
\varepsilon_0>
\frac{\delta_1u_{\max}}{c_Hp_{\min}}
と同値である
[事実]
したがって
\varepsilon_0>\gamma_{\mathrm{crit}}
が示されれば、非自明周期は存在しない
[メモ]
この形にすると、証明の残りは二つの作業に分離される
1
オートマトンまたは有限状態解析で \varepsilon_0 を押し上げる
2
cheap log LP で \delta_1 を押し下げる
最終判定は
\varepsilon_0>\gamma_{\mathrm{crit}}
という一つの不等式に圧縮される
11. 変数ライフサイクル
[メモ]
主要変数の流れを整理する
11.1 m_t
[定義]
周期上の奇数列
[変形]
a_t=v_2(3m_t+1) と型 \tau_t に写る
[消滅]
LP では個々の m_t は現れず、頻度変数へ圧縮される
11.2 a_t
[定義]
2 進指数
[変形]
u_k、\mu_3、cheap、heavy に分解される
[消滅]
最終的には
\mu_3-3\ge\frac{u_{4+}}{u}
に吸収される
11.3 \tau_t
[定義]
O_1,O_2,O_3 の型
[変形]
p_i,q_{ij}、O₁ パターンブロック、危険集合へ移る
[消滅]
最終的には p_1,u,\gamma_{\mathcal K}^{len} に圧縮される
11.4 \gamma_{\mathcal K}^{len}
[定義]
O₁ 内部における危険長さ率
[変形]
周期全体比率へ移すと
p_1\gamma_{\mathcal K}^{len}
になる
[消滅]
\gamma_{\mathcal K}^{len}\ge\varepsilon_0
によって \varepsilon_0 に圧縮される
11.5 u_{4+}
[定義]
heavy O_3 の頻度
[変形]
u_{4+}\ge c_Hp_1\gamma_{\mathcal K}^{len}
から heavy 下限を与える
[消滅]
\mu_3-3\ge\frac{u_{4+}}{u}
によって \delta_0 に吸収される
11.6 \delta_0,\delta_1
[定義]
heavy 側下限幅と cheap 側上限幅
[変形]
比較条件
\delta_0>\delta_1
にまとめられる
[消滅]
非自明周期排除の矛盾に変換される
12. 未解決部分
[推測]
本稿では、次の部分は未解決のまま残る
1
危険ブロック抽出規則の完全定義
2
危険ブロックの非重複選択
3
局所 heavy 補題
N_3^{(4+)}(B)\ge1
の証明
4
オートマトン解析による
\gamma_{\mathcal K}^{len}\ge\varepsilon_0
の証明
5
LP による
p_1\ge p_{\min}
u\le u_{\max}
u\ge u_{\min}
の証明
6
cheap log LP による
\mu_3\le3+\delta_1
の実数評価
7
最終比較
\delta_0>\delta_1
の検証
[メモ]
この一覧は弱点ではなく、証明を完成させるための作業分解である
13. 今後の順序
[メモ]
論理的な順序は次の通りである
1
O₁ パターンブロックの抽出規則を完全固定する
2
危険ブロックが非重複に選べることを証明する
3
局所 heavy 補題を有限ケースで証明する
4
有限オートマトン A_k を設計し、safe only 閉路を排除する
5
\varepsilon_0 を得る
6
q 遷移 LP を構成し、p_{\min},u_{\max},u_{\min} を得る
7
cheap log LP から \delta_1 を得る
8
\delta_0=\frac{c_Hp_{\min}}{u_{\max}}\varepsilon_0
を計算する
9
\delta_0>\delta_1
を確認する
10
非自明周期排除定理としてまとめる
14. 終わりに
[メモ]
この ver.1.1 の核心は、Collatz 周期排除を次の一つの不等式へ圧縮した点にある
\frac{c_Hp_{\min}}{u_{\max}}\varepsilon_0>\delta_1
[メモ]
左辺は heavy 側の強制力である
[メモ]
右辺は cheap log LP が許す余白である
[メモ]
左辺が右辺を超えれば、\mu_3 は同時に
\mu_3\ge3+\delta_0
かつ
\mu_3\le3+\delta_1
を満たさねばならず、矛盾する
[メモ]
したがって、このフレームが示しているのは、Collatz の非自明周期問題を
heavy 強制量
危険構造の最低出現率
O_1 と O_3 の頻度制約
cheap 側の log LP 上限
の比較問題へ還元できるということである
[メモ]
本稿は Collatz 予想の証明ではない
しかし、非自明周期排除のために何を示せばよいかを、かなり明確な条件付き定理として分解している
