新智元報道

【新智元導讀】近80年，沒人動過Erd?s概率方法的下界底數。清華、中科大團隊首次給出指數級改進。

2026年5月，數學四大頂刊Inventiones Mathematicae刊發了一篇來自中國團隊的論文。

作者是：清華/中科大雙聘教授馬杰，清華博士生申武杰，中科大博士生謝晟捷。

論文地址：https://link.springer.com/article/10.1007/s00222-026-01421-9

Erd?s 1947年發明的概率方法，奠定了整個概率組合學。

此后近80年，沒有任何人能從根本上突破它的極限。

而這篇論文，首次給出了指數級改進。

一枚硬幣扔了80年

Erd?s的方法非常簡單：給完全圖的每條邊擲硬幣，正面紅，反面藍。

舉個例子，任何足夠大的社交網絡里，都必然存在一群人全互相認識或全互不認識。而Erd?s用這枚硬幣證明了，「足夠大」至少是指數級的。

有意思的是，上界這些年一直有人在推進，2023年更是從≈4一口氣壓到了3.7992。但下界的底數，自Erd?s提出之后近80年都紋絲未動。

直到馬杰團隊提出了那個關于球面的想法。

但硬幣太笨了

硬幣著色的特點是每條邊紅藍各半、完全獨立。

簡潔，好分析，但它沒有利用任何幾何結構來壓制單色團的形成，浪費了信息。

申武杰的想法是給隨機性加入幾何。

他提出了「隨機球圖」模型，也就是把n個節點隨機撒在高維球面上，兩點距離遠的邊涂紅，近的涂藍。

高維球面有一個極反直覺的特性——

維度一高，幾乎所有點都擠在赤道附近。隨機選兩條徑向線，夾角幾乎一定接近90度。

點對距離集中在一個很窄的區間里，著色不再完全隨機，而是被球面的幾何對稱性精確調控。球面結構天然壓制大片單色團的形成。

但這里有一個取舍。球面模型壓低了紅色團的概率。

也就是說，要形成大的紅色團，需要很多節點彼此都很遠，球面空間有限，這很難發生。但同樣的道理，藍色團的概率反而上升了。

隨后，三人在小規模圖上做了驗證。

數以萬計的著色方案里，無團著色的概率依然大于零——收益確實蓋過了代價。

接下來就是證明這一點，而關鍵恰恰來自高維球面那些極反直覺的幾何性質。

以近對角線Ramsey數r(k, 2k)為例，兩個參數一個是另一個兩倍的情形，Erd?s硬幣給出的下界底數恰好是黃金比例(1+√5)/2≈1.618。

馬杰、申武杰、謝晟捷把這個底數提高到了(1+√5)/2 + 10?21。

你沒看錯。改進量大約是10?21——小數點后面20個零，然后一個1。

但重點在指數。

Ramsey數按指數增長，底數哪怕只加0.000000000000000000001，當k趨向無窮，新下界會把舊下界甩到宇宙盡頭。

近80年來沒有任何人動過這個底數。

而他們不只是把數字往上推了一點，他們還證明了Erd?s的硬幣并非最優著色方案。

隨機球圖在結構上嚴格優于純隨機著色，這意味著概率方法的天花板遠沒有到。

這是該方向自Erd?s以來的首次指數級改進，也是第一次有人給出一條超越硬幣的路徑。

不過這條路徑有一個明確的邊界：它只在藍色團大于紅色團時有效。

當兩種顏色的禁忌團一樣大，也就是Erd?s最初關注的對角線情形，新方法的收益會消失。

整個圈子炸了

論文2025年7月掛上arXiv，不到一周，組合數學泰斗Gil Kalai在博客發了一篇標題以Amazing開頭的長文，稱這套模型「具有相當的獨立研究價值」。

劍橋大學的Julian Sahasrabudhe更是感慨道：「一個熟悉的東西竟然能解決一個熟悉的問題，多少有點令人震驚。」在他看來，這項技術一直藏在眼皮底下。

2025年12月，馬杰在UCLA時的合作導師Benny Sudakov帶著學生證明了，換成高斯隨機圖同樣有效，球面都不需要。這步簡化意味著更多人能參與推廣。

2026年初，又有人推廣到了多色Ramsey數。

2026年5月，文章正式發表于Inventiones Mathematicae。

清華00后的直覺

馬杰，現任清華大學丘成桐數學科學中心教授、中國科學技術大學教授。

他2007年從中科大本科畢業，2011年在Georgia Tech拿到博士學位，導師是Xingxing Yu。此后在UCLA做Hedrick助理教授，師從Benny Sudakov，隨后轉到CMU做博后。2015年回國扎根中科大，2024年同時加入清華YMSC和BIMSA。

他在2017年拿到國家優青，2022年拿到國家杰青，是SIDMA編委。2020年他拿下了ICA的Hall Medal——這個獎每年最多頒兩枚，專門給40歲以下的杰出組合數學家。

謝晟捷，高中拿過數學聯賽廣東一等獎，高二就通過少創班提前進了中科大。

本科期間拿過丘賽團體銅牌，2023年留校直博，師從馬杰。成果發表時在讀博三。

申武杰，00后，目前在清華丘成桐數學科學中心讀博，導師是丘成桐。成果發表時博四。

他高中拿過CMO三等獎，2018年考入北大數院，本科期間拿了全國大學生數學競賽一等獎、阿里數賽銀獎和ICCM創意本科論文獎。2022年他直博進入清華。

讀博的前幾個學期，申武杰主要做的是幾何與拓撲，和Ramsey理論沒有任何交集。

2024年春天，他偶然讀到一篇關于Ramsey數的論文，被深深吸引，開始琢磨一個問題：有沒有一種隨機模型，能比Erd?s的硬幣更高效地生成無團著色？

2024年秋天，馬杰到清華訪問授課，申武杰把這個想法帶給了他，馬杰的學生謝晟捷也加入進來。三個人花了一年時間，寫了40頁密集的計算，才完成了證明。

馬杰后來說：「我們很幸運，感覺所有努力都得到了回報。但這一路確實艱難了很長時間。」

AI解題 vs 人造武器

就在這篇文章發表的同月，DeepMind放出了AlphaProof Nexus的完整戰報。

353個Erd?s開放問題里啃下9個。44個OEIS猜想一并證明。全部Lean形式化驗證通過。其中兩道題已經懸了56年。每道題不過幾百美元。

Gemini 3.1 Pro驅動agentic loop，反復搜索證明路徑直到形式驗證器點頭。

但歸根結底是在已知框架里做搜索。

對此，陶哲軒曾表示：AI是稱職的助手，但不是同行。它善于在已知方法里掃描匹配，但不擅長提出原創想法。

而馬杰團隊做的恰恰是后者。他們沒有去解Erd?s的某一道題，他們升級了Erd?s發明的方法本身。

AI從Erd?s的遺產里拆了9堵墻。三個中國人重鑄了他最引以為傲的那把錘子。

在最需要創造性洞察的數學前沿，人類目前仍然不可替代。至少今天是這樣。

尾聲

1947年，Erd?s掏出一枚硬幣，開辟了概率組合學。

將近80年后，一個00后中國博士生說了一句：「把節點扔到球面上試試。」

參考資料：

https://www.quantamagazine.org/after-80-years-mathematicians-give-famed-erdos-method-an-upgrade-20260626/

編輯：摩西