这是 OpenAI 722 篇数学手稿系列的第三篇，也是收官篇。第二篇讲了整数乘法在多带图灵机上打破 \(n\log n\)（FFT 家族复杂度叙事的根基被撼动），本篇讲 FFT 本体：精确离散傅里叶变换（DFT）在无界系数模型里对所有长度低于 \(n\log n\)。

一句话版本：FFT 是整个信息科学里最重要的算法之一，六十年来 \(O(n\log n)\) 被当成它的”身份复杂度”。这篇论文给出一个确定性算法，对每一个变换长度 \(n\) 把成本压到 \(O(n(\log n)^{1-\delta})\)（显式 \(\delta=10^{-13}\) 量级）。墙，又被凿掉了一角。

官方报告翻译（核心部分）

以下内容译自 OpenAI 发布的论文《An explicit power saving for the exact discrete Fourier transform》（2026 年 9 月 25 日），包含标题、摘要、主定理与引言的核心段落。

标题：精确离散傅里叶变换的一个显式幂节省

摘要：我们给出一个确定性算法，在每个正变换长度 \(n\) 上以 \(O(n(\log n)^{1-\delta})\) 次运算计算长度为 \(n\) 的 DFT，\(\delta=10^{-13}\)。该模型使用精确复数算术、无限制的系数，并提供一个单位根；成本计价包含标量准备与对数字长的索引工作。

算术模型（1.1 节，节译）：我们的模型具有复数寄存器与整数地址寄存器。一次复数域操作——加、减、乘以一个预先确定的、与输入无关的标量——记单位成本。除法仅用于标量准备，并附有分母非零的证明。对 \(O(\log(n+2))\) 位字上的整数操作与随机访问同样记单位成本。我们提供一个显式指定的、依赖于 \(n\) 的 Fourier 根；等价地，对某个给定的阶 \(d\)，一次单位根操作返回指定的 \(\zeta_d\)，记单位成本。本定理只需要一个具有多项式阶的这样的根。对有理常数的域操作不假设能生成任意大阶的根。对复系数或中间数值的模长没有限制，也没有有限精度或数值稳定性断言。

主定理 1.1：存在单一确定性算法，对每个正整数 \(n\) 与每个 \(x\in\mathbb{C}^n\)，精确计算 \(F_nx\)。在上述模型中——包含标量准备、调度构造与索引工作——运行时间为

\[ O\!\left(n(\log n)^{\theta}(\log\log n)^{4-\theta}\right)\qquad(n\to\infty), \]

\[ \theta=\log_m\lambda\approx 0.99999999999978935615699598<1. \]

只需对显式可计算的整数 \(D^*<1024\,n^3\) 供给指定的根 \(\zeta_{D^*}\)。

推论 1.2：同一模型下，变换在每个长度都可在

\[ O\!\left(n(\log n)^{1-10^{-13}}\right)=o(n\log n) \]

时间内计算。

（从定理 1.1 到推论 1.2 的换算：\(\theta\) 距 1 的差是 \(2.1\times10^{-13}\)，把 \((\log\log n)\) 的固定幂吸收进 \((\log n)\) 的微小指数节省即可。）

推论 1.3（精确卷积与多项式乘法）：同一模型下，对每个 \(n\) 与 \(a,b\in\mathbb{C}^n\)，可以计算线性卷积 \(c_k=\sum_{r+s=k}a_rb_s\)——等价地，乘两个次数小于 \(n\) 的复多项式——成本渐近同阶。

其中常数显式给出：\(m=10^6\)，\(W^*=2^{71}\)，\(\Delta=6871402692000000\)，\(\lambda\) 与 \(\theta\) 由它们确定。有限初始区间长度用 \(F_n\) 的直接公式处理。算法常数极其巨大，因此这是渐近存在性与显式性结果，没有有用的交叉点估计。系数与精确根的假设是结果的一部分；特别地，结论不主张对稳定浮点 FFT 或位复杂度的相应改进。

构造概览（节译）：第二节给出固定网络，第三节给出局部 Fourier 编译器，第四节处理张量调度与地址，第五节证明定理 1.1 及卷积推论。附录 A 给出从有限代数证书出发的另一条有效路线。固定网络在出处上归于整数乘法那篇手稿，精确宽度的 Fourier 机制则与那里的构造共享；我们证明此处用到的接口，包括其准备与索引界。

背景知识：\(n\log n\) 是怎么变成 FFT 的”身份”的

