華僑網 科技教育 如果宇宙的答案是42,那么问题是什么? | 姬扬

如果宇宙的答案是42,那么问题是什么? | 姬扬

导言:
难道这就是宇宙的终极问题吗?是还是不是,这是一个问题。“老实说,我认为问题在于,你从来都不知道问题是什么。”

这是《美国科学院院刊》(PNAS)的一篇数学论文的开场白。这篇文章的作者是两位数学家布克尔(Andrew R. Booker)和萨瑟兰(Andrew V. Sutherland),分别来自于英国的布里斯托大学和美国的麻省理工学院,他们讨论的问题是某个丢番图方程(具有整数解的不定方程)。更准确地说,他们发现了代数不定方程

的整数解(x,y,z),其中最小的数也大于1亿亿,也就是

,1后面跟16个0。

其实,开场白的这句话不是这两位数学家说的,而是来自于亚当斯(Douglas Adams)的著名科幻小说《银河系漫游指南》,一台超级计算机经过700万年的思考,得出了关于“生命、宇宙和万事万物终极问题”的答案—— 42。这本小说里并没有具体地描述这个问题,所以,问题来了:如果宇宙的答案是42,那么问题是什么呢?布克尔和萨瑟兰给出了他们的回答。

萨瑟兰(Andrew V. Sutherland,左)和 布克尔(Andrew R. Booker,右)看到这个方程

,很多人都会想到费马大定理(在1637年左右,法国数学家费马在阅读丢番图《算术》的拉丁文译本时提出的一个猜想):对于任何大于2的整数n,没有任何正整数(x,y,z)能够满足

。显然,n=3只是一种特殊的情况,而且著名数学家欧拉早在1753年就证明了它。至于n是大于2的任何整数的情况,则是在1995年被英国数学家怀尔斯(Andrew Wiles)证明了。
既然

没有整数解,自然就会问,对于什么样的整数k,

有整数解呢?因为一个整数的立方除以9的余数只能是0、1或者8,很容易证明,如果k除以9的余数是4或者5,这个方程就不可能有整数解。但是对于其他的k,仍然有很多方程不知道有没有整数解。即使在4年以前的2018年,对于小于100的k来说,33和42对应的方程仍然没人知道有没有整数解——直到布克尔开始思考这个问题。
2019年,布克尔发表了一篇文章,解决了这个问题,2021年,布克尔和萨瑟兰合作发表的PNAS文章,解决了这个问题,以及其他一些相关问题。
他们是怎么做的呢?利用中学的数学知识,就可以理解布克尔的解决思路,以及33这个问题所涉及的数学和计算内容。42这个问题需要的数学要更多一些,但主要是为了提高算法的效率。这里主要介绍布克尔的第一篇文章。再描述一遍问题。为了便于描述,我利用了答案,把问题重新描述如下:
寻找三个正整数x>y>z>0,满足。
这里不考虑(x,y,z)三个变量里有两个相等的情况,因为这样涉及的计算量很少,容易验证不存在这样的解。
对于这个问题,蛮力搜索当然在原则上是可以的,但是太费时间,所以需要用一些数学和计算技巧。因为

令d=x-y和s=x+y,可以得到,

等式右边是个整数,所以,d=x-y必须是

的因子,经过一些简单的代数运算,就得到

注意到等式右边是完全平方数,所以,左边也必须是完全平方数。
根据你的计算能力和资源,选择一个z的上限B,比如说,

。然后,按照如下流程计算,就可以得到答案了。
1、选择一个整数z(<B),
2、计算


3、寻找

的因子d,

  • 找到一个新的因子,继续进行步骤4;
  • 找不到因子,或者找不到新的因子,返回步骤1,选择一个新的整数z。

4、计算


5、检查

是不是某个整数s的平方,

  • 如果是平方数,就成功了,

  • 如果结果不是平方数,回到步骤3,寻找

的下一个因子。

上述流程的思路很清楚,但是需要的计算量仍然很大,为了减少计算量,布克尔还采用了很多技巧。有些很简单,比如说,(x,y,z)不能是3的倍数,d=x-y有上限,等等;有一些需要初等数论的知识,布克尔教授的文章里给出了一些引理,很有帮助;还有一些技巧相当高级,需要利用一些关于莫德尔曲线(Mordell curve)的结论,可以排除所有d≤40的情况(这部分有些困难,就不介绍了)。
利用这些限制,可以显著减少计算量,但是仍然不太够,主要是因为确定一个数是不是平方数,常规检验(也就是计算一个数的平方根)需要的计算量太大。布克尔采用了一种更有效的方案:用几率的方法判断一个数是不是完全平方数。他设定了一系列检验条件,通不过这些检验条件的,一定不是平方数,通过检验的数很少,对它们进行常规的检验。
这里涉及了“二次剩余定理”。这是初等数论的内容,概念和证明都不难,这里只讲一个非常简化的结论。 // “二次剩余定理”有一个推论:两个整数X和Y的乘积的勒让德符号(XY|p),等于它们各自的勒让德符号(X|p)和(Y|p)的乘积,(XY|p)=(X|p)(Y|p)。
对于整数a和p,勒让德符号(a|p)描述二次剩余的性质,其定义如下
(a|p)=0,如果

(a|p)=+1,如果,而且存在某个整数x,使得

