首页专业知识面对数学史上最简单的未解之谜，陶哲轩给出了几十年来最重要的证明

面对数学史上最简单的未解之谜，陶哲轩给出了几十年来最重要的证明

来源：晰数塔互联网快讯时间：2019年12月14日 13:52

编者按：本文来自微信公众号“新智元”（ID：AI_era），来源：quantamagazine，编辑：大明、小芹，36氪经授权发布。

任取一个正整数，如果是偶数，将其除以2。如果是奇数，将其乘以3再加1，然后重复这个过程，最后结果都是1。

这个问题就是著名的“克拉茨猜想”。它几乎可以说是数学史上未解问题中表达形式最简单的一个，也因此成为数学这棵参天大树上最诱人的那颗果实。

不少资深数学家警告称，这个问题简直有毒，堪称魅惑十足的“海妖之歌”：你走进来就再也出不去，再也无力做出其他任何有意义的成果。密歇根大学数学家、克拉茨猜想问题专家Jeffrey Lagarias表示：“这是一个危险的问题，很多人为其如痴如醉，但目前看真的不可能解决。”

但不信邪的人总是有的。陶哲轩就是其中之一，他已经取得了迄今为止在克拉茨猜想问题上走的最远的成果。

9月8日，陶哲轩在个人博客上贴出了一份证明，表明了至少对绝大部分自然数，克拉茨猜想都是正确的。尽管这份证明算不上是完整证明，但已经算是在这个堪称“有毒”的问题上取得的重大进展。

面对数学史上最简单的未解之谜，陶哲轩给出了几十年来最重要的证明

“我没指望能完全解决这个问题，但目前取得的进展已经超出了我的预期。”陶哲轩说。

克拉茨猜想：最简单的“不可能解决”的问题

克拉茨猜想据称是上世纪30年代由德国数学家LotharCollatz提出的。但其具体出处不详，已知的，从西拉古斯大学大学传到贝尔实验室，再到芝加哥大学。因早期有众多的传播者，所以在传播过程中，克拉茨猜想收获了许多名字：3n+1猜想、奇偶归一猜想、乌拉姆(Ulam)问题、角谷猜想等。

其表述形式之简单让它听起来像是聚会上的一个游戏。对于任何一个正整数，如果是奇数，则将其乘以3并加1。如果是偶数，则将其除以2。不断重复这个过程，最后会发生什么？

直觉上看，你可能会觉得最开始的数字不同会影响最终得到的结果。也许某些数字为开端，最后的结果是1，而以另外一些数字为开端，则会趋于无穷大。

但是克拉茨预测并非如此。他推测，如果最开始的数是正整数，重复这个过程的次数足够多，则无论最开始的数是多少，最终结果都将是1。这之后，1成为初始数，会陷入循环：1、4、2 、1、4，2，1……

多年以来，许多人都对克拉兹猜想的表述之简单（该猜想又被称为著名的“ 3x +1问题”）而对这个问题深深着迷。目前，数学家们测试了五百亿个数，结果克拉茨猜想全部是正确的。

“这个问题看上去没有任何理解门槛，你只要知道‘乘以3’和‘除以2’，就可以完全理解。数学家马克·钱伯兰（Marc Chamberland）说，诱人之处正在于此。Chamberland曾经自制了一段关于该问题的YouTube热门视频，称这个问题为“最简单的不可能解决的问题”。

面对数学史上最简单的未解之谜，陶哲轩给出了几十年来最重要的证明

以下是一个克拉茨猜想验证网页，大家可以自己试试。

https://www.dcode.fr/collatz-conjecture

虽然克拉茨猜想的表述和理解都非常简单，但严格证明却非常困难。

上世纪70年代，数学家证明，几乎所有的克拉茨数列，即重复克拉茨猜想的计算过程中得到的数列，最后得到的数字都将小于第一个数字，显然这是个不完全证明。但也有证据表明，几乎所有克拉茨数列的最终值都在向1靠近。

从1994年以来，一直到陶哲轩今年取得新进展之前，Ivan Korec保持着对这个问题证明的最佳记录，数列的最终值在逐步变小。但距离问题的核心仍然有很大距离。

随着时间的推移，很多数学家得出这样的结论，即：克拉茨猜想证明问题完全超出了当前的理解范围，因此最好将精力花在其他问题上，因为再继续下去也是徒劳。

南卡罗来纳大学的乔舒亚·库珀在一封电子邮件中说：“克拉茨猜想是一个众所周知的难题，以至于数学家倾向于在每次讨论前都加上一个警告，以免浪费时间对它进行研究。”

意外的提示：陶哲轩从匿名网友留言获启发

早在40年前，Lagarias就对这个猜想深感兴趣，当时他还是一个学生。几十年来，他一直充当克拉茨猜想问题非官方信息收集人。他整理了与该问题相关的论文库，并于2010年以《极限挑战：3x+1问题》为题将其中一些论文成集出版。

Lagarias说：“现在，在我对这个问题有了更多了解之后，我仍然觉得它是不可能解决的。”

陶哲轩通常不会在“不可能解决”的问题上浪费时间。2006年，他获得了数学领域的最高荣誉“菲尔兹奖”，被广泛认为是年轻一代中最杰出的数学家之一。他习惯于解决问题，而不是追逐梦想。

陶哲轩曾说：“数学家这个头衔实际上对职业生涯是有害的。它可能导致一个人沉迷于一些重量级问题，这些问题超出了任何人的能力，会浪费很多时间。”

