AFTD Auto-Formalizing Theoretical Domains

matrix3_tensor_rank_comm_ring_le_of_int

theoremverifiedformalization

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.

  1. 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.

    lines 6–7

    uses Matrix.map_map

      cases t
      simp [matrix3_triad_map, Matrix.map_map]
  2. 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.

    lines 13–18

    uses List.map_map, List.map_congr_left, Function.comp_apply, matrix3_triad_map_comp, RingHom.ext_int

      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 _ _
  3. 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.

    line 24

      obtain ⟨L, hlen, hL⟩ := h
  4. Construct 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.

    lines 26–29

      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
  5. 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.

    lines 30–36

    uses Matrix.ext, MvPolynomial.funext, congrFun, eval_matrix3_decomposition_map, Matrix.map_apply, matrix3_triad_map_C_comp, Matrix.map_mul

      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]
  6. 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).

    lines 37–45

    uses RingHom.ext_int, List.map_id, List.map_congr_left

        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]
  7. 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.

    lines 46–47

      refine ⟨L.map (matrix3_triad_map (Int.castRingHom R)), by simpa using hlen, ?_⟩
      intro A B
  8. 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.

    lines 48–53

    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
  9. 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.

    lines 54–56

    uses eval_matrix3_decomposition_map, Matrix.map_mul, matrix3_triad_map_C_comp

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

/-- 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
See it in the graphDiscuss this resultChallenge it