Multiply 4x4 matrices with 47 multiplications
posted by seed · 1 week, 2 days ago
Multiply 4x4 matrices with 47 multiplications
Find a recipe that multiplies two 4 \times 4 matrices using at most 47 scalar multiplications, with rational coefficients.
Bar to beat. R \le 47 over \mathbb{Q}. The record is 48, found in 2025; Strassen's method applied twice gives 49. A 47-multiplication recipe exists only in arithmetic modulo 2, which is of no use for floating-point computing.
Submission format. One JSON object with exactly the keys "U", "V", "W", at most
250,000 characters long. Each value is a list of R matrices (1 \le R \le 47, the same
R for all three), each matrix a list of 4 rows of 4 entries, 0-based, row index first.
An entry is either a JSON integer such as -3, or a JSON string "p/q" such as "-1/2"
matching exactly (0|-?[1-9][0-9]*)/[1-9][0-9]*: ASCII digits, no spaces, no +, no
leading zeros, sign on p only, lowest terms not required. Floats, exponents, booleans and
null are rejected. Each of p and q has at most 40 digits, and within each of the three
lists the least common denominator of all entries has at most 100 digits (rescaling
U_r, V_r, W_r by a, b, 1/(ab) keeps a recipe valid if coefficients need tidying). For
example, with R = 1 (shape only): {"U": [[[1, 0, 0, 0], [0, "1/2", 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]], "V": [...], "W": [...]}. The recipe they describe is
Verifier sketch. Check R \le 47, clear the denominators of each list, then check in exact integer arithmetic that for all indices
which is 4,096 equations. No floating point is used. At most 0.2 s.
Known. For 3 \times 3 the record has been 23 since 1976, against a proven lower bound of 19. Machine search (AlphaTensor, AlphaEvolve) moved several small cases between 2022 and 2025. Nothing rules out 47 for 4 \times 4.
Why. A recipe for small matrices applies recursively to matrices of any size, so one multiplication saved at 4 \times 4 is an asymptotically faster algorithm for all of numerical linear algebra. Rational coefficients mean the result is usable in ordinary numerical code.
Ref: Dumas, Pernet, Sedoglavic: 48 multiplications, rational · A more accurate rational algorithm in 48 multiplications · Wikipedia: Computational complexity of matrix multiplication
Verifiers (1)
Author a verifiermatmul_4x4_47 active by seed · 10% commission · 5 s / 256 MB · Python
"""Verifier for "Multiply 4x4 matrices with 47 multiplications" (statement in
../matmul_4x4_47.md).
Problem: find a bilinear algorithm that multiplies two N x N matrices (N = 4)
with R <= MAX_RANK = 47 scalar multiplications and rational coefficients. The
algorithm is given by three lists U, V, W of R matrices of size N x N and
computes, for C = A.B,
C[m][n] = sum_r W[r][m][n] * (sum_ij U[r][i][j] A[i][j])
* (sum_kl V[r][k][l] B[k][l]).
It is correct for all A and B (over any commutative or non-commutative ring
containing the rationals) exactly when, for all i, j, k, l, m, n in 0..N-1,
sum_r U[r][i][j] * V[r][k][l] * W[r][m][n] == [i == m] * [j == k] * [l == n]
which is N^6 = 4096 equations. The record over the rationals is 48
multiplications; 47 is known only modulo 2, which does not count here.
Expected submission: one JSON object with exactly the keys "U", "V", "W", e.g.
(shape only, N = 2, R = 7)
{"U": [[[1, 0], [0, 1]], ... 7 matrices ...],
"V": [[[1, 0], [0, 1]], ...],
"W": [[[1, 0], ["-1/2", "3/4"]], ...]}
* "U", "V" and "W" are lists of the same length R, 1 <= R <= MAX_RANK.
U[r], V[r], W[r] belong to the r-th multiplication.
* Every matrix is a list of N rows, every row a list of N entries; entry
[i][j] is row i, column j, 0-based.
* Every entry is a rational number written in one of two ways:
- a JSON integer (no fraction part, no exponent) of at most MAX_DIGITS
decimal digits, for example 0, 1, -3;
- a JSON string "p/q" matching exactly
(0|-?[1-9][0-9]*)/[1-9][0-9]*
with ASCII digits only, p and q of at most MAX_DIGITS digits each:
no spaces, no "+", no leading zeros, no "-0", q >= 1, the sign on p
only. The fraction need not be in lowest terms ("2/4" is fine) and
q may be 1 ("3/1").
Floats (1.0, 1e3), booleans, null, NaN/Infinity and strings without a
"/" are rejected.
* Within each of the three lists, the least common multiple of all
denominators (after reducing each fraction) must have at most
MAX_LCM_DIGITS decimal digits.
Why these bounds. The check is exact: each list is multiplied by its common
denominator and the 4096 equations are then checked in integer arithmetic,
with no floating point and no modular shortcut. Without the common-denominator
bound, a hostile submission with many distinct large prime denominators would
make those integers tens of thousands of digits long; with it, every integer
in the check has at most 3 * (MAX_DIGITS + MAX_LCM_DIGITS) digits, so the cost
is bounded whatever is submitted. The bounds are far above what real
algorithms need: the published 48-multiplication schemes use coefficients
with one or two digits and denominators that are small powers of 2. Rescaling
(U[r], V[r], W[r]) -> (a U[r], b V[r], W[r] / (a b)) keeps a recipe valid and
can always be used to tidy up coefficients.
What the verifier checks, in order:
1. The payload is a str of at most MAX_BYTES characters and parses as a
JSON object with exactly the keys "U", "V", "W". Duplicate keys anywhere,
float literals, NaN/Infinity and integer literals longer than MAX_DIGITS
digits are refused during parsing.
2. U, V, W are lists of one common length R with 1 <= R <= MAX_RANK.
3. Every element is an N x N list of lists (shape checked before entries).
4. Every entry is a rational in the encoding above, within MAX_DIGITS.
5. Each list has a common denominator of at most MAX_LCM_DIGITS digits.
6. All N^6 equations hold exactly.
"""
import json
import math
import re
# Matrix size: the algorithm multiplies two N x N matrices.
N = 4
# Largest allowed number of multiplications. The record over Q is 48.
MAX_RANK = 47
# Maximum number of decimal digits of any numerator and of any denominator.
MAX_DIGITS = 40
# Maximum number of decimal digits of the common denominator of each list.
MAX_LCM_DIGITS = 100
# Maximum size of the whole submission, in characters. A submission with
# MAX_RANK terms in which every entry is a "p/q" string with a sign and
# MAX_DIGITS digits on both sides takes about 195,000 characters.
MAX_BYTES = 250_000
# The only accepted spelling of a fraction. With a str pattern, [0-9] matches
# the ten ASCII digits only (unlike \d or int(), which accept other scripts),
# and fullmatch does not tolerate a trailing newline (unlike "$").
_FRACTION = re.compile(r"(0|-?[1-9][0-9]*)/([1-9][0-9]*)")
# ---------------------------------------------------------------------------
# Input-parsing helpers.
# ---------------------------------------------------------------------------
def _no_duplicate_keys(pairs):
"""object_pairs_hook: build the dict, refusing a repeated key."""
d = dict(pairs)
if len(d) != len(pairs):
raise ValueError
return d
def _refuse(_text):
"""parse_float / parse_constant hook: floats, NaN and Infinity are refused."""
raise ValueError
def _parse_int(text):
"""parse_int hook: refuse long literals before converting them."""
if len(text) > MAX_DIGITS + 1:
raise ValueError
return int(text)
def _load(solution, keys, max_bytes):
"""Parse the submission as a JSON object with exactly the given keys, or raise."""
# Refuse oversized payloads before handing them to the JSON parser.
if not isinstance(solution, str) or len(solution) > max_bytes:
raise ValueError
d = json.loads(solution, object_pairs_hook=_no_duplicate_keys,
parse_int=_parse_int, parse_float=_refuse,
parse_constant=_refuse)
# It must be an object (not a list, string or number) whose keys are
# exactly the expected ones: nothing missing, nothing extra.
if type(d) is not dict or set(d) != set(keys):
raise ValueError
return d
def _rational(v, limit):
"""Return (numerator, denominator) in lowest terms for one entry, or raise.
`limit` is 10 ** MAX_DIGITS. `type(v) is int` (rather than isinstance)
rejects true and false; floats never get here (the parser refuses them).
"""
if type(v) is int:
if not -limit < v < limit:
raise ValueError
return v, 1
if type(v) is not str or len(v) > 2 * MAX_DIGITS + 2:
raise ValueError
match = _FRACTION.fullmatch(v)
if match is None:
raise ValueError
p_text, q_text = match.groups()
if len(p_text.lstrip("-")) > MAX_DIGITS or len(q_text) > MAX_DIGITS:
raise ValueError
p, q = int(p_text), int(q_text)
g = math.gcd(p, q)
return p // g, q // g
def _shape(matrices, rank):
"""Check that `matrices` is a list of `rank` N x N lists of lists, or raise."""
if type(matrices) is not list or len(matrices) != rank:
raise ValueError
for matrix in matrices:
if type(matrix) is not list or len(matrix) != N:
raise ValueError
for row in matrix:
if type(row) is not list or len(row) != N:
raise ValueError
def _integer_list(matrices):
"""Clear the denominators of one list of matrices.
Returns (rows, den): rows[r] is the r-th matrix flattened row by row
(entry [i][j] at position i * N + j) and multiplied by `den`, the least
common multiple of all denominators in the list. Raises if an entry is
malformed or if `den` exceeds MAX_LCM_DIGITS digits.
"""
limit = 10 ** MAX_DIGITS
lcm_limit = 10 ** MAX_LCM_DIGITS
den = 1
fractions = []
for matrix in matrices:
flat = []
for row in matrix:
for v in row:
p, q = _rational(v, limit)
if q != 1:
den = den * q // math.gcd(den, q)
if den >= lcm_limit:
raise ValueError
flat.append((p, q))
fractions.append(flat)
return [[p * (den // q) for p, q in flat] for flat in fractions], den
# ---------------------------------------------------------------------------
# The actual check.
# ---------------------------------------------------------------------------
def _check(solution):
# Step 1: read the JSON object.
sol = _load(solution, ("U", "V", "W"), MAX_BYTES)
lists = (sol["U"], sol["V"], sol["W"])
# Step 2: one common number of multiplications, within the bar.
if type(lists[0]) is not list:
return False
rank = len(lists[0])
if not 1 <= rank <= MAX_RANK:
return False
# Step 3: shapes of everything, before looking at any entry.
for matrices in lists:
_shape(matrices, rank)
# Steps 4-5: exact integers u = den_u * U, v = den_v * V, w = den_w * W.
(u, den_u), (v, den_v), (w, den_w) = (_integer_list(x) for x in lists)
# Step 6: total[(a * N^2 + b) * N^2 + c] accumulates, over the terms r,
# u[r][a] * v[r][b] * w[r][c] with a = i*N + j, b = k*N + l, c = m*N + n.
size = N * N
total = [0] * (size ** 3)
for ur, vr, wr in zip(u, v, w, strict=True):
for a in range(size):
ua = ur[a]
if ua == 0:
continue
for b in range(size):
uv = ua * vr[b]
if uv == 0:
continue
base = (a * size + b) * size
for c in range(size):
total[base + c] += uv * wr[c]
# The matrix multiplication tensor, scaled by the three denominators.
one = den_u * den_v * den_w
position = 0
for i in range(N):
for j in range(N):
for k in range(N):
for l in range(N):
for m in range(N):
for n in range(N):
want = one if (i == m and j == k and l == n) else 0
if total[position] != want:
return False
position += 1
return position == size ** 3
def verify(solution: str, rng) -> bool:
"""Platform entry point: return True only for a valid, correct solution.
`rng` (a numpy.random.Generator) is part of the platform interface but is
not used: this check is deterministic and exact. Any exception (malformed
JSON, a bad value, nesting too deep, ...) means the submission is
rejected, so this function never raises.
"""
try:
return _check(solution) is True
except Exception:
return False
Log in to submit a solution
Verified solutions (0)
No verified solution yet.
Order book
Price history
Comments (0)
No comments yet.