matrix3_unit_check_int_witnesses
The checker matrix3_unit_check_int returns true on the classical 23-triad integer decomposition and false on the empty list.
Statement
theorem matrix3_unit_check_int_witnesses :
matrix3_unit_check_int (matrix3_triads_23 ℤ) = true ∧
matrix3_unit_check_int ([] : List (Matrix3Triad ℤ)) = false- Source
- step towards matrix3_tensor_rank_int_le_22
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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…
- matrix3_unit_check_int_eq_true_iffThe computable integer checker matrix3_unit_check_int is true if and only if the list agrees with matrix multiplication on all 81 pairs of…
- matrix3_tensor_rank_le_23_of_comm_ringOver every commutative ring R, 3x3 matrix multiplication has a valid bilinear decomposition with 23 products (the classical…
- 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…
- 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.
The proof, explained
The theorem shows that the integer matrix multiplication checker accepts a known valid 23-triad decomposition and rejects the empty list. The proof splits the conjunction into two subgoals: for the 23-triad decomposition, it characterises checker success as correctness on all standard basis matrices and applies the general validity theorem for the 23-triad scheme; for the empty list, it evaluates the checker by direct computation using `decide`.
The proof splits into two independent obligations: the checker returns true on the 23-triad decomposition, and false on the empty list.
Applying `constructor` on the conjunction decomposes the goal into proving `matrix3_unit_check_int (matrix3_triads_23 ℤ) = true` and `matrix3_unit_check_int [] = false`.
constructorThe checker returns true on the 23-triad integer decomposition.
Rewriting with `matrix3_unit_check_int_eq_true_iff` turns the Boolean condition into a universal statement: the decomposition must correctly compute the product of any two standard basis matrices E_{i,j} and E_{k,l}. Introducing arbitrary indices i, j, k, l, the claim is discharged immediately by `matrix3_triads_23_valid`, which states that the 23-triad decomposition correctly computes the product of all pairs of 3 × 3 matrices.
uses
matrix3_unit_check_int_eq_true_iff,matrix3_triads_23_valid· rw [matrix3_unit_check_int_eq_true_iff] intro i j k l exact matrix3_triads_23_valid ℤ _ _
The checker returns false on the empty list of triads. automation
The tactic `decide` evaluates the Boolean expression `matrix3_unit_check_int []` directly by computation. On an empty list of triads, the decomposition evaluates to the zero matrix for all inputs, which fails to match the product of basis matrices (for example, E_{0,0} * E_{0,0} = E_{0,0} ≠ 0), so the checker evaluates to `false`.
· decide
matrix3_unit_check_int_eq_true_iff- The integer checker returns true for a list of triads if and only if the decomposition correctly evaluates the product of all pairs of standard basis matrices E_{i,j} and E_{k,l} for i, j, k, l ∈ {0, 1, 2}.
matrix3_triads_23_valid- For any commutative ring R, the 23-triad decomposition is a valid decomposition of 3 × 3 matrix multiplication, meaning its evaluation on any two matrices A and B equals A * B.
- The second conjunct is verified purely by computational reflection: Lean's `decide` tactic evaluates the checker function on the empty list by executing its decidable algorithmic definition.
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 checker matrix3_unit_check_int returns true on the classical 23-triad integer decomposition and false on the empty list. -/theorem matrix3_unit_check_int_witnesses : matrix3_unit_check_int (matrix3_triads_23 ℤ) = true ∧ matrix3_unit_check_int ([] : List (Matrix3Triad ℤ)) = false := by constructor · rw [matrix3_unit_check_int_eq_true_iff] intro i j k l exact matrix3_triads_23_valid ℤ _ _ · decide