Fix an integer n >= 1 and let X^(1), X^(2), ..., X^(n) be n-by-n matrices of
distinct commuting variables, X^(t) = (x^(t)_{i,j} : 1 <= i, j <= n). The
variables x^(t)_{i,j}, over all t, i, j, are n^3 in number. The iterated
matrix multiplication polynomial is the (1,1) entry of the matrix product:
IMM_{n,n} = (X^(1) X^(2) ... X^(n))_{1,1}
= sum over (p_1, ..., p_{n-1}) in [n]^{n-1}
of x^(1)_{1,p_1} x^(2)_{p_1,p_2} ... x^(n)_{p_{n-1},1}.
The sum runs over all n^(n-1) index sequences ("paths"); each summand is a
distinct monomial of degree n; so IMM_{n,n} is homogeneous of degree n in
the n^3 ambient variables. Most ambient variables are absent from
IMM_{n,n}. For n=2, with X^(1) = [[a,b],[c,d]] and X^(2) = [[e,f],[g,h]],
the (1,1) entry of the product is ae + bg, so IMM_{2,2} =
x^(1)_{1,1} x^(2)_{1,1} + x^(1)_{1,2} x^(2)_{2,1}: two paths, two
monomials. (For n=1 the expression is x^(1)_{1,1}.)
A five-layer Sigma-Pi-Sigma-Pi-Sigma arithmetic circuit over a field K is a
finite directed acyclic graph whose vertices are variable leaves x_i,
constant leaves c in K, sum gates computing K-linear combinations of their
inputs, and product gates computing their products. Fan-in, fan-out, and
gate sharing are unrestricted; the size of the circuit is the total number
of its vertices, including leaves. In the five-layer arrangement the gate
types read +, x, +, x, + from output to leaves. Edges connect only
consecutive computational layers, and the leaves lie directly beneath the
bottom sum gates. A single top sum gate produces the output. Unary gates
are permitted, and scalar coefficients on sum wires do not count as gates.
A circuit is syntactically homogeneous if some formal-degree assignment
assigns degree 1 to each variable, degree 0 to each constant, degree to
each product gate equal to the sum of its input degrees with multiplicity,
degree to each sum gate equal to its (common) input degree, and degree n
to the output gate. The degree is syntactic, not semantic: a gate
computing the zero polynomial still carries its assigned formal degree,
and cancellation does not reset it. The lower bound applies even if
the circuit cancels heavily.
Main theorem. There are absolute constants c > 0 and n_0 such that, for
every integer n >= n_0 and every field K of characteristic zero, every
syntactically homogeneous five-layer circuit over K computing IMM_{n,n}
has size at least n^(c sqrt(n)). One may take c = 1/400.
A block construction gives the matching upper bound: for every field K and
every n >= 2, there is a syntactically homogeneous five-layer circuit of
size at most n^(sqrt(n) + 4) computing IMM_{n,n}. Combined with the lower
bound, the gate complexity of IMM_{n,n} in this model is n^(Theta(sqrt n)).
Unrestricted-depth circuits compute IMM_{n,n} in polynomial size; the
constraint that produces the sqrt(n) exponent is depth.
The technique traces to Nisan and Wigderson, who proved lower bounds on
homogeneous depth-three and constant-depth set-multilinear circuits using
dimensions of spaces of partial derivatives, and who asked whether an
explicit homogeneous polynomial could require superpolynomial size at
constant depth, singling out depth five as the natural test case.
nisan-wigderson-1995.pdf
https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/NW96/final.pdf
Depth reduction explains the square-root scale. Agrawal and Vinay showed
that an N^(O(1))-size formula in N variables reduces to depth four of size
N^(O(sqrt d)); Koiran sharpened the constant; Tavenas gave the current
sharp version. The block construction for IMM follows the same substitution
of d matrix layers into d blocks.
agrawal-vinay-2008.pdf
https://eccc.weizmann.ac.il/report/2008/062/
koiran-2012.pdf
https://arxiv.org/abs/1006.4700v4
tavenas-2013.pdf
https://arxiv.org/abs/1304.5777v2
Lower bounds for restricted IMM computations have followed that scale.
Fournier, Limaye, Malod, and Srinivasan proved depth-four IMM lower bounds
with bounds on both product-layer fan-ins, and separately for homogeneous
multilinear formulas. 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. Kumar and Saraf proved a d^(Omega(sqrt d)) lower bound for
homogeneous depth-four circuits computing IMM_{d^5, d}, over every field.
Kayal, Saha, and Tavenas extended this to w^(Omega(sqrt d)) for
syntactically multilinear depth-four circuits in the range d >= log^2 w,
without homogeneity.
fournier-limaye-malod-srinivasan-2015.pdf
https://webusers.imj-prg.fr/~herve.fournier/publications/imm.pdf
kayal-limaye-saha-srinivasan-2014.pdf
https://eccc.weizmann.ac.il/report/2014/005/
kumar-saraf-2014.pdf
https://arxiv.org/abs/1404.1950v1
kayal-saha-tavenas-2018.pdf
https://theoryofcomputing.org/articles/v014a016/v014a016.pdf
At depth five, Bera and Chakrabarti proved lower bounds with a restriction on
bottom support: for every fixed 0 <= mu < 1/2 there is q = q(mu) such that
homogeneous depth-five 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. Kumar and Saptharishi proved exp(Omega_q(sqrt d))
lower bounds for homogeneous depth-five circuits over each fixed finite field
F_q, for a Nisan-Wigderson design family in VNP. Armand, Behera, and
Tavenas extended the finite-field approach to depth-five circuits whose
top-product fan-in is bounded by a fixed polynomial in the degree, without
requiring homogeneity. These finite-field results concern Nisan-Wigderson
designs rather than IMM; both the field hypothesis and the exponential rate
differ from the IMM theorem.
bera-chakrabarti-2015.pdf
https://drops.dagstuhl.de/storage/00lipics/lipics-vol033-ccc2015/LIPIcs.CCC.2015.183/LIPIcs.CCC.2015.183.pdf
kumar-saptharishi-2017.pdf
https://drops.dagstuhl.de/storage/00lipics/lipics-vol079-ccc2017/LIPIcs.CCC.2017.31/LIPIcs.CCC.2017.31.pdf
armand-behera-tavenas-2026.pdf
https://eccc.weizmann.ac.il/report/2026/104/
Superpolynomial lower bounds for unrestricted-bottom depth-five circuits
over characteristic zero were already known through the constant-depth work
of Limaye, Srinivasan, and Tavenas. Their product-depth convention counts
multiplication gates on a path, so five computational layers correspond to
product-depth two. In the low-degree regime d <= (log w)/100 their Corollary
3 gives w^(Omega(sqrt d)) over every field, and their general results
include a superpolynomial lower bound for IMM_{n,n} over C. Bhargav, Dutta,
and Saxena improved the constant-depth exponents in the low-degree regime.
Forbes established low-depth IMM lower bounds over arbitrary fields in the
regime d = o(log w).
limaye-srinivasan-tavenas-2021.pdf
https://eccc.weizmann.ac.il/report/2021/081/revision/1/download
bhargav-dutta-saxena-2022.pdf
https://drops.dagstuhl.de/storage/00lipics/lipics-vol241-mfcs2022/LIPIcs.MFCS.2022.18/LIPIcs.MFCS.2022.18.pdf
forbes-2024.pdf
https://drops.dagstuhl.de/storage/00lipics/lipics-vol300-ccc2024/LIPIcs.CCC.2024.31/LIPIcs.CCC.2024.31.pdf
Amireddy, Garg, Kayal, Saha, and Thankey gave a direct shifted-partials
approach, obtaining 2^(-O(d)) w^(Omega(sqrt d)) for homogeneous
product-depth-two formulas in the range w = omega(d), over every field. The
degree-dependent loss and the hypothesis w = omega(d) prevent direct
substitution into w = d = n. The present argument closes that gap for
IMM_{n,n} at the same depth, using intermediate-dimensional bounds indexed
by integer-degree discrepancies rather than the residue method that drives
their proof.
amireddy-garg-kayal-saha-thankey-2022.pdf
https://arxiv.org/abs/2211.07691v1
amireddy-garg-kayal-saha-thankey-2023.pdf
https://drops.dagstuhl.de/storage/00lipics/lipics-vol261-icalp2023/LIPIcs.ICALP.2023.12/LIPIcs.ICALP.2023.12.pdf
The shifted-partials method behind several of these bounds has older roots.
Kayal introduced shifted partial derivatives and used them to prove an
exponential lower bound for the sum of powers of bounded-degree polynomials.
Gupta, Kamath, Kayal, and Saptharishi applied shifted partials to depth-four
questions and gave the first superpolynomial lower bounds against depth-four
circuits of product-depth two. The present argument uses partial-derivative
dimensions but restricts derivatives to one variable group and
multiplications to the disjoint group; the two-group split keeps the
resulting linear map finite-dimensional and its rank exactly the trace
moment, whereas classical shifted-partials analyses track
a coarser span dimension.
kayal-2012.pdf
https://eccc.weizmann.ac.il/report/2012/081/revision/1/download
gupta-kamath-kayal-saptharishi-2014.pdf
https://eccc.weizmann.ac.il/report/2012/098/revision/3/download
In the lower-bound analysis the space of homogeneous degree-t polynomials in
a variable set E is given the inner product in which the monomials
z^M / sqrt(M!) are orthonormal, where M! = prod_i M_i! and |M| = t. This is
the finite homogeneous part of the Bargmann-Fock normalization, and in it
differentiation and multiplication act with square roots of local
occupations.
https://www.pnas.org/doi/10.1073/pnas.48.2.199
The proof proceeds in four steps. First, define a rank measure from
differentiation and multiplication. Second, show that any small circuit has
small rank. Third, show that IMM_{n,n} has large rank. Fourth, combine.
For the first step, let V and U be disjoint sets of variables, |V| = v and
|U| = u. Fix nonnegative integers k, m, a, b with a >= k. If g is
homogeneous of total degree n = k + m, let g_{[k,m]} denote its component
of V-degree k and U-degree m. Replace every V-variable by the formal
partial derivative with respect to that variable, and every U-variable by
multiplication by that variable. This produces a K-linear map
F_g : H_V(a) tensor H_U(b) -> H_V(a - k) tensor H_U(b + m),
where H_E(t) is the space of homogeneous degree-t polynomials in the
variables of E. Set R(g) = rank(F_g), with Dim = h(v, a) h(u, b) = dim of
the source, h(r, t) = C(r + t - 1, t). The rank is subadditive in g, because
bidegree projection is linear; it is invariant under nonzero scalar
multiplication; and R(0) = 0. It is not multiplicative, but the underlying
substitution operators commute (V and U are disjoint), and a product of
homogeneous polynomial factors decomposes along bidegrees in a controlled
way.
For the second step, choose the parameters. Set s to be the largest integer
at most sqrt(n) that has the same parity as n, and put k = (n - s)/2,
m = (n + s)/2, rho = k/m, lambda = k/n = rho/(1 + rho), v = k n^2,
u = m n^2, a = ceil(v / (sqrt(n) - 1)), alpha = a/(a + v),
b = ceil(u alpha^rho / (1 - alpha^rho)), beta = b/(b + u),
q = alpha^((1 + rho)/2), Dim = h(v, a) h(u, b). All are functions of n.
The resulting quantity a is of order n^(5/2), as are b and Dim^(1/(n^3)).
The proof also uses two auxiliary quantities: d_e = dist(lambda e, Z) for
each positive integer e, and t_0 = n/(4s). The parameter alpha is close to
n^(-1/2), beta is close to alpha^rho, and q is close to n^(-1/2) with
higher-order corrections. These facts are elementary; they add up to a
list of estimates used repeatedly.
For the third step, if g is computed by a syntactically homogeneous
five-layer circuit of size S, then
R(g) <= 2 S^2 Dim exp(C sqrt(n)) n^(-sqrt(n)/100)
for an absolute constant C. The argument expands the circuit into at most S
upper products, one for each distinct product gate feeding the output;
each upper product has factors from at most S distinct middle sums, each of
which is a sum of at most S products of homogeneous linear forms. For each
upper product, the product-rank bound is applied factor by factor. A factor
of large degree is expanded once into its bottom linear factors, at cost at
most one additional factor of S. A factor of small degree is bounded by its
degree-discrepancy from the integer grid; small even degrees require a
combined-error estimate rather than the naive per-factor bound.
For the fourth step, fix the polynomial f = IMM_{n,n}, and order the matrix
layers as
V U^(l_1) V U^(l_2) ... V U^(l_k)
with l_i = 1 + floor(i s / k) - floor((i - 1) s / k). Then each l_i is 1
or 2, sum_i l_i = k + s = m, and no two V-layers are adjacent. The trace
moments T = tr(F_f^* F_f) and T_2 = tr((F_f^* F_f)^2) become weighted
counts of paths and of quadruples of paths in IMM's expansion; the trace
inequality R(f) >= T^2/T_2 then gives
R(f) >= Dim exp(-C sqrt(n))
over C. The proof of the moment estimates is the technical core of the
argument.
Combining the circuit bound with the IMM bound (with the same V/U
partition and the same a, b):
S^2 >= (1/2) exp(-2 C sqrt(n)) n^(sqrt(n)/100),
so S >= n^(sqrt(n)/400) for all sufficiently large n. The result extends to
any characteristic-zero field by observing that the linear map F_f has
integer entries in the ordinary monomial bases of its source and target,
so its rank over any characteristic-zero field agrees with its rank over C.
A direct block construction gives the matching upper bound. The four steps,
with the technical details filled in, occupy the rest of the argument.
The rank measure is now made precise. Fix nonnegative integers k, m, a, b
with a >= k. If g is homogeneous of total degree k + m, write g_{[k,m]}
for its component of V-degree k and U-degree m. Define
F_g = g_{[k,m]}(partial_V, U) : H_V(a) tensor H_U(b)
-> H_V(a - k) tensor H_U(b + m),
where partial_V are formal partial derivatives with respect to the V
variables, U denotes multiplication by the U variables, and H_E(t) is the
space of homogeneous degree-t polynomials in the variables of E. The source
dimension is Dim = h(v, a) h(u, b). The rank R(g) = rank(F_g) is
subadditive, invariant under nonzero scalar multiplication of g, and zero
at g = 0.
To bound the rank of a product, introduce the auxiliary quantities
H_e = sum_{i=0}^{e} q^(|i - lambda e|), e >= 1,
where q and lambda are as in the parameter list.
Product-rank lemma. Let Q_1, ..., Q_r in K[V, U] be homogeneous of
respective positive degrees e_1, ..., e_r with sum_j e_j = n. Then
R(prod_j Q_j) <= 2 Dim prod_j H_{e_j}.
Proof. Decompose each factor into its bidegree components. The component of
the product that defines the rank measure is
(prod_j Q_j)_{[k,m]}
= sum over (i_1, ..., i_r), each i_j in [0, e_j], sum_j i_j = k,
of prod_j (Q_j)_{[i_j, e_j - i_j]}.
Fix one such (i_1, ..., i_r), and put delta_j = i_j - lambda e_j. Since
lambda n = k, the deltas sum to zero. The operators T_Q = Q(partial_V, U)
commute among themselves (V and U are disjoint), so the corresponding
finite-rank operators may be applied in any order. Apply first the factors
with delta_j > 0, and let
I = sum_{delta_j > 0} i_j, J = sum_{delta_j > 0} (e_j - i_j).
The intermediate space is H_V(a - I) tensor H_U(b + J). It is well defined
because I <= k <= a and J <= m. The rank of the fixed-assignment
contribution is at most its dimension:
h(v, a - I) h(u, b + J).
Bounds on the dimension ratios follow from monotonicity. For 0 <= I <= a,
h(v, a - I)/h(v, a) = prod_(t=0)^(I-1) (a - t)/(a + v - 1 - t)
<= (a/(a + v - 1))^I,
and for 0 <= J,
h(u, b + J)/h(u, b) = prod_(t=1)^J (b + u + t - 1)/(b + t)
<= ((b + u)/b)^J = beta^(-J).
Because beta >= alpha^rho, the two estimates give
h(v, a - I) h(u, b + J) / Dim <= alpha^(I - rho J) (1 - 1/(a + v))^(-I)
<= 2 alpha^(I - rho J).
The last factor accounts for I <= n and a + v = Theta(n^3); empty products
are 1.
With lambda = rho/(1 + rho) and sum_j delta_j = 0,
I - rho J = (1 + rho) sum_{delta_j > 0} delta_j
= (1 + rho)/2 sum_j |delta_j|.
Since q = alpha^((1 + rho)/2), the rank of the fixed-assignment
contribution is at most 2 Dim prod_j q^(|i_j - lambda e_j|).
Sum these bounds over all (i_j), using subadditivity of rank. Dropping the
constraint sum_j i_j = k only increases the nonnegative sum, which then
factors as 2 Dim prod_j H_{e_j}.
The parameter list is now fixed. Set s to be the largest integer at most
sqrt(n) with the same parity as n, and put
k = (n - s)/2, m = (n + s)/2, rho = k/m, lambda = k/n = rho/(1+rho),
v = k n^2, u = m n^2,
a = ceil(v/(sqrt(n) - 1)), alpha = a/(a + v),
b = ceil(u alpha^rho / (1 - alpha^rho)), beta = b/(b + u),
q = alpha^((1 + rho)/2), Dim = h(v, a) h(u, b).
Also set
d_e = dist(lambda e, Z), t_0 = n/(4s),
for each positive integer e. The quantity d_e measures the distance from
lambda e to the nearest integer: it is small when lambda e is near an even
integer, and near 1/2 when lambda e is near an odd integer. Integer-degree
bidegree projections in the product analysis incur a dimension cost
q^{d_e} in the rank bound for a factor of degree e. The threshold t_0
separates low-degree factors, whose H_e is bounded by q^{d_e} directly,
from high-degree factors, whose low-layer structure contributes many
linear factors.
Parameter lemma. For n sufficiently large, all of the following hold:
(a) sqrt(n)/2 <= s <= sqrt(n);
(b) 3/8 <= lambda < 1/2, 0 < rho < 1;
(c) v, u = Theta(n^3);
(d) a, b = Theta(n^(5/2));
(e) a >= k, and 2n <= min(a, b)/2;
(f) n^(-1/2) <= alpha = n^(-1/2) exp(O(1/a)), alpha^(-1) <= sqrt(n);
(g) alpha^rho <= beta <= alpha^rho exp(C/b), beta <= 2/sqrt(n);
(h) q = n^(-1/2) exp(O(s log n / n + 1/a)),
n^(-1/2) <= q <= 2/sqrt(n) <= n^(-2/5), q <= 1/2.
Proof. (a) The interval [sqrt(n) - 2, sqrt(n)] contains an integer of the
same parity as n, and s is the largest such integer at most sqrt(n), so
sqrt(n)/2 <= s <= sqrt(n) for n >= 16.
(b) lambda = 1/2 - s/(2n). Since 0 < s <= sqrt(n), we have 3/8 <= lambda
< 1/2 for n >= 16, and rho = (n - s)/(n + s) lies in (0, 1).
(c) k = (n - s)/2 and m = (n + s)/2 are both Theta(n), so v = k n^2 and
u = m n^2 are Theta(n^3).
(d) v/(sqrt(n) - 1) = Theta(n^3)/Theta(sqrt(n)) = Theta(n^(5/2)), so
a = Theta(n^(5/2)). By (g), alpha^rho = Theta(n^(-1/2)), so
u alpha^rho/(1 - alpha^rho) = Theta(n^(5/2)), and b = Theta(n^(5/2)).
(e) From (d), k = Theta(n) <= a for n large, and 2n <= min(a, b)/2.
(f) Let f(x) = log(x/(x + v)). Then f'(x) = v/(x(x + v)) <= 1/x. The
mean value theorem on [a_0, a] for any fixed lower bound a_0 gives
0 <= f(a) - f(a_0) <= 1/a_0 = O(1/a). Since f(a_0) = log(1/sqrt(n)) =
-(1/2) log n, log alpha = -(1/2) log n + O(1/a) and
alpha = n^(-1/2) exp(O(1/a)). Then alpha^(-1) <= sqrt(n) exp(O(1/a)) <=
sqrt(n) for n large.
(g) Write 1 - rho = s/m = O(s/n). Then
log(alpha^rho) = rho log alpha
= -(1/2) log n + (s/(2m)) log n + O(1/a)
= -(1/2) log n + O(s log n / n + 1/a),
so alpha^rho = n^(-1/2)(1 + o(1)). Put b_0 = u alpha^rho/(1 - alpha^rho);
then b_0 <= b < b_0 + 1 and b_0/(b_0 + u) = alpha^rho. Applying (f) with
u in place of v on [b_0, b],
0 <= log beta - log(alpha^rho) <= 1/b_0 <= C/b
for an absolute C. This gives alpha^rho <= beta <= alpha^rho exp(C/b).
For n large, alpha^rho <= 2 n^(-1/2) and exp(C/b) <= 2, so beta <=
2/sqrt(n).
(h) Use (1 + rho)/2 = n/(2m) = 1 - s/(n + s). Then
log q = (1 - s/(n + s)) log alpha
= -(1/2) log n + (s log n)/(2(n + s)) + O(1/a).
Both extra terms are nonnegative and O(s log n / n + 1/a), so
q = n^(-1/2) exp(O(s log n / n + 1/a)). The exponential correction is
positive and at most 2 for n large, so n^(-1/2) <= q <= 2/sqrt(n). Since
2/sqrt(n) <= n^(-2/5) iff n >= 1024, and q <= 1/2 for n >= 4, all stated
bounds hold. The lemma is proved.
Factor-degree estimates. There is an absolute constant C_1 with the
following property, for every integer 1 <= e <= n and every sufficiently
large n:
(a) H_e <= q^{d_e}(1 + 4 q^{1 - 2 d_e});
(b) if 1 <= e < t_0, then lambda e = e/2 - s e/(2n) and the nearest
integer to lambda e is e/2 for even e and (e - 1)/2 for odd e, so
d_e = s e/(2n) for even e and d_e = 1/2 - s e/(2n) for odd e; in
particular d_e >= s e/(2n) always, and d_e >= 3/8 for odd e;
(c) if e < t_0 is odd, then H_e <= q^{d_e/2};
(d) if e < t_0 is even, then H_e <= q^{d_e} exp(4 q^{1 - s e/n}).
Moreover, for any finite list of even integers e_j < t_0 with sum_j e_j <= n,
(e) sum_j q^{1 - s e_j/n} <= C_1 sqrt(n).
Proof. (a) Split the sum defining H_e at the nearest integer to lambda e.
The central summand contributes q^{d_e}. Every other summand has gap at
least min(1 - d_e, 1/2) from lambda e, so the sum over the remaining terms
is at most 2 q^{1 - d_e}/(1 - q) <= 4 q^{1 - d_e}, using q <= 1/2. Adding
the central summand gives (a).
(b) Write lambda e = e/2 - s e/(2n). For 0 <= e < t_0,
0 <= s e/(2n) <= s t_0/(2n) = 1/8. If e is even, lambda e is between
e/2 - 1/8 and e/2, so the nearest integer is e/2, at distance s e/(2n).
If e is odd, lambda e is (e - 1)/2 + (1/2 - s e/(2n)), and since
3/8 < 1/2 - s e/(2n) < 1/2 the nearest integer is (e - 1)/2, at distance
1/2 - s e/(2n). Both distances are at least s e/(2n), and the second is
at least 3/8.
(c) For odd e < t_0, (a) and (b) give H_e <= 5 q^{d_e}. By (h),
q^{-d_e/2} >= n^{d_e/5} >= n^{3/40} >= 5 for n large, so
5 q^{d_e} <= q^{d_e/2}, and (c) follows.
(d) For even e < t_0, (a) and (b) give
H_e <= q^{d_e}(1 + 4 q^{1 - 2 d_e}). Using 2 d_e = s e/n and
1 + x <= exp(x) for x >= 0,
H_e <= q^{d_e}(1 + 4 q^{1 - s e/n}) <= q^{d_e} exp(4 q^{1 - s e/n}).
(e) Define f(z) = q^{1 - s z/n}/z for real z in [2, t_0]. Its logarithm
is convex, since (log f)''(z) = 1/z^2 > 0. Thus f is at most
max(f(2), f(t_0)) on [2, t_0]. Compute
f(2) = (1/2) q^{1 - 2 s/n} = (1/2) n^(-1/2) exp(O(s log n/n + 1/a))
= O(n^(-1/2)),
f(t_0) = (1/t_0) q^{1 - s t_0/n} = (4 s/n) q^{3/4} = O(n^(-7/8)),
using s t_0/n = 1/4 and q <= 2 n^(-1/2). Thus f(z) = O(n^(-1/2))
uniformly on [2, t_0]. For every even e_j < t_0,
q^{1 - s e_j/n} = e_j f(e_j) <= C_0 e_j / sqrt(n) for an absolute C_0,
and summing over j gives sum_j q^{1 - s e_j/n} <= (C_0/sqrt(n)) sum_j e_j
<= C_0 sqrt(n), since sum_j e_j <= n. Absorb C_0 into C_1.
The circuit bound is now proved. Let K be a field, and let g in K[V, U]
be homogeneous of degree n computed by a syntactically homogeneous
five-layer circuit of size S over K. With the parameters fixed, there is
an absolute constant C such that
R(g) <= 2 S^2 Dim exp(C sqrt(n)) n^(-sqrt(n)/100).
Proof. If g = 0 the conclusion is immediate. Otherwise the 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.
At the bottom sum layer, each gate computes either a scalar (all constant
leaves) or a homogeneous linear form (all variable leaves); this uses the
syntactic homogeneity of the bottom sum, which forces all leaf inputs at a
bottom sum to share the same formal degree. At a lower product gate of
formal degree e > 0, the product is a scalar times a product of exactly e
homogeneous linear-form occurrences. Degree-zero factors are absorbed into
the scalar. A zero factor makes the whole product zero and can be
discarded.
At a middle sum layer or the output, repeated wires from the same
predecessor gate are combined into one scalar multiple by adding the
coefficients; there are at most S distinct predecessors. Thus g is a sum
of at most S scalar multiples of products
G = prod_{j=1}^r Q_j, deg Q_j = e_j >= 1, sum_j e_j = n,
where 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 dropped, and scalar
factors have been absorbed into the lead coefficients.
By subadditivity, R(g) <= sum over the at most S terms of |c| R(G), and
|c| can be absorbed (R(c g) = R(g) for c != 0, and R(0) = 0). So
R(g) <= S max R(G) over the at most S terms. For a single product G,
apply the product-rank lemma. The remaining task is to bound
prod_j H_{e_j} in the two possible regimes for the factor degrees e_j.
Case 1: every e_j < t_0. By (b) and the constraint sum_j e_j = n,
sum_j d_{e_j} >= sum_j s e_j/(2n) = s/2.
For odd e_j, (c) gives H_{e_j} <= q^{d_{e_j}/2}; for even e_j, (d) gives
H_{e_j} <= q^{d_{e_j}} exp(4 q^{1 - s e_j/n}). Weakening q^{d_e} to
q^{d_e/2} for even degrees (legitimate since q^{d_e/2} > q^{d_e} for
0 < q < 1) and combining:
prod_j H_{e_j}
<= q^{(1/2) sum_j d_{e_j}} exp(4 sum_{even j} q^{1 - s e_j/n})
<= q^{s/4} exp(4 C_1 sqrt(n)),
using (e) for the exponential sum. Now q <= n^(-2/5) and s >= sqrt(n)/2
give q^{s/4} <= n^{-(2/5)(sqrt(n)/2)/4} = n^{-sqrt(n)/20}. Therefore
R(G) <= 2 Dim exp(4 C_1 sqrt(n)) n^(-sqrt(n)/20). (C1)
Case 2: some e_j >= t_0. Pick one such index j_0. Use
Q_{j_0} = sum_l c_l M_l, with at most S terms, each M_l a product of
e_{j_0} homogeneous linear forms. By subadditivity,
R(G) <= sum_l |c_l| R((prod_{j != j_0} Q_j) M_l)
<= S max_l R((prod_{j != j_0} Q_j) M_l).
For each term, apply the product-rank lemma to the product
(prod_{j != j_0} Q_j) M_l, whose factors have degrees e_j (j != j_0) and
1 (the e_{j_0} linear factors). The linear factors contribute H_1^{e_{j_0}},
and by (b) and (c) with e = 1 (odd, small), d_1 = 1/2 - s/(2n) = lambda,
so H_1 <= q^{d_1/2} = q^{lambda/2}, giving H_1^{e_{j_0}} <=
q^{lambda e_{j_0}/2} <= q^{lambda t_0/2}.
For the other Q_j with j != j_0:
- if e_j >= t_0, (a) gives H_{e_j} <= 5; there are at most n/t_0 = 4s
such factors;
- if e_j < t_0 is odd, (c) gives H_{e_j} <= q^{d_{e_j}/2} <= 1;
- if e_j < t_0 is even, (d) gives H_{e_j} <= q^{d_{e_j}} exp(4 q^{1 - s e_j/n}).
Drop q^{d_{e_j}} <= 1 and sum the exponential arguments over the even
small e_j: by (e) this contributes exp(4 C_1 sqrt(n)).
Combining,
prod_j H_{e_j}
<= 5^{4s} q^{lambda t_0/2} exp(4 C_1 sqrt(n)).
Now q <= n^(-2/5), lambda >= 3/8, t_0 >= sqrt(n)/4 give
q^{lambda t_0/2} <= n^{-(2/5)(3/8)(sqrt(n)/4)/2} = n^{-3 sqrt(n)/160}.
Also 5^{4s} <= exp(4 log(5) sqrt(n)) since s <= sqrt(n). Thus
R(G) <= 2 S Dim exp((4 C_1 + 4 log 5) sqrt(n)) n^{-3 sqrt(n)/160}. (C2)
Combining cases. Both (C1) and (C2) are at most
2 S Dim exp(C sqrt(n)) n^{-sqrt(n)/100} for an absolute C, because
sqrt(n)/20 >= sqrt(n)/100 and 3 sqrt(n)/160 >= sqrt(n)/100 for n large.
So
R(G) <= 2 S Dim exp(C sqrt(n)) n^(-sqrt(n)/100).
Summing over the at most S terms G in the expansion of g,
R(g) <= S * (2 S Dim exp(C sqrt(n)) n^(-sqrt(n)/100))
= 2 S^2 Dim exp(C sqrt(n)) n^(-sqrt(n)/100),
which is the proposition.
The bound on the rank of IMM_{n,n} is now set up. Fix f = IMM_{n,n} and
let L = n - 1 (number of paths in the product). Partition the n matrix
layers into k V-layers and m U-layers using the balanced schedule
V U^{l_1} V U^{l_2} ... V U^{l_k}
where l_i = 1 + floor(i s/k) - floor((i - 1) s/k). Since 0 < s/k < 1 for
n large, each l_i is 1 or 2, and sum_i l_i = k + s = m. The schedule
starts with V, ends with U, and contains no two adjacent V-layers.
Every homogeneous polynomial space H_E(t) receives the Bargmann-Fock inner
product in which z^M/sqrt(M!) is an orthonormal basis, M! = prod_i M_i!
and |M| = t; this is the finite-degree part of the analytic Fock
normalization, due to Bargmann. In these bases, multiplication by z_i sends
z^M/sqrt(M!) to sqrt(M_i + 1) z^{M + e_i}/sqrt((M + e_i)!), and the
formal differentiation partial/partial z_i sends to sqrt(M_i)
z^{M - e_i}/sqrt((M - e_i)!). The coefficients are nonnegative real
square roots of formal values.
https://www.ncbi.nlm.nih.gov/pmc/articles/PMC220595/
Let T = tr(F_f^* F_f), T_2 = tr((F_f^* F_f)^2). A Cauchy-Schwarz
inequality on the nonzero eigenvalues of F_f^* F_f gives
R(f) >= T^2/T_2, provided T > 0. (Barg)
Each path P determines the shift
eps_P = - sum_{t in V} e_{E_t(P)} + sum_{t in U} e_{E_t(P)},
where e_{E_t(P)} is the unit vector in the coordinate x^{(t)}_{p_{t-1},
p_t}. The sign is -1 on V-layers (a derivative) and +1 on U-layers (a
multiplication). The coefficient of the shifted monomial is
c_P(M) = ( prod_{t in V} M_{E_t(P)} prod_{t in U} (M_{E_t(P)} + 1))^{1/2},
with c_P(M) understood as 0 at any invalid index. Distinct paths give
distinct shifts: a path determines its full coordinate sequence, hence a
distinct unit-vector pattern in eps_P.
Averaging over uniform M in the source space, and using the F_f matrix
entries (F_f)_{M + eps_P, M} = c_P(M),
T = Dim * E_M[ sum_P c_P(M)^2 ]. (T)
Set A = a/v and B = b/u. Replacing M by independent geometric
occupations of means A on V and B on U, each V-layer contributes
E[M_e] = A, each U-layer contributes E[M_e + 1] = B + 1, and
E_Z[c_P(Z)^2] = A^k (1 + B)^m = mu. (mu)
Applying the occupation-moments lemma to the polynomial
M -> c_P(M)^2, which is an order-at-most-(2n) combination of
falling-factorials, gives the comparison between E_M and E_Z with a
logarithmic loss of O(n^2/a + n^2/v + n^2/b + n^2/u) = O(n^{-1/2}).
Hence
E_M[c_P(M)^2] >= exp(-O(n^{-1/2})) mu,
and substituting in (T),
T >= Dim * n^L * mu * exp(-O(n^{-1/2})). (TL)
Since the right side is positive, the trace inequality (Barg) applies.
Occupation-moments lemma. Let M = (M_1, ..., M_r) be uniform among the
weak compositions of t >= 0 into r >= 1 parts.
(i) For integers d_i >= 0 and H = sum_i d_i,
E[prod_i (M_i)_{d_i}] = (t)_H / r^{overline H} * prod_i d_i!,
with the convention (x)_d = x(x-1)...(x-d+1) and
r^{overline H} = r(r+1)...(r+H-1). The right side is 0 when H > t.
(ii) Let Z_1, ..., Z_r be independent geometric variables with mean
G = t/r. If P is a polynomial in the falling-factorial basis with
nonnegative coefficients, then E[P(M)] <= E[P(Z)].
(iii) If in addition all terms of the expansion have total order at most
H_0 <= t/2, then
E[P(M)] >= exp(-H_0^2/t - H_0^2/(2r)) E[P(Z)].
Proof. (i) The generating function identity sum_{j >= 0} (j)_d y^j =
d! y^d / (1 - y)^{d+1} gives
sum_{M >= 0} (prod_i (M_i)_{d_i}) y^{|M|}
= (prod_i d_i!) y^H / (1 - y)^{H + r}.
The coefficient of y^t is (prod_i d_i!) C(t + r - 1, t - H). Dividing by
the number C(t + r - 1, t) of weak compositions of t into r parts gives
(prod_i d_i!) C(t + r - 1, t - H) / C(t + r - 1, t)
= (prod_i d_i!) (t)_H / r^{overline H}.
For t < H this is 0.
(ii) Geometric factorial moment: E[(Z_i)_d] = d! G^d with G = t/r. By (i),
the ratio of the composition moment to the geometric moment is
(t)_H / r^{overline H} * (r/t)^H
= prod_{j=0}^{H-1} (1 - j/t) / (1 + j/r).
Each factor is at most 1 since 0 <= j < t (else numerator nonpositive).
Termwise summing over the nonnegative expansion of P gives (ii).
(iii) Use log(1 - x) >= -2x on 0 <= x <= 1/2 and log(1 + x) <= x on x >= 0.
The logarithm of the ratio is
sum_j log(1 - j/t) - sum_j log(1 + j/r)
>= - (2/t) sum_j j - (1/r) sum_j j
= - (H-1)H/t - (H-1)H/(2r)
>= - H^2/t - H^2/(2r).
Since H <= H_0, the exponent is at least -H_0^2/t - H_0^2/(2r). Composing
with the termwise comparison (ii) gives (iii).
Applying (iii) with H_0 = 2n gives the combined loss
O(n^2/a + n^2/v + n^2/b + n^2/u) = O(n^{-1/2}) used.
The second trace is now expanded. With (F_f)_{N, M} = c_P(M) at
N = M + eps_P and zero otherwise, the entry of F_f^* F_f indexed by M, M''
is sum_{P, Q : M + eps_P = M'' + eps_Q} c_P(M) c_Q(M''). Squaring and
summing gives
T_2 = sum over (M, P, Q, R, S) with eps_P - eps_Q = eps_R - eps_S
of c_P(M) c_Q(M') c_R(M) c_S(M'),
where M' = M + eps_P - eps_Q = M + eps_R - eps_S is determined by
(M, P, Q) (equivalently by (M, R, S)). Averaging over uniform M,
T_2 = Dim * E_M[ sum over compatible quadruples (P, Q, R, S) of
c_P(M) c_Q(M') c_R(M) c_S(M') ].
The compatibility condition eps_P - eps_Q = eps_R - eps_S factors per
layer, because V-layers and U-layers use disjoint variable classes. At
each layer t, either the two pairings agree (N-type: E_t(P) = E_t(Q) and
E_t(R) = E_t(S)) or cross (D-type: E_t(P) = E_t(R) and E_t(Q) = E_t(S)).
The all-equal case belongs to N-type.
Local weight table. Under independent geometric occupations of means A on
V and B on U, and writing u, w for the two distinct coordinates used at
layer t, the normalized per-layer weights are:
type N, group V: 1 if u != w, 1 + alpha^{-1} if u = w;
type N, group U: 1 if u != w, 1 + beta if u = w;
type D, group V: alpha^{-1};
type D, group U: beta.
The normalizations are A^2 on V and (B+1)^2 on U, so that E[M_u M_w]/A^2
= 1 (V, u != w), E[M_u^2]/A^2 = 1 + 1/A = alpha^{-1} (V, u = w),
E[(M_u+1)(M_w+1)]/(B+1)^2 = 1 (U, u != w),
E[(M_u+1)^2]/(B+1)^2 = 1 + B/(B+1) = 1 + beta (U, u = w), and similarly
E[M_u(M_w+1)]/A^2 = alpha^{-1}, E[(M_u+1)M_w]/(B+1)^2 = beta. The product
of normalizations over all layers is mu^2.
Relaxation. Enlarge the compatible quadruples by dropping i != j at all
D-layer positions (that is, admit u = w at D layers too). Original
quadruples retain their weights, and newly admitted quadruples receive
the nonnegative weights alpha^{-1} and beta. So the enlarged sum gives an
upper bound.
For a fixed type word tau in {N, D}^n, the relaxed compatibilities force
the internal vertex labels v_1, ..., v_{n-1} to fall into pairs according
to whether adjacent layers agree or differ. If w(tau) = #{t in [1, n-1] :
tau_t != tau_{t+1}} is the number of switches, then the number of
compatible quadruples is
n^{2L - w(tau)},
since each internal vertex contributes two free labels n^2 when its two
incident layers share a type, and one free label n when they differ.
For each N-layer t in group V, let h_t be the number of internal vertices
of layer t that lie between two N-layers. At such a vertex the {P, Q}
label and the {R, S} label are independent and uniform in [n], so their
equality has probability 1/n. The N|V weight 1 + alpha^{-1} 1_{u=w} thus
averages to 1 + alpha^{-1} n^{-h_t}. For each N-layer in group U the
weight is bounded pointwise by 1 + beta, without an independence
argument.
Every D-layer in V contributes a factor alpha^{-1}, and every D-layer in
U a factor beta. Combining,
T_2 <= Dim * n^{2L} * mu^2 * (1 + beta)^m * Z, (T2)
where Z = sum over tau of W(tau), and
W(tau) = n^{-w(tau)} alpha^{-d_V(tau)} beta^{-d_U(tau)}
prod_{t in N_V(tau)} (1 + alpha^{-1} n^{-h_t}),
with d_V(tau) and d_U(tau) the D-counts in groups V and U. The extra
(1 + beta)^m accounts for the m U-layers of type N, each contributing at
most 1 + beta beyond its base normalization.
Isolated-position reduction. Call a position t isolated if it is an
interior V-layer of type N with both neighbors of type D. Replace every
isolated position of tau by type D, obtaining F(tau). Since no two
V-layers are adjacent, F(tau) has no isolated position, and the values
h_t at its surviving N_V positions are unchanged.
For an isolated position t, comparing weights at position t in tau and in
F(tau): tau contributes a factor (1 + alpha^{-1}) (at h_t = 0, since both
endpoints of t are switch vertices), two switches contributing n^{-2};
F(tau) contributes a factor alpha^{-1} (a D|V weight) and no switches.
Hence
W(tau) / W(F(tau)) = (1 + alpha) / n^2.
For a word y with no isolated position, the preimages under F are
obtained by flipping an arbitrary subset of its D-isolated positions
(interior V positions of type D with both neighbors type D) to type N.
Let E(y) be that subset. Then
sum_{tau : F(tau) = y} W(tau)
= W(y) * sum_{S subset of E(y)} ((1+alpha)/n^2)^{|S|}
= W(y) * (1 + (1+alpha)/n^2)^{|E(y)|}
<= W(y) * (1 + 2/n^2)^{|E(y)|}
<= W(y) * (1 + 2/n^2)^k,
using 0 < alpha < 1 and |E(y)| <= k. Therefore
sum_tau W(tau) <= (1 + 2/n^2)^k * Z_0, (ISO)
where Z_0 = sum over words y with no isolated positions of W(y).
The word sum is now bounded. First bound the prefactor in (ISO):
(1 + 2/n^2)^k (1 + alpha^{-1}) (1 + alpha^{-1}/n)^k. Using k <= n,
alpha^{-1} <= sqrt(n), and 0 < alpha < 1,
log(prefactor)
<= 2k/n^2 + log(1 + sqrt(n)) + k alpha^{-1}/n
<= 2/n + log(1 + sqrt(n)) + 1/sqrt(n)
= O(sqrt(n)).
So the prefactor is at most exp(C_0 sqrt(n)) for an absolute C_0. Define
Z = sum over tau of n^{-w(tau)} alpha^{-d_V(tau)} beta^{-d_U(tau)}. Then
sum_tau W(tau) <= exp(C_0 sqrt(n)) * Z.
Bound Z. Split into three classes.
Pure N (tau = all N). Then w = 0, d_V = d_U = 0, contribution 1.
Pure D (tau = all D). Then w = 0, d_V = k, d_U = m, and the contribution
is alpha^{-k} beta^m. Using beta <= alpha^rho exp(C/b),
alpha^{-k} beta^m <= alpha^{-k + rho m} exp(C m/b)
= exp(C m/b) = exp(O(n^{-3/2})).
Mixed (both types represented). Decompose tau into maximal D-runs. Let r
be the number of interior D-runs (touching neither endpoint) and e the
number of endpoint D-runs (e in {0, 1, 2} for mixed words). Each interior
run has two switches, each endpoint run contributes one switch, and no
other positions contribute switches, so w(tau) = 2r + e.
Interval discrepancy. For a D-run I consisting of consecutive positions
in the balanced schedule, let
d(I) = #V(I) - rho #U(I).
The balanced schedule has k V-layers, m U-layers, and l_i in {1, 2} for
each chunk V U^{l_i}, giving tightly bounded discrepancies. Specifically,
for every contiguous interval of positions,
d(I) <= 1 + rho (disc)
(the extremal case is a single V position, or a single V U V U ... run
that begins and ends on V). The corresponding per-interval contribution
satisfies, using beta <= alpha^rho exp(C/b),
alpha^{-#V(I)} beta^{#U(I)}
<= alpha^{-(#V(I) - rho #U(I))} exp(C #U(I) / b)
= alpha^{-d(I)} exp(C #U(I) / b)
<= alpha^{-(1 + rho)} exp(C #U(I) / b). (local)
Since alpha <= 1/sqrt(n), alpha^{-(1+rho)} <= C'' n for some absolute C''.
Also exp(C#U(I)/b) <= exp(Cn/b) = exp(O(n^{-3/2})). Summing over the r + e
D-runs of tau,
prod over D-runs I of (alpha^{-#V(I)} beta^{#U(I)})
<= (C'' n)^{r + e} exp(O(n^{-3/2})).
So the weight of a mixed word is at most
B(tau) := (C'' n)^{r + e} * n^{-(2r + e)} * exp(O(n^{-3/2}))
= C''^{r + e} * n^{-r} * exp(O(n^{-3/2})).
For each fixed pair (r, e), the number of words with that pattern is at
most 2 C(n - 1, 2r + e), since the word is determined by its initial type
2 choices plus the choice of the 2r + e switch positions among n - 1
gaps. Bounding C(n - 1, 2r + e) by (n - 1)^{2r + e}/(2r + e)! and
summing,
sum over mixed tau of B(tau)
<= 2 exp(O(n^{-3/2}))
* sum_{e=0,1,2} sum_{r >= 0} C(n-1, 2r+e) C''^{r+e} n^{-r}
<= 2 exp(O(n^{-3/2}))
* sum_{e=0,1,2} C''^e (n-1)^e
* sum_{r >= 0} [C''(n-1)^2/n]^r / (2r + e)!.
Put X = C''(n-1)^2/n = Theta(n). Summing in r, the innermost sum is at
most cosh(sqrt(X)) <= exp(sqrt(X)) = exp(O(sqrt(n))). The outer factors
are polynomial in n. Hence
sum over mixed tau of B(tau) = exp(O(sqrt(n))).
Combining the three classes,
Z <= 1 + exp(O(n^{-3/2})) + exp(O(sqrt(n))) = exp(C_Z sqrt(n))
for an absolute C_Z. Therefore
sum_tau W(tau) <= exp((C_0 + C_Z) sqrt(n)). (WS)
The T_2 bound follows. From (T2) and (WS), and using the parameter
estimate (1 + beta)^m <= exp(beta m) <= exp(2 sqrt(n)) since
beta <= 2/sqrt(n) and m <= n,
T_2 <= Dim * n^{2L} * mu^2 * exp(C_T sqrt(n))
for an absolute C_T.
Completion of the large-rank bound. Combine (TL) and the T_2 bound using
the trace inequality (Barg):
R(f) >= T^2 / T_2
>= (Dim n^L mu exp(-O(n^{-1/2})))^2
/ (Dim n^{2L} mu^2 exp(C_T sqrt(n)))
= Dim * exp(-O(n^{-1/2}) - C_T sqrt(n))
= Dim * exp(-C_I sqrt(n))
for an absolute C_I. This closes the large-rank direction: IMM_{n,n} has
rank dimension Dim up to exp(-C_I sqrt(n)).
The two rank bounds now combine into the main lower bound. Let g be the
polynomial computed by a syntactically homogeneous five-layer circuit over
C of size S. If g = IMM_{n,n}, then R(g) = R(IMM_{n,n}), so the circuit
bound and the large-rank bound apply to the same quantity:
Dim * exp(-C_I sqrt(n))
<= R(IMM_{n,n})
<= 2 S^2 Dim exp(C sqrt(n)) n^{-sqrt(n)/100}.
Divide both sides by Dim > 0 and take square roots:
S >= 2^{-1/2} exp(-(C + C_I) sqrt(n) / 2) n^{sqrt(n)/200}.
The exponential factor and the 2^{-1/2} are absorbed by an extra power
n^{sqrt(n)/400} for all sufficiently large n, using that
sqrt(n)/200 - sqrt(n)/400 = sqrt(n)/400 grows like sqrt(n), whereas
(C + C_I) sqrt(n) / 2 grows like sqrt(n) but with no log factor. Hence
S >= n^{sqrt(n)/400}.
Since a five-layer circuit has gate types +, x, +, x, +, it is a
syntactically homogeneous depth-five circuit in the sense of the opening.
This establishes the main lower bound over C.
Characteristic-zero extension. The argument uses the Bargmann-Fock
inner product over C in the large-rank direction. Consider the linear map
F_f as a matrix in the ordinary monomial bases of source and target.
Because f = IMM_{n,n} is a sum of distinct monomials with coefficient 1,
every partial derivative of f has integer coefficients, and multiplication
by a variable has integer coefficients. So the entries of F_f in monomial
bases lie in Z.
For an integer matrix, the rank is the largest r such that some r-by-r
minor is nonzero. The natural map Z -> K is injective for every field of
characteristic zero. So a minor is zero in K if and only if it is zero in
Z if and only if it is zero in C. Consequently
rank_K(F_f) = rank_C(F_f) >= Dim * exp(-C_I sqrt(n))
for every field K of characteristic zero, using the large-rank bound over
C for the last inequality.
Small-rank direction over K. The circuit bound
was proved for an arbitrary field K. It uses only: (a) the syntactic
homogeneity of the circuit, which makes sense over any field; (b) the
decomposition of the circuit into upper products of middle sums, which is
algebraic; (c) the product-rank lemma, which is a statement about ranks of
linear maps over an arbitrary field; and (d) rank subadditivity. So its
conclusion holds verbatim over any field:
R(g) <= 2 S^2 Dim exp(C sqrt(n)) n^{-sqrt(n)/100}
for every homogeneous g of degree n computed by a five-layer circuit over
K.
Combining the two bounds over K, the same square-root absorption gives:
every syntactically homogeneous five-layer circuit over a
characteristic-zero field K computing IMM_{n,n} has size at least
n^{sqrt(n)/400} for all sufficiently large n, where the threshold is
independent of K. This is the lower bound.
Matching upper bound. For every field K and every n >= 2, there is a
syntactically homogeneous five-layer circuit over K computing IMM_{n,n}
of size at most n^{sqrt(n) + 4}.
Set t = ceil(sqrt(n)) and r = ceil(n/t). Partition the n matrix layers
into r consecutive blocks of sizes l_1, ..., l_r, with each l_j at most t
and with sum_j l_j = n. Then r <= t.
Construction. The five computational layers, from bottom (level 5) to
top (level 1), are:
Level 5 (bottom sums): use one identity sum gate per variable x^(s)_{a,b}.
There are n^3 leaves and n^3 bottom sum gates, each shared by all uses
of that variable.
Level 4 (product gates): for each block j, each entry (a, b) of the block
product Y^{(j)} = X^(j_1)...X^(j_{l_j}), and each choice of internal
indices, add one product gate multiplying the l_j variable sum-gates
of that monomial. The number of such monomials in the block-product entry
(a, b) is n^{l_j - 1}, and there are n^2 entries. So block j contributes
n^{l_j + 1} product gates.
Level 3 (sum gates): for each block j and each entry (a, b), add one sum
gate taking all n^{l_j - 1} monomial-product gates of that entry. This
uses n^2 sum gates per block, r n^2 total.
Level 2 (product gates): for each tuple (a_1, ..., a_{r-1}) in [n]^{r-1},
add one product gate taking the r block-entry values
Y^{(1)}_{1, a_1} * Y^{(2)}_{a_1, a_2} * ... * Y^{(r)}_{a_{r-1}, 1}.
There are n^{r-1} such product gates.
Level 1 (output): a single sum gate taking all n^{r-1} level-2 gates.
Syntactic homogeneity. Bottom sum gates have formal degree 0 (identity)
or degree 1 (variables); the product gates at level 4 inherit degree l_j;
middle sum gates at level 3 have degree l_j; level-2 product gates have
formal degree l_1 + ... + l_r = n; the output sum gate has degree n. So
the circuit is syntactically homogeneous with output degree n.
Correctness. By expansion of the matrix product,
IMM_{n,n} = sum over (a_1, ..., a_{r-1}) in [n]^{r-1}
of Y^{(1)}_{1, a_1} Y^{(2)}_{a_1, a_2} ... Y^{(r)}_{a_{r-1}, 1}.
The circuit computes exactly this sum.
Size bound. The total number of gates is
2 n^3 (bottom leaves plus bottom sums)
+ r n^2 (level-3)
+ sum_j n^{l_j + 1} (level-4)
+ n^{r-1} (level-2)
+ 1 (level-1).
Using l_j <= t and r <= t, sum_j n^{l_j+1} <= t n^{t+1}. So
total <= 2 n^3 + t n^2 + t n^{t+1} + n^{t-1} + 1
<= 3 n^3 + n^{t+2} + n^{t-1} + 1
<= 3 n^{t+2} + 1
<= n^{t+3}
<= n^{sqrt(n) + 4},
using t <= sqrt(n) + 1, t >= 2 for n >= 3, and n >= 3, so that
t + 3 <= sqrt(n) + 4 and 3 n^{t+2} <= n^{t+3} for n >= 3.
Combined, the two bounds give that the gate complexity of IMM_{n,n} in
the model of syntactically homogeneous five-layer circuits over
characteristic-zero fields is between n^{sqrt(n)/400} and
n^{sqrt(n) + 4}, i.e. n^{Theta(sqrt n)}. Unrestricted circuits for
IMM_{n,n} are polynomial size; the constraint that produces the
sqrt(n) exponent is depth and syntactic homogeneity alone.
References.
M. Agrawal, V. Vinay. Arithmetic circuits: A chasm at depth four. ECCC
TR08-062, 2008.
agrawal-vinay-2008.pdf
P. Amireddy, A. Garg, N. Kayal, C. Saha, B. Thankey. Direct
approaches to homogeneous depth-four in the shifted-partials framework.
arXiv:2211.07691, 2022.
amireddy-garg-kayal-saha-thankey-2022.pdf
P. Amireddy, A. Garg, N. Kayal, C. Saha, B. Thankey. Direct
approaches to homogeneous depth-four in the shifted-partials framework.
ICALP 2023.
amireddy-garg-kayal-saha-thankey-2023.pdf
J. Armand, A. R. Behera, S. Tavenas. Lower bounds for depth-5
algebraic circuits with bounded fan-in of top product gates. ECCC
TR26-104, 2026.
armand-behera-tavenas-2026.pdf
V. Bargmann. Remarks on a Hilbert space of analytic functions.
Proceedings of the National Academy of Sciences 48 (1962), 199-204.
https://www.pnas.org/doi/10.1073/pnas.48.2.199
S. K. Bera, A. Chakrabarti. A depth-five lower bound for iterated
matrix multiplication. CCC 2015.
bera-chakrabarti-2015.pdf
C. S. Bhargav, P. Dutta, N. Saxena. Improved lower bound, and proof
barrier, for constant depth algebraic circuits. MFCS 2022.
bhargav-dutta-saxena-2022.pdf
M. A. Forbes. Low-depth algebraic circuit lower bounds over any field.
CCC 2024.
forbes-2024.pdf
H. Fournier, N. Limaye, G. Malod, S. Srinivasan. Lower bounds for
depth-4 arithmetic circuits. Computational Complexity, 2015.
fournier-limaye-malod-srinivasan-2015.pdf
A. Gupta, P. Kamath, N. Kayal, R. Saptharishi. Approaching the
chasm at depth four. ECCC TR12-098, Revision 3, 2012.
gupta-kamath-kayal-saptharishi-2014.pdf
N. Kayal. An exponential lower bound for the sum of powers of bounded
degree polynomials. ECCC TR12-081, Revision 1, 2012.
kayal-2012.pdf
N. Kayal, N. Limaye, C. Saha, S. Srinivasan. An exponential lower
bound for homogeneous depth four arithmetic formulas. FOCS 2014.
kayal-limaye-saha-srinivasan-2014.pdf
N. Kayal, C. Saha, S. Tavenas. An exponential lower bound for
homogeneous depth four arithmetic formulas. Theory of Computing
14(16), 2018, 1-24.
kayal-saha-tavenas-2018.pdf
P. Koiran. Arithmetic circuits: The chasm at depth four gets wider.
Theoretical Computer Science 448 (2012), 56-65.
koiran-2012.pdf
M. Kumar, R. Saptharishi. An exponential lower bound for homogeneous
depth-5 circuits over finite fields. CCC 2017.
kumar-saptharishi-2017.pdf
M. Kumar, S. Saraf. On the power of homogeneous depth 4 arithmetic
circuits. SIAM Journal on Computing 46(1), 2017, 336-387.
kumar-saraf-2014.pdf
N. Limaye, S. Srinivasan, S. Tavenas. Superpolynomial lower bounds
against low-depth algebraic circuits. ECCC TR21-081, 2021.
limaye-srinivasan-tavenas-2021.pdf
N. Nisan, A. Wigderson. Lower bounds on arithmetic circuits via
partial derivatives. Computational Complexity 5 (1996), 217-234.
nisan-wigderson-1995.pdf
S. Tavenas. Improved bounds for reduction to depth 4 and depth 3.
Information and Computation 240 (2015), 2-11.
tavenas-2013.pdf