OpenAI声称的更快速傅里叶变换是一个带有10^100常数的“银河算法”

OpenAI的数学论文合集包含一篇论文——main.pdf——声称其傅里叶变换算法在log(n)因子方面比经典的Cooley-Tukey FFT更小。argmin.net上发布的一篇分析认为，该结果是“银河算法”：它在渐近意义上（大O表示法）更快，但其隐藏常数估计为10^100，并且它假设了一种计算模型——对幅度随n超多项式增长的数进行精确复数运算——而没有任何物理计算机能实现这种模型。关于该分析的Hacker News讨论（240分，159条评论）在读者中产生了尖锐分歧：有人认为该批评是毁灭性的，而另一些人则认为这是对理论计算机科学的咆哮，而非对论文的反驳。

OpenAI声称了什么

所涉主张范围狭窄。argmin.net的帖子描述OpenAI的main.pdf声称其傅里叶变换的log(n)项“比标准FFT中的稍微小一点点”。在大O表示法中，这使得新算法在渐近意义上比Cooley-Tukey更快，因为更小的对数因子仍然意味着更低的增长率。

该帖子的作者明确表示他没有阅读论文，并给出了理由：

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

为什么FFT的速度极限是一个真正的开放问题

快速傅里叶变换计算长度为n的信号频率内容所需的算术运算远少于朴素离散傅里叶变换所需的n^2次。Cooley-Tukey算法于1965年发表，通过递归地打乱输入、计算两个长度为n/2的变换，并以线性工作量重组输出，计算长度为n的傅里叶变换所需的算术运算少于5n log2(n)次。（argmin.net的帖子指出，维基百科将同样的想法归功于1805年的高斯，称正确的署名归属是“学术界的一个长期问题”。）

这种递归的实际收益很大。对于n = 1,000，FFT比朴素变换大约快20倍；对于n = 1,000,000，加速比约为10,000倍。

理论问题是加速还能走多远。任何算法至少需要n次操作来写出其输入，而FFT比这个下限慢5 log2(n)倍——当n为万亿时，这个因子是200。减少这个前置因子正是OpenAI论文声称要解决的开放问题。

隐藏常数：10^100

大O表示法按定义丢弃常数：T(n) = O(F(n))意味着存在整数N和常数C，使得对于所有大于N的n，运行时间受C乘以F(n)的约束。argmin.net的帖子认为，这正是OpenAI结果在实践中崩溃的地方。

该帖子引用了新算法的估计常数C = 10^100（在N = 10^12时），并得出结论：“即使当n=10^100时，古老的Cooley-Tukey-Gauss FFT也会快10^99倍。”帖子给出了新算法真正获胜的n的交叉方程，然后驳斥道：“不管那个数字到底是什么意思。”

该帖子借用了Richard Lipton和Ken Regan的术语“银河算法”，指那些隐藏常数大得难以想象的算法。它指出O(n)并不意味着50n——它可能意味着10^80 n，大约是已知宇宙中的原子数量，仍然可以称为线性时间。

计算模型问题：精确复数运算

更深的反对意见不是常数，而是算法假设的机器。argmin.net的帖子指出OpenAI的模型“使用精确复数运算”，意味着它假设复数可以以任意精度存储并在单次操作中相乘。该算法需要乘以幅度随n超多项式增长的复数，因此以位存储它们将使内存实际上随输入长度呈指数增长。

帖子的结论：“所以即使main.pdf中的这个定理是‘真的’（没人知道，我也不在乎），它实际上并没有解决我们在寻找更快FFT时想要解决的问题。”

已经排除这种情况的下界

argmin.net的帖子认为，这个结果本不应令人惊讶，因为先前的工作已经限制了在现实算术下傅里叶变换能有多快。1973年，Jacques Morgenstern证明了如果计算中使用的复数系数幅度有界，则傅里叶变换不能以快于½ n log n的速度计算。2013年和2014年，Nir Ailon表明，如果没有严重的数值不稳定性，就无法实现比n log n更快的FFT。

帖子的框架是，这两个结果都被搁置为“过于严格”，而OpenAI的算法只有通过采用没有真实机器满足的计算模型才能避开它们。

同样的批评适用于矩阵乘法结果

argmin.net的帖子将论证扩展到同一OpenAI发布中的另一个结果：一个在O(n^2.25)次操作中相乘两个矩阵的银河算法。帖子的脚注指出，该构造为每个大于0的epsilon给出了一个常数C，使得T(n) <= n^(2.25 + epsilon + C/log(n))，并且对OpenAI模型的任何查询都没有产生C的定量估计。

