matrix3_tensor_rank_le_zmod2_iff_unit_check
For every natural number r, 3x3 matrix multiplication over ZMod 2 has a valid decomposition with at most r triads if and only if there is a list L of at most r triads over ZMod 2 whose computable unit check matrix3_unit_check L is true.
Statement
theorem matrix3_tensor_rank_le_zmod2_iff_unit_check (r : ℕ) :
matrix3_tensor_rank_le (ZMod 2) r ↔
∃ L : List (Matrix3Triad (ZMod 2)), L.length ≤ r ∧ matrix3_unit_check L = true- Source
- step towards matrix3_tensor_rank_zmod2_le_22
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- 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.
- 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…
- 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.
- matrix3_tensor_rank_leFor a commutative semiring R and a natural number r, matrix3_tensor_rank_le R r asserts that there exists a list L of elements of…
- 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_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…
The proof, explained
The equivalence is proved by establishing both directions. In the forward direction, a valid triad decomposition correctly multiplies all pairs of matrices, so in particular it correctly multiplies all standard basis matrices, which by `matrix3_unit_check_eq_true_iff` makes the computable unit check evaluate to true. In the reverse direction, if a triad list passes the unit check, it is correct on all standard basis matrices, which by `matrix3_valid_of_unit_checks` is sufficient by bilinearity to guarantee validity on all matrices.
If the 3×3 matrix multiplication tensor over ℤ/2ℤ has rank at most r, then there exists a list of at most r triads whose computable unit check evaluates to true.
We split the equivalence into both directions. In the forward direction, assuming the tensor rank is at most r, there exists a decomposition L of length at most r that correctly multiplies all matrices. Taking L as the witness, its length is bounded by r. By `matrix3_unit_check_eq_true_iff`, the computable unit check returns true if and only if L correctly multiplies every pair of standard basis matrices. Since L is valid for all pairs of matrices by assumption, evaluating on any basis matrices completes this direction.
uses
matrix3_unit_check_eq_true_iffconstructor · rintro ⟨L, hlen, hval⟩ refine ⟨L, hlen, ?_⟩ rw [matrix3_unit_check_eq_true_iff] intro i j k l exact hval _ _
Conversely, if there is a list of at most r triads whose computable unit check evaluates to true, then the 3×3 matrix multiplication tensor over ℤ/2ℤ has rank at most r.
In the reverse direction, suppose there is a list L of at most r triads satisfying the unit check. We provide L as the witness of length at most r and must show that it is a valid decomposition. Rewriting the unit check hypothesis using `matrix3_unit_check_eq_true_iff` states that L correctly multiplies all pairs of standard basis matrices. Applying `matrix3_valid_of_unit_checks`, correct multiplication on all basis matrices extends by bilinearity to all matrices, proving that L is a valid decomposition.
uses
matrix3_unit_check_eq_true_iff,matrix3_valid_of_unit_checks· rintro ⟨L, hlen, hchk⟩ refine ⟨L, hlen, ?_⟩ rw [matrix3_unit_check_eq_true_iff] at hchk exact matrix3_valid_of_unit_checks L hchk
matrix3_unit_check_eq_true_iff- The computable check `matrix3_unit_check L` evaluates to `true` if and only if the decomposition `L` correctly multiplies every pair of standard basis matrices.
matrix3_valid_of_unit_checks- If a triad decomposition `L` correctly multiplies every pair of standard basis matrices, then by bilinearity it correctly multiplies all pairs of matrices, so it is a valid decomposition.
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.
/-- Over ZMod 2 the tensor-rank bound is exactly the existence of a short triad list whose computable unit check is true, i.e. the target becomes a finite Bool search over lists of at most r triads. -/theorem matrix3_tensor_rank_le_zmod2_iff_unit_check (r : ℕ) : matrix3_tensor_rank_le (ZMod 2) r ↔ ∃ L : List (Matrix3Triad (ZMod 2)), L.length ≤ r ∧ matrix3_unit_check L = true := by constructor · rintro ⟨L, hlen, hval⟩ refine ⟨L, hlen, ?_⟩ rw [matrix3_unit_check_eq_true_iff] intro i j k l exact hval _ _ · rintro ⟨L, hlen, hchk⟩ refine ⟨L, hlen, ?_⟩ rw [matrix3_unit_check_eq_true_iff] at hchk exact matrix3_valid_of_unit_checks L hchk