Matrix multiplication over fields needs at least 21 terms
A Structural Proof of the Lower Bound 21 for $3\times3$ Matrix Multiplication over $\mathbb F_2$
Computational ComplexityData Structures and AlgorithmsSymbolic Computation
Summary
Multiplying two 3x3 matrices over a simple math system called F2 requires at least 21 basic multiplication steps. The authors prove this by examining how different parts of the multiplication process fit together and using rules from algebra and geometry. They show that trying to do it with only 20 steps leads to logical contradictions. This proves a lower limit on how efficiently this matrix multiplication can be done.
What this means in practice
- •For algorithm designers: Avoid attempting matrix multiplication algorithms over F2 with fewer than 21 multiplication steps for 3x3 matrices, as proven impossible.
- •For cryptography engineers: Use the lower bound on multiplication complexity over F2 to better understand efficiency limits in cryptographic primitives relying on small field arithmetic.
A theory result. No direct application yet.
Authors
Shuxing Yang, Rui Zhao, Junyao Wu, Yize Wang, Wenhao Li, Fujia Chen, Taowen Deng, Shenzhan Hong, Yaqi Li, Zichen Li, Jincheng Mi, Yuang Pan, Kaihao Zhu, Junjie Yang, Hongsheng Chen, Yihao Yang
Abstract
We prove that the tensor rank of $3\times3$ matrix multiplication over $\mathbb F_2$ is at least $21$. The structural proof, independently developed by Qiushi Engine, converts occupation constraints on a single tensor factor into algebraic relations coupling all three factors. Certified quotient-rank bounds and finite geometry force any hypothetical $20$-term decomposition to have first-factor matrix-rank profile $(16,1,3)$. The ranks of the corresponding split-flattened summands therefore sum to $27$, exactly the rank of the full split flattening. Equality in rank subadditivity forces their images to form a direct sum; normalization by the inverse flattening then makes the summands pairwise annihilating idempotents. An explicit product identity for matrix multiplication implies that at most one first factor can be invertible, contradicting the three forced by the profile. The same obstruction constrains $22$-term decompositions attaining the split-rank bound. The complete proof, including the finite quotient bounds, is formalized in Lean. The accompanying research trajectory records Qiushi Engine's long-horizon autonomous research, from numerical experiments and quotient constructions to the structural proof.