DFT 把 \(n\) 个复数变成 \(n\) 个复数，矩阵是 \((F_n)_{jk}=\omega_n^{jk}\)。按定义算是 \(\Theta(n^2)\)。Cooley–Tukey 1965 年的 FFT 发现（更早可追到 Gauss 1805 年未发表的笔记，1985 年由 Heideman–Johnson–Burrus 考据还原）把它拆成大小因子的递归：蝶形网络 \(\Theta(\log n)\) 层、每层 \(\Theta(n)\) 个单位成本运算，总计 \(\Theta(n\log n)\)。素数长度走 Rader（1968）或 Bluestein（1970 年刊出，即啁啾算法）转成卷积，再由可复合长度 FFT 兜底。六十年来这条 \(n\log n\) 线没有动过——工程侧的全部改进（SSE/AVX 向量化、缓存分块、GPU 上按 2 的幂劈线程、cuFFT/FFTW 的计划自适应）都是在常数因子和内存行为上做文章，层数×宽度的骨架纹丝不动。

下界侧（第二篇已详述，这里只列）：Morgenstern 1973 在系数有界的线性电路模型里证明了 \(\Omega(n\log n)\)；Ailon 2013 把类似下界推到无界系数但良态（well-conditioned）的线性算法。无条件的 \(n\log n\) 下界从未存在。所以这篇论文干的事，是在一个条件极其明确的模型里把上界压下去——条件本身值得放在显微镜下看（下一节）。

技术解析：他们做了什么

第一步：为什么”无界系数”是突破口

普通 FFT 的蝶形系数是 \(\omega_n^j=e^{2\pi ij/n}\)——模长 1 的”好”常数。Morgenstern 式下界正是靠”系数不能太大”把每一层能做的事情限死。而这篇论文的模型允许任意大的预定标量：算法可以预先计算一张巨大的乘法表（标量准备计入成本但只计一次），运行期只做加、减、乘表值。直觉上，这让”一层蝶形干多层的事”成为可能——用代数关系代替层数。整个构造就是在回答：这种自由度能兑现成多少渐近节省？答案：\((\log n)^{2.1\times10^{-13}}\)。极小，但严格为正。

第二步：原型变换——一个 2×2 矩阵撑起整座大厦

论文不直接构造每个 \(F_n\)，而是先构造一个”原型张量幂变换”，再把任意 \(F_n\) 编译到它上面。原型是

\[ C=\begin{pmatrix}a&b\\ b&a\end{pmatrix},\qquad a=\frac{1+i}{2},\quad b=\frac{1-i}{2}. \]

三个可以直接验证的性质（拿出纸笔、五分钟的事）：

1. \(C\) 是酉的 ：\(a,b\) 模长都是 \(1/\sqrt2\)、相互正交（\(|a|^2=|b|^2=\tfrac12\)，\(\bar a b+ a\bar b=0\)）；
2. \(C^2\) 是交换矩阵 ：\(C^2=\begin{pmatrix}0&1\\1&0\end{pmatrix}\)（交换两个基向量）；
3. \(C\) 与二点 DFT 只差左右各一个对角相位矩阵 ：\(C=\mathrm{diag}(1,-i)\,F_2\,\mathrm{diag}(a,b)\)。

它的 \(k\) 次张量幂 \(C^{\otimes k}\) 作用在 \(2^k\) 维上——\(\{0,1\}^k\) 索引的”超立方”坐标上，\(k\) 个坐标各自做一次 \(C\)，正是一族”原型 Fourier 变换”的多维版本（与 Walsh–Hadamard 结构同族；论文引理 2.2 证明它的方向核恰是 \(C_z=aI+bR_z\) 与其逆的形式，\(R_z\) 是地址平移）。

关键的成本对比：把 \(C^{\otimes k}\) 按定义逐因子作用，代价是 \(O(k\cdot 2^k)\)——正是 \(n\log n\) 的形状（\(n=2^k\)），普通 FFT 的账单长这样。论文用一个固定的线性网络把它做到

\[ O\!\left(2^k(k+1)^{\theta}\right),\qquad \theta<1. \]

机制与第二篇同源：网络沿”角色”（role）重排数据，每个源、门、汇处可以选一个可逆线性算子作为该数据组的”框架”（frame）；标量门作用于数值时，框架作用于地址坐标，两者对易，中间框架相消——同一条物理数据流在不同网络位置承载不同的逻辑数组。数据不动，坐标系在动；把”换位”的成本换成了”亚线性组合”的成本。这就是”局部 Fourier 编译器”：任何长度 \(n\) 的 DFT 先被编译成这些张量幂块加上调度，再用该引擎执行。

