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

C_{mn} = \sum_{r=1}^{R} W_r[m][n] \Big(\sum_{i,j} U_r[i][j]\, A_{ij}\Big)\Big(\sum_{k,l} V_r[k][l]\, B_{kl}\Big).

Verifier sketch. Check R \le 47, clear the denominators of each list, then check in exact integer arithmetic that for all indices

\sum_{r=1}^{R} U_r[i][j]\, V_r[k][l]\, W_r[m][n] = [i = m]\,[j = k]\,[l = n],

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 verifier
matmul_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

The book is empty. Be the first to bid.

Price history

Comments (0)

No comments yet.