Depth five, sharply?

0:00Circuits for matrix products

An arithmetic circuit computes a polynomial with sum gates and product gates. Take n matrices, each n by n, whose entries are all distinct variables, and multiply them. The top-left entry of the product is called iterated matrix multiplication: a sum over paths through n layers, one variable per step, with n^(n−1) terms. With unrestricted depth, circuits of polynomial size compute it. But restrict the depth to five alternating layers, sums of products of sums of products of sums, and require the circuit to be syntactically homogeneous: every sum gate adds inputs of the same formal degree. The bottom sums may be any linear forms, and gates may be shared. How many gates are needed then? Nisan and Wigderson asked for an explicit homogeneous polynomial that needs superpolynomial size at constant depth, even at depth five. Depth reduction, by Agrawal and Vinay, Koiran and Tavenas, raised the stakes: a polynomial-size circuit for a homogeneous polynomial of degree d in N variables becomes a homogeneous depth-four circuit of size N^O(√d), which sets the square-root scale here. Earlier lower bounds reached this scale only with extra restrictions: matrices much wider than their number, small bottom fan-in, multilinear circuits, other polynomials, or finite fields. Limaye, Srinivasan and Tavenas proved superpolynomial bounds at constant depth over characteristic zero, which for this polynomial give a superpolynomial bound, but not the square-root exponent.

1:37The claim

Result 135 is a single OpenAI preprint, 22 pages, dated September 25. It claims that over every field of characteristic zero, every syntactically homogeneous depth-five circuit computing the n by n case needs at least n^(√n/400) gates, for all sufficiently large n, with a threshold that does not depend on the field. Bottom linear forms may involve all the variables, and fan-in, fan-out and sharing are arbitrary. Over every field, for every n from 2 on, a block construction does it with at most n^(√n+4) gates, counting leaves. So the answer is n^Θ(√n): the exponent is pinned down up to a constant factor. What is not claimed: a lower bound in positive characteristic, or for circuits that are not homogeneous. The constants are far apart, 1/400 against about one, the threshold is not given, and the bound only beats the roughly n³ variables a circuit must read as leaves once n passes about 1.4 million. OpenAI published a Lean formalization of the lower bound, over every characteristic-zero field with a threshold that does not depend on the field, and of the construction over every field: 164 files and about 20,000 lines, not counting Mathlib. We have not run the Lean check.

3:05How the proof goes

The upper bound is direct. Cut the n matrices into about √n consecutive blocks of about √n matrices each. The bottom sums read the variables. The lower products write out every monomial of every block product, and the middle sums add them into the entries of each block product. The upper products multiply one entry from each block along every choice of indices between blocks, and the top sum adds them all. A block has about n^√n monomials, and there are about n^√n choices of indices. In our check, symbolic expansion confirmed this circuit for n from 2 to 5, with 30, 112, 293 and 1,056 gates, leaves included. The lower bound uses a rank measure. Split the n layers into two teams: a smaller one of (n − s)/2 layers and a larger one of (n + s)/2, with s about √n. In a polynomial, replace each variable of the smaller team by a partial derivative, and each variable of the larger team by multiplication. Every polynomial becomes a linear map between huge spaces of polynomials, and the measure is its rank. Rank is subadditive, and because derivatives in one team commute with multiplication in the other, the substitution turns a product of polynomials into a product of operators. Now take one product in the circuit: a product of middle sums whose degrees add up to n. Each factor would like a fair share of the smaller team’s degree, a fraction slightly below one half, but degrees are integers, so small factors miss their share, and every unit missed costs a factor of about 1/√n in rank. If every factor has degree below about √n/4, the misses add up to at least s/2. Otherwise, open the big factor into products of linear forms, and each linear form misses by at least 3/8. Either way, each product, or each of the at most S pieces it opens into, keeps at most about n^(−√n/100) of the full rank. There are at most S products, so a circuit with S gates has rank at most about S² times that. For the polynomial itself, order the layers so that no two layers of the smaller team are adjacent, and use the fact that a rank is at least the square of a trace divided by the trace of the square. The first trace is a sum over paths. The second is a sum over quadruples of paths, and in each layer a contributing quadruple pairs up in one of only two patterns. Each switch of pattern forces four labels to agree, costing a factor n, and the balanced order keeps the total in check: the rank is nearly full, within a factor e^(C√n). That is over the complex numbers; the matrix has integer entries, so the same rank holds over every field of characteristic zero. Comparing the two sides, S² must be at least about n^(√n/100), so S is at least about n^(√n/200), and after absorbing the smaller losses, at least n^(√n/400). In our check, with three-by-three matrices, the relaxed counts of path quadruples, where the paper drops the rule that paired labels differ, matched its formula for all eight pattern words.

6:28Where it stands

The preprint is not peer reviewed and has not been revised. The Lean formalization covers the lower bound over every field of characteristic zero and the upper bound construction; we have not run it. The paper is not among those OSVerify reviewed, and we have seen no expert review. If it holds, syntactically homogeneous depth-five circuits for iterated matrix multiplication need n^Θ(√n) gates, with unrestricted bottom linear forms, over every field of characteristic zero, matching the square-root scale of depth reduction. Positive characteristic and circuits without homogeneity are not covered.