这是 OpenAI 722 篇数学手稿系列的第二篇，讲三篇”打破复杂度墙”结果里与信号处理血缘最深的一个：整数乘法在多带图灵机上打破 \(n\log n\) 界——直接推翻 Schönhage 与 Strassen 在 1971 年提出、被广泛相信了 55 年的最优性猜想。

为什么说它与信号处理血缘最深？因为整数乘法本质上就是一个 FFT 应用问题：两个 \(n\) 位整数的乘积，是两组系数向量的卷积；而卷积与逐点乘法之间隔着的，正是一个离散 Fourier 变换。所以这篇论文真正冲击的，是整个 FFT 家族复杂度叙事的根基。文中涉及矩阵乘法指数的部分（另一篇手稿的主题）只在必要的对照处出现。

一句话版本：你大学算法课学的”FFT 能做到 \(O(n\log n)\)，而且这基本是最优的”——后半句是错的。现在有一个确定性算法在同一个模型里做到 \(O(n(\log n)^{1-\kappa})\)，\(\kappa=2^{-182}\)。指数节省小到荒谬，但它是严格的。

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

以下内容译自 OpenAI 发布的论文《Integer multiplication below n log n》（2026 年 9 月 23 日），包含标题、摘要、主定理与引言的核心段落。

标题：低于 n log n 的整数乘法

摘要：我们给出一个确定性算法，在单台固定有限字母表、固定有限条一维带的图灵机上，于最坏情形 \(O(n(\lg n)^{1-\kappa})\) 时间内完成两个 \(n\) 位整数的乘法，其中 \(\kappa=2^{-182}\)。该算法对所有输入长度精确成立，并在此模型中推翻了 Schönhage 与 Strassen 的 \(n\log n\) 最优性猜想。

定理 1：存在一台确定性图灵机 \(A\)，具有固定有限字母表与固定有限条一维带，对所有 \(n\ge 1\) 与每对 \(n\) 位输入计算精确乘积 \(\mathrm{val}(x)\cdot\mathrm{val}(y)\)。其最坏情形运行时间满足

\[ T_A(n)=O\!\left(n(\lg n)^{1-\kappa}\right),\qquad \kappa=2^{-182}. \]

该渐近界对所有输入长度一致成立。构造中的常数与阈值极其巨大；本算法旨在建立一个位复杂度界。此定理否定了该模型中任何固定乘法机最终具有 \(\Omega(n\log n)\) 下界的可能性。

引言·相关工作（节译）：在多带图灵机模型中，Schönhage 与 Strassen 于 1971 年证明了 \(O(n\log n\log\log n)\) 界并提出 \(n\log n\) 为最优增长阶。Fürer 在 2007 年改进为 \(n\log n\,2^{O(\log^* n)}\)（2009 年全文刊出），其中 \(\log^* n\) 为迭代对数。De、Kurur、Saha 与 Saptharishi 发展了到达同一量级的模算术路线。后续工作把指数因子降到 \(8^{\log^* n}\)、再降到 \(4^{\log^* n}\)。Harvey 与 van der Hoeven 证明了无条件的 \(O(n\log n)\) 界。

引言·继承的方法（节译）：我们的出发点是 Harvey 与 van der Hoeven 的高斯重采样归约：它把源 Fourier 变换替换为 2 的幂维度的张量变换。Fürer 把廉价的多项式单位根与更一般的根组合以降低昂贵乘法的频率。Harvey 与 van der Hoeven 用高斯重采样过渡到 2 的幂维度的多维变换，再用 Nussbaumer 与 Quandalle 发展的多项式变换求值。Dutt 与 Rokhlin 的高斯网格化工作是更早的概念先驱。这里的定量重采样与位成本估计即取自后文。

引言 1.4 节·推论 2（精确除法与整数平方根）：存在固定字母表与固定有限条带的确定性机器，以 \(O(n(\lg n)^{1-\kappa})\) 最坏情形时间完成 \(n\) 位整数对的精确除法与整数平方根，对每个 \(n\ge 1\)。

