Tensor-rank campaign bounds imply complex arithmetic-circuit bounds
Provedmme_complex_arithmetic_omega_le_matMulExpThe arithmetic-circuit exponent for square matrix multiplication over the complex numbers is at most the tensor-rank exponent used by the matrix-multiplication campaign:
The left side uses the published division-free straight-line-program model: inputs and constants are free, and each addition, subtraction, or multiplication costs one. Admissibility requires a correct program at every positive size, with one uniform constant for each positive exponent slack. The right side is the infimum, over integer sizes at least two, of the logarithm of the exact matrix-multiplication tensor rank divided by the logarithm of the size.
Consequently, every non-strict upper bound on the campaign exponent over ℂ also bounds the arithmetic-circuit exponent; every strict upper bound transfers as well. A campaign theorem quantified over all fields is first specialized to ℂ. This theorem asserts the direction needed to transfer upper bounds, not equality of the two exponents.
import Definitions.Def_mme_omega import Definitions.Def_OAI_MatrixMultiplication_Arithmetic_omega
theorem mme_complex_arithmetic_omega_le_matMulExp :
OAI.MatrixMultiplication.Arithmetic.omega ℂ ≤ MME.matMulExp ℂ := by sorry