AFTD Auto-Formalizing Theoretical Domains

matrix3_tensor_rank_le_of_surjective

theoremverifiedformalization

If f : R → S is a surjective homomorphism of commutative semirings and 3x3 matrix multiplication over R has a valid triad decomposition with at most r products, then so does 3x3 matrix multiplication over S (apply f to every coefficient).

Statement

theorem matrix3_tensor_rank_le_of_surjective {R S : Type*} [CommSemiring R] [CommSemiring S] (f : R →+* S) (hf : Function.Surjective f) (r : ℕ) (h : matrix3_tensor_rank_le R r) : matrix3_tensor_rank_le S r
Formalizes
Lower Bound of 22 for 3x3 Matrix Multiplication over the Integers, arXiv:2610.01639, Sec. 5.3 (reading an integer algorithm modulo 2), generalised to any surjective homomorphism of commutative semirings
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • 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.
  • eval_matrix3_decompositionGiven a commutative semiring R, a list L of Matrix3Triad R, and 3x3 matrices A and B over R, eval_matrix3_decomposition L A B is the sum…
  • 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 3

The proof, explained

To show that the 3x3 matrix multiplication tensor rank over S is at most r, we map a minimal triad decomposition over R entrywise under the surjective homomorphism f. First, evaluating a decomposition commutes with applying f because ring homomorphisms preserve all operations in the evaluation formula. Second, the mapped decomposition remains valid over S because surjectivity guarantees that any pair of matrices over S lifts to preimages over R, where the decomposition is known to compute their product. Finally, mapping preserves the length of the list of triads, so the resulting decomposition over S has length at most r.

  1. Definition of entrywise mapping of matrix triads under a ring homomorphism.

    We define matrix3_triad_map, which maps a triad t = (u, v, w) of 3x3 matrices over R to a triad over S by applying the ring homomorphism f : R →+* S entrywise to each of the three matrices u, v, and w.

    lines 1–4

    /-- The image of a triad under a ring homomorphism, entrywise. -/
    def matrix3_triad_map {R S : Type*} [CommSemiring R] [CommSemiring S] (f : R →+* S)
        (t : Matrix3Triad R) : Matrix3Triad S :=
      ⟨t.u.map f, t.v.map f, t.w.map f⟩
  2. Entrywise evaluation of a decomposition reduces to commuting the homomorphism with the sum over triads.

    To show that decomposition evaluation commutes with f, we use matrix extensionality (ext i j) and rewrite both sides entrywise using Matrix.map_apply and eval_matrix3_decomposition_apply. Because f is a homomorphism, it commutes with the list sum (map_list_sum) and list mapping composition (List.map_map), leaving an equality of sums over L.

    lines 6–13

    uses Matrix.map_apply, eval_matrix3_decomposition_apply, map_list_sum, List.map_map

    /-- Evaluating a decomposition commutes with applying a ring homomorphism. -/
    theorem eval_matrix3_decomposition_map {R S : Type*} [CommSemiring R] [CommSemiring S]
        (f : R →+* S) (L : List (Matrix3Triad R)) (A B : Matrix (Fin 3) (Fin 3) R) :
        (eval_matrix3_decomposition L A B).map f =
          eval_matrix3_decomposition (L.map (matrix3_triad_map f)) (A.map f) (B.map f) := by
      ext i j
      rw [Matrix.map_apply, eval_matrix3_decomposition_apply, eval_matrix3_decomposition_apply,
        map_list_sum, List.map_map, List.map_map]
  3. The evaluation of each individual triad commutes with the ring homomorphism.

    Using congruence on the list summation (congr 1 and List.map_congr_left), it suffices to check that each triad's contribution commutes with f. Since f preserves addition and multiplication (map_sum and map_mul), simplifying with the definition of matrix3_triad_map shows that the scalar products and scaling commute with f.

    lines 14–17

    uses List.map_congr_left, map_sum, map_mul

      congr 1
      apply List.map_congr_left
      intro t _
      simp [matrix3_triad_map, map_sum, map_mul]
  4. Every pair of matrices over S can be lifted entrywise to preimages over R.

    To show that the mapped decomposition is valid over S, let A', B' be arbitrary 3x3 matrices over S. By the surjectivity of f (hf), every entry has a preimage in R, giving preimages A, B over R such that A.map f = A' and B.map f = B'.

    lines 19–28

    /-- A valid decomposition stays valid under a surjective ring homomorphism. -/
    theorem is_valid_matrix3_decomposition_map {R S : Type*} [CommSemiring R] [CommSemiring S]
        (f : R →+* S) (hf : Function.Surjective f) (L : List (Matrix3Triad R))
        (hL : is_valid_matrix3_decomposition L) :
        is_valid_matrix3_decomposition (L.map (matrix3_triad_map f)) := by
      intro A' B'
      obtain ⟨A, rfl⟩ : ∃ A : Matrix (Fin 3) (Fin 3) R, A.map f = A' :=
        ⟨fun i j => (hf (A' i j)).choose, by ext i j; exact (hf (A' i j)).choose_spec⟩
      obtain ⟨B, rfl⟩ : ∃ B : Matrix (Fin 3) (Fin 3) R, B.map f = B' :=
        ⟨fun i j => (hf (B' i j)).choose, by ext i j; exact (hf (B' i j)).choose_spec⟩
  5. The mapped decomposition computes the product A' * B'.

    Rewriting A' and B' as A.map f and B.map f, eval_matrix3_decomposition_map pulls f outside the evaluation. Since L is valid over R (hL A B), the inner term evaluates to A * B, and Matrix.map_mul gives (A * B).map f = A' * B'.

    line 29

    uses eval_matrix3_decomposition_map, Matrix.map_mul

      rw [← eval_matrix3_decomposition_map, hL A B, Matrix.map_mul]
  6. Obtain a valid triad decomposition L over R of length at most r.

    From the hypothesis h that 3x3 matrix multiplication over R has tensor rank at most r, we unpack the witness list L of triads, the length bound hlen stating that L has length at most r, and the validity proof hL for L over R.

    lines 31–32

    theorem matrix3_tensor_rank_le_of_surjective {R S : Type*} [CommSemiring R] [CommSemiring S] (f : R →+* S) (hf : Function.Surjective f) (r : ℕ) (h : matrix3_tensor_rank_le R r) : matrix3_tensor_rank_le S r := by
      obtain ⟨L, hlen, hL⟩ := h
  7. The entrywise mapped decomposition witnesses that the tensor rank over S is at most r.

    We provide L.map (matrix3_triad_map f) as the witness decomposition over S. Its length is at most r because mapping does not change list length (simpa using hlen), and it is valid over S by is_valid_matrix3_decomposition_map.

    line 33

    uses is_valid_matrix3_decomposition_map

      exact ⟨L.map (matrix3_triad_map f), by simpa using hlen, is_valid_matrix3_decomposition_map f hf L hL⟩
