质数数列（既是质数又是合数的数）:16·机器之心Pro

选自Quanta Magazine

作者：Erica Klarreich

机器之心编译

编辑：魔王

在著名的埃尔德什等差数列猜想证明之路上，数学界可能又前进了一步。

埃尔德什等差数列猜想（Erdős conjecture on arithmetic progressions），又称埃尔德什 - 图兰猜想（Erdős-Turan conjecture），是由匈牙利数学家、沃尔夫数学奖得主保罗 · 埃尔德什与保罗 · 图兰（Pál Turán）共同提出的关于调和发散数列的等差子序列的数论猜想。

该猜想的内容是：

埃尔德什等差数列猜想内容。（图源：维基百科）

2004 年，陶哲轩和本 · 格林证明了该猜想的弱化版本。

最近，两位数学家 Thomas Bloom 和 Olof Sisask 解决了这一著名猜想的第一大部分，即整数无穷数列一定包含长度至少为三的等差数列（如 26, 29, 32）。

埃尔德什一生中提出了数千个问题，但哪些数列包含「等差数列」这个问题是他的一生最爱。

「我认为很多人将该猜想看作埃尔德什的 NO. 1 问题，」剑桥大学数学系教授 Timothy Gowers 表示。他是 1998 年菲尔兹奖获得者，曾花费大量时间试图证明这一猜想。「令人高兴的是，一些加性组合研究者有志于探究该猜想。」

通常，越稠密的数列越有可能包含等差数列，因此埃尔德什提出了一种简单的数列稠密度测试：求数列中所有数字的倒数和。如果数字多到可以令倒数和发散，则埃尔德什猜想该数列应包含任意长度的等差数列，如等差三元组、四元组等。

最近，来自剑桥大学的 Thomas Bloom 和来自斯德哥尔摩大学的 Olof Sisask 发表论文，证明了这一猜想适用于等差三元组（如 5, 7, 9）。他们证明，只要数列中所有元素的倒数和发散，则它必然包含无穷多个等差三元组（即包含三个数字的等差数列）。

Thomas Bloom 和 Olof Sisask

「这一发现是这么多年来的标志性事件，这是一件大事。」加州理工学院 Nets Katz 教授说道。

质数集合的倒数和是发散的。20 世纪 30 年代，Johannes van der Corput 使用质数的特殊结构表明，它们确实包含无穷多个等差三元组（如 17, 23, 29）。

但 Bloom 和 Sisask 的新发现意味着，在证明质数数列包含无穷多个三元组时，无需掌握质数的独特结构。你只需要知道，质数的数量足够多，足以使其倒数和发散，而这一点在几个世纪之前就被数学家们发现了。

牛津大学数学研究所高级研究员 Tom Sanders 在一封邮件中表示：「Bloom 和 Sisask 的研究结果表明，即使质数具备与以往完全不同的结构，它们仍然能够保证拥有无穷多个等差数列。」

Bloom 和 Sisask 发表的论文长达 77 页，这需要数学家花费一定的时间和精力认真阅读和评审。不过，很多人乐观地认为他们的证明是正确的。「这个证明确实很像样。」早期工作为这一结果奠定了基础的 Nets Katz 表示。

Bloom 和 Sisask 的定理表明，只要数列足够稠密，特定的模式就一定会出现。该发现符合牛津大学 Sarah Peluse 对数学领域的基本口号：「完全的无序是不可能的。」（这句话最初出自数学家 Theodore Motzki。）

被掩盖的「稠密性」

只要数列足够稀疏，则使其不包含等差数列是件很简单的事情。例如，对于序列 1, 10, 100, 1,000, 10,000, …（其倒数和为有尽小数 1.11111…）。这些数字的稠密度极速下降，你永远无法从中找出一个长度 3 的等差数列。

你或许会思考，是否存在非常稠密但不包含等差数列的数集？

你可以从头开始尝试，使数列中所有数字无法形成一个等差数列。最后得到了序列 1, 2, 4, 5, 10, 11, 13, 14, …。第一眼看上去似乎很稠密，但是随着数字越来越大，该数列变得非常稀疏，例如当到达 20 位数字时，只有大约 0.000009% 的数字出现在数列中。1946 年，Felix Behrend 提出了更稠密的示例，但是它们很快就变得稀疏了，数字到达 20 位时，数列中只出现了全部数字的 0.001%。

现在我们来看另一个极端。如果你的数列包含几乎所有整数，那么它必然包含等差数列。

但是在这两个极端之间是广阔且神秘未知的中间领域。数列稀疏性达到什么程度，仍能确保数集包含等差数列呢？

埃尔德什提供了一个可能的答案。他认为倒数和可以用来揭示「稠密性」：最大数字为 N 的数列的稠密性至少逼近 1/N 的位数。也就是说，数列越来越稀疏是可以的，只要稀疏化速度足够慢就行：如果数列中最大的数是 5 位数，则稠密性至少是 1/5；如果数列中存在 20 位数，则稠密性至少是 1/20，依此类推。

