Complexity Lower Bounds of Small Matrix Multiplication over Finite Fields via Backtracking and Substitution

This paper presents a novel automated method combining the substitution technique with systematic backtracking and dynamic programming to prove that the bilinear complexity of $3 \times 3$matrix multiplication over$\mathbb{F}_2$ is at least 20, thereby improving the previous lower bound of 19.

The Gist

Imagine you are trying to solve a massive puzzle: multiplying two 3x3 grids of numbers together.

In the world of computers, doing this isn't just about crunching numbers; it's about how many "multiplication steps" you absolutely must take to get the answer. The fewer steps you take, the faster and more efficient your computer is.

For decades, mathematicians have been trying to figure out the minimum number of steps required to multiply two 3x3 grids of numbers, specifically using a special kind of math called "binary arithmetic" (where numbers are only 0 or 1, like a light switch being off or on).

The Old Story

Before this paper, the best anyone knew was that you needed at least 19 steps. This was a famous result from 2003. But nobody could prove if it was possible to do it in 18, or if 19 was the hard floor. It was like knowing you need at least 19 bricks to build a wall, but not being 100% sure you couldn't get away with 18.

The New Discovery

This paper, written by Chengu Wang, proves that you actually need at least 20 steps.

The author didn't just guess; they built a super-smart computer program that acted like a detective, systematically checking every possible way to solve the puzzle to prove that 19 steps simply aren't enough.

How Did They Do It? (The Detective Analogy)

Imagine you are a detective trying to solve a crime (finding the minimum steps). You have a suspect (the matrix multiplication problem), but the suspect is wearing a mask. To catch them, you have to try different ways to unmask them.

The author's method uses three main tricks:

1. The "Symmetry" Trick (Rotating the Room)

Imagine the puzzle is a room with furniture. If you rotate the room 90 degrees, the furniture is in a different spot, but the room is fundamentally the same.

• The Math: The author realized that many different ways of setting up the problem are actually just the same problem turned sideways or flipped over.
• The Analogy: Instead of checking every single chair in the room, the detective says, "I'll only check the unique chairs. If I check this one, I know what happens if I rotate the room." This saved a massive amount of time.

2. The "Squeeze" Trick (Flattening)

Sometimes, you can prove a puzzle is hard by squishing it flat.

• The Math: The author took the 3D puzzle and "flattened" it into a 2D grid. If the 2D version is already too complex to solve quickly, then the 3D version must be even harder.
• The Analogy: Imagine trying to fit a giant beach ball into a small box. If you can't even fit the ball if you squish it flat, you definitely can't fit the round ball. This trick quickly ruled out many easy solutions.

3. The "Backtracking" Search (The Maze Runner)

This is the heavy lifter. The author built a program that walks through a giant maze of possibilities.

• The Strategy: The program starts with the full problem. It asks, "What if I force one of the numbers to be zero?" or "What if I force two numbers to be equal?"
• The Branching: Every time it makes a choice, the path splits.
  • Path A: "If I set this number to zero, does the problem become easier?" (Yes? Great, we found a shortcut, but maybe not the minimum.)
  • Path B: "If I don't set it to zero, can we still solve it in 19 steps?"
• The "Substitution" Magic: The program uses a clever rule: "If a specific part of the math must appear in the solution, let's just assume it's there and see what's left." It's like saying, "Okay, let's assume the thief used a red car. Now, can we solve the rest of the case with only 18 clues?" If the answer is "No, we still need 19 clues," then the red car assumption didn't help us save a step.

The Result: A 1.5-Hour Hunt

The author's program ran on a standard laptop (a MacBook Air).

• It spent 1.5 hours exploring millions of these "what-if" scenarios.
• It found a proof that 19 steps are impossible.
• The proof is a digital document about 32 megabytes big (like a short novel).
• A separate, simpler program checked the proof in 10 seconds to make sure the author didn't make a mistake.

Why Does This Matter?

You might ask, "Who cares about 3x3 grids?"

1. It's a Fundamental Limit: Just like knowing the speed of light is a limit for physics, knowing the limit of matrix multiplication tells us the absolute fastest a computer can ever be for certain tasks.
2. AI and Big Data: Modern Artificial Intelligence (like the one you are talking to right now) relies heavily on multiplying huge grids of numbers. While AI uses much bigger grids, understanding the rules for small grids (like 3x3) helps mathematicians build better theories for the big ones.
3. The "19 vs 20" Gap: For 20 years, the math world was stuck at 19. Breaking that barrier shows that our tools for understanding complexity are getting much sharper.

In a Nutshell

The author built a digital detective that systematically tried every possible way to solve a 3x3 math puzzle. By using clever shortcuts (symmetry) and a deep search (backtracking), it proved that the puzzle is harder than we thought: you need 20 steps, not 19. It's a small number, but in the world of computer science, proving a limit like this is a huge victory.

Technical Summary

Here is a detailed technical summary of the paper "Complexity Lower Bounds of Small Matrix Multiplication over Finite Fields via Backtracking and Substitution" by Chengu Wang.

1. Problem Statement

The paper addresses the fundamental problem of determining the bilinear complexity (tensor rank) of matrix multiplication over finite fields, specifically $\mathbb{F}_2$.

