matrix3_tensor_rank_le_int_iff_unit_check
The 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 unit checker returns true.
Statement
theorem matrix3_tensor_rank_le_int_iff_unit_check (r : ℕ) :
matrix3_tensor_rank_le ℤ r ↔
∃ L : List (Matrix3Triad ℤ), L.length ≤ r ∧ matrix3_unit_check_int L = true- Source
- step towards matrix3_tensor_rank_int_le_22
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- 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…
- 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_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…
- 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…
- 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…
- 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 equivalence is established in two directions. In the forward direction, any decomposition of length at most r valid for all matrices in particular correctly multiplies all pairs of standard basis matrices, so the computable unit checker returns true. In the reverse direction, if the unit checker returns true for a list of at most r triads, the decomposition is correct on all standard basis matrices, which by multilinearity implies validity for all matrices and bounds the tensor rank by r.
If the tensor rank of 3x3 matrix multiplication over ℤ is at most r, then there exists a triad list of length at most r whose unit checker returns true.
To prove the equivalence, we first establish the forward direction. By the definition of `matrix3_tensor_rank_le`, a rank of at most r provides a list L of at most r triads that validly computes matrix multiplication for all matrices. By `matrix3_unit_check_int_eq_true_iff`, the unit checker `matrix3_unit_check_int L` returns true if and only if the decomposition is correct on all standard basis matrices `Matrix.single i j 1` and `Matrix.single k l 1`. Specializing the validity of L to these basis matrices completes this direction.
uses
matrix3_unit_check_int_eq_true_iffconstructor · rintro ⟨L, hlen, hval⟩ refine ⟨L, hlen, ?_⟩ rw [matrix3_unit_check_int_eq_true_iff] intro i j k l exact hval (Matrix.single i j 1) (Matrix.single k l 1)
Conversely, if there exists a triad list of length at most r whose unit checker returns true, then the tensor rank is at most r.
We now establish the reverse direction. Given a list L of at most r triads with `matrix3_unit_check_int L = true`, we must show that L is a valid decomposition for all matrices. By `matrix3_valid_of_unit_checks`, correctness on all pairs of standard basis matrices implies validity on all matrices. Rewriting this condition with `matrix3_unit_check_int_eq_true_iff` matches the assumption that the unit checker evaluates to true.
uses
matrix3_valid_of_unit_checks,matrix3_unit_check_int_eq_true_iff· rintro ⟨L, hlen, hchk⟩ refine ⟨L, hlen, ?_⟩ apply matrix3_valid_of_unit_checks rw [← matrix3_unit_check_int_eq_true_iff] exact hchk
matrix3_unit_check_int_eq_true_iff- The computable integer unit checker returns true for a list of triads if and only if the decomposition correctly evaluates matrix multiplication on all pairs of standard basis matrices.
matrix3_valid_of_unit_checks- If a decomposition correctly evaluates matrix multiplication on all pairs of standard basis matrices, then it is valid for all matrices.
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 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 unit checker returns true. -/theorem matrix3_tensor_rank_le_int_iff_unit_check (r : ℕ) : matrix3_tensor_rank_le ℤ r ↔ ∃ L : List (Matrix3Triad ℤ), L.length ≤ r ∧ matrix3_unit_check_int L = true := by constructor · rintro ⟨L, hlen, hval⟩ refine ⟨L, hlen, ?_⟩ rw [matrix3_unit_check_int_eq_true_iff] intro i j k l exact hval (Matrix.single i j 1) (Matrix.single k l 1) · rintro ⟨L, hlen, hchk⟩ refine ⟨L, hlen, ?_⟩ apply matrix3_valid_of_unit_checks rw [← matrix3_unit_check_int_eq_true_iff] exact hchk