AFTD Auto-Formalizing Theoretical Domains

matrix3_tensor_rank_le_pred_of_shared_u_v

theoremverified

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

Statement

theorem matrix3_tensor_rank_le_pred_of_shared_u_v {R : Type*} [CommSemiring R]
    (r : ℕ) (L₁ L₂ L₃ : List (Matrix3Triad R)) (t₁ t₂ : Matrix3Triad R)
    (hu : t₁.u = t₂.u) (hv : t₁.v = t₂.v)
    (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
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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.
  • matrix3_shorter_valid_of_shared_u_vIf 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 u…
  • 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…
  • 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 theorem establishes that the tensor rank is at most $r - 1$ by obtaining a strictly shorter valid decomposition $L'$ using `matrix3_shorter_valid_of_shared_u_v`, which merges the two triads sharing $u$ and $v$. Since the original decomposition has length at most $r$, the strictly shorter decomposition $L'$ has length at most $r - 1$, serving as the required witness for the tensor rank bound.

  1. There exists a valid decomposition L' whose length is strictly less than that of the given decomposition.

    Applying `matrix3_shorter_valid_of_shared_u_v` to the decomposition and the hypotheses that $t_1$ and $t_2$ share their $u$ and $v$ components produces a valid decomposition $L'$ with length strictly less than that of the original list $L_1 ++ t_1 :: L_2 ++ t_2 :: L_3$.

    line 8

    uses matrix3_shorter_valid_of_shared_u_v

      obtain ⟨L', hlt, hval'⟩ := matrix3_shorter_valid_of_shared_u_v L₁ L₂ L₃ t₁ t₂ hu hv hval
  2. The tensor rank of 3×3 matrix multiplication is at most r - 1.

    To show that the tensor rank is at most $r - 1$, it suffices to provide a valid decomposition of length at most $r - 1$. The list $L'$ witnesses this: it is valid by the previous step, and its length satisfies $|L'| \le r - 1$ by linear arithmetic (`omega`) from $|L'| < \mathrm{length}(\dots) \le r$.

    line 9

      exact ⟨L', by omega, hval'⟩
matrix3_shorter_valid_of_shared_u_v
If a valid decomposition contains two triads sharing identical u and v matrices, there exists a strictly shorter valid decomposition.

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 u and v, then the tensor rank of 3x3 matrix multiplication over R is at most r - 1. -/theorem matrix3_tensor_rank_le_pred_of_shared_u_v {R : Type*} [CommSemiring R]    (r : ℕ) (L₁ L₂ L₃ : List (Matrix3Triad R)) (t₁ t₂ : Matrix3Triad R)    (hu : t₁.u = t₂.u) (hv : t₁.v = t₂.v)    (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_u_v L₁ L₂ L₃ t₁ t₂ hu hv hval  exact ⟨L', by omega, hval'⟩
See it in the graphDiscuss this resultChallenge it