考拉兹猜想（3n+1 问题） · 公开问题 25

问题

定义迭代 T(n) = n/2（n 偶）或 (3n+1)/2（n 奇）。考拉兹猜想：对每个正整数 n，存在 k 使 T^k(n) = 1。问题源自 1930 年代（考拉兹讲座与 Hasse、角谷等人的传播），陈述之简单与抵抗之顽固形成刺眼反差：数学界通行警示语「数学还未做好对付它的准备」。

主要概念

迭代与停止时间

轨道 17 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 一路振荡向上又骤然坍缩，是「随机游走」直觉的具象化：奇数步使轨道约乘 3/2，偶数步约除 2，长程看除 2 占据统计优势。总停止时间 σ_∞(n) 记首次到达 1 的步数。验证已推进到 n < 2⁶⁸（Barina 2020），周期轨道方面已知任何非平凡循环长度巨大（Eliahou 型下界）。

二进完备域视角

关键转译：把 T 看成二进完备整数环 ℤ₂ 上的连续映射，其迭代完全由「奇偶向量」（每步的奇偶位串）编码。在这一框架下，考拉兹猜想等价于一句可检验的话：每个正整数的奇偶向量最终进入固定周期。这是本页命题 1 的内容，也是 Lagarias 1985 年纲领的基石。

主要命题与证明

命题 1（ℤ₂ 上的共轭；完整证明）　定义 T: ℤ₂ → ℤ₂，T(x) = x/2（x 偶）、(3x+1)/2（x 奇）。定义奇偶向量 Φ(x) = Σ_k≥0 τ(T^k(x))·2^k（τ 取奇偶位）。则 Φ 是 ℤ₂ 到 ℤ₂ 的同胚，且 Φ∘T = 移位∘Φ。

证明　（一）T 良定义且连续：「x 偶」即 x ∈ 2ℤ₂，是 ℤ₂ 中既开又闭的子集，两支定义无冲突；x ↦ x/2 与 x ↦ (3x+1)/2 在 ℤ₂ 上处处连续（3 可逆，2 的除法在 ℤ₂ 内合法——这正是 ℤ₂ 视角的威力），由粘合引理 T 连续。（二）Φ 良定义：数位 τ(T^k(x)) ∈ {0,1}，级数在 ℤ₂ 中收敛（第 k 项的 2 进位权为 2^k → 0）。（三）共轭关系：Φ(T(x)) 的第 k 位 = τ(T^k(T(x))) = τ(T^k+1(x)) = Φ(x) 的第 k+1 位，即 Φ(T(x)) = (Φ(x) − τ(x))/2，恰是移位。（四）Φ 满射：任给位串 ε = (ε₀, ε₁, …)，递归构造 x = Ψ(ε)：若 ε₀ = 0 取 x = 2y，若 ε₀ = 1 取 x = (2y−1)/3（ℤ₂ 中 3 可逆，恒可解），其中 y = Ψ(移位 ε)。每步递归把更高一位的约束固定，极限存在；归纳验证 Φ(Ψ(ε)) = ε。单射由满射与自映射的结构推出（同胚 = 连续双射于紧空间）。□

命题 2（考拉兹猜想的等价重述；完整证明）　正整数 n 的轨道到达 1，当且仅当其奇偶向量最终为周期 2 的模式 (1, 0, 1, 0, …)。

证明　1 → 2 → 1 循环对应奇偶位 (1, 0) 交替：τ(1) = 1，τ(2) = 0。若 T^k(n) = 1，则 k 之后轨道进入该循环，奇偶向量尾部为 (1,0) 重复。反之若奇偶向量尾部周期为 (1,0)，则由命题 1 的共轭，轨道本身尾部进入点列的像，即循环 1 → 2 → 1，特别地到达 1。□

命题 3（不可判定性；陈述与说明）　Conway（1972）：考虑「广义考拉兹映射」——在模 P 的各剩余类上分别取线性函数 n ↦ (a_rn+b_r)/d_r 的映射族——不存在算法判定「任给此类映射，是否每条轨道都到达 1」。Kurtz–Simon（2007）加强：判定「是否存在发散轨道」是 Π⁰₂ 完全的。

说明　Conway 的构造用映射族模拟图灵机：轨道的奇偶向量编码机器计算，到达 1 ⇔ 停机。这不动摇考拉兹猜想本身（原版 T 只是族中一个成员），但摧毁了「用一族统一方法处理所有此类迭代」的希望：任何证明技术若对整个映射族生效，就会与不可判定性冲突。考拉兹问题的解答必须使用 3 与 2 之间的特殊算术——某种尚未被发现的不变量。□

命题 4（最强的密度型结果；陈述）　Tao（2019）：对任意满足 f(N) → ∞ 且增长慢于三重对数的函数 f，几乎所有 n（在对数密度意义下）的轨道最小值 min_k T^k(n) < f(n)。另：Krasikov–Lagarias 证明 1 到 x 之间最终到达 1 的整数至少有 x^0.84 个。

说明　Tao 的方法把轨道的「随机游走」模型做到密度意义的极限：除一个（对数密度为零的）例外集外，几乎所有轨道都被压到任意缓慢增长函数之下。但猜想要求的是把例外集缩到空——从「几乎所有」到「所有」之间隔着至今无人跨过的鸿沟，因为不可判定性现象表明不存在普适的密度交换论证。□

进展与文献

Lagarias 的两篇权威综述（Amer. Math. Monthly 92, 1985；以及《The Ultimate Challenge: The 3x+1 Problem》, AMS 2010）；Tao, Almost all orbits of the Collatz map attain almost bounded values（Forum Math. Pi 2022）；Barina 的 2⁶⁸ 验证（J. Supercomputing 2020）；Conway, Unpredictable iterations（1972）。Krasikov–Lagarias 的 x^0.84 下界见 Acta Arith. 2003。