引言 1.8 节·对精确 Fourier 变换的伴随应用（节译）：命题 8 的复相位网络同样用于伴随手稿——该手稿给出对每个正变换长度 \(n\) 的精确离散 Fourier 变换的单一算法，当 \(n\to\infty\) 时成本为 \(O(n(\log n)^{1-10^{-13}})=o(n\log n)\)。它既不是定带乘法定理的位复杂度推论，也不是稳定浮点 FFT 的推论。

背景知识：一部 FFT 视角下的整数乘法简史

电子信息出身的人对这条链最熟，我们按 FFT 的演化顺序讲。

卷积是一切的桥。两个整数 \(x=\sum x_i2^i\)、\(y=\sum y_j2^j\) 的乘积系数是 \(c_k=\sum_{i+j=k}x_iy_j\)——线性卷积。反过来，一切卷积（循环的、线性的）都可以用足够长的 DFT 变换为逐点乘法（卷积定理）。所以”整数乘法的复杂度”与”DFT 的复杂度”是同一个问题的两张皮。

1962 Karatsuba（分治卷积的开端）：不碰 Fourier，直接分治——把两个 2 位基数段的多项式乘法用 3 次子乘法完成（\(xy=(a_1t+a_0)(b_1t+b_0)\)，用 \(a_1b_1\)、\(a_0b_0\)、\((a_1+a_0)(b_1+b_0)\) 三次乘法组合出全部系数），得 \(O(n^{\log_2 3})\approx O(n^{1.585})\)。这是”乘法可以低于平方”的第一声。

1963 Toom–Cook（多项式插值卷积）：把 Karatsuba 的 3 点插值推广到 \(k\) 点，得 \(O(n^{1+\eta})\) 对任意 \(\eta>0\)。Cook 把它适配到图灵机——这是位复杂度模型的起点。

1971 Schönhage–Strassen（数论 FFT）：第一个真 FFT 时代算法。在 \(\mathbb{Z}/(2^{2^k}+1)\) 环上做数论变换（NTT，把单位根换成 \(2\) 的幂——乘 \(2^j\) 就是循环移位，对二进制磁带机零成本），实现 \(O(n\log n\log\log n)\)。立碑：\(n\log n\) 应是终点。此后大数乘法的基础设施（GMP 的乘法例程等）都在这个谱系上。

2007–2016 Fürer 时代：\(n\log n\cdot 2^{O(\log^* n)}\)——超出 \(n\log n\) 的部分被压成”迭代对数的指数”，慢到几乎不存在但还不是常数。技术核心：混合单位根（廉价的多项式根 + 昂贵的一般根，控制昂贵乘法的频率）。

2019/2021 Harvey–van der Hoeven（触碑）：无条件 \(O(n\log n)\)。技术核心：高斯重采样——把任意长度的变换恒等式转化为 2 的幂维度的多维变换，源/目标的坐标置换保留在变换恒等式里不真正执行，从而绕开置换成本。这成为本文的直接出发点。

2026 本文（穿碑）：\(O(n(\log n)^{1-\kappa})\)，\(\kappa=2^{-182}\)。碑，被凿穿了。

下界侧从未闭合。严格的 \(\Omega(n\log n)\) 下界从未在无条件下证明过：

• Morgenstern（1973） ：线性电路模型（加法和乘以常数各记一次）中，如果所有系数的绝对值一致有界，DFT 至少要 \(\Omega(n\log n)\) 次运算。
• Ailon（2013） ：无界系数线性算法在”良态”（well-conditioned）条件下有类似的 \(\Omega(n\log n)\)。

也就是说，下界都附加了条件（系数有界、线性结构、数值稳定之类）。Schönhage–Strassen 1971 年的”猜想”说的是：在多带图灵机这个无条件的位复杂度模型里，乘法最终逃不出 \(n\log n\)。55 年来所有上界工作都像是”从上面逼近这条线”，大家越来越相信它就是真相。这篇论文证明：不是。

