搜索算法如何改变数学课程

M长期以来，数学家们一直想知道是否有可能将数字33表示为三个立方体的和——也就是说，是否等式33 =x³+Y³+Z³有一个解决方案。例如，他们知道29可以写成3³+1³+1³，而32不能表示为三个整数的三次方之和。但33的问题64年来一直没有解决。

现在，布里斯托尔大学(University of Bristol)的数学家安德鲁·布克(Andrew Booker)终于破解了这个难题:他发现（8866128975287528）³+（-8778405442862239）³+（-2736111468807040）³=33。

布克通过设计一种新的搜索算法，从千万亿种可能性中筛选出了这三个16位整数。该算法在大学的超级计算机上连续运行了三周。(他说他原以为需要6个月，但一个答案“在我预期之前就出现了”。)本月早些时候，当他的答案在互联网上传开时，数论同行和数学爱好者们都兴奋不已。根据关于这一发现的数字档案视频当布克得知这一消息时，他自己也在办公室里高兴得跳了起来。

“他找到了一种真正更有效的找到解决方案的方法。”

为什么这么高兴？部分原因是找到这样一个解决方案非常困难。自1955年以来在美国，数学家们利用他们能得到的最强大的计算机，在数轴上寻找满足“三个立方体和”方程的三个整数K=x³+Y³+Z在哪里K是一个整数。有时解决方案很简单，例如K= 29;另一些时候，已知解不存在，如所有被9除后余数为4或5的整数，例如数字32。

但通常情况下，解决方案是“非平凡的”。在这些情况下，像（114844365）³+（110902301）³+（–142254840）³，等于26的三个三次整数看起来更像彩票，而不是具有可预测结构的任何东西。目前，数论学家发现此类解决方案的唯一方法是反复玩数学“彩票”，利用计算机辅助搜索的强大力量尝试不同的立方整数组合，并希望“赢”

但是，即使有越来越强大的计算机和更高效的算法来解决这个问题，一些整数仍然顽固地拒绝获得任何中奖。33是一个特别顽固的例子:在布克找到他的解之前，它是100以下仅剩的两个整数之一(不包括那些绝对不存在解的整数)，仍然不能表示为三个立方体的和。33个已经解决了，剩下的只有42个。

之所以花了这么长时间才找到33的解决方案，是因为在数字线上一直搜索到10¹⁶在布克设计出他的算法之前，对于右边的数字三重奏来说，在计算上是不切实际的。奥地利科学技术研究所的数字理论家蒂姆·勃朗宁说:“与10年前的计算机相比，他不仅在更大的计算机上运行了这个程序，他还发现了一种更有效的定位解决方案的方法。”

布克解释说，以前的算法“不知道他们在寻找什么；他们可以有效地搜索给定范围的整数，以找到问题的解K=x³+Y³+Z适用于任何整数K，但他们无法瞄准一个特定的目标，比如K= 33. 布克的算法可以，因此它的工作“在实际应用中，可能比采用无目标方法的算法快20倍，”他说。

33岁的中奖票已经拿到，布克计划下一步寻找42岁的解决方案。（他已经确定在10万亿范围内不存在任何物质；他将不得不进一步观察数字线，至少是10¹⁷）但即使他或另一位数字理论家已经为每一个合格整数确定了三个立方体之和的解（最多100个），他们也将面临11个更“顽固”的整数，而三个立方体之和的解不在101到1000之间，而且还有无穷多的整数。更重要的是，布克和其他专家说，为这些顽固分子中的一个找到的每一个新的解决方案都无法从理论上阐明在哪里或如何找到下一个解决方案。布克说：“我不认为这些研究目标本身就足够有趣，足以证明大量资金可以任意占用一台超级计算机。”。

那么，为什么还要为33或42而烦恼呢？

也学数学

如何解决有史以来最难的逻辑难题

由布莱恩·加拉格尔

1957年，当雷蒙德·斯穆利安(Raymond Smullyan)在普林斯顿大学(Princeton University)攻读博士学位时，他的手下是一位理论计算机科学的创始人，他偶尔会去纽约。在一次访问中，他遇到了一位“非常迷人的女音乐家”，在他们的……阅读更多

布克解释说，“非常有趣的是，每一个新发现的解决方案都是关于三个立方体之和问题本身的“帮助你决定什么是正确的工具”。这个问题，说成K=x³+Y³+Z这就是数论学家所说的丢番图方程——一种代数结构，其性质吸引了数学家数千年。布朗宁说：“它们足够丰富，可以对与丢番图方程无关的[其他数学]语句进行编码。”。“他们足够富有，可以模拟计算机。”

丢番图方程是多项式方程，其未知变量必须取整数值。它们的基本性质会阻碍数论者。例如，没有数学方法可以可靠地判断给定的丢番图方程是否有解。根据布克的说法，三个立方体之和问题是这些棘手的丢番图方程中“最简单”的一个。布朗宁补充道：“这正是我们能够处理的最前沿问题。”。

正因为如此，数论家们渴望了解关于三个立方体之和的一切。一个主要的结果将是证明以下猜测：K=x³+Y³+Z对于每个整数，有无穷多个解K,除K被9除后有4或5的余数。为这种证明而设计的工具可能会打开问题的逻辑，或应用于其他丢番图方程。布克对33的研究结果为这一猜想提供了支持，使数字理论家更加相信这是一个值得研究的证据。事实上，每次数字理论家用他们的搜索算法进一步查找数字线时，例如，通过扩展到10¹⁴2009年，到10年¹⁵2016年，现在是10年¹⁶2019年，可靠地找到了以前顽固整数的新解决方案，排除了可能的反例。

布朗宁说：“所有这些都是数据的积累。”。他指出，布克针对33的新解决方案“不会改变这一领域的数学研究进程。但令人欣慰的是，情况正在按应有的方式下降。”

约翰·帕夫卢斯是一位作家和电影制作人，他的作品曾在科学美国人，彭博商业周刊，和美国最好的科学与自然写作系列。他住在俄勒冈州波特兰市。

首席艺术信贷：露西阅读Ikkanda/Quanta杂志

经许可转载自广达电脑杂志的抽象博客。