matrix3_tensor_rank_le_of_surjective
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
- matrix3_tensor_rank_zmod2_le_of_intA bilinear algorithm for 3x3 matrix multiplication with integer coefficients and r products gives one over the two-element field with r…
- matrix3_tensor_rank_ge_of_surjectiveIf f : R → S is a surjective homomorphism of commutative semirings and every valid triad decomposition of 3x3 matrix multiplication over S…
- matrix3_tensor_rank_comm_ring_le_of_intFor any commutative ring R and any natural number r, if 3x3 matrix multiplication has tensor rank at most r over the integers, then 3x3…
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.
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.
/-- 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⟩
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.
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]
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.
uses
List.map_congr_left,map_sum,map_mulcongr 1 apply List.map_congr_left intro t _ simp [matrix3_triad_map, map_sum, map_mul]
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'.
/-- 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⟩
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'.
uses
eval_matrix3_decomposition_map,Matrix.map_mulrw [← eval_matrix3_decomposition_map, hL A B, Matrix.map_mul]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.
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
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.
uses
is_valid_matrix3_decomposition_mapexact ⟨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.
- The proof constructs matrix preimages entrywise under the surjective homomorphism f using the axiom of choice (via Function.Surjective.choose).
- The Lean snippet includes two prerequisite results: eval_matrix3_decomposition_map, which shows that decomposition evaluation commutes with ring homomorphisms, and is_valid_matrix3_decomposition_map, which shows that valid decompositions remain valid under surjective homomorphisms.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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⟩