Terras 定理

Terras 定理是 3x+1 问题中最重要的成果之一, 它最早由 Riho Terras 提出. 这个定理是如此的重要, 这一页将全部用来展现出关于这个定理的逼近和思想方法的一幅图景.  在本页中, 你只需要一些最基本的数学背景知识, 下列所有的证明都不需要一些高等技巧或更深的理论. 

尽管所有引理都被证明了(不带任何跳步和忽略部分), 本页的原意应是把 Terras 定理介绍给 3x+1 问题的新人. 因此请注意, 本页的重点是使这个定理更好理解而非 100% 的严格证明(这个注解里有更精确严谨的证明).

这个定理的最简化版本如下:  几乎所有数的滑翔步数都是有限的.

事实上这太过于简略了. 这样吧, 我们先回来看 3x+1 算法的一个更精确的描述:

重新叙述的 3x + 1 算法

对于任意正整数 N ，定义一个数列如下：
S₀ = N
并对于所有 i > 0

  Si = Si-1 / 2              只要 Si 是偶数
  Si = ( Si-1 * 3 + 1 ) / 2  只要 Si 是奇数

然后我们把满足 S_i < S₀
的最小的 i 称为 N 的停止时间(stopping time)（其实也就是滑翔步数）

例如:

设 N = 17; 那么 S₀ = 17, S₁ = 26, S₂ = 13, S₃ = 20, S₄ = 10, S₅ = 5, 等等。
可以看到 S₂ 是小于 17 的第一项，所以 17 的停止时间是 2。

其实这个重定义并不影响该级数的收敛性.

紧接着我们定义每个数的等价矢量(parity vector)如下:

奇偶矢量(parity vector)

任意的 N 的奇偶矢量 v(N) 定义为： v_i(N) = 由 S_i mod 2 形成的矢量

例如:

对于 N = 17 我们容易得到 v₀ = 1, v₁ = 0, v₂ = 1, v₃ = 0, v₄ = 0, v₅ = 1, 等等.

奇偶矢量直接和 3x+1 算法的分类准则相关, 从而完整地描述了 N 在 3x+1 迭代中的行为/表现.

为了加深对于奇偶矢量的理解, 我们现在看一个简单的引理:

引理 1 :

如果 N 是一个正整数，并且有如下形式： a . 2^k + b (b < 2^k)
那么奇偶矢量的前 k 个分量只与 b 有关。

证明:

对k运用数学归纳法证明如下
当 k = 0 时，我们有 N = 2a + b ，其中 b 只能是 0 或 1
那么由 3x + 1 算法的定义，此时引理得证。
现在假设此引理对于某些 k 成立
令 N = a . 2^k+1 + b (b < 2^k+1)
那么如果 S₀ = N 是奇数，有 S₁ = a . 2^k + b / 2
如果 S₀ = N 是偶数，有 S₁ = 3a . 2^k + (3b+1) / 2
在上述任一种情形下 v(S₁) 的前 k 个分量都只与 b 有关
因此奇偶矢量的前 k+1 个分量也都与 a 无关
综合起来，引理得证。

例如:

令 N = 17 = 0 . 2⁶ + 17. 奇偶矢量的前 6 个分量是(1,0,1,0,0,1). 由引理 1, 对于 任意 有 a . 2⁶ + 17 形式的数这都成立. 因此, (1,0,1,0,0,1)也是 81, 145, 209, 273, 等等数的奇偶矢量的前 6 个分量. 

关于奇偶矢量的另一个引理如下:

引理 2 :

假设 w_i (0 ≤ i < k) 是长度为k的奇偶矢量
那么必存在数 N 使得 v_i(N) = w_i (0 ≤ i < k) 成立

证明:

再次对k运用数学归纳法
当 k = 0 时，我们知道 w₀ 只能是 0 或 1
所以 N 要不是任意偶数，要不是任意奇数
现在假设此引理对于某些 k 成立
令 w_i (0 ≤ i < k+1 ) 是长度为 k+1 的奇偶矢量
那么必存在 N 满足 v_i(N) = w_i (0 ≤ i < k)
由引理 1 我们可把 N 写成 a . 2^k + b (b < 2^k) 的形式
我们取两个数 M₁ 和 M₂, 令 M₁ = a . 2^k+1 + b 且 M₂ = a . 2^k+1 + 2^k + b
对于 M₁ 和 M₂ 我们容易知道 v_i(M₁) = v_i(M₂) = w_i (0 ≤ i < k)
接着在 3x+1 算法中令 S₀ = M₁ 并记 S_k(M₁) = X
由 3x+1 算法的定义，我们有 S_k(M₂) = Y = X + 3ⁿ
其中 n 是 w_i （i从0到k）中奇数的个数
因为 3ⁿ 总是奇数，所以 X 和 Y 一奇一偶
从而 w_k+1(M₁) ≠ w_k+1(M₂)
这就意味着，无论 w_k+1 = 0 还是 w_k+1 = 1
必存在一个数 M 满足 v_i(M) = w_i (0 ≤ i < k+1)
综合起来，引理得证。

