结果族 130：Exact Fourier transforms below
@@M@@n\log n@@· 学科：Theoretical computer science · 验证状态：暂无形式化证明，请以社区核验为准
把一段声音拆成各个频率的成分（傅里叶变换），1965 年 Cooley–Tukey 的标准菜谱 FFT 约需 @@M@@n\log n@@ 次运算，Bluestein 的啁啾卷积又把任意长度化归到同一量级，此后六十年没人动过这道线。这篇论文造出一台算法，对任何长度 @@M@@n@@ 都只需 @@M@@n(\log n)^{1-10^{-13}}@@ 次精确运算——第一次在所有长度上把这道限速往下压，哪怕只压了一根头发丝。
关键词卡片
@@M@@n@@ 个数拆成 @@M@@n@@ 个频率成分的矩阵乘法。@@M@@n\log n@@ 次运算完成变换。@@M@@k@@ 层的大矩阵，FFT 的核心子问题。@@M@@\log n@@ 因子的指数从 1 压到 @@M@@1-10^{-13}@@。看个具体例子
瓶颈子问题是算小矩阵 @@M@@C@@ 的 @@M@@k@@ 层张量幂 @@M@@C^{\otimes k}@@：朴素逐层要 @@M@@O(k2^k)@@ 次。论文的固定网络每 @@M@@m=10^6@@ 层递归一次，靠绝对盈余 @@M@@\Delta/W_*@@（@@M@@\Delta=6\,871\,402\,692\,000\,000@@，@@M@@W_*=2^{71}@@）让每轮递归省约 @@M@@3\times10^{-6}@@ 次调用，递推 @@M@@t(k)\le A+\lambda\,t(\lfloor k/m\rfloor)@@ 解出：
@@M@@Dt(k)=O\big(2^{k}(k+1)^{0.99999999999978}\big)\;\Longrightarrow\;\text{DFT：}\ O\big(n(\log n)^{1-10^{-13}}\big)=o(n\log n).@@
每百万层省不到十万分之一调用，胜在层层复利：对数因子的指数确实降到了 1 以下。作者也明言常数极大、没有实用交叉点——这是渐近意义上的突破，不是更快的实用 FFT。
为什么值得关心
@@M@@n\log n@@ 被当作傅里叶变换的”物理极限”六十年，本文第一次严格证明它并非极限；连”对数因子还能不能省”这类定性问题里，都仍藏着未被发现的算法空间。
暂无形式化证明（AI 结果待核验）
第一级台阶
导读里的”把声音拆成频率成分”翻译成半数学的说法：对象是一张由单位根填成的 @@M@@n\times n@@ 表格，操作是把这张表格精确地乘到一个长度为 @@M@@n@@ 的数列上；而”菜谱”指的是完成这件事所需的最少步数——每一步只许做加法、减法，或乘一个事先备好的常数。经典菜谱约花 @@M@@n\log n@@ 步，本文的全部戏剧性在于：把这个数压低了一点点，且对所有长度同时做到。
第二级台阶
精确地说：@@M@@n@@ 次单位根 @@M@@\zeta_n=\mathrm e^{2\pi i/n}@@，傅里叶矩阵 @@M@@F_n=(\zeta_n^{jk})@@，输入向量 @@M@@x\in\mathbb C^n@@，要精确算出 @@M@@F_nx@@。计算模型按”精确复数算术”计费：加减与乘预选标量各记一次操作，系数幅度不受限，另配一个由外部提供的指定阶单位根。”省下对数盈余”指运行时间为 @@M@@O(n(\log n)^\theta)@@ 且常数 @@M@@\theta<1@@。
第三级台阶
定理的语境是：存在单一确定性算法，对每个 @@M@@n@@ 都算出 @@M@@F_nx@@，耗时 @@M@@O(n(\log n)^\theta(\log\log n)^{4-\theta})@@，其中 @@M@@\theta=\log_m\lambda=0.9999\ldots<1@@ 由显式常数给出。”精确算术”假设挡住了浮点稳定性与比特复杂度的追问；”系数不受限”挡住了 Morgenstern 型 @@M@@n\log n@@ 下界的适用；”标量准备与寻址计费”挡住了”把成本藏进免费预处理”的质疑。结论即：在一切长度上 @@M@@o(n\log n)@@，推论还把同样的界带给精确卷积与多项式乘法。
本文给出单一确定性算法，对每个长度 @@M@@n@@ 都用 @@M@@O(n(\log n)^{1-10^{-13}})@@ 次精确复数运算完成离散傅里叶变换（discrete Fourier transform），且标量准备与寻址开销全部计费，首次在一切长度上严格突破 @@M@@n\log n@@ 界线。
长度 @@M@@n@@ 的傅里叶矩阵 @@M@@F_n=(\zeta_n^{jk})@@ 的快速计算是算法理论的试金石：1965 年 Cooley–Tukey 的 FFT 在高复合长度达到 @@M@@O(n\log n)@@，Bluestein 的啁啾卷积（chirp convolution）又把任意长度化归到同一量级，@@M@@n\log n@@ 从此被视作天然界线。下界方面，Morgenstern 的行列式论证只适用于系数有界的模型，Ailon 的熵型下界依赖酉两坐标门等限制，都无法约束系数不受限的精确计算；上界方面，Alman–Rao 借矩阵非刚性只改进了 2 的幂长度的领先常数。能否在所有长度上把对数因子本身的指数压低，此前没有任何先例。
定理 1.1：存在单一确定性算法，对每个正整数 @@M@@n@@ 与每个 @@M@@x\in\mathbb C^n@@ 精确计算 @@M@@F_nx@@，耗时 @@M@@O(n(\log n)^\theta(\log\log n)^{4-\theta})@@，其中指数 @@M@@\theta=\log_m\lambda@@ 由显式常数 @@M@@m=10^6@@、@@M@@W_*=2^{71}@@、@@M@@\Delta=6871402692000000@@、@@M@@\lambda=m-\Delta/W_*@@ 给出，数值上 @@M@@\theta=0.99999999999978\ldots<1@@；推论 1.2 即为 @@M@@O(n(\log n)^{1-10^{-13}})=o(n\log n)@@。计算模型的计费相当苛刻：精确复数算术，数据上只允许加减及乘预选标量，系数幅度不受限；由外部提供一个指定单位根（root of unity）@@M@@\zeta_{D_*}@@，@@M@@D_*<1024n^3@@；标量准备、调度构造与对数字长的寻址操作全部计入。推论 1.3 把同样的界推广到精确卷积与多项式乘法。
证明由三个部件拼装而成。
先造固定网络，攻克一个二元矩阵的张量幂（tensor power）。取 @@M@@C=\frac12\begin{pmatrix}1+i&1-i\\1-i&1+i\end{pmatrix}@@：逐轴计算 @@M@@C^{\otimes k}@@ 需 @@M@@O(k2^k)@@，而文中显式构造的标量网络（寄存器由 100 元集合的三元组编址，三阶段、每段八行更新，恒等式 @@M@@RG+JV=I@@ 保证一切辅助线复原）能把两排寄存器整体轮换。关键一招是换标架：给每个门贴上 @@M@@\mathbb F_2^m@@ 的子空间标签 @@M@@U@@，令 @@M@@\Phi_U=J_m\diag(i^{\wt(P_Ux)\bmod4})J_m@@，则 @@M@@\Phi_0=I@@、@@M@@\Phi_{\mathbb F_2^m}=C^{\otimes m}@@；由正交向量的 Hamming 重量模 4 可加，嵌套标签之间的换架恰化为若干方向核 @@M@@C_z=aI+bR_z@@，个数等于残差维数。清点全部残差得 @@M@@s=Wm-\Delta@@，绝对盈余 @@M@@\Delta=2v^2(v-3h(h+1))>0@@；把角色数补齐到 @@M@@W_*=2^{71}@@ 后，递归式 @@M@@t(k)\le A+\lambda t(\lfloor k/m\rfloor)@@ 解出 @@M@@C^{\otimes k}@@ 只需 @@M@@O(2^k(k+1)^\theta)@@。注意网络必须连暂存角色一起变换，递归批处理在任意初值下才严格成立——这是全文反复强调的设计约束。
再造局部编译器，把任意 @@M@@F_r@@ 压回恰好 @@M@@r@@ 个坐标。Newton 插值给出分解 @@M@@F_r(u)=ND_N^{-1}N^{\mathsf T}@@，其中 @@M@@N@@ 是两个对角阵夹一个可逆下三角 Toeplitz 阵；后者用位移秩（displacement rank）方法拆成至多三个秩一外积与平移的卷积和，经 Bennett 式”计算—读取—逆算”重放，可在原有坐标上借用携带任意数据的”脏”坐标执行并复原，深度 @@M@@O(\log^4 r)@@；块大小由打印出的电路门数这一纯整数判据选定。任意剪切运算再用固定的六拷贝 @@M@@C@@ 词实现，@@M@@\kappa=1+|\mu|^2@@ 的非零拆分避开了复数零判别。
最后同步并覆盖全部长度。Good 互素分解把 @@M@@F_L@@ 写成各素因子傅里叶阵的张量积，扇区打包公式让同时的两坐标层在线性数组工作量内变成 @@M@@C^{\otimes k}@@ 调用；取 @@M@@L@@ 为前 @@M@@\ell@@ 个奇素数之积再乘一个 2 的幂（@@M@@2n\le L<4n@@），初等组合估计（不用素数定理）给出 @@M@@\ell=\Theta(\log n/\log\log n)@@；Bluestein 啁啾恒等式 @@M@@\zeta_n^{jk}=\eta^{k^2}\eta^{-(k-j)^2}\eta^{j^2}@@ 把任意 @@M@@n@@ 化为长度 @@M@@L@@ 的循环卷积，且全部所需单位根都是单个 @@M@@\zeta_{D_*}@@ 的幂。合并即得 @@M@@O(n\ell^\theta(\log\ell)^4)@@，也就是定理的界。
本文主结果暂无形式化证明，请以社区核验为准。姊妹篇《Finite tensor savings and exact Fourier circuits》用矩阵价格方法独立证明”有限盈余必然存在”，为本文的证书接口提供第二条来源；两坐标核 @@M@@C@@ 的网络则出自同项目的整数乘法论文。按 OpenAI 官方声明，未经形式化的结果可能有问题。另外文中常数极大，作者明言这是渐近存在性与显式性结果，没有实用的交叉点估计，也不涉及数值稳定性或比特复杂度。
问 1：证明中最脆弱的一步是什么？
答：固定网络对张量幂 @@M@@C^{\otimes k}@@ 的盈余清点。残差计数要精确得出 @@M@@\Delta=2v^2(v-3h(h+1))>0@@，再凑齐 @@M@@W_*=2^{71}@@ 个角色得 @@M@@\lambda=m-\Delta/W_*@@；若任何一处角色或残差被漏数，@@M@@\Delta@@ 的符号翻转，递归式 @@M@@t(k)\le A+\lambda t(\lfloor k/m\rfloor)@@ 的指数 @@M@@\theta@@ 就回到 1，盈余归零。论文还强调网络必须连同暂存角色一起变换，递归批处理才严格成立。
问 2：”系数不受限的精确算术”这个假设为什么不能去掉？
答：这不是缺陷而是命题本身：Morgenstern 的行列式论证与 Ailon 的熵型下界都依赖系数有界或酉两坐标门，恰恰在这些限制下 @@M@@n\log n@@ 是真下界。论文明确声明结论不涉及有界系数电路、数值稳定性或比特复杂度（定理 1.1 后的说明）。
问 3：与 Alman–Rao 相比真正的新意是什么？
答：对方用矩阵非刚性只改进 2 的幂长度上的领先常数；本文给出的是对数因子指数本身的压低，且对全部长度、在把标量准备与寻址全部计费的更苛刻模型下成立——同类首次。
问 4：AI 生成证明最可能在哪里出错？
答：典型风险是天文常数背后的整数恒等式与索引簿记：@@M@@m=10^6@@、@@M@@W_*=2^{71}@@、@@M@@\Delta=6871402692000000@@ 层层相扣，扇区打包公式与角色补齐只要错一格就可能”省了又赔回去”。本文未经形式化，核验只能靠独立重算证书。
问 5：每百万层只省 @@M@@3\times10^{-6}@@ 次调用，凭什么撬动指数？
答：靠复利：递归式解出 @@M@@t(k)=O(2^k(k+1)^\theta)@@，对数因子的指数由 @@M@@\theta=\log_m\lambda@@ 决定，只要 @@M@@\lambda<m@@ 严格成立就有 @@M@@\theta<1@@。论文亦明言常数巨大、无实用交叉点。
问 6：谁会用到它？
答：结论的直接下游是精确卷积与多项式乘法（推论 1.3）；更远的受众是算术复杂度方向——它划定了”下界必须先限制模型”这一教训。姊妹篇的证书接口为同类构造提供了第二条来源。
总评
这是六十年来首次在所有长度上严格突破傅里叶变换 @@M@@n\log n@@ 界线的工作，概念意义重大；但未经形式化、常数巨大，其成立与否完全系于那张巨大网络的逐项清点，短期内只能作渐近存在性结果看待。