AI 竟提出 o(n log n) 乘法新算法
The recently proposed o(n log n) integer multiplication algorithm [pdf]
一家美国科技公司最近在 GitHub 上公开了一堆数学论文，其中一篇声称提出了复杂度为 o(n log n) 的整数乘法算法。作为该领域专家，David Harvey 认为这个结果虽然看似荒谬，但理论上是可信的。他坦言，自己花费两周仅理解了论文的一小部分，而 AI 模型 Claude Fable 5.1 却在几分钟内就完全理解了论证细节。这标志着 AI 在解决高难度数学问题上已展现出远超人类的速度与能力，人类数学家可能很快面临无法独立发表严肃研究成果的困境。
我怀疑人类作为数学研究论文作者还能被认真对待的时间已经不多了，就像我们不再接受大学生的书面作业一样。
HN 评论区
144- jdb1729
> 最好能有一个关于 o(n log n) 结果的正式化证明，比如在 Lean 中。据我所知，目前还没有这样的证明。
该结果已由 @platypii 和我在 Lean 中完全形式化（基于 Mathlib 的 TM2 机），并且指数部分正在持续优化（目前为 1-2^-14.38）：https://github.com/platypii/integer-mult-bounds-lean
欢迎贡献！
- Kapura
> 我其实还没读过那篇论文。事实上，有三篇紧密相关的论文 [TC26a]、[TC26b]、[TC26c]，我一篇都没读过。我试过，但很快就放弃了。这些数学论文的叙述方式似乎不太强。相反，我让 Fable 给我解释一下 [TC26a]。Fable 似乎理解了其中的论证，并认为它是正确的。
这种状况感觉不太健康。
- jdb1729
> 新结果并不直接意味着在固定有限域上的多项式乘法有新的复杂度界限，比如在 F2[x] 中的乘法。该问题的现有技术是一种算法，能在 O(n log n 4^log*(n)) 时间内乘积 n 次多项式 [HvdH19]。
@platypii 和我已经获得了针对素数阶有限域上 DFT 的相同改进的 Lean 证明（通过卷积定理实现多项式乘法）：https://github.com/platypii/integer-mult-bounds-lean/blob/ma...
- kenferry
> 我想强调一下这种情况的另一个方面。经过两周的艰苦努力，我仅理解了 [TC26a] 的一小部分。当我向 Fable 询问这篇论文时，它似乎能在几分钟内从头开始阅读并理解整篇内容，即使是从全新的上下文开始。我知道有些读者可能对我使用拟人化术语感到不适，但我认为“理解”一词是准确的，因为 LLM 似乎能够正确且清晰地回答关于该论文的各种问题，包括一些非常繁琐的技术细节。这正是我会用来判断人类同事是否“理解”某事的方式。人类与 LLM 之间这种“思维速度”的鸿沟，至少可以说令人不安。
这很奇怪，因为它完全不符合我对这些系统的经验。是的，它们通常听起来很自信，但对于我来说难以理解的代码（例如），通常对机器来说也难以理解。虽然它们比我更有耐力，但并不比我更聪明。
这位数学家处于评估 Fable 是否真正理解的最佳位置，但这很奇怪，也与我的经验相悖。
- flebron
请注意，在这个案例中，标题写的是“O(n log n)”，但关键部分在于这是“o(n log n)”，而不仅仅是“O(n log n)”。前者是后者的一个真子集。通过 FFT，我们已经知道如何在 O(n log n) 时间内将两个 n 位整数相乘。
- yaoke259
来自悉尼老乡的精彩文章和介绍，让我一直读下去！作为一个数学白痴，技术细节对我来说太快了，但文章的文字让我能深刻共情该领域的从业者，这非常启发人。我从未意识到这篇数学论文的影响有多大，以及它如何撼动了整个领域。我想我们都在努力弄清楚这种“按需获取的智能”到底是怎么回事。
- jonhohle
> 我想公司里的员工现在应该已经意识到，这一事件给我的专业社区带来的痛苦和深切的失落感。
我自己也在努力接受这一切。我同意这种未来是不可避免的，进步无论怎样都会到来。
我现在的感觉很像《侏罗纪公园》里的格兰特博士。
- Eji1700
我知道这完全不是重点，但这是否是一个能立即改变计算机领域的实用突破？
根据我极其有限的理解，答案是“否”，我推测如果是这样，那应该是头条新闻了。主要观点是，虽然这比之前的任何进步都要巨大，但从实际角度来看，它仍然“很小”。
这并非要贬低这篇论文所传达的极其重要的问题，我只是想确认我是否理解正确。
我确实想知道这是否会成为未来发展的一个重大问题，还是说现在那些还在穿尿布的数学专家们长大后，会在这个世界里成长，拥有工具和知识来提供帮助，而我们只是处于一个艰难的过渡期。但不幸的是，我只能贡献这么多。