一个新证明的关于长串 0 和 1 的定理解开了加法和代数结构之间的联系。
塞缪尔·贝拉斯科/广达杂志
介绍
在随机选择的一组数字中，加法可能会变得疯狂。
将这样一组中的每一对加在一起，您最终会得到一个新列表，该列表的数字可能比您开始时的数字多得多。从 10 个随机数开始，这个新列表（称为求和集）将包含大约 50 个元素。从 100 开始，总和可能约为 5,000； 1,000 个随机初始数字将使总和达到 500,000 个数字的长度。
但是，如果您的初始集合具有结构，则总和最终的数字可能会比这个少。考虑另一个 10 个数字的集合：从 2 到 20 的所有偶数。因为不同的对将加起来为相同的数字 – 10 + 12 与 8 + 14 和 6 + 16 相同 – 总和只有 19 个数字，而不是50. 随着集合变大，这种差异变得越来越深刻。包含 1,000 个数字的结构化列表可能有一个仅包含 2,000 个数字的总和。
20 世纪 60 年代，一位名叫格雷戈里·弗雷曼 ( Gregory Freiman)的数学家开始研究具有小和集的集合，试图探索加法与集合结构之间的联系——这是定义加性组合数学领域的关键联系。弗雷曼取得了令人印象深刻的进展，证明了一个具有小总和的集合必须包含在一个较大的集合中，该集合的元素以高度规则的模式间隔。但随后该领域陷入停滞。 “弗雷曼最初的证明非常难以理解，以至于没有人真正绝对确定它是正确的。因此，它并没有真正产生应有的影响。”法兰西学院和剑桥大学的数学家、菲尔兹奖得主蒂莫西·高尔斯(Timothy Gowers)说。 “但随后鲁兹萨伊姆雷突然出现了。”
在 20 世纪 90 年代的一系列两篇论文中，Ruzsa 用一个优雅的新论证重新证明了弗雷曼定理。几年后，于 2019 年去世的颇具影响力的匈牙利数学家卡塔琳·马顿 (Katalin Marton)调整了一个小求和集对原始集合结构意味着什么的问题。她替换了集合中出现的元素类型以及数学家应该寻找的结构类型，认为这将使数学家能够提取更多信息。马顿猜想与证明系统、编码理论和密码学有关，并且在加性组合学中占有崇高的地位。
卡塔琳·马顿（Katalin Marton）在一张未注明日期的照片中提出了一个关于求和集结构的猜想，该猜想与证明系统、编码理论和密码学有关。
牛津大学数学家本·格林说，她的猜想“感觉确实是我们不理解的最基本的事情之一”。它“只是支撑了我关心的很多事情。”
格林与高尔斯、加州大学圣地亚哥分校的弗雷迪·曼纳斯以及加州大学洛杉矶分校的菲尔兹奖获得者陶伦斯联手，组建了以色列数学家兼博主吉尔·卡莱所说的“ A队”。数学家。他们在11 月 9 日分享的一篇论文中证明了该猜想的一个版本。
莱斯大学的数学家奈茨·卡茨（Nets Katz）没有参与这项工作，他将这个证明描述为“非常简单”——而且“或多或少完全出乎意料”。
随后，Tao 开始尝试用Lean形式化证明，Lean 是一种帮助数学家验证定理的编程语言。短短几周内，这一努力就取得了成功。 12 月 5 日星期二一早， Tao 宣布Lean 已经证明了这个猜想，没有任何“抱歉”——这是计算机无法验证某个步骤时出现的标准声明。这是自 2021 年以来此类验证工具最引人注目的使用，标志着数学家以计算机可以理解的方式编写证明方式的拐点。高尔斯说，如果这些工具变得足够容易让数学家使用，它们也许能够取代通常漫长而繁重的同行评审过程。
证明的成分已经酝酿了几十年。高尔斯在 2000 年代初期构想了它的第一步。但卡莱用了 20 年的时间才证明了这个领域的“圣杯”。
集团内
要理解马顿猜想，需要熟悉群的概念，群是由集合和运算组成的数学对象。想想整数——无限的数字集合——以及加法运算。每次将两个整数相加，都会得到另一个整数。加法还遵循群运算的其他一些规则，例如结合性，它允许您更改运算顺序：3 + (5 + 2) = (3 + 5) + 2。
在一个组中，有时您可以找到满足所有组属性的较小集合。例如，如果将任意两个偶数相加，您将得到另一个偶数。偶数本身就是一个群，使它们成为整数的子群。相比之下，奇数不是子群。如果将两个奇数相加，就会得到一个偶数——不在原始集合中。但只需将每个偶数加 1 即可得到所有奇数。像这样的移位子群称为陪集。它不具有子群的所有属性，但它在很多方面保留了子群的结构。例如，就像偶数一样，奇数也都是均匀分布的。
几十年前，蒂莫西·高尔斯 (Timothy Gowers) 就提出了如何证明马顿猜想的想法；它们成为新证明的核心。
帕特里克·安伯特/法兰西学院
介绍
Marton 假设，如果有一个集合，我们称之为A ，由群元素组成，其总和并不比A本身大很多，那么就存在一些具有特殊属性的子群（称为G ）。移动G几次以生成陪集，这些陪集一起包含原始集合A 。此外，她认为陪集的数量增长不会比总和的大小快得多——她认为它应该与多项式因子相关，而不是更快的指数增长。
这听起来像是一种高度技术性的好奇心。但因为它涉及一个简单的测试 – 当您在集合中仅添加两个元素时会发生什么？ ——对于一个子群的总体结构来说，这对于数学家和计算机科学家来说非常重要。当计算机科学家尝试对消息进行加密以便一次只能解码消息的一部分时，就会出现相同的总体想法。它还出现在概率可检查的证明中，计算机科学家可以通过仅检查一些孤立的信息来验证这种证明形式。在每种情况下，您只需处理结构中的几个点 – 仅解码长消息中的几个位，或验证复杂证明的一小部分 – 并得出有关更大、更高级别结构的结论。
“你可以假装一切都是一个群体的一个大子集，”汤姆·桑德斯（Tom Sanders）说，他是高尔斯的前学生，现在是格林在牛津大学的同事，或者你也可以，“从许多附加巧合的存在中得到你想要的一切。这两种观点都很有用。”
Ruzsa于1999年发表了Marton的猜想，给予了她充分的信任。 “她独立于我和弗雷曼，甚至可能比我们更早地得出了这个猜想，”他说。 “这就是为什么，当我和她交谈时，我决定称其为她的猜想。”尽管如此，数学家现在将其称为多项式弗雷曼-鲁萨猜想（PFR）。
零和一
像许多数学对象一样，群有多种不同的形式。马顿认为她的猜想对于所有群体都是正确的。这还有待证明。新论文证明了一种特定类型的群，该群将二进制数列表作为其元素，如 (0, 1, 1, 1, 0)。由于计算机以二进制方式工作，因此该组在计算机科学中至关重要。但它在加法组合学中也很有用。 “这就像一个玩具环境，你可以在其中玩耍和尝试一些东西，”桑德斯说。他补充说，“代数比处理整数要好得多”。
Terence Tai 领导了一项协作工作，使用精益证明助手将证明形式化。只花了三个星期。
里德·哈钦森
介绍
这些列表具有固定长度，每个位可以是 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的元素是随机选择的，则大多数和彼此不同。如果A中有k 个元素，则意味着总和中将有大约k 2 /2 个元素。当k很大时（例如 1,000）， k 2 /2 比k大很多。但如果A是子群，则A + A的每个元素都在A中，这意味着A + A 的大小与A本身的大小相同。
PFR 考虑的集合不是随机的，但也不是子组。在这些集合中， A + A中的元素数量有点小 – 例如 10 k或 100 k 。 “当你的结构概念比精确的代数结构更加丰富时，它真的很有用，”加州大学圣地亚哥分校的计算机科学家Shachar Lovett说。
陶说，数学家知道的所有遵守该性质的集合“都非常接近实际的子群”。 “这就是直觉，周围没有任何其他类型的假团体。”弗雷曼在他的原始著作中证明了这一说法的一个版本。 1999年，Ruzsa将Freiman定理从整数扩展到二进制列表的设置。他证明了当A + A中的元素数量是A大小的常数倍时， A包含在子群中。
但鲁兹萨定理要求子群必须是巨大的。 Marton 的见解是假设A不是包含在一个巨大的子群中，而是可以包含在不大于原始集合A的子群的多项式陪集中。
“当我看到一个真实的想法时，我就知道一个真实的想法”
世纪之交左右，高尔斯在研究有关包含均匀间隔数字串的集合的不同问题时，偶然发现了鲁兹萨对弗雷曼定理的证明。 “我需要这样的东西，从某个集合的松散信息中获取结构信息，”高尔斯说。 “我很幸运，不久前，Ruzsa 制作了这个绝对华丽的证明。”
弗雷迪·曼纳斯 (Freddie Manners) 和他的合作者几个月前就已经有了证明的轮廓，但不得不努力完成它。 “你想公布这个伟大的结果并告诉全世界，但实际上你仍然需要写你的中期选举，”他说。
高尔斯开始研究该猜想的多项式版本的潜在证明。他的想法是从总和相对较小的集合A开始，然后逐渐将A变成一个子群。如果他能够证明所得子群与原始集合A相似，他就可以轻松断定该猜想是正确的。高尔斯与同事分享了他的想法，但没有人能够将它们转化为完整的证明。尽管高尔斯的策略在某些情况下是成功的，但在其他情况下，这些操纵使A远离了多项式 Freiman-Ruzsa 猜想的预期结论。
最终，这个领域继续前进。 2012年，桑德斯几乎证明了PFR 。但他需要的移位子群的数量高于多项式水平，尽管只是一点点。 “一旦他这样做了，就意味着这件事不再那么紧迫了，但仍然是一个非常好的问题，我非常喜欢，”高尔斯说。
但高尔斯的想法仍然存在于他同事的记忆和硬盘中。 “这是一个真正的想法，”格林说，他也是高尔斯的学生。 “当我看到一个真正的想法时，我就知道一个真正的想法。”今年夏天，格林、曼纳斯和陶终于将高尔斯的思想从炼狱中解放出来。
Green、Tao 和 Manners 深入合作了 37 页，然后才考虑回到高尔斯 20 年前的想法。在 6 月 23 日的一篇论文中，他们成功地使用了概率论中称为随机变量的概念来探测具有小和集的集合的结构。通过进行这种切换，团队可以更巧妙地操纵他们的场景。 “处理随机变量在某种程度上比处理集合要简单得多，”曼纳斯说。有了随机变量，“我可以稍微调整其中一个概率，这可能会给我一个更好的随机变量。”
利用这种概率视角，格林、曼纳斯和陶可以从处理集合中的元素数量转向测量随机变量（称为熵的量）中包含的信息。熵对于加法组合学来说并不新鲜。事实上，陶在 2000 年代末就曾试图普及这一概念。但还没有人尝试将它用于多项式 Freiman-Ruzsa 猜想。格林、曼纳斯和道发现它的威力强大。但他们仍然无法证明这个猜想。
本·格林说，马顿的猜想“感觉确实是我们不理解的最基本的事情之一”。
当小组仔细研究他们的新成果时，他们意识到他们终于建立了一个环境，让高尔斯休眠的想法可以蓬勃发展。如果他们使用熵而不是元素数量来测量集合的大小，那么技术细节可能会更好。 “在某个时候，我们意识到 Tim 20 年前的这些旧想法实际上比我们正在尝试的想法更可行，”Tao 说。 “所以我们把蒂姆带回了这个项目。然后所有的部分都完美地组合在一起。”
尽管如此，在证明之前还有许多细节需要弄清楚。 “我们四个人都忙于其他事情，这有点愚蠢，”曼纳斯说。 “你想公布这个伟大的结果并告诉全世界，但实际上你仍然需要写你的中期选举。”最终，该小组坚持了下来，并于 11 月 9 日发表了论文。他们证明，如果A + A不大于A大小的k倍，则A可以被不大于A的子群的不超过k 12 次移位所覆盖。这可能是一个巨大的转变。但它是一个多项式，因此当k变大时，它不会像k在指数中那样呈指数增长。
几天后，陶开始将证明形式化。他协作运行了形式化项目，使用版本控制包 GitHub 来协调来自世界各地 25 名志愿者的贡献。他们使用巴黎萨克雷大学数学家帕特里克·马索开发的名为“蓝图”的工具来组织将陶所谓的“数学英语”翻译成计算机代码的工作。除其他外，蓝图还可以创建一个图表来描述证明中涉及的各种逻辑步骤。一旦所有的气泡都被陶所说的“可爱的绿色阴影”覆盖，团队就完成了。他们在论文中发现了一些非常小的拼写错误——在一条在线消息中，陶指出，“该项目中数学上最有趣的部分相对容易形式化，但技术上的‘明显’步骤花费了最长的时间。”
马顿在她著名的猜想被证明前几年去世，但这个证明与她一生在熵和信息论方面的工作相呼应。 “当你在这个熵框架中做这件事时，一切都会比在我试图做的框架中做得更好，”高尔斯说。 “对我来说，这似乎仍然有些神奇。”
广达正在进行一系列调查，以更好地服务我们的受众。参加我们的数学读者调查，您将有机会赢得免费的Quanta商品。