1 Introduction
We study how many gates are needed to compute iterated matrix multiplication with five homogeneous arithmetic layers. For integers w,d\geq 1, let X^{(1)},\ldots,X^{(d)} be w\times w matrices whose entries are distinct commuting variables. Define
For d=1, the expression means x^{(1)}_{1,1}. The first index denotes matrix width and the second denotes degree. We retain all dw^2 matrix-entry variables as ambient variables, including entries absent from the polynomial. Our target is \IMM_{n,n}, of degree n in n^3 ambient variables.
1.1 Circuit model and main result
An arithmetic circuit over a field K is a finite directed acyclic graph. Its leaves are variables or elements of K. A sum gate computes a K-linear combination of its inputs, and a product gate computes their product. 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. Scalar coefficients on sum inputs are part of the circuit and do not require additional gates.
A \Sigma\Pi\Sigma\Pi\Sigma circuit has five computational layers, listed from output to leaves, with respective gate types +,\times,+,\times,+ and a single output gate. Edges between computational gates join consecutive layers, and the bottom sums read leaves. Unary gates are allowed. In particular, no bound is placed on the number of variables in a bottom linear form.
The circuit is syntactically homogeneous if it has the following formal-degree assignment: variables have degree 1, constants have degree 0, product gates add their input degrees with multiplicity, and all inputs of a sum gate have the same degree, which is assigned to that gate. Empty sums and products, if present, compute 0 and 1 and have formal degree 0. Thus a zero polynomial at a gate still carries its assigned formal degree; cancellation does not reset that degree. All computations and equalities below concern formal polynomials.
We define size to be the number of vertices, including leaves. The number of computational gates excludes leaves, whereas wire size counts input occurrences. These quantities are not identified: our lower bound is on gates, and the circuit analysis also bounds the number of computational gates alone.
Theorem 1.1. There exist absolute constants c>0 and n_0 such that, for every integer n\geq n_0, every syntactically homogeneous \Sigma\Pi\Sigma\Pi\Sigma circuit over \C computing \IMM_{n,n} has size at least
One may take c=1/400.
The model permits unrestricted bottom fan-in and support, constants, and shared subcircuits. Corollary 6.1 extends the n^{\sqrt n/400} lower bound to every field of characteristic zero, with the same absolute threshold. Proposition 6.2 gives an elementary block construction of size at most n^{\sqrt n+4} over every field for n\geq2. It is homogeneous of depth four; inserting unary bottom sums makes it depth five, so the lower bound has the matching scale. Iterated matrix multiplication nevertheless has polynomial-size circuits when depth is unrestricted.
1.2 Historical context and previous bounds
Iterated matrix multiplication has long served as a test of the cost of restricting arithmetic depth. Its path expansion connects matrix products with reachability, while its polynomial-size unrestricted circuits make it a natural target for lower bounds on weaker circuit models. Nisan and Wigderson used dimensions of partial-derivative spaces to prove lower bounds for homogeneous depth-three circuits and for constant-depth set-multilinear circuits. They asked for an explicit homogeneous polynomial requiring superpolynomial size at constant depth, even at depth five [19, Section 2.2 of the linked author journal manuscript].
Depth reduction gave this program a further motivation. Agrawal and Vinay reduced general arithmetic computation to depth four, and Koiran and Tavenas sharpened the size bounds [1, 14, 20]. For d=N^{O(1)}, Tavenas’s theorem converts a circuit of size N^{O(1)} computing a homogeneous degree-d polynomial in N variables to a homogeneous depth-four circuit of size N^{O(\sqrt d)} [20, Theorem 1 of the linked preprint]. This explains the square-root scale in depth-four lower bounds and in the block construction for IMM used here.
The progress toward this scale involved several distinct restrictions. Fournier, Limaye, Malod, and Srinivasan proved IMM lower bounds with bounds on both product-layer fan-ins and, separately, for homogeneous multilinear formulas [9, Theorems 16 and 29 of the cited author version]. Kayal, Limaye, Saha, and Srinivasan removed the bottom-fan-in restriction for homogeneous depth-four formulas, obtaining an exponential lower bound over characteristic zero for a Nisan–Wigderson design family [12, Theorem 1]. Kumar and Saraf proved a d^{\Omega(\sqrt d)} lower bound for homogeneous depth-four circuits computing \IMM_{d^5,d}, over every field [16, Theorem 1.2 and Section 8.2 of the cited preprint]. In another direction, Kayal, Saha, and Tavenas obtained w^{\Omega(\sqrt d)} for syntactically multilinear depth-four circuits computing \IMM_{w,d}, without homogeneity, in the range d\geq\log^2 w, over every field [13, Theorem 1.4 and the following comparison].
At depth five, Bera and Chakrabarti proved a lower bound with a restriction on bottom support. Their Theorem 1.1 states that, for every fixed 0\leq\mu<1/2, there is an integer q=q(\mu)>0 such that homogeneous \Sigma\Pi\Sigma\Pi\Sigma circuits computing \IMM_{d^q,d}, with N=d^{2q+1} ambient variables and bottom fan-in at most N^\mu, require N^{\Omega_\mu(\sqrt d)} gates over every field [6, Theorem 1.1]. Their precise Theorem 4.2 proves the lower bound for a restricted IMM polynomial, using the number of distinct variables feeding each bottom linear gate as its support parameter [6, Theorem 4.2]. The Kumar–Saraf and Bera–Chakrabarti bounds use different width–degree regimes from w=d=n, and the latter restricts the bottom linear forms.
For a different hard family, Kumar and Saptharishi proved, over each fixed finite field \mathbb F_q, \exp(\Omega_q(\sqrt d)) lower bounds for homogeneous depth-five circuits without a bottom-support restriction [15, Theorem 1]. Their family is based on Nisan–Wigderson designs and lies in \mathrm{VNP}. Armand, Behera, and Tavenas have since extended this finite-field approach to depth-five circuits whose top-product fan-in is bounded by a fixed polynomial in the degree d, without homogeneity [4, Corollary 1.3]. These finite-field theorems concern NW polynomials rather than IMM; both the field hypothesis and the exponential rate differ from those in Theorem 1.1.
Superpolynomial lower bounds for unrestricted-bottom depth-five circuits over characteristic zero were already established by the constant-depth results of Limaye, Srinivasan, and Tavenas [17, 18]. We use the theorem numbering of their ECCC revision 1. Their product-depth convention counts multiplication gates on a path, so our five-layer model has product-depth two. In the low-degree regime d\leq(\log w)/100, their Corollary 3 gives w^{\Omega(\sqrt d)} for homogeneous product-depth-two circuits over every field [17, Corollary 3]. Their general-circuit results also imply superpolynomial lower bounds for \IMM_{n,n} over \C [17, Corollary 4 and the following discussion]. Bhargav, Dutta, and Saxena improved the constant-depth exponents in the low-degree regime [7]. Forbes subsequently established low-depth IMM lower bounds over arbitrary fields in the regime d=o(\log w) [8, Theorem 10].
Amireddy, Garg, Kayal, Saha, and Thankey gave a direct shifted-partials approach. For homogeneous product-depth-two formulas they obtain 2^{-O(d)}w^{\Omega(\sqrt d)} when w=\omega(d), over every field [3, Theorem 24]. The degree-dependent loss and the hypothesis w=\omega(d) prevent direct substitution of w=d=n. 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.
1.3 Proof overview
The proof uses a derivative-based linear-algebraic measure. Dimensions of partial-derivative spaces were used by Nisan and Wigderson [19]; shifted partial derivatives were developed in work of Kayal [11] and Gupta, Kamath, Kayal, and Saptharishi [10]. We define the operator needed here directly and prove its estimates.
Partition the matrix layers into two groups containing k and m layers, where k+m=n and m-k is of order \sqrt n. Let V and U be the corresponding variable sets. For a homogeneous polynomial g of degree n, let g_{[k,m]} be the sum of its monomials having degree k in V and degree m in U. Replace its V-variables by partial derivatives and its U-variables by multiplication operators. On polynomials of fixed bidegree (a,b) this gives a linear map
into polynomials of bidegree (a-k,b+m). We choose a,b of order n^{5/2}, write D for the dimension of the source, and use R(g)=\rank F_g as the complexity measure. Differentiation in V commutes with multiplication in U; the full substitution therefore respects products, while the finite map is linear in g and its rank is subadditive. Section 2 gives the definitions and parameters.
We first bound the rank of a circuit in Section 3. For a product of homogeneous factors, resolve each factor into its possible V-degrees. Apply first those factors whose V-degree exceeds their proportional share ke/n for a factor of degree e. Their composition passes through a smaller intermediate polynomial space, which bounds its rank. The distance of each proportional share from the integers controls the sum over all such decompositions. These are the same integer-degree discrepancies that underlie the residue method of Amireddy, Garg, Kayal, Saha, and Thankey [2, Definition 2.1 and Lemma 3.1]; here they control intermediate homogeneous dimensions. If all factor degrees are small, these distances give the required saving. If some factor has large degree, expand just one such factor into its bottom products of linear forms. This costs at most one additional factor of the circuit size. Proposition 3.1 gives, for a size-S circuit,
with an absolute constant C.
The opposite estimate uses the paths in matrix multiplication. Section 4 arranges the two groups of layers in a balanced order, with no adjacent V-layers. Declare the monomials z^M/\sqrt{M!} orthonormal, where M is an exponent vector and M! is the product of its coordinate factorials. In these bases, differentiation and multiplication have coefficients given by square roots of exponents and their successors. For g=\IMM_{n,n}, the first two trace moments of F_g^*F_g become weighted counts of paths and quadruples of paths. Exact factorial moments for uniform weak compositions compare these weights with independent geometric random variables. We verify the coefficient signs needed for that comparison.
At each layer, a contributing quadruple has one of two pairing patterns. A change of pattern forces four vertex labels to agree and reduces the number of choices by a factor of n. Section 5 sums the resulting weights, treating isolated corrections and the two endpoints explicitly. The balanced order controls the weight accumulated along each run of one pattern. The trace inequality
then yields R(\IMM_{n,n})\geq D\exp(-C'\sqrt n), as stated in Proposition 4.1. Section 6 compares the two rank estimates and proves the field extension and matching upper bound.
2 A rank measure from differentiation and multiplication
We associate a linear map to a polynomial by differentiating in one group of variables and multiplying in a disjoint group. The rank of this map is subadditive. More importantly, the map associated to a product can be factored through intermediate homogeneous spaces, whose dimensions will control the circuit upper bound.
2.1 The operator and its homogeneous spaces
Let K be a field, and let V,U be disjoint finite sets of variables, of cardinalities v,u\ge1. For a variable set E and an integer t\ge0, write \HH_E(t)=K[E]_t for the vector space of homogeneous polynomials of degree t. Its dimension is
For Q\in K[V,U], let
be the operator on K[V,U] obtained by replacing each variable in V by its formal partial derivative and each variable in U by multiplication by that variable. These operators commute because the two variable sets are disjoint. Thus T_{Q_1Q_2}=T_{Q_1}T_{Q_2}. This identity holds over every field.
Fix integers k,m\ge0, a\ge k, and b\ge0. If g is homogeneous of degree k+m, denote its component of V-degree k and U-degree m by g_{[k,m]}. Define the finite-dimensional map
The source dimension is D=h(v,a)h(u,b). Projection to a bidegree and operator substitution are both linear, so
Also R(0)=0. The multiplicative identity for T_Q does not assert multiplicativity of g\mapsto F_g: the latter includes a fixed bidegree projection. We will first decompose products into their bidegree components and then use multiplicativity of T_Q on each contribution.
2.2 Choosing the degrees
We now choose the spaces in (2) for degree-n polynomials on the n matrix layers. Throughout the proof n is sufficiently large, and all implicit constants and thresholds are absolute. Let s be the largest integer at most \sqrt n having the same parity as n, and put
For now assign any k full matrix layers to V and the other m layers to U. Each layer retains all its n^2 variables, including variables absent from the endpoint entry of the matrix product. Section 4 will specify their order when bounding the rank of \IMM_{n,n} from below.
The small excess m-k=s makes the slope \lambda slightly less than 1/2. For small positive even factor degrees e, this moves \lambda e away from the integers; Section 3 quantifies the resulting rank saving. The definitions of a,b balance the dimension decrease caused by differentiation against the dimension increase caused by multiplication. Without the ceiling in the definition of b, we would have \beta=\alpha^\rho and \alpha^k\beta^{-m}=1. We record the rounding estimates explicitly, as their errors must stay small after many factors are combined.
Lemma 2.1. For all sufficiently large n, the parameters in (3) satisfy
where C is an absolute constant.
Proof. The parity choice gives \sqrt n-2<s\le\sqrt n, and hence the claims about s,k,m,\lambda,\rho,v,u. Write a_0=v/(\sqrt n-1), so that a_0\le a<a_0+1 and a_0/(a_0+v)=n^{-1/2}. The function x/(x+v) is increasing, and the derivative of its logarithm is v/(x(x+v))\le1/x. The mean value theorem therefore gives
In particular a=\Theta(n^{5/2}) and \alpha^{-1}\le\sqrt n.
Since 1-\rho=s/m=O(s/n), the preceding estimate implies
Put b_0=u\alpha^\rho/(1-\alpha^\rho). Then b_0=\Theta(n^{5/2}), b_0\le b<b_0+1, and b_0/(b_0+u)=\alpha^\rho. Applying the same logarithmic derivative bound with u in place of v gives
This proves the assertions about b,\beta, including \beta\le2/\sqrt n eventually. The growth of a,b also gives a\ge k and 2n\le\min(a,b)/2.
Finally,
Because 0<\alpha<1 and (1+\rho)/2\le1, we have q\ge\alpha\ge n^{-1/2}. The remaining upper bounds follow from the last display and s\log n/n\to0.
The estimate q\le n^{-2/5} will suffice for the main power savings. The sharper q=O(n^{-1/2}) will be essential when summing the smaller errors contributed by even factor degrees.
3 The rank of a homogeneous depth-five circuit
We now bound the rank measure in terms of circuit size. The argument is uniform over the choice of the k matrix layers assigned to V. Its first step bounds the rank of a product using only the degrees of its factors. We then expand one middle-layer sum when its degree is large, exposing its lower products of linear forms.
Proposition 3.1. There are absolute constants C>0 and n_0 with the following property. For n\ge n_0, use the parameters in (3) and any partition of the matrix layers with k layers in V and m layers in U. Let K be a field, and let g\in K[V,U] be a homogeneous degree-n polynomial computed by a syntactically homogeneous \Sigma\Pi\Sigma\Pi\Sigma circuit of size S. Then
All thresholds in this section are absorbed into a single absolute n_0, independent of the field, the circuit, and the partition. Only the parameter estimates of Lemma 2.1 will be used.
3.1 Products and intermediate dimensions
For a positive integer e, define
These quantities account for all choices of bidegree in a product.
The quantities H_e use the same integer-degree discrepancies as the residue method of Amireddy, Garg, Kayal, Saha, and Thankey [2, Definition 2.1 and Lemma 3.1]. In the present argument they control the dimensions of the intermediate homogeneous spaces through which the differentiation–multiplication operator factors.
Lemma 3.2. Let K be a field, and let Q_1,\ldots,Q_r\in K[V,U] be homogeneous of respective positive degrees e_1,\ldots,e_r, with \sum_{j=1}^r e_j=n. Then
Proof. Decompose each factor into its bidegree components. The component of their product that defines the rank measure is
Fix an assignment in this sum, and put \delta_j=i_j-\lambda e_j. Since \lambda n=k, we have \sum_j\delta_j=0. The operators obtained by substituting \partial_V and U commute, so we may apply first the factors with \delta_j>0. Write their total bidegree as
The resulting intermediate space is \HH_V(a-I)\otimes\HH_U(b+J). It is well defined because I\le k\le a; also J\le m. Its dimension bounds the rank of this contribution, including when the set of positive discrepancies is empty.
The successive ratios of binomial coefficients give
The first inequality follows because x/(x+v-1) is nondecreasing for x>0. Since \beta\ge\alpha^\rho, these inequalities imply
The last bound holds uniformly for I\le n, because a+v=\Theta(n^3). Empty products in the ratio formulas equal 1.
Using \lambda=\rho/(1+\rho) and \sum_j\delta_j=0, we obtain
As q=\alpha^{(1+\rho)/2}, the rank of the fixed-assignment contribution is therefore at most
Rank subadditivity permits summing these bounds. Dropping the constraint \sum_j i_j=k increases the resulting nonnegative sum and makes it factor as 2D\prod_jH_{e_j}. Zero bidegree components contribute rank zero throughout.
3.2 The cost of integer degrees
The product estimate is effective because \lambda e is usually separated from the integers. Small even degrees require particular care: their separation can tend to zero, so a constant loss for each factor would be too large. We bound their combined error instead.
Put
Lemma 3.3. For every integer e\ge1,
If 1\le e<t_0, then
In this range, odd degrees satisfy H_e\le q^{d_e/2}, whereas even degrees satisfy
There is an absolute constant C_1 such that, for every finite list of positive integers e_1,\ldots,e_r with \sum_j e_j\le n,
Proof. Enlarge the sum defining H_e to all integers. Apart from one nearest integer to \lambda e, the terms have total at most 2q^{1-d_e}/(1-q). This remains valid when the nearest integer is not unique. Since q\le1/2, it gives the first inequality in (5); the second follows from 0\le d_e\le1/2 and 0<q<1.
For e<t_0, write
The nearest integer is consequently e/2 for even e, and (e-1)/2 for odd e. This proves (6). For odd e we have d_e\ge3/8. By q\le n^{-2/5},
after increasing n_0. Thus H_e\le5q^{d_e}\le q^{d_e/2}. For even e, substitute 2d_e=se/n in (5) and use 1+x\le\exp(x) to obtain (7).
It remains to sum these even-degree errors. Increase n_0 so that t_0>2, and for real z\in[2,t_0] define
Its logarithm is convex, since (\log f)''(z)=1/z^2>0. Hence f(z)\le\max\{f(2),f(t_0)\}. The sharp estimate for q in Lemma 2.1 gives
At the other endpoint, s\le\sqrt n and q\le2n^{-1/2} give
Therefore q^{1-se/n}\le C_1e/\sqrt n uniformly over the low even degrees. Summing and using \sum_j e_j\le n proves (8).
These estimates control a product of factors below t_0 regardless of their coefficients. A factor of degree at least t_0 will instead supply many linear factors through its bottom-layer expansion.
3.3 From gates to products
Proof of Proposition 3.1. If g=0, the conclusion is immediate. Otherwise its formal output degree is n: induction on the gates shows that every nonzero polynomial at a formally homogeneous degree-d gate is homogeneous of degree d.
We first record exactly what the circuit layers provide. A bottom sum gate computes either a homogeneous linear form or a scalar, because all its leaf inputs have the same formal degree. A lower product of formal degree e>0 therefore computes a scalar times a product of exactly e homogeneous linear-form occurrences. Degree-zero factors are absorbed into that scalar. A zero factor makes the whole product zero and its contribution can be discarded. A gate computing zero need not be assigned a different formal degree.
At either a middle sum or the output sum, repeated wires from the same predecessor gate can be combined by adding their scalar coefficients. There are at most S distinct predecessors. Thus g is a sum of at most S scalar multiples of products
and each Q_j is a sum of at most S scalar multiples of products of e_j homogeneous linear forms. Zero upper terms have been discarded, and degree-zero factors in the remaining terms have been absorbed into their coefficients. If empty sums or products are allowed, they contribute only zero or a scalar and are handled in the same way.
In (9), inputs to a product are counted with multiplicity: repeated use of a gate gives repeated factors. Their positive degrees add to n, so r\le n. Shared subcircuits do not affect the bounds on the number of distinct additive predecessors. In particular, this description does not charge for wires or impose any restriction on the support of a linear form.
Suppose first that every e_j<t_0. By (6),
Apply Lemmas 3.2 and 3.3, weakening q^{d_{e_j}} to q^{d_{e_j}/2} for even degrees. The combined even-degree correction is at most \exp(4C_1\sqrt n). Consequently
where we used q\le n^{-2/5} and s\ge\sqrt n/2.
Now suppose that one factor occurrence has degree e\ge t_0. Expand that occurrence, using its middle sum, into at most S products of e homogeneous linear forms. All other factors remain unexpanded. This includes any other occurrences of the same gate: expanding one occurrence in Q^h leaves its other h-1 occurrences unexpanded.
In each resulting product, the e newly supplied linear factors contribute H_1^e\le q^{\lambda e/2} to the estimate of Lemma 3.2, because d_1=\lambda and 1<t_0. There are at most n/t_0=4s remaining factor occurrences of degree at least t_0, and their H-factors are at most 5 each. The remaining low odd degrees contribute at most 1. The remaining low even degrees contribute at most \exp(4C_1\sqrt n) after their favorable powers of q are dropped. Rank subadditivity over the expansion therefore yields
For the last step, q\le n^{-2/5} and \lambda\ge3/8, t_0\ge\sqrt n/4 imply \lambda t_0/5\ge3\sqrt n/160.
Since 5^{4s}\le\exp(4\log(5)\sqrt n), both (10) and () are at most
for an absolute C. Multiplication by a nonzero scalar leaves rank unchanged, and multiplication by zero gives rank zero. Summing the at most S upper-product contributions proves the proposition.
4 Trace moments for iterated matrix multiplication
We now choose the partition of the layers and prove that its mixed operator has large rank on iterated matrix multiplication. The parameters remain those of (3). Arrange the groups along the matrix product in the order
For sufficiently large n we have 0<s/k<1, so each \ell_i is either one or two. Their sum is k+s=m. Thus this word has exactly k layers in V and m in U, and no two V layers are adjacent. Every layer contributes all its n^2 variables to its group, including the variables of the first and last matrices that do not occur in the (1,1) entry.
Put f=\IMM_{n,n} and L=n-1. A path P is a sequence (p_0,\ldots,p_n) with p_0=p_n=1 and p_1,\ldots,p_{n-1}\in[n]. Its coordinate in layer t is
There are n^L paths, and f is the sum of the products of their layer coordinates. In particular, f has bidegree (k,m), so its finite map F_f is the restriction of the full operator T_f=f(\partial_V,U) to \HH_V(a)\otimes\HH_U(b).
Proposition 4.1. Over \C, for the partition (12), there is an absolute constant C such that, for all sufficiently large n,
The proof uses two trace moments. Give every homogeneous polynomial space the inner product in which
is an orthonormal basis. This is the finite homogeneous part of the Bargmann–Fock polynomial normalization [5]. Use the tensor product of these inner products for the domain and codomain of F_f, and write
If T>0, Cauchy–Schwarz applied to the nonzero eigenvalues of F_f^*F_f gives
Define
We will prove the bounds
This section reduces the second bound to a sum over two-letter words; the next section bounds that sum and completes Proposition 4.1.
4.1 Occupation moments
A uniformly chosen basis vector of \HH_V(a)\otimes\HH_U(b) has two independent exponent vectors: one is uniform among weak compositions of a into v parts, and the other among weak compositions of b into u parts. We compare their moments with those of independent geometric variables. For an integer d\ge0, write
with both empty products equal to one.
Lemma 4.2. Let M=(M_1,\ldots,M_r) be uniform among the weak compositions of an integer t\ge0 into r\ge1 parts. For integers d_i\ge0 and H=\sum_i d_i,
The right side is zero when H>t.
Let Z_1,\ldots,Z_r be independent geometric variables on the nonnegative integers with mean G=t/r. If a polynomial P has nonnegative coefficients in the basis \{\prod_i(z_i)_{d_i}\}, then
If t>0 and all terms of that expansion have total order at most H_0\le t/2, then also
Proof. For d\ge0,
If H\le t, coefficient extraction therefore gives
Divide by \binom{t+r-1}{t} to obtain (14). If H>t, every composition has M_i<d_i for some i, so every summand is zero, as is (t)_H.
For G>0, the geometric law is
and its factorial moment is \mathbb E(Z_i)_d=d!G^d. For H\le t the ratio of the moment in (14) to the corresponding independent geometric moment is
It is at most one. For H>t the composition moment is zero, so the same upper comparison holds. When H\le H_0\le t/2, the inequalities \log(1-x)\ge-2x for 0\le x\le1/2 and \log(1+x)\le x for x\ge0 show that the logarithm of (17) is at least
Sum these comparisons with the nonnegative coefficients of P. If t=0, both M and the geometric vector of mean zero are identically zero, giving (15) directly.
The comparison is termwise and does not assert independence of the coordinates of M. We apply it separately in the two groups. By Lemma 2.1, total orders at most 2n satisfy the lower-bound hypothesis, and their combined logarithmic loss is
4.2 The first trace
In the chosen orthonormal bases, differentiation and multiplication act by
The derivative is zero when M_i=0; its displayed expression is used only when M_i\ge1. Here \mathbf e_i is the coordinate unit vector. In particular, repeated differentiation of order d has coefficient \sqrt{(M_i)_d}, with no additional factorial divisor.
Index a domain basis vector by the combined exponent vector M on V\cup U, with totals a and b in the two groups. The summand of F_f corresponding to a path P shifts this vector by
with coefficient
A shift requiring a negative occupation contributes zero. We extend the coefficient notation by zero to invalid input indices as well. Different layers have disjoint coordinates, so a path never repeats a coordinate. Moreover, the shifts \epsilon_P are distinct: a shift specifies the coordinate in every layer and hence every vertex of P.
Consequently different paths from the same input reach different output indices. Summing the squared entries of F_f gives the exact identity
where the expectation is over the uniform domain indices. Every polynomial inside this expectation has nonnegative falling-factorial coefficients. Under independent geometric occupations of means A and B, its expectation is \mu. Lemma 4.2 and (18) therefore imply
The inactive endpoint coordinates are included in the uniform compositions and in v,u throughout; they introduce no additional factor into this calculation.
4.3 Four paths in the second trace
The matrix entries of F_f in these bases are real and nonnegative. An entry of F_f^*F_f indexed by M,M' is the sum of c_P(M)c_Q(M') over pairs of paths satisfying M+\epsilon_P=M'+\epsilon_Q. Squaring its entries and summing yields
The zero convention handles invalid indices. There is no additional sum over M', because M,P,Q determine it.
The condition on four paths holds separately in each layer. Denoting their four coordinates in that layer by p,q,r,s, respectively, it is \mathbf e_p-\mathbf e_q=\mathbf e_r-\mathbf e_s. If this difference is zero, then p=q and r=s. Otherwise its positive and negative coordinates force p=r and q=s, with p\ne q. Thus there are exactly two types:
The all-equal case belongs to \mathcal N. For each compatible quadruple, the four-coefficient product in (21) is a product over layers of the following polynomials:
Indeed, the shift from M to M' is zero in type \mathcal N. In a V layer of type \mathcal D it is -\mathbf e_i+\mathbf e_j, so the two coefficients at M contribute M_i and the two at M' contribute M_j+1. In a U layer of type \mathcal D the shift is \mathbf e_i-\mathbf e_j, giving (M_i+1)M_j instead.
These polynomial formulas also account for invalid indices. In type \mathcal D, a negative coordinate of M' requires M_i=0 in a V layer or M_j=0 in a U layer, and the corresponding table entry vanishes. In type \mathcal N, an unavailable derivative makes M_iM_j zero. Since different layers use distinct coordinates, these exhaust the possible failures. Thus the product in (22) equals the zero-extended contribution.
When i=j in type \mathcal N, the required expansions are
All other table entries are products of (z)_1 and (z)_1+1 on distinct coordinates. Hence every product of local entries has nonnegative falling-factorial coefficients, with order at most 2k in V and 2m in U. Lemma 4.2 bounds its expectation by the expectation for independent geometric occupations.
For a geometric variable Z of mean G, \mathbb EZ^2=2G^2+G and \mathbb E(Z+1)^2=2G^2+3G+1. Dividing the geometric expectations in each V layer by A^2 and in each U layer by (1+B)^2, we obtain
Here (A+1)/A=\alpha^{-1} and B/(B+1)=\beta. For example, the repeated-coordinate V entry is (2A^2+A)/A^2=1+\alpha^{-1}, so the repeated factorial contribution has been retained. The product of the normalizing factors over all layers is \mu^2.
4.4 A sum over pairing types
Assign to a compatible quadruple its type word \tau\in\{\mathcal N,\mathcal D\}^n. For each such word, enlarge its class of quadruples by dropping the inequalities i\ne j at all \mathcal D layers. Keep their weights equal to \alpha^{-1} and \beta as in (23). These are assigned weights on the newly admitted tuples, not their geometric occupation moments. Every original tuple retains its weight, and every new weight is nonnegative, so this enlargement gives an upper bound.
Equality of matrix-entry coordinates equates the path labels at both ends of that layer. The relaxed equalities can therefore be counted independently at every internal vertex. A layer of type \mathcal N pairs the paths as \{P,Q\},\{R,S\}, while a layer of type \mathcal D pairs them as \{P,R\},\{Q,S\}. At a vertex between layers of the same type, there are two free labels in [n]. At a vertex between different types the two pairings together identify all four labels, leaving one free label. These give n^2 and n choices, respectively, as illustrated in Figure 1. The two external vertex labels are fixed to 1. Every independent choice at the internal vertices gives four paths, because all matrix entries are available, and every relaxed quadruple arises uniquely this way. The set of assignments is therefore a Cartesian product over internal vertices. If
the number of assignments is exactly n^{2L-w(\tau)}.
Figure 1: Equality constraints on the four path labels at one internal vertex after the \mathcal D inequalities are relaxed. Type \mathcal N pairs P,Q and R,S (solid edges); type \mathcal D pairs P,R and Q,S (dashed edges). Equal neighboring types leave two free labels. A change of type identifies all four, contributing a factor n^{-1} to the count. The same two-label count holds for neighboring types \mathcal D,\mathcal D.
For a layer t of type \mathcal N, let h_t be the number of its end vertices that are internal and lie between two layers of type \mathcal N. At each of these vertices the two free labels are independent and uniform in [n], so they agree with probability 1/n. At an external vertex or an interface between different types the labels already agree. Consequently the two coordinates i,j of this \mathcal N layer agree with probability n^{-h_t}.
The end-vertex sets of different V layers are disjoint, because no two V layers are adjacent in (12). Under the uniform distribution on the Cartesian product of relaxed vertex assignments, the equality events just described are therefore independent for the \mathcal N layers in V. Their average weight is
For each \mathcal N layer in U we instead bound its weight pointwise by 1+\beta, so no independence assertion for these layers is needed.
Write d_V(\tau) and d_U(\tau) for the numbers of \mathcal D layers in V and U, respectively, and put N_V(\tau)=\{t:t\text{ is in }V,\ \tau_t=\mathcal N\}. Combining the occupation comparison, the relaxed assignment count, and the preceding weight estimates proves
Since \beta\le2/\sqrt n, the factor (1+\beta)^m is \exp(O(\sqrt n)). It remains to prove the same bound for the word sum in (24). Lemma 5.1 establishes this using the spacing of the V layers and the balanced schedule.
5 Bounding the path-type sum
We now bound the sum in (24). The coincidence factor at an interior V layer can be large only when both neighboring layers have the opposite type. Removing these isolated positions and bounding the endpoint factors will leave a sum controlled by the number of runs of \mathcal D layers.
Lemma 5.1. For all sufficiently large n, use the layer schedule (12) and the parameters \alpha,\beta,\rho of (3). For a word \tau\in\{\mathcal N,\mathcal D\}^n, let w(\tau) be its number of switches, let d_V(\tau),d_U(\tau) count its \mathcal D positions in the respective variable groups, and let N_V(\tau) be its set of \mathcal N positions in group V. For t\in N_V(\tau), let h_t be the number of internal vertices adjacent to layer t whose two incident layers both have type \mathcal N. There is an absolute constant C such that
Proof. Denote the summand on the left of (25) by W(\tau). Call a position isolated if it is an interior V layer with type \mathcal N and both its neighbors have type \mathcal D. Change every isolated position to type \mathcal D, obtaining a word F(\tau). No two V layers are adjacent, so none of their neighbors is changed. It follows that F(\tau) has no isolated position, and the values of h_t at its remaining \mathcal N_V positions are unchanged.
Each changed position has h_t=0 before the change. Its two incident switches disappear, its factor 1+\alpha^{-1} disappears, and a factor \alpha^{-1} is introduced. Switches removed at distinct positions are distinct, even when those positions are separated by only one U layer. Thus, if j positions were changed,
The preimages can be counted exactly. For a word y with no isolated position, let E(y) be the set of interior V positions whose type and both neighboring types are \mathcal D. Its preimages are obtained by changing an arbitrary subset of E(y) to \mathcal N. These positions are nonadjacent, their neighbors remain unchanged, and the operation creates precisely the isolated positions that are changed back by F. Consequently
where 0<\alpha<1 and |E(y)|\le k were used.
In a word with no isolated position, every interior \mathcal N_V position has h_t\ge1. An endpoint position can have h_t=0; there is at most one endpoint V layer, since the schedule starts with V and ends with U. Hence
Here we enlarged the final sum from words without isolated positions to all words. By Lemma 2.1, \alpha^{-1}\le\sqrt n and k\le n/2, so the logarithm of the prefactor is at most
It remains to bound Z. A run of \mathcal D positions is a maximal nonempty interval of such positions. Each interior run has two switches, contributing n^{-2}, whereas a run meeting exactly one endpoint has one switch. We will show that the product of layer weights on every run is at most n times a rounding factor. Thus the switch costs leave a factor n^{-1} for every interior run.
The relation between \alpha and \beta reduces the layer weight to a discrepancy between the two layer counts. For an interval I of consecutive layers, define
We claim that
Indeed, r consecutive complete chunks of the schedule, starting after chunk j, contain r layers in V and r+E layers in U, where
Using m=k+s and \rho=k/m, their discrepancy is
An interval spanning several chunks consists of consecutive complete chunks, possibly preceded by a proper terminal part of one chunk and followed by a proper initial part of another. The terminal part contains only U layers and has nonpositive discrepancy; the initial part contains at most one V layer and has discrepancy at most 1. An interval contained in a single chunk also has discrepancy at most 1. This proves the first assertion of (28). The second is the identity k-\rho m=0.
By Lemma 2.1, the product of layer weights on a \mathcal D run I is at most
For the last inequality, the sign of d(I) causes no difficulty:
since 0<\alpha<1, \alpha\ge n^{-1/2}, and \rho<1. The runs are disjoint, so all their rounding factors together contribute at most \exp(Cn/b).
Consider a mixed word, meaning one containing both types. Let r be its number of interior \mathcal D runs and e its number of \mathcal D runs meeting an endpoint. A mixed word has no run meeting both endpoints, so e\in\{0,1,2\} and
There are r+e runs. Their weight, including the switch factors, is therefore at most
The initial type and the set of switch positions uniquely specify a word. Thus at most 2\binom{n-1}{2r+e} words have given values of r,e. Taking binomial coefficients outside their usual range to be zero, the mixed-word contribution to Z is at most
To see the last inequality, for each e\in\{0,1,2\} use
The constant word \mathcal N^n has weight 1. The other constant word has weight
It follows that
where b=\Theta(n^{5/2}). Combining this with (27) proves the lemma.
Completion of the proof of Proposition 4.1. Lemma 5.1, applied to (24), gives
because \beta\le2/\sqrt n and m\le n. By (20),
For the positive semidefinite matrix H=F_f^*F_f, the Cauchy–Schwarz inequality applied to its nonzero eigenvalues yields
Since T>0 and \rank(H)=\rank(F_f)=R(f), the two moment bounds imply
This is the assertion of Proposition 4.1.
6 Completion and consequences
We compare the two rank bounds for the balanced partition of the matrix layers. We then transfer the resulting lower bound to every field of characteristic zero and give an elementary upper bound of the same order in the exponent.
Proof of Theorem 1.1. Let a syntactically homogeneous \Sigma\Pi\Sigma\Pi\Sigma circuit over \C of size S compute f=\IMM_{n,n}. Use the partition from Proposition 4.1. For all sufficiently large n, Propositions 4.1 and 3.1 give absolute constants C_1,C_2>0 such that
Since D>0, cancellation and square roots yield
After increasing the absolute threshold for n, the exponential factor and 2^{-1/2} are absorbed by n^{\sqrt n/400}. Therefore S\ge n^{\sqrt n/400}, as asserted.
The inner products in Proposition 4.1 were used over \C, but its conclusion concerns the rank of a matrix defined over the integers. This gives a field-independent consequence.
Corollary 6.1. 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.
Proof. Fix n and the parameters and partition used in Proposition 4.1. Express F_{\IMM_{n,n}} in ordinary monomial bases of both its domain and codomain. The coefficients of \IMM_{n,n} are integers, multiplication has integral matrix entries, and differentiation has integral matrix entries: a repeated derivative acts by a product of falling factorials of nonnegative integers. Consequently this finite matrix has entries in \Z.
Every minor is an integer. Under the natural map \Z\longrightarrow K, an integer is zero precisely when it was zero in \Z, because K has characteristic zero. The same holds over \C. Thus the largest order of a nonzero minor, and hence the rank, is the same over K and over \C. Changing from ordinary monomials to the normalized bases used in the complex moment argument does not change that complex rank. Proposition 4.1 therefore supplies its lower bound over K. Proposition 3.1 holds over every field, with the same constants. The preceding comparison proves the corollary with an absolute threshold independent of K.
A direct block construction gives an upper bound of the form n^{\sqrt n+O(1)}. The next count includes variable leaves and permits the computed block entries to be shared.
Proposition 6.2. Let K be any field and n\ge2. Put
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
Proof. Partition the n consecutive matrix layers into r nonempty consecutive blocks, with lengths \ell_1,\ldots,\ell_r\le t. For block j, let Y^{(j)} be the product of its matrices. An entry Y^{(j)}_{a,b} is a sum of n^{\ell_j-1} monomials, one for each choice of the internal indices of that block, and each monomial has degree \ell_j.
At the bottom sum layer, use one identity sum gate for each variable, sharing it among all its uses. This requires at most n^3 leaves and n^3 bottom sum gates. For every block and each of its n^2 entries, compute the displayed monomials by lower product gates and add them at a middle sum gate. Thus block j uses n^{\ell_j+1} lower product gates and n^2 middle sum gates. When \ell_j=1, the product and sum gates have one input; all five computational layers are still present.
Set a_0=a_r=1. Matrix multiplication now gives
For r=1 the right-hand side means the single entry Y^{(1)}_{1,1}. Use one upper product gate for each of the n^{r-1} summands, and one output sum gate. Each block-entry gate is shared by all summands that use it. The upper products have formal degree \ell_1+\cdots+\ell_r=n, and every middle sum adds monomials of its block’s degree. The bottom sums have degree one, so the whole circuit is syntactically homogeneous. Any gates that do not feed the output may be discarded.
The gate count is at most
which proves the first bound in (29). For the second, note that r\le t\le n. If n\ge3, then t\ge2 and the first bound is at most
Here 3n^3\le n^{t+2} and n^{t-1}+1\le n^{t+2} justify the middle estimate. For n=2, the first bound is 30\le2^5 and t=2, giving the same conclusion.
References
- [1]Manindra Agrawal and V. Vinay. Arithmetic Circuits: A Chasm at Depth Four. Technical Report TR08-062, Electronic Colloquium on Computational Complexity, 2008. https://eccc.weizmann.ac.il/report/2008/062/.
- [2]Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, and Bhargav Thankey. Low-depth arithmetic circuit lower bounds via shifted partials. 2022. Version 1, 14 November 2022; full-version theorem and proof locators. arXiv:2211.07691, https://arxiv.org/abs/2211.07691v1.
- [3]Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, and Bhargav Thankey. Low-Depth Arithmetic Circuit Lower Bounds: Bypassing Set-Multilinearization. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), pages 12:1–12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.ICALP.2023.12.
- [4]Jules Armand, Amik Raj Behera, and Sébastien Tavenas. Lower Bounds for Depth-5 Algebraic Circuits with Bounded Fan-in of Top Product Gates. Technical Report TR26-104, Electronic Colloquium on Computational Complexity, 2026. 24 June 2026. https://eccc.weizmann.ac.il/report/2026/104/.
- [5]V. Bargmann. Remarks on a Hilbert Space of Analytic Functions. Proceedings of the National Academy of Sciences of the United States of America, 48(2):199–204, 1962. doi:10.1073/pnas.48.2.199.
- [6]Suman K. Bera and Amit Chakrabarti. A Depth-Five Lower Bound for Iterated Matrix Multiplication. In David Zuckerman, editor, 30th Conference on Computational Complexity (CCC 2015), pages 183–197, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2015. doi:10.4230/LIPIcs.CCC.2015.183.
- [7]C. S. Bhargav, Sagnik Dutta, and Nitin Saxena. Improved Lower Bound, and Proof Barrier, for Constant Depth Algebraic Circuits. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), pages 18:1–18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.MFCS.2022.18.
- [8]Michael A. Forbes. Low-Depth Algebraic Circuit Lower Bounds over Any Field. In 39th Computational Complexity Conference (CCC 2024), pages 31:1–31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.CCC.2024.31.
- [9]Hervé Fournier, Nutan Limaye, Guillaume Malod, and Srikanth Srinivasan. Lower Bounds for Depth 4 Formulas Computing Iterated Matrix Multiplication. SIAM Journal on Computing, 44(5):1173–1201, 2015. Theorem locators refer to the linked author manuscript dated 6 June 2015. doi:10.1137/140990280.
- [10]Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi. Approaching the Chasm at Depth Four. Journal of the ACM, 61(6):33:1–33:16, 2014. Linked preprint: ECCC TR12-098, revision 3, 4 September 2013. doi:10.1145/2629541.
- [11]Neeraj Kayal. An Exponential Lower Bound for the Sum of Powers of Bounded Degree Polynomials. Technical Report TR12-081, Electronic Colloquium on Computational Complexity, 2012. Revision 1, 7 September 2012. https://eccc.weizmann.ac.il/report/2012/081/revision/1/download/.
- [12]Neeraj Kayal, Nutan Limaye, Chandan Saha, and Srikanth Srinivasan. An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas. Technical Report TR14-005, Electronic Colloquium on Computational Complexity, 2014. https://eccc.weizmann.ac.il/report/2014/005/.
- [13]Neeraj Kayal, Chandan Saha, and Sébastien Tavenas. On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree. Theory of Computing, 14(16):1–46, 2018. doi:10.4086/toc.2018.v014a016.
- [14]Pascal Koiran. Arithmetic Circuits: The Chasm at Depth Four Gets Wider. Theoretical Computer Science, 448:56–65, 2012. Linked preprint: version 4, 23 March 2012; first posted in 2010. doi:10.1016/j.tcs.2012.03.041, arXiv:1006.4700.
- [15]Mrinal Kumar and Ramprasad Saptharishi. An Exponential Lower Bound for Homogeneous Depth-5 Circuits over Finite Fields. In Ryan O'Donnell, editor, 32nd Computational Complexity Conference (CCC 2017), pages 31:1–31:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017. doi:10.4230/LIPIcs.CCC.2017.31.
- [16]Mrinal Kumar and Shubhangi Saraf. On the Power of Homogeneous Depth 4 Arithmetic Circuits. SIAM Journal on Computing, 46(1):336–387, 2017. Theorem locators refer to arXiv:1404.1950v1, 7 April 2014. ECCC TR14-045, revision 2, 13 January 2015. doi:10.1137/140999335, arXiv:1404.1950.
- [17]Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas. Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits. Technical Report TR21-081, Electronic Colloquium on Computational Complexity, 2021. Revision 1, 6 July 2021. https://eccc.weizmann.ac.il/report/2021/081/revision/1/download.
- [18]Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas. Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits. Journal of the ACM, 72(4), 2025. Article 26, 35 pages. doi:10.1145/3734215.
- [19]Noam Nisan and Avi Wigderson. Lower Bounds on Arithmetic Circuits via Partial Derivatives. In 36th Annual Symposium on Foundations of Computer Science, pages 16–25, 1995. Section locators refer to the linked author journal manuscript. https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/NW96/final.pdf.
- [20]Sébastien Tavenas. Improved Bounds for Reduction to Depth 4 and Depth 3. Information and Computation, 240:2–11, 2015. Theorem locators refer to arXiv:1304.5777v2, 16 May 2014. doi:10.1016/j.ic.2014.09.004, arXiv:1304.5777.