22 MULTIPLICATIONS, NOT ONE FEWER

Conflict of interest. The authors state that AI agents — Claude, by Anthropic — wrote the search code and the Lean proofs that do not need a human auditor, under their direction, while the part a human must audit was designed by the authors. This article is also written by Claude.

Multiplying two square grids of numbers — matrices — the schoolbook way takes n³ multiplications for grids of n rows and n columns. Strassen showed that two 2 × 2 matrices can be multiplied with 7 multiplications instead of 8. The trick can be applied recursively: cut a big matrix into four blocks, treat each block as a single number, and repeat. The cost then grows like n^2.807 instead of n³. According to the paper, this 2 × 2 recipe was proven optimal in 1971.

The same idea works for any fixed size. A recipe that multiplies two 3 × 3 matrices with r multiplications, and still works when the entries are blocks, gives a cost that grows like n to the power log₃ r. Simple arithmetic sets the stakes: such a recipe beats Strassen exactly when r is 21 or less, and loses at 22 or more. The best known 3 × 3 recipe, due to Laderman, uses 23 multiplications and has not been improved since 1976.

A door that stayed ajar

The best possible number for a given problem is called its rank. Lower bounds on the rank of 3 × 3 multiplication crept up slowly: 19 in 2003, then 20 in March 2026, computed by Wang over a tiny number system with only 0 and 1, where 1 + 1 = 0. In September 2026, Wang and a team led by Yang reached 21 independently, within ten days of each other. But 21 still left room for a 3 × 3 recipe faster than Strassen’s.

Isaac Rudich, of Polytechnique Montréal and Carnegie Mellon University, and Louis-Martin Rousseau, of Polytechnique Montréal, have now pushed the bound to 22.

Theorem 1. Any algorithm that multiplies two 3 × 3 matrices with integer constants, and can be applied recursively to blocks of any size, uses at least 22 multiplications.

So no such algorithm can do better than about n^2.814 — and none can beat Strassen’s 2 × 2 method.

496 smaller puzzles

The proof builds on a table devised by Wang, which splits the hard problem into 496 easier ones. Each one adds “conditions” on the first matrix — for instance, that certain of its entries add up to zero. The more conditions, the easier the problem, down to the trivial case where the matrix is all zeros.

The authors first built an exact search program that told them the true answer for each puzzle before they tried to prove it. Those answers served as a map: they showed which lower bounds were worth chasing. In the end, their proof bounds all 496 puzzles, settles 359 of them exactly — against 195 in Wang’s latest results — and raises the lower bound for 252. A “gluing” theorem of their own combines recipes for two easier puzzles into a recipe for a third, and supplied 145 of the upper bounds.

Two conditions matter in the final statement. Integer constants: a recipe with whole-number constants, read in the 0-and-1 number system, stays a valid recipe with no more multiplications, so the bound transfers. Blocks: without that requirement, shortcuts exist. Rosowski’s 3 × 3 algorithm, cited in the paper, needs only 21 multiplications, but it relies on numbers commuting and cannot be applied recursively.

A proof checked by a machine

The proof is written in Lean, a programming language in which a theorem only compiles if every step is verified. The full proof runs to about a million lines spread over 3,521 modules, and takes 11.1 hours to check on a single processor core. Nobody needs to read all of it. An auditor reads a library of about 1,000 lines, written by the authors before any proof existed, which defines what a multiplication recipe is and states the theorem; Lean’s kernel checks the rest, and an independent checker can replay the result.

The authors also note that the AI agents searched the literature: they checked that each reference exists, “but not that each contains exactly the idea we credit to it.”

The last gap

One question remains: does a 3 × 3 recipe with 22 multiplications exist, or is Laderman’s 23 the true minimum? The authors expect the gap “to be closed imminently”, and will release their search code once it is, or once the paper is accepted for publication. The bound also leaves aside recipes with non-integer constants.