• Context: The bilinear complexity of multiplying an $l \times m$ matrix by an $m \times n$ matrix, denoted as $R(\langle l, m, n \rangle)$, is the minimum number of scalar multiplications required by any bilinear algorithm.
• The Gap: While upper bounds (algorithms) are well-studied (e.g., Strassen's algorithm), proving tight lower bounds is notoriously difficult.
• Specific Target: The paper focuses on the case of multiplying two $3 \times 3$matrices over$\mathbb{F}_2$. The previous best lower bound was 19 (established by Bläser in 2003). The goal is to determine if the rank is actually higher.

2. Methodology

The authors propose a novel automated framework that combines substitution, backtracking, and symmetry enumeration to prove lower bounds. The approach is structured as follows:

A. Symmetry and Orbit Enumeration

Matrix multiplication tensors possess inherent symmetries (sandwich, cyclic, and transpose symmetries).

• The method restricts the first matrix $A$ in the product $AB = C^T$ using linear constraints (e.g., setting specific entries to 0 or equating entries).
• Instead of checking every possible restriction, the algorithm enumerates orbits of restrictions under the symmetry group.
• Algorithm 1 is used to generate canonical representatives for these orbits using Reduced Row Echelon Form (RREF) and lexicographical ordering, drastically reducing the search space (e.g., finding 496 orbits for $\langle 3, 3, 3 \rangle$).

B. Four Core Lower Bound Techniques

For each orbit (restricted tensor), the algorithm attempts to prove a rank lower bound using four techniques, applied hierarchically:

1. Flattening: The tensor is flattened into a matrix (e.g., combining dimensions $A$ and $B$). The rank of this matrix provides a trivial lower bound for the tensor rank.
2. Forced Product (Substitution): Based on Lemma 2 from Hopcroft and Kerr. If a subset of terms in the tensor can be expressed as independent single products, the algorithm assumes these terms must exist in any decomposition. It then enumerates the presence/absence of remaining terms to find the minimum rank of the residual tensor.
3. Degenerate Reduction: If a restriction set $X$ is a subset of restriction set $Y$, the rank of the tensor under $X$ is at least the rank under $Y$ plus the number of added constraints.
4. Backtracking (The Core Innovation):
   • If the above techniques fail to reach the target bound, the algorithm performs a systematic backtracking search.
   • It enumerates "canonical factors" (linear combinations of entries in $A$) that could appear in a decomposition.
   • It sets these factors to zero, reducing the problem to a previously solved orbit with a known lower bound.
   • Algorithm 3 manages this recursion: $R(T) \ge R(T|_{factor=0}) + k$, where $k$ is the number of factors set to zero.

C. Optimization Strategies

To make the search feasible for $3 \times 3$ matrices, the authors implemented several optimizations:

• Multi-threading: Parallelizing the processing of orbits with the same number of restrictions.
• Restriction Map: Using a hash map to cache symmetry transformations, reducing the complexity of orbit lookup from $O(|P| \cdot |Q|)$ to roughly $O(\sqrt{|P| \cdot |Q|})$.
• Local Caching & Memory Management: Storing local lower bounds for sub-problems in each thread, with random eviction policies to prevent Out-Of-Memory (OOM) errors.
• Incremental Target: The algorithm attempts to prove the bound $LB_{known} + 1$, iterating until the target is reached.

3. Key Contributions

1. New Methodology: Introduction of a systematic backtracking search combined with substitution and symmetry reduction to prove tensor rank lower bounds. This moves beyond manual proofs to automated, exhaustive search.
2. Proof Automation: The framework generates machine-verifiable proofs. The search process is distinct from the verification process, allowing for independent auditing of the results.
3. Resolution of Open Problems:
   • Proved $R(\langle 3, 3, 3 \rangle) \ge 20$ over $\mathbb{F}_2$.
   • Completed the formal proof for $R(\langle 2, 3, 4 \rangle) \ge 19$ over $\mathbb{F}_2$ (previously mentioned by Hopcroft and Kerr but lacking a formal proof).
4. Comprehensive Bounds: Reproduced and verified lower bounds for various matrix shapes ($2 \times 2 \times 2$through$3 \times 3 \times 3$), providing a unified table of results.

4. Results

The paper presents the following definitive results over $\mathbb{F}_2$:

Matrix Shape	Previous Lower Bound	New Lower Bound	Upper Bound
$\langle 2, 2, 2 \rangle$	7	7	7
$\langle 2, 3, 3 \rangle$	15	15	15
$\langle 2, 3, 4 \rangle$	18 (or 19?)	19	20
$\langle 3, 3, 3 \rangle$	19	20	23

• Performance: The proof for $R(\langle 3, 3, 3 \rangle) \ge 20$ was found in 71 minutes on a MacBook Air M4 (8 cores, 16GB RAM).
• Verification: The resulting proof file is ~32 MiB and can be verified in 10 seconds.
• Proof Size: The proof for $\langle 2, 3, 4 \rangle$ is under 100 KiB, though verification took longer (110 mins) due to the specific structure of that proof.

5. Significance

• Breaking a 20-Year Record: The result $R(\langle 3, 3, 3 \rangle) \ge 20$ improves upon Bläser's 2003 lower bound of 19, a result that had stood for over two decades.
• Methodological Shift: This work demonstrates that complex algebraic complexity lower bounds can be tackled via computer-assisted exhaustive search rather than purely theoretical derivation. The combination of symmetry reduction and backtracking offers a scalable path for future research.
• Implications for Fast Matrix Multiplication: Since the rank of $3 \times 3$matrices is a building block for larger matrix multiplication algorithms, a higher lower bound suggests that the current best algorithms (like Strassen's or those based on$3 \times 3$ blocks) are closer to optimal than previously thought, or that new, fundamentally different approaches are needed to improve the exponent of matrix multiplication.
• Reproducibility: The authors provide the code and proof files on GitHub, setting a standard for transparency in computational complexity proofs.

In summary, this paper successfully leverages modern computational power and algorithmic optimization to settle a long-standing open problem in algebraic complexity theory, proving that multiplying $3 \times 3$matrices over$\mathbb{F}_2$ requires at least 20 scalar multiplications.