AFTD Auto-Formalizing Theoretical Domains

matrix3_tensor_rank_le_int_iff_unit_check

theoremverified

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.

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

    lines 5–10

    uses matrix3_unit_check_int_eq_true_iff

      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)
  2. 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.

    lines 11–15

    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

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