🔢 mathematics

Substitution and quotient of the isotropy group action

This paper introduces a method to fix partial solutions of Brent equations in a way that avoids redundancy from isotropy group actions, thereby generating nontrivial parameterized solution sets that yield infinitely many inequivalent rational-coefficient algorithms for 48 multiplications.

Original authors: Xin Li, Yu Wang, Shenglong Hu

Published 2026-07-17

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Xin Li, Yu Wang, Shenglong Hu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive, interlocking puzzle where the pieces are numbers and the goal is to multiply huge grids of numbers (matrices) as quickly as possible. For decades, mathematicians have been hunting for the most efficient way to do this, looking for "shortcuts" that use fewer multiplication steps than the standard method. These shortcuts aren't just about saving time; they are the secret engines behind everything from video game graphics to artificial intelligence. The rules of this puzzle are written in a complex language of equations known as "Brent equations." Think of these equations as a map to a treasure island of super-fast algorithms. However, there's a catch: the map is covered in a fog of symmetry. If you find one treasure, the fog hides thousands of others that look different but are actually just the same treasure rotated, flipped, or stretched. These "fake" differences are caused by what mathematicians call an "isotropy group action"—a fancy way of saying the puzzle pieces can be shuffled around in specific ways without changing the fundamental solution.

The big question has been: How do you find truly new treasures, rather than just finding the same one again in a different outfit? Usually, when mathematicians try to zoom in on a specific part of the map to find more solutions, they get stuck. They either find a single, isolated point (a dead end) or they find a whole path of solutions that are all just the same "rotated" version of the original. It's like trying to explore a forest by walking in circles; you might walk a long way, but you never leave the same clearing. This paper, by Xin Li, Yu Wang, and Shenglong Hu, introduces a clever new compass to break this cycle. They developed a method to "fix" certain parts of the puzzle in just the right way so that when you look for new solutions, you are guaranteed to step out of the fog and find paths that lead to genuinely different, unique algorithms.

The authors' main discovery is a mathematical technique that acts like a filter for these symmetries. They realized that the "fog" of symmetry has a specific shape and direction, which they can calculate using something called a "tangent basis matrix" (think of it as a compass needle pointing in the direction of the symmetry). By comparing this compass to the "nullspace" (the directions where the puzzle allows movement), they found a rule for choosing which pieces of the puzzle to lock down. If you lock down the right pieces, the remaining free pieces don't just wiggle along the same old symmetry path; they branch out into entirely new territories.

Using this method, the team tested their theory on some of the most famous and difficult matrix multiplication puzzles known to science. They started with a known solution for multiplying 4x4 matrices using 48 steps, a solution found by Dumas, Pernet, and Sedoglavic. By applying their "symmetry-breaking" filter, they didn't just find one new answer; they unlocked an infinite family of solutions. They proved that within this new family, there are infinitely many algorithms that are mathematically distinct and cannot be turned into one another by simple rotations or shuffles. They also applied this to solutions for 3x3 matrices (using 23 steps) and 4x4 matrices (using 49 steps), finding that in each case, they could generate parameterized sets of solutions—essentially infinite lists of new, unique algorithms—where previously, researchers might have only found isolated points or repetitive loops.

The paper doesn't claim to have solved the ultimate mystery of matrix multiplication for all sizes, nor does it say every single solution is now found. Instead, it offers a powerful new tool: a way to ensure that when you search for new solutions, you aren't just walking in circles. It turns the search from a game of "find the same thing again" into a genuine exploration of new mathematical landscapes, revealing that for certain problems, there are infinitely many unique ways to multiply matrices efficiently, waiting to be discovered if only we know how to look past the symmetry.

Technical Summary: Substitution and Quotient of the Isotropy Group Action

Problem Statement
The paper addresses the challenge of discovering new, nontrivial parameterized solution sets for the Brent equations, which govern algorithms for matrix multiplication. Specifically, the authors focus on the system $B(m, n, p|r)$ , whose solution set $V(m, n, p|r)$ describes tensor decompositions of the matrix multiplication tensor $\langle m, n, p \rangle$ with rank $r$ .

A primary obstacle in exploring these solution sets is the presence of a positive-dimensional isotropy group action $I(m, n, p|r)$ . This group consists of four components: the de Groote (sandwiching) action, layer scaling, permutation of rank-one summands, and $S_3$ -symmetry. Because the solution set is invariant under this group, standard methods of fixing partial solutions and performing substitution often yield reduced systems where the resulting parameterized solutions belong to the same isotropy group orbit as the original solution. Consequently, these "new" solutions are merely symmetry copies of known ones, failing to provide genuinely distinct algorithms. The authors aim to develop a method to fix partial solutions such that the resulting parameterized set intersects distinct isotropy group orbits, thereby generating infinitely many inequivalent algorithms.

