AFTD Auto-Formalizing Theoretical Domains

matrix3_tensor_rank_le_pred_of_shared_v_w

theoremverified

If a valid decomposition has length at most r and contains two triads sharing v and w, then the tensor rank of 3x3 matrix multiplication over R is at most r - 1.

Statement

theorem matrix3_tensor_rank_le_pred_of_shared_v_w {R : Type*} [CommSemiring R]
    (r : ℕ) (L₁ L₂ L₃ : List (Matrix3Triad R)) (t₁ t₂ : Matrix3Triad R)
    (hv : t₁.v = t₂.v) (hw : t₁.w = t₂.w)
    (hlen : (L₁ ++ t₁ :: L₂ ++ t₂ :: L₃).length ≤ r)
    (hval : is_valid_matrix3_decomposition (L₁ ++ t₁ :: L₂ ++ t₂ :: L₃)) :
    matrix3_tensor_rank_le R (r - 1)
Source
step towards matrix3_tensor_rank_int_le_22
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • matrix3_shorter_valid_of_shared_v_wIf a list of triads written as L₁ ++ t₁ :: L₂ ++ t₂ :: L₃ is a valid decomposition of matrix multiplication, and t₁ and t₂ have the same v…
  • 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.
  • 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…

The proof, explained

The proof constructs a shorter valid decomposition by combining the two triads that share both their v and w factors, via the lemma matrix3_shorter_valid_of_shared_v_w. Since the original decomposition has length at most r, this strictly shorter decomposition has length strictly less than r, and hence at most r - 1. This shorter decomposition witnesses that the tensor rank is at most r - 1.

  1. There exists a valid decomposition L' strictly shorter than the given decomposition L₁ ++ t₁ :: L₂ ++ t₂ :: L₃.

    Because the two triads t₁ and t₂ in the decomposition share the same v and w matrices (hv and hw), they can be combined into a single triad by summing their u matrices. Invoking matrix3_shorter_valid_of_shared_v_w yields such a valid decomposition L' whose length is strictly smaller than the original list's length.

    line 8

    uses matrix3_shorter_valid_of_shared_v_w

      obtain ⟨L', hLt, hval'⟩ := matrix3_shorter_valid_of_shared_v_w L₁ L₂ L₃ t₁ t₂ hv hw hval
  2. The tensor rank of 3x3 matrix multiplication over R is at most r - 1.

    By definition, matrix3_tensor_rank_le R (r - 1) requires a valid decomposition of length at most r - 1. We provide L' as the witness: since its length is strictly less than that of the original decomposition, which itself is at most r (hlen), lt_of_lt_of_le gives length(L') < r. By Nat.le_sub_one_of_lt, this implies length(L') ≤ r - 1, which alongside the validity of L' concludes the proof.

    line 9

    uses Nat.le_sub_one_of_lt, lt_of_lt_of_le

      exact ⟨L', Nat.le_sub_one_of_lt (lt_of_lt_of_le hLt hlen), hval'⟩
matrix3_shorter_valid_of_shared_v_w
If a valid matrix multiplication decomposition contains two triads with identical v and w matrices, there exists a strictly shorter valid decomposition.
lt_of_lt_of_le
Strict inequality is transitive with non-strict inequality: if a < b and b ≤ c, then a < c.
Nat.le_sub_one_of_lt
For natural numbers, if a < b, then a ≤ b - 1.

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

/-- If a valid decomposition has length at most r and contains two triads sharing v and w, then the tensor rank of 3x3 matrix multiplication over R is at most r - 1. -/theorem matrix3_tensor_rank_le_pred_of_shared_v_w {R : Type*} [CommSemiring R]    (r : ℕ) (L₁ L₂ L₃ : List (Matrix3Triad R)) (t₁ t₂ : Matrix3Triad R)    (hv : t₁.v = t₂.v) (hw : t₁.w = t₂.w)    (hlen : (L₁ ++ t₁ :: L₂ ++ t₂ :: L₃).length ≤ r)    (hval : is_valid_matrix3_decomposition (L₁ ++ t₁ :: L₂ ++ t₂ :: L₃)) :    matrix3_tensor_rank_le R (r - 1) := by  obtain ⟨L', hLt, hval'⟩ := matrix3_shorter_valid_of_shared_v_w L₁ L₂ L₃ t₁ t₂ hv hw hval  exact ⟨L', Nat.le_sub_one_of_lt (lt_of_lt_of_le hLt hlen), hval'⟩
See it in the graphDiscuss this resultChallenge it