本文是 OpenAI 722 数学手稿系列之 Family 130 官方论文的中文全文翻译。译自 OpenAI 2026 年 9 月 25 日发布的《An explicit power saving for the exact discrete Fourier transform》（31 页），覆盖论文全部章节：摘要、§1.1 算术模型与主结果、§2–§5（固定网络、Fourier 编译器、张量调度、最终估计）及附录 A（有效合成与均匀编译）。原文见 openai/math 仓库（GitHub）preprints/An-explicit-power-saving-for-the-exact-discrete-Fourier-transform-September-25-2026/main.pdf。本站配套科普解析见《OpenAI 722 手稿解读（三）》（文章 ID 4818）。

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

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

1.1 算术模型与主结果

我们的模型具有复数寄存器与整数地址寄存器。一次复数域操作具有单位成本：加法、减法、或乘以一个预先确定的、与输入无关的标量。每一次这样的操作都被计价。除法只用于标量准备，并附有分母非零的证明。对 \(O(\log(n+2))\) 位字上的整数操作与随机访问同样记单位成本；固定数量的此类字可以表示一个地址或整数。这些约定中隐含的所有常数都独立于 \(n\)。

我们提供一个显式指定的、依赖于 \(n\) 的 Fourier 根。等价地，对某个声明的阶 \(d\)，一次单位根操作返回指定的 \(\zeta_d\)，记单位成本。下面的定理只需要一个具有多项式阶的这样的根。从它出发准备其他标量、构造调度、组织数组都计入运行时间。我们不假设有理常数上的域操作能生成任意大阶的根。对复系数或中间数值的模长没有限制，也没有有限精度或数值稳定性断言。

定义绝对常数

\[ m=10^6,\qquad W^*=2^{71},\qquad \Delta=6871402692000000, \]

\[ \lambda=m-\frac{\Delta}{W^*},\qquad \theta=\log_m\lambda. \]

第 2 节的构造使用 \(m\) 个二元坐标的块与 \(W^*\) 个数组。节省量 \(\Delta\) 给出递归乘子 \(\lambda\)，从而给出指数 \(\theta\)。这些常数满足 \(1<\lambda<m\) 且

\[ \theta=0.99999999999978935615699598\ldots<1. \]

小数只为指示节省的量级；(1.1) 中的定义是精确的。

定理 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). \]

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

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

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

时间内计算。

有限初始区间长度用 \(F_n\) 的直接公式处理。算法常数极其巨大，因此这是渐近存在性与显式性结果，没有有用的交叉点估计。系数与精确根的假设是结果的一部分。特别地，结论不主张对稳定浮点 FFT 或位复杂度的相应改进。

推论 1.3（精确卷积与多项式乘法）。存在单一确定性算法，对每个正整数 \(n\) 与每个 \(a,b\in\mathbb{C}^n\)，计算线性卷积

\[ c_k=\sum_{\substack{0\le r,s<n\\ r+s=k}}a_rb_s,\qquad 0\le k\le 2n-2. \]

等价地，它乘两个次数小于 \(n\) 的复多项式。在上面的精确复域操作、指定根与地址成本模型中（允许逐点乘积使用一般域乘法），包括标量准备、调度构造、填充与索引工作在内的总运行时间为 \(O(n(\log n)^{\theta}(\log\log n)^{4-\theta})\)（\(n\to\infty\)）。

第 2 节给出一个固定二坐标变换的显式节省。第 3 节给出局部 Fourier 编译器，第 4 节处理张量调度与地址，第 5 节证明定理 1.1 及其卷积推论。附录 A 给出从有限代数证书出发的另一条有效路线：它用精确有理代数使”有限赢”证书均匀化，并给出一个证明搜索终止的局部证书。附录 A 的路线对 (1.2) 中的指数不是必需的。

固定网络在出处上归于 [13]（整数乘法手稿）在用到处，精确宽度的 Fourier 机制与 [12, 第 3 节] 共享。我们证明此处用到的接口，包括其准备与索引界。特别地，我们不导入 [13] 后面的磁带或精度界，也不从 [12] 的电路存在性结论推断均匀性。

2 一个固定二坐标变换的显式节省

置

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

普通算法逐个作用 \(C^{\otimes k}\) 的 \(k\) 个因子，用 \(O(k2^k)\) 次运算。我们用一个来自 [13, 命题 8 与第 3.5 节] 复数构造的固定网络得到更小的 \(k\) 次幂指数。该网络交换两组值并恢复任意辅助值。沿其导线改变坐标框架即可变换每个组与辅助数组。框架改变的总维数小于分别变换这些数组的代价。我们给出完整的有限构造，因为这个严格节省与对任意辅助值的处理是递归的主要输入。

2.1 带任意辅助值的标量网络

固定 \(h=100\)、\(\mathcal T=\{T\subseteq\{1,\ldots,h\}:|T|=3\}\)、\(v=\binom h3=161700\)、\(N_0=v^3\)、\(m=h^3=10^6\)。

两组标量线 \(X_d,Y_d\) 由 \(d=(d_1,d_2,d_3)\in\mathcal T^3\) 索引。两个三元组相交为偶数时称为相邻；相邻三元组互异。网络有三个阶段。在阶段 \(j\)，固定除 \(d_j\) 外的两个下标，对变动 \(d_j\) 得到的两个列表操作。这样的调用共有 \(I_0=3v^2\) 个。每次调用有自己的辅助线，与其他调用互异：对每个有序相邻对 \((S,T)\) 一条侧线 \(A_{ST}\)，以及 \(h+1\) 条中心线 \(c_1,\ldots,c_h,c^*\)。

对一次调用，记逻辑源组与目标组为 \(x=(x_T)\) 与 \(y=(y_S)\)。定义固定线性映射

\[ (Vx)_{ST}=x_T,\qquad (Gx)_j=\sum_{T\ni j}x_T,\qquad (Gx)_*=\sum_T x_T, \]

\[ (JA)_S=-\sum_{T:\ S\text{ 邻 }T}\frac{|S\cap T|-1}{2}A_{ST},\qquad (Rc)_S=\frac{\sum_{j\in S}c_j-c^*}{2}. \]

前向调用由以下八行组成，按序：

