首页 > 新闻 > 正文

本文来自微信公众号:原理(ID:principia1687),作者:佐佑,题图来自:视觉中国

著名数学家陶哲轩的伯乐保罗·埃尔德(Paul Erdös)曾说:“数学还没有做好准备面对这样的问题”。专门研究这个问题的数学家Jeffrey Lagarias说:”这是一个危险的问题。人们沉迷于这个问题,但解决它真的是不可能的任务。“

两位数学家口中所说的问题,名为考拉兹猜想

考拉兹猜想是数学中最引人注目的难题之一,它由德国数学家洛塔尔·考拉兹(Lothar Collatz)于1937年最早提出。与众多晦涩难懂的数学猜想不同的是,它看起来非常简单,任何已经学过加减乘除的小学生都可以对它进行推演。

考拉兹猜想说的是:无论选择什么正整数作为开始,通过应用上述函数中的规则,最终都会得到1。

这个问题说起来很简单,理解起来也很容易,从f(n)的表达式来看,它的运算规则一目了然:对于任何正整数,如果数字是偶数,则将其除以2;如果数字是奇数,则让其乘以3,再加1,再除以2;一遍一遍地重复这个过程,直到得到1,然后开始陷入一个循环。

以数字13为例:13是奇数,所以对于f(13)来说,它需要乘以3得到39,加1得到40;这时,40是偶数,所以f(40)需要除以2,得到20;再用20来重复这个计算;20又是偶数,所以只需继续除以2得到10;10还是偶数,除以2后得到5;5是奇数,乘以3、再加1再除以2,得到8;8为偶数,除以2等于4;4再除以2得到2;最后2除以2得到1。

当1开始出现时,事情开始变得有趣了。1是奇数,它需要乘以3再加上1,于是你又会重新得到4。接下来,故事的发展就是我们已经知道的那样,4到2到1再到4——陷入一个循环。如果用箭头来表示整个计算过程,以13为例,我们就会得到考拉兹序列:

任何正整数都会进入这个循环吗?

这正是考拉兹猜想所预测的:无论你以任何正整数开始,最后都会以这个循环结束。不信的话你可以拿任何正整数来试试,看会不会都最终陷入这样一个循环。

 图片来源:swimmingthestyx.com

其实,如果你想要找到一个反例,可能需要代入一个稍微大点的数字才可能有机会,因为目前在计算机的帮助下,数学家已经对每一个小于2⁶⁸的数字进行了验证。尽管每个已被试过的正整数都会在这个循环中结束,但我们仍然不能确定考拉兹猜想是否总是正确,它至今仍只是个猜想,始终没有人能为这个看似简单易懂的猜想给出完整的证明。

 图片来源:wordpress.com

为什么证明每一个数字都符合这个猜想会如此之难呢?

要证明这个猜想,一个重要的思路是,如果能够证明当对任何正整数运用函数f的运算法则时,总会得到更小的数,那么这将会是证明这一猜想的关键。这是什么意思?我们可以以一个与函数f相似,但又稍微简单一点的分段函数g为例。

继续13为例,在函数g下,13的序列会是:

当g中出现1时,它的循环变成了:

相比于f,13在函数g的运算规则下进入循环的速度更快。那么,对所有的正整数来说,在函数g中迭代是否总能循环到1呢?答案是肯定的,这是可以被证明的。

在函数g中,如果n是正偶数,那么g(n) = n/2,始终小于n本身。也就是说,当在函数g中迭代的数字为偶数时,下一个数字一定会更小;如果n是正奇数,那么g(n) = n + 1,大于n,而n + 1是偶数,那么接下来,下一个数字将变成(n + 1)/2,如此一来,对于一个奇数n来说,它在函数g下的迭代序列会是:

而我们已知,当n > 1时,(n+1)/2 总是小于n的。这也就是说,在函数g下,当一个轨道中出现了大于1的奇数n时,就总能在两步之后得到一个更小的数(n+1)/2。

