arxiv: 2603.07280 · v5 · submitted 2026-03-07 · 💻 cs.CC · cs.DS

Recognition: no theorem link

Automated Lower Bounds for Small Matrix Multiplication Complexity over Finite Fields

Chengu Wang

Authors on Pith no claims yet

Pith reviewed 2026-05-15 15:37 UTC · model grok-4.3

classification 💻 cs.CC cs.DS

keywords matrix multiplicationbilinear complexitylower boundsfinite fieldsF23x3 matricesautomated proofsorbit classification

0 comments

The pith

Multiplying two 3x3 matrices over F2 requires at least 20 bilinear multiplications.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces an automated framework to prove lower bounds on the bilinear complexity of matrix multiplication over finite fields. The framework classifies orbits of restricted matrices, then applies dynamic programming and recursive substitutions to search exhaustively for possible algorithms. It uses this method to establish that 3x3 matrix multiplication over the field with two elements needs at least 20 multiplications, improving the prior bound of 19. A reader would care because these bounds constrain the efficiency of algebraic computations and provide verifiable certificates that can be checked in seconds.

Core claim

We prove that the bilinear complexity of multiplying two 3×3 matrices over F2 is at least 20, improving upon the longstanding lower bound of 19. The proof is obtained via an automated framework that systematically combines orbit classification of the restricted first matrix and dynamic programming over these orbits with recursive substitution strategies, and produces efficiently verifiable proof certificates.

What carries the argument

Automated framework that performs orbit classification of the restricted first matrix, dynamic programming over the resulting orbits, and recursive substitution to generate lower-bound certificates.

If this is right

New lower bounds hold for various small matrix formats over finite fields.
The 3x3 case over F2 is settled by a search that runs in 1.5 hours on a laptop and yields a certificate verifiable in seconds.
The same framework produces machine-checkable proofs rather than manual arguments.
Similar exhaustive searches become feasible for other small dimensions and base fields.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The orbit-based classification may reveal structural patterns that apply to tensor rank problems beyond matrix multiplication.
If the new bound is tight, it would confirm that known algorithms for this size are optimal up to constants.
The method could be adapted to prove lower bounds for related bilinear forms such as polynomial multiplication over finite fields.

Load-bearing premise

The orbit classification of the restricted first matrix together with the dynamic programming and recursive substitution rules exhaustively cover all possible bilinear algorithms without missing cases or introducing implementation errors.

What would settle it

Discovery of a bilinear algorithm for 3x3 matrix multiplication over F2 that uses only 19 multiplications would falsify the lower bound of 20.

read the original abstract

