陶哲軒趙宇飛學(xué)生聯(lián)手攻下組合數(shù)學(xué)難題，23年來首次突破

魚羊 2024-08-07 12:31:05 來源：量子位

克雷西 魚羊 發(fā)自 凹非寺

量子位 | 公眾號(hào) QbitAI

陶哲軒和趙宇飛的學(xué)生聯(lián)手，給數(shù)學(xué)界整了個(gè)新驚喜：

讓組合數(shù)學(xué)領(lǐng)域最大難題之一——從無序中證明有序，取得了23年來的重大突破。

這個(gè)問題有多難？

用知名華裔數(shù)學(xué)家、MIT副教授趙宇飛本人的話說，是“我不會(huì)建議任何學(xué)生去做這個(gè)課題”。

有意思的是，這甚至還是個(gè)“意外”收獲：

陶哲軒弟子、剛上研究生二年級(jí)的James Leng（以下簡(jiǎn)稱小冷）原本試圖延續(xù)另一位菲爾茲獎(jiǎng)得主——蒂莫西·高爾斯的理論研究。

但搞了一年多，他幾乎是“一無所獲”。

就在一籌莫展之時(shí)，他遇上了趙宇飛的兩位天才學(xué)生——本科期間就聯(lián)手發(fā)了十幾篇論文的Ashwin Sah（以下簡(jiǎn)稱小薩）和Mehtaab Sawhney（以下簡(jiǎn)稱索哥）。

三人一碰頭，頓時(shí)靈光乍現(xiàn)：小冷這研究思路用到塞邁雷迪定理上，那說不定真能整出點(diǎn)新進(jìn)展。

幾個(gè)月后，都還在攻讀博士學(xué)位的三個(gè)年輕人真的做到了——

23年首次突破組合數(shù)學(xué)難題

小冷、小薩和索哥的這項(xiàng)研究，是組合數(shù)學(xué)領(lǐng)域的一大難題，是對(duì)塞邁雷迪定理的進(jìn)一步研究。

塞邁雷迪定理由2012年阿貝爾獎(jiǎng)得主、匈牙利數(shù)學(xué)家塞邁雷迪·安德烈（Szemerédi Endre，注：匈牙利人的習(xí)慣是姓前名后）于1975年證明，其中說到：

若一個(gè)整數(shù)集A具有正的自然密度，則對(duì)任意的正整數(shù)k，都可以在A中找出一個(gè)包含k項(xiàng)的等差數(shù)列。

所謂具有正自然密度，就是當(dāng)n趨于無窮時(shí)，A與1,2,…,n這個(gè)數(shù)列的交集中元素個(gè)數(shù)與n的比值大于0。

比較著名的反例就是2,4,8…這樣的等比數(shù)列，它們被認(rèn)為在數(shù)軸上“過于稀疏”，不具備正自然數(shù)密度。

這個(gè)理論的猜想由兩名匈牙利數(shù)學(xué)家埃爾德什·帕爾（Erd?s Pál）和圖蘭·帕爾（Turán Pál）在1936年提出。

顯然對(duì)于k=1和2的情況，這個(gè)結(jié)論毫無疑問是成立的，k=3的情況則在1953年由英國數(shù)學(xué)家克勞斯·羅特證明。

到了1969年，塞邁雷迪用組合數(shù)學(xué)方法證明了k=4的情況，直到最終證明該結(jié)論對(duì)任意k均成立。

后來，又有數(shù)學(xué)家利用遍歷理論、傅里葉分析等其他方法證明了這一結(jié)論。

這也讓陶哲軒為之感慨，還把該定理的眾多證明稱為“羅塞塔石碑”，因?yàn)樗鼈冞B結(jié)了幾個(gè)乍看起來完全不同的數(shù)學(xué)分支。

但總之，塞邁雷迪定理的證明并不是一個(gè)終點(diǎn)，而且還開啟了新的討論。

塞邁雷迪定理還有另一種表述形式——

若在正整數(shù)1-N中取一個(gè)子集，使得對(duì)于某一k值，在該子集中找不到長(zhǎng)度為k的等差數(shù)列；

則當(dāng)N趨近于無窮時(shí)，該子集的大小r_k(N)與N的比值趨近于0。

不過這個(gè)比值趨近于0的速度究竟是怎樣的，仍然是一個(gè)未知數(shù)，也就成了后續(xù)這幾十年的研究課題。

前面提到，有人用傅里葉分析方法給出了塞邁雷迪定理的新證明，這個(gè)人就是1998年菲爾茲獎(jiǎng)得主、英國數(shù)學(xué)家蒂莫西·高爾斯（Timothy Gowers）。

更重要的是，高爾斯同時(shí)給出了r_k(N)與N比值的上界，即該比值下降的速度不會(huì)慢于某個(gè)特定的函數(shù)。

這個(gè)函數(shù)長(zhǎng)這樣：

此后的20多年來，不斷有人針對(duì)具體k值，對(duì)r(N)的范圍給出了更精確的上界。

比如在2017年，陶哲軒和英國數(shù)學(xué)家本·格林（Ben Green）一起給出了k=4時(shí)的新上界。

然而，對(duì)k取任意值的情況一直未有新的進(jìn)展，直到這次研究的出現(xiàn)。