(a|p)=-1,如果,而且不存在任何整数x,使得

如果(a|p)=+1,就称a为二次剩余(mod p);如果(a|p)=-1,就称a为非二次剩余(mod p)。应用这个结论,可以快速地判断某个数XY是不是平方数,因为计算(X|p)和(Y|p)比直接计算(XY|p)更容易。稍微具体的说,是这样的:
1、判断是不是平方数,等价于判断是不是平方数,这个转换只是把除法变成了乘法,判断起来更容易了。
2、选择某个整数(例如)M=5×7×11×13=5005,它是四个最小素数(除了2和3以外)的乘积,不考虑素数2和3是因为前面提到的限制条件已经有效地计算了相关的情况。
3、计算3d和这两个数对整数M取模的余数X和Y,计算勒让德符号(XY|p)=(X|p)(Y|p),这个结果只可能是0或±1。大约有一半的机会,结果是-1,这样的数肯定不是平方数。对素数p=5,7,11,13进行这种操作,就可以淘汰掉大约百分之九十的选手。
4、对于剩下来的幸运儿,还可以用更多的素数考验它们(需要相应地改变M),每次考验可以淘汰大约一半的选手。
5、经过步骤3和4的筛选,就可以大大减少真正需要计算平方根的情况了。上面是数学,下面再简单讨论一下计算。
布克尔证明了,应用上述所有技巧以后,寻找42所需的时间正比于搜索量,或者说B的大小,而相比之下,蛮力计算的用时跟

成正比。事后来看,因为B是10的16 次方的量级,即使用上现在所有的计算机,蛮力计算需要的时间也很容易就超过了宇宙的年龄。

查表可以加快计算。有些数值需要经常算,把它们的结果存下来,需要的时候直接查表,这也是常用的方法,能够“以空间换时间”——因为需要把许多表格存下来。

并行处理也可以让计算加速。每个符合条件的z值可以单独处理,彼此并不影响,这样就可以把任务分配给不同的计算机(或者同一个“并行计算机”的不同的核),结果就是“人多力量大”——大家不会互相干扰,无论谁找到结果,都是最终的胜利。

编程当然也很重要。布克尔的文章里也有描述,但是我不太懂,所以就不多谈了。

利用上面描述的方法和技巧,如果z跑完了上限以内的所有值,仍然得不到想要的结果,你要么放弃,要么设定一个更大的上限,重复上述流程。实际上,布克尔在

这个范围里,只找到了33的结果,

后来,他跟萨瑟兰合作,采用了更精细的算法,在更大的范围搜索,在全球40万台计算机的帮助下,才得到

这些答案检查起来很简单,用笔记本电脑里自带的科学计算器就可以验证,但是,寻找答案所需要的计算量却是非常惊人的。总之,

这个不定方程有整数解吗?答案是肯定的。

难道这就是宇宙的终极问题吗?是还是不是,这是一个问题。后记布克尔(Andrew R. Booker)和萨瑟兰(Andrew V. Sutherland),还有那个证明了费马大定理的怀尔斯(Andrew Wiles),他们的名字都是安德鲁。这个名字有什么奥秘吗?我们注意到,安德鲁这个名字有33个笔画,也许这就是他们成功的奥秘吧。
这里我强行规定了

这个不定方程整数解为正,并根据答案确定了它们前面的加减号。这样描述起来很方便,但是不严谨——布克尔的文章是非常严谨的。

这里提到的两篇文章是:

[1]Andrew R. Booker, Cracking the problem with 33, arXiv:1903.04284. 正式发表于Res. Number Theory 5, 26 (2019)

[2]Andrew R. Booker and Andrew V. Sutherland, On a question of Mordell, PNAS 118 (11), e2022377118.

我觉得,第一篇文章很容易读,第二篇文章要困难得多,可能是因为必须进一步提高算法效率的原因。这里只讲了第一篇文章。

点击下载原文附件 如果宇宙的答案是42,那么问题是什么?.pdf

■ 扩展阅读:

兴风作浪的翻译人 | 姬扬

《半导体的故事》译者的话 | 姬扬

科普困境之窥一斑而知全豹 | 姬扬

量子信息的显学、玄学和科学 | 姬扬

从《科学:无尽的前沿》看科学的功用、规划和实施 | 姬扬

我们需要真正的中文科技文章的预印本文库 | 姬扬

■ 背景简介:本文作者姬扬,中国科学院半导体研究所研究员,科学网博客主页(blog.sciencenet.cn/u/ji)。作者授权风云之声首发。
■ 责任编辑:KK.
关注风云之声 提升思维层次

免責聲明:本文僅代表作者個人觀點,與華僑網無關。其原創性以及文中陳述文字和內容未經本站證實,對本文以及其中全部或者部分內容、文字的真實性、完整性、及時性本站不作任何保證或承諾,請讀者自行核實相關內容。如發現稿件侵權,或作者不願在華僑網發布文章,請版權擁有者通知華僑網處理。

对俄乌战争的军事科学分析 | 汪涛

第四范式下的科教研:算力困局怎么解?


联系我们

联系我们

5143979969

邮箱: cpress@chinesepress.com

工作时间:周一至周五,9:00-17:30,节假日休息

关注微信
微信扫一扫关注我们

微信扫一扫关注我们

关注微博
返回顶部