Methodology
The proposed methodology integrates tools from Lie group theory with numerical algebraic geometry. The core approach involves analyzing the relationship between the nullspace of the Jacobian matrix and the tangent space of the group orbits.

Geometric Framework: The authors model the solution set $V(m, n, p|r)$ as a manifold foliated by the orbits of the isotropy group $I(m, n, p|r)$ . Fixing a partial solution corresponds to intersecting this manifold with an affine coordinate linear space $L_I$ .
Tangent and Nullspace Basis Matrices:
- Nullspace Basis Matrix ( $N(s)$ ): Derived from the Jacobian matrix $J(s)$ of the Brent equations at a smooth solution $s$ . Its rank $d$ represents the local dimension of the solution set.
- Tangent Basis Matrix ( $T(s)$ ): Constructed using the infinitesimal generators of the Lie group action (specifically the de Groote and layer scaling groups). Its rank $d_T$ represents the dimension of the group orbit passing through $s$ .
Selection Criterion: The authors propose a first-order criterion to select a subset of variables $I$ $I$ to fix. They search for an index set $I$ $I$ such that:
$\text{rank } N(s) - \text{rank } N_I(s) > \text{rank } T(s) - \text{rank } T_I(s)$
where $N_I(s)$ $N_{I} (s)$ and $T_I(s)$ $T_{I} (s)$ are submatrices restricted to rows indexed by $I$ $I$ .
- If the inequality holds strictly, the reduced system possesses linear directions at $s$ that are not tangent to the group orbit. This implies the reduced solution set intersects infinitely many distinct group orbits.
- If the ranks are equal, the reduced system likely remains within a single orbit (or a finite union of orbits), yielding no new inequivalent solutions.
Implementation: The method is implemented in Julia. The process involves:
- Verifying the smoothness of a known solution via deflation sequences.
- Computing $J(s)$ , $N(s)$ , and $T(s)$ .
- Searching for index sets $I$ satisfying the rank gap condition.
- Solving the resulting reduced polynomial system (often using Gröbner bases via Oscar.jl) to obtain parameterized curves or higher-dimensional sets.

Key Contributions

Theoretical Criterion: The paper establishes a rigorous first-order criterion (Equation 3.10) based on the difference between the codimension of the fixed variables in the nullspace versus the tangent space. This criterion guarantees that the substitution process yields solutions in different isotropy group orbits.
Explicit Construction: The authors provide explicit formulas for computing the tangent basis matrix $T(s)$ for Brent equations, accounting for the specific structure of the de Groote and layer scaling actions.
Algorithmic Framework: A practical, step-by-step procedure is outlined for transforming known solutions into families of inequivalent solutions, overcoming the "isolated solution" or "same orbit" pitfalls of previous substitution attempts.

Results
The authors applied their method to several known solutions of the Brent equations:

$V(4, 4, 4|48)$ (Dumas, Pernet, and Sedoglavic's Solution):
- The solution has a local dimension of 151, while the orbit dimension is 141.
- By fixing 2082 variables, the authors reduced the system to 222 variables.
- The resulting solution set is a one-dimensional curve containing infinitely many points belonging to distinct $I(4, 4, 4|48)$ -orbits. This provides infinitely many inequivalent algorithms for $4 \times 4$ matrix multiplication using 48 multiplications with rational coefficients.
- Larger rank gaps were also found, allowing for higher-dimensional parameterized sets.
$V(4, 4, 4|49)$ (AlphaTensor's Solution):
- The solution has a local dimension of 197 and an orbit dimension of 143.
- Fixing 2344 variables reduced the system to 8 variables, yielding a one-dimensional parameterized curve of inequivalent solutions.
- Fixing 2269 variables resulted in a reduced system with 83 variables and a 9-dimensional solution set, demonstrating the ability to generate high-dimensional families of new algorithms.
$V(3, 3, 3|23)$ (Laderman's Solution):
- The solution has a local dimension of 76 and an orbit dimension of 70.
- Fixing 613 variables reduced the system to 8 variables, producing a one-dimensional curve of inequivalent solutions.
- Fixing 574 variables yielded a 6-dimensional parameterized solution set.

Significance
The paper claims that this method successfully overcomes the limitations of previous substitution techniques, which often failed to distinguish between symmetry-equivalent solutions and genuinely new algorithms. By utilizing the tangent basis matrix to identify "transverse" directions relative to the group action, the authors can systematically extract nontrivial parameterized families from known solutions.

The primary significance lies in the ability to generate infinitely many inequivalent algorithms for matrix multiplication from a single known solution. For instance, the parameterization of the rational solution for $4 \times 4$ matrix multiplication with 48 multiplications demonstrates that there is not just one such algorithm, but an infinite family of them with rational coefficients. This expands the known landscape of matrix multiplication algorithms and provides a systematic tool for exploring the geometry of the Brent equations. The authors note that while the method relies on the assumption of transverse intersection, numerical experiments confirm its effectiveness for smooth solutions in the tested cases.

More like this