Collatz 猜想（3n+1 問題）研究報告

1. 問題陳述

1.1 原始形式

定義 Collatz 映射 \( T: \mathbb{N} \to \mathbb{N} \)：

• 若 \( n \) 為偶數：\( T(n) = n/2 \)
• 若 \( n \) 為奇數：\( T(n) = 3n + 1 \)

Collatz 猜想：對所有正整數 \( n \)，反覆施用 \( T \) 最終到達 1。

1.2 壓縮形式

定義壓縮 Collatz 映射 \( S: \mathbb{N}_{\text{odd}} \to \mathbb{N}_{\text{odd}} \)（奇數到奇數）：

其中 \( v_2(m) \) 是 \( m \) 的 2-adic 賦值（\( m \) 被 2 整除的最大次數）。

等價猜想：對所有奇數 \( n > 1 \)，反覆施用 \( S \) 最終到達 1。

1.3 已知結果

2. 補充工具：Epoch 分解與位移座標

2.1 尾隨 1-bit 結構

定義：奇數 \( n \) 的「尾隨 1-bit 數」\( t = v_2(n+1) \)，即 \( n \) 的二進位表示中末尾連續 1 的個數。

寫成 \( n = 2^t m' - 1 \)，其中 \( m' \) 為奇數。

2.2 核心公式

定理（精確公式）：若奇數 \( n \) 有 \( t \) 個尾隨 1-bit，則前 \( t-1 \) 步壓縮 Collatz 映射（每步 \( v_2 = 1 \)）之後：

證明：

定義 \( T(n) = (3n+1)/2 \)（\( v_2 = 1 \) 的壓縮步驟）。

歸納法：

• \( T^1(n) = (3n+1)/2 \)
• \( T^j(n) = (3^j n + c_j)/2^j \)，其中 \( c_j \) 滿足 \( c_j = 3c_{j-1} + 2^{j-1} \)

解遞推：\( c_1 = 1 \)，\( c_j = 3^j - 2^j \)（可直接驗證）。

所以

