陶哲轩高徒撬动数十年难题,华人研究生联手MIT解谜等差数列!

之槐看科技 2024-08-08 06:29:24

编辑:编辑部

【新智元导读】组合数学领域的一个难题,完全无序的数学不可能性,被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/

0 阅读:0

之槐看科技

简介:感谢大家的关注