OpenAI 数学问题 #130 后续：精确离散傅里叶变换指数节省提升至 7.3e-5

自 1965 年以来，快速傅里叶变换一直以 O(n log n) 次运算计算长度为 n 的离散傅里叶变换。2026 年 9 月，OpenAI 数学问题 #130（精确离散傅里叶变换的显式幂节省）表明，精确变换可以以 log n 的小幂次超越该界限，已发表的指数节省为 1e-13。本仓库包含一份研究草案，提出了更大的节省。

在 #130 的精确复数算术、指定根和对数级字地址模型下，所提出的全长度界为

$$T(n) = O\left( n (\log n)^{1-\delta} \right), \qquad \delta = 7.3 \times 10^{-5}$$

其中 T(n) 是计算长度为 n 的输入的精确 DFT 的成本。

研究状态：书面论证和精确有限检查支持这一提议结果。独立数学评审和端到端形式化验证仍未完成。外部 Lean 源代码检查数值证书和整数乘法参数组装；它并未形式化此傅里叶定理。较早的、可单独评审的结果被保留作为后备。

这不是更快的 FFT。该结果是一个渐近指数。因子 (log n)^delta 仅在 log n 约为 2^13,700 时才达到 2，远超任何可能存在的输入。未声称实际 FFT 加速、有限精度稳定性、有界系数定理或新的整数乘法界。

谁做了什么

• 网络：Swapnil Jain 的第六轮复数网络，基于 Douglas Colkitt、icekylinx、eumemic 和 Aurel Prosz / Paureel 的工作。网络改进归功于其引用的作者。源代码固定为 f2176bc。
• 本草案：提议将该网络转移到傅里叶论文的均匀阵列模型中，并附加额外的有限检查。
• AI 协助：本草案是在 GPT-6 Pro 和 GPT-6-Astra Max 的协助下开发的。完整记录见手稿和外部 NOTICE。

定量比较

这些是渐近指数参数，不是实测运行时加速。较早构造的增益未加到导入网络的节省上。

新的张量值是一个经认证的严格见证，而非临界根。它给出了一个带有额外 (log log n)^(4-theta) 因子的界，其中 theta=1-a。选择 delta<a 可吸收该因子。证书验证了严格矩不等式和正间隙 a-delta=8.52222e-7。

构造

问题 #109 和 #130 中的共同要素是一个用于张量幂的有限网络

$$C = \frac{1}{2} \begin{pmatrix} 1+i & 1-i \\ 1-i & 1+i \end{pmatrix}$$

它不是整数乘法子程序。新构造将相同的张量变换应用于任意输入，同时将每个残差块分组为一次递归调用。三个特征带来了改进：

• 全残差批处理：对排除生产者共享不相交性计算。
• 两阶段拓扑：两个阶段使用m=h^2=576。
• 复制中心调度：保留的中心通过临时副本提供读出，其变换被显式计费。

手稿给出了两阶段端点校正、线性时间数组布局、带不完整批次的不等宽递推，以及通过 #130 现有编译器和全长度归约的转移。整数特定的精度、磁带布局和高斯重采样改进不是此转移的依赖项。

验证

使用标准库 Python 3.10+ 运行：

python3 verification/run_checks.py

这些检查重建所有4,096,576局部系数条目，检查两个方向上的二进制标签和实际辅助帧路径，重建完整的子宽度直方图，并使用精确有理对数边界认证矩。它们还测试标量和端点恒等式，并拒绝缺失副本、缺失端点和过度保存的对照。先前的测试套件继续运行并与其原始参考证书匹配。

这些检查是有限证据。它们不是独立的评审报告，也不是对庞大的完整 DFT 算法的执行。

使用python3 scripts/build_manuscript.py重建 PDF 和 LaTeX（需要 Pandoc 和 pdfLaTeX）。

最需要审查的地方

1. 复制读取调度。
2. 两阶段数据帧接口和端点校正。
3. 线性时间全残差布局。
4. 递推的剩余成本。

先前的审计适用于归档的三阶段结果。它不是对这个新定理的审计。

文件

来源

共享网络源自 OpenAI 的#109 手稿。该转移使用单独的#130 显式傅里叶手稿，特别是命题 4.2 和第 5.4 节。

新的有限构造是Swapnil Jain 的第六轮复杂网络，建立在 Douglas Colkitt 的框架和先前贡献之上，包括 icekylinx 的全残差批处理和复制中心、eumemic 的完整复杂批处理，以及 Aurel Prosz / Paureel 的两阶段拓扑和端点校正。完整的归属和许可证保留在手稿和外部 NOTICE中。