matrix3_tensor_rank_comm_ring_le_of_int
For any commutative ring R and any natural number r, if 3x3 matrix multiplication has tensor rank at most r over the integers, then 3x3 matrix multiplication has tensor rank at most r over R.
Statement
theorem matrix3_tensor_rank_comm_ring_le_of_int (R : Type*) [CommRing R] (r : ℕ) (h : matrix3_tensor_rank_le ℤ r) : matrix3_tensor_rank_le R r
- Formalizes
- Bürgisser, Clausen, Shokrollahi, Algebraic Complexity Theory (1997), Proposition 14.1
- Verified
- 08 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…
- 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…
- matrix3_tensor_rank_le_of_surjectiveIf f : R → S is a surjective homomorphism of commutative semirings and 3x3 matrix multiplication over R has a valid triad decomposition…
- 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…
Read back from the Lean
For any commutative ring $R$ and any natural number $r$, if there exists a valid $3 \times 3$ matrix multiplication decomposition over $\mathbb{Z}$ of length at most $r$ (that is, matrix3_tensor_rank_le ℤ r), then there also exists a valid $3 \times 3$ matrix multiplication decomposition over $R$ of length at most $r$ (matrix3_tensor_rank_le R r).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To transfer an upper bound on the tensor rank of 3x3 matrix multiplication from ℤ to an arbitrary commutative ring R, the proof establishes matrix multiplication as a universal polynomial identity. It defines generic 3x3 matrices X and Y with indeterminate entries in a polynomial ring P over ℤ. Using polynomial identity testing over the infinite domain ℤ, the validity of the integer decomposition on all integer matrices implies that the decomposition correctly multiplies X and Y over P. Finally, specializing the indeterminates to any matrices A and B over R via the evaluation homomorphism P →+* R shows that the canonical integer-to-R image of the decomposition computes A * B, preserving the rank bound.
Mapping a triad along two ring homomorphisms successively is equivalent to mapping it along their composition. automation
Deconstructing a triad into its three matrices, mapping applies the homomorphism entrywise to each matrix. By Matrix.map_map, successively mapping each matrix by f and then g equals mapping by g ∘ f.
uses
Matrix.map_mapcases t simp [matrix3_triad_map, Matrix.map_map]
Embedding the integer triads into a polynomial ring via the constant map C and then applying a ring homomorphism f is equivalent to mapping them directly along the canonical map ℤ →+* S.
By List.map_map and List.map_congr_left, it suffices to check this elementwise. By matrix3_triad_map_comp, mapping by C and then f is mapping by f.comp C. Since there is a unique ring homomorphism from ℤ to any ring S (RingHom.ext_int), f.comp C equals the canonical homomorphism Int.castRingHom S.
uses
List.map_map,List.map_congr_left,Function.comp_apply,matrix3_triad_map_comp,RingHom.ext_intrw [List.map_map] apply List.map_congr_left intro t _ simp only [Function.comp_apply, matrix3_triad_map_comp] congr 1 exact RingHom.ext_int _ _
There exists a list L of integer triads of length at most r that forms a valid decomposition of 3x3 matrix multiplication over ℤ.
From the hypothesis that 3x3 matrix multiplication has tensor rank at most r over ℤ, we extract a witness list L of triads of length at most r satisfying eval_matrix3_decomposition L A B = A * B for all integer matrices A and B.
obtain ⟨L, hlen, hL⟩ := hConstruct the polynomial ring in 18 indeterminates, two generic 3x3 matrices X and Y, and the embedded decomposition LP over polynomials.
We define P = ℤ[X_{false, i, j}, X_{true, i, j}], set X and Y to be 3x3 matrices whose entries are the corresponding indeterminates, and define LP by embedding the integer triads of L into P using the constant map C.
set P := MvPolynomial (Bool × Fin 3 × Fin 3) ℤ set X : Matrix (Fin 3) (Fin 3) P := fun i j => MvPolynomial.X (false, i, j) with hX set Y : Matrix (Fin 3) (Fin 3) P := fun i j => MvPolynomial.X (true, i, j) with hY set LP := L.map (matrix3_triad_map (MvPolynomial.C : ℤ →+* P)) with hLP
The generic decomposition identity eval_matrix3_decomposition LP X Y = X * Y reduces to verifying it under every evaluation into ℤ.
By matrix extensionality (Matrix.ext), it suffices to prove equality at each entry (i, j). Since ℤ is an infinite integral domain, two polynomials in P are equal if they agree under every evaluation into ℤ (MvPolynomial.funext). Commuting evaluation with the decomposition via eval_matrix3_decomposition_map and simplifying the constant embedding via matrix3_triad_map_C_comp reduces the goal to evaluating L on integer matrices.
uses
Matrix.ext,MvPolynomial.funext,congrFun,eval_matrix3_decomposition_map,Matrix.map_apply,matrix3_triad_map_C_comp,Matrix.map_mulhave hgen : eval_matrix3_decomposition LP X Y = X * Y := by refine Matrix.ext fun i j => ?_ apply MvPolynomial.funext intro x have h1 := congrFun (congrFun (eval_matrix3_decomposition_map (MvPolynomial.eval x) LP X Y) i) j rw [Matrix.map_apply] at h1 rw [h1, hLP, matrix3_triad_map_C_comp, ← Matrix.map_apply (f := MvPolynomial.eval x), Matrix.map_mul]
The decomposition LP correctly computes the product X * Y of the generic matrices over P.
The canonical homomorphism from ℤ to ℤ is the identity (RingHom.ext_int), which leaves L unchanged under mapping (hLid). Therefore, each integer evaluation specializes the generic identity to eval_matrix3_decomposition L (X.map eval) (Y.map eval), which equals their product by the validity of L over ℤ (hL).
uses
RingHom.ext_int,List.map_id,List.map_congr_lefthave hid : Int.castRingHom ℤ = RingHom.id ℤ := RingHom.ext_int _ _ have hLid : L.map (matrix3_triad_map (Int.castRingHom ℤ)) = L := by rw [hid] conv_rhs => rw [← List.map_id L] apply List.map_congr_left intro t _ cases t simp [matrix3_triad_map] rw [hLid, hL]
The mapped list of triads over R has length at most r, and it remains to check that it computes matrix multiplication for arbitrary matrices A and B over R.
We provide the candidate decomposition over R obtained by mapping L along the canonical map ℤ →+* R. Its length is the same as L (at most r), and we introduce arbitrary 3x3 matrices A, B over R to check validity.
refine ⟨L.map (matrix3_triad_map (Int.castRingHom R)), by simpa using hlen, ?_⟩ intro A B
There is an evaluation homomorphism f : P →+* R that maps the generic matrices X and Y to A and B, respectively.
Using MvPolynomial.eval₂Hom, we construct the evaluation homomorphism extending ℤ →+* R that assigns the indeterminates of X to the entries of A and the indeterminates of Y to the entries of B. By MvPolynomial.eval₂Hom_X', X.map f = A and Y.map f = B.
uses
Matrix.ext,Matrix.map_apply,MvPolynomial.eval₂Hom_X'set f : P →+* R := MvPolynomial.eval₂Hom (Int.castRingHom R) (fun x => if x.1 then B x.2.1 x.2.2 else A x.2.1 x.2.2) with hf have hXA : X.map f = A := Matrix.ext fun i j => by rw [Matrix.map_apply, hf, hX, MvPolynomial.eval₂Hom_X']; rfl have hYB : Y.map f = B := Matrix.ext fun i j => by rw [Matrix.map_apply, hf, hY, MvPolynomial.eval₂Hom_X']; rfl
Specializing the generic identity along f proves that the mapped decomposition over R computes A * B.
Applying f to the generic identity eval_matrix3_decomposition LP X Y = X * Y via eval_matrix3_decomposition_map yields (X * Y).map f = eval_matrix3_decomposition (LP.map f) (X.map f) (Y.map f). Since (X * Y).map f = A * B and LP.map f simplifies via matrix3_triad_map_C_comp to L.map (Int.castRingHom R), this shows that the mapped decomposition evaluates to A * B.
uses
eval_matrix3_decomposition_map,Matrix.map_mul,matrix3_triad_map_C_comphave := eval_matrix3_decomposition_map f LP X Y rw [hgen, Matrix.map_mul, hXA, hYB, hLP, matrix3_triad_map_C_comp] at this exact this.symm
Matrix.map_mul- For any matrices L and M and any ring homomorphism f, applying f entrywise to the product L * M yields the product of the mapped matrices (L.map f) * (M.map f).
Matrix.map_map- Mapping a matrix by a function f and then by g is equivalent to mapping entrywise by their composition g ∘ f.
Matrix.map_apply- The (i, j)-th entry of a mapped matrix M.map f is f applied to M i j.
Matrix.ext- Two matrices of the same dimensions are equal if and only if all their corresponding entries are equal.
List.map_map- Mapping a list by f and then by g is equal to mapping by the composite function g ∘ f.
List.map_id- Mapping a list by the identity function returns the list unchanged.
List.map_congr_left- Two list mappings are equal if the two functions agree on every element of the list.
MvPolynomial.funext- For a multivariate polynomial ring over an infinite integral domain, two polynomials are equal if their evaluations agree on all points.
MvPolynomial.eval₂Hom_X'- The unique evaluation homomorphism eval₂Hom extending f and mapping variables via g evaluates the indeterminate variable X i to g i.
RingHom.ext_int- Any two ring homomorphisms from the integers ℤ to a semiring R are equal.
Function.comp_apply- Applying a composite function (f ∘ g) to an argument x equals f (g x).
congrFun- If two functions f and g are equal, their evaluations f a and g a on any argument a are equal.
eval_matrix3_decomposition_map- Evaluating a matrix decomposition evaluation commutes with applying a ring homomorphism f entrywise: the mapped evaluation of L on A and B equals the decomposition evaluation of L.map f on A.map f and B.map f.
matrix3_triad_map_comp- Mapping a triad by f and then by g is equal to mapping the triad by the composite homomorphism g.comp f.
matrix3_triad_map_C_comp- For any ring homomorphism f from polynomials over ℤ to S, mapping integer triads into the polynomial ring via the constant embedding C and then applying f yields the same triads as mapping directly by the canonical homomorphism ℤ →+* S.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. 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.
/-- Mapping a triad twice is mapping it by the composite (`matrix3_triad_map` and`eval_matrix3_decomposition_map` come from the module of `matrix3_tensor_rank_le_of_surjective`). -/theorem matrix3_triad_map_comp {R S T : Type*} [CommSemiring R] [CommSemiring S] [CommSemiring T] (g : S →+* T) (f : R →+* S) (t : Matrix3Triad R) : matrix3_triad_map g (matrix3_triad_map f t) = matrix3_triad_map (g.comp f) t := by cases t simp [matrix3_triad_map, Matrix.map_map]theorem matrix3_triad_map_C_comp {σ S : Type*} [CommRing S] (f : MvPolynomial σ ℤ →+* S) (L : List (Matrix3Triad ℤ)) : (L.map (matrix3_triad_map (MvPolynomial.C : ℤ →+* MvPolynomial σ ℤ))).map (matrix3_triad_map f) = L.map (matrix3_triad_map (Int.castRingHom S)) := by rw [List.map_map] apply List.map_congr_left intro t _ simp only [Function.comp_apply, matrix3_triad_map_comp] congr 1 exact RingHom.ext_int _ _/-- Tensor rank upper bounds for 3x3 matrix multiplication transfer from the integers to every commutative ring. -/theorem matrix3_tensor_rank_comm_ring_le_of_int (R : Type*) [CommRing R] (r : ℕ) (h : matrix3_tensor_rank_le ℤ r) : matrix3_tensor_rank_le R r := by obtain ⟨L, hlen, hL⟩ := h -- the identity holds for the generic matrices over `MvPolynomial ℤ` set P := MvPolynomial (Bool × Fin 3 × Fin 3) ℤ set X : Matrix (Fin 3) (Fin 3) P := fun i j => MvPolynomial.X (false, i, j) with hX set Y : Matrix (Fin 3) (Fin 3) P := fun i j => MvPolynomial.X (true, i, j) with hY set LP := L.map (matrix3_triad_map (MvPolynomial.C : ℤ →+* P)) with hLP have hgen : eval_matrix3_decomposition LP X Y = X * Y := by refine Matrix.ext fun i j => ?_ apply MvPolynomial.funext intro x have h1 := congrFun (congrFun (eval_matrix3_decomposition_map (MvPolynomial.eval x) LP X Y) i) j rw [Matrix.map_apply] at h1 rw [h1, hLP, matrix3_triad_map_C_comp, ← Matrix.map_apply (f := MvPolynomial.eval x), Matrix.map_mul] have hid : Int.castRingHom ℤ = RingHom.id ℤ := RingHom.ext_int _ _ have hLid : L.map (matrix3_triad_map (Int.castRingHom ℤ)) = L := by rw [hid] conv_rhs => rw [← List.map_id L] apply List.map_congr_left intro t _ cases t simp [matrix3_triad_map] rw [hLid, hL] refine ⟨L.map (matrix3_triad_map (Int.castRingHom R)), by simpa using hlen, ?_⟩ intro A B set f : P →+* R := MvPolynomial.eval₂Hom (Int.castRingHom R) (fun x => if x.1 then B x.2.1 x.2.2 else A x.2.1 x.2.2) with hf have hXA : X.map f = A := Matrix.ext fun i j => by rw [Matrix.map_apply, hf, hX, MvPolynomial.eval₂Hom_X']; rfl have hYB : Y.map f = B := Matrix.ext fun i j => by rw [Matrix.map_apply, hf, hY, MvPolynomial.eval₂Hom_X']; rfl have := eval_matrix3_decomposition_map f LP X Y rw [hgen, Matrix.map_mul, hXA, hYB, hLP, matrix3_triad_map_C_comp] at this exact this.symm