当这一稠密性条件得到满足时，埃尔德什猜想，该数列应包含无穷多个任意长度的等差数列。

1991 年 6 月，埃尔德什在剑桥大学授课。

1953 年，Klaus Roth 开始证明埃尔德什等差数列猜想。在三年后帮他获得 1958 年菲尔兹奖的一项工作中，他构建了一个可以确保存在等差三元组的稠密性函数，其稠密性没有埃尔德什猜想得那么低，但是随着数列越来越长，该值趋近于 0。Roth 的定理意味着数列稠密性将最终低于 1%，再低于 0.1%，再低于 0.01%…… 只要稠密性低于这些阈值的速度足够慢，则该数列必然包含等差数列。

Roth 的方法依赖于这一事实：具备其所选稠密性的大多数数列「想要」包含等差数列，它们包含足够多不同的数字对，这些数字对的中心值也属于该数列，从而出现等差三元组。

棘手的部分在于如何将这一属性从「大多数」泛化到「全部」数列，甚至那些结构尽量避免等差数列的数列。

基于一个高度结构化的数列，Roth 想到使用傅里叶变换映射其「频谱」，从而蒸馏数列结构。这可以检测出数列中表现强烈的重复模式，也是 X 光片和无线电频谱底层技术所涉及的数学知识。

一些频率出现的时候要比别的频率更加强烈，这些变体更突出了模式本身，例如强频率可能表明数列包含更多奇数。如果是这样，你只需专注于奇数，这样你就可以得到比最初更加稠密的集合了。Roth 证明，经过有限数量的蒸馏后，可以获得足够稠密的数字集合，且它们包含等差数列。

在过去的半个世纪中，Roth 的方法启发了解析数论领域的许多发展。斯坦福大学数学系教授 Jacob Fox 表示，「这些是很有影响力的想法。」

从纸牌游戏中找等差数列

Roth 的观点仅对最开始比较稠密的数集有效，否则重复的蒸馏只会使数集衰减。其他数学家逐渐发现一些方法，可以从 Roth 的方法中得到更多，但却无法解决埃尔德什等差数列猜想中的稠密性问题。Fox 表示，「这似乎是很难跨越的槛儿。」

2011 年，Katz 和 Michael Bateman 发现了在更简单设置下克服上述障碍的方法：在 Set 纸牌游戏中，寻找符合三元组模式的纸牌。他们发现，存在一种精确的方式，可以将匹配的 Set 三元组纸牌看作等差数列，而且就像在整数数列中那样，你可以询问放下哪部分纸牌才能确保找到至少一个三元组。

这个问题是整数数列对应问题的简化版模型，因此数学家希望 Bateman 和 Katz 的发现可以为证明埃尔德什等差数列猜想提供突破口，尤其是与其他近期进展结合之后。

在 Bateman 和 Katz 的论文发表后不久，Gowers 启动了一个大规模线上合作项目——Polymath，进行此类尝试。

但是，这个项目很快搁浅。「这需要很高超的技术能力，这个项目更适合一两个为此坚持了很久的人来执行。」Gowers 表示。

幸运的是，Bloom 和 Sisask 出现并做了尝试。最初，二人受到埃尔德什等差数列猜想中技术之美的吸引，开始各自思考该猜想。「这是我最初涉及的研究问题之一。」Sisask 说道。

2014 年，Bloom 和 Sisask 联手。2016 年，他们认为自己得到了解决方案。Bloom 甚至在一次讲座中宣布了结果，不过后来发现其中一些论据站不住脚。于是他们继续努力，深入探索 Bateman 和 Katz 方法的内部原理，并最终提出了新的思路，能够将其观点从 Set 纸牌迁移到整数范畴。

Katz 表示，二人发表的新论文看起来「万事俱备」，「我不相信他们之前的论断，但我相信这次的结果。」

Fox 认为，Bloom 和 Sisask 的工作是「一项伟大的成就」。他和其他数学家急切地想要探索能否将这篇新论文中的技术应用到其他问题中。「我认为，这个方法将会产生巨大影响，」Fox 说道。

当然，这项工作距离完整地证明埃尔德什等差数列猜想还很远。Bloom 和 Sisask 只证明了等差三元组的部分，还没有证明更长的数列。

即使二人已经解决掉了等差三元组问题，很多数学家仍将埃尔德什等差数列猜想看作「红鲱鱼」（即为分散注意力而提出的不相干事实或论点）。证明埃尔德什稠密性能够确保等差三元组的存在很难，数学家怀疑使这一保障失效的稠密性或许更低，可能只比 Behrend 构建的避免等差数列的数集稠密性稍高一点。

「我们并未完全解决该猜想，我们只是对此多了一点深刻认识。」Bloom 说道。

Fox 表示，Bloom 和 Sisask 或许已经竭尽所能地推进当前的方法。「我们需要真正的新工具，能够更好地挖掘出新东西。」Fox 说道。但是他还表示：「现在或许并不是故事的结局。」