Homogeneous depth-five lower bounds for iterated matrix multiplication

1 · The essentials

Multiply a sequence of square matrices whose entries are separate variables, and ask for just the top-left entry of the answer. How many addition and multiplication steps are needed to calculate it? The manuscript studies calculations arranged in five alternating layers, with a rule requiring each intermediate expression to keep its terms at the same total degree. For matrices with n rows and a sequence of n matrices, it gives closely matching limits on how small such a calculation can be. The lower limit still applies when intermediate work can be reused and the first layer can combine any of the variables. That limit assumes a number system of characteristic zero, while the construction giving the upper limit works over every field. The main result has a Lean formalization, though the supplied description does not specify which additional claims it covers.

A picture to help (an imperfect image, not to be taken literally)

As an imperfect image, imagine a five-stage production line in which stations either combine ingredients by addition or multiply them, and earlier outputs can feed several later stations. The result says that even with this reuse and very flexible access to the ingredients, making this particular output requires many stations under the stated rules.

Why it matters

The result identifies the growth rate of the smallest circuits in this restricted model, rather than giving only a lower limit without a comparable construction. Allowing shared gates and bottom linear forms involving all variables makes clear that the lower bound does not depend on forbidding either of those features. Its conclusion concerns homogeneous depth-five circuits, not unrestricted methods of calculation.

2 · Going further

The polynomial $IMM_{n, n}$ is the $(1, 1)$ entry of the product of $n$ independent $n \times n$ matrices of variables. The precise problem is to determine the gate complexity of computing this polynomial by syntactically homogeneous $ΣΠΣΠΣ$ circuits: five alternating layers of sums and products, with a sum layer at both ends. Syntactic homogeneity requires the circuit's operations to respect total degree, including equal degrees for the inputs to each sum gate.

The manuscript states that, over every characteristic-zero field, every such circuit has at least $n^{n /400}$ gates for all sufficiently large $n$ . The threshold is absolute and independent of the field. The model permits arbitrary finite fan-in and fan-out, gate sharing, and bottom linear forms with arbitrary support; thus the lower bound includes circuits whose bottom linear forms involve all the variables.

For the other direction, the abstract describes a block expansion yielding circuits with at most $n^{n + 4}$ gates for $n \geq 2$ , over every field. Together, the bounds give gate complexity $n^{Θ (n)}$ in characteristic zero: the constants in the exponent need not match. The supplied abstract names block expansion as the upper-bound construction but gives no details of the lower-bound argument. Only the main manuscript is supplied, so no relationship to companion manuscripts can be described from this source.

Useful notions

Matrix multiplication
Polynomials and total degree
Arithmetic circuits and gate counts
Fields and characteristic
Asymptotic growth notation

What was known before / what is new

Before

The supplied text does not describe earlier bounds or a history of this problem. It presents block expansion as the construction providing the upper bound, without saying whether that construction was previously known.

New

The manuscript's central lower-bound statement is $n^{n /400}$ gates for homogeneous depth-five circuits over characteristic-zero fields, for all sufficiently large $n$ . It explicitly allows gate sharing, arbitrary finite fan-in and fan-out, and unrestricted support in bottom linear forms. Paired with the stated upper bound, this determines the growth rate as $n^{Θ (n)}$ .

Limits and assumptions

The lower bound requires characteristic zero, syntactic homogeneity, the specified five-layer sum–product structure, and sufficiently large n; its threshold is independent of the field. The upper bound holds over every field for n ≥ 2. These statements do not give an exact minimum gate count or a matching lower bound in positive characteristic. The main result has a Lean formalization, but the supplied material does not delineate its coverage of individual bounds or auxiliary claims. No further open problems are identified in the supplied text.

Mini glossary

Iterated matrix multiplication: Here, the polynomial obtained by taking the top-left entry of a product of n independent n-by-n matrices of variables.
Arithmetic circuit: A network of addition and multiplication gates that computes a polynomial and may reuse intermediate outputs.
Syntactic homogeneity: A degree constraint in which sum gates combine inputs of equal degree and product gates add their input degrees.
Characteristic-zero field: A field in which adding the multiplicative identity to itself any positive number of times never gives zero.
Support of a linear form: The set of variables that occur with nonzero coefficients in that linear form.
Gate complexity: The smallest number of gates needed to compute the polynomial in the specified circuit model.

Keywords : Iterated matrix multiplication · Arithmetic circuit lower bounds · Homogeneous depth-five circuits

AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.

3 · Technical details and sources

Claim made in the manuscript (source text)

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

Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.

Scope of the Lean formalization (source text)

…

lean/docs/135.md

Manuscripts in this family

★

Homogeneous depth-five lower bounds for iterated matrix multiplication

25/09/2026

To be verified

Let $IMM_{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 $ΣΠΣΠΣ$ circuit computing $IMM_{n, n}$ has at least $n^{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^{n + 4}$ gates for n ≥ 2. Thus the gate complexity over characteristic-zero fields is $n^{Θ (n)}$ .

PDF GitHub folder