TejasviTomar
October 2026 · Preprint

Local optimality of rank-47 schemes for 4×4 matrix multiplication over F2

Tejasvi Singh Tomar

In plain words

Some shortcuts for multiplying two 4×4 tables can be reused on larger tables split into a 4×4 grid of blocks. When the entries are bits, with one plus one counting as zero, the record for such shortcuts is 47 multiplications. Fawzi and colleagues set it using machine learning and reported it in Nature in 2022. Later searches found more with 47 but none with 46, and it remains unknown whether a reusable shortcut with 46 exists. This paper studies five essentially different shortcuts with 47, including the one from 2022 and a new one the author found. For each of the five, the paper proves that no group of up to 18 multiplications can be swapped for a smaller group of the same kind with the same combined effect.

Abstract

The tensor ⟨4,4,4⟩ of 4×4 matrix multiplication has rank at most 47 over F2, and as it is not known whether 47 is optimal, we ask how far the known decompositions of rank 47 are from one of rank 46. A decomposition is locally optimal to depth D if no D or fewer of its rank-one terms can be replaced by fewer rank-one terms. We prove that five pairwise inequivalent decompositions of rank 47 over F2 are locally optimal to depth 18, as is every decomposition equivalent to one of them, so a decomposition of rank 46 over F2 shares at most 28 terms with any decomposition in these five classes. The five classes include the scheme of Fawzi et al. and every public decomposition of rank 47 over F2 known to us; one of them, found in our flip-graph searches, is new. The proof rests on a peeling lemma and, for four sets of terms that resist the other bounds, on a refinement of the substitution method, which we call substitution over subspaces with lifting. Local optimality to depth 18 is also proved in Lean 4.

Forty-seven white cards in rows of six, each with three 4-by-4 grids of small squares in teal, magenta and yellow showing the matrix entries used by one product of a 47-multiplication scheme for 4-by-4 matrices; eighteen of the cards have heavy black frames.
Of the five rank-47 decompositions in the paper, only C4 is new. This illustration shows C4 as 47 cards, one for each product it uses to multiply 4×4 matrices A and B over F₂. On each card, the teal grid marks the entries of A that are added up, the magenta grid marks those of B, and the yellow grid marks the entries of C = AB to which the product of the two sums is added. Section 6.2 of the paper proves that the combined contribution to C of the 18 products on the cards with heavy frames cannot be computed with fewer than 18 such products.