您现在的位置: 首页 > 网站导航收录 > 百科知识百科知识
(质数数列)-既是质数又是合数的数
数列,等差数列,稠密(质数数列)-既是质数又是合数的数
发布时间：2020-12-06加入收藏来源：互联网点击：
质数数列（既是质数又是合数的数）: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 的发现可以为证明埃尔德什等差数列猜想提供突破口，尤其是与其他近期进展结合之后。