2022年，正在加州大學(xué)洛杉磯分校（UCLA）讀研二的小冷開始研究起了高爾斯的理論。

不過他腦海里的是高爾斯提出的幾個(gè)技術(shù)問題，并沒有想到塞邁雷迪定理。

一年很快過去，小冷沒有得到任何成果，但他的研究引起了小薩和索哥的注意。

他們意識(shí)到，小冷的研究可能有助于在塞邁雷迪定理上取得進(jìn)一步進(jìn)展。

于是三位年輕的數(shù)學(xué)家走到了一起，并在幾個(gè)月之內(nèi)就想出了k=5時(shí)更精確的上界。

直到今年，三人又把這一結(jié)論推廣到了k為任意取值的情況，成為了23年以來在這個(gè)問題上最重大的突破。

證明的核心在于應(yīng)用了高爾斯U^(k+1)范數(shù)的逆定理，這是一個(gè)與傅里葉分析相關(guān)的高級(jí)工具，它提供了一種衡量函數(shù)在某種意義上接近于零的方法。

該逆定理也是由三人發(fā)現(xiàn)的，用了足足100頁的論文進(jìn)行闡述。

其中指出，如果一個(gè)函數(shù)在范數(shù)意義上足夠大，那么它必然與某些具有特定結(jié)構(gòu)的序列相關(guān)聯(lián)，這些序列在數(shù)學(xué)上被稱為“結(jié)構(gòu)性對(duì)象”。

利用這個(gè)逆定理，作者們將問題從原始的整數(shù)集合，轉(zhuǎn)移到了具有特定代數(shù)結(jié)構(gòu)的nilmanifolds流形上。

通過深入分析這些流形上的nil序列，作者們實(shí)現(xiàn)了對(duì)這些序列在整數(shù)集合上變化的控制。

然后，他們通過對(duì)集合進(jìn)行分解并運(yùn)用密度增量策略，逐步增加不包含k項(xiàng)等差數(shù)列的子集密度，直到達(dá)到某一閾值或無法繼續(xù)增加。

經(jīng)過迭代這個(gè)過程，作者們證明了存在一個(gè)足夠大的子集，其密度遠(yuǎn)高于之前的結(jié)果，實(shí)現(xiàn)了k=5時(shí)結(jié)論向著更高k值的推廣。

陶哲軒趙宇飛的天才學(xué)生們

三位作者中，小冷（James Leng）目前就讀于加州大學(xué)洛杉磯分校（UCLA），師從菲爾茲獎(jiǎng)得主陶哲軒。

他的主要研究方向是算術(shù)組合學(xué)、動(dòng)力系統(tǒng)和傅里葉分析。

而小薩（Ashwin Sah）和索哥（Mehtaab Sawhney）都是MIT副教授趙宇飛的學(xué)生。

小薩其人，不可謂不是一位“天才少年”。

他是2016年國際奧林匹克數(shù)學(xué)競(jìng)賽（IMO）金牌得主，2018年還獲得過首屆阿里巴巴全球數(shù)學(xué)競(jìng)賽銀獎(jiǎng)。

剛上大一，小薩就跑去聽了趙宇飛研究生級(jí)別的組合數(shù)學(xué)課。這迅速引起了趙宇飛的注意：

盡管他只是大一的學(xué)生，但很顯然，他已經(jīng)掌握了這門課程。

就在本科期間，小薩已經(jīng)有20多篇數(shù)學(xué)論文在手——并且他只用了兩年半時(shí)間就從MIT本科畢業(yè)了。

其中，還包括在拉姆齊數(shù)方面的重大突破：給出了拉姆齊數(shù)的新上限，被認(rèn)為是“使用現(xiàn)有研究線索可以獲得的最佳結(jié)果”。

索哥（Mehtaab Sawhney）比小薩高一年級(jí)，他同樣在本科期間就參與了趙宇飛的組合數(shù)學(xué)課程。

打從本科起，索哥和小薩就是彼此的科研搭子，關(guān)系密切到索哥主頁列出的70篇論文里，有60篇都帶小薩的名字。

而導(dǎo)師趙宇飛在本科時(shí)對(duì)他倆的評(píng)價(jià)就是：

（MIT）的本科生研究有著悠久的歷史和傳統(tǒng)，但在論文的質(zhì)量和數(shù)量上，都達(dá)不到Ashwin Sah和Mehtaab Sawhney的水平。

目前，索哥已經(jīng)率先博士畢業(yè)，獲得了哥倫比亞大學(xué)的教職，還在今年年初被任命為克萊研究員。

△小薩索哥和趙宇飛合影，圖源：MIT

兩位老友的合作仍在繼續(xù)，這也令外界感到期待。他們的導(dǎo)師趙宇飛是這樣說的：

他們的非凡之處在于總能理解極具技術(shù)挑戰(zhàn)的事物并加以改進(jìn)。

很難用語言概括他們的整體成就。

參考鏈接：
[1]https://arxiv.org/abs/2402.17995
[2]https://www.quantamagazine.org/grad-students-find-inevitable-patterns-in-big-sets-of-numbers-20240805/
[3]https://en.wikipedia.org/wiki/Szemer%C3%A9di%27s_theorem

— 完 —