AFTD Auto-Formalizing Theoretical Domains

eval_matrix3_decomposition_sum_right

theoremverified

Given a commutative semiring R, a finite set s, a list L of triads, a matrix A, and a family of matrices G, evaluating L on A and (∑ i ∈ s, G i) equals ∑ i ∈ s, eval_matrix3_decomposition L A (G i).

Statement

theorem eval_matrix3_decomposition_sum_right {R : Type*} [CommSemiring R] {ι : Type*} (s : Finset ι) (L : List (Matrix3Triad R)) (A : Matrix (Fin 3) (Fin 3) R) (G : ι → Matrix (Fin 3) (Fin 3) R) : eval_matrix3_decomposition L A (∑ i ∈ s, G i) = ∑ i ∈ s, eval_matrix3_decomposition L A (G i)
Source
step towards matrix3_tensor_rank_int_le_22
Verified
23 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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_decomposition_add_rightGiven a commutative semiring R, a list L of Matrix3Triad R, and matrices A, B₁, and B₂, eval_matrix3_decomposition L A (B₁ + B₂) equals…
  • 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.
  • 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…
Used by 1
  • matrix3_valid_of_unit_checksIf a list L of triads over a commutative semiring R evaluates to matrix multiplication on all 81 pairs of matrix units, then L is a valid…

The proof, explained

The theorem is proved by finite set induction on s using `Finset.induction_on`. The base case of the empty set reduces to evaluating the decomposition on the zero matrix, which is zero. In the inductive step, the sum over insert a s is split using `Finset.sum_insert`, distributed across the addition using the right-additivity lemma `eval_matrix3_decomposition_add_right`, and closed using the induction hypothesis.

  1. It suffices to prove the identity when s is empty and when a new element is inserted into s.

    We invoke classical logic to obtain decidable equality on the index type ι, and set up an induction on the finite set s using the induction principle `Finset.induction_on`.

    lines 3–4

    uses Finset.induction_on

      classical
      induction s using Finset.induction_on with
  2. The identity holds when s is the empty set. automation

    When s = ∅, the sum of matrices on the left is the zero matrix, and evaluating the decomposition on the zero matrix yields zero. On the right, the sum over the empty set is also zero. The simplifier unfolds the definitions of `eval_matrix3_decomposition` and `eval_matrix3_triad` and computes that both sides equal zero.

    lines 5–6

    uses eval_matrix3_decomposition, eval_matrix3_triad

      | empty =>
        simp [eval_matrix3_decomposition, eval_matrix3_triad]
  3. The identity holds for insert a s, completing the induction.

    Assuming a ∉ s and the induction hypothesis for s, we separate the a-term from both sums using `Finset.sum_insert`. The left-hand side becomes the evaluation on G(a) + ∑ i ∈ s, G(i). By right-additivity (`eval_matrix3_decomposition_add_right`), this decomposes into the evaluation on G(a) plus the evaluation on ∑ i ∈ s, G(i). Replacing the latter using the induction hypothesis matches the right-hand side.

    lines 7–8

    uses Finset.sum_insert, eval_matrix3_decomposition_add_right

      | insert a s ha ih =>
        rw [Finset.sum_insert ha, Finset.sum_insert ha, eval_matrix3_decomposition_add_right, ih]
Finset.induction_on
The induction principle for finite sets: a property holds for all finite sets if it holds for the empty set and is preserved under adjoining a new element.
eval_matrix3_decomposition
Evaluating a list of triads on matrices A and B computes the sum of the individual triad evaluations over the list.
eval_matrix3_triad
Evaluating a triad (u, v, w) on matrices A and B produces the scalar (∑ uᵢⱼ Aᵢⱼ)(∑ vᵢⱼ Bᵢⱼ) multiplied by w.
Finset.sum_insert
Splitting off an element from a sum over a finite set: if a ∉ s, then ∑ x ∈ insert a s, f x = f a + ∑ x ∈ s, f x.
eval_matrix3_decomposition_add_right
Evaluation of a triad decomposition is additive in its right matrix argument: eval L A (B₁ + B₂) = eval L A B₁ + eval L A B₂.

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

/-- Evaluation of a triad decomposition distributes over finite sums in the right matrix argument. -/theorem eval_matrix3_decomposition_sum_right {R : Type*} [CommSemiring R] {ι : Type*} (s : Finset ι) (L : List (Matrix3Triad R)) (A : Matrix (Fin 3) (Fin 3) R) (G : ι → Matrix (Fin 3) (Fin 3) R) : eval_matrix3_decomposition L A (∑ i ∈ s, G i) = ∑ i ∈ s, eval_matrix3_decomposition L A (G i) := by  classical  induction s using Finset.induction_on with  | empty =>    simp [eval_matrix3_decomposition, eval_matrix3_triad]  | insert a s ha ih =>    rw [Finset.sum_insert ha, Finset.sum_insert ha, eval_matrix3_decomposition_add_right, ih]
See it in the graphDiscuss this resultChallenge it