考拉兹猜想：数学还不知如何应对的问题
考拉兹猜想：数学还不知如何应对的问题2017-07-14
小雨
中科院物理所
http://mmbiz.qpic.cn/mmbiz_gif/tqOuxs8dsHPGXBd4nEYicfaPEIHick6LXyD2BmAQ5NLZ9ZrmqFmclNG2dGzfwg3zEOFvZocsevWIs1hyz2UwzyHA/0?wx_fmt=gif（图片来源: Alex Bellos & Edmund Harriss）
上面这幅看着像是正在野蛮生长的水藻，又像正在绽放的礼炮的动画，实际上展示的是一个复杂的数学问题——它为考拉兹猜想(Collatz conjecture)提供了一个新视角。
考拉兹猜想是数学中最引人注目的难题之一，它也被称为奇偶归一猜想、3n+1猜想、冰雹猜想还有角谷猜想等等。这个猜想的很容易掌握，你只需要知道如何加1，如何除以2，以及何乘以3就行了。
然而，这般的简单性却与证明猜想本身的难度形成了鲜明的对比。著名数学家保罗·埃尔德什（Paul Erdös）曾说：“数学还没有做好准备面对这样的问题。”上图中的动画就为大家展示了为什么这是一个如此难于破解的问题。http://mmbiz.qpic.cn/mmbiz_jpg/QAEJXB03eMBKtWetxHeOW9dvN5IA8hh4YF06U3zUAqDrCVK4LQvw6l5sCAC9848dribhQCEylQNQkYqlShfNjFQ/0?wx_fmt=jpeg（保罗•埃尔德什是发表过论文数量最多的数学家，论文总数约1500多篇，与511位数学家合作编写过论文。也是著名数学华裔家陶哲轩的伯乐）
它的运算规则非常简单：首先，取一个任意正整数，根据以下规则进行运算
[*]若数字为偶数，则将其除以2;
[*]若数字为奇数，则让其乘以3，再加1，再除以2;
[*]重复上述过程。
我们以数字13为例：
[*]13是奇数，所以我们将其乘以3倍得到39，加1得到40，减半后得到20;
[*]再用20来重复这个计算，20是偶数，所以只需减半得到10；
[*]10也是偶数，除以2后得到5；
[*]5是奇数，乘以3、再加1再减半，得到8；
[*]8为偶数，除以2等于4；
[*]4再减半得到2；
[*]最后2除以2得到1。
因此13的完整序列为：13 → 20 → 10 → 5 → 8 → 4 → 2 → 1
考拉兹猜想首先由德国数学家Lothar Collatz在1937年提出：无论选择什么正整数作为开始，通过应用上述的规则，最终都会得到1。
大多数数学家都认为这是正确的。我们已经可以通过计算机来检测非常庞大的数字，就目前结果来看还没发现任何反例。但至今也仍没有人知道该如何证明这个猜想。http://mmbiz.qpic.cn/mmbiz_png/tqOuxs8dsHPGXBd4nEYicfaPEIHick6LXyoOSQIrTicp4JhrWsorMW2TSHqepWib1UTrKcpwYs3nibe5xgPrPtO1Jbw/0?wx_fmt=png（图片来源: Visions of Numberland/Alex Bellos）
上图显示的是我们一般在讨论该猜想的书籍或论文中常常看到的树形图。对于树中的每个数字在分支以从上往下的方向显示考拉兹序列中的数字， 例如之前列举的数字13，顺着13往下找便能找到根据考拉兹规则计算出的那一系列数字。由于迄今为止调查到的所有数字都会到达4、2，最后再到1，因此所有数字都是起源于同一树中的分支。
http://mmbiz.qpic.cn/mmbiz_png/tqOuxs8dsHPGXBd4nEYicfaPEIHick6LXylVr2MOVzY6icotqribrMJKxickgBQ5pCfQicAzvNeuP29Zxl9DRia08Vmeg/0?wx_fmt=png（图片来源: Visions of Numberland/Edmund Harriss）
为了说明这个问题为何如此复杂，费耶特维尔的阿肯色大学的数学艺术家埃德蒙·哈里斯(Edmund Harriss)在标准图的基础上新添了一条关于分支方向的规则，用来反映一个数字是由两种算法中的哪一种运算而生成，如上图所示。
这种曲折揭示了从一个给定数字到1的路径有多难以预测。无论你处在树枝中的哪个数字，如果在你上面的数字是你的两倍，则上端分支会以固定角度向顺时针方向转动；如果不是两倍，则以固定角度向逆时针方向转动。
我们将数字去掉，并将分支的线条加粗(如上右图)，就得到了文章开头的动画中所显示的大致样子。这幅动画显示树在包含10000以下的所有数字时会如何生长。它完美的为我们展示了一个简单有序的规则是如何造成严重的混乱和无序的：整个结构看起来自然又野蛮。哈里斯所制作的这些图像让我们顺接了解到，为什么要解决考拉兹猜想会如此困难。
有什么是我们已经可以证明的呢？
首先，我们可以证明，4、2、1是唯一简单的固定循环模式。一个简单的循环模式意味着它只涉及到一个奇数，因此 3n + 1在这个过程中只使用一次。在4、2、1中，唯一的奇数是1，唯一一次需要用到 3n + 1 的机会是将1转换为4。
假设一个简单的循环模式包含奇数n，那么 3n + 1 必须是 2n 的倍数。因为我们必须能够从 3n + 1 除以 2 这个过程中返回到数字 n。也就是说：3n + 1 = y2n，其中 y 是一个正整数。
若 y 是正整数，那么可取到的最小的值是1，即如果 y = 1，那么3n + 1 = 2n。这个等式显然不对，因为 n 是一个正整数。取下一个最小正整数y，即 y = 2，我们得到等式：3n + 1 = 4n，得出 n = 1。从而得到重复模式1、4、2、1、4、2.…… 如果继续增加 y 的值，让 y ≥ 3，则有3n + 1 =y2n ≥ 6n，这意味着1 ≥ 3n，所以1/3 ≥ n。
同样，因为 n 是正整数，所以这个不等式也不对。因此，我们已经证明4、2、1是唯一简单的重复模式。如果一个考拉兹序列最终落在一个简单的循环模式上，那么这个模式必须是4、2、1…… 然而，这并不能证明没有含有多于一个奇数的重复模式。
另外一件可以证明的事是，有无数的数字能产生循环性模式4、2、1。实际上，任何以 n = 2^m 的形式的数字 n，其中 m 是正整数时，最终都会产生循环在4、2、1周期上的序列。显然这样的数字 n 为偶数，所以对 n 来说考拉兹过程的第一步是将它除以 2 得到 2^(m-1) 。如果 m-1 = 0，那么 2^(m-1) = 1，证明已经到达4、2、1周期；如果 m-1> 0，那么 2^(m-1) 是偶数，所以下一步运算也是除以2。
重复这个过程表明序列中的所有数字均为偶数，所以进程中的所有步骤都是除以2，所以最终都会降至4、2、1。这对于任何正整数m都成立的，因此证明了有无限多的数字在考拉兹序列中最终落在这个周期上。但同样的道理，这并不能证明每个数字在考拉兹运算中都会产生一个4，2，1的序列。如果你觉得这听上去有点拗口，这有一个简单的类比：偶数有无穷个，但并不是每一个数字都是偶数。
考拉兹猜想看似简单，实际却如此复杂。真心期待能早日看到全部的证明过程。
参考来源：https://www.newscientist.com/article/2139238-mathematics-has-a-bad-hair-day/https://plus.maths.org/content/os/latestnews/may-aug10/hailstones/index
页:
[1]