\[ \begin{aligned} 0:\ &y\leftarrow y-JA &&\text{每个目标及其侧线一门}\\ 1:\ &y\leftarrow y-Rc &&\text{目标与中心一门}\\ 2:\ &A\leftarrow A+Vx &&\text{每个源及其侧线一门}\\ 3:\ &c\leftarrow c+Gx &&\text{源与中心一门}\\ 4:\ &y\leftarrow y+Rc &&\text{目标与中心一门}\\ 5:\ &y\leftarrow y+JA &&\text{每个目标及其侧线一门}\\ 6:\ &c\leftarrow c-Gx &&\text{源与中心一门}\\ 7:\ &A\leftarrow A-Vx &&\text{每个源及其侧线一门} \end{aligned} \]

门就是所指明的其线上的有限线性映射。其标量实现（包括全部加法 \(a+b\) 与移位）恰为所指矩阵。逆调用按相反顺序执行这些行，并把 \(V,G,J,R\) 换为各自的转置；源与目标互换。

中间系数是积分的：相邻三元组的交大小为 0 或 2。二元向量 \(t_X,t_Y\) 是侧线的两个物理三元指示子。

2.2 帧把二元维数变成方向操作

标量网络连接每条物理线的连续触碰处，包括其源与汇。我们给每个门与端点指派一个二元子空间，同一门触碰的所有线共用一个子空间。该子空间指定了替换每条线的复数组上的一个框架变化。下面的构造有两个有用性质：公共框架与标量门对易，且在合适的嵌套子空间之间移动时每新增或删除一个二元维数只需一次方向操作。

为此使用带普通点积的二元空间 \(D=\mathbb F_2^m\)。子空间非退化指其限制双线性形式的根基为零。其正交补与下面的投影都在 \(\mathbb F_2\) 上取；它们与承载数据的复空间是分开的。

对 \(z\in\mathbb F_2^m\)，记 \(R_z\) 为数组地址的平移：\((R_zf)(x)=f(x+z)\)。归一化 Walsh 矩阵

\[ J_m=2^{-m/2}\big((-1)^{x\cdot y}\big)_{x,y\in\mathbb F_2^m} \]

与每个 \(R_z\) 对易。对非退化子空间 \(U\) 置

\[ q_U(x)=\mathrm{wt}(P_Ux)\pmod 4,\qquad \Phi_U=J_m\,\mathrm{diag}_x\big(i^{q_U(x)}\big)J_m. \]

这里 wt 是整数 Hamming 重量。这些矩阵证明恒等式；算法不执行 Walsh 变换。特别地 \(\Phi_0=I\) 且 \(\Phi_D=C^{\otimes m}\)。

引理 2.2。设 \(U,V\subseteq D\) 为嵌套的非退化子空间。称较小子空间在较大子空间中的正交补为其残差。设它有大小为 \(\rho\) 的标准正交二元基。则 \(\Phi_V\Phi_U^{-1}\) 是恰 \(\rho\) 个形如 \(C_z=aI+bR_z\) 或 \(C_z^{-1}\) 的方向核之积，其中 \(z\ne0\)。每个逆需要一个前向核与一次平移。

证明。对二元向量 \(x,y\)，

\[ \mathrm{wt}(x+y)=\mathrm{wt}(x)+\mathrm{wt}(y)-2|\mathrm{supp}(x)\cap\mathrm{supp}(y)|. \]

故重量对正交向量按模四可加。若 \(V=U^\perp E\) 且 \(z_1,\ldots,z_\rho\) 是 \(E\) 的标准正交基，则

\[ q_V(x)-q_U(x)=\sum_{j=1}^{\rho}\mathrm{wt}(z_j)[z_j\cdot x]\pmod 4, \]

其中括号取整数代表 0 或 1。每个 \(\mathrm{wt}(z_j)\) 为奇数，故其模四值是 1 或 \(-1\)。递减边上整个表达式变号。恒等式 \(i^{[z\cdot x]}=a+b(-1)^{z\cdot x}\) 与 Walsh 共轭给出所述核。最后 \(R_z^2=I\) 且 \(C_z^2=R_z\)，从而 \(C_z^{-1}=R_zC_z\)。□

要把此计算应用到网络，把每条标量线替换为以 \(D\) 索引的数组。给每个门一个非退化标签 \(U\)，对它触碰的所有线公共；给每个源与汇各自的标签。沿标签 \(U\) 到 \(V\) 的边插入 \(\Phi_V\Phi_U^{-1}\)，并逐点应用标量门。标量门以标量系数混合它触碰的数组，而它们的公共框架作用于地址坐标。这两个操作对易。中间框架因此相消，在源框架与汇框架之间留下标量网络。

更一般地，对整数 \(f\ge1\)，每个数组以 \(f\) 列 \(m\) 位索引并以 \(\Phi_U^{\otimes f}\) 为其框架。相同的相消给出完整的线性映射。级数扩张与行 1 的对角相位幂恰好吸收指标 \(z\to(0,z)\)。

引理 2.3（嵌套标签）。存在对每条线与网络每个顶点的非退化子空间标签，使相邻标签嵌套，其正交残差有标准正交二元基，且每个门的标签包含其输入与输出标签之和。（论文以表格逐行给出：X 线 in→2 的残差 \(B\otimes t_X^\perp\)、X 线 2→3 的残差 \(P\otimes t_X^\perp\)、Y 线 0→1 与 4→5 的 \(B\otimes t_Y^\perp\)、中心线的 \(B\otimes D\) 与 \(P\otimes D\)、侧线各行的 \(B\otimes\langle t_Y\rangle\)、\((B\otimes t_Y^\perp)^\perp(P\otimes\langle t_X\rangle)\)、\(P\otimes\langle t_X,t_Y\rangle^\perp\)、\(P\otimes\langle t_Y\rangle\)、辅助线的 \(E\otimes D\otimes Q^\perp\)。）

（证明要点：\(t_X\cdot t_Y=0\) 且两向量范数一，故 \(t_Y^\perp=\langle t_X\rangle^\perp\cap\langle t_X,t_Y\rangle^\perp\)。2→5 边的行 2 标签 \((B\otimes D)^\perp(P\otimes\langle t_X\rangle)\) 落在其行 5 标签 \((B\otimes D)^\perp(P\otimes t_Y^\perp)\) 中，残差恰如所示。其余行由 \(E=B^\perp P\) 与 \(D=\langle t\rangle^\perp t^\perp\) 给出。这些分解验证全部包含关系，并表明唯一的减少是中心边 3→4，每次维数 \(h\)。）