Matrix.map_mul
Applying a ring homomorphism entrywise to two matrices preserves their product.
Matrix.map_apply
The (i, j)-th entry of a matrix mapped under a function f is f applied to the (i, j)-th entry of the original matrix.
List.map_congr_left
Two functions produce the same mapped list if they agree on all elements belonging to that list.
List.map_map
Mapping a function g over a list and then mapping f is equivalent to mapping their composition f ∘ g.
eval_matrix3_decomposition_map
Evaluating a triad decomposition commutes with applying a ring homomorphism entrywise to each triad and to the input matrices.
eval_matrix3_decomposition_apply
The (i, j)-th entry of an evaluated decomposition is the sum over all triads in the list of the product of the bilinear forms on the inputs scaled by the output matrix entry.
is_valid_matrix3_decomposition_map
A valid triad decomposition over R remains valid over S after applying a surjective ring homomorphism f entrywise to each triad.
map_sum
A ring homomorphism distributes over finite sums.
map_list_sum
A ring homomorphism preserves the sum of elements in a list.
map_mul
A ring homomorphism preserves multiplication.

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

/-- The image of a triad under a ring homomorphism, entrywise. -/def matrix3_triad_map {R S : Type*} [CommSemiring R] [CommSemiring S] (f : R →+* S)    (t : Matrix3Triad R) : Matrix3Triad S :=  ⟨t.u.map f, t.v.map f, t.w.map f⟩/-- Evaluating a decomposition commutes with applying a ring homomorphism. -/theorem eval_matrix3_decomposition_map {R S : Type*} [CommSemiring R] [CommSemiring S]    (f : R →+* S) (L : List (Matrix3Triad R)) (A B : Matrix (Fin 3) (Fin 3) R) :    (eval_matrix3_decomposition L A B).map f =      eval_matrix3_decomposition (L.map (matrix3_triad_map f)) (A.map f) (B.map f) := by  ext i j  rw [Matrix.map_apply, eval_matrix3_decomposition_apply, eval_matrix3_decomposition_apply,    map_list_sum, List.map_map, List.map_map]  congr 1  apply List.map_congr_left  intro t _  simp [matrix3_triad_map, map_sum, map_mul]/-- A valid decomposition stays valid under a surjective ring homomorphism. -/theorem is_valid_matrix3_decomposition_map {R S : Type*} [CommSemiring R] [CommSemiring S]    (f : R →+* S) (hf : Function.Surjective f) (L : List (Matrix3Triad R))    (hL : is_valid_matrix3_decomposition L) :    is_valid_matrix3_decomposition (L.map (matrix3_triad_map f)) := by  intro A' B'  obtain ⟨A, rfl⟩ : ∃ A : Matrix (Fin 3) (Fin 3) R, A.map f = A' :=    ⟨fun i j => (hf (A' i j)).choose, by ext i j; exact (hf (A' i j)).choose_spec⟩  obtain ⟨B, rfl⟩ : ∃ B : Matrix (Fin 3) (Fin 3) R, B.map f = B' :=    ⟨fun i j => (hf (B' i j)).choose, by ext i j; exact (hf (B' i j)).choose_spec⟩  rw [← eval_matrix3_decomposition_map, hL A B, Matrix.map_mul]theorem matrix3_tensor_rank_le_of_surjective {R S : Type*} [CommSemiring R] [CommSemiring S] (f : R →+* S) (hf : Function.Surjective f) (r : ℕ) (h : matrix3_tensor_rank_le R r) : matrix3_tensor_rank_le S r := by  obtain ⟨L, hlen, hL⟩ := h  exact ⟨L.map (matrix3_triad_map f), by simpa using hlen, is_valid_matrix3_decomposition_map f hf L hL⟩
See it in the graphDiscuss this resultChallenge it