HEXAGONbeta

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

A mix of human-written and AI-generated textHuman understanding: all partsmath.RA — Rings and Algebrascs.CC — Computational Complexitycs.SC — Symbolic Computation

Contributed by Tejasvi Singh Tomar ↗

Version 1 / Nov 12, 2026 / CC BY 4.0

Abstract

The tensor ⟨4,4,4⟩\langle 4,4,4\rangle of 4×44\times4 matrix multiplication has rank at most 47 over F2\mathbb{F}_2, 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 DD if no DD 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\mathbb{F}_2 are locally optimal to depth 18, as is every decomposition equivalent to one of them, so a decomposition of rank 46 over F2\mathbb{F}_2 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\mathbb{F}_2 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.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23721965

References

  1. Agarwal, Abhinav. Certified local rank and uniqueness barriers for a 48-term matrix-multiplication decomposition. 2026. arXiv:2609.13596arXiv
  2. Alexeev, Boris; Forbes, Michael A.; Tsimerman, Jacob. Tensor Rank: Some Lower and Upper Bounds. 2011 IEEE 26th Annual Conference on Computational Complexity (CCC), pp. 283–291. 2011arXivDOI
  3. Arai, Yamato; Ichikawa, Yuma; Hukushima, Koji. Adaptive Flip Graph Algorithm for Matrix Multiplication. Proceedings of the 2024 International Symposium on Symbolic and Algebraic Computation (ISSAC '24), pp. 292–298. 2024arXivDOI
  4. Biere, Armin; Faller, Tobias; Fazekas, Katalin; Fleury, Mathias; Froleyks, Nils; Pollitt, Florian. CaDiCaL 2.0. Computer Aided Verification (CAV 2024), pp. 133–152. 2024DOI
  5. Bläser, Markus. A 52n2\frac{5}{2}n^2-lower bound for the rank of n×nn\times n-matrix multiplication over arbitrary fields. 40th Annual Symposium on Foundations of Computer Science (FOCS '99), pp. 45–50. 1999DOI
  6. Bläser, Markus. On the complexity of the multiplication of matrices of small formats. Journal of Complexity, vol. 19, no. 1, pp. 43–60. 2003DOI
  7. Bläser, Markus. Fast Matrix Multiplication. Theory of Computing Graduate Surveys, vol. 5, pp. 1–60. 2013DOI
  8. Brockett, Roger W.; Dobkin, David. On the Optimal Evaluation of a Set of Bilinear Forms. Linear Algebra and its Applications, vol. 19, no. 3, pp. 207–235. 1978DOI
  9. Bürgisser, Peter; Clausen, Michael; Shokrollahi, M. Amin. Algebraic Complexity Theory. Springer, vol. 315. 1997DOI
  10. Cruz-Filipe, Luís; Heule, Marijn J. H.; Hunt, Warren A.; Kaufmann, Matt; Schneider-Kamp, Peter. Efficient Certified RAT Verification. Automated Deduction – CADE 26, pp. 220–236. 2017DOI
Show all 43 referencesShow fewer references
  1. D'Ambrosio, Ian. The Exact F2\mathbb{F}_2-Rank of 2×32\times 3 by 3×43\times 4 Matrix Multiplication. 2026. Preprint, ZenodoDOI
  2. de Moura, Leonardo; Ullrich, Sebastian. The Lean 4 Theorem Prover and Programming Language. Automated Deduction – CADE 28, pp. 625–635. 2021DOI
  3. Dumas, Jean-Guillaume; Pernet, Clément; Sedoglavic, Alexandre. A non-commutative algorithm for multiplying 4×44\times 4 matrices using 48 non-complex multiplications. 2025. arXiv:2506.13242arXiv
  4. Fawzi, Alhussein; Balog, Matej; Huang, Aja; Hubert, Thomas; Romera-Paredes, Bernardino; Barekatain, Mohammadamin; Novikov, Alexander; Ruiz, Francisco J. R.; Schrittwieser, Julian; Swirszcz, Grzegorz; Silver, David; Hassabis, Demis; Kohli, Pushmeet. Discovering faster matrix multiplication algorithms with reinforcement learning. Nature, vol. 610, no. 7930, pp. 47–53. 2022DOI
  5. Heule, Marijn J. H.; Kauers, Manuel; Seidl, Martina. Local Search for Fast Matrix Multiplication. Theory and Applications of Satisfiability Testing – SAT 2019, pp. 155–163. 2019arXivDOI
  6. Heule, Marijn J. H.; Kauers, Manuel; Seidl, Martina. New ways to multiply 3×33\times 3-matrices. Journal of Symbolic Computation, vol. 104, pp. 899–916. 2021arXivDOI
  7. Hopcroft, J. E.; Kerr, L. R. On Minimizing the Number of Multiplications Necessary for Matrix Multiplication. SIAM Journal on Applied Mathematics, vol. 20, no. 1, pp. 30–36. 1971DOI
  8. Kauers, Manuel. Rank-47 multiplication schemes for 4×44\times 4 matrices over Z2\mathbb{Z}_2. 2022. 99,101 scheme files dated 4 November 2022; accessed 23 October 2026. Web directory, http://www.algebra.uni-linz.ac.at/people/mkauers/matrix-mult/solutions/444/x47/link
  9. Kauers, Manuel. Rank-47 multiplication schemes for 4×44\times 4 matrices over Z2\mathbb{Z}_2, directory \texttt47. 2022. 19 scheme files dated 6 to 29 October 2022; accessed 24 October 2026. Web directory, http://www.algebra.uni-linz.ac.at/people/mkauers/matrix-mult/solutions/444/47/link
  10. Kauers, Manuel; Moosbauer, Jakob. Flip Graphs for Matrix Multiplication. Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation (ISSAC '23), pp. 381–388. 2023arXivDOI
  11. Kauers, Manuel; Wood, Isaac. Exploring the Meta Flip Graph for Matrix Multiplication. 2025. arXiv:2510.19787arXiv
  12. Landsberg, J. M. Tensors: Geometry and Applications. American Mathematical Society, vol. 128. 2012DOI
  13. Landsberg, J. M. Geometry and Complexity Theory. Cambridge University Press. 2017DOI
  14. Landsberg, J. M.; Michałek, Mateusz. Abelian tensors. Journal de Mathématiques Pures et Appliquées, vol. 108, no. 3, pp. 333–371. 2017arXivDOI
  15. Landsberg, J. M.; Ottaviani, Giorgio. Equations for secant varieties of Veronese and other varieties. Annali di Matematica Pura ed Applicata, vol. 192, no. 4, pp. 569–606. 2013arXivDOI
  16. Landsberg, J. M.; Ottaviani, Giorgio. New lower bounds for the border rank of matrix multiplication. Theory of Computing, vol. 11, pp. 285–298. 2015arXivDOI
  17. Lempel, Abraham; Winograd, Shmuel. A New Approach to Error-Correcting Codes. IEEE Transactions on Information Theory, vol. 23, no. 4, pp. 503–508. 1977DOI
  18. Medley, Zeke; Gokul, Anagha; Luu, Quan; Manolios, Panagiotis. GPU-Accelerated Search for Fast Matrix Multiplication over F2\mathbb{F}_2. 2026. arXiv:2609.17533arXiv
  19. Moosbauer, Jakob. \textttflips (GitHub repository). 2022. Repository cited in \citeKauersMoosbauer2023flip; contains \textttsolutions/444-47-mod2.exp. https://github.com/jakobmoosbauer/flipslink
  20. Moosbauer, Jakob. Search Techniques for Matrix Algorithms. 2023link
  21. Moosbauer, Jakob; Poole, Michael. Flip Graphs with Symmetry and New Matrix Multiplication Schemes. Proceedings of the 2025 International Symposium on Symbolic and Algebraic Computation (ISSAC '25), pp. 233–239. 2025arXivDOI
  22. Novikov, Alexander; Vũ, Ngân; Eisenberger, Marvin; Dupont, Emilien; Huang, Po-Sen; Wagner, Adam Zsolt; Shirobokov, Sergey; Kozlovskii, Borislav; Ruiz, Francisco J. R.; Mehrabian, Abbas; Kumar, M. Pawan; See, Abigail; Chaudhuri, Swarat; Holland, George; Davies, Alex; Nowozin, Sebastian; Kohli, Pushmeet; Balog, Matej. AlphaEvolve: A coding agent for scientific and algorithmic discovery. 2025. arXiv:2506.13131arXiv
  23. Pan, V. Ya. Methods of computing values of polynomials. Russian Mathematical Surveys, vol. 21, no. 1, pp. 105–136. 1966DOI
  24. Shpilka, Amir. Lower Bounds for Matrix Product. SIAM Journal on Computing, vol. 32, no. 5, pp. 1185–1200. 2003DOI
  25. Strassen, Volker. Gaussian elimination is not optimal. Numerische Mathematik, vol. 13, no. 4, pp. 354–356. 1969DOI
  26. The mathlib Community. The Lean Mathematical Library. Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP 2020), pp. 367–381. 2020arXivDOI
  27. Tomar, Tejasvi Singh. The rank of 3×33\times 3 matrix multiplication over F2\mathbb{F}_2 is 2323. 2026. arXiv:2610.11823arXiv
  28. Wang, Chengu. Automated Lower Bounds for Bilinear Complexity over Finite Fields. 2026. arXiv:2603.07280arXiv
  29. Wang, Chengu. A Lower Bound of 21 for 3×33\times 3 Matrix Multiplication over F2\mathbb{F}_2. 2026. arXiv:2609.06725arXiv
  30. Wei, Victor K. Generalized Hamming Weights for Linear Codes. IEEE Transactions on Information Theory, vol. 37, no. 5, pp. 1412–1418. 1991DOI
  31. Wetzler, Nathan; Heule, Marijn J. H.; Hunt, Warren A. DRAT-trim: Efficient Checking and Trimming Using Expressive Clausal Proofs. Theory and Applications of Satisfiability Testing – SAT 2014, pp. 422–429. 2014DOI
  32. Yang, Shuxing; others. A Structural Proof of the Lower Bound 21 for 3×33\times 3 Matrix Multiplication over F2\mathbb{F}_2. 2026. arXiv:2609.18722arXiv
  33. Zaru, Nadim F. Exact Symmetry-Stratified Search for Fast Matrix Multiplication over F2\mathbb{F}_2: A Second Inequivalent Rank-47 Scheme for 4×44\times4, Rigidity Theorems, and Large Same-Rank Families at 5×55\times5 and 6×66\times6. 2026. Zenodo, version 1.0.1DOI

Version history

  1. v1 · 25 pagesSubmitted by Tejasvi Singh TomarPublished on Zenodo: https://doi.org/10.5281/zenodo.23721965CurrentNov 12, 2026