AFTD Auto-Formalizing Theoretical Domains

matrix3_tensor_rank_zmod2_le_of_int

theoremverifiedformalization

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

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

    line 1

    uses matrix3_tensor_rank_le_of_surjective, Int.castRingHom, ZMod.intCast_surjective

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