AFTD Auto-Formalizing Theoretical Domains

matrix3_tensor_rank_int_ge_of_zmod2

theoremverifiedformalization

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

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

    line 1

    uses matrix3_tensor_rank_ge_of_surjective, ZMod.intCast_surjective

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