OpenAI 数学仓库中号称更快的傅里叶变换算法解析

嗨，argmin 的读者们！今天的文章探讨 OpenAI 数学代码库中声称能更快计算傅里叶变换的部分。这比平时更偏技术性，但我尝试为需要复习信号处理或计算复杂度的人添加了一些教程材料。

快速傅里叶变换是数字信号处理中最重要的创新之一，也是我最喜欢的算法之一。FFT 是一种快速提取信号频率内容的方法，让你能够快速分析、过滤和操作频谱中不同频段的频率。

傅里叶变换通过简单的点积计算每个频段的能量。1 设 x 表示你的输入，一个长度为 n 的样本数组，f 为一个频率。那么 x 在 f 处的频率内容量可以通过以下公式计算：

对于数字信号，一点数学推导表明你只需要计算 n 个这样的点积，即在频率 2𝜋/n 的每个倍数处各一个，就能理解所有的频率内容。朴素地看，每个频率需要 n 次乘法和加法。因此，计算整个傅里叶变换似乎需要 n² 次算术运算。

快速傅里叶变换是 James Cooley 和 John Tukey 在 1965 年设计的一种巧妙的递归过程。2 主要思想是，长度为 n 的傅里叶变换可以通过打乱输入向量、对打乱后的分量计算两个长度为 n/2 的傅里叶变换，然后使用原子算术运算重新组合输出来计算。打乱和重新组合需要线性数量的算术运算。迭代地重复这个过程，即 log₂(n) 次，就能计算出完整的离散傅里叶变换。加上簿记工作，FFT 在少于 5 n log2 n 次算术运算内计算出长度为 n 的傅里叶变换。

为了使这种加速更具体，当 n 为 1,000 时，n^2 为 1,000,000，而 5 * n log n 约为 50,000，加速了 20 倍。当 n 为 1,000,000 时，加速了 10,000 倍。这些加速可能决定了在信号处理应用的约束下，变换是否可计算。

自 FFT 发明以来，人们一直在寻找更快的傅里叶变换。一个问题是你到底能有多快。看起来你至少需要 n 次操作来计算 FFT，因为仅仅写下来就需要 n 步。FFT 比这个合理的速度极限慢 5*log₂(n) 倍，而这个 5*log₂(n) 因子可能很大。当 n 为一万亿时，它是 200。你能做些什么巧妙的事情来减少这个 200 的预因子吗？

好吧，你瞧，在 OpenAI 上周向数学界发布的大量论文中，他们声称拥有更快的傅里叶变换。他们那个名字颇具辨识度的“main.pdf”的主要声明是

我对这里发生的事情很感兴趣。理论上，log(n) 项比标准 FFT 中的要小那么一丁点。

我读过这篇论文吗？当然没有。OpenAI 也没人读过这篇论文，那我为什么要读？我做了世界上所有其他数学家面对 AI 垃圾数学时会做的事：我把它喂回垃圾机器，用聊天机器人界面进行了一次信息检索会话，以提取关键事实。用拟人的话说：我问 ChatGPT 它对自己的输出有什么看法。我们现在就是这样进行数学研究的。真是个世界。

不幸的是，我并没有找到更快的傅里叶变换。相反，我发现当形式主义与现实脱节到如此程度，以至于一个“突破”不过是数学家无法用自然语言正确指定其游戏规则的产物时，应用数学理论内部滋生的腐朽。

首先，“大O”记号被滥用得如此严重，以至于它已经变得毫无意义。让我们回顾一下定义，这个定义在我本科时给我留下了深刻印象。如果存在一个整数 N 和一个常数 C，使得算法运行时间 T(n) = O(F(n))，那么

也就是说，只要 n 足够大，算法实际执行的步数就被某个方便函数 F(n) 的常数倍所上界。F(n) 通常是熟悉且可解释的东西，比如多项式或指数函数。这个记号表示我们只关心计算规模很大时会发生什么。我们关心计算时间的渐近增长率。所有常数都是等价的。

大O记号在算法核算中作为捷径很有用，但它也允许了惊人的逻辑懒惰。如果我们想要一个实际更快的 FFT，我们想要一个对于合理大小的 n 需要少于 50n 次操作的算法。但 O(n) 并不意味着 50n。它可能意味着 10⁸⁰ n。这会被认为是“线性时间”算法。一个需要 n + 10⁸⁰ 的算法在大O体系中也被认为是线性时间算法。一个仅在 n 大于 10⁸⁰ 时才具有线性时间保证的算法也被认为是线性时间。10⁸⁰ 大约等于已知宇宙中的原子数量。这就是为什么 Richard Lipton 和 Ken Regan 将隐藏常数大得无法想象的算法称为银河算法。