沿物理线的带符号变化相消。源端维数合计 \(N_0\)、汇端合计 \(Wm-N_0\)，总量为 \(Wm-2N_0\)。\(I_0(101)\) 条中心线每条损失 \(h=100\) 维一次。带符号变化换成绝对变化要加上两倍损失，即得 \(s\) 的公式。特别地

\[ \Delta=2N_0-2I_0(h+1)h=2v^2\big(v-3h(h+1)\big)>0, \]

因为 \(v>3h(h+1)\)。代入 \(h=100\)、\(v=161700\) 给出所示整数。

单独的非退化性在特征二中不保证标准正交基：非退化形式可能是交错的。这里每个非零残差含范数一的向量：\(t^\perp\) 与 \(\langle t_X,t_Y\rangle^\perp\) 分别包含支撑至多 3 与 6 的坐标单位向量。

2.3 张量扇区的调度与打包

（原文 §2.3 给出打包数组的内存布局与递归批次的枚举：\(W\) 个长度 \(2^{mf}\) 的打包数组中，角色流上的地址由列数码的字典序组成；递归调用以 \(S=W^*m-\Delta\) 个批次组织，每批处理 \(2^{k-f}/W^*\) 个列副本。）

2.4 主递归

定理 2.6。设 \(W^*=2^{71}\)、\(m=10^6\)、\(\Delta\) 同 (1.1)。对所有 \(k\ge0\)，\(W^*\) 个数组的同时变换 \(I_{W^*}\otimes C^{\otimes k}\) 可在

\[ O\!\left(W^*2^k(k+1)^{\theta}\right) \]

时间内完成，对每个整数 \(k\ge0\)。界包括固定表构造、全部标量算术、数组初始化、索引准备与数据移动。只需有理常数与 \(i\)。

证明。先同时变换 \(W^*\) 个任意数组。置 \(K=m(71+1)\)。对 \(k<K\)，逐个沿纤维作用 \(C\) 的 \(k\) 个因子。因 \(K\) 固定，成本除以 \(W^*2^k\) 在整个基础区间有绝对常数界。对 \(k\ge K\)，写 \(k=mf+r\)，\(f=\lfloor k/m\rfloor\)、\(0\le r<m\)。直接作用剩余 \(r\) 个位因子。在 \(W\) 个数组上用命题 2.4 处理 \(f\) 列与 \(r\) 个旁观位。在其余 \(W^*-W\) 个数组的每个坐标位置用一个方向步，同样对所有 \(f\) 列同时进行。方向步共 \(S\) 个。

每步需要 \(2^{k-f}\) 个独立变换 \(C^{\otimes f}\)。因 \(f\ge72\) 且 \(k-f\ge(m-1)f\ge71\)，\(2^{k-f}\) 可被 \(W^*=2^{71}\) 整除。经引理 2.5 的置换后，把打包数组分成大小 \(W^*\) 的批；批数至多其长度。于是

\[ T(k)\le AW^*2^k+\frac{S}{W^*}\frac{2^{k-f}}{2^{f}}\,T(f)\cdot\frac{2^f}{1}, \]

归一化 \(t(k)=T(k)/(W^*2^k)\) 后

\[ t(k)\le A+\lambda\,t(\lfloor k/m\rfloor)\qquad(k\ge K). \]

这个精确递归允许临界指数 \(\theta=\log_m\lambda\)。直接展开 \(d\) 步直到参数低于 \(K\)。相继参数为 \(\lfloor k/m^j\rfloor\)，且 \(d\le\lceil\log_m(k+1)\rceil\)。若 \(B\) 界住归一化基础成本，则

\[ t(k)\le A\sum_{j=0}^{d-1}\lambda^j+B\lambda^d\le\frac{A}{\lambda-1}+B\lambda^d=O\big((k+1)^{\theta}\big). \]

这里 \(\lambda^d\le\lambda(k+1)^{\theta}\)。基础区间上增大常数即得同样估计。□

2.5 线性时间地址变更

命题 2.4 的地址置换不得引入因子 \(f\)。下列枚举也解释了递归批次的均匀构造。（原文给出四状态遍历：扇区起点 \(S\)、前缀宽 \(Q\)、扇区内偏移 \(o\)、原地址 \(I\)；按实际局部数码 \(a_j\) 以表提供的 \(p_j,q_j,t_j\) 更新 \(S\leftarrow S+Qp_j\tau_j\)、\(Q\leftarrow Qq_j\)、\(o\leftarrow oq_j+t_j\)、\(I\leftarrow Ir_j+a_j\)；叶处打包地址为 \(S+o\)，总成本 \(O(R)\)。）

3 编译自身坐标上的 Fourier 变换

我们接着用恰在其给定坐标上的浅层表示 Fourier 矩阵。保持宽度是本质的：之后坐标集将是张量因子，单独填充它们会乘以总维数。先把 Fourier 矩阵分解为对角与三角 Toeplitz 矩阵，再在其自身坐标上实现那些 Toeplitz 因子（用 [12, 第 3 节] 的精确宽度机制与工作区的有效选取），最后把每个二坐标操作编译到上面的矩阵 \(C\)。

剪切把一个坐标的标量倍加到另一坐标并保持其他坐标不变。剪切层由不相交对上的剪切组成。单项层是可逆单项矩阵。混合轮在互不相交的坐标区域上执行单项层或剪切层；它分解为一个单项层后随一个剪切层。

引理 3.1（Fourier 矩阵的分解）。（原文：对每个 \(r\)，\(F_r\) 等于 \(N^{-1}\) 型三角 Toeplitz 因子、对角相位与置换的乘积；由 Kailath–Kung–Morf 的位移秩理论，宽度 \(r\) 的三角 Toeplitz 因子在自身坐标上有 \(O(1+\log^4 r)\) 层的字。）

