数十年来首次取得进展，陶哲轩高徒、赵宇飞高徒突破组合数学难题

机器之心编译

选自quantamagazine

机器之心编译机器之心编辑部

近期，一个数十年来未解决的数学难题首次取得了进展。

推动这项进展的是来自加州大学洛杉矶分校的研究生 James Leng 和麻省理工学院数学研究生 Ashwin Sah、哥伦比亚大学助理教授 Mehtaab Sawhney。其中James Leng 师从著名数学家陶哲轩，Ashwin Sah 师从离散数学大牛赵宇飞。

论文地址：https://arxiv.org/pdf/2402.17995

要了解这项研究取得的突破，需要从算术级数说起。

等差数列的前 n 项和称为一个等差级数，也称为算术级数。1936 年，数学家 Paul Erdős 和 Pál Turán 猜想：如果一个集合由整数的非零分数组成（即使是 0.00000001%），那么它一定包含任意长的算术级数。唯一可以避免算术级数的集合是那些包含整数「可忽略不计」部分的集合。例如，集合 {2, 4, 8, 16, …}，其中每个数字都是前一个数字的两倍，它沿着数轴分散，没有级数。

1975 年，数学家 Endre Szemerédi 证明了这个猜想。他的工作催生了数学家至今仍在探索的多种研究方向。

数学家们在有限数集（从 1 到某个数 N 之间的所有整数）的情况下建立了 Szemerédi 的结果。在不可避免地包含一个被禁止的级数之前，集合中可以使用的部分占初始池的多少？随着 N 的变化，这个占比会如何变化？

例如，令 N 为 20，那么可以写下这 20 个数字中的多少个，同时仍然避免长度为 5 个或更多数字的级数？事实证明，答案是初始池的 16% 到 80%。

Szemerédi 是第一个证明随着 N 的增长，这个占比必须缩小到零的人，后来数学家们一直试图量化该情况发生的速度。

去年，两位计算机科学家的突破性工作几乎解决了三项级数的问题，例如 {6, 11, 16}。但当你试图避免四项或更多项的算术级数时，问题就变得更加困难。这是因为较长的级数反映了经典数学方法难以揭示的潜在结构。

三项算术级数中的数字 x、y 和 z 始终满足简单方程 x – 2y + z = 0（以级数 {10, 20, 30} 为例：10 – 2*(20) + 30 = 0），证明一个集合是否包含满足这种条件的数字相对容易。而四项级数中的数字还必须满足更复杂的方程 x^2 – 3y^2 + 3z^2 – w^2 = 0，具有五项或更多项的级数必须满足更复杂的方程。这意味着包含此类级数的集合会表现出更微妙的模式。数学家也更难证明这种模式是否存在。

20 世纪 90 年代末，数学家 Timothy Gowers 提出了一种克服这一障碍的理论。后来他被授予菲尔兹奖，这是数学界的最高荣誉，部分原因是因为这项工作。2001 年，他将自己的方法应用于 Szemerédi 定理，证明了最大集合大小的更好界限，避免了任何给定长度的算术级数。

2022 年，当时正读加州大学洛杉矶分校研究生二年级的 James Leng 开始理解 Gowers 的理论。他没有考虑 Szemerédi 定理。相反，他希望回答与 Gowers 的方法相关的问题。

然而，努力探索了一年多，他一无所获。

一直在思考相关问题的 Sah 和 Sawhney 了解了 Leng 的工作，他们很感兴趣，Sawhney 甚至说道：「我很惊讶竟然可以这样思考」。

Sah 和 Sawhney 意识到 Leng 的研究可能有助于他们在 Szemerédi 定理上取得进一步进展。几个月之内，三位年轻的数学家就想出了如何在没有五项级数的情况下获得更好的集合大小上限。然后，他们将工作扩展到任意长度的级数，这标志着自 Gowers 证明以来 23 年来该问题的首次取得进展。

表示

，没有 k 项算术级数的最大子集的大小。Leng、Sah 和 Sawhney 证明，对于 k ≥ 5，存在 c_k > 0 使得

研究团队

论文一作 James Leng 是加州大学洛杉矶分校 (UCLA) 的数学研究生，本科毕业于加州大学伯克利分校。他师从著名数学家陶哲轩。

James Leng 的研究兴趣包括算术组合学、动力系统和傅里叶分析等等。他的研究还曾得到 NSF 研究生奖学金的支持。

James Leng

Ashwin Sah 从小就喜欢数学，他在竞赛中接触到了高等数学并表现优异。2016 年夏天，16 岁的 Sah 夺得国际奥林匹克数学竞赛（IMO）的金牌，次年他进入 MIT 求学。

Ashwin Sah

在 MIT 读书期间，有两个人对 Sah 的数学发展起到重要作用。第一个是离散数学大牛赵宇飞（Yufei Zhao）教授，他也是 Sah 的研究生导师。

第二个就是 Mehtaab Sawhney，他们在课堂上相遇并成为朋友。后来，二人一起做研究，共同探讨离散数学领域内的多个主题，如图论、概率论和随机矩阵的属性。2017 年底，Ashwin Sah 和 Mehtaab Sawhney 在（MIT）读本科时相识。从那时起，两人一起编写了令人难以置信的 57 个数学证明，其中许多在各个领域产生了深远的影响。

Mehtaab Sawhney

Mehtaab Sawhney 现在是哥伦比亚大学助理教授。他的研究兴趣包括组合学、概率和理论计算机科学等等。

参考链接：https://www.quantamagazine.org/grad-students-find-inevitable-patterns-in-big-sets-of-numbers-20240805/