AFTD Auto-Formalizing Theoretical Domains

matrix3_tensor_rank_le_23_of_comm_ring

theoremverifiedformalization

Over every commutative ring R, 3x3 matrix multiplication has a valid bilinear decomposition with 23 products (the classical 23-multiplication algorithm with integer coefficients 0, 1, -1); hence its rank over R is at most 23.

Statement

theorem matrix3_tensor_rank_le_23_of_comm_ring (R : Type*) [CommRing R] : matrix3_tensor_rank_le R 23
Formalizes
A noncommutative algorithm for multiplying matrices using 23 multiplications (1976), as cited in Lower Bound of 22 for 3x3 Matrix Multiplication over the Integers, arXiv:2610.01639, Sec. 1 and Sec. 7 (upper bound 23); the integer coefficients 0, 1, -1 make it valid over every commutative ring
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • matrix3_tensor_rank_leFor a commutative semiring R and a natural number r, matrix3_tensor_rank_le R r asserts that there exists a list L of elements of…
  • eval_matrix3_decomposition_applyEntry (i, j) of the evaluation of a list of 3x3 triads on A and B is the sum, over the triads, of (sum of u_kl A_kl) times (sum of v_kl…
  • Matrix3TriadGiven a type R, a Matrix3Triad R is a structure consisting of three 3-by-3 matrices with entries in R, labeled u, v, and w.
  • is_valid_matrix3_decompositionGiven a commutative semiring R and a list L of Matrix3Triad R, is_valid_matrix3_decomposition L asserts that for all 3x3 matrices A and B…
Used by 4
  • matrix3_tensor_rank_z_le_23The tensor rank of 3x3 matrix multiplication over the integers is at most 23; that is, there exists a valid decomposition of 3x3 matrix…
  • matrix3_tensor_rank_f2_le_23The tensor rank of 3x3 matrix multiplication over the field ZMod 2 is at most 23; that is, there exists a valid decomposition of 3x3…
  • matrix3_unit_check_witnessesThe checker matrix3_unit_check returns true on the classical 23-triad decomposition of 3x3 matrix multiplication over ZMod 2 (so the…
  • matrix3_unit_check_int_witnessesThe checker matrix3_unit_check_int returns true on the classical 23-triad integer decomposition and false on the empty list.

The proof, explained

The theorem shows that the tensor rank of 3×3 matrix multiplication over any commutative ring R is at most 23 by exhibiting Laderman's 1976 decomposition consisting of 23 explicit triads with coefficients in {-1, 0, 1}. Validity is verified entry-by-entry: after reducing to the 9 matrix positions, each entry simplifies to an algebraic identity in the coefficients of the input matrices, verified by ring normalization. Packaging this list along with its length equality proves the tensor rank bound.

  1. An explicit list of 23 triads of 3×3 matrices is defined over any commutative ring R.

    We construct Laderman's 23 triples of 3×3 matrices (u, v, w) with coefficients in {0, 1, -1}.

    lines 1–28

    /-- An explicit list of 23 triads over any commutative ring; its 23 products compute the 3×3 matrix product. -/
    def matrix3_triads_23 (R : Type*) [CommRing R] : List (Matrix3Triad R) :=
      [
        ⟨!![1, 1, 1; -1, -1, 0; 0, -1, -1], !![0, 0, 0; 0, 1, 0; 0, 0, 0], !![0, 1, 0; 0, 0, 0; 0, 0, 0]⟩,
        ⟨!![1, 0, 0; -1, 0, 0; 0, 0, 0], !![0, -1, 0; 0, 1, 0; 0, 0, 0], !![0, 0, 0; 1, 1, 0; 0, 0, 0]⟩,
        ⟨!![0, 0, 0; 0, 1, 0; 0, 0, 0], !![-1, 1, 0; 1, -1, -1; -1, 0, 1], !![0, 0, 0; 1, 0, 0; 0, 0, 0]⟩,
        ⟨!![-1, 0, 0; 1, 1, 0; 0, 0, 0], !![1, -1, 0; 0, 1, 0; 0, 0, 0], !![0, 1, 0; 1, 1, 0; 0, 0, 0]⟩,
        ⟨!![0, 0, 0; 1, 1, 0; 0, 0, 0], !![-1, 1, 0; 0, 0, 0; 0, 0, 0], !![0, 1, 0; 0, 1, 0; 0, 0, 0]⟩,
        ⟨!![1, 0, 0; 0, 0, 0; 0, 0, 0], !![1, 0, 0; 0, 0, 0; 0, 0, 0], !![1, 1, 1; 1, 1, 0; 1, 0, 1]⟩,
        ⟨!![-1, 0, 0; 0, 0, 0; 1, 1, 0], !![1, 0, -1; 0, 0, 1; 0, 0, 0], !![0, 0, 1; 0, 0, 0; 1, 0, 1]⟩,
        ⟨!![-1, 0, 0; 0, 0, 0; 1, 0, 0], !![0, 0, 1; 0, 0, -1; 0, 0, 0], !![0, 0, 0; 0, 0, 0; 1, 0, 1]⟩,
        ⟨!![0, 0, 0; 0, 0, 0; 1, 1, 0], !![-1, 0, 1; 0, 0, 0; 0, 0, 0], !![0, 0, 1; 0, 0, 0; 0, 0, 1]⟩,
        ⟨!![1, 1, 1; 0, -1, -1; -1, -1, 0], !![0, 0, 0; 0, 0, 1; 0, 0, 0], !![0, 0, 1; 0, 0, 0; 0, 0, 0]⟩,
        ⟨!![0, 0, 0; 0, 0, 0; 0, 1, 0], !![-1, 0, 1; 1, -1, -1; -1, 1, 0], !![0, 0, 0; 0, 0, 0; 1, 0, 0]⟩,
        ⟨!![0, 0, -1; 0, 0, 0; 0, 1, 1], !![0, 0, 0; 0, 1, 0; 1, -1, 0], !![0, 1, 0; 0, 0, 0; 1, 1, 0]⟩,
        ⟨!![0, 0, 1; 0, 0, 0; 0, 0, -1], !![0, 0, 0; 0, 1, 0; 0, -1, 0], !![0, 0, 0; 0, 0, 0; 1, 1, 0]⟩,
        ⟨!![0, 0, 1; 0, 0, 0; 0, 0, 0], !![0, 0, 0; 0, 0, 0; 1, 0, 0], !![1, 1, 1; 1, 0, 1; 1, 1, 0]⟩,
        ⟨!![0, 0, 0; 0, 0, 0; 0, 1, 1], !![0, 0, 0; 0, 0, 0; -1, 1, 0], !![0, 1, 0; 0, 0, 0; 0, 1, 0]⟩,
        ⟨!![0, 0, -1; 0, 1, 1; 0, 0, 0], !![0, 0, 0; 0, 0, 1; 1, 0, -1], !![0, 0, 1; 1, 0, 1; 0, 0, 0]⟩,
        ⟨!![0, 0, 1; 0, 0, -1; 0, 0, 0], !![0, 0, 0; 0, 0, 1; 0, 0, -1], !![0, 0, 0; 1, 0, 1; 0, 0, 0]⟩,
        ⟨!![0, 0, 0; 0, 1, 1; 0, 0, 0], !![0, 0, 0; 0, 0, 0; -1, 0, 1], !![0, 0, 1; 0, 0, 1; 0, 0, 0]⟩,
        ⟨!![0, 1, 0; 0, 0, 0; 0, 0, 0], !![0, 0, 0; 1, 0, 0; 0, 0, 0], !![1, 0, 0; 0, 0, 0; 0, 0, 0]⟩,
        ⟨!![0, 0, 0; 0, 0, 1; 0, 0, 0], !![0, 0, 0; 0, 0, 0; 0, 1, 0], !![0, 0, 0; 0, 1, 0; 0, 0, 0]⟩,
        ⟨!![0, 0, 0; 1, 0, 0; 0, 0, 0], !![0, 0, 1; 0, 0, 0; 0, 0, 0], !![0, 0, 0; 0, 0, 1; 0, 0, 0]⟩,
        ⟨!![0, 0, 0; 0, 0, 0; 1, 0, 0], !![0, 1, 0; 0, 0, 0; 0, 0, 0], !![0, 0, 0; 0, 0, 0; 0, 1, 0]⟩,
        ⟨!![0, 0, 0; 0, 0, 0; 0, 0, 1], !![0, 0, 0; 0, 0, 0; 0, 0, 1], !![0, 0, 0; 0, 0, 0; 0, 0, 1]⟩
      ]
    
  2. The triad list matrix3_triads_23 has length 23.

    The length of the list is 23 by definition (refl).

    lines 29–30

    theorem matrix3_triads_23_length (R : Type*) [CommRing R] : (matrix3_triads_23 R).length = 23 := rfl
    
  3. It suffices to show that for any two 3×3 matrices A and B and any indices i, j ∈ Fin 3, the (i, j)-th entry of the decomposition's evaluation matches (A * B) i j.

    We introduce arbitrary matrices A and B, then use matrix extensionality to reduce the equality of the two 3×3 matrices to showing their entries agree at every row i and column j.

    lines 31–35

    theorem matrix3_triads_23_valid (R : Type*) [CommRing R] :
        is_valid_matrix3_decomposition (matrix3_triads_23 R) := by
      set_option maxHeartbeats 1000000 in
      intro A B
      ext i j
  4. The (i, j)-th entry of the decomposition is expanded as the sum of the triad products.

    We rewrite the left-hand side using eval_matrix3_decomposition_apply, expressing the entry as the sum over all 23 triads of the scalar product of A with u, times the scalar product of B with v, scaled by the (i, j)-th entry of w.

    line 36

    uses eval_matrix3_decomposition_apply

      rw [eval_matrix3_decomposition_apply]
  5. For each of the 9 index pairs (i, j), the evaluated decomposition equals the (i, j)-th entry of A * B. automation

    We exhaust all 9 choices of (i, j) in Fin 3 × Fin 3. For each pair, simp unfolds the definition of the 23 triads, expands the sums over Fin 3 via Fin.sum_univ_three, and writes the right-hand side via Matrix.mul_apply; the ring tactic then confirms that the resulting polynomial identity in the matrix entries of A and B holds in the commutative ring R.

    lines 37–38

    uses Fin.sum_univ_three, Matrix.mul_apply

      fin_cases i <;> fin_cases j <;>
        simp [matrix3_triads_23, Fin.sum_univ_three, Matrix.mul_apply] <;> ring
  6. The tensor rank of 3×3 matrix multiplication over R is at most 23.

    We witness the definition of matrix3_tensor_rank_le using the explicit triad list matrix3_triads_23 R. Its length is at most 23 by le_of_eq applied to matrix3_triads_23_length, and its validity is given by matrix3_triads_23_valid.

    lines 39–40

    uses le_of_eq, matrix3_triads_23_length, matrix3_triads_23_valid

    theorem matrix3_tensor_rank_le_23_of_comm_ring (R : Type*) [CommRing R] : matrix3_tensor_rank_le R 23 := ⟨matrix3_triads_23 R, le_of_eq (matrix3_triads_23_length R), matrix3_triads_23_valid R⟩
Matrix.mul_apply
The (i, j)-th entry of the matrix product A * B is the sum over k of A i k * B k j.
Fin.sum_univ_three
A sum of a function over the three elements of Fin 3 equals the sum of its values at 0, 1, and 2.
eval_matrix3_decomposition_apply
The (i, j)-th entry of the evaluated decomposition is the sum over all triads t in L of (∑ k l, t.u k l * A k l) * (∑ k l, t.v k l * B k l) * t.w i j.
le_of_eq
If a equals b, then a is less than or equal to b.
matrix3_triads_23_length
The explicit list of triads matrix3_triads_23 has length exactly 23.
matrix3_triads_23_valid
The explicit list of 23 triads correctly computes 3×3 matrix multiplication for any pair of matrices A and B.

Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- An explicit list of 23 triads over any commutative ring; its 23 products compute the 3×3 matrix product. -/def matrix3_triads_23 (R : Type*) [CommRing R] : List (Matrix3Triad R) :=  [    ⟨!![1, 1, 1; -1, -1, 0; 0, -1, -1], !![0, 0, 0; 0, 1, 0; 0, 0, 0], !![0, 1, 0; 0, 0, 0; 0, 0, 0]⟩,    ⟨!![1, 0, 0; -1, 0, 0; 0, 0, 0], !![0, -1, 0; 0, 1, 0; 0, 0, 0], !![0, 0, 0; 1, 1, 0; 0, 0, 0]⟩,    ⟨!![0, 0, 0; 0, 1, 0; 0, 0, 0], !![-1, 1, 0; 1, -1, -1; -1, 0, 1], !![0, 0, 0; 1, 0, 0; 0, 0, 0]⟩,    ⟨!![-1, 0, 0; 1, 1, 0; 0, 0, 0], !![1, -1, 0; 0, 1, 0; 0, 0, 0], !![0, 1, 0; 1, 1, 0; 0, 0, 0]⟩,    ⟨!![0, 0, 0; 1, 1, 0; 0, 0, 0], !![-1, 1, 0; 0, 0, 0; 0, 0, 0], !![0, 1, 0; 0, 1, 0; 0, 0, 0]⟩,    ⟨!![1, 0, 0; 0, 0, 0; 0, 0, 0], !![1, 0, 0; 0, 0, 0; 0, 0, 0], !![1, 1, 1; 1, 1, 0; 1, 0, 1]⟩,    ⟨!![-1, 0, 0; 0, 0, 0; 1, 1, 0], !![1, 0, -1; 0, 0, 1; 0, 0, 0], !![0, 0, 1; 0, 0, 0; 1, 0, 1]⟩,    ⟨!![-1, 0, 0; 0, 0, 0; 1, 0, 0], !![0, 0, 1; 0, 0, -1; 0, 0, 0], !![0, 0, 0; 0, 0, 0; 1, 0, 1]⟩,    ⟨!![0, 0, 0; 0, 0, 0; 1, 1, 0], !![-1, 0, 1; 0, 0, 0; 0, 0, 0], !![0, 0, 1; 0, 0, 0; 0, 0, 1]⟩,    ⟨!![1, 1, 1; 0, -1, -1; -1, -1, 0], !![0, 0, 0; 0, 0, 1; 0, 0, 0], !![0, 0, 1; 0, 0, 0; 0, 0, 0]⟩,    ⟨!![0, 0, 0; 0, 0, 0; 0, 1, 0], !![-1, 0, 1; 1, -1, -1; -1, 1, 0], !![0, 0, 0; 0, 0, 0; 1, 0, 0]⟩,    ⟨!![0, 0, -1; 0, 0, 0; 0, 1, 1], !![0, 0, 0; 0, 1, 0; 1, -1, 0], !![0, 1, 0; 0, 0, 0; 1, 1, 0]⟩,    ⟨!![0, 0, 1; 0, 0, 0; 0, 0, -1], !![0, 0, 0; 0, 1, 0; 0, -1, 0], !![0, 0, 0; 0, 0, 0; 1, 1, 0]⟩,    ⟨!![0, 0, 1; 0, 0, 0; 0, 0, 0], !![0, 0, 0; 0, 0, 0; 1, 0, 0], !![1, 1, 1; 1, 0, 1; 1, 1, 0]⟩,    ⟨!![0, 0, 0; 0, 0, 0; 0, 1, 1], !![0, 0, 0; 0, 0, 0; -1, 1, 0], !![0, 1, 0; 0, 0, 0; 0, 1, 0]⟩,    ⟨!![0, 0, -1; 0, 1, 1; 0, 0, 0], !![0, 0, 0; 0, 0, 1; 1, 0, -1], !![0, 0, 1; 1, 0, 1; 0, 0, 0]⟩,    ⟨!![0, 0, 1; 0, 0, -1; 0, 0, 0], !![0, 0, 0; 0, 0, 1; 0, 0, -1], !![0, 0, 0; 1, 0, 1; 0, 0, 0]⟩,    ⟨!![0, 0, 0; 0, 1, 1; 0, 0, 0], !![0, 0, 0; 0, 0, 0; -1, 0, 1], !![0, 0, 1; 0, 0, 1; 0, 0, 0]⟩,    ⟨!![0, 1, 0; 0, 0, 0; 0, 0, 0], !![0, 0, 0; 1, 0, 0; 0, 0, 0], !![1, 0, 0; 0, 0, 0; 0, 0, 0]⟩,    ⟨!![0, 0, 0; 0, 0, 1; 0, 0, 0], !![0, 0, 0; 0, 0, 0; 0, 1, 0], !![0, 0, 0; 0, 1, 0; 0, 0, 0]⟩,    ⟨!![0, 0, 0; 1, 0, 0; 0, 0, 0], !![0, 0, 1; 0, 0, 0; 0, 0, 0], !![0, 0, 0; 0, 0, 1; 0, 0, 0]⟩,    ⟨!![0, 0, 0; 0, 0, 0; 1, 0, 0], !![0, 1, 0; 0, 0, 0; 0, 0, 0], !![0, 0, 0; 0, 0, 0; 0, 1, 0]⟩,    ⟨!![0, 0, 0; 0, 0, 0; 0, 0, 1], !![0, 0, 0; 0, 0, 0; 0, 0, 1], !![0, 0, 0; 0, 0, 0; 0, 0, 1]⟩  ]theorem matrix3_triads_23_length (R : Type*) [CommRing R] : (matrix3_triads_23 R).length = 23 := rfltheorem matrix3_triads_23_valid (R : Type*) [CommRing R] :    is_valid_matrix3_decomposition (matrix3_triads_23 R) := by  set_option maxHeartbeats 1000000 in  intro A B  ext i j  rw [eval_matrix3_decomposition_apply]  fin_cases i <;> fin_cases j <;>    simp [matrix3_triads_23, Fin.sum_univ_three, Matrix.mul_apply] <;> ringtheorem matrix3_tensor_rank_le_23_of_comm_ring (R : Type*) [CommRing R] : matrix3_tensor_rank_le R 23 := ⟨matrix3_triads_23 R, le_of_eq (matrix3_triads_23_length R), matrix3_triads_23_valid R⟩
See it in the graphDiscuss this resultChallenge it