很简单但还没有解决的Collatz猜想

作者 | Patrick Honner

译者 | 慕容玖

原载于 | Quanta Magazine

引入

善意提醒：不要尝试解决这个数学问题. 你会受到诱惑的.

这个问题很简单, 很容易理解, 也很吸引人. 只需选择一个数字 ：如果是偶数, 则将其减半；如果是奇数, 则将其乘以并加. 得到新数字后再重复以上过程. 最终你会陷入无尽的循环.

以为例：

我们回到了, 我们知道接着会发生什么：会变成,再到, 再到, 以此类推,我们陷入了循环.

"臭名昭著"的 Collatz (科拉茨) 猜想说, 从任意正整数开始, 你总是会陷入这个循环. 你可能会忽视本文开头给出的尝试解决它的提醒：它看起来太简单、太有序, 让人无法抗拒. 事实上, 很难找到一个没有研究过这个问题的数学家. 之所以说Collatz猜想"臭名昭著", 是因为尽管尝试过的每个数字最终都陷入了这个循环, 但我们仍然不能确定它一定是正确的. 虽然它广受关注, 但这仍然只是一个猜想.

当然对它的研究也是有进展和成果的. 著名世数学家陶哲轩在2019年给出了一个证明, 在这个问题上取得了几十年来最大的进步. 下面让我们看看是什么让这个简单的问题变得如此复杂.

Collatz猜想

为了理解 Collatz猜想, 我们将从以下函数开始：

这是一个分段函数, 输入自变量, 输出的结果取决于是奇数还是偶数. 该函数 执行我们前面描述的规则：例如, , 因为是偶数, 而, 因为是奇数. 由于奇数输入的规则, Collat​​z 猜想也称为猜想.

Collat​​z 猜想涉及函数的“轨迹”. 如果从一个数字开始并重复应用一个函数, 获取每个输出值并将其作为新的输入值反馈到函数中, 那么你将得到一个轨迹. 我们称为“迭代”函数. 我们已经计算过在作用下数字的轨迹.

表示轨迹的一种简便方法是用带有箭头的序列. 下面是作用下的轨迹：

我们发现最后我们陷入了循环

类似地, 作用下的轨迹可以表示为

我们再次陷入同样的​​循环. 再尝试几个例子, 你会发现轨迹似乎总是稳定在循环中. 初始值是或会很有趣. 如果你有几分钟的空闲时间, 请尝试初始值, 如果计算正确, 你将在步后陷入循环.

Collat​​z猜想指出, 在函数作用下, 每个数字的轨迹最终都会到达. 虽然还没有人能证明这一猜想, 但已经验证了对小于的所有数字都是正确的. 因此, 如果你在寻找反例, 你可以从大约开始.

简化版的猜想——Nollat​​z猜想

验证Collat​​z猜想对于任何确定的数字是否正确都很容易：只需计算轨迹直到达到. 但是要证明对任意数字都正确却很难, 让我们探索一个稍微简单的函数.

函数与类似, 但对于奇数, 它只是加. 由于和是不同的函数, 因此数字在作用下的轨迹与在作用下的轨迹是不同的.

例如, 以下是和在作用下的轨迹：

请注意, 在的作用下的轨迹到达的速度比在作用下更快. 同样也是.

在这些例子中, 作用下的轨迹似乎也会趋于稳定, 只是在一个更简单的循环中：

我们可能会猜想作用下的轨迹总是能到达数字. 我将其称为“Nollat​​z”(诺拉茨)猜想, 当然我们也可以将其称为猜想. 我们可以通过测试更多的数字来探索这个问题, 但是知道某些数字(甚至是其中的 个数字)是正确的, 并不能证明它对每个数字都正确.

幸运的是, Nollat​​z猜想是可以被证明的.

具体过程如下：

我们知道正整数的一半总是小于该整数本身. 因此, 如果 是偶数且为正数, 则 换句话说, 当一个轨迹到达偶数时, 下一个数字总是更小.

