22次乘法，一次也不能少

利益冲突声明。 作者表示，在他们的指导下，AI智能体——Anthropic公司的Claude——编写了搜索代码以及无需人工审核的那部分Lean证明，而必须由人工审核的部分则由作者本人设计。本文同样由Claude撰写。

按照教科书的方法，将两个n行n列的方形数表——矩阵——相乘，需要n³次乘法。施特拉森（Strassen）证明，两个2 × 2矩阵相乘只需7次乘法，而不是8次。这个技巧可以递归使用：把一个大矩阵切成四块，把每一块当作一个数来处理，再不断重复。于是计算量的增长速度变为n^2.807，而不是n³。据论文介绍，这个2 × 2方案已在1971年被证明是最优的。

同样的思路适用于任何固定尺寸。如果一个方案能用r次乘法完成两个3 × 3矩阵的相乘，并且在矩阵元素是分块时依然成立，那么其计算量的增长速度就是n的log₃ r次方。简单的算术就能说明其中的利害：这样的方案恰好在r不超过21时胜过施特拉森方法，而在22次或更多时则落败。已知最好的3 × 3方案出自拉德曼（Laderman）之手，需要23次乘法，自1976年以来一直没有被改进。

一扇半掩的门

一个问题所能达到的最少乘法次数被称为它的秩（rank）。3 × 3矩阵乘法之秩的下界提升得十分缓慢：2003年为19，2026年3月升至20——这是Wang在一个只有0和1、且1 + 1 = 0的微型数系上计算得出的。2026年9月，Wang与Yang领导的团队在相隔不到十天的时间里各自独立地将下界推进到21。但21依然为一个比施特拉森方法更快的3 × 3方案留有余地。

蒙特利尔理工学院和卡内基梅隆大学的艾萨克·鲁迪奇（Isaac Rudich），以及蒙特利尔理工学院的路易-马丁·卢梭（Louis-Martin Rousseau），如今将这个下界推进到了22。

定理1。 任何使用整数常数、将两个3 × 3矩阵相乘、并且可以递归应用于任意大小分块的算法，至少需要22次乘法。

因此，这类算法的计算量增长不可能优于约n^2.814——也就没有任何一种能胜过施特拉森的2 × 2方法。

496个更小的谜题

这一证明建立在Wang设计的一张表格之上，该表格把这个难题拆分为496个更容易的问题。每个问题都对第一个矩阵附加了一些“条件”——例如，它的某些元素之和为零。条件越多，问题越容易，直至矩阵全为零的平凡情形。

作者首先编写了一个精确搜索程序，在尝试证明之前就告诉他们每个谜题的真实答案。这些答案起到了地图的作用：它们指明了哪些下界值得去追求。最终，他们的证明为全部496个谜题给出了下界，精确解决了其中359个——而Wang最新的结果只解决了195个——并提高了252个谜题的下界。他们自己提出的一条“粘合”定理能把两个较易谜题的方案组合成第三个谜题的方案，提供了其中145个上界。

最终的表述中有两个条件至关重要。整数常数：一个使用整数常数的方案，放到只有0和1的数系中解读时，依然是有效方案，且乘法次数不会增加，因此下界可以迁移过来。分块：如果不要求这一点，就存在捷径。论文引用的罗索夫斯基（Rosowski）3 × 3算法只需21次乘法，但它依赖于数的乘法可交换，因而不能递归使用。

由机器验证的证明

这一证明用Lean写成。Lean是一种编程语言，在其中一条定理只有在每一步都经过验证后才能编译通过。完整的证明长达约一百万行，分布在3,521个模块中，在单个处理器核心上验证需要11.1小时。没有人需要通读全部内容。审核者只需阅读一个约1,000行的库——它由作者在任何证明出现之前写成，定义了什么是乘法方案，并陈述了定理；其余部分由Lean的内核检查，另有一个独立的检查程序可以复现这一结果。

作者还指出，AI智能体检索了相关文献：它们核实了每篇参考文献确实存在，“但没有核实每篇文献是否恰好包含我们归功于它的那个想法”。

最后的缺口

还剩一个问题：是否存在只需22次乘法的3 × 3方案，还是拉德曼的23次才是真正的最小值？作者预计这个缺口“即将被填补”，并将在缺口被填补后、或论文被接受发表后公开他们的搜索代码。这一下界也没有涵盖使用非整数常数的方案。