新智元報道

【新智元導讀】GPT-5.5 Pro 生成了一個數學證明，解決了計算幾何中一個 陳立杰苦思 7 年未解的核心難題。關鍵技術來自 OpenAI 上月的另一項突破，而最初推進這個問題的陳立杰發現，鑰匙竟是自己參與的工作。

6 月 24 日，arXiv 上出現了一篇論文：UCSD 三位研究者 Barna Saha、Yinzhan Xu 和 Christopher Ye 證明，「最遠點對」等經典計算幾何問題，在任意超常數維度下需要近平方時間。

https://arxiv.org/pdf/2606.25887

論文聲明，初始證明由 GPT-5.5 Pro 生成。

給 AI 的 Prompt 只有兩句話，大意就是「試試用這個證明思路去改進那個已知結果」，附上兩篇論文鏈接。

這個問題 7 年前由陳立杰首次推進到接近極限，而補上最后一塊拼圖的關鍵技術，恰好來自他自己上個月在 OpenAI 參與的另一項工作。

陳立杰在 X 上驚呼，「This is incredible!!!」

陳立杰想了 7 年的問題

陳立杰是算法圈頂級天才，IOI 金牌得主，本科畢業于清華姚班，博士前往 MIT 師從理論計算機科學家 Ryan Williams，畢業后入職加州伯克利擔任助理教授，現任職 OpenAI，是理論計算機科學領域最受關注的青年學者之一。

拓展閱讀：姚班陳立杰入職OpenAI！破解50年世界難題的30歲天才，要顛覆ChatGPT

2018 年，他讀博的第一篇論文就在這個問題上取得了關鍵進展，把維度下界推到了 2Θ(log* n)。

https://arxiv.org/pdf/1802.02325

log* 是一個增長極其緩慢的函數，拿宇宙中原子總數那樣大的數去算 log*，結果也才 5 左右。

他已經把下界逼到了一個幾乎不增長的門檻前，再往下推就撞到了硬墻。

此后 7 年，斷斷續續地想，始終沒能跨過去。

上個月，他在 OpenAI 參與了對 Erd?s 單位距離猜想的反證。

這篇新論文的作者們隨后發現，那項工作中的代數數論技術，恰恰是跨過最后一步所需要的。

猜想科普

這個重大猜想具體是什么意思呢？

想象一個體育館里坐了一萬人，要找出坐得最遠的兩個。

如果體育館是個平面，用兩個坐標描述每個人的位置，有很聰明的算法可以快速搞定。

但如果每個人的「位置」需要用 100 個、1000 個數來描述呢？這就進入了高維空間。

目前最好的算法運行時間大致是 n2-c/d，n 是點的數量，d 是維度，c 是常數。

維度低時指數明顯小于 2，有捷徑可走；維度一高，指數逼近 2，退化成把每兩個人都比一遍的暴力方法。

這篇論文回答的核心問題是，算法不夠聰明，還是問題天生就這么難？

答案是后者。

只要維度在增長，哪怕增長得慢到 log log log log n（一個對天文數字來說也才等于 2 的速度），就不可能存在真正快于 n2 的算法。現有算法的表現已經基本是極限。

同一結論還覆蓋了一整個問題家族，雙色最近點對、最大內積搜索、Hopcroft 問題，全部適用。

補充一個前提——結論的成立依賴 SETH（強指數時間假設），它說的是 SAT 問題（判斷一個布爾公式能否被滿足）不存在比暴力搜索快很多的算法。

這個假設被廣泛認為成立，理論計算機科學中大量下界結論都建立在它之上。

卡點：質數太稀疏了

之前所有攻克方法共享一個核心思路。

把長向量切成 L 個小塊，每塊 b 位。

對每個小塊用不同的質數取余數，中國剩余定理保證，如果一個數對足夠多個不同的質數取余都得零，那這個數本身就是零。

所以只要用 b 個不同的質數分別檢驗每一位，就能判斷兩個向量的內積是否為零。

問題出在「足夠多」三個字上。

b 個不同的質數，最小也得排到第 b 個質數，大約是 b log b。

這些質數的乘積隨 b 指數級增長，編碼出來的數字大到離譜。

當維度很低、每塊位數 b 很大時，編碼的計算開銷比原問題還重，整個方法就失效了。

陳立杰 2020 年用遞歸技巧把這個矛盾壓到了極限。

再往下，「質數密度不夠大」這堵墻翻不過去。

破局：在另一個數學世界里讓質數「裂開」

轉機來自一個看起來完全不相關的方向。

大家都學過復數，在實數基礎上引入 i（滿足 i2 = -1），得到一個新的數系，加減乘除規則不變，但多了一個維度，可以做更多事情。

數學家發現同樣的操作可以推廣。

往有理數（就是所有分數）里加入某個特定的根，就能造出一個新的數系，叫做「數域」。

比如加入 √2，得到所有形如 a + b√2 的數（a、b 是有理數）。

這個新數系和普通數一樣可以正常做加減乘除，也有自己版本的「整數」（叫整數環），也有自己版本的「質數」（叫素理想）。

關鍵在這里。

在普通整數世界里，7 是質數，不可拆分。

但在包含 √2 的數域里，7 可以寫成 (3+√2)(3?√2)。

一個原本不可分割的質數，裂成了兩個因子，每個因子在新數系里各自充當「質數」的角色。