引理 3.2（自身坐标上的 Toeplitz 因子）。宽度 \(v\) 的三角 Toeplitz 矩阵在恰 \(v\) 个坐标上有 \(O(1+\log^4 v)\) 个混合层的字，其系数为 \(\mathbb Q(u)\) 与二幂根中的有理式，所有分母非零。

（证明要点：把区间分成连续块；对目标块大小 \(a\)、源块大小 \(e\)，由 (3.5) 的远差恒等式，矩阵 \(D=M-J_aMJ_e^T\) 是三个外积之和 (3.7)——第一个外积由首行修正、第二个由首列修正。由幂零性迭代 \(M=D+J_aMJ_e^T\) 给出有限重建 (3.8)。对每个外积 \(vw^T\)，其贡献可按前向复制-逆序-再复制的模式——Bennett 可逆模拟——在借用坐标上重放，恢复任意初始内容。）

引理 3.3（带任意借用坐标的重放）。设 \(M:\mathbb C^e\to\mathbb C^a\) 有含 \(g\) 个门、深度 \(H\)、扇入至多二、扇出至多 \(\delta\)（含输出使用）的线性 DAG。则 \(M\) 可在恰 \(e+a\) 个坐标上以 \(O(g)\) 门、深度 \(O(H)\) 实现，保持其余借用坐标的任意初始值。（这是干净透明计算 [6, 第 3 节] 的原理；其首次重放有 Bennett 计算-复制-逆序模式，去源的第二次重放证明精确相消与层界。）

命题 3.1（局部编译）。对每个整数 \(r\ge2\)，宽度 \(r\) 的 Fourier 矩阵 \(F_r\) 可在自身坐标上以

\[ O(1+\log^4 r) \]

个单项与剪切层之字实现，其系数为 \(u\) 与引理 3.4 的二幂根中的有理表达式，所有分母非零。

（证明：对 \(N\) 的 Toeplitz 因子应用引理 3.4；\(N\) 的两个对角因子是单项层；组合各字的转置、逆并分裂混合轮即得。）

完成命题 3.1 的证明：回忆 \(C=\begin{pmatrix}a&b\\ b&a\end{pmatrix}\)、\(a=(1+i)/2\)、\(b=(1-i)/2\)。置

\[ H’=\begin{pmatrix}1&1\\ 1&-1\end{pmatrix},\qquad S=\mathrm{diag}(1,i). \]

直接相乘给出 \(H’=a^{-1}SCS\)，且

\[ K:=H’\mathrm{diag}(2,1)H’\,\mathrm{diag}(-3,1)H’=\begin{pmatrix}-8&-10\\ 0&-6\end{pmatrix}. \]

于是每个非零系数 \(t\) 的上剪切恰有三个 \(C\) 的前向复制与可逆对角因子的字：

\[ \begin{pmatrix}1&t\\ 0&1\end{pmatrix}=D_t\,\mathrm{diag}(-1/8,-1/6)\,K\,D_t^{-1},\qquad D_t=\mathrm{diag}(4t/5,1). \]

更新 \(y\leftarrow y+tx\) 就是有序对 \((y,x)\) 上的这个上剪切。对的次序是离散调度的一部分。

一般系数 \(\mu\) 可能为零，但无须检验：在计算坐标上该字恰实现所需剪切，零系数在非门保留恒等。（原文在此完成二坐标编译与工作区计量的说明。）

4 线性数组工作中的张量因子同步

引理 4.1（打包与扇区枚举）。宽度 \(R=\sum r_j\) 的打包数码地址与块选择可在 \(O(R)\) 次操作内枚举，且局部表与后缀积准备好后，对数也可在 \(O(R)\) 内生成。（证明：按块选择首次分叉的轴 \(j\) 分类先前扇区；前面的已选块贡献宽度 \(\sum_{i<j}q_i\)，轴 \(j\) 的较早块总宽 \(p_j\)，后续轴总宽 \(\tau_j\)。这些互斥类给出 (4.2)。数字遍历维持四状态 (4.3)。叶处打包地址为 \(S+o\)。）

命题 4.2（同步变换）。设 \(\ell\ge1\) 与 \(r_1,\ldots,r_\ell\ge2\) 为整数、\(\sum N\) 且给出所需指定根。置 \(R=\sum r_j\)、\(r_{\max}=\max r_j\)。映射 \(\bigotimes_jF_{r_j}\) 可在

\[ O\!\left(R(\ell+1)^{\theta}\big(1+\log r_{\max}\big)^4+\mathrm{poly}(\ell,r_{\max},\log(R+2))\right) \]

次操作内计算，包括编译、标量准备与数组工作。多项式与隐含常数是绝对的。

证明。在每个轴上用命题 3.1。其字可细化为 \(O((1+\log r_{\max})^4)\) 种槽型的公共序列：单项槽或 \(C\) 的不相交复制与单位恒等的槽。填充一个对槽意味着在该轴只用单位块。

在每个槽上跨轴取张量积。这些槽相乘得到所需张量变换，因为

\[ \Big(\bigcirc_j A_j\Big)\Big(\bigcirc_j B_j\Big)=\bigcirc_j(A_jB_j). \]

特别地，局部字在任意输入上的正确性就够了。另一轴可在中间槽改变坐标；不要求它在该字全程保持局部字的借用坐标。

张量单项式由前缀遍历计价 \(O(R)\)。张量对槽分解为引理 4.1 的扇区。其宽 \(2^k\) 的扇区恰承载 \(C^{\otimes k}\)。定理 2.6 界其成本（含调用与移动）为 \(O(2^k(k+1)^{\theta})\)。因 \(k\le\ell\) 且扇区宽之和为 \(R\)，总成本 \(O(R(\ell+1)^{\theta})\)。打包、解包与发现连宽一的扇区再花 \(O(R)\)。这给出 (4.4) 的第一项。

局部编译器用其宽度中的多项式工作。后缀积、局部块表与其他整数准备用 \(\ell,r_{\max},\log(R+2)\) 中的多项式工作。运行标量积已在遍历中计价，故多项式项只描述局部准备。□

5 工作长度与每个长度的变换

