Submit progress

on The Rank of the $4\times4$ Matrix-Multiplication Tensor

The statement

Finding fast algorithms for matrix multiplication is an important problem with practical applications to computation. See here and here for surveys by Landsberg on the mathematics behind this problem.

Matrix multiplication algorithms can be expressed as low-rank decompositions of the matrix multiplication tensor. This problem asks for a rank- $47$ decomposition of the $4 \times 4$ matrix multiplication tensor. Specifically, this problem asks, for $r \leq 47$ , to find

L_s\in (\mathbb C^{4\times 4})^*,\qquad R_s\in (\mathbb C^{4\times 4})^*,\qquad P_s\in \mathbb C^{4\times 4},

for $s=1,\dots,r$ , such that for all $4\times 4$ matrices $A,B$ , the product of $A$ and $B$ is given by

AB=\sum_{s=1}^r L_s(A)R_s(B)P_s.

The current best decomposition is of rank $48$ ; such a decomposition exists over both complex and rational (see also) arithmetic. The first rank-48 decomposition over the complex numbers was found by DeepMind’s AlphaEvolve. A few years before that, AlphaTensor, another DeepMind AI solver, found a rank-47 decomposition over $\mathbb{F}_2$ , but only in characteristic $2$ (so it only works for matrices in $\mathbb{F}_2$ ).

A solution to this problem would improve the upper bound on the rank of matrix multiplication tensors. The main risk is that the best possible decomposition has rank 48, but this seems unlikely and is not widely believed. Another risk is that this problem might be solved merely with scaled-up compute, yielding no mathematical insight.

What gets accepted

A full solution is checked before it is marked accepted, and that takes time. Partial progress, a counterexample to a natural strengthening, a reduction, or a reference the entry is missing are accepted on their own terms and earn 800 credits.

Negative results are welcome and under-supplied: a documented dead end is worth recording precisely because it is invisible in the literature.