组合数学领域的一个难题，完全无序的数学不可能性，被UCLA华人研究生和两位MIT研究生取得了突破！为此，他们强化了陶哲轩的一项成果，并再进一步。这是数十年来该领域的首次进展。
刚刚，组合数学领域最大的未解之谜之一——完全无序的数学不可能性，取得了数十年来的首次进展。
突破这项成就的是，是UCLA的华人研究生James Leng，以及两位MIT研究生Ashwin Sah和Mehtaab Sawhney。
今年2月，三人宣布，他们对整数集合在必须包含间隔均匀的数字序列（如{9, 19, 29, 39, 49}或{30, 60, 90, 120}）之前能有多大的估计值，进行了长期的改进。
这个证明，即是组合数学领域最大的未解决问题之一。
论文地址：https://arxiv.org/abs/2402.17995
这一成果，也在数学圈内引起了轰动。
牛津大学数学家Ben Green表示，几位学生的成果，令人印象深刻。尤其是成果发布时，三人都还在读研究生。
算术级数问题
级数（progression）是一列展现出特定模式的数或项，即每一项都对前一项应用特定规则而得到，也可称之为序列。
数学中，级数主要有三种类型，包括算数级数、几何级数以及调和级数。
有规则间隔的数字序列，称为算术级数（arithmetic progression），我们更熟悉的说法是等差数列。
尽管模式简单，但它们背后隐藏着令人震惊的数学复杂性。
更神奇的是，无论我们怎样努力，算术级数都很难避免。
1936年，数学家Paul Erdős和Pál Turán推测，如果一个集合由整数的非零分数组成（哪怕只有0.00000001%），那么它一定包含任意长的算术级数。
唯一可以避免算术级数的集合，就是那些包含整数「可忽略不计」部分的集合。
例如，集合 {2, 4, 8, 16, …}，其中每个数字都是前一个数字的两倍，它沿着数轴分布得如此分散，以至于可以说它占据整个数字集合的0%。
因此，这个集合没有级数。
四十年后的1975年，这个猜想被一位叫Endre Szemerédi的数学家证明了。
而他的工作，催生了众多研究方向，至今仍在令数学家们探索。
Sah和Sawhney的MIT博导Yufei Zhao这样介绍道：「他证明中的许多想法，都发展成了自己的世界」。
Yufei Zhao数学家们将Szemerédi的结果应用于有限数集。在这种情况下，我们需要从一个有限的集合开始——从1到N之间的每一个整数。在不可避免地包含一个被禁止的级数之前，我们在起始集合中能使用的最大部分是多少？随着N的变化，这个部分会如何变化？比如，令N为20。我们可以写下这20个数字中的多少个，同时仍能避免长度为5个或更多数字的级数？事实证明，答案是起始集合的16%到80%。
论文地址：https://www.jstor.org/stable/2005105现在，令N为1,000,000。如果我们使用了这个池子中的80%，那么我们将看到包含800,000个数字的集合。这么大的集合，是不可能避免五项级数的。因此，我们将不得不使用池子中较小的部分。
算术级数达到4项时，就会「咬人」
Szemerédi是第一个证明「随着N的增长，这个部分必须缩小到零」的人。从那时起，数学家们就一直试图量化这种情况发生的速度。去年，两位计算机科学家的突破性工作几乎解决了三项级数的问题，例如 {6, 11, 16}。
论文地址：https://arxiv.org/abs/2302.05537可是，每当我们试图避免使用四项或更多项的算术级数时，问题就会变得更加棘手。用Sawhney的话来说就是，「我喜欢这个问题的一点就是，它看起来很单纯，但事实并非如此。这个问题会咬人。」这是因为，较长的级数反映了经典数学技巧难以发现的潜在结构。三项算术级数中的数字x、y和z，总是满足简单方程x-2y+z=0（以级数 {10、20、30} 为例：10 – 2(20) + 30 = 0）。要证明一个集合中是否包含满足这种条件的数，是比较容易的。但是，四项级数中的数字还必须满足更复杂的方程x^2 – 3y^2 + 3z^2 – w^2 = 0。这就意味着，包含这些级数的集合会呈现出更微妙的模式。想要证明这种规律是否存在，对数学家们来说，也就更难了。终于，在1990年代，法兰西学院数学家Timothy Gowers提出了一种理论，克服了这种障碍。这项工作发表后，直接促成了他拿到菲尔兹奖——数学界的最高荣誉。2001年，他将自己的成果应用于Szemerédi定理，证明了最大集合大小的更好界限，避免了任何给定长度的算术级数。在接下来的二十年里，虽然数学家们使用了Gowers的框架解决了其他问题，但他在2001年的纪录，仍旧保持着稳定。
华人研究生，打破研究阻碍
2022年，当时正在UCLA读研究生二年级的Leng，开始研究Gowers的理论。他脑子里并没有装着Szemerédi定理，相反，他希望自己能解决一个由Gowers发展出的技巧相关的问题。其他数学家并不看好，担心他解决问题所需要耗费的精力太大了，与之相比可能得到的结果根本不值一提，于是纷纷劝阻他。Leng后来评价道：「他们是有道理的。」整整一年多的时间，他都一无所获。但是某一天开始，他忽然做出了某些东西。而一直在研究相关问题的Sah和Sawhney看到他的工作后，表示了巨大的兴趣。用Sawhney的话说，「我很惊讶，居然还可以这样思考。」他们意识到，Leng的研究可能帮助他们在Szemerédi定理上取得进展。几个月后，他们做到了！这三位年轻的数学家想到了一个办法，在没有五项技术的情况下，获得了更好的集合大小上限。（也就是我们开头看到的那篇论文）然后，他们将工作扩展到了任意长度的级数，这标志着Gowers证明以来的23年里，这个问题首次取得了进展。Gowers已经证明，当起始数字池变大时，我们可以做出的避免进展的集合，会以某种速度变得相对较小。而现在， Leng、Sah和Sawhney证明，这种情况发生的速度要快得多。而导师Zhao对学生们的工作赞不绝口：「这是一项巨大的成就。但我不会建议任何学生攻克这种问题，因为它真的太难了。」许多数学家都对三人获得新界限方法感到非常兴奋。为了顺利解决问题，他们必须先强化一项先前的、技术性更强的成果。这项成果来自牛津大学的Ben Green、陶哲轩和希伯来大学的Tamar Ziegler。数学家们认为，这一结果（Gowers理论的某种阐述）可以进一步改进。Green介绍说：「我的感觉是，我们对这个理论的理解也并不完善，我们只是看到了它的一些影子。」自从2月份发表这篇论文后，Sawhney已经完成了他的博士学位。现在，他是哥大的一名助理教授。Sah仍然在MIT攻读研究生。
Sah在MIT校园中两人仍在继续合作。导师Zhao评论道：「他们令人难以置信的优势就在于，能够接受技术要求极高的东西，并且去理解它、改进它。他们的整体成就难以言喻。」
论文概述
在这项工作中，研究者令r_k(N)表示 [N]= {1，…，N} 中最大且不存在k项等差数列的子集的大小。他们证明了，对于k≥5，存在c_k> 0，使得。这个证明是基于Gowers U^k-范数逆定理的准多项式界值，以及由Heath-Brown和Szemerédi提出的密度增量策略，后者由陶哲轩和Green重新做了表述。设「N」= {1，…，N}，r_k(N) 表示在S没有k项算术级数的情况下，中最大的S。r_3（N）的第一个非平凡上界，来自Roth的研究，他证明了。后来的一系列研究中，数学家们又将证明突破到了。对于更高的k，Erdős和Turán的一个长期猜想认为r_k(N) = o(N)。在开创性的工作中，Szemerédi首先建立了r_4(N) = o(N) 的估计，然后建立了以他命名的定理r_k(N) = o(N)。由于使用了van der Waerden定理和规则性引理，Szemerédi的成果密度增量极小。而在随后的突破性工作中，Gowers引入了高阶傅里叶分析，并为Szemerédi定理证明了第一个「可行」的上界：。对于k≥4的唯一显著改进，来自Green和陶哲轩的工作，他们最终证明了。最近，研究者们的工作又证明了。而三位作者此次的主要结果，是将这一上界扩展到了所有k≥5。即定理1.1——随后，他们证明了：对于给定「N」中的无序序列表，可以将「N」分解为一个受控的算术级数集合，从而使这些序列上的无序序列基本保持恒定。在这个过程中，他们采用了以下几项引理。在第三节中，他们利用了Green和陶哲轩提出的Heath-Brown和Szemerédi密度增量策略。最终，成功完成了证明。
MIT本科生，推动图论研究前沿
其实，早在Sah和Sawhney在MIT读本科时，两人就做出了令人印象深刻的工作。两人相识后，一起发表了57个令人难以置信的数学证明，许多都在各个领域取得了深远进展。在2020年5月，Sah在组合学最重要的问题中，就发表了有史以来最好的结果，而这只是他本科期间发表的一长串数学结果其中的一部分。
论文地址：https://arxiv.org/abs/2005.09251在这篇论文中，Sah重点研究了组合学的一个重要特征——拉姆齐数，它量化了图（由边连接的点或顶点的集合）在必然包含某种子结构之前可以达到多大。随着我们要寻找的派系规模越来越大的，计算精确的拉姆齐数变得非常困难。在20世纪30年代，Paul Erdős和George Szekeres发起了拉姆齐数上限和下限的研究。而Sah的证明，改进了双色拉姆齐数的上限。他证明：一旦图达到一定大小，就必然会包含某个相应大小的派系。这就将现有的研究路线推向了逻辑极限，可以说是为该问题设定了目前的最佳上限。领域内的许多人认为，Sah的证明是利用现有研究路线可以实现的最佳结果。加州理工学院的David Conlon这样评价：「作为一个本科生，他的成果已经足够让他获得教职了」。
作者介绍
James Leng本科毕业于加州大学伯克利分校，目前是UCLA数学系的在读研究生，与陶哲轩共同合作。他的研究领域包括算术组合数学、动力系统和傅里叶分析，主要关注高阶傅里叶分析。Ashwin Sah从2020年起成为MIT的数学系研究生，由Yufei Zhao指导，研究兴趣包括组合数学、概率论和数论。Mehtaab Sawhney目前是哥伦比亚大学助理教授，同时担任Clay数学研究所的研究员，他的研究同样关注组合数学、概率论和理论计算机科学。在俄勒冈州波特兰长大的Sah，16岁时获得奥数金牌，17岁就读于MIT，两年半后毕业。在MIT的第一年，他上了Yufei Zhao教授的两门课，其中一门是关于组合学的研究生水平讨论课。在全世界最有才华的数学学生中，Sah仍然能脱颖而出。
11岁的Sah最早的记忆之一，就是和妈妈一起学算术在课堂上，Sah认识了高一级的学生，从宾大转学到MIT的Sawhney。两人结识后，研究了离散数学中的一系列主题，例如图论、概率和随机矩阵的性质。Sawhney表示，「我喜欢那些可以从基本原理出发思考的问题，不需要阅读大量文献或了解大量理论就可以开始思考」。导师Zhao对两人的速度印象深刻。他会要求两人研究一个特定的问题，觉得接下来他们有的忙了。然而，经常是第二天，他们就带着答案回来。Zhao的评价是，「他们都是精力非常充沛的人。我每提出一个问题，都会立刻收到回复。」本科的三年里，Sah和Sawhney撰写了数十篇论文，并且获得了2021年的摩根奖。Zhao表示，二人的成就没有先例。「本科生研究有着悠久的传统，但在数量和质量上都无法达到他们俩的水平」。参考资料：https://www.quantamagazine.org/grad-students-find-inevitable-patterns-in-big-sets-of-numbers-20240805/
