AFTD Auto-Formalizing Theoretical Domains

matrix3_tensor_rank_not_le_iff_ge_succ

theoremverifiedoriginal

For any commutative semiring R and any natural number r, the tensor rank of 3x3 matrix multiplication over R is not at most r if and only if every valid triad decomposition of 3x3 matrix multiplication over R has length at least r + 1.

Statement

theorem matrix3_tensor_rank_not_le_iff_ge_succ (R : Type*) [CommSemiring R] (r : ℕ) : (¬ matrix3_tensor_rank_le R r) ↔ matrix3_tensor_rank_ge R (r + 1)
Related work
folklore; generalizes matrix3_tensor_rank_not_le_22_iff_ge_23
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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_tensor_rank_geFor a commutative semiring R and a natural number r, matrix3_tensor_rank_ge R r asserts that for every list L of elements of Matrix3Triad…

Read back from the Lean

For any commutative semiring $R$ and any natural number $r$, it is not the case that matrix3_tensor_rank_le R r holds (i.e., there is no list of triads of length at most $r$ that forms a valid matrix multiplication decomposition) if and only if matrix3_tensor_rank_ge R (r + 1) holds (i.e., every list of triads that forms a valid matrix multiplication decomposition has length at least $r + 1$).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The equivalence is established by expanding the definitions of upper and lower bounds on tensor rank into conditions on triad decomposition lengths, then proving both implications by contradiction. If no valid decomposition has length at most r, any valid decomposition must have length at least r + 1 because a length strictly smaller than r + 1 would be at most r. Conversely, if every valid decomposition has length at least r + 1, no decomposition can have length at most r, as the two length bounds are contradictory.

  1. The equivalence reduces to proving two implications: that the non-existence of a valid decomposition of length at most r implies every valid decomposition has length at least r + 1, and conversely.

    Expanding the definitions of `matrix3_tensor_rank_le` (existence of a valid decomposition of length at most r) and `matrix3_tensor_rank_ge` (every valid decomposition has length at least r + 1) expresses the equivalence in terms of decomposition lengths. Splitting the equivalence with `constructor` yields the forward and backward directions as separate subgoals.

    lines 3–4

      dsimp [matrix3_tensor_rank_le, matrix3_tensor_rank_ge]
      constructor
  2. If no valid decomposition has length at most r, then every valid decomposition has length at least r + 1.

    Assume no valid decomposition of length at most r exists, and let L be an arbitrary valid decomposition. Arguing by contradiction, suppose the length of L is strictly less than r + 1. Since L.length is a natural number, L.length < r + 1 implies L.length ≤ r (justified by linear arithmetic via `omega`). Thus L is a valid decomposition of length at most r, which contradicts the initial assumption.

    lines 5–7

      · intro h L hL
        by_contra! hlt
        exact h ⟨L, by omega, hL⟩
  3. If every valid decomposition has length at least r + 1, then no valid decomposition has length at most r.

    Assume every valid decomposition has length at least r + 1. To prove that no decomposition has length at most r, suppose for contradiction that there exists a valid decomposition L with L.length ≤ r. Specializing the universal assumption to L yields r + 1 ≤ L.length. The simultaneous inequalities r + 1 ≤ L.length and L.length ≤ r contradict each other in the natural numbers, and `omega` closes the goal.

    lines 8–10

      · intro h ⟨L, hlen, hL⟩
        have := h L hL
        omega

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

/-- For any commutative semiring R and bound r, 3x3 matrix multiplication does not have rank at most r iff its rank is at least r + 1. -/theorem matrix3_tensor_rank_not_le_iff_ge_succ (R : Type*) [CommSemiring R] (r : ℕ) : (¬ matrix3_tensor_rank_le R r) ↔ matrix3_tensor_rank_ge R (r + 1) := by  dsimp [matrix3_tensor_rank_le, matrix3_tensor_rank_ge]  constructor  · intro h L hL    by_contra! hlt    exact h ⟨L, by omega, hL⟩  · intro h ⟨L, hlen, hL⟩    have := h L hL    omega
See it in the graphDiscuss this resultChallenge it