浙大校友用AI突破32年拉姆齊數(shù)下界

聞樂 發(fā)自 凹非寺
量子位 | 公眾號 QbitAI

數(shù)學界塵封32年的拉姆齊數(shù)經(jīng)典難題被打破！

浙大校友王宜平借助自研AI框架ScaleAutoResearch-Ramsey，成功將拉姆齊數(shù)R(3,17)下界從92提升至93，終結(jié)了自1994年以來長期停滯的紀錄。

同時他還將R(4,15)下界刷新至160，成果直接超越谷歌DeepMind同期AlphaEvolve的研究水平。

而且，這次世界級數(shù)學突破并沒有依賴超級算力集群，僅用Claude Code、Codex+1臺CPU服務(wù)器就完成全部攻堅，成果已全量開源。

拉姆齊數(shù)

如果外星人威脅地球，要求我們給R (5,5) 的精確值，人類應(yīng)動用所有算力；但如果要的是R (6,6)，我們不如直接開戰(zhàn)。

數(shù)學巨匠保羅?埃爾德什的這句調(diào)侃，直接說明了拉姆齊數(shù)有多難纏。

作為組合數(shù)學的核心難題，拉姆齊數(shù)本質(zhì)上是在尋找“無序中必然出現(xiàn)秩序”的臨界值。

R (3,17) 下界用生活化的派對問題來理解就是：

無論派對上的人如何隨機社交，總能找到3個互相認識的小圈子（對應(yīng)數(shù)學中的三角形結(jié)構(gòu)），或是17個完全互不相識的人（對應(yīng)“17點獨立集”），這個最小的派對人數(shù)，就是R (3,17) 的精確值。

但求解這個數(shù)值遠比想象中艱難。

如今R (5,5) 的精確值仍卡在43-48的區(qū)間，算出R (6,6)還不如向外星人開戰(zhàn)……

而R (3,17) 自1994年被數(shù)學家Wang-Wang-Yan鎖定在92后，全球頂尖團隊輪番攻關(guān)，卻始終無法撼動這一數(shù)字，漸漸成了橫跨32年的學術(shù)僵局。

而且，它的研究成果直接關(guān)聯(lián)圖論、算法設(shè)計、網(wǎng)絡(luò)優(yōu)化等關(guān)鍵領(lǐng)域，從人工智能到通信網(wǎng)絡(luò)，都能找到它的應(yīng)用影子，是數(shù)學與計算機科學交叉領(lǐng)域的香餑餑。

怎么做到的？

王宜平的突破，始于一次“反其道而行之”的嘗試。

在此之前，傳統(tǒng)方法的思路是：

先構(gòu)造一張沒有三角形的圖，再慢慢壓縮其中的獨立集規(guī)模。

但無論算法如何優(yōu)化，在92個頂點的限制下，獨立集始終停留在18個，怎么也壓不到16個的目標。

但王宜平換了一條逆向思路：

放棄零三角形的初始要求，先構(gòu)建一張獨立集不超過16個但含少量三角形的圖，再通過AI的復合刪除修復策略，一點點刪掉三角形，同時修復過程中新生的獨立集沖突。

他融合了了karpathy autoresearch、AlphaEvolve、拉姆齊數(shù)綜述等成熟思路，搭建了一套AI自我迭代進化的研究框架，讓AI可以不斷沿用過往的優(yōu)質(zhì)探索結(jié)果，往更深、更細的方向持續(xù)深挖。

系統(tǒng)會同時啟動多組獨立智能體，用不同算法、不同初始參數(shù)并行搜索圖結(jié)構(gòu)空間，有效避免探索陷入局部無解；

全程以結(jié)構(gòu)沖突數(shù)為評判標準，把每一次優(yōu)化出的更好圖譜保存下來當作基礎(chǔ)模板，后續(xù)迭代都在已有優(yōu)質(zhì)成果上繼續(xù)打磨，靠不斷沉淀積累逼近最優(yōu)解，這也是其和谷歌AlphaEvolve最大的區(qū)別；

而且所有推演得出的結(jié)果都會通過專業(yè)核驗工具嚴格篩查，精準校驗圖中是否存在違規(guī)三角形、是否超出獨立集數(shù)量上限，每一個關(guān)鍵突破節(jié)點都有完整核驗記錄，從根源上保證研究結(jié)果嚴謹可信。

這套AI框架從最初僅含12個三角形的圖結(jié)構(gòu)出發(fā)，像闖關(guān)升級一樣逐步推進。

12個、11個、10個……每一步都要平衡“刪三角形”和“控獨立集”的矛盾，最終在92個頂點上，成功構(gòu)造出一張完美的圖——

既沒有三角形，也不存在17個互不相連的點，直接證明了R (3,17)≥93。

這套框架還順帶攻克了R (4,15) 的下界難題，將其從159提升至160。

而就在今年，谷歌DeepMind的AlphaEvolve也只做到了復刻R (3,17) 的舊下界92，沒能實現(xiàn)實質(zhì)性突破。

作者介紹

王宜平本科畢業(yè)于浙江大學竺可楨榮譽學院，獲計算機科學與數(shù)學雙學位。

現(xiàn)在是華盛頓大學保羅·G·艾倫計算機科學與工程學院博士生。

他現(xiàn)任xAI 技術(shù)團隊成員，并曾在微軟實習。長期研究目標是開發(fā)安全、可擴展的超人類AI系統(tǒng)，推動科學進步。

近期研究聚焦于大語言模型的推理強化學習以及AI for Math，同時也涉獵多模態(tài)和機器學習理論等領(lǐng)域。

One More Thing

除此之外，中科大馬杰教授、清華申武杰、中科大謝晟捷團隊在拉姆齊數(shù)研究中實現(xiàn)78年來首次指數(shù)級理論改進。

就在前幾天，相關(guān)成果發(fā)表于數(shù)學四大頂刊之一《Inventiones Mathematicae》（《數(shù)學新進展》）；

從宏觀數(shù)學規(guī)律層面，顯著拔高了拉姆齊數(shù)下界的增長階數(shù)，相當于給這類問題的求解劃定了更高的理論天花板。

參考鏈接：
[1]https://x.com/ypwang61/status/2052508685591785619
[2]https://github.com/ypwang61/ScaleAutoResearch-Ramsey