這就像換了一套貨幣體系。

原來一張 100 元面額的鈔票沒法找零，換了個國家的貨幣后，同樣價值可以用很多張小面額硬幣來湊。

質數不夠用的問題，突然有解了。

論文用了一種更精密的構造（CM 域），讓少量大小約 √L 的質數（L 是向量的塊數），每個都裂成 Θ(b) 個素理想（b 是每塊的位數）。

原來需要 b 個大質數，現在只要常數個中等大小的質數，裂開后就夠用。

這個技巧來自 OpenAI 今年對 Erd?s 單位距離猜想的反證。

拓展閱讀：OpenAI徹底震撼數學界，80年核心猜想被破解！菲爾茲獎得主驚呼坐不穩

https://openai.com/zh-Hans-CN/index/model-disproves-discrete-geometry-conjecture/

Erd?s 1946 年提出這個猜想時碰到的瓶頸幾乎一模一樣，都是質數不夠稠密。

OpenAI 的證明用代數數論繞過了那面墻，而這篇論文的作者們在 GPT-5.5 Pro 的幫助下發現，同一套工具直接搬得過來。

質數裂開之后，還需要三步完成歸約。

第一步，在數域的整數環中編碼向量，讓正交和非正交的向量對映射到不同的代數值。

第二步，嵌入復數域，利用數域的代數性質保證不同的值在映射后仍然可區分。

第三步，取實部虛部做四舍五入，映射回普通整數，同時控制舍入誤差。

整個歸約的計算開銷被壓縮到 eO(b√L log L)，對任意超常數維度都足夠小。

歸約成立。

AI 是怎么找到這個證明的

論文第 6 頁完整引用了給 ChatGPT 5.5 Pro 的原始 Prompt，兩個鏈接加一句話：

「Try to use this proof idea [鏈接 1] to improve the 2^{O(log* n)} bound in [鏈接 2].」

GPT-5.5 Pro 第一次沒解決。

經過多輪來回，包括要求模型繼續嘗試、根據 AI 生成的反饋修復手稿，才產出了可用的證明。

后續階段動用了 Codex 迭代手稿，Claude Opus 和 Gemini 參與審閱。

驗證環節同樣依賴 AI。

作者用 Aristotle（亞里士多德，一個 AI 定理證明器）在 Lean 4 中對關鍵引理進行了形式化驗證，而這個形式化又依賴 Aleph Prover 此前對 OpenAI 單位距離證明的形式化工作。

論文對 AI 角色的定位很坦誠。

作者寫道，初始 Prompt 基本上是他們唯一有數學實質的輸入。

同時明確聲明，已完整驗證和編輯了證明，對正確性負全部責任。

人類提出方向性洞察（「用 A 的方法去攻克 B」），AI 完成繁重的技術推導，形式化工具負責驗證。

這套分工，正在成為數學研究中一種可復制的協作模式。

作者簡介

這篇論文是由一位印度學者和兩位華人學者共同完成的。

Barna Saha

她是一位印度裔美國理論計算機科學家，研究興趣包括概率方法的算法應用、概率數據庫、細粒度復雜度以及大數據分析。

她目前是加州大學圣地亞哥分校（UCSD）計算機科學與工程系 Harry E. Gruber 冠名教授，同時在 Hal?c?o?lu 數據科學研究所兼任教職。

她曾獲得 2019 年總統青年科學家和工程師獎（PECASE）以及斯隆研究獎。

Yinzhan Xu（徐寅展）

他目前是 UCSD 計算機科學系的博士后研究員，合作導師是 Barna Saha。

此前他在 MIT 完成博士學位，導師是 Virginia Vassilevska Williams，本科也畢業于 MIT，獲得計算機科學和數學雙學位。

他的研究興趣集中在理論計算機科學，尤其是細粒度復雜度和算法設計。

他在 IOI 2014（國際信息學奧林匹克競賽）中代表中國隊參賽，獲得金牌榜并列第一名。

Christopher Ye

他是 UCSD 計算機科學理論組的四年級博士生，導師是 Barna Saha 和 Russell Impagliazzo。

研究興趣包括算法設計、細粒度復雜度、計算復雜度以及學習理論。

在讀博之前，他曾在摩根士丹利固定收益部門擔任量化分析師一年。

他于 2021 年在普林斯頓大學獲得數學本科學位。

當 AI 開始給數學「牽紅線」

這篇論文的意義超出了單個定理。

單位距離問題屬于組合幾何，最遠點對的下界屬于計算復雜性理論。

兩個領域的研究者平時很少互相引用。

AI 識別出它們共享同一個技術瓶頸（質數密度），然后把一邊的突破搬到了另一邊。

新的下界還會往下游傳導。

論文指出，最大內積搜索的復雜性約束直接影響幾何圖線性代數、動態神經元觸發檢測、以及 Transformer 注意力計算的理論天花板。

一個純數學定理，給工程優化畫了邊界。

數學史上很多重要進展來自跨領域的意外連接。

傅里葉分析從熱傳導走向信號處理，黎曼幾何從純數學走向廣義相對論。

這些連接過去依賴個別天才的直覺和廣泛閱讀。

AI 正在開始系統性地扮演這個連接者角色。

證明這件事本身，比 AI 證明單個定理更重要。

參考資料：

https://arxiv.org/pdf/2606.25887

編輯：馬可