The middle coefficient matrix of a noncommutative polynomial
DefinitionNCQuadLB_Supplement_middleCoeffMatrixarithmetic-circuitscomputational-complexitylower-boundsnoncommutative-polynomialsp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a noncommutative polynomial and let . The middle coefficient matrix is the matrix whose rows and columns are indexed by ordered degree- monomials and whose entries are
the coefficient of the concatenated word in . Neither word is reversed or commutativized. This matrix is the coefficient-space complexity measure used in Theorem 5.1.
Formalization Note A degree- monomial is represented by a tuple in , with indices starting at . The module also defines the ordered word represented by such a tuple. Coefficients are read through the published NCFactorClosure607.Circuits.coeff.
Definition code
import Mathlib
import Definitions.Def_NCFactorClosure607_Circuits_Polynomials
namespace NCQuadLB
namespace Supplement
/-- The word `x_{i₁}⋯x_{i_d}` indexed by a tuple `i : Fin d → Fin n`. -/
def tupleWord {n d : ℕ} (i : Fin d → Fin n) : FreeMonoid (Fin n) :=
FreeMonoid.ofList (List.ofFn i)
/-- The **middle coefficient matrix** `M_f^{d,d}` (Shastri–Willumsgaard,
*A Quadratic Lower Bound for Noncommutative Circuits*, arXiv:2604.20575, version of
November 2, 2026, sha256 34159453f21da4d8e225baf84bf89c6cd2feb49797548f4efa6c67543940dcd8,
§5, p.8). Its rows and columns are indexed by degree-`d` noncommutative monomials, and
the `(m,m')` entry is the coefficient of the concatenated word `mm'` in `f`.
**Formalization Note** A degree-`d` monomial is indexed by its ordered, 0-based tuple
`i : Fin d → Fin n`; hence the square matrix has `n^d` rows and columns. Neither tuple is
reversed or commutativized. Coefficients are read through the published
`NCFactorClosure607.Circuits.coeff`. -/
noncomputable def middleCoeffMatrix {F : Type*} [Field F] {n : ℕ} (d : ℕ)
(f : FreeAlgebra F (Fin n)) : Matrix (Fin d → Fin n) (Fin d → Fin n) F :=
fun i j => NCFactorClosure607.Circuits.coeff (tupleWord i * tupleWord j) f
end Supplement
end NCQuadLB
Source
Shastri, Willumsgaard, A Quadratic Lower Bound for Noncommutative Circuits, arXiv:2604.20575 (version of November 2, 2026, sha256 34159453f21da4d8e225baf84bf89c6cd2feb49797548f4efa6c67543940dcd8), §5, p.8