要在请求长度 \(n\) 应用同步变换，先选工作长度 \(L\) 使 \(2n\le L<4n\)。下界允许下面的啁啾卷积，上界保持数组大小为 \(n\) 的线性。还需要小的互素因子：其宽度必须是 \(\log n\) 的多项式，使局部编译只有对数多项式成本。初始奇素数之积提供这些轴，一个 2 的幂填满到 \(2n\) 的剩余缺口。

5.1 足够的小互素因子

设 \(r_1<r_2<\cdots\) 为奇素数、\(R_\ell=\prod_{j=1}^\ell r_j\)、\(R_0=1\)。下面的适度估计就够了；不用素数定理。

引理 5.1。有 \(r_j=O((j+1)^2)\) 且 \(\log R_\ell=\Theta(\ell\log(\ell+2))\)。对满足 \(R_\ell\le2n\) 的最大 \(\ell\)，当 \(n\to\infty\)，

\[ \ell=\Theta\!\left(\frac{\log n}{\log\log n}\right),\qquad \log\ell=\Theta(\log\log n). \]

素数与该 \(\ell\) 值可用 \(\log(n+2)\) 的多项式次操作、\(O(\log(n+2))\) 位整数找到。

证明。记 \(\pi(t)\) 为至多 \(t\) 的素数个数。对整数 \(u\ge1\)，

\[ \frac{1}{2u+1}\binom{2u}{u}\le\binom{2u}{u}\le(2u)^{\pi(2u)}. \]

第一个不等式因为中心二项系数最大。在阶乘公式中，素数 \(p\) 在 \(\binom{2u}{u}\) 中的指数至多 \(\lfloor\log_p(2u)\rfloor\)；其素数幂贡献至多 \(2u\)，得第二个不等式。取 \(u=(j+1)^2\) 得 \(r_j=O((j+1)^2)\)。上界由求和给出；下界由 \(r_j\ge j+2\) 得 \(R_\ell\ge(\ell+2)!/2\)。最大化条件给出 \(\log n=\Theta(\ell\log\ell)\)，即 (5.1)。□

选此 \(\ell\)，令 \(e\ge0\) 为使 \(L=R_\ell2^e\ge2n\) 的最小整数。则 \(2n\le L<4n\)、\(2^e<2r_{\ell+1}\)、\(e=O(\log(\ell+2))\)。有界长度直接处理。

5.2 CRT 置换与工作变换

用 Good 的互素张量分解 [9]，其指标置换计入成本。对 \(L\) 的两两互素因子 \(q\)（这里为奇素数与非平凡的 \(2^e\)），选 \(d_q\) 使 \((L/q)d_q\equiv1\pmod q\)、\(E_q=(L/q)d_q\)。整数 \(E_q\) 是模 \(L\) 的正交幂等元。中国剩余索引 \((j_q)_q\mapsto\sum E_qj_q\pmod L\) 是双射，且

\[ \zeta_L^{jk}=\prod_q\zeta_q^{d_qj_qk_q}. \]

故在输入输出指标的置换后，\(F_L\) 是诸 \(F_q\) 的张量积。这些置换取 \(O(L)\) 数组操作。

在奇素数轴上应用命题 4.2，依次固定 2 的幂轴的每个数码；再在该轴的纤维上应用通常的基二 FFT。前者成本 \(O(L(\ell+1)^{\theta}(1+\log(\ell+2))^4+\mathrm{poly}(\log(n+2)))\)；后者 \(O(L(1+e))\)。于是 \(F_L\) 及其逆的总成本为

\[ O\!\left(L\big[(\ell+1)^{\theta}(1+\log(\ell+2))^4+1+e+\mathrm{poly}(\log(n+2))\big]+O(1)\right). \]

对逆，几何根和给出 \(F_L^2=LJ\)（\(J\) 模 \(L\) 反转指标），故 \(F_L^{-1}=L^{-1}JF_L\)，只加线性工作。

5.3 啁啾卷积与准备

归约是 Bluestein 啁啾卷积 [5]（[14, 第 II 节] 的加权卷积形式）。固定卷积操作数的准备被显式计价。置 \(\eta=\zeta_{2n}\)。对 \(0\le j,k<n\)，

\[ \zeta_n^{jk}=\eta^{k^2}\eta^{-(k-j)^2}\eta^{j^2}. \]

准备两个长度 \(L\) 的向量：输入依赖向量在 \(0\le j<n\) 处取值 \(\eta^{j^2}x_j\)、其余为零；固定向量在 \(-(n-1)\le u\le n-1\) 表示的剩余类处取值 \(\eta^{-u^2}\)、其余为零。由 \(L\ge2n\) 这些剩余类互异。循环卷积在每处 \(0\le k<n\) 给出 (5.7) 中乘以 \(\eta^{k^2}\) 之前的和。

卷积由对两向量应用 \(F_L\)、逐点相乘、应用 \(F_L^{-1}\) 得到。固定向量的变换是标量准备的一部分，显式计为一个完整变换。只有三次完整变换。

现在指定定理 1.1 允诺的单位根。以 (5.3) 的 \(L\)，置

\[ D^*=(2n)L\,2^{\lceil\log_2(16L)\rceil}. \]

啁啾根阶为 \(2n\)，工作因子根的阶整除 \(L\)。命题 3.1 对局部宽度 \(r\le L\) 需要至多 \(8r\) 阶的 2 幂根；每个这样的阶整除 (5.8) 的最后一个因子。固定核只用 \(i\) 与有理常数。故每个所需初始根是供给的指定 \(\zeta_{D^*}\) 的整数幂。而且

\[ D^*<64nL^2<1024n^3. \]

二进制取幂在 \(O(\log(n+2))\) 次域操作内提取每个局部初始根。

5.4 最终估计

定理 1.1 与推论 1.2 的证明。构造中的全部映射都是精确且确定性的。由 (5.4)、\(e=O(\log(\ell+2))\)、\(L=\Theta(n)\)、\(\theta>0\)，(5.6) 与常数次变换给出

\[ T(n)=O\big(n\ell^{\theta}(\log\ell)^4\big)+\mathrm{poly}(\log(n+2))+O(1). \]

每个固定的 \(\log(n+2)\) 幂最终相对 \(n\ell^{\theta}\) 可忽略。代入 (5.1) 证 (1.2)。

对指数的精确界，(1.1) 中的直接整数算术给出