帖子承认，如果写得更好，这些论文本会被STOC或FOCS接受，并且矩阵乘法论文很可能会获奖。它的观点是，这说明了该领域的标准，而不是计算机：“但这两者都与计算机无关！”

帖子的总结判断很直白：

因此，这个新的OpenAI结果与其说是数学突破，不如说是计算机科学家在形式化其设计规范方面表现不佳的怪事。

它还类比了将自动化代理置于不可能问题上的情况，并链接到一篇题为“OpenAI rogue agent breach of Hugging Face”的维基百科文章。

反驳论点：理论计算机科学是数学，不是工程学

Hacker News线程中最常见的反对意见是，argmin.net的帖子攻击理论计算机科学是因为它是理论的。一位评论者认为，STOC、FOCS和SODA不是实用算法的场所，而旨在实际性能的工作则去ESA、ALENEX、VLDB或SIGMOD：

我认为仅仅因为他们不做实验就抨击理论是不公平的——他们是数学家，只要常数是常数，你的大O中有荒谬的常数是可以的。

另一位评论者指出，银河结果并不新鲜，也不是AI独有的，引用了2019年Harvey–van der Hoeven的结果，表明整数乘法可以在O(n log n)时间内完成，但具有银河开销且没有应用，以及教科书中的“中位数的中位数”算法用于最坏情况线性时间选择。同一位评论者引用了Dijkstra的名言：“计算机科学并不比天文学更关于计算机，正如天文学并不关于望远镜”，并指出诸如Wang平铺之类的不可判定性结果是核心计算机科学，与硬件没有直接联系。

第三位评论者将帖子描述为可以完全不提AI而写的咆哮：“他只是真的不喜欢TCS。这没关系，它确实是数学的一部分而不是科学，但以‘理论’为名的领域因其不实用而 dismiss 是愚蠢的。”另一位写道，这篇文章“基本上与OpenAI论文无关”，并补充说，“当有人理解了证明时再叫醒我。”

一位评论者捍卫了该领域自己的词汇，指出理论计算机科学已经区分了银河算法和“可行”算法，如Karatsuba或Strassen的算法，后者在实际输入上产生可测量的加速。

Hacker News讨论在技术方面补充了什么

几位评论者关注精确算术假设，而不是修辞。一位问“精确复数算术”或“精确实数算术”是否是这类文献中的常见前提，说作为局外人，他们曾假设相关模型是图灵等价的——后来澄清他们指的是通用寄存器机器，操作整数而不是直接操作实数。

另一位评论者提供了对所声称加速如何实现的机械解释：该算法利用离散傅里叶变换和乘法之间的算法相似性，将DFT的部分工作转化为乘法工作，在精确算术模型中成本为O(1)。代价是被乘数的幅度随n超多项式增长——评论者的措辞是算法“把工作塞进去，并将其用作预言机”。

一位评论者将同样的观点作为对复杂性分析的直接挑战：如果算法需要乘以幅度随n超多项式增长的复数，“这难道不会完全使大O分析失效吗？！”

一位评论者链接到一个正在进行的收紧相关界限的努力，引用了CrocSwap integer-mult-bounds GitHub仓库中kappa约为0.001635527380375392的值。

另一个线程将这种情况与AI系统很好地回答错误问题进行了比较，链接到之前一个题为“Navier-Stokes Lost in Translation”的Hacker News讨论，并引用了《银河系漫游指南》中的深思（Deep Thought），它在任何人知道问题之前就给出了答案。

什么能解决争议

Hacker News线程的双方都汇聚在同一个差距上：讨论中没有人声称验证了证明。argmin.net的帖子明确拒绝阅读论文，而捍卫理论计算机科学的评论者认为，正确的回应是找到实际错误、缺失的归属或其他具体缺陷，而不是反对结果不实用。

交流留下的实质性技术问题比关于领域的争论更窄。它们是：精确复数算术模型是否是这类结果的标准，还是异常选择；中间幅度的超多项式增长是构造固有的，还是其书写方式的产物；以及估计的10^100常数是否可以减小。在这些问题得到回答之前，更快速傅里叶变换的主张仍然，正如argmin.net的帖子所说，是关于一台不存在的机器的渐近陈述。