但陶哲轩也不是完全不碰这些问题。每年，他都会选择一个尚未解决的著名问题中尝试一两天。多年来，他为解决克拉茨猜想问题作了几次尝试，但都没有成功。

今年8月，一位匿名读者在他的个人博客上发表了评论，建议他尝试去解决“几乎所有”数字的克拉茨猜想，而不是尝试完全解决。

陶哲轩说：“我没有回复，但这条留言确实让我再次考虑了这个问题。”

他意识到，Collatz猜想在某种程度上类似于一种方程式的形式，即偏微分方程，他正是这个领域取得了职业生涯中一些最重要的成果。

输入和输出：来自偏微分方程的启示

偏微分方程可以用于模拟宇宙中许多最基本的物理过程，例如流体的演化或重力在时空中的波动。它们发生在系统的未来位置（例如将石头扔进池塘后五秒钟的状态）取决于两个或多个因素（例如水的粘度和速度）的影响的情况下。看上去，复杂的偏微分方程似乎与克拉茨猜想这样的简单算术问题无关。

但陶哲轩意识到，二者之间有相似之处。使用偏微分方程，也可以插入一些值，获取其他值，再重复这一过程。所有这些都是为了了解系统的未来状态。对于任何给定的偏微分方程，数学家都想知道，某些初始值最终会导致无穷大的输出值，还是会产生有限值，而不管以什么值作为开头。

面对数学史上最简单的未解之谜，陶哲轩给出了几十年来最重要的证明

在陶哲轩看来，偏微分方程和克拉茨猜想具有相同的风格。因此，他认为研究偏微分方程的思路也可以应用于克拉茨猜想的证明。

一种特别有用的技术涉及一种统计方法，可以用于研究少量初始值（例如，池塘中水的少量初始配置）的长期行为，并以此出发推断所有可能初始设置下的长期行为。

如果引申到克拉茨猜想上，可以理解为从大量数字样本开始，目标是研究在应用克拉茨流程时这些数字的行为。如果样本中接近100％的数字最终恰好等于1或非常接近1，您可能会得出结论，几乎所有数字的行为方式都是相同的。

但是要使结论正确，必须非常仔细地构建样本。就像在总统选举中构建选民样本一样。为了从民调中准确地推断出整个人口的投票意愿，需要以正确比例对共和党人、民主党人，以男女同等的权重对样本进行加权。

数字具有自己的“人口统计学”特征。比如存在奇偶性、是3的倍数，或者数字之间通过其他微妙的方式体现彼此的不同。构造数字样本时，可以将其加权为包含某些种类、但不包含其他种类的数字。选择的权重质量越好，就越能得出关于整体数字的结论。

小心探寻数字加权，陶哲轩给出克拉茨猜想最强证明

陶哲轩所面临的挑战远比弄清楚如何用合适的权重创建一个初始数字样本要困难得多。在Collatz过程的每一个步骤中，处理的数字都在变化。一个明显的变化是，样本中几乎所有的数字都变小了。

另一个可能不那么明显的变化是，这些数字可能会开始聚集在一起。例如，你可以从一个均匀的分布开始，比如从1到100万的数字。但是经过五次Collatz迭代之后，这些数字很可能集中在数轴上的几个小区间内。换句话说，你可能一开始有一个很好的样本，但是五步之后，它就完全扭曲了。

陶哲轩在一封电子邮件中说：“通常情况下，人们会认为迭代后的分布与最初的分布完全不同。”

陶哲轩的关键见解是找出如何在整个Collatz过程中选择一个很大程度上保持原有权重的数字样本。

例如，陶哲轩的初始样本加权后不包含3的倍数，因为Collatz过程很快就排除了3的倍数。陶哲轩提出的其他一些权重更复杂。他把初始样本的权重取为除以3后余数为1的数字，而不是除以3后余数为2的数字。

结果是，即使在Collatz过程继续进行时，陶哲轩的初始样本仍然保持其特性。

“他找到了进一步推进这个过程的方法，这样经过一些步骤之后，你仍然知道发生了什么，”Soundararajan说。“当我第一次看到这篇论文时，我非常激动，认为它非常引人注目。”

陶哲轩使用这种加权技术证明了，几乎所有的Collatz初始值(99%甚至更多)最终都达到一个非常接近1的值。这使他能够得出99%的初始值大于1千万亿的克拉茨数列，最终结果小于200的结论。

可以说，这是该猜想历史上最强的证明结果。

Lagarias说：“这是我们对这个问题的了解取得的一大进步。这肯定是很长一段时间以来最好的结果。”

陶哲轩的方法几乎肯定不能完全证明克拉茨猜想。原因是他的初始样本在过程的每一步之后仍然有一点偏斜。只要样本中仍然包含许多与1相距甚远的不同值，则偏差就很小。但随着Collatz过程仍在继续，样本中的数字趋近于1，小的偏差效应越来越明显——类比来说，民意调查中当样本容量很大时，一个轻微的误算影响不大；但当样本量很小时，就会产生较大的影响。

要完全证明这个猜想，很可能需要另一种方法。因此，陶哲轩的工作既是胜利，也是对为克拉茨猜想着迷的数学家的一种警告：就在你以为自己可能已经把问题逼到了绝路的时候，它却溜走了。

陶哲轩说：“你可以尽可能接近克拉茨猜想，但要完全证明，目前仍然遥不可及。”

参考链接：

https://www.quantamagazine.org/mathematician-terence-tao-and-the-collatz-conjecture-20191211/

陶哲轩博客：https://terrytao.wordpress.com/2019/09/10/almost-all-collatz-orbits-attain-almost-bounded-values/

论文：https://arxiv.org/abs/1909.03562