例如:

取一个奇偶矢量 (1,0,1,0,0,1,x), 其中 x 为 0 或 1.  那么这与 N = 17 的奇偶矢量的前 6 个分量相同. 并且对于 S₀ = N = 17 我们发现 S₆ = 8, 所以 N = 17 的奇偶矢量的前7个分量是 (1,0,1,0,0,1,0).  如果我们取 S₀ = N = 17 + 2⁶ = 81, 那么由引理 2 我们知道它的奇偶矢量的前 7 个分量一定是 (1,0,1,0,0,1,1), 从而 S₆ 一定是奇数, 实际上 S₆ = 35. 在注意到该奇偶矢量的前6个分量中有三个 1, 故 S₆ 也必须等于 8 + 3³ = 8 + 27 = 35.

下一步就是定义 序 k (order k) 的奇偶数 (parity number):

奇偶数 (Parity number)

对于任意一个数 N ，它的奇偶数 P_k 定义为 P_k = ∑_i<k (v_i . 2ⁱ)

例如:

对于 N = 17 我们有 P₀ = 1, P₁ = 1, P₂ = 5, P₃ = 5, P₄ = 5, P₅ = 37, 等等.

注意到, 序k的奇偶数的二进制表示恰恰就是奇偶矢量前 k 个分量从后往前读的序列. 举个例子, 17 的奇偶矢量开头是 (1,0,1,0,0,1), 因此 P₆ = 37, 而 37 的二进制表示为 100101. 很明显, 对于 序 k  的任一个奇偶数, 我们有 0 ≤ P_k < 2^k

现在我们遇到一个很重要的引理:

引理 3 :

M 和 N 是正整数， 则 P_k(M) = P_k(N) 当且仅当 M ≡ N mod 2^k

证明:

• 由 M ≡ N mod 2^k 可知它们均可被写成如下形式：
M = x . 2^k + b 和 N = y . 2^k + b, 对于 M 和 N ，b 是相同的
由引理 1 ，v 的前 k 个分量只与 b 有关
因此对于 0 ≤ i < k ，v_i(M) = v_i(N) 这样便有 P_k(M) = P_k(N)，必要条件得证
• 令 P_k(M) = P_k(N), 那么自然，对于0 ≤ i < k ，v_i(M) = v_i(N)
假设 M 和 N mod 2^k 分别同余于 b1 和 b2
那么 a . 2^k + b1 和 a . 2^k + b2 这两个数长度为k的奇偶矢量完全相同
从引理 2 ，对于任意一个长为 k 的奇偶矢量 w ，都存在一个数 Q 使得 v_i(Q) = w_i (0 ≤ i < k)
由于长为 k 的奇偶矢量共有 2^k 个，
mod 2^k的同余类也恰有 2^k 个，这样便有 b1 = b2
引理 3 证毕。

由引理 3 我们获知, mod 2^k的同余类可以与序k的奇偶数一一对应, 并且都介乎 0 和 2^k - 1 之间.  这可以看成是 0 到 2^k - 1 的数的一个排列(permutation).

例如:

取 k=3 我们知道 8x + 0 (同余类)映射到 0(奇偶数), 8x+1 映射到 5, 等等. 简而言之, 8x + r (r=0, 1, 2, 3, 4, 5, 6, 7) 分别映射到0, 5, 2, 3, 4, 1, 6, 7. 我们发现 1 映射到 5 , 反之亦然, 但是其他的数都映射到他们自身.  因此 k=3 的映射可以更简短地用 (1,5) 来描述.  类似地, k=4 的映射可以写成 (1,5) (2,10) (9,13).

