Homogeneous depth-five lower bounds for iterated matrix multiplication

Five-layer recipes for multiplying n matrices need n to a power that grows like √n.

1 paper September 25, 2026 Explained by AI

Iterated matrix multiplication is the top-left entry of a product of n grids of unknowns. It is cheap to compute with many layers of steps. This paper proves that a homogeneous recipe with only five layers needs at least n to the power (√n/400) gates. The paper also gives a block recipe with at most n to the power (√n + 4) gates. So the cost is n raised to a constant times √n.

First step

1995

Nisan and Wigderson, partial-derivative lower bounds

Significance

Solid

It pins the exponent for a standard test polynomial in a well-studied shallow circuit model.

Trust

Formal proof listed

Field

Theoretical computer science

1 paper

The explanation

Take three grids of numbers, each 3 by 3, and multiply them in a row. Look only at the top-left entry of the result. Written out in full, it is a sum of 9 terms. Each term multiplies three entries, one from each grid. With n grids of size n by n, the count is n to the power n minus 1. For n = 10 that is a billion terms. This top-left entry, with every grid entry treated as an unknown, is called iterated matrix multiplication, or IMM.

Nobody needs to write out the billion terms. Multiply the grids one after another, and the work stays modest. In the paper's words, IMM has polynomial-size circuits when depth is unrestricted. A circuit [a recipe of additions and multiplications, where each step is a gate] can reuse earlier results. Its depth is the number of layers of steps. Step-by-step multiplication uses many layers, one after another.

The question is what happens when the recipe must be shallow. Here it gets exactly five layers: add, multiply, add, multiply, add. The bottom layer forms simple sums of the unknowns, called linear forms. The recipe must also be homogeneous [each step keeps a fixed degree, so no terms later cancel away]. Under these rules the paper gives a recipe. Cut the n grids into about the square root of n blocks. Multiply out each block fully, then combine the blocks. For n = 16, four blocks of four grids give a count of 4,207,617 gates by the paper's formula. In general the paper shows at most n to the power (square root of n plus 4) gatesSource 1.

Lower bounds of this kind have a long history. Nisan and Wigderson, in 1995, asked for an explicit polynomial needing superpolynomial size at constant depth, even at depth five. Kumar and Saraf proved a bound of the right square-root shape for depth four, with much wider grids. In 2015, Bera and Chakrabarti proved a depth-five bound for IMM. Theirs limited how many unknowns each bottom linear form could use. Limaye, Srinivasan and Tavenas, in 2021, gave superpolynomial bounds with no such limit, over characteristic zero. But the matching square-root exponent was missing for n grids of size n by n.

This paper proves the missing boundSource 2. Over every field of characteristic zero, any such recipe needs many gatesSource 3. The count is at least n to the power (square root of n divided by 400). Characteristic zero means that adding 1 to itself never gives 0, as with ordinary fractions. The bottom linear forms may use every unknown. Gates may be shared freelySource 4. Together with the recipe above, the true cost is n raised to a constant times the square root of n.

The sticking point was the bottom layer. The earlier depth-five bound for IMM limited how many unknowns each bottom sum may use. This paper needs no such limit. It gives each polynomial a score. Some unknowns become derivatives [rates of change], and the rest become multipliersSource 5. The score counts how many genuinely different results come out. A small five-layer recipe can only reach a modest score. IMM reaches a large one, because of the many paths through its gridsSource 6. The two scores clash unless the recipe is large.

The bound is about shape, not small cases. Its constant 1/400 is tiny. At n = 100 the formula gives about 1.12 gates, which says nothing. The theorem holds only beyond a threshold that the paper does not state as a number. At n = 100,000,000 the formula gives 10 to the power 200 gates, if that size is past the threshold. The upper recipe there is far larger again. The two bounds agree in shape, not in their constantsSource 7.

How sure is this? The Lean scope note says a formalization proves both the lower bound and the upper bound. Lean is a computer proof checker. The note links a Comparator statement for the result. No specialist review of the paper has been published.

What it doesn't show. This does not give useful numbers for small n, and it does not cover circuits that are not homogeneous.

Where it came from

This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026.

Hype check

Solid if the proof holds. The Lean scope note lists a formal proof of both bounds, but no specialist review is published. Superpolynomial bounds in this setting were already known; the new part is the sharp exponent.

Words used

Iterated matrix multiplication (IMM): The top-left entry of a product of n grids whose entries are unknowns.
Circuit: A recipe of additions and multiplications in which each step is a gate and results can be reused.
Depth: The number of layers of steps in a circuit.
Homogeneous: Every step keeps a fixed degree, so no step builds terms that later cancel away.
Linear form: A plain weighted sum of unknowns, with no products.
Characteristic zero: A number system where adding 1 to itself never gives 0, like ordinary fractions.
Superpolynomial: Growing faster than any fixed power of the input size.

The original paper

Homogeneous depth-five lower bounds for iterated matrix multiplication (PDF, opens in a new tab)
September 25, 2026

Lean notes

All quoted lines (7)

There is a syntactically homogeneous $\Sigma\Pi\Sigma\Pi\Sigma$ circuit over $K$ computing $\IMM_{n,n}$ whose number of gates, including leaves, is at most $2n^3+rn^2+rn^{t+1}+n^{r-1}+1 \le n^{\sqrt n+4}.$
Homogeneous depth-five lower bounds for iterated matrix multiplication Back to text
The comparison addressed here is quantitative: we obtain the $\sqrt n$ exponent in the balanced regime $w=d=n$ for homogeneous five-layer circuits with unrestricted bottom linear forms.
Homogeneous depth-five lower bounds for iterated matrix multiplication Back to text
There is an absolute integer $n_0$ such that, for every field $K$ of characteristic zero and every $n\ge n_0$ , every syntactically homogeneous $\Sigma\Pi\Sigma\Pi\Sigma$ circuit over $K$ computing $\IMM_{n,n}$ has at least $n^{\sqrt n/400}$ gates. Bottom fan-in and bottom support are unrestricted.
Homogeneous depth-five lower bounds for iterated matrix multiplication Back to text
Fan-in and fan-out are arbitrary and finite. Gates may be shared, and a gate may occur repeatedly among another gate's inputs; repeated occurrences at a product gate are counted with their multiplicities.
Homogeneous depth-five lower bounds for iterated matrix multiplication Back to text
Replace its $V$ -variables by partial derivatives and its $U$ -variables by multiplication operators.
Homogeneous depth-five lower bounds for iterated matrix multiplication Back to text
The opposite estimate uses the paths in matrix multiplication.
Homogeneous depth-five lower bounds for iterated matrix multiplication Back to text
Thus the gate complexity over characteristic-zero fields is $n^{\Theta(\sqrt n)}$ .
Homogeneous depth-five lower bounds for iterated matrix multiplication Back to text