We develop an automated framework for proving lower bounds on the bilinear complexity of matrix multiplication over finite fields. Our approach systematically combines orbit classification of the restricted first matrix and dynamic programming over these orbits with recursive substitution strategies, culminating in efficiently verifiable proof certificates. Using this framework, we obtain several new lower bounds for various small matrix formats. Most notably, we prove that the bilinear complexity of multiplying two $3 \times 3$ matrices over $\mathbb{F}_2$ is at least $20$, improving upon the longstanding lower bound of $19$ (Bl\"aser 2003). Our computer search discovers it in $1.5$ hours on a laptop, and the proof certificate can be verified in seconds.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

They raised the lower bound for 3x3 matrix multiplication over F2 from 19 to 20 with an automated orbit-based search that produces quick-to-check certificates.

read the letter

They have raised the lower bound on the bilinear complexity of 3x3 matrix multiplication over F2 from 19 to 20. The method classifies orbits of the restricted first matrix under GL(3,F2), runs dynamic programming over those orbits, and uses recursive substitutions to produce a machine-checkable certificate. The search finished in 1.5 hours on a laptop and the certificate verifies in seconds on ordinary hardware. That combination is the main advance over the manual techniques in Bläser 2003. The framework also yields new bounds for other small formats, showing it is not limited to this single case. The verifiable certificate is a practical strength because it lets anyone confirm the result without re-running the full search, which reduces the usual worry about implementation errors in exhaustive methods. The orbit classification and dynamic programming appear to shrink the space enough to make the computation feasible while still aiming for exhaustiveness. A minor soft spot is that the bound still depends on the orbit enumeration being complete and the substitution rules covering every possible bilinear algorithm without gaps or duplicates. If the classification misses a configuration, the lower bound could be incorrect, though the certificate step is designed to catch errors that occur after the classification. The paper does not appear to rely on any fitted parameters or circular reductions, so the result stands on its own. This work is for people who follow algebraic complexity and concrete matrix multiplication bounds. The new number is a modest but clear improvement, and the automated certificate approach could be reused on other small cases. It deserves a serious referee because the claim is specific, the evidence is computational but independently checkable, and it moves a known result forward.

Referee Report

0 major / 2 minor

Summary. The paper develops an automated framework for lower bounds on bilinear matrix multiplication complexity over finite fields. It combines orbit classification of the restricted first matrix under GL(3,F2), dynamic programming over orbits, and recursive substitution rules to produce machine-checkable certificates. The central result is a proof that the bilinear complexity of 3x3 matrix multiplication over F2 is at least 20, improving the 2003 bound of 19; the search runs in 1.5 hours on a laptop and the certificate verifies in seconds.

Significance. If the result holds, the work provides a concrete, verifiable improvement on a classic open problem in algebraic complexity. The machine-checkable certificate and exhaustive-search design (with independent verification) constitute a genuine methodological advance that could be reused for other small formats. The absence of free parameters or fitted quantities in the lower-bound derivation further strengthens the contribution.

minor comments (2)

[§4] The description of the recursive substitution rules in §4 could be expanded with one additional worked example showing how a single substitution step reduces the search space.
[Table 1] Table 1 lists several new bounds; adding a column for the previous best known lower bound for each format would make the improvements immediately visible.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, including the recognition of the methodological advance via orbit classification, dynamic programming, and machine-checkable certificates, as well as the recommendation to accept. We are pleased that the verifiable improvement to the lower bound for 3x3 matrix multiplication over F2 is viewed as a concrete contribution to algebraic complexity.

Circularity Check

0 steps flagged

Exhaustive computational enumeration yields independent lower bound

full rationale

The paper establishes the lower bound of 20 via an automated exhaustive search that classifies orbits under GL(3,F2), applies dynamic programming over those orbits, and uses recursive substitutions to generate a machine-checkable certificate. No parameter is fitted to the target quantity, no self-citation supplies a load-bearing uniqueness theorem, and the certificate verification step is independent of the search implementation. The derivation chain therefore does not reduce to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The framework rests on the standard definition of bilinear complexity and the group action used for orbit classification; no free parameters or new entities are introduced in the abstract.

axioms (2)

standard math Bilinear complexity is the minimum number of scalar multiplications in a bilinear algorithm for matrix multiplication.
Standard definition invoked implicitly when stating the complexity measure.
domain assumption Orbits under the action of the stabilizer group correctly partition the space of possible restricted matrices.
Central to the classification step described in the abstract.

pith-pipeline@v0.9.0 · 5407 in / 1307 out tokens · 48310 ms · 2026-05-15T15:37:00.621993+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages

[1]

Graph-theoretic algorithms for the alternating trilinear form equivalence prob- lem

Ward Beullens. Graph-theoretic algorithms for the alternating trilinear form equivalence prob- lem. InAnnual International Cryptology Conference, pages 101–126. Springer, 2023

work page 2023
[2]

A 5/2n2-lower bound for the multiplicative complexity ofn×n-matrix mul- tiplication

Markus Bl¨ aser. A 5/2n2-lower bound for the multiplicative complexity ofn×n-matrix mul- tiplication. InProceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 45–50. IEEE, 1999

work page 1999
[3]

Lower bounds for the multiplicative complexity of matrix multiplication

Markus Bl¨ aser. Lower bounds for the multiplicative complexity of matrix multiplication. computational complexity, 8(3):203–226, 1999

work page 1999
[4]

On the complexity of the multiplication of matrices of small formats.Journal of Complexity, 19(1):43–60, 2003

Markus Bl¨ aser. On the complexity of the multiplication of matrices of small formats.Journal of Complexity, 19(1):43–60, 2003

work page 2003
[5]

A lower bound for matrix multiplication.SIAM Journal on Computing, 18(4):759–765, 1989

Nader H Bshouty. A lower bound for matrix multiplication.SIAM Journal on Computing, 18(4):759–765, 1989

work page 1989
[6]

The ge- ometry of rank decompositions of matrix multiplication i: 2×2 matrices.Experimental Math- ematics, 28(3):322–327, 2019

Luca Chiantini, Christian Ikenmeyer, Joseph M Landsberg, and Giorgio Ottaviani. The ge- ometry of rank decompositions of matrix multiplication i: 2×2 matrices.Experimental Math- ematics, 28(3):322–327, 2019

work page 2019
[7]

Take your meds: digital signa- tures from matrix code equivalence

Tung Chou, Ruben Niederhagen, Edoardo Persichetti, Tovohery Hajatiana Randrianarisoa, Krijn Reijnders, Simona Samardjiska, and Monika Trimoska. Take your meds: digital signa- tures from matrix code equivalence. InInternational conference on cryptology in Africa, pages 28–52. Springer, 2023

work page 2023
[8]

On varieties of optimal algorithms for the computation of bilinear mappings i

Hans F de Groote. On varieties of optimal algorithms for the computation of bilinear mappings i. the isotropy group of a bilinear mapping.Theoretical Computer Science, 7(1):1–24, 1978

work page 1978
[9]

Wildness for tensors

Vyacheslav Futorny, Joshua A Grochow, and Vladimir V Sergeichuk. Wildness for tensors. Linear Algebra and its Applications, 566:212–244, 2019

work page 2019
[10]

On the algebraic proof complexity of tensor isomorphism.arXiv preprint arXiv:2305.19320, 2023

Nicola Galesi, Joshua A Grochow, Toniann Pitassi, and Adrian She. On the algebraic proof complexity of tensor isomorphism.arXiv preprint arXiv:2305.19320, 2023

work page arXiv 2023
[11]

On the complexity of isomorphism problems for tensors, groups, and polynomials i: tensor isomorphism-completeness.SIAM Journal on Computing, 52(2):568–617, 2023

Joshua Grochow and Youming Qiao. On the complexity of isomorphism problems for tensors, groups, and polynomials i: tensor isomorphism-completeness.SIAM Journal on Computing, 52(2):568–617, 2023

work page 2023
[12]

On the complexity of isomorphism problems for tensors, groups, and polynomials iv: linear-length reductions and their applications

Joshua A Grochow and Youming Qiao. On the complexity of isomorphism problems for tensors, groups, and polynomials iv: linear-length reductions and their applications. InProceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 766–776, 2025

work page 2025
[13]

On minimizing the number of multiplications necessary for matrix multiplication.SIAM Journal on Applied Mathematics, 20(1):30–36, 1971

John E Hopcroft and Leslie R Kerr. On minimizing the number of multiplications necessary for matrix multiplication.SIAM Journal on Applied Mathematics, 20(1):30–36, 1971. 18

work page 1971
[14]

Faster iso- morphism testing of p-groups of frattini class 2.SIAM Journal on Computing, pages FOCS24– 115, 2025

G´ abor Ivanyos, Euan J Mendoza, Youming Qiao, Xiaorui Sun, and Chuanqi Zhang. Faster iso- morphism testing of p-groups of frattini class 2.SIAM Journal on Computing, pages FOCS24– 115, 2025

work page 2025
[15]

General linear group action on tensors: A candidate for post-quantum cryptography

Zhengfeng Ji, Youming Qiao, Fang Song, and Aaram Yun. General linear group action on tensors: A candidate for post-quantum cryptography. InTheory of cryptography conference, pages 251–281. Springer, 2019

work page 2019
[16]

Faster algorithms for structured matrix multiplication via flip graph search, 2025

Kirill Khoruzhii, Patrick Gelß, and Sebastian Pokutta. Faster algorithms for structured matrix multiplication via flip graph search, 2025

work page 2025
[17]

A noncommutative algorithm for multiplying 3×3 matrices using 23 multiplications.Bulletin of the American Mathematical Society, 82(1):126–128, January 1976

Julian David Laderman. A noncommutative algorithm for multiplying 3×3 matrices using 23 multiplications.Bulletin of the American Mathematical Society, 82(1):126–128, January 1976

work page 1976
[18]

Algorithms for matrix code and alternating trilinear form equivalences via new isomorphism invariants

Anand Kumar Narayanan, Youming Qiao, and Gang Tang. Algorithms for matrix code and alternating trilinear form equivalences via new isomorphism invariants. InAnnual Interna- tional Conference on the Theory and Applications of Cryptographic Techniques, pages 160–187. Springer, 2024

work page 2024
[19]

Faster symmetric matrix multiplication with thunderkittens, 2024

Laker Newhouse, Dakota Goldberg, and Ricardo Ruiz. Faster symmetric matrix multiplication with thunderkittens, 2024

work page 2024
[20]

The bilinear complexity and practical algorithms for matrix multiplication

Alexey V Smirnov. The bilinear complexity and practical algorithms for matrix multiplication. Computational Mathematics and Mathematical Physics, 53(12):1781–1795, 2013

work page 2013
[21]

Contracting symmetric tensors using fewer multipli- cations

Edgar Solomonik and James W Demmel. Contracting symmetric tensors using fewer multipli- cations. 2015

work page 2015
[22]

Gaussian elimination is not optimal.Numerische Mathematik, 13(4):354–356, August 1969

Volker Strassen. Gaussian elimination is not optimal.Numerische Mathematik, 13(4):354–356, August 1969

work page 1969
[23]

Faster isomorphism for p-groups of class 2 and exponent p

Xiaorui Sun. Faster isomorphism for p-groups of class 2 and exponent p. InProceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 433–440, 2023

work page 2023
[24]

Practical post-quantum signature schemes from isomorphism problems of trilinear forms

Gang Tang, Dung Hoang Duong, Antoine Joux, Thomas Plantard, Youming Qiao, and Willy Susilo. Practical post-quantum signature schemes from isomorphism problems of trilinear forms. InAnnual international conference on the theory and applications of cryptographic techniques, pages 582–612. Springer, 2022

work page 2022
[25]

On multiplication of 2×2 matrices.Linear algebra and its applications, 1971

Shmuel Winograd. On multiplication of 2×2 matrices.Linear algebra and its applications, 1971. 19

work page 1971