奇偶矢量的定义明确了它描述 3x + 1 序列的行为/表现的能力.  事实上, 我们可以用 V_i (0 ≤ i < k) 对 S_k 给出一个很好的近似.  这在引理 4 里得到明确的表述.

引理 4 :

令 S₀ = N 为正整数，而 v_i 是它的奇偶矢量.
定义 d(a,b) = ∑ v_i (a ≤ i < b)
特别地，把 d(0,k) 简记为 d(k)
那么 S_k ≈ T_k = S₀ . 3^d(k) . 2^-k
(或如下对数形式： ln(S_k) ≈ ln(T_k) = ln(S₀) + d(k).ln(3) - k.ln(2)) 并且当 S_k → ∞ 时 lim (S_k - T_k) / S_k = 0

证明:

由于 v_i 的每一个分量中的“1”代表了一次加倍(3x + 1)， 而每一个“0”代表了一次减半，很明显的有：
S_i+1 = (3S_i+1)/2 （若 v_i = 1 ） 且 S_i+1 = S_i/2 （若 v_i = 0 ）
因而 S_k = T_k + R_k ，其中 R_k 如下
R_k = ∑ v_i . 3^d(i+1,k) / 2^k-i (0 ≤ i < k)
由于当 S_k → ∞ 时，lim (R_k / S_k) = 0 引理 4 得证。

例如:

取 N = S₀ = 17 且 k = 5 我们有 S₅ = 5. 另一方面, T₅ = 17 . 3² . 2^-5 = 4.78125 仅比真实值小 5% . 对于很大的数, 结果将更加接近.  例如取 N = 1,234,567 将算出 S₅ = 3,125,000, 而另一方面,  T₅ = N . 3⁴ . 2^-5 = 3,124,997.7, 此时估计值与近似值之间的差别小于 10^-6 . S₅

注意到因子 R_k 非负, 这就说明了 T_k ≤ S_k
现在我们有了一个清晰可行的方法通过 v(N) 估算 S_k , 我们便可以用 v(N) 来试探 N 的收敛性. 为此, 我们又引入一个新的定义.

矢量的收敛与发散(Convergent and Divergent vectors)

令 v_i (0 ≤ i < k) 是一个长为 k 的奇偶矢量
记 d(j) = ∑ v_i (0 ≤ i < j)
并定义 c(j) 为 d(j).ln(3) - j.ln(2) （j < k）
那么我们说 v 是收敛的 只要 c(j) < 0 对于任意 j < k 都成立， 并把使 c(j) < 0 成立的最小的 j 称为 v 的 收敛时间 (convergence time)， 也称为任何奇偶矢量为 v 的整数 N 的收敛时间。
最后，如果这样的 j 不存在，我们称 v 是 发散的。

引理 4 明确指出, N 有停止时间 k 的一个必要但不充分条件是 N 的奇偶矢量有收敛时间 k .
我们现已越来越接近真正的 Terras 定理了.  下一个引理将向终点迈出很大一步.

引理 5 :

令 v_i 为长为 k ，具有收敛时间 k 的奇偶矢量， 并令 M 为所有具有奇偶矢量 v 的整数构成的集合。
那么 M 中所有充分大的元素 N 都有停止时间 k。

证明:

首先我们注意到引理 2 断定了必有一些 N 满足集合 M 的条件，故 M 非空。
由引理 3 我们知道，集合 M 的所有元素都在 mod 2^k 的同一个同余类里。
由引理 4 我们容易看出 S₀ < T_i ≤ S_i (0 ≤ i < k-1)
因此 N 必然有一个最小为 k 的停止时间。
这样，当 S₀ → ∞ 时，( S_k ) / S₀ 的极限 便等于 (S₀ . e^c(k) + R_k) / S₀ = e^c(k)
由于 c(k) < 0 很明显有 e^c(k) < 1 继而证明了此引理.

例如:

任意 mod 16 (x ≥ 0) 同余于 3 的数的奇偶矢量 v 都以 (1,1,0,0) 开头, 故 v 的收敛时间是 4.  因此所有充分大的, mod 16 同余于 3 的数都有停止时间 4 .  3 是这样的数中最小的, 也很明显已经“充分大”了, 因为 3 的停止时间正是 4 .

引理 5 有效地表明了, 只有很有限的数字有收敛时间 k , 却没有停止时间 k. 实际上, 除了一个小case:N=1 之外, 就我们所知, 没有数字具有此性质. 有此性质的数应当相对较小(从引理 5 得知), 普遍认为不存在这样的数. 换句话说:

