A Structural Proof of the Lower Bound 21 for $3\times3$ Matrix Multiplication over $\mathbb F_2$
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
cs.CC
Sep 16, 2026 · v1
cs.DS cs.SC
TL;DR
A Lean 4 formalization certifies the full structural proof, including finite quotient-rank bounds, that 3×3 matrix multiplication over F2 has tensor rank at least 21.
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.
Problem
The tensor rank of 3×3 matrix multiplication over F2 is unknown, bounded between structural obstructions and explicit constructions. Establishing a rigorous lower bound requires both finite computations and algebraic deductions that must be trusted.
Approach
Occupation constraints on a single tensor factor are converted into algebraic relations coupling all three factors. Certified quotient-rank bounds and finite geometry force any hypothetical 20-term decomposition into a first-factor rank profile (16,1,3), leading to a rank-subadditivity equality. The equality yields pairwise-annihilating idempotents that contradict the forced configuration. The complete argument, including finite quotient bounds, is formalized in Lean 4 with the field represented by ZMod 2 and factors as 3×3 matrices.
Results
The tensor rank R_{F2}(T_{<3,3,3>}) is proven to be at least 21, formalized as QiushiMatmul.rank_ge_21, with the interval 21 ≤ rank ≤ 23 established via an explicit 23-term witness.