matrix3_tensor_rank_ge_of_surjective
If f : R → S is a surjective homomorphism of commutative semirings and every valid triad decomposition of 3x3 matrix multiplication over S has at least r products, then the same holds over R.
Statement
theorem matrix3_tensor_rank_ge_of_surjective {R S : Type*} [CommSemiring R] [CommSemiring S] (f : R →+* S) (hf : Function.Surjective f) (r : ℕ) (h : matrix3_tensor_rank_ge S r) : matrix3_tensor_rank_ge R r
- Formalizes
- Lower Bound of 22 for 3x3 Matrix Multiplication over the Integers, arXiv:2610.01639, Sec. 5.3 (lower bounds over the two-element field transfer to the integers), generalised to any surjective homomorphism of commutative semirings
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- matrix3_tensor_rank_geFor a commutative semiring R and a natural number r, matrix3_tensor_rank_ge R r asserts that for every list L of elements of Matrix3Triad…
- 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…
- Used by 1
- matrix3_tensor_rank_int_ge_of_zmod2A lower bound r on the number of products of every bilinear algorithm for 3x3 matrix multiplication over the two-element field is also a…
The proof, explained
To show that every valid triad decomposition over R requires at least r products, consider an arbitrary valid decomposition L over R. By matrix3_tensor_rank_le_of_surjective, the surjective homomorphism f transfers L to a valid decomposition L' over S with length at most that of L. The lower bound hypothesis on S then guarantees r ≤ L'.length, which by transitivity yields r ≤ L.length.
To establish matrix3_tensor_rank_ge R r, it suffices to consider an arbitrary valid decomposition L over R and show that r ≤ L.length.
By definition, matrix3_tensor_rank_ge R r asserts that every valid triad decomposition of 3×3 matrix multiplication over R has length at least r. We introduce an arbitrary list of triads L together with the assumption hL that L is a valid decomposition over R.
intro L hLThere exists a valid triad decomposition L' over S whose length is at most that of L.
Because L has length at most L.length (by reflexivity of inequality, le_rfl) and is valid (hL), it witnesses that matrix3_tensor_rank_le R L.length holds. Pushing this decomposition through the surjective homomorphism f via matrix3_tensor_rank_le_of_surjective yields a decomposition L' over S that is valid (hL') and satisfies L'.length ≤ L.length (hlen).
uses
matrix3_tensor_rank_le_of_surjective,le_rflobtain ⟨L', hlen, hL'⟩ := matrix3_tensor_rank_le_of_surjective f hf L.length ⟨L, le_rfl, hL⟩The length of L is at least r.
Applying the hypothesis h (that any valid decomposition over S has length at least r) to L' and its validity witness hL' gives r ≤ L'.length. Chaining this with hlen (L'.length ≤ L.length) via transitivity of ≤ concludes that r ≤ L.length.
exact (h L' hL').trans hlen
matrix3_tensor_rank_le_of_surjective- If f : R →+* S is a surjective homomorphism of commutative semirings and 3×3 matrix multiplication over R has a valid triad decomposition of length at most r, then so does 3×3 matrix multiplication over S.
le_rfl- The inequality relation ≤ is reflexive: a ≤ a for any a.
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.
theorem matrix3_tensor_rank_ge_of_surjective {R S : Type*} [CommSemiring R] [CommSemiring S] (f : R →+* S) (hf : Function.Surjective f) (r : ℕ) (h : matrix3_tensor_rank_ge S r) : matrix3_tensor_rank_ge R r := by intro L hL obtain ⟨L', hlen, hL'⟩ := matrix3_tensor_rank_le_of_surjective f hf L.length ⟨L, le_rfl, hL⟩ exact (h L' hL').trans hlen