审视 OpenAI 所宣称的更快傅里叶变换

各位 argmin 的读者们好！今天这篇文章会分析 OpenAI 数学代码库中宣称能更快计算快速傅里叶变换的部分。内容比平时更技术性一些，但我为需要在信号处理或计算复杂性方面补课的读者补充了一些教程内容。

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

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

对于数字信号来说，一点数学推导表明：你只需要计算这些点积中的 n 个（即在 2𝜋/n 的每个整数倍频率处各计算一次），就能得到所有频率成分。直观地看，每个频率需要 n 次乘法和加法。因此，计算整个傅里叶变换似乎需要 n² 次算术运算。

快速傅里叶变换是 James Cooley 和 John Tukey 在 1965 年提出的一种巧妙的递归过程。2 其主要思路是：将输入向量混洗（shuffle）后，对混洗后的各部分分别计算两个长度为 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 被发明以来，人们就一直在寻找更快的傅里叶变换。一个问题就是究竟能算多快。看起来计算 FFT 至少需要 n 次操作，因为光是把它写下来就要 n 步。FFT 比这一合理速度上限慢 5*log₂(n) 倍，而这个 5*log₂(n) 因子可能很大。当 n 为一万亿时，它就是 200。有没有什么巧妙的方法能把这个 200 的前置因子降低？

结果你瞧，在 OpenAI 上周向数学界倾泻的那批海量论文中，他们声称拥有一种更快的傅里叶变换。在他们那篇名字极具辨识度的 "main.pdf" 中，主要论断是

我对这里到底发生了什么很感兴趣。从理论上讲，其 log(n) 项比标准 FFT 略小一点点。

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

可惜的是，我没有找到更快的傅里叶变换。相反,l，我发现了应用数学理论内部滋生的腐烂：当形式主义与现实脱节到如此程度，以至于所谓"突破"不过是数学家们无法用自然语言正确表述他们游戏规则的产物。

首先，"大 O"符号已经被滥用到了毫无意义的地步。让我们回顾一下这个定义，它曾让我这个本科生印象深刻。一个算法的运行时间为 T(n) = O(F(n))，如果存在一个整数 N 和一个常数 C，使得

也就是说，只要 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 算法绝对是银河级别的。常数 C 的估计值为 10¹⁰⁰，而 N=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) 次运算来乘法两个矩阵的银河算法。论文中使用的构造甚至无法让你估计隐藏在 big O 中的常数。3它不妨就是无限的，只有借助天球的神圣音乐才能计算。

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

这是因为计算机科学理论领域形成了一种文化，积极劝阻人们在计算机上实际运行算法。在理论会议上发表论文，只断言某个算法存在、却从不把它写下来，也是可以接受的。计算机科学理论已经变成了一种不关心计算机本身的数学，并且对那些数学追求之外的影响几乎不予回报。我向一位朋友解释了这一点，他对我说，“theory”（理论）一词在不同学科语境中的含义是“躲在自己制造的晦涩之中”。

AI 非常擅长把我们最糟糕的倾向自动化。它放大了那些没人喜欢、但任何个人都无法合理偏离的隐性文化惯例。它利用了那些对集体行动顽固抵抗的机械化传统。顺着这条路，AI 现在能够撰写毫无用处的理论论文了。但或许正是在 OpenAI 那些令人倒胃口的证明垃圾堆的荒诞之中，我们都能抬起头来，一起意识到我们应当考虑去做点别的事情了。

如今的小孩子们管它叫余弦相似度。

维基百科页面上说，这应该归功于 1805 年的高斯！合理的署名归属在学术界一直是个长期存在的问题。

那一条证明了：对于任意大于 0 的 ε，存在常数 C 使得 T(n) <= n^(2.25 +epsilon + C/log(n))。无论我怎么提问，都没法让 OpenAI 的模型给出 C 的定量估计。算了！

另一个糟糕的传统是，计算机科学把那些评审仓促的会议论文集当作它最负盛名的发表场所。