\[ \epsilon:=\frac{\Delta}{mW^*}=\frac{1717850673}{590295810358705651712}>\frac{28}{10^{13}}. \]

因 \(\log m<14\)，对 \(\eta_0=2/10^{13}\) 有 \(\eta_0\log m<\epsilon\)。用 \(\exp(-t)\ge1-t\)，

\[ \lambda=m(1-\epsilon)<m\exp(-\eta_0\log m)=m^{1-2\cdot10^{-13}}. \]

故 \(\theta<1-2\cdot10^{-13}\)。(1.2) 中 \(\log\log n\) 的固定幂对充分大 \(n\) 小于 \((\log n)^{10^{-13}}\)。这证明推论 1.2。□

最后，所有长度、根阶、指标积与地址都以绝对常数在 \(n\) 的多项式内界；(5.9) 显式处理最大根阶。固定网络表贡献绝对常数，局部表大小为 \(\log(n+2)\) 的多项式。数组移动与遍历已在定理 2.6 与引理 4.1 中计数。故模型所要求的每整数固定个 \(O(\log(n+2))\) 位字贯穿始终。

5.5 双输入卷积与多项式乘法

上面的啁啾归约卷积输入数据与固定向量，故保持线性。对两个可变操作数，同一 Fourier 恒等式给出推论 1.3，在每个变换坐标处有一次两个输入依赖值之积。

推论 1.3 的证明。置 \(M=2n-1\)，把 \(a,b\) 零填充为长度 \(M\) 的向量 \(\tilde e_a,\tilde e_b\)。其支撑中两个指标之和在 \(0\) 与 \(2n-2=M-1\) 之间，故长度 \(M\) 的循环卷积无回绕且恰为 \((c_0,\ldots,c_{M-1})\)。以正指数约定，卷积恒等式为

\[ (F_Mc)_j=\sum_{r,s=0}^{n-1}a_rb_s\zeta_M^{j(r+s)}=(F_M\tilde e_a)_j(F_M\tilde e_b)_j. \]

计算两个前向变换与其 \(M\) 个逐点积得 \(p=F_Mc\)。由 \(F_M^2=MJ\) 得 \(c=M^{-1}JF_Mp\)：再一次前向变换、指标反转与缩放给出答案。

对三次变换的每一个在长度 \(M\) 应用定理 1.1，每次计价其标量准备、调度构造与索引工作。该长度供给的单一指定根可在三次调用中复用；其显式可计算阶满足 \(D^*<1024M^3<8192n^3\)。填充、逐点积、反转与输出缩放取 \(O(M)\) 次域与地址操作。总计 \(3T(M)+O(M+\log(M+2))\)；由 \(M=\Theta(n)\) 得第一个界，推论 1.2 给出最终的小数次幂界。\(n=1\) 时同一公式适用。□

附录 A 有效合成与均匀编译

本附录给出从有限张量节省到均匀 Fourier 算法的一般路线。其目的是分开两个问题：如何从 \(\mathbb C\) 上的存在定理得到可用系数，以及当有效小电路的编译时间没有有用界时如何使用它们。主论证中的显式网络不经过搜索即给出更强的定量结论。

所用的证书由同一个可逆非单项矩阵 \(A\in\mathrm{GL}_q(\mathbb C)\)（整数 \(q,b\ge2\)）的两个有限字组成。第一个字在恰 \(q^b\) 个坐标上作为 \(A^{\otimes b}\) 作用，用

\[ g<b\,2^{b-1} \]

次对 \(A\) 的前向调用，间以可逆单项式。第二个字在 \(q\) 个坐标上作为 \(U=I_q+E_{12}\)（\(E_{12}\) 为矩阵单位）作用，用同一 \(A\) 的正数次前向调用与可逆单项式。伴随论文 [12, 定理 8.3 与引理 2.2] 从一般有限赢定理与可逆非单项矩阵的正生成得到这样一对。

引理 A.1（符号搜索的局部证书）。对 (2.1) 的可逆非单项矩阵 \(C\)，存在整数 \(b\ge2\)、\(g\ge0\) 与恰在 \(2^b\) 个坐标上的字，用 \(g<b2^{b-1}\) 次对 \(C\) 的前向调用与可逆单项式实现 \(C^{\otimes b}\)。在两个坐标上，\(I_2+E_{12}\) 有恰三次对同一 \(C\) 的前向调用与可逆对角因子的字。

证明。在 \(W^*=2^{71}\) 个长度 \(2^{mf}\) 的数组上用命题 2.4 与 (2.10) 的填充。\(S=W^*m-\Delta\) 个方向步在其张量因子分别应用时恰需 \(Sf2^{mf-1}\) 次前向 \(C\)-调用：一步有 \(2^{(m-1)f}\) 条纤维，每条需 \(f2^{f-1}\) 次调用。逆步只加平移。(2.3) 的每个标量行是既有互异角色间初等剪切的复合；其源坐标在该行内不变。系数为非零有理数。(3.13) 把逐点工作界为 \(H2^{mf}\) 次前向调用，\(H\) 为固定整数。其余操作均为可逆单项式。每个角色承载任意数据，故该字恰用 \(W^*2^{mf}\) 个坐标并作为 \(I_{W^*}\otimes C^{\otimes mf}\) 作用。

把角色索引等同于 71 个二元轴，沿其每个应用 \(C\)。这花费 \(71W^*2^{mf-1}\) 次调用并给出 \(C^{\otimes b}\)、\(b=mf+71\)。其实际调用数满足

\[ g\le(Sf+71W^*+2H)2^{mf-1}=b2^{b-1}-(\Delta f-2H)2^{mf-1}<b2^{b-1} \]

对任何整数 \(f>2H/\Delta\)。最后 \(\det C=i\) 且 (2.1) 的两个标量系数非零，故 \(C\) 可逆且非单项。取 \(t=1\) 的 (3.13) 给出 \(I_2+E_{12}\) 的三次调用字。有序对上的任何嵌入调用是 \(C\oplus I_{2^{b-2}}\) 的置换共轭；置换可吸收进相邻单项因子。□