如此一来,无论是n是奇数还是偶数,它在g函数中的迭代都会产生呈越来越小的趋势发展的序列,唯一会打破这个规则的是在变小的过程中出现了1,当1一旦出现,便开始进入循环之中。

那么,为什么同样的方法就无法被来证明考拉兹猜想呢?

如果n是偶数,那么在函数f中,下一个数字n/2会变小。但当n为奇数时,会得到偶数3n+1,接着这个偶数再除以2,得到始终比n大的(3n+1)/2。这种情况在g的证明中是不存在的,对函数g来说,当一个奇数n出现时,两步的迭代之后就能得到更小的数字;但对f来说,情况并非这样。

为什么会出现这一问题?其实,问题出在(3n+1)/2的数值上,它既有可能是奇数,也有可能是偶数。

如果(3n+1)/2是偶数,那么下一个数字将是(3n+1)/4,序列会呈减小趋势;但如果(3n+1)/2是奇数,那么下一个数字将是3(3n+1)/2+1,序列会呈增加趋势。因此,这一方法并不适用于证明考拉兹猜想。

不过,以上这种方法也并非对数学家完全没有启发。从概率来看,(3n+1)/2有一半的概率是偶数,也就是说在下一步能得出小于n的(3n+1)/4的概率为50%,这也就意味着一个奇数在两步迭代后会变小的概率是50%。接着,(3n+1)/4又有50%的概率是偶数,也就是说,一个奇数在经过三步迭代后,变成一个小于自身的一半的数的概率是25%……

最终的结果是,平均来说,当函数f中出现一个奇数时,是会出现减小的趋势的。再加上f函数在遇到偶数时总是会减小,因此从长远来看,在函数f下的迭代所产生一定是趋于减小的序列。这种概率性的论证已被大多数数学家所接受,他们相信这一猜想是正确的,但仍然没有人能发展出一个数学上的严格证明。

对于这个问题,数学家们已经达成普遍的共识,那就是这是个不可能的问题。然而,好在仍有一众优秀的数学家愿意为这个可能是徒劳的问题付出努力,使得在我们这一问题上也并非全无进展。2019年,数学家取得了”最接近考拉兹猜想“的结果,而做出了这一工作的,就是著名的数学家陶哲轩。

2019年9月,陶哲轩在博客上发表了一篇标题为《几乎所有的考拉兹序列都得到了几乎有界值》的文章,他用一种巧妙而隐晦的方式,让考拉兹猜想几乎得到了解决。“几乎”的意思是,他证明了相对于已知能最终达到1的数字的数量来说,无法确定的数字数量可以忽略不计。

在1976年,数学家Riho Terras证明了在反复应用考拉兹函数之后,几乎所有的数字最终都比它们最开始时要小,他证明几乎任何正整数n的考拉兹序列,最终都小于n。陶哲轩的工作对这一结果进行了进一步的限制,他证明了几乎任何正整数n的考拉兹序列,最终都比n/2、√n、ln(n)更小。这也就是说,对于几乎任何正整数,都可以确定它的考拉兹序列会尽可能的向更小的方向发展。

虽然我们几乎可以肯定,陶哲轩的方法无法完全证明考拉兹猜想,但这绝对是在没有完全解决这个猜想的情况下,所能得到的最好结果,他取得了近几十年来在这个问题上的最大进步。与此同时,这也是对想要继续挑战这个问题的数学家的一个警钟:这个看似简单的问题,真的太难了!

参考来源:

https://www.quantamagazine.org/why-mathematicians-still-cant-solve-the-collatz-conjecture-20200922/

https://plus.maths.org/content/os/latestnews/may-aug10/hailstones/index

https://terrytao.wordpress.com/

                                                       

本文来自微信公众号:原理(ID:principia1687),作者:佐佑

猜你喜欢
文章评论已关闭!
picture loss