AFTD Auto-Formalizing Theoretical Domains

matrix3_shorter_valid_of_shared_v_w

theoremverified

If 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 and the same w, then there is a valid decomposition with strictly fewer triads (merging their u matrices).

Statement

theorem matrix3_shorter_valid_of_shared_v_w {R : Type*} [CommSemiring R]
    (L₁ L₂ L₃ : List (Matrix3Triad R)) (t₁ t₂ : Matrix3Triad R)
    (hv : t₁.v = t₂.v) (hw : t₁.w = t₂.w)
    (h : is_valid_matrix3_decomposition (L₁ ++ t₁ :: L₂ ++ t₂ :: L₃)) :
    ∃ L' : List (Matrix3Triad R),
      L'.length < (L₁ ++ t₁ :: L₂ ++ t₂ :: L₃).length ∧ is_valid_matrix3_decomposition L'
Source
step towards matrix3_tensor_rank_int_le_22
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • 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…
  • eval_matrix3_decompositionGiven a commutative semiring R, a list L of Matrix3Triad R, and 3x3 matrices A and B over R, eval_matrix3_decomposition L A B is the sum…
  • eval_matrix3_triadGiven a commutative semiring R, a triad t of type Matrix3Triad R, and 3x3 matrices A and B over R, eval_matrix3_triad t A B is the scalar…
  • matrix3_eval_triad_mergeTwo triads that agree in two of their three slots can be replaced by a single triad: if they share u and w their v's add, if they share v…
Used by 1

The proof, explained

The proof constructs an explicit shortened list of triads by replacing t₁ and t₂ with a single triad whose u-component is t₁.u + t₂.u and whose v and w components are the shared ones. This list is strictly shorter because two triads are merged into one. Its validity follows from the linearity of triad evaluation: when two triads agree on their v and w components, their evaluations sum linearly in the u-component, so the total sum of triad evaluations is preserved.

  1. We witness the existence of a shorter valid decomposition by merging t₁ and t₂ into ⟨t₁.u + t₂.u, t₁.v, t₁.w⟩.

    We construct the candidate list L' = L₁ ++ ⟨t₁.u + t₂.u, t₁.v, t₁.w⟩ :: (L₂ ++ L₃), replacing the two separate triads t₁ and t₂ with a single merged triad and concatenating the remaining segments. This leaves two subgoals: showing that the new list is strictly shorter, and showing that it remains a valid decomposition.

    line 8

      refine ⟨L₁ ++ ⟨t₁.u + t₂.u, t₁.v, t₁.w⟩ :: (L₂ ++ L₃), ?_, ?_⟩
  2. The candidate list has strictly shorter length than the original list.

    Simplification using List.length_append and List.length_cons expands the length of the new list to |L₁| + 1 + |L₂| + |L₃| and that of the original list to |L₁| + 1 + |L₂| + 1 + |L₃|, reducing the goal to |L₁| + |L₂| + |L₃| + 1 < |L₁| + |L₂| + |L₃| + 2, which holds trivially.

    line 9

    uses List.length_append, List.length_cons

      · simp [List.length_append, List.length_cons]
  3. To establish validity, it suffices to show that evaluating the candidate list on arbitrary matrices A and B yields A * B.

    By definition of is_valid_matrix3_decomposition, a list of triads is valid if its evaluation equals the matrix product A * B for all pairs of matrices A and B. We introduce arbitrary 3 × 3 matrices A and B.

    line 10

      · intro A B
  4. The triads t₁ and t₂ can be expressed in constructor form as ⟨t₁.u, t₁.v, t₁.w⟩ and ⟨t₂.u, t₁.v, t₁.w⟩.

    Decomposing t₁ into its constructor fields gives t₁ = ⟨t₁.u, t₁.v, t₁.w⟩ definitionally. Similarly, decomposing t₂ and rewriting with the hypotheses t₁.v = t₂.v (hv) and t₁.w = t₂.w (hw) expresses t₂ using the v and w components of t₁.

    lines 11–12

        have ht1 : t₁ = ⟨t₁.u, t₁.v, t₁.w⟩ := by cases t₁; rfl
        have ht2 : t₂ = ⟨t₂.u, t₁.v, t₁.w⟩ := by cases t₂; simp [hv, hw]
  5. The sum of the evaluations of t₁ and t₂ equals the evaluation of the merged triad ⟨t₁.u + t₂.u, t₁.v, t₁.w⟩ on (A, B).

    Rewriting t₁ and t₂ with their explicit component forms, the result follows from the linearity of triad evaluation in the u-component, given by the second conjunct of matrix3_eval_triad_merge.

    lines 13–16

    uses matrix3_eval_triad_merge

        have h1 : eval_matrix3_triad t₁ A B + eval_matrix3_triad t₂ A B
            = eval_matrix3_triad ⟨t₁.u + t₂.u, t₁.v, t₁.w⟩ A B := by
          rw [ht1, ht2]
          exact (matrix3_eval_triad_merge t₁.u t₂.u t₁.v t₂.v t₁.w t₂.w A B).2.1
  6. The evaluation of the candidate list on A and B equals A * B.

    From the validity hypothesis h, A * B equals the evaluation of the original list. By unfolding eval_matrix3_decomposition and distributing the mapping and summation over list concatenation and cons (List.map_append, List.map_cons, List.sum_append, List.sum_cons), both list evaluations expand into sums of individual triad evaluations. Replacing the merged triad evaluation by the sum of evaluations of t₁ and t₂ via the previously established identity leaves identical terms on both sides, which match by associativity and commutativity of addition (ac_rfl).

    lines 17–22

    uses List.map_append, List.map_cons, List.sum_append, List.sum_cons

        have hh := h A B
        rw [← hh]
        unfold eval_matrix3_decomposition
        simp only [List.map_append, List.map_cons, List.sum_append, List.sum_cons]
        rw [← h1]
        ac_rfl