引理 A.2（有效有限代数提取）。给定 \(\mathbb Q\) 上 \(a\) 个变量中的有限多个多项式 \(f_i\)，一个确定性有理算法或者证明 \((f_i)\) 是单位理想，或者产出非零有限维交换含幺 \(\mathbb Q\)-代数 \(E\)（带理数乘法表）与满足每个 \(f_i(\xi)=0\) 的元素 \(\xi_1,\ldots,\xi_a\in E\)。特别地，复解保证第二种结局。所需单位可用加逆见证方程施加。

证明。维护理想 \(I=(f_i)\) 的有限生成清单与整数 \(m\)（初始 \(m=a\)）。在对坐标的可逆多项式变更后，对每个 \(j>m\) 维护 \(I\) 中形如 \(x_j^{d_j}+\sum c_e(x_1,\ldots,x_{j-1})x_j^e\)、\(d_j\ge1\) 的首一成员。故 \(S=\mathbb Q[x_1,\ldots,x_a]/I\) 作为 \(R=\mathbb Q[x_1,\ldots,x_m]\) 上的模有限。

先计算纤维 \(S/(x_1,\ldots,x_m)S\)：置 \(x_1=\cdots=x_m=0\)，只按所示首一关系取商。作为首一扩张的塔，\(B\) 有由 \(x_j\)-次数小于 \(d_j\)（\(j>m\)）的单项式组成的基底。若纤维非零即为所求答案。若 \(m=0\) 且纤维为零，则 \(S=0\)、\(I\) 为单位理想。

设纤维为零且 \(m>0\)。断言 \(I\cap R\ne0\)：否则 \(R\hookrightarrow S\)。在 \(R\) 的 \(\mathfrak m=(x_1,\ldots,x_m)\) 处局部化。有限 \(R_{\mathfrak m}\)-模 \(S_{\mathfrak m}\) 非零。零纤维会给 \(S_{\mathfrak m}=\mathfrak mS_{\mathfrak m}\)；对有限生成列 \(v\) 有 \(v=Mv\)、\(M\) 全部元素在极大理想中。乘以 \(I-M\) 的伴随行列式得 \(\det(I-M)v=0\)，其行列式为单位——矛盾（Nakayama 引理的行列式形式 [15]）。

按递增次数截断枚举 \(I\) 生成元单项式倍数、有理线性代数检验其张成是否含仅前 \(m\) 个变量的非零元，找到非零 \(h\in I\cap R\)。非零常数证明 \(I=(1)\)。否则设 \(d=\deg h\ge1\)，代换

\[ x_i=y_i+y_m^{(d+1)^i}\ (1\le i<m),\qquad x_m=y_m, \]

保持后续变量。权 \(1,(d+1),\ldots,(d+1)^{m-1}\) 由 \((d+1)\) 进制展开区分总次数至多 \(d\) 的全部单项式。故变换后的 \(h\) 中 \(y_m\) 的最高次幂有非零有理首项系数；除以它得到 \(y_m\) 中的首一关系。变量重命名并 \(m\) 减一。至多 \(a\) 次这样的递减，证明终止。这就是 Noether 正规化的标准证明中的三角形单一代换 [16]。□

注 A.3（忠实标量模拟）。若 \(d=\dim_{\mathbb Q}E\)，则 \(E\otimes_{\mathbb Q}\mathbb C\) 是带计算出的乘法表的 \(\mathbb C^d\)。嵌入 \(z\mapsto z1_E\) 单。加法按坐标、乘以任何准备好的代数元素是 \(d\times d\) 复矩阵，故每线性代数操作 \(O(d^2)\) 次普通标量操作。当电路作为 \(F_r\) 乘代数单位作用时，输入嵌入为 \(1_E\) 的倍数、读每个输出的第一坐标即可。选择复嵌入或提取代数根是不必要的。\(d\) 在输入长度已知前已固定。

A.2 越来越高效的基的打印机

记录固定恒等式为何对有效电路打印机足够。[12, 引理 2.3] 的张量放大也在 \(E\) 上可行：其证明只用恒等式与线性操作。显式地，置 \(Q=q^b\)、\(j=\lfloor k/b\rfloor\)，把 (A.2) 的第一个字跨 \(j\) 组张量。每个调用槽分解为

\[ (A\oplus I_{Q-q})^{\otimes j}\sim\bigoplus_{r=0}^{j}\binom jr(A^{\otimes r})\oplus{}^{(r)}(Q-q)^{j-r}, \]

在这些较小的张量阶上递归、对少于 \(b\) 个剩余轴直接调用。设 \(f(k)\) 为该递归构造除以 \(q^k\) 的大小。扇区按维数加权，故归一化成本满足

\[ f(k)\le C_0+g\,\mathbb E f(K),\qquad K\sim\mathrm{Bin}\big(\lfloor k/b\rfloor,\ q/Q\big). \]

由 \(gq/(bQ)<1\)，选 \(0<\alpha<1\) 使 \(g(q/(bQ))^\alpha<1\)。凹性与归纳给出

\[ f(k)=O\big((k+1)^\alpha\big). \]

对相继的 \(t\ge1\)，令 \(r_1<\cdots<r_t\) 为大于 \(2q\) 的前 \(t\) 个素数、\(m_t=\prod r_i\)、\(\ell_t=m_t2^{\lceil\log_2(16r_t)\rceil}\)、\(R_t=\mathbb Q[z]/(\Phi_{\ell_t}(z))\)。分圆多项式与该有限代数中的算术是有效的。在 \(E\otimes_{\mathbb Q}R_t\) 上、Fourier 系数在中心因子 \(R_t\) 中进行构造。两个证书恒等式及其逆见证在纯量扩张下保持。

在每个宽度 \(r_i\) 上用引理 3.5 的精确宽度 Fourier 层构造，得 \(O(1+\log^4r_t)\) 个单项或不相交剪切层。其有理公式在 \(R_t\) 中成立。为代换 (A.2) 的第二个字，把任何剪切系数 \(c\in R_t\) 拆为两个单位 \(d^+(c-d)\)：测试 \(d=1,2,\ldots\) 直到 \(c-d\) 是单位。单位系数 \(v\) 的剪切由 \(\mathrm{diag}(v,1,\ldots,1)\) 共轭 \(U\) 得到，故它有 (A.2) 的固定字模式。跨轴同步这些固定字模式，闲位置用恒等。由 (A.3)，其他槽是 \(A^{\otimes k}\)（\(k\le t\)、总宽 \(m_t\)）的直和，大小 \(O(m_t(t+1)^\alpha)\)。中国剩余重索引由局部 Fourier 变换的张量给出 \(F_{m_t}\)。以 \(z\mapsto\zeta_{\ell_t}\) 特化 \(R_t\)，得到 \(\mathbb C\) 上输出矩阵为 \(F_{m_t}\) 乘代数单位的电路。由注 A.3 只展开固定代数 \(E\)。所得复线性电路大小

