智能AI
evening
刚刚,姚班传奇陈立杰苦思7年的计算几何核心难题,被ChatGPT推翻了
2026-06-29
1 阅读
约10分钟阅读
新智元
字号:
新智元报道 【新智元导读】 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 个数来描述呢?这就进入了高维空间。 目前最好的算法运行时间大致是 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 单位距离猜想的反证。 拓展阅读: OpenAI彻底震撼数学界,80年核心猜想被破解!菲尔兹奖得主惊呼坐不稳 https://openai.com/zh-Hans-CN/index/model-disproves-discrete-geometry-conjecture/ Erdős 1946 年提出这个猜想时碰到的瓶颈几乎一模一样,都是质数不够稠密。 OpenAI 的证明用代数数论绕过了那面墙,而这篇论文的作者们在 GPT-5.5 Pro 的帮助下发现,同一套工具直接搬得过来。 质数裂开之后,还需要三步完成归约。 第一步,在数域的整数环中编码向量,让正交和非正交的向量对映射到不同的代数值。 第二步,嵌入复数域,利用数域的代数性质保证不同的值在映射后仍然可区分。 第三步,取实部虚部做四舍五入,映射回普通整数,同时控制舍入误差。 整个归约的计算开销被压缩到 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 定理证
这篇文章对您有帮助吗?
订阅66必读
每日精选科技资讯,直达你的邮箱