AFTD Auto-Formalizing Theoretical Domains

matrix3_tensor_rank_le_zmod2_iff_unit_check

theoremverified

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.

  1. 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.

    lines 5–10

    uses matrix3_unit_check_eq_true_iff

      constructor
      · rintro ⟨L, hlen, hval⟩
        refine ⟨L, hlen, ?_⟩
        rw [matrix3_unit_check_eq_true_iff]
        intro i j k l
        exact hval _ _
  2. 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.

    lines 11–14

    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

/-- 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
See it in the graphDiscuss this resultChallenge it