Homogeneous depth-five lower bounds for iterated matrix multiplication

Over every characteristic-zero field, the (1,1) entry of a product of n independent n\times n variable matrices requires n^{\Theta(\sqrt n)} gates in homogeneous depth-five sum–product circuits. This sharp bound allows shared gates and bottom linear forms involving all variables. (Lean)

Manuscript

Homogeneous depth-five lower bounds for iterated matrix multiplication

September 25, 2026 · source · cite as \cite{OAI:Homogeneous-depth-five-lower-bounds-for-iterated-matrix-multiplication-September-25-2026}

Let \mathop{\mathrm{IMM}}\nolimits _{n,n} be the (1,1) entry of a product of n independent n\times n matrices of variables. Over every field of characteristic zero, every syntactically homogeneous \Sigma\Pi\Sigma\Pi\Sigma circuit computing \mathop{\mathrm{IMM}}\nolimits _{n,n} has at least n^{\sqrt n/400} gates for all sufficiently large n, with an absolute threshold independent of the field. Bottom linear forms may have arbitrary support, and arbitrary finite fan-in, fan-out, and gate sharing are allowed. Over every field, a block expansion gives such circuits with at most n^{\sqrt n+4} gates for n ≥ 2. Thus the gate complexity over characteristic-zero fields is n^{\Theta(\sqrt n)}.

Result 135 · Theoretical computer science. Imported from openai/math, a collection of manuscripts produced by an OpenAI model; results are at different stages of verification. Discussion below is by Lemma members.