本文是 OpenAI 722 数学手稿系列之 Family 109 官方论文的中文全文翻译。译自 OpenAI 2026 年 9 月 23 日发布的《Integer multiplication below n log n》（73 页），覆盖论文全部章节：摘要、定理 1、引言（§1.1–§1.8）、§2 机器模型与基本流、§3 两个带秩节省的有限网络、§4–§8（地址块交换、并行蝶形层、合成变换、多项式乘积、重采样）、§9 精确整数乘法与成本汇总、§10 除法与平方根、§11 矩阵转置推论、附录 A。原文见 openai/math 仓库（GitHub）preprints/Integer-multiplication-below-n-log-n-September-23-2026/paper.pdf。本站配套科普解析见《OpenAI 722 手稿解读（二）》（文章 ID 4817）。

低于 n log n 的整数乘法

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

对二进制串 \(x\)，记 \(\mathrm{val}(x)\) 为其数值；对输入 \((x,y)\)，记 \(\mathrm{bin}_n(\mathrm{val}(x)\mathrm{val}(y))\) 为乘积的 \(n\) 位二进制表示。记 \(\lg n=\max\{\lceil\log_2 n\rceil,1\}\)。

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

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

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

1 引言

1.1 两种带操作。把输入按基数位分解将乘法化为短整数系数的卷积。我们的出发点是 Harvey 与 van der Hoeven 的高斯重采样归约 [15]：它把 Fourier 变换需要的任意长度换成 2 的幂。本文对该图景的贡献是两个磁带过程，每一个都以各自固定线性网络的形式出现——以规定的符号交换两组值并恢复全部辅助值。第一个过程在地址构成完全笛卡尔积的数组里，交换两个各 \(u\) 位的互斥连续地址字段，成本 \(O(Vu^\tau)\)（固定 \(\tau<1\)）；虽然其最终效果是一个精确置换，中间步骤却是数据的逐点 XOR 组合，且对任意初始辅助值精确成立。第二个过程在数值数组选定坐标位上同时施加 \(H_0(u,v)=((u{+}v)/2,(u{-}v)/2)\)，成本 \(O(Vd^{\lambda’})\)（固定 \(\lambda'<1\)）；中间值是精确的高斯二进有理数。两个过程合用即实现一套地址与数据协同的并行蝶形层。节省的来源：规模参数乘 \(m\) 时，更小调用的总数 \(s<Wm\)——严格不等式 \(s/W<m\) 在对数层复合后给出对数幂的节省。

1.2 线性网络与递归节省。每个过程源于各自的固定线性网络。线在网络中的固定位置称为其角色（role）。把行循环分配到 \(W\) 个角色后，各角色流具有相同的局部地址形状；角色数组的表示可以沿网络改变——在每个源、门或汇处选取一个可逆线性算子作为其框架（frame）。决定性的组合不变量（式 (5) 的框架恒等式）：公共地址置换与逐点位门对易，中间框架相消——同一条物理数据流在不同网络位置承载不同的逻辑数组。第 3 节的有限构造把固定 \(m\) 维空间的子空间附着在门与端点上：相邻顶点的子空间嵌套，其维数差计数一条边所需的小操作；三元子集的相交给出系数，辅助线对消多余项。决定性性质是更小调用的总数 \(s<Wm\)。参数为 \(mf\) 的递归调用因此使用参数 \(f\) 的 \(s\) 次调用，每次作用在体积 \(V/W\) 的流上；除以体积后，参数乘 \(m\) 使递归贡献只乘 \(s/W<m\)。这个严格不等式是幂节省的来源。后续的全部磁带与算术估计都保持它，包括改变数值地址坐标的开销（整块移动 + 受控移位 + 对显式识别的例外地址的确定性修复）。

1.3 从变换到精确乘积。归约链：基数位分解 → 中国剩余映射到互异素数循环轴（保卷积；第 9 节用三角受控移位与计价的轴移动实现）→ 高斯重采样到 2 的幂张量变换（源与目标坐标置换保留在变换恒等式中，不作为独立完整排序执行；第 8 节）→ Bluestein 啁啾恒等式转规范化循环卷积 → 相位扭转把最后循环坐标变为模 \(y^r+1\) 的多项式环（\(y\) 的幂给出免费单位根；Nussbaumer 合成变换）→ 恢复系数、舍入、进位。已确立的 \(O(n\log n)\) 乘法器只作普通子程序调用，不递归调用改进后的定理。

1.4 其他算术操作。推论 2（精确除法与整数平方根）：存在定带确定性机器以 \(O(n(\lg n)^{1-\kappa})\) 完成除法（输出 \(q=\lfloor a/b\rfloor\) 与余数）与平方根（输出 \(\lfloor\sqrt a\rfloor\)）。证明用 Brent [5, 引理 2.1–2.4] 的经典牛顿归约：倒数/平方根近似在几何递增的精度上计算，乘法成本被最后一次精度控制的几何和约束，精确的余数与平方测试恢复整数答案。

1.5 历史脉络。Karatsuba–Ofman（1962）给出 \(O(n^{\log_2\sqrt3})\) [18]；Toom（1963）给出 \(n\exp(O(\sqrt{\log n}))\) [26]；Cook 把 Toom 方法适配到图灵机 [25, 第 1 节]。多带图灵机上，Schönhage–Strassen（1971）证明 \(O(n\log n\log\log n)\) [25]；Fürer（2007/2009）改进为 \(n\log n\,2^{O(\log^* n)}\) [10,11]；后续压到 \(8^{\log^* n}\) 与 \(4^{\log^* n}\) [17,14]；Harvey–van der Hoeven 证明无条件 \(O(n\log n)\) [15]。这些多带界只关乎该固定模型：Schönhage 在存储修改机上得到线性时间 [24]；Groff 在单位成本 RAM 上得到小于 \(\log n\) 的因子（不计预处理）[13]。两者都未在定理 1 的固定有限带模型中建立该界。变换方法层面：Fürer 用廉价多项式单位根降低昂贵乘法频率；HvdH 用高斯重采样过渡到 2 的幂多维变换并用多项式变换求值 [21,20,15]；Dutt–Rokhlin 的高斯网格化是更早的概念先驱 [8]。本文具体改编 HvdH 的高斯重采样恒等式、收缩界与短卷积过程 [15, 定理 4.2、命题 4.7、引理 4.8–4.12]；带符号系数打包是 Kronecker 代换的一种形式，[15, 引理 2.5] 的固定带版本是其直接前身。

1.6 有限网络的组合成分。第 3 节的子集相交构造在乘法之外有更早源头：Alon 对 Frankl–Wilson 构造的表述 [9] 给出互补相交图在不同域上的低次表示 [2, 第 3 节]。素数 \(p=2\) 时子集大小为三，两个多项式求值是”交大小模 2″与”交大小减一”——正是本文的两条配对公式（我们改变底集大小并把第二条用有理双线性型表达）。gather/scatter 与边线的形式是线性索引码解码：低秩线性摘要给出想要的坐标加已知邻坐标的贡献，后者被减去——Bar-Yossef–Birk–Jayram–Kol 建立了拟合矩阵表述 [3, 第 3 节]；Lubetzky–Stav 处理其他域上的解码 [19]。

1.7 下界范围与矩阵转置。Schönhage 与 Strassen 猜想 \(n\log n\) 是乘法成本的最优阶 [25, 第 1 节]。在固定带模型中，”每个乘法机最终有下界”意味着对每个固定机器 \(A\) 存在常数 \(c_A>0\) 与 \(N_A\) 使 \(n\ge N_A\) 时 \(T_A(n)\ge c_An\lg n\)；其否定只需要一台机器使 \(\liminf T_A(n)/(n\lg n)=0\)。本文证明的幂节省给出对所有输入长度为零的极限——这是更强的结论。Harvey 与 van der Hoeven 考虑供给整数 \(m\ge1\) 与 \(k\times k\) 二进制矩阵（\(k=\lfloor\sqrt m\rfloor\)）的转置机，并证明：若每个固定转置机对全部足够大的 \(m\) 有最坏情形 \(\Omega(m\lg m)\)，则每个固定乘法机有相应的最终下界 [16, 定理 1.2]。把他们的定量归约 [16, 推论 6.2] 与定理 1 结合，得到以 \(O(k^2(\lg k)^{1-\kappa})\)（\(\kappa\) 同定理 1）转置行主序 \(k\times k\) 二进制矩阵的确定性固定带算法；第 11 节证明更一般的矩形矩阵界。这一对照只关乎固定条数一维带上的无限制计算：我们的地址过程形成中间数据的 XOR 组合（尽管最终效果是置换），因此位于禁止此类计算的那些模型之外 [16, 第 1.4 节]。

1.8 对精确 Fourier 变换的伴随应用。命题 8 的复相位网络同样用于伴随手稿 [22]——对每个正变换长度 \(n\) 的精确 DFT 的单一算法，成本 \(O(n(\log n)^{1-10^{-13}})=o(n\log n)\)，度量于精确复寄存器模型（单位成本复域操作；\(O(\log(n+2))\) 位字的整数操作与随机访问记单位成本；只允许加、减、乘预定标量；系数与中间值模长无界）。该伴随结果有自己的均匀数组实现，既不是定带乘法定理的位复杂度推论，也不是稳定浮点 FFT 的推论。

2 机器模型与基本流

机器有一个固定有限字母表与固定有限条一维带。一步在每条带上至多读写一格并移动各头至多一格。固定轨道与有限条工作带只改变常数倍时间。我们区分”移动固定基数里的一个数字”（有限次扫描）与”交换位数增长的字段”（第 4 节用 XOR 组合实现）。地址集 \([a_1]\times\cdots\times[a_t]\) 的数组按字典序存储（第一坐标最高位）。

引理 3（受控更新）。固定素数 \(q\) 与有理系数（分母与 \(q\) 互素）。设目标字段 \(y\in[Q]\)（\(Q=q^b\)）跟在其控制字段之后，则更新 \(y\mapsto y+a(\text{controls})\pmod Q\) 成本 \(O(V)\)（偏移可从有限个控制值在 \(b^{O(1)}\) 时间内准备）。证明：按前缀把结果纤维分成 \(Q\) 个长度 \(B\) 的连续块，在 \(Q-a\) 处分裂、两带拼接、按前缀合并读回——两段恰为新目标坐标的连续区间 \([0,a)\) 与 \([a,Q)\)。乘以指定的有理单位（及其逆）同样 \(O(V)\)。

3 两个带秩节省的有限网络

3.1 三元组网络。固定 \(h=100\)，\(T=\{T\subseteq\{1,\dots,h\}:|T|=3\}\)，\(v=\binom h3=161700\)，\(N_0=v^3\)，\(m=h^3=10^6\)。两族标量线 \(X_d,Y_d\)（\(d\in T^3\)）。三元组在交为偶时相邻。网络三阶段：阶段 \(j\) 固定除 \(d_j\) 外的两个下标，在变化 \(d_j\) 得到的两个列表上操作，共 \(I_0=3v^2\) 次调用；每次调用有自己的辅助线（每对有序相邻对 \((S,T)\) 一条边线 \(A_{ST}\)，中心线 \(c_1,\dots,c_h,c^*\)）。一次前向调用是八行调度（行 0–7：\(y\leftarrow y-JA\)；\(y\leftarrow y-Rc\)；\(A\leftarrow A+Vx\)；\(c\leftarrow c+Gx\)；\(y\leftarrow y+Rc\)；\(y\leftarrow y+JA\)；\(c\leftarrow c-Gx\)；\(A\leftarrow A-Vx\)），其中 \(V,G,J,R\) 是定义在源/汇/边线上的固定线性映射（如 \((Vx)_{ST}=x_T\)，\((Gx)_j=\sum_{T\ni j}x_T\)，\((J A)_S=-\sum_{T:|S\cap T|=1}A_{ST}\)）。

引理 5。对辅助线的任意初始值，一次前向调用把 \(y_S\) 变为 \(y_S+x_S\) 且保持其他一切不变。三阶段的”前向—逆向—前向”组合实现 \((X_a,Y_a)\mapsto(-Y_a,X_a)\) 并恢复全部辅助值——正是交换 \(X_a,Y_a\) 的置换。证明是七行代数的直接验证：净目标变化为 \((JV+RG)x\)，与初始辅助值无关；二元情形中心系数是 \(|S\cap T|\bmod 2\)，边线恰好对消交为一的情形；复情形中心系数是 \((|S\cap T|-1)/2\)，边线对消交为零或二的情形。

3.3 标签与维数账。二元标签空间取 \(\mathbb{F}_h^2\) 上双线性型 \(\langle x,y\rangle=x^{\mathsf T}(I-J/9)y\)（特征值 \(1\) 与 \(-h/9\)，非退化），使 \(\langle t_S,t_T\rangle=|S\cap T|-1\)、\(\langle t_T,t_T\rangle=2\)；复情形取 \(\mathbb{F}_{h^2}\) 与普通点积，\(t_T\cdot t_T=1\)。环境标签空间 \(F=\mathbb{F}^{\otimes 3}\)（维数 \(m\)，非退化），端点标签规定为：角色 \(X_a\) 源标签 \(U_a=\langle t_{a_1}\otimes t_{a_2}\otimes t_{a_3}\rangle\)、汇标签 \(F\)；角色 \(Y_a\) 源 \(0\)、汇 \(U_a^\perp\)；暂存角色源 \(0\)、汇 \(F\)。

引理 6。每条边连接可比的非退化标签；唯一的降维边是中心线从时刻 3 到 4 的边，每次维数损失 \(h\)。于是（\(I\) 为调用数、\(c\) 为每调用的中心线数、\(W\) 为总线数）总损失 \(L=Ich\)，且带符号维数和 \(\sum_e(\dim U_{\mathrm{head}(e)}-\dim U_{\mathrm{tail}(e)})=Wm-2N_0+2L\)。

网络的显式数值。二元（b）网络与复（c）网络的显式常数（§3.6）：

\[ W_b=1{,}873{,}807{,}244{,}643{,}542{,}670{,}000,\qquad s_b=W_bm-2N_0 \]

等——以及相对秩亏

\[ \eta_b=\frac{W_bm-s_b}{W_bm}=\frac{339}{22{,}587{,}335{,}000{,}000},\qquad \eta_c=\frac{W_cm-s_c}{W_cm}=\frac{73}{19{,}906{,}842{,}167{,}500}. \]

由 \(m<2^{20}\) 与 \(m^{1-2^{-50}}>m(1-20\cdot2^{-50})>m(1-\eta)\)，取 \(\tau=\sigma=1-2^{-50}\) 得 \(s_b/W_b<m^\tau\)、\(s_c/W_c<m^\sigma\)，\(0<\tau=\sigma<1\)。递归不等式 \(s<Wm\) 的定量版本，全部数值显式可审计。

4 更快的地址块交换

引理 9（下三角分解）。每个秩 \(a\) 的有理 \(m\times m\) 矩阵 \(A\) 有分解 \(A=E_1\Pi E_2\)：\(E_1,E_2\) 可逆下三角有理矩阵，\(\Pi\) 恰有 \(a\) 个 1（部分置换）。这是 Bruhat 分解按相反坐标顺序的初等消元证明（Grigor’ev [12]）。

引理 10（有理矩阵剪切的成本）。固定有理矩阵的有限族与奇素数 \(q\)。对秩 \(a\) 的 \(A\)，把两组各 \(b\) 位字段 \((H,D)\)（前面有控制字段）变为 \((H+AD,D)\) 需要 \(a\) 次更小的交换：按引理 9 分解后，\(E_1,E_2\) 的下三角坐标变换由引理 3 的”后字段由前字段线性更新”实现，\(\Pi\) 由 \(a\) 对 \(\Theta(1)\) 位字段的交换实现。

命题 11（等宽块交换）。存在固定 \(\tau\in(0,1)\) 使 \(s/W<m^\tau\)，则对长度 \(e=mk\) 的两个互斥连续地址块（行字段长度被 \(W^k\) 整除），交换成本 \(O(Ve^\tau)\)。证明：把每块写成 \(m\) 个 \(b=e/m\) 位字段，对每个角色流逐边施加 \(\Phi_{A_e}\)（把地址 \((H,D)\) 处的表项移到 \((H+A_eD,D)\)）——正是框架恒等式：顶点 \(M\) 处的框架是地址置换 \(\Phi_M\)，每条边把它改变 \(\Phi_{M’-M}\)，公共地址置换与逐点位门对易。

引理 12（任意宽度交换）。固定过程把 \([P]\times[2^u]\times[G]\times[2^u]\times[B]\) 上的数组按 \((p,h,g,d,z)\mapsto(p,d,g,h,z)\) 置换，成本 \(O(Vu^\tau)\)，\(V=PGB2^{2u}\)。证明要点：把每块分为顶部 \(\rho=O(\log(2e))\) 位与剩余位，先用命题 11 交换高位对，再用三次”移位拼接”完成整体换位——全程只用受控扫描，不做无限制的数组转置。

5 快速并行合成蝶形层

数组地址集 \([P]\times[2^K]^D\times[S]\)（\(1\le D\le d\)），\(D\) 个连续 \(K\) 位块各选同一位 \(\rho\)。每地址存 \(r\) 个复系数的多项式记录（\(\Theta(p)\) 位/分量）。目标操作是 \(H_0^{\otimes D}\)（系数式作用）。参数 \(d=\Theta(p^\epsilon)\)、\(K=\lfloor dc\rfloor\)、\(r=2^{\Theta(p/d)}\)。

5.1 张量核与精确递归契约。对一组 \(e=mf\) 个选定轴施加有限网络：残差维数之和恰为 \(s_c\) 个子调用（每个在槽的 \(f=e/m\) 个轴上）；源/汇符号与标量 \(i^{27f}\) 把每个端点核变为前向；否定规定的物理库并撤销其交换把结果送回原角色。命题 8 因此在每个角色上给出 \(C^{\otimes e}\)（含初始暂存值为任意的角色）。逆子调用由式 (17) 从一次前向调用得到。剩余操作是固定次数的二元行加与系数式标量操作。

归一化蝶形。对地址 \(x\) 的选定位 \(x_1,\dots,x_D\)，对角算子 \(S_D\) 乘以相位 \(i^{x_1+\cdots+x_D}\)。式 (18)：\(H_0^{\otimes D}=b^D S_D C^{\otimes D} S_D\)，\(b=(-i/2)^{\lfloor D/2\rfloor}b^{D\bmod 2}\)——二元移位加四次根相位。全部相位、逆包装与标量修正是精确的高斯二进操作。

5.2 打包地址加法。把 \(H_0\) 的各行打包为对 \(y,z\) 的段对同时施加。物理上，”以符号 \(\epsilon\) 更新 \(y\) 并测试 \(z\) 的奇偶 \(b\)”是单一循环移位 (22)：\(y\leftarrow y+\epsilon\sum_{i}2^{2j_i}[x_{j_i}=1][z_{j_i}=b]\pmod{2^{j_{f-1}}}\)（移位偏移不依赖目标块，故每行是矩形的双射）。守卫：段初值 \(u_i=2g_i+a_i\) 中的守卫值 \(g_i\) 若都满足 (23)（\(10\le g\le 2^{K-1}-11\)，恰排除 20 个值），则打包加法与独立段加法一致——无段间进位/借位。坏地址比例 \(\delta_{\mathrm{bad}}\le 2(f-1)2^{-K+O(1)}\)，随后被排序修复：提取例外记录、稳定排序、重插。

5.3 命题 14（整层）。在上述布局与守卫下，程序在 \(O(Vd^{\lambda’})\) 时间内返回 \(Q_p(Hz)\)（相同数组/格式），误差 \(\|Q_p(Hz)-Hz\|_\infty<2\sqrt2\,2^{-p}\)；层先被精确求值再做最终截断。内部宽度至多 \(p+\lceil C_0d^{C_1}\rceil\) 分数位（\(C_0=128m_{s_c}+64(W_c+m+1)^3\)，\(C_1=20\)），为 \(O(p)\)。

展开递归。固定 \(\beta=1/2\)，取满足 \(0<\tau<1\)、\(\max\{0,\log_m(s/W)\}\le\sigma<1\)、\(\max\{\tau,\sigma\}<\lambda<1\)、\(\tau(1+c/\beta)<\lambda\) 的有理指数（可显式取得）。\(e<d^\beta\) 时停止递归并逐个施加 \(C\) 核（至多 \(8e\) 次初等操作）。深度 \(\le\lceil\log_m d\rceil\)，每节点至多 \(s\) 个分支且子流体积除以 \(W\)——时间递归 \(F(e)\le sF(e/m)+O(1)\) 逐层展开后以 \(d^{\lambda’}\) 封顶。

6 合成变换与磁带布局

需要的卷积 Fourier 变换的元素是商环 \(R_r=\mathbb{C}[y]/(y^r+1)\)（\(r=2^\ell\)）中的短多项式，所需的单位根以系数表的精确带符号置换作用（多项式变换方法源自 Nussbaumer–Quandalle [21,20]，此处用 [15, §2.4] 的形式）。频率序在卷积中被保留：点乘后反变换消费同一顺序。一轮在每参与轴上施加一个当前 \(H_0\)；轴 \(i\) 的扭转只依赖该轴的地址位，故与其他轴的蝶形对易——各轴步骤可分组为并行蝶形 \(H\) + 记录式单项式 \(J_E\)，在每个地址乘以 \(E\equiv-\sum_{i\text{参与}}y^{E_{b_ik_i}}\cdot\frac{2^r}{t_i}\pmod{2^r}\)（式 (29)）。

7 精确归一化多项式乘积

用 Harvey–van der Hoeven 的固定带乘法器 [15, 定理 1.1]（\(O(N\log(2N))\)）作为独立子程序乘多项式记录（输入 \(O(rp)\) 位），归约是带符号 Kronecker 代换。

引理 17（带符号打包与规范化环乘法）。\(r=2^\ell<2^p\)、\(p+2\le w\le C_wp\)。对盘网格输入 \(f,g\in R_r\)：可精确计算 \(fg\) 的高斯整数分子并返回同格式的 \(Q_p(fg/r)\)，时间 \(O(rp\log(rp))\)。证明要点：实虚分子流分别为 \(ac-be\) 与 \(ae+bc\)；模 \(y^r+1\) 归约即”系数 \(j+r\) 从 \(j\) 中减去”；每个结果系数 \(H_j\) 是恰 \(r\) 个模长至多 \(2^p\) 的高斯整数带符号积之和，故 \(|H_j|\le r2^{2p}\)；以 \(4p\) 位打包字段防相邻字段溢出；最终 \(p\) 位网格分子是 \(\mathrm{trunc}_0(\Re H_j/2^{p+\ell})+i\,\mathrm{trunc}_0(\Im H_j/2^{p+\ell})\)（右移 \(p+\ell\) 位、恢复符号，每系数 \(O(p)\)）。

8 置换留在变换里的重采样

需要的变换长度两两互素，合成变换用 2 的幂——高斯重采样连接两个形状。常规实现每坐标排序两次；这里把两个置换都保留在变换公式中直接计算。

命题 19（一维接口）。按 (33)：\(RF_s=2\gamma B_0′ QF_tA\)，其中 \(A=S’_{16p}\)、\(B_0’=D’_{3p^{3/4}}J’_{4}C\)，各有声明的收缩误差（\(<16p\) 与 \(<4+3p^2/4\)，单位 \(2^{-p}\)）与行机成本 \(O(tp^{3/2+\delta\alpha})\) 级。选择算子 \(C\)（\(\lceil s\cdot j/t\rceil\) 型）是有序子列的选择——前向扫描配计数器即可，零数值误差；被选下标本身可由进位递推 \(c_j=\mathbf 1_{e_j+\rho\ge s}\)、\(e_{j+1}=e_j+\rho-c_js\)、\(f_{j+1}=f_j+h+c_j\) 逐步生成，全部计数器 \(O(p)\) 位。

命题 20（多维接口）。\(T=\prod t_i\)、\(\gamma=2^{d\alpha^2}\)、\(Q=\prod P_{s_i}\)、\(A=\prod A_i\)、\(B_0’=\prod B_{0,i}’\)，则 \(RF_s=2\gamma B_0’QF_tA\)（张量化 (33)）。\(A,B_0’\) 均为收缩，各线实现误差 \(<dp^2\)，一维算法总时间 \(O(dTp^{3/2+\delta\alpha})\)。每 \(t_i\in\{r/2,r\}\) 时，在 \(T\) 项的全填充框里暴露与恢复所有线的成本为 \(O(Tpd^2(1+\ell\tau))\)（等宽块交换界 \(O(Vu^\tau)\) + 固定位移动原语）。

9 精确整数乘法及其成本

9.1–9.2 参数与素轴。取 \(p=6b\)（\(b\) 为基数位宽），素轴长度 \(s_i\in\{r/2,r\}\)、\(r=2^{\Theta(p^{1-\epsilon})}\)、\(d=\Theta(p^\epsilon)\)、\(K=\lfloor dc\rfloor\)、\(\ell=\Theta(p^{1-\epsilon})\)。系数地址同构 \(\Phi:\mathbb{Z}[x]/(x^{s_1}-1,\dots,x^{s_d}-1)\to R_r\) 由 \(x_i\mapsto y^{\mu_i}\)（\(\mu_i\cdot\prod_{j<i}s_j\equiv1\bmod s_i\)）给出：目标单项群大小为 \(S\)，\(x\) 的像的阶为 \(S\)（各 \(\mu_i\) 是单位且 \(s_i\) 两两互素），故 \(\Phi\) 是保持循环卷积的同构。混合基坐标 (42) 按字典序一次嵌套扫描完成填充/去填充。

9.6 算法（六步）。(1) 施加 \(\Phi\)（含填充布局）得源数组 \(u,v\)（系数为模长 \(<1/4\) 的精确 \(p\) 位网格值）；(2) 计算 \(\tilde F(u),\tilde F(v)\)；(3) 对应复系数精确相乘、截断到 \(p\) 位得 \(z\)；(4) 计算 \(\tilde F^+(z)\)，分子精确乘 \(S\) 得 \(\tilde w\approx w=(u*v)/S\)；(5) 分子精确乘 \(2^{2b+4}S\)、逐分量舍入到最近整数、施加 \(\Phi^{-1}\)（含去填充）；(6) 按递增系数序传播基数 \(2^b\) 进位，逆序输出 \(2n\) 位。

9.7 精度与精确恢复。全部接口的误差预算（单位 \(2^{-p}\)）：环卷积 \(E_{\mathrm{ring}}=M(3L+2)<5TL\)；啁啾 \(<8TL\)；源变换 \(E_s=9\cdot2^\gamma TL\)（式 (43)）。中间范数界（.5→.51→.6→.701 等）全部由”收缩不增范数 + 双线性两误差相加”传播；\(b\ge2^{24}\) 等截止使全部边距 \(<10^{-3}\)。最终误差 (44)：

\[ 2^{2b+4}S\cdot28\sqrt2\,\gamma T^2L\cdot2^{-6b}<448b\,2^{-3b/4}<\tfrac12 . \]

真系数是实整数，误差严格小于 \(1/2\) 使最近整数为唯一正确系数——这就是”精确”的最终根据。进位传播的显式不变量：\(k_0=0\)、\(d_j=(c_j+k_j)\bmod Q_0\)、\(k_{j+1}=\lfloor(c_j+k_j)/Q_0\rfloor\)，携带 \(0\le k_j\le q(Q_0-1)<Q_0^2\)，不变量 \(\sum_{h<j}c_hQ_0^h=\sum_{h<j}d_hQ_0^h+k_jQ_0^j\) 逐步验证；乘积 \(<2^{2n}\) 保证第 \(2n-1\) 位以上全零，正好输出 \(2n\) 位。

9.8 完整时间界（成本表）。\(V=Tp=\Theta(n)\)。除以 \(Tp\) 后：

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

式 (45) 直接代入（\(\tau=1-2^{-50},\lambda=1-2^{-52},c=2^{-56},\lambda’=1-2^{-54},\epsilon=2^{-75},\delta=1/16\)）：

\[ g_1>\tfrac12,\quad g_2=2^{-181},\quad g_3=2^{-129},\quad g_4>2^{-51},\quad g_5>\tfrac18,\quad g_6>\tfrac12,\quad g_7=2^{-75}. \]

故 \(\min_i g_i=2^{-181}=2\kappa\)。高斯行的推导：每轴至多 \(T/t_i\) 条处理线，线机成本求和为 \(O(dTp^{3/2+\delta\alpha})\)，除以 \(Tp\) 得第五行（\(\alpha=\Theta(p^{1/4+\epsilon/2})\) 解释其幂）。例外流：每次换基的坏地址份额 \(O(d^22^{-K})\)，紧致例外流长度 \(O(V_{\mathrm{call}}d^2(rp+p)/rp)\)，稳定排序 \(O(p)\) 遍扫描——因 \(d=O(p^\epsilon)\)、\(K=\Theta(p^{\epsilon c})\)，全调用求和 \(O(Vp^{A’}2^{-K})=o(V)\)。七项幂的每一个至多 \(1-2\kappa\)，任何固定的 \(\log p\) 幂最终至多 \(p^\kappa\)，总界

\[ O(Tp\cdot p^{1-\kappa})=O(n(\log n)^{1-\kappa}). \]

固定一个越过全部尺寸/精度/边距/布局条件的截止（以下用教科书乘法），把有限多个更小长度并入隐含常数，即得单一固定字母表、固定带的确定性机器，对每个输入长度以最坏情形 \(O(n(\lg n)^{1-\kappa})\) 输出 \(2n\) 位乘积。

10 精确除法与整数平方根（推论 2 的证明）

用 Brent [5] 的经典牛顿归约。记 \(R_t(z)=2^{-t}\lfloor2^tz\rfloor\)、\(\delta=2^{-t}\)。倒数迭代 \(x\leftarrow x(2-cx)\)：\(u=R_t(c_tx)\)、\(x_+=R_t(x(2-u))\)。设 \(\varepsilon=1-cx\)，则

\[ |1-cx_+|\ \le\ \varepsilon^2+\tfrac{23}{4}\delta<\varepsilon^2+6\delta.\tag{EQINLINE379XEQ} \]

固定种子 \(x=5/8\) 使 \(|\varepsilon|\le3/8\)；\(t=6\) 的一步给残差 \(<1/4\)。此后用封顶倍增精度调度：目标从 \(m\) 到 \(m’=\min\{2m,p\}\)，工作精度 \(t=m’+5\) 位守卫——若残差 \(\le2^{-m-1}\)，则 (\(*\)) 给 \(|1-cx_+|\le7\cdot2^{-m’-1}/16<2^{-m’-1}\)。平方根迭代 \(x\leftarrow(x+c/x)/2\)：规范化 \(x=2^jd\) 后由目标 \(t\) 的倒数得 \(v\)（\(|v-1/x|\le2^{-t}\)），商 \(q_t=R_t(c_tv)\)、\(x_+=R_t((x+q_t)/2)\)；均匀商误差 \(\le7\delta\)，牛顿恒等式给 \(|x_+-\sqrt c|\le\frac{(x-\sqrt c)^2}{2x}+\delta+\tfrac98\delta\)；种子 \(3/2\)、\(t=6\) 一步后误差 \(<1/4\)，同一封顶调度达到 \(2^{-p-1}\)。成本聚合：各阶段只读自己所需的前缀、在标记起点上返回；封顶倍增下 \(\sum_j(m_j+5)=O(p)\) 且 \(\sum_jB(m_j+5)\le(\lg(p+5))^{1-\kappa}\sum_j(m_j+5)=O(B(p))\)——对数幂节省沿牛顿链传播。取 \(P=2n+4\)：倒数给 \(|x-1/c|\le2^{-P}\)，\(a2^{-h}x-a/b<1/4\)，故 \(\lfloor\cdot\rfloor\) 至多差一，用精确余数/平方测试校正——除法与平方根都得 \(O(B(n))\)。

11 矩阵转置的推论

Harvey–van der Hoeven [16, 推论 6.2]：任何最坏情形成本 \(M(m)\) 的乘法机给出固定多带转置机，成本 \(O(M(m)+m\lg\lg\max(n_1,n_2))\)（\(n_1n_2b\le m\)）。调用接口规范化后（把 \(m\) 与两个 \(m\) 位操作数送入定理 1，输出 \(2m\) 位积），由维数与位宽的正性 \(\max(n_1,n_2)\le m\)：

\[ \lg\lg\max(n_1,n_2)\ \le\ \lg\lg m\ =\ o\big((\lg m)^{1-\kappa}\big) \]

（最后一步用 \(1-\kappa>0\)）。故行主序 \(n_1\times n_2\) 二进制矩阵的转置成本 \(O(m(\lg m)^{1-\kappa})\)（\(m=n_1n_2b\) 为矩阵位数）；特别地 \(n\times n\) 二进制矩阵转置 \(O(n^2(\lg n)^{1-\kappa})\)。维数为一不产生例外（约定 \(\lg1=1\)）。

附录 A 分组矩形上的打包加法

定义 22（分组打包流）。固定模板（\(t\ge3\) 个两位标签：00=旁观字段，01/10/11=\(x,y,z\)，每块标签恰出现一次），\(J\ge1\) 个组各有行数 \(n_\nu\) 与各旁观位长度 \(a_{\nu,h}\)（块标签处 \(a_{\nu,h}=2^L\)，\(L=fK\)）。流由 \(M=\sum_\nu M_\nu\) 条 \(R\) 位记录组成，组内地址构成连续字典序矩形 \([n_\nu]\times\prod_h[a_{\nu,h}]\)。

引理 23（分组矩形的打包选位加法）。设描述子 \(D\) 的实际总位长 \(\le A\)。在位置 \(j_i=\rho+iK\)（自最低位编号），一个固定多带过程在每个组里执行 \(y_{j_i}\leftarrow y_{j_i}\oplus x_{j_i}\)（\(0\le i<f\)），固定组、行序数、旁观坐标、其余块位与每条记录载荷（特别是块 \(z\) 被恢复）。对 \(V=MR\)，时间为

\[ O\!\left(V(L\tau+1)+MA^3+M\min\{1,80(f-1)2^{-K}\}\,A(R+A)\right).\tag{46} \]

当 \(A=O(p)\)、\(R\) 超过 \(p\) 的每个固定多项式、\(f\le d\le p\)、\(K/\log p\to\infty\) 时，这就是 \(O(V(L\tau+1))\)，对满足该界的任意组数/形状/载荷一致。证明要点：每组显式存 \(s+1\) 个正整数代码（\(s\)=旁观标签数），故 \(J(s+1)\le A\)、\(Jt\le3A\)；把行序数与首块前的旁观字段折叠为一个前缀字段、块间/块后的旁观区间同样折叠——得到的四长度 \(N_0,\dots,N_3\) 与 \(x,y,z\) 的当前命名恰为引理 13 的矩形；每组内例外的提取/排序/重插完全局部（用局部 \(A_\nu\)-位地址界，无需跨组排序）；对 (46) 的两个附加项除以 \(V\) 后分别为 \(A^3/R\to0\) 与 \(80(f-1)2^{-K}A(1+A/R)=o(1)\)。

---

参考文献（择要，完整见原文）：[1] Agarwal–Cooley 1977。[2] Alon 1998。[3] Bar-Yossef–Birk–Jayram–Kol，FOCS 2006。[4] Bluestein，IEEE TAU 1970。[5] Brent，JACM 1976。[6] Buhrman–Cleve–Koucký–Loff–Speelman，STOC 2014。[7] De–Kurur–Saha–Saptharishi，SICOMP 2013。[8] Dutt–Rokhlin 1993。[9] Frankl–Wilson 1981。[10][11] Fürer 2007/2009。[12] Grigor’ev 1982。[13] Groff 2019。[14] Harvey–HvdH–Lecerf，J. Complexity 2016。[15] Harvey–van der Hoeven，Annals of Math 193 (2021)。[16] Harvey–van der Hoeven，Integer multiplication is at least as hard as matrix transposition，FOCS 2025。[17] 同 [14]。[18] Karatsuba–Ofman 1962。[19] Lubetzky–Stav 2009。[20] Nussbaumer 1980。[21] Nussbaumer–Quandalle 1978。[22] OpenAI，An explicit power saving for the exact DFT，2026。[23] Rosser–Schoenfeld 1962。[24] Schönhage，Storage modification machines，SICOMP 1980。[25] Schönhage–Strassen 1971。[26] Toom 1963。

译注：本家族（109）在 722 手稿中没有 Lean 形式化，是三篇”打破 n log n”结果中唯一无机器检查证明的——73 页构造性证明全部依赖人工验证。译文保留原文编号与公式编号；§3 的七行调度的边线系数表、§5.2 的段位模板、§9.7 的全部中间范数界等逐位机械细节在保持数学内容完整（全部引理/命题/公式/关键证明步骤与全部显式数值）的前提下按原文结构压缩叙述，完整展开请查原文对应章节。