猜想:

对于所有 N > 1 ，它的收敛时间等于停止时间。

回到 Terras 定理之前, 我们还有一个引理.  不过这个引理把我们带到了里最终目标只有一臂距离的地方.

引理 6 :

令 V_k 为所有长为 k 的奇偶矢量组成的集合。
令 W_k 为 V 中所有发散的元素组成的子集。
则 (记 |C| 为集合 C 的元素个数) lim k → ∞ |W_k| / |V_k| = 0.

证明:

由收敛矢量的定义知道，c(k) < 0 是收敛的一个充分但不必要条件。
由于奇偶矢量里 1 和 0 的分布可以用二项式分布来描述，上述极限将受如下约束： lim k → ∞ ∑ _{0 ≤ i < kα} 2^-k . k! / i!(k-i)!
其中 α = ln(2) / ln(3)
这个极限仅仅代表了二项式分布的一部分，并且有一个著名结论，
对于任意小于 ½ 的 α ，此极限为 0 。
由于 ln(2) / ln(3) < ½ ，满足上述条件，于是引理得证。

例如:

下面的表格列出了大量不同的 k 所对应的发散奇偶矢量的个数和相对数(即所占比例), 尽管发散奇偶矢量的个数急剧增长, 它们的相对数实质上是在下降的, 对于相当“不合作”的 k 也是如此. 举个例子, k=70 时, 发散奇偶矢量所占比例大约是 0.001, 也就是说 99.9% 的长为 70 奇偶矢量都是收敛的.

k |Wk| |Wk| / |Vk| 1 1 0.5000 2 1 0.2500 3 2 0.2500 4 3 0.1875 5 4 0.1250 6 8 0.1250 7 13 0.1016 8 19 0.0742 9 38 0.0742 10 64 0.0625

k |Wk| |Wk| / |Vk| 11 128 0.0625 12 226 0.0552 13 367 0.0448 14 734 0.0448 15 1295 0.0395 16 2114 0.0323 17 4228 0.0323 18 7495 0.0286 19 14990 0.0286 20 27328 0.0261

k |Wk| |Wk| / |Vk| 30 1.28e+007 0.01189418 40 6.40e+009 0.00582334 50 3.73e+012 0.00331669 60 2.22e+015 0.00192219 70 1.24e+018 0.00105159 80 8.03e+020 0.00066440 90 5.09e+023 0.00041078 100 3.03e+026 0.00023868 110 2.03e+029 0.00015662 120 1.31e+032 0.00009879

k |Wk| |Wk| / |Vk| 130 8.11e+034 0.00005957 140 5.52e+037 0.00003963 150 3.67e+040 0.00002569 160 2.52e+043 0.00001726 170 1.64e+046 0.00001093 180 1.13e+049 0.00000736 190 7.69e+051 0.00000490 200 4.92e+054 0.00000306 250 7.41e+068 0.00000041 300 1.11e+083 0.00000005

最后,我们回到 Terras 定理本身.  说得再精确一些, 定理的精髓在于, 当给定的区间越来越大时, 区间内那些没有有限的停止时间的数的个数所占的比例趋近于 0 . 换句话说:

定理 (Terras) :

令 M 为一正整数。
记 D(M) 为小于 M 且没有有限的停止时间的数所占的比例。
则当 M → ∞ 使，D(M) 的极限为0 。

证明:

首先，由引理 5 我们承认，只有很有限个的数字的停止时间不等于收敛时间。
现在把区间内的数划分入 mod 2^k 的同余类里。
由引理 3 ，mod 2^k 同余于 m 的每个数都映射到同一个奇偶数 n 上
( 0 ≤ n < 2^k ) ，并因此映射到同一个长为 k 的奇偶矢量上。
但是，引理 6 已经证明，当 k → ∞ 时，发散奇偶向量的个数所占比例极限为 0 。
考虑小于 2^k 并且停止时间不小于 k 的那些 N，
自然的，当 k → ∞ 时，lim D(2^k) = 0.
由此，定理得证。

注解: 上述版本的 Terras 定理是一个简化版. 此定理还可以有另外几种证法, 比如, 精确描述出到底那个极限趋近于零的速度有多快. 更正式和完整的证明可以在这个出色而规范的 3x+1 问题 概要里找到, 作者为 Jeffrey Lagarias.

回到 3x+1 主页面.