接着, 如果是奇数, 则 但由于 是奇数, 是偶数, 因此我们知道接下来轨迹的走向： 会将 减半. 对于奇数轨迹是：

注意到,当时,

这就说明, 当作用下的轨迹到达大于的奇数时, 两步后我们将始终处于较小的数字.

现在我们可以概述Nollat​​z猜想的证明：对于任意轨迹, 都会呈递减趋势. 唯一的例外是轨迹到达时. 一旦到达, 就会陷入循环.

尝试证明Collat​​z猜想

类似的论证适用于Collat​​z猜想吗？让我们回到原来的函数,

与一样, 将应用于偶数结果会变小, 将应用于奇数会产生偶数, 这意味着我们知道接下来会发生什么：会将新数减半. 当为奇数时,下的轨迹如下所示：

但这里就是我们证明不下去的关键点. 不像之前的例子, 这个数字总是比大, 证明Nollatz猜想的关键是奇数必须在两步后变小, 但在Collatz的情况下并非如此. 我们的论点行不通.

你现在可能会对证明Collat​​z猜想是错误的感到兴奋：毕竟, 如果轨迹上的数字继续变大, 那么它怎么会降到呢？但这一论点需要思考接下来的情况, 接下来会发生什么就说明了为什么Collatz猜想如此难以捉摸：我们无法确定是偶数还是奇数.

我们知道是偶数. 如果也能被整除, 那么也是偶数, 轨迹就会递减. 但是如果不能被整除, 那么就是奇数, 轨迹就会递增. 一般来说, 我们无法预测哪个是真的, 所以我们的论点就停滞不前了.

但是这种方法并不是完全无用的. 由于所有正整数中有一半是偶数, 因此有的可能性是偶数, 这使得轨迹上的下一步是, 对于这比小, 所以有一半的时间奇数应该会在两步之后变得更小.

同样, 也有的可能性是偶数, 这意味着奇数在三步后有的可能性会减少到不到开始时的一半.

诸如此类. 最终的结果是, 在平均意义上, 当Collatz轨迹遇到奇数时, 数字会递减. 由于Collatz轨迹总是遇偶数递减, 这表明从长远来看, 所有Collatz轨迹都必须递减. 这一概率论据广为人知, 但还没有人能够将其扩展到对这一猜想的完整证明.

数学家研究成果

然而, 几位数学家已经证明, Collatz猜想“几乎总是”正确的. 这意味着他们已经证明, 相对于他们知道的最终到达的那些数字的数量, 他们不确定的数字的数量可以忽略不计. 1976年, 爱沙尼亚裔美国数学家Riho Terras证明, 在反复应用Collatz函数后, 几乎所有的数字最终都会小于它们的初始值. 正如我们在上面看到的, 显示轨迹上的数字不断变小是表明它们最终达到的一条途径.

2019年, 当今世界上最杰出的数学家之一 Terence Tao(陶哲轩)在这一结果的基础上有所改进. 此前Terras证明了对于几乎所有的数字, 的Collatz轨迹最终都会小于. 而陶哲轩证明了对于几乎所有的数字, 的Collatz轨迹最终都要小得多：小于, 小于, 小于(的自然对数), 甚至小于每个其中是任何趋向无穷大的函数. 也就是说, 对于几乎每个数字, 我们可以保证它的Collatz序列是我们想要的那样小. 在一次关于这个问题的谈话中, 陶说这个结果“几乎是在没有真正解决的情况下尽可能接近Collatz猜想的一个结果. ”

即便如此, 这个猜想仍将继续吸引数学家和爱好者. 所以选择一个数字, 任何一个数字, 然后试一试. 只要记住, 你已经被提醒过：不要陷入无休止的循环.

关于作者

Mathematics and Computer Science Teacher in New York City

1. 原文发布于 Quanta Magazine