matrix3_tensor_rank_zmod2_le_of_int
A bilinear algorithm for 3x3 matrix multiplication with integer coefficients and r products gives one over the two-element field with r products; in particular a 22-product algorithm over the integers would answer the two-element-field question positively.
Statement
theorem matrix3_tensor_rank_zmod2_le_of_int (r : ℕ) (h : matrix3_tensor_rank_le ℤ r) : matrix3_tensor_rank_le (ZMod 2) r- Formalizes
- Lower Bound of 22 for 3x3 Matrix Multiplication over the Integers, arXiv:2610.01639, Sec. 5.3 (an algorithm with integer constants, read modulo 2, is an algorithm over the two-element field with no more multiplications; classical reduction cited there)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- matrix3_tensor_rank_le_of_surjectiveIf f : R → S is a surjective homomorphism of commutative semirings and 3x3 matrix multiplication over R has a valid triad decomposition…
- 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…
The proof, explained
The proof transfers a matrix multiplication algorithm from the integers to the field ℤ/2ℤ by applying the canonical reduction homomorphism modulo 2 entrywise. Because reduction modulo 2 is a surjective ring homomorphism from ℤ to ℤ/2ℤ, any valid length-r bilinear decomposition over ℤ directly yields a valid decomposition of the same length over ℤ/2ℤ.
The 3x3 matrix multiplication tensor rank over ℤ/2ℤ is at most r.
We apply the general transfer lemma matrix3_tensor_rank_le_of_surjective to the canonical ring homomorphism Int.castRingHom (ZMod 2) from ℤ to ℤ/2ℤ. Since this reduction modulo 2 is surjective by ZMod.intCast_surjective, the given integer decomposition of length at most r (h) projects entrywise to a valid decomposition of the same length over ℤ/2ℤ.
uses
matrix3_tensor_rank_le_of_surjective,Int.castRingHom,ZMod.intCast_surjectivetheorem matrix3_tensor_rank_zmod2_le_of_int (r : ℕ) (h : matrix3_tensor_rank_le ℤ r) : matrix3_tensor_rank_le (ZMod 2) r := matrix3_tensor_rank_le_of_surjective (Int.castRingHom (ZMod 2)) ZMod.intCast_surjective r h
matrix3_tensor_rank_le_of_surjective- A surjective ring homomorphism between commutative semirings transfers bounds on 3x3 matrix multiplication rank: if the tensor rank over the source ring is at most r, it is at most r over the target ring.
Int.castRingHom- The canonical ring homomorphism from the integers ℤ into any target ring R, mapping an integer to its image in R.
ZMod.intCast_surjective- The canonical projection from ℤ to ℤ/nℤ is surjective.
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
theorem matrix3_tensor_rank_zmod2_le_of_int (r : ℕ) (h : matrix3_tensor_rank_le ℤ r) : matrix3_tensor_rank_le (ZMod 2) r := matrix3_tensor_rank_le_of_surjective (Int.castRingHom (ZMod 2)) ZMod.intCast_surjective r h