matrix3_tensor_rank_int_ge_of_zmod2
A lower bound r on the number of products of every bilinear algorithm for 3x3 matrix multiplication over the two-element field is also a lower bound over the integers.
Statement
theorem matrix3_tensor_rank_int_ge_of_zmod2 (r : ℕ) (h : matrix3_tensor_rank_ge (ZMod 2) r) : matrix3_tensor_rank_ge ℤ r- Formalizes
- Lower Bound of 22 for 3x3 Matrix Multiplication over the Integers, arXiv:2610.01639, Sec. 5.3 (lower bounds over the two-element field bound algorithms with integer constants)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- matrix3_tensor_rank_ge_of_surjectiveIf f : R → S is a surjective homomorphism of commutative semirings and every valid triad decomposition of 3x3 matrix multiplication over S…
- 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…
The proof, explained
The result follows by transferring the lower bound across the canonical quotient homomorphism from the integers to the two-element field ℤ → ℤ/2ℤ. By matrix3_tensor_rank_ge_of_surjective, tensor rank lower bounds are preserved under surjective ring homomorphisms. Because the reduction modulo 2 is surjective (ZMod.intCast_surjective), the lower bound r over ℤ/2ℤ immediately implies the same lower bound over ℤ.
Every bilinear algorithm for 3×3 matrix multiplication over the integers ℤ requires at least r products.
We apply the general transfer theorem matrix3_tensor_rank_ge_of_surjective to the canonical ring homomorphism from ℤ to ℤ/2ℤ (Int.castRingHom (ZMod 2)). Because every residue class modulo 2 contains an integer, this map is surjective by ZMod.intCast_surjective. If there were a decomposition of 3×3 matrix multiplication over ℤ using fewer than r products, projecting its coefficients modulo 2 would yield a valid decomposition over ℤ/2ℤ of the same length, contradicting the hypothesis h.
uses
matrix3_tensor_rank_ge_of_surjective,ZMod.intCast_surjectivetheorem matrix3_tensor_rank_int_ge_of_zmod2 (r : ℕ) (h : matrix3_tensor_rank_ge (ZMod 2) r) : matrix3_tensor_rank_ge ℤ r := matrix3_tensor_rank_ge_of_surjective (Int.castRingHom (ZMod 2)) ZMod.intCast_surjective r h
matrix3_tensor_rank_ge_of_surjective- If f : R →+* S is a surjective ring homomorphism and every bilinear decomposition for 3×3 matrix multiplication over S requires at least r products, then every such decomposition over R also requires at least r products.
ZMod.intCast_surjective- The canonical ring homomorphism from the integers 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_int_ge_of_zmod2 (r : ℕ) (h : matrix3_tensor_rank_ge (ZMod 2) r) : matrix3_tensor_rank_ge ℤ r := matrix3_tensor_rank_ge_of_surjective (Int.castRingHom (ZMod 2)) ZMod.intCast_surjective r h