刚刚，姚班传奇陈立杰苦思7年的计算几何核心难题，被ChatGPT推翻了

新智元报道

【新智元导读】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 的速度），就不可能存在真正快于 n² 的算法。现有算法的表现已经基本是极限。

同一结论还覆盖了一整个问题家族，双色最近点对、最大内积搜索、Hopcroft 问题，全部适用。

补充一个前提——结论的成立依赖 SETH（强指数时间假设），它说的是 SAT 问题（判断一个布尔公式能否被满足）不存在比暴力搜索快很多的算法。

这个假设被广泛认为成立，理论计算机科学中大量下界结论都建立在它之上。

卡点：质数太稀疏了

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

把长向量切成 L 个小块，每块 b 位。

对每个小块用不同的质数取余数，中国剩余定理保证，如果一个数对足够多个不同的质数取余都得零，那这个数本身就是零。

所以只要用 b 个不同的质数分别检验每一位，就能判断两个向量的内积是否为零。

问题出在「足够多」三个字上。

b 个不同的质数，最小也得排到第 b 个质数，大约是 b log b。

这些质数的乘积随 b 指数级增长，编码出来的数字大到离谱。

当维度很低、每块位数 b 很大时，编码的计算开销比原问题还重，整个方法就失效了。

陈立杰 2020 年用递归技巧把这个矛盾压到了极限。

再往下，「质数密度不够大」这堵墙翻不过去。

破局：在另一个数学世界里让质数「裂开」

转机来自一个看起来完全不相关的方向。

大家都学过复数，在实数基础上引入 i（满足 i² = -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

编辑：马可