姚班陈立杰苦思7年计算几何难题被ChatGPT推翻

ASI启示录 2026-06-29 13:01 北京

在上个月 OpenAI 官宣解决的 Erdős 猜想的基础上完成

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。他是这个领域最受瞩目的青年学者之一。

2018年，他读博的第一篇论文就在这个卡点上取得了关键进展，把维度下界推到了2^{Θ(log* n)。}

https://arxiv.org/pdf/1802.02325

log* 是个什么概念？一个增长极其缓慢的函数。拿宇宙中原子总数那么大的数去算 log*，结果也才5左右。他已经把下界逼到了一个几乎不增长的门槛前，再往下推，就撞上了一堵硬墙。此后7年，他断断续续地琢磨，始终没能跨过去。

转机出现在上个月。他在OpenAI参与了对Erdős单位距离猜想的反证。而这篇新论文的作者们随后发现，那项工作中的代数数论技术，恰恰是跨过最后一步所需要的钥匙。

猜想科普

这个重大猜想具体是什么意思？我们不妨用个比喻。想象一下，一个体育馆里坐了一万人，要找出坐得最远的两个人。

如果体育馆是个平面，用两个坐标就能描述每个人的位置，那么算法可以很聪明地快速搞定。但如果每个人的「位置」需要用100个、1000个数来描述呢？这就进入了高维空间。

目前最好的算法，运行时间大致是 n^{2-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单位距离猜想的反证。Erdős在1946年提出这个猜想时，碰到的瓶颈几乎一模一样，都是质数不够稠密。OpenAI的证明用代数数论绕过了那面墙，而这篇论文的作者们在GPT-5.5 Pro的帮助下发现，同一套工具可以直接搬过来。

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

质数裂开之后，还需要三步完成归约：第一步，在数域的整数环中编码向量，让正交和非正交的向量对映射到不同的代数值；第二步，嵌入复数域，利用数域的代数性质保证不同的值在映射后仍然可区分；第三步，取实部虚部做四舍五入，映射回普通整数，同时控制舍入误差。整个归约的计算开销被压缩到 e^{O(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

你是一名 AI 行业编辑，请围绕下面这条热点输出一份资讯解读：
热点：姚班陈立杰苦思7年计算几何难题被ChatGPT推翻要求：
1. 先用一句话解释这条热点在讲什么
2. 再总结它为什么重要
3. 说明会影响哪些 AI 产品或内容方向
4. 最后给出 3 个适合资讯站使用的标题