驗證：\( n = 7 = 111_2 \)，\( t = 3 \)，\( m' = 1 \)。

\( T^2(7) = (3/2)^2 \cdot 8 - 1 = \tfrac{9}{4} \cdot 8 - 1 = 18 - 1 = 17 \)。

實際：\( 7 \to 11 \to 17 \)。✓

2.3 位移座標

定義：\( x = n + 1 \)。

在位移座標下，\( t-1 \) 步「壞步」段是純粹的縮放：

精確等式，無誤差項。

2.4 Epoch 分解

將軌道分解為一系列 epoch：

其中 \( w_i = v_2(3^{t_i} m'_i - 1) \geq 1 \)。

2.5 下降條件

軌道下降的條件化簡為：

等價地，壓縮步驟的平均 \( v_2 \) 必須超過 \( \log_2 3 \approx 1.585 \)。

2.6 隨機遊走模型

取對數後，軌道成為隨機遊走：

其中 \( d_k \) 是 epoch 末步的 \( v_2 \) 值。

• \( E[\text{步幅}] = 2\log(3/2) - 2\log 2 = 2\log(3/4) < 0 \)（負漂移）
• 猜想等價於此遊走對所有初始條件都趨向 \( -\infty \)

3. 結構性結果一：3 態轉換器譜間隙 = 1/2 [Paper A]

3.1 轉換器構造

\( 3n + 1 = n + 2n + 1 \) 在二進位中是逐位加法加進位。進位傳播構成有限狀態轉換器。

位置 i 的計算：

sum = b_i(n) + b_{i-1}(n) + δ_{i,0} + carry_{i-1}
output_bit = sum mod 2
carry_i = sum ÷ 2

進位 \( \in \{0, 1\} \)，結合上一輸入位 \( b_{i-1} \in \{0, 1\} \)，等效為 4 態自動機。

合併等效態後得到 3 態：

3.2 轉移規則

A --0→ A (out 0)     A --1→ B (out 1)
B --0→ A (out 1)     B --1→ C (out 0)
C --0→ B (out 0)     C --1→ C (out 1)

3.3 v₂ 與轉換器的關係

初始狀態（位置 0 特殊處理 +1）：carry₀ = 1, prev = 1 → 狀態 C。

v₂(3n+1) 由首次非零輸出位的位置決定：

3.4 譜間隙計算

對均勻隨機輸入位，3 態轉移矩陣為：

特徵多項式：

因式分解：\( (\lambda - 1)(2\lambda - 1)(2\lambda + 1) = 0 \)

結果：

穩態分佈：\( \pi = (1/3, 1/3, 1/3) \)。

3.5 譜間隙的含義

carry 狀態以速率 \( (1/2)^t \) 收斂到穩態分佈。處理 \( t \) 個隨機輸入位後，carry 的分佈距穩態的距離 \( \leq (1/2)^t \)。

3.6 對 v₂ 去相關性的推論

\( S(n) \) 的低位元是 \( n \) 的高位區段經 carry 濾波的結果。carry 混合（譜間隙 1/2）意味著 \( S(n) \) 的低位與 \( n \) 的低位之間的相關性指數衰減。

4. 結構性結果二：log₂3 連分數 65/41 屏障 [Paper C]

4.1 連分數展開

log₂3 的連分數展開為：

這個展開是無限不循環的（因為 log₂3 是超越數）。每一個部分商（partial quotient）\( a_i \) 產生一個收斂子 \( p_i/q_i \)，交替地從上方和下方逼近 log₂3。

4.2 收斂子表

4.3 與 Collatz 最壞情況的關聯

實驗發現：在所有測試的 \( k \) 值（\( k = 5 \) 到 \( k = 44 \)，涵蓋 14 位到 44 位整數），最壞情況的下降比率 \( B/T \) 幾乎全部精確等於 65/41。

這是 \( \log_2 3 \) 的第 6 個連分數收斂子（上方最近的）。

4.4 為什麼 65/41 是天然屏障

• \( \log_2 3 \) 是無理數（由 Gelfond-Schneider 定理，它甚至是超越數）
• 因此不存在整數 \( B, T \) 使得 \( B/T = \log_2 3 \)
• 下降所需的最小整數 \( B = \lceil T \cdot \log_2 3 \rceil \) 永遠嚴格超過臨界值
• 對 \( T = 41 \)：\( \lceil 41 \times 1.58496 \rceil = 65 \)，且 \( 65/41 = 1.5854 > \log_2 3 \)

4.5 數值驗證

\( 2^{64} < 3^{41} < 2^{65} \)：

所以 \( (T, B) = (41, 65) \) 的下降門檻 \( N_0 = 3^{41}/(2^{65} - 3^{41}) \approx 87 \)。

含義：對所有 \( n > 87 \) 且命中 \( (41, 65) \) 窗口的數，\( S^{41}(n) < n \)。

5. 失敗路線：序數方法 [Paper B：嚴格化為「不可能性」結果]

結論：此路線不夠。嘗試用序數值勢函數（仿 Goodstein 定理）證明 Collatz 終止；斷裂於兩處：(1) 乘 3 加 1 的 carry 傳播可能增加二進位 block 數量，使序數反而上升；(2) 任何形如 \(\log n + g(n \bmod 2^k)\) 的有限修正函數都被 \(n \equiv -1 \pmod{2^{k+1}}\) 擊敗。理由：序數良序性要求單調下降，但 Collatz 步驟對序數的影響非單調。詳細推導與限制分析展開於下方 details。

6. 失敗路線：反向樹密度

結論：此路線不夠。反向 Collatz 樹以 1 為根，覆蓋比例經密度論證確實趨近 100%。斷裂於：密度為零的正向不變集仍可存在（如非平凡循環元素）。理由：密度為零不蘊含空集——有理數在實數中密度為零卻無處不在。詳細構造與遺漏集性質分析展開於下方 details。

7. 失敗路線：2-adic 遍歷性

結論：此路線不夠。在 \(\mathbb{Z}_2\) 上 \(\times 3\) 是保測遍歷自同構，理論上 \(v_2\) 序列趨向 \(\text{Geo}(1/2)\)。斷裂於：\(\mathbb{N} \subset \mathbb{Z}_2\) 是測度零子集。理由：遍歷定理對 Haar 測度幾乎所有點成立，但 \(\mathbb{N}\) 整體就是測度零的例外集——標準遍歷論工具不能直接適用。詳細構造與所需「有效遍歷定理」展開於下方 details。

8. 失敗路線：Kolmogorov 複雜度

結論：此路線不夠。發散軌道的大數確實高度可壓縮——\(K(S^T(n)) = O(\log n + \log T)\)，比 \(\log_2 S^T(n)\) 小得多。斷裂於：可壓縮性不直接蘊含「\(v_2\) 值會下降」。理由：結構化不等於數值會下降（\(2^n\) 高度結構化卻持續增長）；carry 傳播可能保持某些類型的壓縮結構而不破壞它們。詳細推導與所需「壓縮結構衰減定理」展開於下方 details。

9. 計算實驗 [Paper C 之實證部分]

9.1 實驗一：每個位元長度 k 的最壞情況平均 v₂

完整枚舉所有 \( k \)-位奇數（\( k \leq 18 \)），計算 descent 軌跡的平均 \( v_2 \)。

關鍵發現：最壞情況的 B/T 比率穩定在 \( 65/41 = 1.5854 \)，始終 \( > \log_2 3 = 1.5850 \)。

9.2 實驗二：Mersenne 數 \( (2^k - 1) \) 的軌道

所有 Mersenne 數均到達 1，平均 \( v_2 \) 始終 \( > \log_2 3 \)。

9.3 實驗三：大 k 值的最壞情況搜尋

使用智慧抽樣（Mersenne + 尾隨 1 模式 + 前輪最壞擴展 + 隨機），搜尋 \( k = 5 \) 到 \( k = 44 \)。

結果：所有測試的 \( k \) 值中，最壞情況的 B/T 始終 \( \geq 65/41 > \log_2 3 \)。

偶見 \( B/T = 149/94 \approx 1.5851 \)（\( k = 19, 29, 31 \)），這是 \( 65/41 \) 和 \( 84/53 \) 的中位分數，仍 \( > \log_2 3 \)。

9.4 實驗四：累積比率 \( R(T) = \Sigma v_2 / (T \cdot \log_2 3) \)

• 全局最小 \( R = 1/\log_2 3 \approx 0.6309 \)，總是出現在第 1 步（\( v_2 = 1 \)）
• \( R \) 在初始壞步段下降，之後回升
• 最終 \( R \) 始終 > 1（軌道始終最終下降）

9.5 實驗五：v₂ = 1 比例的 Expander Mixing 驗證

即使 \( v_2 = 1 \) 的比例高達 68%，偶發的大 \( v_2 \)（3, 6）足以補償：

n = 154079 的 v₂ 分佈（41 步下降軌跡）：
  v₂=1: 28 步 (68.3%)
  v₂=2:  5 步 (12.2%)
  v₂=3:  7 步 (17.1%)
  v₂=6:  1 步 (2.4%)
  總和: 28 + 10 + 21 + 6 = 65 = B  ✓

一次 \( v_2 = 6 \) 的步驟補償了 5 次 \( v_2 = 1 \) 的損失。

9.6 實驗六：v₂ 序列可視化

Mersenne 數的 \( v_2 \) 序列示例：

2⁸-1 = 255:    111111163331234
2¹²-1 = 4095:  11111111111511111211322212321215122312242111111243331234
2²⁰-1:         111111111111111111152125132232212251111113146422312412241123

可見：初始長串 \( v_2=1 \)（尾隨 1-bit 造成），然後出現 \( v_2 \geq 2 \) 的補償步驟。

9.7 互動實驗場

以下提供六個互動實驗，可自行調整參數，即時觀察計算結果。

10. 結構性結果三：引理 D ⟺ Collatz

10.1 下降引理 D

10.2 引理 D ⇒ Collatz 猜想

步驟一（無非平凡循環）：

假設存在循環 \( \{c_1 < c_2 < \cdots < c_P\} \)。取最小元 \( c_1 \)。引理 D 說存在 \( k \) 使得 \( S^k(c_1) < c_1 \)。但 \( S^k(c_1) \) 在循環中，所有元素 \( \geq c_1 \)。矛盾。\( \square \)

步驟二（無發散軌道）：

從 \( n \) 出發，由引理 D 得 \( n_1 = S^{k_1}(n) < n \)。再由引理 D 得 \( n_2 = S^{k_2}(n_1) < n_1 \)。嚴格遞減的正奇數序列 \( n > n_1 > n_2 > \cdots \) 由 \( \mathbb{N} \) 的良序性必終止於 1。\( \square \)

10.3 引理 D 的算術等價

\( S^T(n) < n \) 等價於 \( B_T > T \cdot \log_2 3 \)，其中 \( B_T = \sum_{i=1}^T v_i \)。

精確表述：

若 \( B_T > T \cdot \log_2 3 \)：\( 2^{B_T} > 3^T \)，故左邊 \( > 0 \)，右邊 \( > 0 \)。對充分大的 \( n \)（\( n > C_T/(2^{B_T} - 3^T) \)）成立。

10.4 逆向

Collatz 猜想 ⇒ 引理 D 是平凡的（軌道到 1 途中必有下降）。

因此：引理 D ⇔ Collatz 猜想。

11. 結構性結果四：循環的算術約束 [Paper C 之 Corollary]

11.1 有界軌道 → 循環

證明：軌道是有限集 \( \{m \in \mathbb{N}_{\text{odd}} : n \leq m \leq M\} \) 中的序列，由鴿巢原理必重複。\( \square \)

11.2 循環方程

壓縮 Collatz 映射的 \( P \)-循環 \( S^P(m) = m \)：

其中 \( C = \sum_{j=0}^{P-1} 3^{P-1-j} \cdot 2^{B - B_{j+1}} > 0 \)。

11.3 循環蘊含 \( 2^B > 3^P \)

由 \( C > 0 \) 和 \( m > 0 \)：\( 2^B - 3^P > 0 \)，即 \( 2^B > 3^P \)，即 \( B > P \cdot \log_2 3 \)。

由 \( \log_2 3 \) 是無理數（超越數，Gelfond-Schneider 定理）：\( 2^B \neq 3^P \) 對所有正整數 \( B, P \)。

所以 \( 2^B - 3^P \geq 1 \)（它們是不同的正整數）。

11.4 循環元素的上界

\( m = C/(2^B - 3^P) \)。

11.5 未解決部分

12. 為何完整證明仍困難（三重不可通約性）

12.1 三重不可通約性

Collatz 映射同時涉及三種不可通約的數學結構：

12.2 所有框架的共同失敗模式

每個框架都能處理這三種結構中的一到兩種，但在第三種面前失敗：

12.3 核心不可化約的困難

所有路線最終都化約為同一個陳述：

此陳述等價於 Collatz 猜想本身，因此不構成「簡化」。

13. 現狀總結

13.1 四個結構性結果（有獨立數學價值）

本報告的核心貢獻是以下四個結構性結果。它們不依賴於 Collatz 猜想是否成立，本身即為完整的定理或代數事實，可獨立應用於相關問題：

1. 結構性結果一（§3）：3 態轉換器譜間隙 = 1/2。將 Collatz 的 carry 傳播寫成 3 態自動機 \(\{A, B, C\}\)，轉移矩陣特徵值精確等於 \(\{1, 1/2, -1/2\}\)。這把一個數論問題化約為有限狀態自動機的譜分析。
2. 結構性結果二（§4）：log₂3 連分數 65/41 屏障。第 6 個收斂子是 Collatz 最壞情況的天然下界；由 \(\log_2 3\) 的超越性（Gelfond-Schneider）保證 \(B/T > \log_2 3\) 的算術不等式永遠嚴格。
3. 結構性結果三（§10）：引理 D ⟺ Collatz。把整個猜想精煉成一個簡潔的下降命題（對任意奇數 \(n > 1\)，存在某步使 \(S^T(n) < n\)）；雙向等價的證明把難度精準定位。
4. 結構性結果四（§11）：循環元素的算術上界。由 \(\log_2 3\) 的無理性給出非平凡循環的尺寸限制 \(m < \frac{2^B \cdot 3^P}{2(2^B - 3^P)}\)，把循環存在性轉成可計算的數論不等式。

13.2 補充工具與計算支援

• §2 Epoch 分解與位移座標：位移座標 \(x = n + 1\) 下，壞步段是純粹的乘以 \((3/2)^{t-1}\)（精確等式）——後續四個結果共用的記號工具。
• §9 計算實驗：對 \(k = 5\) 到 \(k = 44\) 的奇數，最壞 \(B/T\) 始終精確命中 \(65/41\)，數值上支持結構性結果二。
• §5–§8 失敗路線：序數方法、反向樹密度、2-adic 遍歷性、Kolmogorov 複雜度——已確認不足以給出完整證明，但每條路線的限制都精確指向同一個結構性障礙（見 §12）。

13.3 化約後的剩餘困難

本報告把 Collatz 猜想的完整證明從「未知方向」的問題化約為「需要一個確定性 Expander Mixing 定理」的明確子目標——四個結構性結果作為部分結果獨立成立，並把難度精準定位。

14. 附錄：程式碼與符號索引

14.1 主實驗程式

功能：

• 實驗 1：每個位元長度 k 的最壞情況平均 v₂
• 實驗 2：Mersenne 數 (2^k − 1) 的軌道分析
• 實驗 3：Expander Mixing 驗證（v₂=1 比例分佈）
• 實驗 4：滑動窗口 v₂ 分析
• 實驗 5：累積比率 \( R(T) = \Sigma v_2 / (T \cdot \log_2 3) \) 的軌跡
• 實驗 6：所有 k-位奇數的最小累積比率

14.2 深度分析程式

功能：

• 分析 1：\( \log_2 3 \) 的連分數收斂子計算
• 分析 2：大 k 值最壞情況搜尋（智慧抽樣）
• 分析 3：危險軌道的逐步分析
• 分析 4：最壞情況 B/T 比率 vs 連分數收斂子對應
• 分析 5：每個步數 T 的最小下降所需 B
• 分析 6：全軌道最小累積比率分佈

14.3 符號索引

14.4 參考文獻

• Tao, T. (2019). Almost all orbits of the Collatz map attain almost bounded values. arXiv:1909.03562
• Eliahou, S. (1993). The 3x+1 problem: new lower bounds on nontrivial cycle lengths. Discrete Mathematics
• Conway, J. H. (1972). Unpredictable iterations. Proc. 1972 Number Theory Conf.
• Lagarias, J. C. (2010). The Ultimate Challenge: The 3x+1 Problem. AMS.