数学“A-Team”证明了加法和集合之间的关键联系广达杂志

在随机选择的一组数字中，加法可能会变得疯狂。

将这样一组中的每一对加在一起，您最终会得到一个新列表，该列表的数字可能比您开始时的数字多得多。 从 10 个随机数开始，这个新列表（称为求和集）将包含大约 50 个元素。 从 100 开始，总和可能约为 5,000； 1,000 个随机初始数字将使总和达到 500,000 个数字的长度。

但是，如果您的初始集合具有结构，则总和最终的数字可能会比这个少。 考虑另一个 10 个数字的集合：从 2 到 20 的所有偶数。因为不同的对将加起来为相同的数字 - 10 + 12 与 8 + 14 和 6 + 16 相同 - 总和只有 19 个数字，而不是50. 随着集合变大，这种差异变得越来越深刻。 包含 1,000 个数字的结构化列表可能有一个仅包含 2,000 个数字的总和。

1960世纪XNUMX年代，有一位数学家，名叫 格雷戈里·弗里曼 开始研究具有小总和的集合，以探索加法和集合结构之间的联系——这是定义加法组合数学领域的关键联系。 弗雷曼取得了令人印象深刻的进展，证明了一个具有小总和的集合必须包含在一个较大的集合中，该集合的元素以高度规则的模式间隔。 但随后该领域陷入停滞。 “弗雷曼最初的证明非常难以理解，以至于没有人真正绝对确定它是正确的。 所以它并没有真正产生它可能产生的影响，”说 蒂莫西·高尔斯（Timothy Gowers），法兰西学院和剑桥大学的数学家，菲尔兹奖得主。 “但是之后 伊姆雷鲁萨 突然出现在现场。”

在一系列 二 文件 1990世纪XNUMX年代，Ruzsa用一个优雅的新论证重新证明了弗雷曼定理。 几年后， 卡塔琳·马顿于 2019 年去世的一位颇具影响力的匈牙利数学家，对小求和集对原始集合结构意味着什么的问题进行了调整。 她替换了集合中出现的元素类型以及数学家应该寻找的结构类型，认为这将使数学家能够提取更多信息。 马顿猜想与证明系统、编码理论和密码学有关，并且在加性组合学中占有崇高的地位。

她的猜想“感觉确实是我们不理解的最基本的事情之一，”说 本·格林，牛津大学数学家。 它“只是支撑了我关心的很多事情。”

格林与高尔斯联手， 弗雷迪·曼纳斯 加州大学圣地亚哥分校，以及 陶ence，加州大学洛杉矶分校菲尔兹奖获得者，以色列数学家和博主 吉·凯莱（Gil Kalai） 称为“一个团队” 数学家们。 他们在论文中证明了该猜想的一个版本 9月XNUMX日分享.

网队卡茨莱斯大学的一位数学家没有参与这项工作，他将这个证明描述为“非常简单”——而且“或多或少完全出乎意料”。

随后，Tao 开始努力将证明形式化 精益，一种帮助数学家验证定理的编程语言。 短短几周内，这一努力就取得了成功。 5月XNUMX日星期二清晨， 陶宣布 精益证明了这个猜想，没有任何“抱歉”——当计算机无法验证某个步骤时出现的标准声明。 这是此类技术最引人注目的用途 2021 年起的验证工具，并标志着数学家用计算机可以理解的术语编写证明的方式的拐点。 高尔斯说，如果这些工具变得足够容易让数学家使用，它们也许能够取代通常漫长而繁重的同行评审过程。

证明的成分已经酝酿了几十年。 高尔斯在 2000 年代初期构想了它的第一步。 但卡莱用了 20 年的时间才证明了这个领域的“圣杯”。

集团内

要理解马顿猜想，需要熟悉群的概念，群是由集合和运算组成的数学对象。 想想整数——无限的数字集合——以及加法运算。 每次将两个整数相加，都会得到另一个整数。 加法还遵循群运算的其他一些规则，例如结合性，它允许您更改运算顺序：3 + (5 + 2) = (3 + 5) + 2。

在一个组中，有时您可以找到满足所有组属性的较小集合。 例如，如果将任意两个偶数相加，您将得到另一个偶数。 偶数本身就是一个群，使它们成为整数的子群。 相比之下，奇数不是子群。 如果将两个奇数相加，就会得到一个偶数——不在原始集合中。 但只需将每个偶数加 1 即可得到所有奇数。 像这样的移位子群称为陪集。 它不具有子群的所有属性，但它在很多方面保留了子群的结构。 例如，就像偶数一样，奇数也都是均匀分布的。

