AFTD Auto-Formalizing Theoretical Domains

matrix3_shorter_valid_of_shared_u_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 u and the same w, then there is a valid decomposition with strictly fewer triads (namely L₁ ++ ⟨t₁.u, t₁.v + t₂.v, t₁.w⟩ :: (L₂ ++ L₃)).

Statement

theorem matrix3_shorter_valid_of_shared_u_w {R : Type*} [CommSemiring R]
    (L₁ L₂ L₃ : List (Matrix3Triad R)) (t₁ t₂ : Matrix3Triad R)
    (hu : t₁.u = t₂.u) (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_zmod2_le_22
Verified
23 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • 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…
  • 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_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…
  • 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…
Used by 2

The proof, explained

The proof shows that any valid triad decomposition containing two triads t₁ and t₂ that share the same u and w components can be compressed into a strictly shorter valid decomposition by merging them into a single triad ⟨t₁.u, t₁.v + t₂.v, t₁.w⟩. Because two list entries are replaced by one, the length strictly decreases. By bilinearity of triad evaluation (`matrix3_eval_triad_merge`), the evaluation of the merged triad equals the sum of the evaluations of t₁ and t₂, so the total evaluation sum over all triads is preserved and continues to compute A * B.

  1. There exists a candidate decomposition L' = L₁ ++ ⟨t₁.u, t₁.v + t₂.v, t₁.w⟩ :: (L₂ ++ L₃) whose length is strictly less than that of the original list, leaving only its validity to be shown.

    We provide L' as the witness. While the original list contains both t₁ and t₂ (separated by L₂), the candidate list L' combines them into a single merged triad ⟨t₁.u, t₁.v + t₂.v, t₁.w⟩. Thus, L' has length |L₁| + 1 + |L₂| + |L₃|, which is strictly smaller than the original length |L₁| + 1 + |L₂| + 1 + |L₃|; this inequality is verified by simplification (`simp`).

    line 8

      refine ⟨L₁ ++ ⟨t₁.u, t₁.v + t₂.v, t₁.w⟩ :: (L₂ ++ L₃), by simp, ?_⟩
  2. It suffices to show that evaluating the candidate decomposition on arbitrary 3 × 3 matrices A and B produces A * B.

    By definition, a triad list is a valid decomposition if its evaluation on any pair of matrices A and B yields their matrix product A * B. We introduce arbitrary matrices A and B into the context.

    line 9

      intro A B
  3. The sum of the evaluations of t₁ and t₂ on A and B equals the evaluation of the merged triad: eval(t₁, A, B) + eval(t₂, A, B) = eval(⟨t₁.u, t₁.v + t₂.v, t₁.w⟩, A, B).

    The first clause of `matrix3_eval_triad_merge` asserts that evaluating two triads that agree in u and w and adding the results is equivalent to evaluating a single triad with the sum of their v components. Decomposing t₁ and t₂ into their components (`cases`), simplifying projections (`dsimp`), and substituting the hypotheses hu (t₁.u = t₂.u) and hw (t₁.w = t₂.w) aligns the triads with this lemma.

    lines 10–17

    uses matrix3_eval_triad_merge

      have hmerge : eval_matrix3_triad t₁ A B + eval_matrix3_triad t₂ A B =
          eval_matrix3_triad ⟨t₁.u, t₁.v + t₂.v, t₁.w⟩ A B := by
        have := (matrix3_eval_triad_merge t₁.u t₂.u t₁.v t₂.v t₁.w t₂.w A B).1
        cases t₁
        cases t₂
        dsimp at hu hw ⊢
        subst hu hw
        exact this
  4. The evaluation of the candidate decomposition on A and B is rewritten as the sum of evaluations over L₁, t₁, t₂, L₂, and L₃.

    Unfolding the definition `eval_matrix3_decomposition` expresses the evaluation as the sum of the evaluations of the list's triads. Using `List.map_append`, `List.map_cons`, `List.sum_append`, and `List.sum_cons`, the sum distributes over list concatenation and cons into terms for L₁, the merged triad, L₂, and L₃. Rewriting with `hmerge` in reverse replaces the merged triad's evaluation by eval(t₁, A, B) + eval(t₂, A, B).

    lines 18–19

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

      simp only [eval_matrix3_decomposition, List.map_append, List.map_cons, List.sum_append, List.sum_cons]
      rw [← hmerge]
  5. The target product A * B is rewritten as the sum of triad evaluations over L₁, t₁, L₂, t₂, and L₃ from the original decomposition.

    Specializing the validity hypothesis h of the original list to matrices A and B yields eval_matrix3_decomposition (L₁ ++ t₁ :: L₂ ++ t₂ :: L₃) A B = A * B. Distributing the list map and summation across the original decomposition via `eval_matrix3_decomposition`, `List.map_append`, `List.map_cons`, `List.sum_append`, and `List.sum_cons` expands A * B into the sum over L₁, t₁, L₂, t₂, and L₃. Rewriting by this identity substitutes the expanded sum for A * B in the goal.

    lines 20–22

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

      have h_orig : eval_matrix3_decomposition (L₁ ++ t₁ :: L₂ ++ t₂ :: L₃) A B = A * B := h A B
      simp only [eval_matrix3_decomposition, List.map_append, List.map_cons, List.sum_append, List.sum_cons] at h_orig
      rw [← h_orig]
  6. The evaluation of the candidate decomposition equals A * B.

    Both sides of the equation are now sums of the exact same five matrix terms—the sum over L₁, the evaluation of t₁, the evaluation of t₂, the sum over L₂, and the sum over L₃—differing only in their grouping and order of addition. The `abel` tactic closes the goal by associativity and commutativity of addition in the abelian group of matrices.

    line 23

      abel
matrix3_eval_triad_merge
Evaluating two triads that share the same u and w matrices and adding the results is equal to evaluating the single triad formed by adding their v matrices (with analogous merge identities for shared v, w or shared u, v).
eval_matrix3_decomposition
The evaluation of a decomposition list on matrices A and B is defined as the sum of the evaluations of its constituent triads on A and B.
List.map_append
Mapping a function over the concatenation of two lists equals the concatenation of the results of mapping over each list separately.
List.map_cons
Mapping a function over a list with head a and tail l equals f(a) prepended to the result of mapping over l.
List.sum_append
The sum of elements in the concatenation of two lists equals the sum of the elements in the first list plus the sum of the elements in the second list.
List.sum_cons
The sum of elements in a list with head a and tail l equals a plus the sum of elements in l.

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

/-- A valid list containing two triads that share u and w can be replaced by a strictly shorter valid list (merge them and drop one product). -/theorem matrix3_shorter_valid_of_shared_u_w {R : Type*} [CommSemiring R]    (L₁ L₂ L₃ : List (Matrix3Triad R)) (t₁ t₂ : Matrix3Triad R)    (hu : t₁.u = t₂.u) (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₁.v + t₂.v, t₁.w⟩ :: (L₂ ++ L₃), by simp, ?_⟩  intro A B  have hmerge : eval_matrix3_triad t₁ A B + eval_matrix3_triad t₂ A B =      eval_matrix3_triad ⟨t₁.u, t₁.v + t₂.v, t₁.w⟩ A B := by    have := (matrix3_eval_triad_merge t₁.u t₂.u t₁.v t₂.v t₁.w t₂.w A B).1    cases t₁    cases t₂    dsimp at hu hw ⊢    subst hu hw    exact this  simp only [eval_matrix3_decomposition, List.map_append, List.map_cons, List.sum_append, List.sum_cons]  rw [← hmerge]  have h_orig : eval_matrix3_decomposition (L₁ ++ t₁ :: L₂ ++ t₂ :: L₃) A B = A * B := h A B  simp only [eval_matrix3_decomposition, List.map_append, List.map_cons, List.sum_append, List.sum_cons] at h_orig  rw [← h_orig]  abel
See it in the graphDiscuss this resultChallenge it