matrix3_unit_check_witnesses
The checker matrix3_unit_check returns true on the classical 23-triad decomposition of 3x3 matrix multiplication over ZMod 2 (so the verification pipeline is sound end to end), and returns false on the empty list (so it does not accept everything).
Statement
theorem matrix3_unit_check_witnesses :
matrix3_unit_check (matrix3_triads_23 (ZMod 2)) = true ∧
matrix3_unit_check ([] : List (Matrix3Triad (ZMod 2))) = false- Source
- step towards matrix3_tensor_rank_zmod2_le_22
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- matrix3_unit_checkA computable Bool-valued checker that tests a list L of triads over ZMod 2 against all 81 pairs of 3x3 matrix units: it returns true…
- matrix3_unit_check_eq_true_iffThe computable checker matrix3_unit_check is true exactly when the list agrees with matrix multiplication on every pair of 3x3 matrix units.
- 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…
- 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…
The proof, explained
The proof establishes both conjuncts directly in term mode as a pair. The first conjunct shows the checker accepts the classical 23-triad algorithm over ZMod 2: matrix3_unit_check_eq_true_iff reduces the check to verifying multiplication on all elementary basis matrices, which is immediately discharged by the general correctness theorem matrix3_triads_23_valid. The second conjunct shows the checker rejects the empty list, which evaluates to false by definition and is closed by reflexivity (rfl).
matrix3_unit_check returns true on the 23-triad decomposition over ZMod 2, and returns false on the empty list of triads.
The theorem is proven as a conjunction ⟨h₁, h₂⟩. For the first conjunct, matrix3_unit_check_eq_true_iff reduces the goal of showing that the checker returns true to verifying that the 23-triad decomposition correctly multiplies all pairs of elementary basis matrices Matrix.single i j 1 and Matrix.single k l 1. This condition follows directly from matrix3_triads_23_valid specialized to R = ZMod 2 and applied to the basis matrices. For the second conjunct, the empty decomposition evaluates to the zero matrix, which fails to match the non-zero product Matrix.single 0 0 1 * Matrix.single 0 0 1 = Matrix.single 0 0 1, so the checker computes to false by definition, verified by reflexivity (rfl).
uses
matrix3_unit_check_eq_true_iff,matrix3_triads_23_valid,rflmatrix3_unit_check ([] : List (Matrix3Triad (ZMod 2))) = false := ⟨(matrix3_unit_check_eq_true_iff _).2 fun _ _ _ _ => matrix3_triads_23_valid (ZMod 2) _ _, rfl⟩
matrix3_unit_check_eq_true_iff- A triad decomposition L satisfies the boolean checker matrix3_unit_check if and only if it correctly computes the product of every pair of elementary standard basis matrices over ZMod 2.
matrix3_triads_23_valid- The classical 23-triad decomposition is a valid decomposition for 3x3 matrix multiplication over any commutative ring R, meaning it correctly computes the product of any two matrices.
rfl- Equality is reflexive: for any expression a, a = a holds by definitional equality.
- The second conjunct holds entirely by definitional reduction: computing the empty list of triads on the first pair of basis elements yields the zero matrix rather than the non-zero product, causing the checker to evaluate to false definitionally, closed by rfl.
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
/-- Sanity witnesses for the checker: it returns true on the classical 23-triad algorithm and false on the empty list, so it is neither vacuously true nor vacuously false. -/theorem matrix3_unit_check_witnesses : matrix3_unit_check (matrix3_triads_23 (ZMod 2)) = true ∧ matrix3_unit_check ([] : List (Matrix3Triad (ZMod 2))) = false := ⟨(matrix3_unit_check_eq_true_iff _).2 fun _ _ _ _ => matrix3_triads_23_valid (ZMod 2) _ _, rfl⟩