马顿认为如果你有一组我们会调用 A 由组元素组成，其总和并不比 A 本身，那么存在一些子群——称之为 G - 具有特殊属性。 转移 G 几次来制作陪集，这些陪集将一起包含原始集 A。 此外，她认为陪集的数量增长不会比总和的大小快得多——她认为它应该与多项式因子相关，而不是更快的指数增长。

这听起来像是一种高度技术性的好奇心。 但因为它涉及一个简单的测试 - 当您在集合中仅添加两个元素时会发生什么？ ——对于一个子群的总体结构来说，这对于数学家和计算机科学家来说非常重要。 当计算机科学家尝试对消息进行加密以便一次只能解码消息的一部分时，就会出现相同的总体想法。 它还出现在概率可检查的证明中，计算机科学家可以通过仅检查一些孤立的信息来验证这种证明形式。 在每种情况下，您只需处理结构中的几个点 - 仅解码长消息中的几个位，或验证复杂证明的一小部分 - 并得出有关更大、更高级别结构的结论。

“你可以假装一切都是一个群体的一个大子集，”说 汤姆桑德斯，高尔斯的前学生，现在是格林在牛津大学的同事，或者你可以，“从许多附加巧合的存在中得到你想要的一切。 这两种观点都很有用。”

鲁兹萨 1999年发表马顿猜想，给予她充分的信任。 “她独立于我和弗雷曼，甚至可能比我们更早地得出了这个猜想，”他说。 “这就是为什么，当我和她交谈时，我决定称其为她的猜想。” 尽管如此，数学家现在将其称为多项式弗雷曼-鲁萨猜想（PFR）。

零和一个

像许多数学对象一样，群有多种不同的形式。 马顿认为她的猜想对于所有群体都是正确的。 这还有待证明。 新论文证明了一种特定类型的群，该群将二进制数列表作为其元素，如 (0, 1, 1, 1, 0)。 由于计算机以二进制方式工作，因此该组在计算机科学中至关重要。 但它在加法组合学中也很有用。 “这就像一个玩具环境，你可以在其中玩耍和尝试一些东西，”桑德斯说。 他补充说，“代数比处理整数要好得多”。

这些列表具有固定长度，每个位可以是 0 或 1。您可以通过将每个条目添加到另一个列表中的对应条目来将它们加在一起，规则为 1 + 1 = 0。因此 (0, 1, 1, 1 , 0) + (1, 1, 1, 1, 1) = (1, 0, 0, 0, 1)。 PFR 试图找出一个集合在不完全是一个子群但具有一些类群特征的情况下会是什么样子。

为了使 PFR 更精确，假设您有一组名为 A。 现在取出每对元素 A 并将它们相加。 所得总和构成 A，被称为 A + A。 如果元素 A 是随机选择的，那么大多数总和彼此不同。 如果有 k 元素 A，这意味着周围会有 k²总和中的 /2 个元素。 什么时候 k 很大 — 比如说 1,000 — k²/2 比 k。 但如果 A 是一个子群，其中的每个元素 A + A 在 A， 意思是 A + A 大小与 A 本身。

PFR 考虑的集合不是随机的，但也不是子组。 在这些集合中，元素的数量 A + A 有点小——比如 10k或100k。 “当你的结构概念比仅仅作为一个精确的代数结构要丰富得多时，它真的很有用，”说 沙查·洛维特，加州大学圣地亚哥分校的计算机科学家。

陶说，数学家知道的所有遵守该性质的集合“都非常接近实际的子群”。 “这就是直觉，周围没有任何其他类型的假团体。” 弗雷曼在他的原始著作中证明了这一说法的一个版本。 1999年，Ruzsa将Freiman定理从整数扩展到二进制列表的设置。 他证明了 当元素的数量 A + A 是大小的常数倍 A, A 包含在子组中。

但鲁兹萨定理要求子群必须是巨大的。 马顿的见解是假设，与其被包含在一个巨大的子群中， A 可以包含在不大于原始集合的子群的多项式陪集中 A.

“当我看到一个真实的想法时，我就知道一个真实的想法”

世纪之交左右，高尔斯在研究有关包含均匀间隔数字串的集合的不同问题时，偶然发现了鲁兹萨对弗雷曼定理的证明。 “我需要这样的东西，从某个集合的松散信息中获取结构信息，”高尔斯说。 “我很幸运，不久前，Ruzsa 制作了这个绝对华丽的证明。”

