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

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

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

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

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

拉姆齊數(shù)

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

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

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

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

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

但求解這個(gè)數(shù)值遠(yuǎn)比想象中艱難。

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

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

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

怎么做到的？

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

作者介紹

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

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

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

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

One More Thing

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

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

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

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