多带图灵机为什么重要：它是”诚实”的位复杂度模型——没有随机访存，每步只能动常数距离，每次只读写常数位。FFT 在 RAM 上是 \(O(n\log n)\) 次运算，但每次”运算”本身的位成本、以及蝶形运算中 \(\Theta(n)\) 个数据在磁带上的 \(\Theta(\log n)\) 层换位，都要老实计价。在这个模型里数据移动就是算力成本，这正是工程直觉（HBM 带宽、cache 局部性）的理论镜像。

技术解析：节省从哪里来

两种带操作：一切都是”蝶形”与”换位”

论文的机器只做两类固定操作，都是对磁带上数组（笛卡尔积布局）的整块并行变换：

地址交换（换位）：把地址中两个不相交的连续字段（各 \(u\) 比特）互换。最终效果是精确置换，但中间步骤是数据的按位 XOR 组合（类比：三个变量的交换 a^=b; b^=a; a^=b 的数组版放大——但被组织成完整的线性网络，且对任意初始辅助值都精确成立）。成本 \(O(V\,u^{\tau})\)，\(\tau<1\) 严格小于线性于宽度。

数值层（蝶形）：对数值数组的选定地址比特位同时施加

\[ H_0(u,v)=\Big(\tfrac{u+v}{2},\ \tfrac{u-v}{2}\Big). \]

