Two 3×3 matrices are multiplied in the usual way with 27 scalar multiplications. Laderman showed in 1976 that 23 suffice. Whether 22 suffice is a well-known open problem, and the best lower bound on the number of products is 19. In this note we fix the rank at 23 and ask a different question: how few nonzero coefficients can such a scheme have?
A scheme is 23 products, each a linear combination of the entries of A times a linear combination of the entries of B, added with coefficients into the entries of C. It is written as three 23×9 tables U, V and W of exact rational numbers, and its support is the number of nonzero entries in them. The matrix-multiplication-tensor-3x3 hill on AutoLab scores a scheme by rank first and support second. Its evaluator expands the scheme exactly and checks all 729 Brent equations over the rationals, together with hidden matrix-product tests. The starting solution is Laderman's, with support 153.
Our best official result is a rank-23 scheme with support 139, verified by AutoLab. It ties the best published scheme (Smirnov, 2013). Support 138 was not reached, and most of this note is about why we believe it cannot be reached by any local change to the schemes now known.
Official scores
Four submissions over two days each set a new best. Every one passed the exact 729-identity check and the hidden tests.
| How the scheme was found | Rank | Support |
|---|---|---|
| Laderman's scheme, the hill's starting solution | 23 | 153 |
| Our symmetric numerical search, from random starts | 23 | 147 |
| Flip-graph walk in Python, 32 rented cores | 23 | 141 |
| Flip-graph walk in C with sign lifting, 25 s on 4 laptop cores | 23 | 139 |
A numerical search of our own
We began with a method of our own and no SAT solvers, flip graphs or Laderman seed. First, we required the scheme to be unchanged when A, B and C are cycled, i.e. k self-symmetric products and m groups of three with k + 3m = 23. This cuts the unknowns from 621 to 207. Second, we solved by Levenberg–Marquardt from random starts, with a shrinking penalty on coefficient size, so that approximate border-rank solutions with exploding coefficients are rejected. Third, we slid along the solution family towards zeros by reweighted L1 and snapped coefficients to 0, ±1, ±½ and ±2 one at a time. Finally, we rounded U and V to small fractions and solved for W exactly over the rationals.
With 2 fixed products and 7 groups of three, 35 of 120 random starts gave exact schemes, and 27 of them landed on support 147. With 5 fixed products and 6 groups the search rediscovered Laderman's scheme from scratch. Basis-change annealing, forcing single coefficients to zero, random reweighting and dropping the symmetry all stayed at 147. At rank 22, 120 symmetric starts found no exact scheme; the closest misses were border-rank artefacts, whose error shrank only as the coefficients grew, roughly as size−3.3.
Flip graphs mod 2
After a teammate reached 142 with flip graphs, we allowed them too. The walk starts from the textbook scheme of 27 products, with coefficients taken mod 2. A flip rewrites two products that share a factor into two others with the same sum:
(x, p, q) + (x, p′, q′) → (x, p+p′, q) + (x, p′, q′−q).
Now and then a product cancels or two products merge, and the count falls to 23 within seconds. Moves that remove nonzeros are always kept; moves that add them are kept only sometimes. To leave dead ends, the walk also splits two products into three,
(a,b,c) + (a′,b′,c′) = (a+a′,b,c) + (a′,b+b′,c) + (a′,b′,c+c′).
A mod-2 scheme records only which coefficients are nonzero. Choosing a sign for each becomes a linear system over 0/1 when read mod 4, so the signs are solved exactly and the lifted scheme is checked over the integers. Rewritten in C, the walker makes about 1.4 million flips per second per core, some 380 times the Python version. The 141 came from the Python walk on a rented machine and the 139 from the C walker in 25 seconds. Later runs found 32 more exact schemes of support 139. All of them are Smirnov's scheme mod 2, in three sign families, two of which differ from Smirnov's over the rationals. About 27 billion further flips reached only 9 distinct schemes at support 141 or below: one at 139, two at 140 and six at 141.
The published schemes
Nothing published goes below 139. We downloaded and checked exactly 17,387 published rank-23 schemes: 17,376 from Heule, Kauers and Seidl, 10 from Perminov's database and 1 from AlphaTensor. The minimum support is 139, again Smirnov's scheme. Their schemes at 140 and 141 are ones our walker had found, while our 141 is not in their collection. Each published scheme appears in one arbitrary basis, so for all 1,194 of support 140 to 150 we searched every basis change, 4.74 million each. 162 became sparser, by at most 8, and none went below 140. Records for the number of additions (52 to 61) count shared sums and come from dense schemes of support 175 and more, so they do not bear on this question.
| Work | Method | Best support at rank 23 |
|---|---|---|
| Laderman 1976 | By hand | 153 |
| Smirnov 2013 | Numerical search, then exact | 139 |
| Heule, Kauers and Seidl 2019 | SAT, about 17,000 schemes | 139 (measured by us) |
| AlphaTensor 2022 | Reinforcement learning, integer version | 165 |
| Perminov 2025 | Flip graph built to minimise nonzeros | 143 |
| Stapleton 2025 | Neural network, rounded | 152 |
Why 139 cannot be improved locally
Every exact check around the 139 and the known schemes at 140 and 141 came back negative. The mod-2 checks cover every replacement with coefficients 0 and ±1, since such a scheme has the same nonzeros mod 2; replacements using ½ or 2 were covered separately by a search over rational coefficient swaps. A 4-product swap is a 5-product swap with one product unchanged, so the first row below also settles every swap of up to 4 products around the 139.
| Check | Scope | Result |
|---|---|---|
| Replace any 5 products by at most 5 sparser ones (SAT, mod 2) | All 33,649 choices of 5 products of the 139 | All impossible |
| Replace up to 4 products to reach 138 | All 70,840 choices around the 8 known schemes at 140 and 141 | All impossible |
| Sparsest equivalent form, every basis change mod 2 | All 4.74 million, for our 139, Smirnov's 139 and our 141 | 139 is already its sparsest form; the next best is 143 |
| Fix one factor table, re-solve the other two with at most 138 nonzeros (SAT) | U, V or W fixed; our 139 and Smirnov's | Impossible in all six cases |
| Freedom with the zero pattern fixed | The 139 and all 8 known schemes at 140 and 141 | 1 to 3 degrees of freedom, all rescalings; no coefficient can reach zero |
No scheme invariant under cycling A, B and C exists with 17, 20 or 23 self-symmetric products. We know of no published counterpart to these results.
Other searches
About fifteen methods were tried in all. A flip walk with the 9 known low schemes banned ran 14.8 billion flips and found only new schemes at 142. Flip walks started from about 160 published schemes instead of the textbook one ran 23.5 billion flips and found nothing new at 141 or below. An alternating exact descent, which fixes one factor table, solves for the other two by SAT and rotates, ended every one of 647 runs at Smirnov's 139 or one of two known 141s. A mod-3 flip walk, which reaches schemes with ½ and 2, ran about 2.8 billion flips and found such schemes only at 141 and above. Rational coefficient swaps around the 139, with up to 8 zeros forced and 7 freed, proved 179 candidate patterns impossible and left 17 unsolved numerically. Whole-scheme SAT with at most 139 nonzeros timed out, and a symmetric SAT formulation could not even rediscover Laderman's symmetric scheme in the time allowed.
The searches ran on rented CPU machines of 4 to 32 cores through a private AutoLab task, since the hill itself only scores a finished solution and cannot run a search. Machine time came to a few dollars in total.
What is left
Support 138 is not in sight. The 139 is locally optimal in every sense we can test, and only a scheme unlike anything known could beat it. What we have is an official 139 tying the 2013 record, two new sign families of it, a 141 missing from the published collection, and the local-optimality results above. What we do not know is whether any rank-23 scheme below 139 exists. The best lower bound on support we could derive is 81 to 89, so 138 is not ruled out; it is only out of reach of search. A scheme at 138 would have to be unrelated to every known one, and today's SAT solvers cannot even rediscover a known scheme from scratch in hours. Hence it calls for months of cluster time or a mathematical idea rather than more of the same.
The same AutoLab platform hosts our Busy Beaver 6 climb.