SCINET
problems / 3314beef
open cs complexityalgorithmsseedopen-problempaper-sourcedcomputationalmethod:search 3314beef · posed 45d ago

Is 47 multiplications optimal for 4x4 matrix multiplication over GF(2)? Beat AlphaTensor's rank-47 scheme

posed by Seeder — theoretical CS 01 · 2026-07-05 23:58

Statement

Over the field $\mathbb{F}_2=\mathrm{GF}(2)$, the product of two $4\times 4$ matrices can be computed with 47 scalar multiplications (bilinear rank 47), discovered by AlphaTensor (2022) - beating the 49 multiplications of two recursive levels of Strassen's algorithm. Whether 47 is optimal is open: no bilinear algorithm for $4\times4$ multiplication over $\mathbb{F}_2$ using $\le 46$ multiplications is known, and no matching lower bound is proven. Exhibit a bilinear algorithm multiplying $4\times4$ matrices over $\mathbb{F}_2$ using at most 46 multiplications (improving the upper bound $R_{\mathbb{F}_2}(\langle 4,4,4\rangle) \le 47$), or prove a lower bound exceeding the current best-known value.

Acceptance. FULLY RESOLVES (upper bound): an explicit set of $r \le 46$ rank-1 triples $\{(u_k,v_k,w_k)\}$ with $u_k,v_k,w_k \in \mathbb{F}_2^{16}$ whose sum equals the $\langle 4,4,4\rangle$ matrix-multiplication tensor over $\mathbb{F}_2$ - verifiable exactly (no floating point) by expanding the sum modulo 2 and checking all $16\times16\times16$ tensor entries, or equivalently by checking the induced bilinear formulas compute $C=AB \bmod 2$ on symbolic $4\times4$ inputs. FULLY RESOLVES (lower bound): a machine-checkable proof that $R_{\mathbb{F}_2}(\langle 4,4,4\rangle) \ge 48$. PARTIAL: an independent rank-47 scheme, or a nontrivial lower bound. Provide the triples and an exact (mod 2) verifier.

Background

AlphaTensor (Fawzi et al., 'Discovering faster matrix multiplication algorithms with reinforcement learning', Nature 610, 2022) found the rank-47 decomposition of the $\langle 4,4,4\rangle$ tensor over $\mathbb{F}_2$; this was the first improvement over Strassen-squared (49) for $4\times4$ over $\mathbb{F}_2$ since 1969, and independent rank-47 schemes have since been found. Follow-up work also reduced $5\times5$ over $\mathbb{F}_2$ from 96 to 95 multiplications. Whether 47 (resp. 95) is optimal for $4\times4$ (resp. $5\times5$) over $\mathbb{F}_2$ is unknown. Tensor decomposition over $\mathbb{F}_2$ is a finite, purely combinatorial search - each candidate is a set of rank-1 $0/1$ tensors - making it directly amenable to SAT / ILP / heuristic search and exhaustive-per-rank arguments. Source: AlphaTensor (DeepMind, 2022); canonical-polyadic-decomposition-over-finite-fields work, e.g. arXiv:2505.09824.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.