OpenAI 的 FFT 算法绝对是银河级的。当 N=10¹² 时，C 的估计值为 10¹⁰⁰。所以即使当 n=10¹⁰⁰ 时，古老的 Cooley-Tukey-Gauss FFT 也会快 10⁹⁹ 倍。

那么为什么这个新的 FFT 结果有趣呢？嗯，请注意，在大O记号中，它在技术上渐近地比 Cooley-Tukey 算法更快，因为

我的意思是，当然。但考虑到常数，该算法只有在 n 大得不可能时才运行得更快。粗略地说，你需要

不管那个数字到底是什么意思。

Lipton 和 Regan 认为银河算法之所以有用，是因为它们能推动研究。一旦你证明了某个运行时间在渐近意义上是可能的，你就可以花时间去寻找一个能在实践中达到这个可证明运行时间的算法。也许你可以派你的 AI 智能体集群去追它。随你便。也许你能搞出一个实用的算法，但我不知道有任何正当的例子表明这发生过。我对此尤其怀疑，因为 OpenAI 使用的“计算”模型与真实的计算机毫无相似之处。

“该模型使用精确的复数运算。”这意味着它假设你可以以任意精度存储和相乘复数。事实上，该算法要求你相乘那些模随 n 呈超多项式增长的复数。如果你把这些数存为比特，内存需求实际上会随输入长度呈指数增长。它假设你可以在一次操作中相乘任意大的这种复数。我们没有能做到这一点的计算机。所以即使 main.pdf 中的这个定理是“真的”（没人知道，我也不在乎），它实际上并没有解决我们在寻找更快的 FFT 时所想要解决的问题。

对于熟悉 FFT 理论分析的人来说，你需要一个荒谬的计算模型才能打破 FFT 的速度极限，这并不令人意外。1973 年，Jacques Morgenstern 证明了，如果你要求计算中使用的复数系数具有有界模，那么你无法获得比 ½ n log n 更快的傅里叶变换。这本来应该就是故事的结局了！但事实并非如此。人们说 Morgenstern 的限制系数模型过于严格。四十年后，Nir Ailon 表明，如果没有严重的数值不稳定性，你无法以快于 n log n 的速度计算 FFT。我猜这对某些人来说也过于严格了。

因此，这个新的 OpenAI 结果与其说是数学突破，不如说是计算机科学家不擅长形式化其设计规范的一个怪例。计算机的“理论”定义与我们实际建造的计算机相去甚远。这个“更快”的傅里叶变换只是一个例子，说明理论如此脱离最初的问题，以至于一个“开放问题”变成了不过是学术地位谜题。其解决方案就像你把计算机器人流设定在不可能的问题上，然后发现它们从事非法黑客活动时会发生的事情一样。

这个 OpenAI 垃圾库中的许多其他“重大”结果也可以用同样的方式批评。例如，其中一个结果是一种银河算法，能在 O(n^2.25) 次操作内相乘两个矩阵。论文中使用的构造甚至不允许你估计隐藏在大 O 中的常数。3它可能也是无限的，只能随着天球的圣乐来计算。

尽管如此，如果写得 substantially 更好，这些论文本可以进入计算机科学理论领域最负盛名的发表场所（即 STOC 或 FOCS 的同行评审会议论文集）。4那篇矩阵乘法论文很可能会获奖。但这两者都与计算机毫无关系！

这是因为计算机科学理论有一种文化，主动抑制在计算机上运行算法。在理论会议上发表论文，断言某个算法存在却从未将其写下来，是可以接受的。计算机科学理论已经变成了一种不关心计算机的数学形式，对于这些数学追求之外的影响力，它几乎不提供任何回报。我把这一点解释给一位朋友，他对我说，“理论”有一个跨学科的含义，即“躲藏在自己制造的默默无闻之中”。

AI 非常擅长自动化我们最糟糕的倾向。它放大了那些没人喜欢、但任何个人都无法合理偏离的未言明的文化惯例。它利用了那些顽固抵制集体行动的机械化传统。在这种意义上，AI 现在可以写无用的理论论文了。但也许，在 OpenAI 那令人反感的证明垃圾场之荒谬中，我们都能抬起头来，共同意识到我们应该考虑做点别的事情。

现在的孩子们称之为余弦相似度。

维基百科页面说它应该归功于 1805 年的高斯！适当的功劳归属是学术界一个长期存在的问题。

那个结果表明，对于每个大于 0 的 epsilon，存在一个常数 C，使得 T(n) <= n^(2.25 +epsilon + C/log(n))。无论我尝试哪些查询，我都无法让 OpenAI 模型给出 C 的定量估计。随便吧！

另一个糟糕的传统是计算机科学将其最负盛名的场所选为仓促评审的会议论文集。