matrix3_unit_check_int_eq_true_iff
The computable integer checker matrix3_unit_check_int is true if and only if the list agrees with matrix multiplication on all 81 pairs of 3x3 standard basis units.
Statement
theorem matrix3_unit_check_int_eq_true_iff (L : List (Matrix3Triad ℤ)) :
matrix3_unit_check_int L = true ↔
∀ i j k l : Fin 3,
eval_matrix3_decomposition L (Matrix.single i j (1 : ℤ)) (Matrix.single k l (1 : ℤ))
= Matrix.single i j (1 : ℤ) * Matrix.single k l (1 : ℤ)- Source
- step towards matrix3_tensor_rank_int_le_22
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- matrix3_unit_check_intA computable Bool-valued checker that tests a list L of triads over ℤ against all 81 pairs of 3x3 matrix units: it returns true exactly…
- 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_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
- matrix3_tensor_rank_le_int_iff_unit_checkThe tensor rank of 3x3 matrix multiplication over ℤ is at most r if and only if there exists a list of at most r triads whose computable…
- matrix3_unit_check_int_witnessesThe checker matrix3_unit_check_int returns true on the classical 23-triad integer decomposition and false on the empty list.
The proof, explained
The proof unfolds the definition of `matrix3_unit_check_int` and simplifies using standard list and boolean equivalence lemmas. The checker is defined by four nested `List.all` loops over `List.finRange 3` verifying whether the boolean decision `decide` of the matrix equality is `true`. The simplifier converts each `List.all` over the exhaustive range into an unbounded universal quantifier over `Fin 3` and reduces `decide P = true` directly to the proposition `P`.
`matrix3_unit_check_int L = true` if and only if the decomposition evaluated on basis elements `Matrix.single i j 1` and `Matrix.single k l 1` equals their product for all `i, j, k, l : Fin 3`.
Unfolding the definition of `matrix3_unit_check_int` expresses the boolean check as four nested calls to `List.all` over `List.finRange 3`, testing `decide (...) = true`. The simplifier applies `List.all_eq_true` to turn each list check into a bounded universal quantification. Because `List.mem_finRange` proves that every index in `Fin 3` belongs to `List.finRange 3`, these bounded quantifications simplify directly to universal quantifications `∀ (i j k l : Fin 3)`. Finally, `decide_eq_true_eq` simplifies `decide P = true` to the underlying equality `P`.
uses
matrix3_unit_check_int,List.all_eq_true,List.mem_finRange,decide_eq_true_eqsimp [matrix3_unit_check_int, List.all_eq_true, List.mem_finRange, decide_eq_true_eq]
matrix3_unit_check_int- The definition of the verification function, which tests equality on all 81 basis pairs by checking whether `decide` of the equality holds across four nested `List.all` calls over `List.finRange 3`.
List.all_eq_true- A list satisfies `l.all p = true` if and only if `p x = true` for every element `x ∈ l`.
List.mem_finRange- Every element `x` of `Fin n` belongs to the list `List.finRange n`.
decide_eq_true_eq- For any decidable proposition `p`, the boolean value `decide p` is `true` if and only if `p` holds.
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.
/-- The computable integer checker matrix3_unit_check_int is true if and only if the list agrees with matrix multiplication on all 81 pairs of 3x3 standard basis units. -/theorem matrix3_unit_check_int_eq_true_iff (L : List (Matrix3Triad ℤ)) : matrix3_unit_check_int L = true ↔ ∀ i j k l : Fin 3, eval_matrix3_decomposition L (Matrix.single i j (1 : ℤ)) (Matrix.single k l (1 : ℤ)) = Matrix.single i j (1 : ℤ) * Matrix.single k l (1 : ℤ) := by simp [matrix3_unit_check_int, List.all_eq_true, List.mem_finRange, decide_eq_true_eq]