AFTD Auto-Formalizing Theoretical Domains

matrix3_tensor_rank_le_pred_of_shared_u_w

theoremverified

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.

  1. 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'`).

    lines 8–9

    uses matrix3_shorter_valid_of_shared_u_w

      obtain ⟨L', hlt, hval'⟩ :=
        matrix3_shorter_valid_of_shared_u_w L₁ L₂ L₃ t₁ t₂ hu hw hval
  2. The 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$.

    line 10

      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.

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

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