第三步：显式常数——论文的”诚实”部分，以及它们怎么来的

论文最不寻常的地方是显式性：指数 \(\theta\) 距离 1 只差 \(2.1\times 10^{-13}\)，而这个每一位数字都可以沿着一条完全显式的构造链回溯。链是这样的：

起点 \(h=100\)：一切从一个手工选定的小整数出发。取 \(\{1,\dots,100\}\) 的全部三元子集 \(T\)（共 \(v=\binom{100}{3}=161{,}700\) 个）。为什么是三？ 因为分离系数用的是三元子集的交集大小——同一集合的两个三元子集交集为 0、2 时给出良定义的配对系数（交为 1 的情况用辅助线对消掉）。为什么是 100？ 组合计数的余量要够大：邻居数（交集大小为 0 或 2 的三元子集数）要压倒性地大于 0（\(\binom{97}{3}+3\cdot 97=147{,}731\) 个），而 \(h\) 越大、比率越干净。100 是”让所有计数不等式都宽松成立”的保守选择。

维度 \(m=h^3=10^6\)：三阶段网络的地址空间是 \(\mathbb{F}_2^m\)——\(m\) 比特的二元向量空间。取 \(m=h^3\) 是为了让三个阶段各占 \(h\) 位的”块坐标”，与三元子集的三个元素对应。

线的总数 \(W\)：网络里每个三元组需要 2 条数据线（两个”bank”）、\(I_0=3v^2\) 次调用各带自己的辅助线（每对邻居一条侧线 + 101 条中心线），总账

\[ \begin{aligned}W&=2N_0+I_0\big(v\cdot d_{\mathrm{nbr}}+101\big)\\&=1{,}873{,}807{,}244{,}643{,}542{,}670{,}000\approx 1.87\times 10^{21}.\end{aligned} \]

（其中 \(N_0=v^3\)，\(d_{\mathrm{nbr}}=147{,}731\)。）这就是那个 \(10^{21}\) 量级的”线数”。

补到 2 的幂 \(W^*=2^{71}\)：递归要求把 \(2^{k-f}\) 个并行副本整批分给数组，分批数必须是 2 的幂。\(2^{70}\approx 1.18\times10^{21}<W\)，所以取覆盖 \(W\) 的最小 2 的幂：\(W^*=2^{71}\approx 2.36\times10^{21}\)。多出来的 \(W^*-W\) 个”空数组” 每个老实使用全部 \(m\) 个普通坐标方向——它们不贡献节省，只为对齐。

绝对节省 \(\Delta\)：三阶段网络里，相邻顶点的子空间是嵌套的，每条线沿网络走一圈实际需要的”方向步”总数 \(s\) 严格小于 \(Wm\)（每条线在每个坐标方向都动一次的上界）。论文 (2.8)–(2.9) 给出这笔维数账的精确形式：带符号求和时，源端维度合计 \(N_0\)、汇端合计 \(Wm-N_0\)，总增量 \(Wm-2N_0\)；唯一的减少项是每条中心线损失 \(h=100\) 维——把带符号换成绝对值要加上两倍损失。于是

\[ \begin{aligned}s&=Wm-2N_0+2I_0(h+1)h,\\ \Delta&=Wm-s=2N_0-2I_0(h+1)h=2v^2\big(v-3h(h+1)\big).\end{aligned} \]

代入 \(h=100\)、\(v=161700\)：\(v-3h(h+1)=161700-30300=131400\)，\(\Delta=2\times 161700^2\times 131400=6{,}871{,}402{,}692{,}000{,}000\approx 6.87\times10^{15}\)。注意这个闭式：节省量恰好等于 \(2v^2\) 乘上”\(v\) 与 \(3h(h+1)\) 之差”——组合计数 \(v=\binom{100}{3}\) 是 \(3h(h+1)=30300\) 的五倍多，严格不等式 \(\Delta>0\) 的余量同样以这个倍数比呈现。这就是”递归增益严格为正”的显式代数化：不是存在某个 \(\delta>0\)，而是这个 16 位整数。

增长率 \(\lambda\) 与指数 \(\theta\)：规模乘 \(m\) 时，更小调用的总数是 \(S=s+(W^*-W)m=W^*m-\Delta\)，摊到 \(W^*\) 个数组上：

