matrix3_tensor_rank_le_pred_of_shared_u_w
If a valid decomposition has length at most r and contains two triads sharing u 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_u_w {R : Type*} [CommSemiring R] (r : ℕ) (L₁ L₂ L₃ : List (Matrix3Triad R)) (t₁ t₂ : Matrix3Triad R) (hu : t₁.u = t₂.u) (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
- 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_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 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 argument exhibits an explicit decomposition witness of length at most $r - 1$. Because two triads in the given decomposition share their $u$ and $w$ factors, the lemma `matrix3_shorter_valid_of_shared_u_w` can combine them into a single triad, yielding a strictly shorter valid decomposition $L'$. Since the original decomposition has length at most $r$, the shortened decomposition has length at most $r - 1$, proving the upper bound on the tensor rank.
There exists a valid decomposition $L'$ whose length is strictly less than that of the original decomposition.
Applying `matrix3_shorter_valid_of_shared_u_w` using the assumptions that triads $t_1$ and $t_2$ share their $u$ and $w$ matrices (`hu` and `hw`) and that the original list is a valid decomposition (`hval`) produces a strictly shorter list of triads $L'$ (`hlt`) that remains a valid decomposition (`hval'`).
uses
matrix3_shorter_valid_of_shared_u_wobtain ⟨L', hlt, hval'⟩ := matrix3_shorter_valid_of_shared_u_w L₁ L₂ L₃ t₁ t₂ hu hw hvalThe tensor rank of $3 \times 3$ matrix multiplication over $R$ is at most $r - 1$. automation
By definition, the tensor rank is at most $r - 1$ if there exists a valid decomposition of length at most $r - 1$. The list $L'$ serves as the required witness: it is valid by `hval'`, and linear integer arithmetic (`omega`) establishes that $|L'| \le r - 1$ since $|L'| < |L_1 ++ t_1 :: L_2 ++ t_2 :: L_3| \le r$.
exact ⟨L', by omega, hval'⟩
matrix3_shorter_valid_of_shared_u_w- If a valid $3 \times 3$ matrix multiplication decomposition contains two triads sharing their first and third components ($u$ and $w$), there exists a valid decomposition of strictly shorter length.
- The arithmetic inequality on list lengths, namely that $|L'| \le r - 1$ follows from $|L'| < |L|$ and $|L| \le r$, is resolved automatically by the `omega` tactic.
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
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.
/-- Tensor rank bound decreases by at least 1 when a valid decomposition contains two triads sharing u and w. -/theorem matrix3_tensor_rank_le_pred_of_shared_u_w {R : Type*} [CommSemiring R] (r : ℕ) (L₁ L₂ L₃ : List (Matrix3Triad R)) (t₁ t₂ : Matrix3Triad R) (hu : t₁.u = t₂.u) (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_u_w L₁ L₂ L₃ t₁ t₂ hu hw hval exact ⟨L', by omega, hval'⟩