高尔斯开始研究该猜想的多项式版本的潜在证明。 他的想法是从一套开始 A 其总和较小，然后逐渐操纵 A 进入一个子组。 如果他能证明得到的子群与原始集合相似 A，他很容易断定这个猜想是正确的。 高尔斯与同事分享了他的想法，但没有人能够将它们转化为完整的证明。 尽管高尔斯的策略在某些情况下是成功的，但在其他情况下，操纵行为却受到了影响。 A 与多项式 Freiman-Ruzsa 猜想的预期结论相去甚远。

最终，这个领域继续前进。 2012年，桑德斯 几乎证明了PFR。 但他需要的移位子群的数量高于多项式水平，尽管只是一点点。 “一旦他这样做了，就意味着这件事不再那么紧迫了，但仍然是一个非常好的问题，我非常喜欢，”高尔斯说。

但高尔斯的想法仍然存在于他同事的记忆和硬盘中。 “这是一个真正的想法，”格林说，他也是高尔斯的学生。 “当我看到一个真正的想法时，我就知道一个真正的想法。” 今年夏天，格林、曼纳斯和陶终于将高尔斯的思想从炼狱中解放出来。

Green、Tao 和 Manners 深入合作了 37 页，然后才考虑回到高尔斯 20 年前的想法。 在 23 月 XNUMX 日 纸，他们成功地使用了概率论中称为随机变量的概念来探测具有小和集的集合的结构。 通过进行这种切换，团队可以更巧妙地操纵他们的场景。 “处理随机变量在某种程度上比处理集合要简单得多，”曼纳斯说。 有了随机变量，“我可以稍微调整其中一个概率，这可能会给我一个更好的随机变量。”

利用这种概率视角，格林、曼纳斯和陶可以从处理集合中的元素数量转向测量随机变量（称为熵的量）中包含的信息。 熵对于加法组合学来说并不新鲜。 事实上，陶 曾尝试过 在 2000 年代末普及这一概念。 但还没有人尝试将它用于多项式 Freiman-Ruzsa 猜想。 格林、曼纳斯和道发现它的威力强大。 但他们仍然无法证明这个猜想。

当小组仔细研究他们的新成果时，他们意识到他们终于建立了一个环境，让高尔斯休眠的想法可以蓬勃发展。 如果他们使用熵而不是元素数量来测量集合的大小，那么技术细节可能会更好。 “在某个时候，我们意识到 Tim 20 年前的这些旧想法实际上比我们正在尝试的想法更可行，”Tao 说。 “所以我们把蒂姆带回了这个项目。 然后所有的部分都完美地组合在一起。”

尽管如此，在证明之前还有许多细节需要弄清楚。 “我们四个人都忙于其他事情，这有点愚蠢，”曼纳斯说。 “你想公布这个伟大的结果并告诉全世界，但实际上你仍然需要写你的中期选举。” 最终，该小组坚持了下来，并于 9 月 XNUMX 日发表了论文。 他们证明了如果 A + A 不大于 k 大小的倍 A， 然后 A 可以覆盖不超过约 k¹² 子群的平移不大于 A。 这可能是一个巨大的转变。 但它是一个多项式，因此它的增长速度不会像 k 变得更大，就像这样 k 都在指数中。

几天后，陶 开始 将证明形式化。 他协作运行了形式化项目，使用版本控制包 GitHub 来协调来自各方的贡献。 全球25名志愿者。 他们使用了一个名为 蓝图 由开发 帕特里克·马索特巴黎萨克雷大学数学家组织努力翻译道的内容 被称为 “数学英语”转化为计算机代码。 除其他外，蓝图还可以创建 图表 描述证明中涉及的各种逻辑步骤。 一旦所有的气泡都被陶所说的“可爱的绿色阴影”覆盖，团队就完成了。 他们在网上的一篇论文中发现了一些非常小的错别字 的话陶指出，“该项目中数学上最有趣的部分相对容易形式化，但技术‘明显’步骤花费的时间最长。”

马顿在她著名的猜想被证明前几年去世，但证据与她相呼应 一生的工作 关于熵和信息论。 “当你在这个熵框架中做这件事时，一切都会比在我试图做的框架中做得更好，”高尔斯说。 “对我来说，这似乎仍然有些神奇。”

广达 正在进行一系列调查，以更好地为我们的观众服务。 就拿我们的 数学读者调查 您将有机会免费赢取 广达 货品。