AFTD Auto-Formalizing Theoretical Domains

matrix3_tensor_rank_ge_of_surjective

theoremverifiedformalization

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

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.

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

    line 2

      intro L hL
  2. There 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).

    line 3

    uses matrix3_tensor_rank_le_of_surjective, le_rfl

      obtain ⟨L', hlen, hL'⟩ := matrix3_tensor_rank_le_of_surjective f hf L.length ⟨L, le_rfl, hL⟩
  3. 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.

    line 4

      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

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