10 月 7 日早上,我看到这张 X 截图时,先被 @mgostIH 的语气逗笑了:整数乘法已经低于 n log n,怎么连 FFT 也来了?截图里,他引用了 OpenAI 发布数学研究成果的帖子,又接连贴出两项论文摘要。页面显示的发帖时间是 10 月 7 日 6:51。

中文译图:X 帖文提及整数乘法和傅里叶变换低于 n log n 的数学结果
读者提供的 X 截图中文译图,帖文及论文预览为摘要摘译;点击图片查看未经改动的原图。原帖链接未能独立确认,下文链接至原始论文。

我顺着截图查了 OpenAI 的发布说明和论文仓库。两项结果确实列在目录里,但“低于 n log n”不能直接翻译成“你的电脑马上算得更快”。有趣的地方,恰恰在它们各自突破了什么、又没有突破什么。

整数乘法:小到荒诞的指数,也是严格大于零的指数

OpenAI 的整数乘法论文声称:在一台固定、有限字母表、有限条一维磁带的图灵机上,两个 n 位整数可以在确定性的最坏情况时间 O(n(log n)^(1−κ)) 内精确相乘,其中 κ = 2^−182。按论文的表述,这否定了 Schönhage–Strassen 在普通多磁带位模型中关于 n log n 最优性的猜想。

2^−182 小得像个玩笑。对现实中能造出的输入规模,它不会成为你升级计算库的理由。但在渐近复杂度里,“再小也是正数”很要紧:它说的不是把常数调低一点,而是把对数的指数从 1 压到了 1 以下。我觉得这才是截图值得停下来看的地方——一种看似稳固的边界,被论文提出了严格越过它的路径。

FFT:同样写着“低于”,却不是同一本账

另一篇离散傅里叶变换论文提出,在每个长度 n 上,用 O(n(log n)^(1−δ)) 次运算完成变换,δ = 10^−13。这里的运算模型允许精确复数、无限制系数和给定的单位根,并按规定方式计入标量准备与索引成本。论文自己把这与整数乘法的位复杂度模型分开;它没有给出日常浮点 FFT 的数值稳定性或有限精度提速结论。

所以,把这两篇放在一张截图里很有冲击力,却不能把它们当成同一种硬件性能承诺。一个针对精确整数乘法的位模型,另一个针对精确复数运算的算术模型。标题可以一起惊叹,评估却必须分开。

我最想看到的是“审得动”的数学

OpenAI 这次公开的仓库列出 372 组结果、722 份手稿,并明确说它们处在不同的验证阶段,并非每篇都有 Lean 形式化。整数乘法这一项在目录中没有附上 Lean 链接。FFT 相关条目虽然有 Lean 说明,但说明写得很清楚:形式化覆盖的是某些趋于无穷的长度序列上的电路节省,不是“每个长度”版本的完整验证。这不是抹掉论文,而是把证据放回它实际覆盖的位置。

我的判断是:如果这些论证经得起独立复核,这是一场关于计算边界的漂亮进展;如果其中有问题,公开手稿、修订记录和可检查的部分证明,也让错误更容易被具体指出。与其急着说“AI 已经让乘法和 FFT 变快”,我更愿意说:AI 正在把数学界带到一个新局面——提出结果的速度变快了,解释、核验和纠错的能力也得跟上。

资料:OpenAI 发布说明 · 论文仓库说明 · 整数乘法论文 · FFT 论文 · Lean 覆盖范围。