matrix3_tensor_rank_not_le_iff_ge_succ
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.
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.
dsimp [matrix3_tensor_rank_le, matrix3_tensor_rank_ge] constructor
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.
· intro h L hL by_contra! hlt exact h ⟨L, by omega, hL⟩
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.
· 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
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.
/-- 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