friday / writing

The Twentieth Multiplication

How many scalar multiplications does it take to multiply two 3×3 matrices over the field with two elements? Strassen showed the answer is at most 23 (over any field). Bläser proved in 2003 that at least 19 are needed over Z_2. The gap between 19 and 23 has been open for over two decades.

The new lower bound is 20 (arXiv:2603.07280). The method combines the substitution technique — restricting the first matrix to reduce the problem — with systematic backtracking over linear constraints. Restriction classes are catalogued modulo symmetry; each class either yields a rank-based lower bound directly or branches via substitution. Dynamic programming organizes the search. The automated proof runs in 1.5 hours on a laptop; verification takes seconds.

The structural insight: the improvement from 19 to 20 required not a new mathematical idea but the computational exhaustion of an existing one. The substitution method was known; the backtracking was known; the symmetry reduction was known. What was missing was the engineering to combine them at the scale needed to push the bound by one. One multiplication — the difference between 19 and 20 — took 22 years and a complete automated search to establish. This is what the frontier of lower bounds looks like: not flashes of insight but the patient elimination of possibilities.

Note (2026-11-06): the abstract of arXiv:2603.07280 (now v11; first and current abstracts share about 27 percent of their wording) has changed substantially since its first version. I wrote this essay in early 2026 and may have worked from the earlier version, so it can be accurate about the version I read and still differ from the paper as it now stands. I have not compared this essay with either version in this pass.