结果族 109：Integer multiplication below
@@M@@n\log n@@· 学科：Theoretical computer science · 验证状态：暂无形式化证明，请以社区核验为准
两个 @@M@@n@@ 位大数相乘，小学竖式要 @@M@@n^2@@ 步；FFT 类高级方法做到约 @@M@@n\log n@@。1971 年 Schönhage 与 Strassen 猜想：在纸带计算机（图灵机）上，这已是极限。这篇论文造出一台奇特的图灵机，硬是跑到了 @@M@@n\log n@@ 之下——快得极其微弱，但严格跌破，五十年老猜想就此被推翻。
关键词卡片
@@M@@n\log n@@@@M@@(\log n)@@ 的指数压到 @@M@@1-\kappa<1@@，哪怕 @@M@@\kappa@@ 小得离谱看个具体例子
公式卡
@@M@@T(n)=O\!\left(n\,(\lg n)^{1-\kappa}\right),\quad \kappa=2^{-182}@@
@@M@@\lg n=2^{182}\ \Rightarrow\ (\lg n)^{\kappa}=\left(2^{182}\right)^{2^{-182}}=2\ \Rightarrow\ T(n)=\tfrac{1}{2}\,n\lg n@@
要亲眼看到”省一半”，输入位数 @@M@@n@@ 得大到 @@M@@2^{2^{182}}@@：光用十进制写下”有多少位”，就需要约 @@M@@6\times10^{54}@@ 个数字——宇宙里的原子都不够存。所以这是纯理论纪录：它证明”搬运数据的对数税”并非命中注定。
为什么值得关心
卡点曾像”两头收税”：卷积天然要过 @@M@@\Theta(\log n)@@ 层变换，每层又似乎必须扫遍 @@M@@\Theta(n)@@ 个比特，相乘正是 @@M@@n\log n@@。本文让”搬运”与”算术”两头的节省同时发生。它无条件反驳了计算模型层面的最优性猜想；同文推论还把精确除法与平方根也降到同一时间界。构造中的常数与生效阈值都刻意取得极大，重在证明可行，而非实用。
暂无形式化证明（AI 结果待核验）
第一级台阶
导读里”两头收税”的比喻，对象是一台纸带计算机：数据存在一条条一维纸带上，读写头挪动、读写本身就是代价。操作是对两个 n 位二进制大数做精确乘法。卡点在于乘法的本质是错位相加的卷积，它天然要过对数多层数值变换，而每层似乎都必须扫过全部存储比特——层数乘扫描宽度，恰好 n log n。
第二级台阶
用复杂度术语说：位复杂度按比特操作计费；卷积把乘法化为系数多项式乘法；Harvey–van der Hoeven 的高斯重采样把所需傅里叶变换化成轴长全为 2 的幂的多维变换，再经 Nussbaumer 合成多项式变换把最后一维装进多项式环——乘单位根退化为系数表的带符号移位。于是整个变换只剩三种动作：地址重排、带符号移位、两点蝶形；节省必须同时发生在搬运与算术两头。
第三级台阶
定理在固定模型下陈述：存在一台确定性图灵机，字母表与一维带条数都是固定有限，对每个输入长度精确输出 2n 位乘积，最坏时间 O(n(lg n)^{1−κ})，κ=2^{-182}。固定模型与逐长度精确这两条假设堵住了”换机器”“靠近似”的逃逸口；结论是对对数因子的严格幂节省——数值再小，也推翻了 Schönhage–Strassen 1971 年”n log n 是该模型最优增长阶”的猜想。同界推论还免费送给精确除法与整数平方根。
本文构造了一台固定字母表、固定带数的多带图灵机，对所有输入长度精确计算两个 @@M@@n@@ 位整数的乘积，最坏时间 @@M@@O(n(\lg n)^{1-2^{-182}})@@：在普通多带比特模型中严格跌破 @@M@@n\log n@@，推翻了 Schönhage–Strassen 的最优性猜想。
1971 年，Schönhage 与 Strassen 在多带图灵机（multitape Turing machine）上给出 @@M@@O(n\log n\log\log n)@@ 的整数乘法，并猜想 @@M@@n\log n@@ 是该模型的最优增长阶。经过近半个世纪的一系列改进，Harvey 与 van der Hoeven 于 2021 年达到无条件的 @@M@@O(n\log n)@@ 上界，恰好停在猜想阈值上，而任何非平凡下界始终无从建立。卡点在于比特模型中”搬运数据就是代价”：卷积需要 @@M@@\Theta(\log n)@@ 层变换，每层似乎又必须扫过 @@M@@\Theta(n)@@ 个存储比特，合计天然是 @@M@@\Theta(n\log n)@@。要想严格更快，必须在数据搬运与算术运算两个维度同时省下对数因子中的幂。
主定理：存在一台确定性图灵机 @@M@@A@@，字母表与一维带条数均为固定有限，对每个 @@M@@n\ge 1@@ 和每对 @@M@@n@@ 位输入都输出精确的 @@M@@2n@@ 位乘积，最坏时间为 @@M@@T_A(n)=O(n(\lg n)^{1-\kappa})@@，其中 @@M@@\kappa=2^{-182}@@。指数上的节省极其微小，却是严格的幂节省（power saving），因而反驳了该模型中任何固定乘法机器可能有的 @@M@@\Omega(n\log n)@@ 下界。作者明言构造中的常数与阈值极大，目的是建立比特复杂度（bit complexity）纪录，而非实用算法。同文推论还给出同样时间的精确除法（输出商与余数）与整数平方根，由 Brent 式 Newton 迭代归约到乘法。
起点是 Harvey–van der Hoeven 的高斯重采样（Gaussian resampling）归约：先把乘法化作轴长全为 2 的幂的多维变换，再把最后一维装进多项式环 @@M@@\mathbb C[y]/(y^r+1)@@（@@M@@r@@ 为 2 的幂），使”乘单位根”退化为系数表的带符号移位（Nussbaumer 合成多项式变换）。此后整个变换只剩地址重排、带符号移位与两点蝶形（butterfly）；但逐层全量扫描仍是 @@M@@\Theta(n\log n)@@，节省必须同时来自搬运与算术。
核心新工具是一个固定线性网络：@@M@@W@@ 条线加上各自的暂存线，能把两组标量带符号互换并还原全部辅助值（恢复任意初值的技巧是 Buhrman 等人”透明计算”构造的线性版本）。把数组的行循环分配到 @@M@@W@@ 个角色（role）流，并在源、门、汇处指定可逆线性框架（frame）@@M@@D_v@@；因为公共框架与逐点线性门可交换，中间框架沿路径层层抵消，端点只剩想要的算子——位网络得到地址剪切 @@M@@(H,D)\mapsto(H+D,D)@@，复数网络得到同时作用的蝶形层 @@M@@H_0(u,v)=((u+v)/2,(u-v)/2)@@。框架标注用 @@M@@h=100@@ 元集合的三元子集及其正交子空间实现（Alon 式组合构造）；决定性计数是：每条边的框架变化都能由更小的同类调用实现，而递归调用总数 @@M@@s<Wm@@（@@M@@m=h^3=10^6@@）。于是参数放大 @@M@@m@@ 倍的一次调用只花 @@M@@s@@ 次体积 @@M@@V/W@@ 的小调用，@@M@@s/W<m@@ 这一严格不等式沿递归几何级数放大，得到地址块交换 @@M@@O(Vu^{\tau})@@ 与同时蝶形层 @@M@@O(Vd^{\lambda'})@@，其中 @@M@@\tau=1-2^{-50}@@、@@M@@\lambda'=1-2^{-54}@@ 均固定小于 1。
最后是总装：先用 Agarwal–Cooley 式中国剩余映射把一维循环卷积分到互素素数长度的轴上，实现为三角受控循环移位而非整体排序；高斯重采样恒等式刻意保留源与目标坐标置换，使其在两正一反三次变换中相消、无需单独执行排序；Bluestein 啁啾（chirp）恒等式把中间变换化为循环卷积，相位扭转转入环 @@M@@\mathbb C[y]/(y^r+1)@@，其中的多项式乘法把已知的 @@M@@O(n\log n)@@ 乘法器当普通子程序调用。取工作精度 @@M@@p=6\lceil\log_2 n\rceil@@，逐级舍入误差分析给出最终系数误差 @@M@@448b\,2^{-3b/4}<1/2@@（@@M@@b=\lceil\log_2 n\rceil@@），四舍五入恢复整数系数、传播进位即得精确 @@M@@2n@@ 位输出。代价表七个主导项的指数余量最小为 @@M@@2^{-181}=2\kappa@@，足以吸收零散对数因子，合计 @@M@@O(n(\lg n)^{1-\kappa})@@。
主结果暂无 Lean 形式化证明，OpenAI 官方声明”未经形式化的结果可能有问题”，宜以社区核验为准。本结果族（109）目前仅此一篇手稿：精确除法与平方根是同文推论，直接继承主定理的时间界，族内尚无其他姊妹篇交叉印证。构造常数（@@M@@\kappa=2^{-182}@@、@@M@@h=100@@、生效阈值 @@M@@b\ge 2^{24}@@ 等）刻意保守，论文亦不声称任何优化，属纯复杂性理论结果。
问 1：证明里最关键也最脆弱的一步是什么？
（答：固定线性网络的递归计数。网络的行循环分配到 W 个角色流，源、门、汇处指定可逆线性框架 D_v，公共框架与逐点线性门可交换使中间框架沿路径层层抵消；决定性计数是递归小调用总数 s<Wm（m=h³=10⁶）——参数放大 m 倍只花 s 次体积 V/W 的小调用，s/W<m 这一严格不等式沿递归几何级数放大才有幂节省。任何一处 s≥Wm，节省归零。）
问 2：为什么节省必须”搬运与算术”两头同时发生？
（答：Θ(log n) 层变换、每层扫 Θ(n) 比特，单独省哪头都剩 n log n。故论文配了两台发动机：地址字段互换 O(Vu^τ)（τ=1−2^{−50}）与同时蝶形层 O(Vd^{λ’})（λ’=1−2^{−54}），前者治搬运、后者治算术，缺一即回临界。）
问 3：与 Harvey–van der Hoeven 的 O(n log n) 相比真正的新意是什么？
（答：HvH 恰好停在猜想阈值上；本文在同一固定多带比特模型严格跌破，推翻 SS 1971 最优性猜想。技术新点是”透明计算”的线性版本——中间步是数据的 XOR/线性组合，最终置换对任意初值的辅助线仍精确还原——配上 Alon 式三元子集正交框架标注，把地址操作本身做出幂节省。）
问 4：中间值全是线性组合，怎么保证最终精确？
（答：数值侧用精确高斯二进有理数（实虚部分母为 2 的幂），完整收缩层后只做一次截断；工作精度 p=6⌈log₂n⌉ 下逐级舍入误差收敛到 448b·2^{−3b/4}<1/2，四舍五入恢复整数系数再传进位。地址侧则由”对任意初值精确”的网络性质兜底，例外地址被显式识别后确定性修正。）
问 5：AI 生成证明最可能在哪里出错？
（答：本篇暂无形式化证明。高危点有三：重采样中刻意保留的源/目标坐标置换能否真在两正一反三次变换中相消、无需单独排序；代价表七个主导项的指数余量最小仅 2^{−181}=2κ，散落对数因子稍多就吃穿余量；以及 Bluestein 啁啾与 y^r+1 环上相位扭转的环绕衔接。常数（κ=2^{−182}、阈值 b≥2^{24}）刻意保守是诚实信号。）
问 6：谁会用到它？
（答：直接推论是精确除法与平方根同界（Brent 式 Newton 迭代，几何级数求和由末精度控制）；更重要的是概念层面：n log n 不是比特模型的天然地板，任何依赖”乘法必然 Θ(n log n)”的论证都需要重新审视。实用层面无意义——生效阈值超过宇宙存储能力。）
总评
五十年老猜想的正面击破，纯理论纪录含金量极高；最大风险是无形式化背书且证明横跨网络构造、误差分析与代价表三套账本，任何一本账出差都足以让 κ 归零，急需社区逐项复核。