\[ s_t=O\big(m_t(t+1)^\alpha(1+\log^4(t+2))\big)=o(m_t\log m_t). \]

打印机显式计算全部张量系数与接线。它可花任意有限的位计算来做。每个系数是在 \(\zeta_{\ell_t}\) 处求值的有理系数多项式；符号逆已在 \(R_t\) 中归约。对每个多项式系数打印有限的 Horner 求值清单，有理字面量显式写出。故打印记录含完整电路与完全展开的标量准备程序，无未指定的复常数或隐藏循环。

A.3 从慢打印机到快均匀算法

定理 A.4（有界打印机均匀化）。设一台固定位机器打印一列完整记录 \((m_t,\mathcal C_t)\)，\(m_t\) 严格递增趋于无穷，\(\mathcal C_t\) 以 \(s_t=o(m_t\log m_t)\) 个标量线性门计算 \(F_{m_t}\)。每条记录须显式列出门、输出指标与一个每条指令显式列出并按序执行一次的标量准备程序。其指令用有理字面量、带有效非零除数的域操作、以及以二进制字面量写明阶的标准 Fourier 根 \(\zeta_a=\exp(2\pi i/a)\)。则存在一个确定性算法在本文模型中（含准备与索引）以 \(o(n\log n)\) 时间计算每个 \(F_n\)。单一指定根（阶小于 \(8n^3\)）就足够。

证明。打印预算同时控制电路描述与全部字面量标量数据。规范化打印机为每步至多输出一位。对 \(n\ge2\)，从头运行 \(B=\lfloor\log_2 n\rfloor\) 位步。选最后一个满足 \(2\le m_t\le B\) 的完成记录；若没有，用普通基 \(m=2\) 电路。可见描述至多 \(B\) 位；解码、求值准备程序、构造有理字面量花费 \(B^{O(1)}\)。门表对每个新输入在 \(O(m+s)\) 时间内执行。

置 \(X=2n-1\)、\(m_H\) 为不超过 \(X\) 的最大 \(m\) 的幂、\(p=\lceil X/m_H\rceil\)、\(P=m_Hp\)。则 \(X\le P<2X<4n\)、\(H\le\log(2n)/\log m\)。混合基数 Fourier 递归用 \(H\) 份基 \(m\) 与一份直接计算的基 \(p\)。分裂 \(ab\) 处输入指标 \(bj_a+j_b\)、输出指标 \(ka+ak_b\)，恒等式

\[ (bj_a+j_b)(ka+ak_b)\equiv bj_aka+aj_bk_b+j_bka\pmod{ab} \]

给出两个较小的 Fourier 变换与中间旋转因子。复用解码出的基电路每次。一次变换（或其逆）成本

\[ O\big(P[1+p+H(1+s/m)]\big)+B^{O(1)}. \]

最后把 \(F_n\) 归约到长度 \(P\) 的卷积。以 \(\eta=\zeta_{2n}\)，存 \(\eta^{j^2}x_j\)（\(0\le j<n\)）并零填充；固定核在 \(-(n-1)\le h\le n-1\) 的剩余类处存 \(\eta^{-h^2}\)。卷积输出 \(k\) 乘 \(\eta^{k^2}\)。恒等式 \(k^2+j^2-(k-j)^2=2kj\) 恰好给出 \(F_nx\)。常数次 (A.5) 界的变换加线性准备与缩放即完成。

根计数：设 \(R\) 为所选准备程序中列出的根阶之积。其总二进制长度至多 \(B\)，故 \(R\le2^B\le n\)。单一根 \(\zeta_D\)（\(D=2nPR<8n^3\)）以整数取幂供给每个列出的根与两个外层根。至多 \(B\) 个这样的请求，取幂与构成指数花费 \(B^{O(1)}\)。

由 \(p=O(1+\log n)\)，(A.5) 的算术项除以 \(n\log n\) 给出

\[ O\!\left(\frac{1+p}{\log n}+\frac1{\log m}+\frac{s}{m\log m}\right)=o(1). \]

对数多项式准备项也是 \(o(n\log n)\)。长度 1 是恒等。这证明了断言，全部选择与输入值无关。□

把定理 A.4 应用到上面的打印机，直接从有限证书接口得到一个均匀的全长度 \(o(n\log n)\) 算法。符号搜索、有限代数与存储电路是实现装置；唯一供给的复原语是显式指定的 Fourier 根。这个结论补充了正文的显式定量构造。

---

参考文献（择要）：[1] Ailon 2013。[2] Ailon 2014。[3] Alman–Rao，STOC 2023。[4] Bennett 1973。[5] Bluestein，IEEE TAU 1970。[6] Buhrman 等，Catalytic space，STOC 2014。[7] Cooley–Lewis–Welch 1967。[8] Cooley–Tukey 1965。[9] Good 1958。[10] Kailath–Kung–Morf 1979。[11] Morgenstern，JACM 1973。[12] OpenAI，Finite tensor savings and exact Fourier circuits，2026。[13] OpenAI，Integer multiplication below n log n，2026。[14] Rabiner–Schafer–Rader，chirp z-transform，1969。[15][16] Stacks Project（Nakayama 引理、Noether 正规化）。

译注：本家族的 Lean 形式化覆盖的是子序列版本（姊妹篇 [12]：对每个 \(c>0\) 与 \(N_0\ge2\)，存在 \(n\ge N_0\) 使无缩放 DFT 可用少于 \(c\cdot n\log_2 n\) 个门的电路计算）；全长度、显式指数的主定理 1.1 本身尚未形式化。译文保留原文编号；§2.3 的内存布局细节与若干长证明在保持数学内容完整的前提下按原文结构概述并注明”原文给出”，完整细节请查原文。