认出它了吗？这就是 FFT 蝶形（去掉 twiddle 因子的 2 点 DFT，带一个 \(\tfrac12\) 归一化）。它对”至多 \(d\) 个等宽地址块中同一比特位”同时作用，成本 \(O(V\,d^{\lambda’})\)，\(\lambda'<1\) 严格小于层数。中间值是精确的高斯二进有理数——没有舍入，没有近似。

关键的调度机制：角色与框架——数据不动，坐标系动

每个过程来自各自的固定线性网络：交换两组值（带规定符号）并恢复所有辅助值。网络中一条线的固定位置称为其角色（role）。把行循环分配到 \(W\) 个角色上；角色流的表示可以沿网络改变：在网络的每个源、门、汇处选取一个可逆线性算子作为该数据组的框架（frame）。标量门作用于数值时，框架作用于地址坐标，两者对易——中间框架沿途相消，首尾框架决定整段的实际坐标变换。

这个设计的意义：同一条物理磁带流，可以在网络的不同位置承载不同的逻辑数据，而不需要物理搬运。数据不动，坐标系在动。这是把”地址重排成本”转化为”亚线性组合成本”的机制核心——普通 FFT 算法在磁带上每层蝶形都要真实搬 \(\Theta(n)\) 个数据，这里让”逻辑上的搬”在物理上免费、只在统计成本时付”框架变化”的钱。

递归不等式：s < Wm

网络构造把 \(m\) 维空间的子空间附着在门与端点上（子空间嵌套，三元子集相交给出系数，辅助线对消多余项）。决定性性质是：参数乘 \(m\) 时，更小调用的总次数 \(s\) 满足 \(s<Wm\)。摊到单位数据体积后，递归贡献的增长率是 \(s/W<m\)——严格小于 1 的增长比，经过对数层的复合，指数上就出现 \((\log n)^{1-\kappa}\) 的幂节省。

完整归约链

从输入到输出（论文图 1）：基数位分解 → 中国剩余映射到素数循环轴（保卷积）→ 高斯重采样到 2 的幂多维变换（沿用 Harvey–van der Hoeven 的恒等式与收缩界）→ Bluestein 啁啾转卷积 → 模 \(y^r+1\) 的多项式环卷积（\(y\) 的幂 = 免费单位根，乘 \(y^k\) = 带符号移位，Nussbaumer 合成变换）→ 恢复系数、舍入、进位。注意一个细节：对已确立的 \(O(n\log n)\) 乘法器（即 Harvey–van der Hoeven）只作普通子程序调用，不递归调用改进后的定理——节省全部来自磁带层的调度，不来自”用更快的乘法算乘法”的自举。

\(\kappa=2^{-182}\) 的解剖：那个”拉马努金般的常数”是怎么长出来的

这是全文最漂亮的部分，值得放慢。你盯着 \(\kappa=2^{-182}\) 看，第一反应必然是：为什么是 182？它不像任何人会”设计”出来的数。答案分四层展开——每一层都是”刻意保守、声明不做优化”的选择，182 只是它们在某一个瓶颈项上相遇时的算术结果。

第一层：两个网络的精确有理亏

两种带操作各自的网络（地址交换的 b 网络、数值层的 c 网络）有自己的参数 \(W_b,s_b,W_c,s_c\)——线的总数与更小调用的总数。递归增长率是 \(s/W\)，而构造给出的精确值是有理数。论文 §3.6 算出了它们的相对秩亏：

\[ \eta_b=\frac{W_bm-s_b}{W_bm}=\frac{339}{22{,}587{,}335{,}000{,}000}\]

\[ \eta_c=\frac{W_cm-s_c}{W_cm}=\frac{73}{19{,}906{,}842{,}167{,}500}. \]

（量级 \(10^{-11}\) 和 \(10^{-12}\)——真实存在但极小的亏空。）参数 \(m\) 满足 \(m<2^{20}\)。论文没有直接用这些分数，而是统一包装成 2 的幂：因为 \(\log m<20\)，

\[ m^{1-2^{-50}}=m\,e^{-2^{-50}\log m}>m\big(1-20\cdot 2^{-50}\big)>m(1-\eta), \]

所以取

\[ \tau=\sigma=1-2^{-50} \]

就同时覆盖两个网络（\(s_b/W_b<m^\tau\)，\(s_c/W_c<m^\sigma\)）。这就是 \(-50\) 的来源：不是设计，是”用 2 的幂盖住一个 \(10^{-11}\) 量级的精确有理亏，且 \(m<2^{20}\) 决定了需要 20 倍余量，\(20\cdot 2^{-50}\) 恰好同时小于 \(\eta_b\) 和 \(\eta_c\)”。

第二层：常数组与层条件

地址轴的选取与各层的耦合引出更多”接近 1 但严格小于 1″的指数和比例。论文 §9.1 一次固定整组（原文声明”刻意保守；不做任何优化”）：

\[ \begin{aligned}\tau=\sigma=1-2^{-50},\quad \beta=\tfrac12,\quad \delta=\tfrac1{16},\\ \lambda=1-2^{-52},\quad c=2^{-56},\quad \lambda’=1-2^{-54},\end{aligned} \] \[ C_1=20,\qquad \epsilon=2^{-75},\qquad \kappa=2^{-182}.\]

各参数的角色：\(\beta\) 分配”维数 vs 深度”的权衡；\(\delta\) 控制精度参数的增长；\(\lambda\) 是归一化蝶形层的指数（§5 的复系数递归）；\(c\) 是每个地址轴实际选取的比特比例（\(K=\lfloor dc\rfloor\)）；\(\lambda’\) 是并行蝶形层指数；\(\epsilon\) 决定地址轴的个数（\(d=\Theta(p^\epsilon)\)，\(p\) 为精度参数，与 \(n\) 同阶）；\(C_1\) 是一个组合常数。

这组常数必须让一整墙的”层条件”同时成立（原文逐一验证）：

\[ \max\{\tau,\sigma\}<\lambda<1,\qquad \tau(1+c/\beta)<1-31\cdot 2^{-55}<\lambda, \] \[ \sigma+\beta(1-\sigma)=1-2^{-51}<\lambda<\lambda'<1,\qquad \epsilon<\tfrac1{12},\qquad \epsilon C_1<1, \] \[ \epsilon(2-\tau)<1-\tau,\qquad \tfrac34+\delta+\tfrac{3\epsilon}{2}<1,\qquad \epsilon(1+c)<1,\qquad \epsilon+\delta<1. \]

每一条都是”某层递归的增益必须严格大于那层的开销”的代数化。比如第一条说：蝶形层的增益指数必须压过 motif 指数（否则递归不收敛到节省）；\(c=2^{-56}\) 之所以必须这么小，是第二条逼的：\(\tau(1+c/\beta)\) 要 \(<\lambda=1-2^{-52}\)，而 \(\tau=1-2^{-50}\) 已经离 1 只差 \(2^{-50}\)，展开可知 \(c/\beta\) 必须在 \(2^{-52}\) 量级以下，\(\beta=1/2\) 下 \(c\) 只能取 \(2^{-53}\) 附近的 2 的幂，取 \(2^{-56}\) 再留数位余量。

第三层：七项成本与瓶颈的会合

最后把所有操作的归一化成本列表（论文 §9.3 的成本表；\(p\) 为精度参数、与 \(n\) 同阶，\(d=\Theta(p^\epsilon)\) 为地址轴数，\(K=\lfloor dc\rfloor\) 为每轴选宽，\(\ell=\Theta(p^{1-\epsilon})\)，\(r\) 为环参数）。每项操作折算成 \(Tp\)（\(T\) 个长度 \(p\) 的工作总量）的附加开销后，都是 \(p\) 的某个幂：

操作	归一化成本	\(p\) 的幂
前缀槽移动与单独蝶形轮次	\(dK\)	\(\epsilon(1+c)\)
变换布局的块交换	\(pK^{\tau-1}\)	\(1-\epsilon c(1-\tau)\)
并行蝶形轮次	\(\ell d^{\lambda’}\)	\(1-\epsilon(1-\lambda’)\)
CRT 与轴布局	\(d^2(1+\ell\tau)\)	\(\tau+\epsilon(2-\tau)\)
高斯线映射	\(dp^{1/2+\delta}\alpha\)	\(\tfrac34+\delta+\tfrac{3\epsilon}{2}\)
啁啾、扭转与标量积	\(dp^\delta\)	\(\epsilon+\delta\)
打包多项式乘积	\(\log(rp)\)	\(1-\epsilon\)

整台机器要跑进 \(n\log n\) 之下，需要七个幂同时严格小于 1——离 1 的缺口分别记作 \(g_i=1-(\text{幂})\)。代入常数组算缺口：

\[ g_1=1-\epsilon(1+c)\approx 1,\qquad g_2=\epsilon\,c\,(1-\tau)=2^{-75}\cdot 2^{-56}\cdot 2^{-50}=2^{-181}, \] \[ g_3=\epsilon(1-\lambda’)=2^{-75}\cdot 2^{-54}=2^{-129},\qquad g_4=1-\tau-\epsilon(2-\tau)>2^{-51}, \] \[ g_5=\tfrac14-\delta-\tfrac{3\epsilon}{2}>\tfrac18,\qquad g_6=1-\epsilon-\delta>\tfrac12,\qquad g_7=\epsilon=2^{-75}. \]

瓶颈是 \(g_2\)：三个”接近 1/接近 0″的保守常数在同一个缺口里相乘，指数相加：

\[ 75+56+50=181. \]

\(g_2\) 对应的操作是”变换布局的块交换”——地址交换网络的成本项 \(pK^{\tau-1}\)：轴数 \(p^\epsilon\)、每轴宽度 \(K=p^{\epsilon c}\) 的 \((\tau-1)\) 次幂。它的缺口把三类独立的保守性（地址轴要少：\(\epsilon\)；每轴选的比特要窄：\(c\)；交换网络的次线性度：\(1-\tau\)）串联在了一起。

第四层：从 \(-181\) 到 \(-182\)

\(g_2=2^{-181}\) 是七个缺口的最小值。最终聚合（论文原话转述）：七个幂中的每一个至多是 \(1-2\kappa\)；而任何固定的 \(\log p\) 幂最终至多 \(p^\kappa\)——所以杂项（各层的对数因子、栈管理、头移动的 \(\log\) 开销）全部被 \(p^\kappa\) 吃掉，总成本

\[ O\big(Tp\cdot p^{1-\kappa}\big)=O\big(n(\log n)^{1-\kappa}\big),\qquad \kappa=2^{-182}=\tfrac12\,2^{-181}. \]

即：取 \(\min g_i=2^{-181}=2\kappa\)，额外留出一个因子 2 的安全垫（\(1-2\kappa\) 而非 \(1-\kappa\)），覆盖所有残余的对数多项式开销。182 = 181 + 1。

复盘：这个数”美”在哪里

回看整个链条：\(-50\) 来自”2 的幂盖住 \(10^{-11}\) 的有理亏”；\(-56\) 来自”层条件对 \(c/\beta\) 的逼挤”；\(-75\) 来自”地址轴数量与十来个不等式的联立求解”；它们在”块交换”这一项相遇，指数相加成 \(-181\)；最后加 1 的安全垫成 \(-182\)。没有任何一步是精调的——论文原话是”刻意保守；不做任何优化声明”。这意味着 \(\kappa\) 的真实自由度远未用尽：把任何一个常数收紧（或者直接用精确有理数 \(\eta_b,\eta_c\) 而非 2 的幂包装），\(\kappa\) 都会显著变大。182 不是这个算法的极限，只是”证明书写到可以机器验证”与”常数好看”之间的一个诚实折中。它的美不在数值，在于它是被三重独立保守性复合出来的、可逐位审计的数——每一位都能沿着上面的表回溯到一个具体的组合构造。

意义与限制

模型与条件的诚实清单（论文自己写得很清楚）：

• 这是 位复杂度 结果：固定字母表、固定带数的多带图灵机，确定性算法，所有输入长度精确成立。这是复杂度理论里最严格的串行模型——更宽松的机器模型上早就有的更快结果（Schönhage 存储修改机上的线性时间、Groff 单位成本 RAM 上低于 \(\log n\) 的因子，后者不计预处理成本），论文原文明确指出都从未覆盖这个固定带模型，本文覆盖了。
• \(\kappa=2^{-182}\)：要感觉到这个节省，\(n\) 得大到宇宙原子数不够用。 渐近意义 100%，实践意义 0% 。论文原话：常数与阈值极其巨大，旨在建立位复杂度界。
• 无 Lean 形式化 ：三篇中唯一没有机器检查证明的（矩阵乘法和 DFT 那两篇有）。73 页的构造性证明，全部人工验证。考虑到第一篇的 Lean 化程度，这个缺口值得注意——但也合理，磁带机的位级调度是形式化最难啃的类型。
• 推论顺带把 精确除法 和 整数平方根 也拉进同界（对数幂节省在减法链上传导），论文第 11 节还讨论了对矩阵转置下界的推论。
• 与第三篇（DFT）的关系：本文命题 8 的复相位网络被 DFT 论文直接复用。两篇是同一套”有限网络节省”技术在两个模型（位复杂度 vs 精确复算术）上的平行应用，互不推导。

对实践的启示：工程界 FFT 的”\(n\log n\) 墙”仍然在——而且要强调，这个结果不改进浮点 FFT、不改进 SRAM 上的实现。它的启示是观念性的：那道墙是模型和条件的产物，不是数学的铁律。当你在下一篇里看到 DFT 在无界系数模型里也被凿穿时，这个判断会更立体。

一句话收束：1971 年，Schönhage 与 Strassen 给出 \(O(n\log n\log\log n)\) 时顺手立了一块碑：”\(n\log n\) 是终点”。2019 年 Harvey 与 van der Hoeven 摸到了碑。2026 年，一台未发布的模型证明碑后面还有路——哪怕只挪动 \(2^{-182}\) 步，那条路是真的。