List.length_append
The length of the concatenation of two lists is the sum of their lengths: |as ++ bs| = |as| + |bs|.
List.length_cons
Prepending an element to a list increases its length by 1: |a :: as| = |as| + 1.
matrix3_eval_triad_merge
Triad evaluation is linear in each component when the other two are identical; in particular, evaluating ⟨u₁, v₁, w₁⟩ plus evaluating ⟨u₂, v₁, w₁⟩ equals evaluating ⟨u₁ + u₂, v₁, w₁⟩.
List.map_append
Mapping a function over the concatenation of two lists distributes over concatenation: map f (l₁ ++ l₂) = map f l₁ ++ map f l₂.
List.map_cons
Mapping a function over a cons list applies the function to the head: map f (a :: l) = f a :: map f l.
List.sum_append
The sum of elements in the concatenation of two lists is the sum of their individual sums: (l₁ ++ l₂).sum = l₁.sum + l₂.sum.
List.sum_cons
The sum of a cons list adds the head to the sum of the tail: (a :: l).sum = a + l.sum.

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

/-- Valid 3x3 triad decompositions can be shortened by merging two triads sharing v and w components. -/theorem matrix3_shorter_valid_of_shared_v_w {R : Type*} [CommSemiring R]    (L₁ L₂ L₃ : List (Matrix3Triad R)) (t₁ t₂ : Matrix3Triad R)    (hv : t₁.v = t₂.v) (hw : t₁.w = t₂.w)    (h : is_valid_matrix3_decomposition (L₁ ++ t₁ :: L₂ ++ t₂ :: L₃)) :    ∃ L' : List (Matrix3Triad R),      L'.length < (L₁ ++ t₁ :: L₂ ++ t₂ :: L₃).length ∧ is_valid_matrix3_decomposition L' := by  refine ⟨L₁ ++ ⟨t₁.u + t₂.u, t₁.v, t₁.w⟩ :: (L₂ ++ L₃), ?_, ?_⟩  · simp [List.length_append, List.length_cons]  · intro A B    have ht1 : t₁ = ⟨t₁.u, t₁.v, t₁.w⟩ := by cases t₁; rfl    have ht2 : t₂ = ⟨t₂.u, t₁.v, t₁.w⟩ := by cases t₂; simp [hv, hw]    have h1 : eval_matrix3_triad t₁ A B + eval_matrix3_triad t₂ A B        = eval_matrix3_triad ⟨t₁.u + t₂.u, t₁.v, t₁.w⟩ A B := by      rw [ht1, ht2]      exact (matrix3_eval_triad_merge t₁.u t₂.u t₁.v t₂.v t₁.w t₂.w A B).2.1    have hh := h A B    rw [← hh]    unfold eval_matrix3_decomposition    simp only [List.map_append, List.map_cons, List.sum_append, List.sum_cons]    rw [← h1]    ac_rfl
See it in the graphDiscuss this resultChallenge it