\[ \lambda=\frac{S}{W^*}=m-\frac{\Delta}{W^*}=10^6-\frac{6.8714\times10^{15}}{2^{71}}\approx 10^6-2.910\times10^{-6}. \]

递归 \(t(k)\le A+\lambda\,t(\lfloor k/m\rfloor)\) 展开约 \(d=\lceil\log_m(k+1)\rceil\) 层：几何级数求和 \(t(k)\le A\sum_{j<d}\lambda^j+B\lambda^d=O(\lambda^d)=O\big((k+1)^{\log_m\lambda}\big)\)。所以

\[ \theta=\log_m\lambda=\frac{\log\lambda}{\log m}\approx 1-\frac{2.910\times10^{-6}/10^6}{\ln 10^6}\approx 1-2.107\times 10^{-13}. \]

验算：论文给的 \(\theta=0.99999999999978935615699598\)，距 1 的差 \(=2.1064\times10^{-13}\)，与我们从 \(\Delta/W^*\) 独立算出的值吻合——这 15 位小数，每一位都锚定在 \(W\)、\(\Delta\) 这两个显式整数上。

复盘”美感”在哪里：\(\theta\) 的那串 9，不是任何人挑选的；它是 \(h=100\) 的组合计数、三阶段嵌套构造的维数账、以及”2 的幂对齐”这三个完全独立的保守决定复合出的必然值。和第二篇的 \(-182=75+56+50+1\) 同一美学：显式到每一位可审计的渐近节省。想放大 \(\delta\)（比如到可用的量级），就要在这条链的每一环同时收紧——每一环的收紧都对应真实的组合构造难题。

验证状态：形式化了什么、没形式化什么

这个家族的 Lean 形式化覆盖的是子序列版本：对每个 \(c>0\) 与每个 \(N_0\)，存在某个 \(n\ge N_0\)，使得无缩放 DFT 可以用少于 \(c\cdot n\log_2 n\) 个门（加、减、乘预定复标量各一门，对角缩放计价）的电路计算——即沿无穷长度序列存在低于 \(n\log n\) 的电路，无所有长度、有界系数、条件数或位复杂度的主张。全长度、显式指数的主定理 1.1 本身尚未形式化。官方目录同时注明：姊妹篇（有限张量节省与精确 Fourier 电路）与本文共享机制，两篇各自证明自己的接口。换句话说：突破的方向已被机器证明确认，全强度的定量版本还在等待。

意义与限制

对工程：明确为零，且是设计出来的零。摘要和引言反复强调不适用于稳定浮点 FFT。cuFFT、FFTW、你的雷达信号处理链路里的每一行 FFT 代码都不会变——它们的成本由内存带宽、并行度和数值精度主导，与这个模型的计数方式生活在不同宇宙。这篇论文改变的是我们对 \(n\log n\) 的理解：它不是 DFT 的内在税，而是”逐因子作用”这种计算方式的税。

对理论：与第二篇合起来看，\(n\log n\) 这堵墙在两个不同模型（位复杂度：整数乘法；精确复算术：DFT 本体）里被同一套机制（固定线性网络 + 严格递归不等式 + 显式常数）先后击穿。剩下的问题是这面墙还剩多少：两篇的节省都是指数级微小的（\(2^{-182}\) 与 \(10^{-13}\)），而模型条件（无界系数、不计精度的复算术、单位根 oracle）与物理计算的距离也都不小。真正的开放问题是：多项级的节省存不存在，以及有界系数/数值稳定的世界里 \(n\log n\) 是不是真的下界。

方法论上的提示：Morgenstern 和 Ailon 的下界都依赖”系数有界”或”良态”。这些条件在浮点世界是物理必然，在精确算术世界只是习惯。当算法被允许使用无界系数的预乘表时，下界的外墙出现了缺口——而没有任何已知理由禁止这种使用。给做理论的读者的提醒：条件性下界的条件，往往就是突破口所在。

一句话收束：1965 年 Cooley 和 Tukey 把 Gauss 的旧思想写成 \(n\log n\) 时，人们以为那是 DFT 的价格标签。2026 年，这堵墙的核心两块砖在前后十天内被同一套方法凿穿，而 \(n\log n\) 终于显出了它的真实身份：不是数学的铁律，而是一类算法范式的守恒律——范式变了，律也就变了。至于墙后头的路有多长，\(\delta=10^{-13}\) 说了不算，下一个范式说了算。