================================================================
HOMOGENEOUS DEPTH-FIVE LOWER BOUNDS FOR ITERATED MATRIX
MULTIPLICATION
================================================================
A complete, self-contained proof written for a curious
high-school reader. You need some linear algebra (dimension,
rank, inner products) and some combinatorics (binomial
coefficients, geometric series). Nothing else is assumed.
Every concept used is defined here from scratch.
----------------------------------------------------------------
CONTENTS
----------------------------------------------------------------
1. The theorem
2. Setup: circuits and syntactic homogeneity
3. Strategy of the proof
4. The measure: rank of a linear map attached to a
polynomial
5. The parameters
6. Any small circuit has small rank
7. Iterated matrix multiplication has large rank
8. The main theorem
9. Lifting to every characteristic-zero field
10. A matching upper bound
11. Index of notation
================================================================
1. THE THEOREM
================================================================
For each integer n >= 1 and t in {1, 2, ..., n}, let
X^(t) = ( x^(t)_{i,j} : 1 <= i, j <= n )
be an n-by-n matrix of DISTINCT variables. The total number of
ambient variables is n^3.
The iterated matrix multiplication polynomial IMM_{n,n} is
the (1,1) entry of the product of the n matrices:
IMM_{n,n}
= ( X^(1) X^(2) ... X^(n) )_{1,1}
= sum over paths (1 = p_0, p_1, ..., p_{n-1}, p_n = 1)
with each p_1, ..., p_{n-1} in {1, ..., n}, of
x^(1)_{p_0,p_1} x^(2)_{p_1,p_2} ... x^(n)_{p_{n-1},p_n}.
There are exactly n^(n-1) index sequences ("paths"), and each
contributes one distinct monomial of degree n. So IMM_{n,n}
is a homogeneous polynomial of degree n in the n^3 ambient
variables (some of which it does not use; see Section 3).
Concrete check, n = 2. Let X^(1) = [[a,b],[c,d]] and
X^(2) = [[e,f],[g,h]]. Then (X^(1) X^(2))_{1,1} = ae + bg.
So
IMM_{2,2} = x^(1)_{1,1} x^(2)_{1,1} + x^(1)_{1,2} x^(2)_{2,1}.
Two paths, matching the formula.
MAIN LOWER BOUND.
Theorem 1. There are absolute constants c > 0 and n_0 with
the following property. Let n >= n_0 and let K be any field
of characteristic zero. Then every syntactically homogeneous
Sigma-Pi-Sigma-Pi-Sigma circuit (Section 2) over K computing
IMM_{n,n} has size at least
n^(c sqrt(n)).
One may take c = 1/400.
MATCHING UPPER BOUND.
Theorem 2 (proved in Section 10). For every field K and every
n >= 2, there is a syntactically homogeneous
Sigma-Pi-Sigma-Pi-Sigma circuit computing IMM_{n,n} with
size at most n^(sqrt(n) + 4).
Combining Theorems 1 and 2, the gate complexity of IMM_{n,n}
in the five-layer homogeneous model is n^(Theta(sqrt(n))).
The lower and upper bounds differ only in the constant
(1/400 versus 1) in front of sqrt(n).
"Size at least" refers to the total number of vertices of
the circuit, including variable leaves and constants. The
proof also separately bounds the number of computational
gates, so the lower bound is not an artefact of counting
leaves.
The model permits:
- arbitrary fan-in at every gate, in particular bottom
sum gates that read any number of variables,
- arbitrary fan-out and shared subcircuits,
- unrestricted bottom linear forms (no bound on the size
of their support).
================================================================
2. SETUP: CIRCUITS AND SYNTACTIC HOMOGENEITY
================================================================
An arithmetic circuit over a field K is a finite directed
acyclic graph with a single designated output vertex. Each
vertex is one of:
- a VARIABLE LEAF, labelled by a variable x_i,
- a CONSTANT LEAF, labelled by c in K,
- a SUM GATE, whose value is a K-linear combination of its
input values,
- a PRODUCT GATE, whose value is the product of its input
values.
Fan-in and fan-out are unrestricted. The size of the circuit
is the total number of vertices.
A gate can be used as input to another gate many times. When
a sum gate takes the same source twice, the two occurrences
are added. When a product gate takes the same source twice,
they are multiplied. A gate can also feed many other gates
(shared subcircuits).
The five-layer Sigma-Pi-Sigma-Pi-Sigma model.
Label the levels 1, 2, 3, 4, 5 from output to leaves, with
levels 1, 3, 5 sums and levels 2, 4 products. Edges join
level t and level t+1 gates only. The output is the single
gate at level 1. Level 5 (bottom) sum gates read leaves
directly. If some gate does not lie on any path from a leaf
to the output, it can be deleted without changing what the
circuit computes; we assume from now on that all gates do
feed the output.
Unary gates (one input) are allowed and do not change the
shape. Scalar coefficients on sum wires are "free": they do
not count as extra gates.
Syntactic homogeneity.
Assign every variable formal degree 1 and every constant
formal degree 0. Extend to gates as follows:
- At a product gate with inputs u_1, ..., u_r (each an
occurrence, possibly repeated), the formal degree is
deg(u_1) + deg(u_2) + ... + deg(u_r).
- At a sum gate, all input formal degrees must be equal;
that common value is the gate's formal degree.
- An empty sum computes 0, formal degree 0; an empty
product computes 1, formal degree 0.
A circuit is SYNTACTICALLY HOMOGENEOUS of degree n if such an
assignment exists and the output gate has formal degree n.
Two features of this definition are important later.
(a) The formal degree is SYNTACTIC, not semantic. A gate may
compute the zero polynomial and still carry a nonzero formal
degree. Cancellations do not "reset" the degree. This lets
us reason about "the degree of a gate" even when the actual
polynomial is zero. It is the reason the proof works
uniformly even when a circuit weasels its way to the answer
via cancellations.
(b) At the bottom layer (level 5), all leaves are variables
of degree 1 or constants of degree 0, and all leaves of one
sum gate have equal formal degree. Therefore a bottom sum
gate is either a scalar (all const leaves) or a homogeneous
linear form (all variable leaves). Combined with (a), a
lower product gate of formal degree e > 0 is a scalar
times a product of EXACTLY e homogeneous linear forms,
counted with multiplicity. This is what "exposes" the
bottom layer as a pool of linear forms.
================================================================
3. STRATEGY OF THE PROOF
================================================================
Fix n large. Split the n matrix layers into two groups: k
layers called "V-layers" and m layers called "U-layers", with
k + m = n, m - k = s of order sqrt(n).
Let V denote the variable set consisting of all n^2 variables
of the V-layers, and U the variable set of all n^2 variables
of the U-layers. Then |V| = v := k n^2 and |U| = u := m n^2.
Throughout, we treat ALL n^3 ambient variables (including
those not present in IMM_{n,n}) as part of V or U. This is
essential for the lower bound to apply to circuits that might
use the unused variables to no effect, or to try to encode
something clever with them. A circuit that computes IMM_{n,n}
must compute our specific polynomial; unused variables do not
help, and the proof must survive circuits that try to use them.
STEP 1: A rank measure.
Choose two nonnegative degrees a, b. Consider the space
Source = H_V(a) tensor H_U(b)
where H_V(a) is the space of homogeneous polynomials of
degree a in the v variables of V (dimension
C(v+a-1, a) = C(v+a-1, v-1)), and similarly H_U(b). Write
Dim = dim(Source) = C(v+a-1, a) C(u+b-1, b).
For a homogeneous degree-n polynomial g in V and U
variables, let g_{[k,m]} be its component of V-degree k and
U-degree m (so U-degree m = n - k).
Define the linear map
F_g : Source -> Target := H_V(a-k) tensor H_U(b+m)
as follows. In g_{[k,m]}, replace each V-variable v by the
operators partial / partial v, and each U-variable u by
multiplication by u. Then F_g is the resulting linear
operator from Source to Target.
Let R(g) = rank(F_g).
Basic properties (proved in Section 4):
(P1) R(g_1 + g_2) <= R(g_1) + R(g_2) [subadditive]
(P2) R(c g) = R(g) for c != 0 [scaling]
(P3) R(0) = 0
(P4) "Differentiate in V" and "multiply in U" commute.
So for a product of homogeneous factors Q_1 ... Q_r,
the operator grows factor by factor. This lets us
bound R(prod Q_j) using only the degrees of each Q_j.
STEP 2: Any small circuit has small rank (Section 6).
Key result (Proposition 6.1):
For n large, any homogeneous degree-n g computed by a
syntactically homogeneous five-layer circuit of size S
satisfies
R(g) <= 2 S^2 Dim exp(C sqrt(n)) n^(-sqrt(n)/100).
The constant C is absolute.
Idea. The circuit expands into a sum of at most S "upper
products" of "lower factors". Each upper product is a product
of homogeneous Q_j of positive degrees e_j summing to n. For
such a product, a factor-by-factor analysis via (P4) bounds
R(prod Q_j) as a product of explicit quantities H_{e_j}
(defined Section 6) depending only on e_j. Summing over the
at most S additive terms contributes a factor S; expanding
one factor when required contributes another factor S; hence
S^2.
STEP 3: IMM has large rank (Section 7).
Key result (Proposition 7.1):
There is an absolute constant C such that, with a, b and
the V/U-layer order chosen deliberately, for all large n,
R(IMM_{n,n}) >= Dim exp(-C sqrt(n)).
Idea. Give every homogeneous polynomial space the standard
inner product in which the monomials z^M / sqrt(M!) are
orthonormal (this is the finite homogeneous part of the
Bargmann-Fock normalization). Then squared entries of F_f
become weighted sums over paths P in IMM's expansion. The
first moment tr(F^*F) and the second moment tr((F^*F)^2)
become weighted counts of paths and quadruples of paths.
Exact combinatorial facts about uniform compositions and
geometric variables compare these weights to simple
products. Finally the trace inequality
rank H >= (tr H)^2 / tr(H^2) (H != 0, PSD)
turns the two moments into a lower bound on rank.
STEP 4: Combine.
From Steps 2 and 3 with the SAME a, b, V, U,
Dim exp(-C sqrt(n))
<= R(f) <= 2 S^2 Dim exp(C sqrt(n)) n^(-sqrt(n)/100).
Divide by Dim exp(C sqrt(n)) and take square roots:
S^2 >= (1/2) exp(-2 C sqrt(n)) n^(sqrt(n)/100),
hence S >= n^(sqrt(n)/400) for sufficiently large n. The
remaining sections fill in the details.
================================================================
4. THE MEASURE: RANK OF A LINEAR MAP ATTACHED TO A POLYNOMIAL
================================================================
Let V, U be disjoint variable sets with |V| = v and |U| = u.
For a variable set E and an integer t >= 0, let H_E(t) be the
space of homogeneous polynomials of degree t in the variables
of E; its dimension is
h(|E|, t) = C(|E| + t - 1, t).
If E is empty and t = 0, take H_empty(0) = K (constants).
For a polynomial Q in K[V, U], define the endomorphism
T_Q = Q(partial_V, U) : K[V, U] -> K[V, U]
of the whole polynomial ring: replace each V-variable v by
the formal partial derivative operator d/dv, and each
U-variable u by the multiplication operator "multiply by u".
Fact 4.1 (commutativity). For polynomials Q_1, Q_2 in K[V, U],
T_{Q_1} T_{Q_2} = T_{Q_2} T_{Q_1} = T_{Q_1 Q_2}.
Proof. V-variables become partial derivatives, which commute
among themselves. U-variables become multiplications, which
commute among themselves. Every partial derivative commutes
with every multiplication (V and U are disjoint). Substituting
into Q_1 Q_2 is bilinear in (Q_1, Q_2), so the identity holds.
Each T_Q is a graded operator of the polynomial ring: it maps
H_V(p) H_U(q) into H_V(p - deg_V(Q)) H_U(q + deg_U(Q)), where
deg_V(Q) is the V-degree and deg_U(Q) the U-degree.
Bidegree projection. Write g_{[k,m]} for the component of a
polynomial g having V-degree k and U-degree m. Projection is
linear:
(g_1 + g_2)_{[k,m]} = (g_1)_{[k,m]} + (g_2)_{[k,m]},
(cg)_{[k,m]} = c g_{[k,m]}.
Fix nonnegative integers k, m, a with a >= k. Define
F_g := (g_{[k,m]})(partial_V, U) : H_V(a) H_U(b)
-> H_V(a - k) H_U(b + m).
This is a K-linear operator between finite-dimensional vector
spaces, determined by g (which must be homogeneous of degree
k + m, so that g_{[k,m]} is well defined as a homogeneous
polynomial). Let R(g) := rank(F_g).
Note: F_g depends on the FIXED parameters k, m, a, b, v, u
along with g. They will be chosen in Section 5 to depend only
on n, and will never depend on g or on the circuit.
Basic properties of R.
(i) (subadditivity) R(g_1 + g_2) <= R(g_1) + R(g_2).
(ii) (scaling) R(c g) = R(g) for c != 0.
(iii)(trivial) R(0) = 0.
Proof. (i) F_{g_1+g_2} = F_{g_1} + F_{g_2}, and rank of a sum
of matrices is at most the sum of their ranks. (ii) F_{c g} =
c F_g, and multiplying by a nonzero scalar preserves rank.
(iii) F_0 = 0, rank 0.
The measure is NOT multiplicative. The projection g -> g_{[k,m]}
does not respect multiplication: (g_1 g_2)_{[k,m]} is a sum of
products (g_1)_{[i, *]} (g_2)_{[k-i, *]} over i, and is not
generally equal to (g_1)_{[k,m]} (g_2)_{[k,m]}. However, the
UNDERLYING operators T_Q DO commute (Fact 4.1). This lets us
handle a product's bidegree decomposition factor by factor.
Bidegree decomposition of a product. Let Q_1, ..., Q_r be
homogeneous of positive degrees e_1, ..., e_r with sum e_j = n.
For each monomial in the product Q_1 Q_2 ... Q_r, the V-degree
of its part in Q_j is some i_j in [0, e_j], and sum i_j = k if
the product's V-degree is k. The U-degree of Q_j's part is
e_j - i_j, and sum (e_j - i_j) = n - k = m. So
(Q_1 Q_2 ... Q_r)_{[k,m]}
= sum over (i_1, ..., i_r), each i_j in [0, e_j],
sum_j i_j = k, of
prod_{j=1}^r (Q_j)_{[i_j, e_j - i_j]}.
Factorizing one assignment. Fix one such (i_1, ..., i_r). The
corresponding operator on H_V(a) H_U(b) factors as a product
T_{(Q_1)_{[i_1, e_1 - i_1]}} T_{(Q_2)_{[i_2, e_2 - i_2]}} ...
T_{(Q_r)_{[i_r, e_r - i_r]}}
by Fact 4.1 (order does not matter). Each factor is a
homogeneous-bidegree linear operator on the polynomial ring.
Applying them one after another, we pass through an
intermediate homogeneous space whose dimension bounds the
rank of this contribution.
Choosing an application order. Set lambda := k/n and
delta_j := i_j - lambda e_j.
Because sum_j i_j = k = lambda n, we have sum_j delta_j = 0.
We apply the factors with delta_j > 0 FIRST. Let
I := sum_{delta_j > 0} i_j,
J := sum_{delta_j > 0} (e_j - i_j).
The intermediate space after applying all delta_j > 0 factors is
H_V(a - I) H_U(b + J).
This is well-defined: I <= sum_j i_j = k <= a, and
J <= sum_j (e_j - i_j) = m. Its dimension bounds the rank of
the fixed-assignment contribution.
Dimension ratios. For integers 0 <= I <= a and 0 <= J:
h(v, a - I) / h(v, a)
= prod_{t=0}^{I-1} (a - t)/(a + v - 1 - t)
<= ( a / (a + v - 1) )^I [x -> x/(x+v-1) increasing]
h(u, b + J) / h(u, b)
= prod_{t=1}^{J} (b + u + t - 1)/(b + t)
<= ( (b + u)/b )^J = beta^{-J} [beta = b/(b+u)]
Put alpha := a/(a+v) and rho := k/m, so beta >= alpha^rho
(verified in Lemma 5.1). Then
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 2 comes from (1 - 1/(a+v))^{-I} <= 2 when I <= n and
a+v = Omega(n^2) (true for large n); this 2 is the "2" in the
product rank lemma.
Discrepancy identity. Using lambda = rho/(1+rho) and
sum_j delta_j = 0:
I - rho J
= sum_{delta_j > 0} i_j - rho sum_{delta_j > 0} (e_j - i_j)
= sum_{delta_j > 0} (i_j - rho e_j + rho i_j)
= (1 + rho) sum_{delta_j > 0} delta_j
= (1 + rho)/2 sum_j |delta_j|.
The last step uses sum_{delta_j > 0} delta_j =
-sum_{delta_j < 0} delta_j, so
sum_{delta_j > 0} delta_j = (1/2) sum_j |delta_j|.
Bounding one fixed assignment. Let
q := alpha^{(1 + rho)/2}.
Then
rank of the (i_1, ..., i_r) contribution
<= Dim * 2 q^{sum_j |delta_j|}
= Dim * 2 * prod_j q^{|i_j - lambda e_j|}.
Product rank lemma. Summing over all assignments (i_j) with
sum_j i_j = k, and dropping the constraint sum_j i_j = k
(every extra term is nonnegative), we get the following.
Lemma 4.2 (product rank). For homogeneous Q_1, ..., Q_r of
positive degrees e_1, ..., e_r with sum e_j = n:
R(prod_j Q_j) <= 2 Dim prod_j H_{e_j},
where
H_e := sum_{i=0}^{e} q^{|i - lambda e|}.
The sum is over all bidegree choices for a factor of degree e.
================================================================
5. THE PARAMETERS
================================================================
Now pick the parameters. Throughout this section s is the
LARGEST integer at most sqrt(n) that has the same parity as n.
The parity choice makes k and m integers.
Parameters.
k = (n - s)/2,
m = (n + s)/2, k + m = n, m - k = s.
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).
The quantity a measures the number of "differentiation steps"
applied to V-variables; the average per V-variable is A = a/v,
which is about n^{-1/2}. Similarly B = b/u is about n^{-1/2}
for U. The parameters alpha, beta are A/(1+A) and B/(1+B).
The parameters are chosen so that in the trace analysis
(Section 7) the leading-order V-shift and U-shift balance out.
Two auxiliary quantities used in Section 6:
d_e := dist(lambda e, Z), for e a positive integer.
t_0 := n / (4s).
Here dist(., Z) is the distance to the nearest integer.
Lemma 5.1 (parameter estimates). For all sufficiently large n,
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)),
and alpha^{-1} <= sqrt(n).
(g) alpha^rho <= beta <= alpha^rho exp(C/b),
and beta <= 2/sqrt(n).
(h) q = n^{-1/2} exp(O(s log n / n + 1/a)),
and n^{-1/2} <= q <= 2/sqrt(n) <= n^{-2/5}, q <= 1/2.
Here C is an absolute constant.
Proof. (a) By construction sqrt(n) - 2 < s <= sqrt(n), since
the parity adjustment costs at most 2. So s >= sqrt(n)/2 for
n >= 16.
(b) lambda = k/n = (n - s)/(2n) = 1/2 - s/(2n). With s <=
sqrt(n), lambda >= 1/2 - 1/(2 sqrt(n)) >= 3/8 for n >= 16.
Also lambda < 1/2 since s > 0. rho = k/m = (n - s)/(n + s),
strictly between 0 and 1 for 0 < s < n.
(c) v = k n^2 with k = (n - s)/2 = n/2 * (1 - s/n) = Theta(n).
So v = Theta(n^3). Same for u.
(d) Write a_0 = v/(sqrt(n) - 1). Then a_0 <= a < a_0 + 1,
and
a_0 / (a_0 + v)
= [v/(sqrt(n)-1)] / [v/(sqrt(n)-1) + v]
= 1 / sqrt(n).
So a_0 = n^{-1/2} (a_0 + v) >= n^{-1/2} * v = Theta(n^{5/2}).
Since a_0 <= a < a_0 + 1, a = Theta(n^{5/2}) too. Similarly
b_0 := u alpha^rho / (1 - alpha^rho) satisfies b_0/(b_0 + u) =
alpha^rho exactly, and b_0 = u alpha^rho / (1 - alpha^rho).
Since alpha^rho ~ n^{-1/2} and u ~ n^3/2, b_0 = Theta(n^{5/2}).
Then b_0 <= b < b_0 + 1 gives b = Theta(n^{5/2}).
(e) a = Theta(n^{5/2}) and k = Theta(n), so a >= k for large
n. min(a, b) = Theta(n^{5/2}), so 2n <= min(a, b)/2 as well.
(f) Let f(x) = log(x/(x+v)). Then f'(x) = v/(x(x+v)) <= 1/x,
which is <= 1/a_0 on [a_0, a]. By the mean value theorem
applied on [a_0, a]:
0 <= f(a) - f(a_0) <= 1/a_0.
Since f(a_0) = log(1/sqrt(n)) = -(1/2) log n,
log(alpha) = log(a/(a+v)) = -(1/2) log n + epsilon, with
epsilon in [0, 1/a_0] = O(1/a). So alpha = n^{-1/2} exp(O(1/a)),
and alpha^{-1} <= sqrt(n) exp(O(1/a)) <= sqrt(n) for large n.
(g) We have 1 - rho = s/m = s/(n+s) = O(s/n). Also
log alpha = -(1/2) log n + O(1/a). So
log(alpha^rho) = rho * log alpha
= rho * (-(1/2) log n) + O(1/a)
= -(1/2) log n + (s/m)((1/2) log n) + O(1/a)
= -(1/2) log n + O(s log n / n + 1/a).
So alpha^rho = n^{-1/2} exp(O(s log n / n + 1/a)) =
n^{-1/2}(1 + o(1)).
Let b_0 = u alpha^rho/(1 - alpha^rho). Then b_0 <= b < b_0 + 1
and b_0/(b_0 + u) = alpha^rho. Apply the log-derivative bound
with u in place of v on [b_0, b]:
0 <= log(beta) - log(alpha^rho) <= 1/b_0 <= C/b.
So alpha^rho <= beta <= alpha^rho exp(C/b). For large n,
alpha^rho <= 2 n^{-1/2} and exp(C/b) <= 2, so beta <= 4 n^{-1/2}.
Absorbing 4 into the constant, beta <= 2/sqrt(n) for large
enough n.
(h) Use (1 + rho)/2 = n/m = n/(n+s) = 1 - s/(n+s). Then
log q = ((1 + rho)/2) log alpha
= (n/(n+s)) (-(1/2) log n + O(1/a))
= -(1/2) log n + O(s log n / n + 1/a).
So q = n^{-1/2} exp(O(s log n / n + 1/a)).
Since (1 + rho)/2 <= 1 and alpha < 1, q = alpha^{(1+rho)/2} >=
alpha^1 = alpha. By (f), alpha >= n^{-1/2}. So q >= n^{-1/2}.
For large n, q <= 2 n^{-1/2} by the formula. And 2 n^{-1/2} <=
n^{-2/5} for n >= 1024 (since -1/2 < -2/5). Also 2 n^{-1/2}
<= 1/2 for n >= 16.
================================================================
6. ANY SMALL CIRCUIT HAS SMALL RANK
================================================================
Fix n large and choose V-layers, U-layers, k, m, v, u, a, b,
and Dim exactly as in Section 5. All subsequent constants are
absolute, independent of n (for n large), of the field K, of
the specific circuit, and of the split into V-layers and
U-layers.
Proposition 6.1 (main circuit bound). Let g in K[V, U] be a
homogeneous polynomial of degree n computed by a
syntactically homogeneous Sigma-Pi-Sigma-Pi-Sigma circuit of
size S. Then
R(g) <= 2 S^2 Dim exp(C sqrt(n)) n^(-sqrt(n)/100)
for an absolute constant C.
This section proves Proposition 6.1.
6.1 Expansion of a circuit into a sum of products
Let us name the circuit levels from bottom to top: level 5
(bottom) are sum gates reading leaves; level 4 are product
gates; level 3 are sum gates; level 2 are product gates; and
level 1 (output) is a single sum gate.
By Section 2(b), every level-4 gate value is a scalar times
a product of EXACTLY e homogeneous linear forms, where e is
its positive formal degree.
A level-3 gate is a scalar-weighted sum of level-4 gates
feeding it; combining repeated wires, we can write it as a
sum of at most S scalar multiples of products of e_j
homogeneous linear forms, where e_j is the level-3 gate's
formal degree. So a level-3 gate value Q_j is a sum of at
most S products of e_j linear forms.
A level-2 gate takes, as input, r distinct level-3 gates
(with repetition allowed, combining scalar coefficients). Its
value G = prod_{j=1}^{r} Q_j, homogeneous of degree
sum_j e_j. Since G feeds the output sum gate with a nonzero
coefficient, and the output's formal degree is n, we must
have sum_j e_j = n.
Summing over the at most S distinct level-2 predecessors of
the output gate, we get
g = sum_{k=1}^{K} c_k G_k, K <= S, c_k != 0,
where each G_k = prod_{j=1}^{r_k} Q_{k, j} is a product of
homogeneous polynomials Q_{k, j} of positive degrees
e_{k, j} with sum_j e_{k, j} = n, and each Q_{k, j} is a
sum of at most S scalar multiples of products of e_{k, j}
homogeneous linear forms.
We can drop any G_k that equals 0 (by subadditivity, its R
contribution is 0). So assume all G_k != 0.
The rest of the proof bounds R(G) for a generic product G of
this shape, then sums.
6.2 Degree estimates
Recall H_e = sum_{i=0}^e q^{|i - lambda e|},
d_e = dist(lambda e, Z), and t_0 = n/(4s).
Lemma 6.2 (degree estimates). For all sufficiently large n,
the following hold for every integer e >= 1:
(6.1) H_e <= q^{d_e}(1 + 4 q^{1-2d_e}) <= 5.
For 1 <= e < t_0:
(6.2) d_e = se/(2n) if e even,
d_e = 1/2 - se/(2n) if e odd;
in either case d_e >= se/(2n).
Furthermore for 1 <= e < t_0:
(6.3) H_e <= q^{d_e/2} (e odd),
(6.4) H_e <= q^{d_e} exp(4 q^{1-se/n}) (e even).
There is an absolute constant C_1 such that, for any finite
list of positive integers e_1, ..., e_r with sum_j e_j <= n,
(6.5) sum_{j: e_j < t_0, e_j even} q^{1 - s e_j/n} <= C_1 sqrt(n).
Proof. (6.1) Enlarge the sum defining H_e to all integers i in
Z; the extra terms are nonnegative. Designate one nearest
integer i_0 of lambda e; if two are equally near, pick one.
For every other integer i, |i - lambda e| >= 1 - d_e. Grouping
terms by distance:
sum_{i != i_0} q^{|i - lambda e|}
<= 2 (q^{1-d_e} + q^{2-d_e} + ...)
= 2 q^{1-d_e}/(1 - q).
So H_e <= q^{d_e} + 2 q^{1-d_e}/(1-q), which, since q <= 1/2
implies 1/(1-q) <= 2, gives q^{d_e}(1 + 4 q^{1-2d_e}). Finally,
q < 1 and 0 <= d_e <= 1/2, so q^{1-2d_e} <= 1, giving
q^{d_e}(1 + 4q^{1-2d_e}) <= 5.
(6.2) Write lambda e = e/2 - se/(2n). For 1 <= e < t_0 =
n/(4s), we have 0 < se/(2n) < 1/8. If e is even, e/2 is an
integer and the nearest integer to lambda e is e/2, so
d_e = se/(2n). If e is odd, e/2 is a half-integer and the
nearest integer is (e-1)/2 or (e+1)/2, so d_e = 1/2 - se/(2n),
which is >= 3/8. In both cases d_e >= se/(2n): for even e
trivially, for odd e because se/(2n) < 1/8 < 3/8 <= d_e.
(6.3) Odd e < t_0: d_e >= 3/8. From (6.1), H_e <= 5 q^{d_e}.
We want to replace the constant 5 by the extra power of q
in q^{d_e/2}, i.e., to show q^{d_e/2} <= 1/5. Since
d_e/2 >= 3/16 and q <= 2 n^{-1/2},
q^{d_e/2} <= (2 n^{-1/2})^{3/16} = 2^{3/16} n^{-3/32}
which is <= 1/5 for n large enough. So H_e <= q^{d_e/2}.
(6.4) Even e < t_0: from (6.1), H_e <= q^{d_e}(1 + 4 q^{1-2d_e}).
Substitute 2d_e = se/n and use 1 + x <= exp(x):
1 + 4 q^{1-se/n} <= exp(4 q^{1-se/n}),
so H_e <= q^{d_e} exp(4 q^{1-se/n}).
(6.5) Fix a list of even integers e_j < t_0 with sum_j e_j <= n.
Consider f(z) = q^{1 - sz/n}/z on the interval [2, t_0].
Since (log f)''(z) = 1/z^2 > 0, log f is convex, so f(z) is
maximized at an endpoint of the interval. We compute
f(2) = (1/2) q^{1 - 2s/n}
= (1/2) n^{-1/2} exp(O(s log n/n + 1/a)) = O(n^{-1/2}),
using q's formula from Lemma 5.1(h) with s/n -> 0. At the
other endpoint, t_0 = n/(4s), so s t_0/n = 1/4, and
f(t_0) = (4s/n) q^{3/4}
<= (4 sqrt(n)/n) (2 n^{-1/2})^{3/4}
= 4 * 2^{3/4} n^{-1/2 - 3/8}
= O(n^{-7/8}).
So f(z) = O(n^{-1/2}) uniformly on [2, t_0], and
q^{1 - s e_j/n} = e_j f(e_j) <= C_0 e_j / sqrt(n)
for an absolute C_0 (absorb f's constant). Summing over the
even e_j in the list:
sum_j q^{1 - s e_j/n} <= (C_0/sqrt(n)) sum_j e_j <= C_0 sqrt(n).
Absorb C_0 into C_1.
6.3 Proof of Proposition 6.1
Let g = sum_{k=1}^{K} c_k G_k be the circuit expansion from
Section 6.1. By subadditivity,
R(g) <= sum_k R(G_k) <= K max_k R(G_k) <= S max_k R(G_k).
Fix one k and view G = prod_{j=1}^r Q_j as in the expansion:
each Q_j is homogeneous of degree e_j > 0, sum_j e_j = n, and
each Q_j is a sum of at most S scalar multiples of products of
e_j homogeneous linear forms.
By Lemma 4.2 (product rank),
R(G) <= 2 Dim prod_{j=1}^r H_{e_j}.
We bound prod_j H_{e_j} in two cases.
Case 1: Every e_j < t_0.
By (6.2), sum_j d_{e_j} >= (s/2n) sum_j e_j = s/2. By (6.3)
for odd e_j (weakening q^{d_e} to q^{d_e/2}, legitimate since
q^{d_e/2} >= q^{d_e}), and (6.4) for even e_j:
prod_j H_{e_j}
<= q^{(1/2) sum_j d_{e_j}} exp(4 sum_{even j} q^{1-se_j/n})
<= q^{s/4} exp(4 C_1 sqrt(n)). (6.6)
Using q <= n^{-2/5} and s >= sqrt(n)/2,
q^{s/4} <= n^{-(2/5) * sqrt(n)/8} = n^{-sqrt(n)/20}.
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 summands, each M_l a product of e_{j_0} linear
forms. By subadditivity,
R(G) <= sum_l R( (prod_{j != j_0} Q_j) M_l )
<= S max_l R( (prod_{j != j_0} Q_j) M_l ).
For each l, (prod_{j != j_0} Q_j) M_l is a product of homogeneous
factors: the Q_j (j != j_0) with degrees e_j, plus e_{j_0} linear
forms of degree 1. Total degree
(sum_{j != j_0} e_j) + e_{j_0} = n. Apply Lemma 4.2:
R( (prod_{j != j_0} Q_j) M_l )
<= 2 Dim (prod_{j != j_0} H_{e_j}) H_1^{e_{j_0}}.
Now H_1 = H_1 (evaluate at e = 1). d_1 = dist(lambda, Z). Since
0 < lambda < 1/2, d_1 = lambda. And 1 < t_0 for n large. So by
(6.3), H_1 <= q^{lambda/2}. Hence
H_1^{e_{j_0}} <= q^{lambda e_{j_0}/2} <= q^{lambda t_0/2}
(the second inequality uses e_{j_0} >= t_0 and q < 1).
For the other Q_j with j != j_0:
- if e_j >= t_0, (6.1) gives H_{e_j} <= 5; there are at most
n/t_0 = 4s such factors;
- if e_j < t_0 and odd, (6.3) gives H_{e_j} <= 1;
- if e_j < t_0 and even, (6.4) gives
H_{e_j} <= q^{d_{e_j}} exp(4 q^{1 - se_j/n}). Drop
q^{d_{e_j}} (<= 1); summing over all such even j gives
exp(4 C_1 sqrt(n)) by (6.5).
Combining,
prod_j H_{e_j}
<= 5^{4s} q^{lambda t_0/2} exp(4 C_1 sqrt(n)).
Use q <= n^{-2/5}, lambda >= 3/8, t_0 >= sqrt(n)/4:
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). So
R(G) <= 2 S Dim exp((4 C_1 + 4 log 5) sqrt(n)) n^{-3 sqrt(n)/160}. (6.7)
Combining both cases.
Case 1: R(G) <= 2 Dim exp(4 C_1 sqrt(n)) n^{-sqrt(n)/20}.
Case 2: R(G) <= 2 S Dim exp((4 C_1 + 4 log 5) sqrt(n)) n^{-3 sqrt(n)/160}.
Because sqrt(n)/20 > sqrt(n)/100 and 3 sqrt(n)/160 > sqrt(n)/100
for n large, both bounds are at most
2 S Dim exp(C sqrt(n)) n^{-sqrt(n)/100}
for an absolute C (the extra S in Case 1 is harmless). So
R(G) <= 2 S Dim exp(C sqrt(n)) n^{-sqrt(n)/100}.
Finally, sum over k = 1, ..., K (K <= S):
R(g) <= K * max_k R(G_k)
<= S * 2 S Dim exp(C sqrt(n)) n^{-sqrt(n)/100}
= 2 S^2 Dim exp(C sqrt(n)) n^{-sqrt(n)/100}.
This is Proposition 6.1.
================================================================
7. ITERATED MATRIX MULTIPLICATION HAS LARGE RANK
================================================================
Proposition 7.1 (main IMM bound). Over C, using the balanced
schedule of Section 7.1 and the parameters of Section 5,
there is an absolute C such that, for all sufficiently large
n,
R(IMM_{n,n}) >= Dim exp(-C sqrt(n)).
This section proves Proposition 7.1.
7.1 The balanced schedule
Let f := IMM_{n,n} and L := n - 1 (so there are n^L paths).
The n matrix layers are partitioned into k V-layers and m
U-layers (Section 3), with k + m = n and m - k = s = Theta(sqrt
n). What we have NOT yet fixed is the ORDER in which the
V-layers and U-layers appear along the matrix product. For the
present proof we use the BALANCED SCHEDULE
V U^{l_1} V U^{l_2} V ... V U^{l_k}
where
l_i := 1 + floor(is/k) - floor((i-1)s/k), for i = 1, ..., k.
Because 0 < s/k < 1 for n large, each l_i is 1 or 2. Also
sum_i l_i = k + (floor(ks/k) - floor(0)) = k + s = m.
So the word contains k V's and m U's, starts with V, ends
with U. Crucially, NO TWO V LAYERS ARE ADJACENT (each pair of
consecutive V's has at least one U between them).
The schedule's balanced-ness (roughly one "extra" U per V
when s is spread evenly) is what drives the trace analysis
later: it prevents runs of consecutive same-type layers from
accumulating too much weight.
Paths. A path is a sequence P = (p_0, p_1, ..., p_n) with
p_0 = p_n = 1 and p_1, ..., p_{n-1} in [n]. Its coordinate
at layer t is E_t(P) := x^{(t)}_{p_{t-1}, p_t}. Different
layers involve disjoint variables, and different paths give
different sequences of coordinates.
7.2 Inner product and the two trace moments
Give every homogeneous polynomial space H_E(t) the inner
product in which
z^M / sqrt(M!), |M| = t,
is an orthogonal basis of unit length. Here M ranges over
exponent vectors on the variables of E, |M| = sum_i M_i = t,
and M! = prod_i M_i!. This is the finite homogeneous part of
the Bargmann-Fock normalization, and it has the useful
property that differentiation and multiplication act with
square roots of integer occupations.
Precisely:
d/dv_i ( z^M / sqrt(M!) ) = sqrt(M_i) * z^{M - e_i} / sqrt((M-e_i)!),
v_i ( z^M / sqrt(M!) ) = sqrt(M_i + 1) * z^{M + e_i} / sqrt((M+e_i)!),
where e_i is the unit vector in coordinate i. Repeated
differentiation of order d has coefficient
sqrt(M_i (M_i - 1) ... (M_i - d + 1)) =: sqrt((M_i)_d), with
NO extra factorial divisor beyond what M! already encodes.
Since f = IMM_{n,n} has bidegree (k, m) (V-degree k,
U-degree m in the balanced schedule), the finite map
F_f = f_{[k,m]}(partial_V, U): H_V(a) H_U(b) -> H_V(a-k) H_U(b+m)
is EXACTLY the restriction to H_V(a) H_U(b) of the full
operator T_f = f(partial_V, U). We denote by Dim := h(v,a) h(u,b)
the source dimension.
Trace moments. Define
T := tr(F_f^* F_f) = ||F_f||_F^2 (squared Frobenius norm),
T_2 := tr((F_f^* F_f)^2) = ||F_f^* F_f||_F^2.
If (s_1, ..., s_R) are the nonzero singular values of F_f
(R = rank = R(f)), then T = sum s_i^2 and T_2 = sum s_i^4.
By the Cauchy-Schwarz inequality,
T^2 = (sum_i s_i^2)^2 <= R * sum_i s_i^4 = R * T_2,
so if T > 0,
R(f) >= T^2 / T_2. (7.1)
This is the trace-rank inequality.
The plan: prove the moment bounds
T >= D n^L mu exp(-O(n^{-1/2})), (7.2)
T_2 <= D n^{2L} mu^2 exp(O(sqrt(n))), (7.3)
where D := Dim (source dimension), L := n - 1, and
mu := A^k (1 + B)^m, A := a/v, B := b/u.
Then (7.1) gives:
R(f) >= T^2 / T_2
>= D exp(-O(n^{-1/2}) - O(sqrt(n)))
>= Dim exp(-C sqrt(n))
for large n, which is Proposition 7.1.
7.3 Occupation moments
Fix an inner product on H_V(a) H_U(b). A uniformly random
basis vector has exponent vector M = (M_V, M_U) where M_V is
uniform among weak compositions of a into v parts (v V-
variables) and M_U is uniform among weak compositions of b
into u parts (u U-variables). M_V and M_U are independent.
We compare these to GEOMETRIC variables: independent
nonnegative-integer variables Z_i with Pr(Z_i = j) =
(1/(1+G)) (G/(1+G))^j, mean E[Z_i] = G. Factorial moments:
E[(Z_i)_d] = d! G^d.
Lemma 7.2 (occupation moments). Let M = (M_1, ..., M_r) be
uniform among the weak compositions of t >= 0 into r >= 1
parts.
(a) 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!, (7.4)
where (x)_d := x(x-1)...(x-d+1) is the falling factorial and
r^{overline H} := r(r+1)...(r+H-1) is the rising factorial.
Both empty products are 1. RHS is 0 when H > t.
(b) Let Z_1, ..., Z_r be independent geometric, mean G = t/r.
If P is a polynomial with nonnegative coefficients in the
basis {prod_i (z_i)_{d_i}}, then
E[P(M)] <= E[P(Z)]. (7.5)
(c) If t > 0 and 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)]. (7.6)
Proof. (a) For d >= 0,
sum_{j >= 0} (j)_d y^j = d! y^d / (1 - y)^{d+1}.
Therefore, by generating functions over all weak compositions
(no total-size constraint),
sum_{M >= 0} prod_i (M_i)_{d_i} y^{|M|}
= (prod_i d_i!) y^H / (1 - y)^{H+r}.
Coefficient of y^t is (prod_i d_i!) C(t + r - 1, t - H).
Divide by the number C(t + r - 1, t) of weak compositions:
E[prod (M_i)_{d_i}]
= (prod_i d_i!) C(t + r - 1, t - H) / C(t + r - 1, t)
= (prod_i d_i!) (t)_H / r^{overline H}.
Zero when H > t. This proves (7.4).
(b) and (c) Ratio of composition moment to geometric moment,
using E[(Z_i)_d] = d! G^d and G = t/r:
E_comp[prod (M_i)_{d_i}] / E_geom[prod (Z_i)_{d_i}]
= [ (t)_H / r^{overline H} ] / (t/r)^H
= prod_{j=0}^{H-1} [ (1 - j/t) / (1 + j/r) ].
Each factor is <= 1 (since j/t >= 0 and j/r >= 0, so both
numerator and denominator are between 0 and 1 and denominator
>= 1). Hence (7.5).
For (7.6): using log(1 - x) >= -2x for 0 <= x <= 1/2 and
log(1 + x) <= x for x >= 0,
log of the ratio
= sum_{j=0}^{H-1} log(1 - j/t) - sum_{j=0}^{H-1} log(1 + j/r)
>= -sum_j (2j/t) - sum_j (j/r)
= -(H-1)H/t - (H-1)H/(2r)
>= -H^2/t - H^2/(2r).
Since H <= H_0, bounded below by -H_0^2/t - H_0^2/(2r).
Combining with (b) and summing over the (nonnegative) terms
of P produces (7.6). The case t = 0: both M and a mean-zero
geometric vector are identically 0, and (7.5) is immediate.
The lemma's comparison is TERMWISE in the falling-factorial
basis: we do not need to assume the coordinates of M are
independent. We will apply it separately in V and U.
By Lemma 5.1, taking H_0 = 2n satisfies H_0 <= min(a,b)/2
and gives a combined logarithmic loss of
O( (2n)^2/a + (2n)^2/v + (2n)^2/b + (2n)^2/u )
= O(n^2/n^{5/2} + n^2/n^3) = O(n^{-1/2}). (7.7)
7.4 The first trace T
For each path P, the summand of F_f corresponding to P
contracts the derivative factors at V-layers and expands the
multiplication factors at U-layers:
d/dv applied at layer t (V-type) lowers the occupation of
x^{(t)}_{p_{t-1}, p_t} by 1; multiplying by x^{(t)}_{p_{t-1}, p_t}
at layer t (U-type) raises it by 1.
So the shift in exponent vector is
epsilon_P := - sum_{t in V} e_{E_t(P)} + sum_{t in U} e_{E_t(P)},
where e_{E_t(P)} denotes the unit vector in the coordinate
x^{(t)}_{p_{t-1}, p_t}. The coefficient (in the orthonormal
basis) is, applying the formulas above across all layers,
c_P(M)
= ( prod_{t in V} M_{E_t(P)} prod_{t in U} (M_{E_t(P)} + 1) )^{1/2}. (7.8)
We interpret c_P(M) = 0 when any V-coordinate M_{E_t(P)} < 1
so that the corresponding derivative gives zero.
Observation. DIFFERENT PATHS GIVE DISTINCT SHIFTS. A path P
specifies the coordinate in every layer, hence every vertex
p_0, ..., p_n. Two different paths differ in at least one
layer's coordinate, hence in at least one coordinate of
epsilon_P, so epsilon_P != epsilon_Q.
Consequence. For a fixed domain exponent vector M, summing
c_P(M)^2 over all paths P gives the sum of squared entries
of F_f. With the expectation over uniform M in the domain
(weak compositions of a into v parts times weak compositions
of b into u parts),
T = Dim * sum_{P} E_M[ c_P(M)^2 ]. (7.9)
The function M -> c_P(M)^2 = prod_{t in V} M_{E_t(P)}
prod_{t in U} (M_{E_t(P)} + 1) is a polynomial in M with
NONNEGATIVE falling-factorial expansion. Each factor is
either M_e = (M_e)_1 (order 1 in M_e's falling-factorial
basis) or M_e + 1 = (M_e)_1 + 1 (order at most 1). So each
layer contributes order at most 1 in its own coordinate, and
the total order in V is at most k, in U at most m. (Total
order <= k + m = n <= 2n =: H_0.)
Under independent geometric occupations Z_V of mean
A = a/v (V-side) and Z_U of mean B = b/u (U-side),
each V-layer contributes E[M_e] = A, each U-layer
contributes E[M_e + 1] = B + 1. So
E_Z[ c_P(Z)^2 ] = A^k (1 + B)^m = mu. (7.10)
Applying Lemma 7.2 (occupation moments) to M -> c_P(M)^2
with H_0 = 2n, and using the combined loss (7.7):
E_M[ c_P(M)^2 ] >= exp(-O(n^{-1/2})) * E_Z[ c_P(Z)^2 ]
= mu * exp(-O(n^{-1/2})). (7.11)
Substituting into (7.9):
T >= Dim * n^L * mu * exp(-O(n^{-1/2})). (7.12)
Since T > 0 (the RHS is positive for large n), the trace-
rank inequality (7.1) applies. This completes the lower
bound (7.2) on T.
7.5 The second trace T_2: four paths
Write F_f(N, M) for the entry of F_f at (row N, column M),
where N is a codomain basis vector and M is a domain basis
vector. Then
(F_f^* F_f)_{M, M''} = sum_N conj(F_f(N, M)) F_f(N, M''),
and T_2 = sum_{M, M''} |(F_f^* F_f)_{M, M''}|^2. Expand
F_f(N, M) = c_P(M) if N = M + eps_P for some path P, else 0.
Then
T_2 = sum over (M, M'', P, Q, R, S) such that
M + eps_P = M'' + eps_Q and M + eps_R = M'' + eps_S,
of c_P(M) c_Q(M'') c_R(M) c_S(M'').
The two conditions combine into eps_P - eps_Q = eps_R - eps_S,
and M'' = M + eps_P - eps_Q is determined by (M, P, Q). So
T_2 = sum over (M, (P,Q,R,S): eps_P - eps_Q = eps_R - eps_S)
of c_P(M) c_Q(M') c_R(M) c_S(M'),
(7.13) M' = M + eps_P - eps_Q.
We use the zero convention: c_P(M) etc. are extended by 0 to
any M with a negative or out-of-range coordinate.
Averaging over uniform M in the domain:
T_2 = Dim * E_M [ sum_{...} c_P(M) c_Q(M') c_R(M) c_S(M') ]. (7.14)
Per-layer condition. Since V-layers and U-layers use DISJOINT
variable sets, and every layer has its own coordinates,
condition eps_P - eps_Q = eps_R - eps_S holds PER LAYER:
e_{E_t(P)} - e_{E_t(Q)} = e_{E_t(R)} - e_{E_t(S)}, for every t. (7.15)
Here e_{E_t(X)} is the unit vector in the variable "layer t's
entry used by path X". For fixed t, condition (7.15) says that
the difference of two such unit vectors equals another such
difference. There are EXACTLY two ways this can happen:
N-type (SAME pairing): E_t(P) = E_t(Q) =: u and E_t(R) = E_t(S) =: w.
(Both differences are zero.)
D-type (CROSS pairing): E_t(P) = E_t(R) =: u and E_t(Q) = E_t(S) =: w,
with u != w.
The all-equal case (u = w) belongs to N-type.
Local polynomial table. Fix a compatible (P, Q, R, S) at layer t.
The four-coefficient product c_P(M) c_Q(M') c_R(M) c_S(M') is a
product over layers; at layer t, using (7.8) and the shifts in
each case, its contribution depends only on the type (N or D),
the group (V or U), and on the two variables u, w via their
occupations in M (and M'). Concretely, the contribution is:
| V-group | U-group
-----+---------------------------+---------------------
N | M_u M_w | (M_u + 1)(M_w + 1)
D | M_u (M_w + 1) | (M_u + 1) M_w
Let me verify the entries, using (7.8) c_X(Y) = sqrt of
(prod_{t in V} Y_{E_t(X)} prod_{t in U} (Y_{E_t(X)} + 1)).
- N | V. P and Q both use u; R and S both use w. The four
coefficients are c_P(M), c_Q(M'), c_R(M), c_S(M') with
square factors sqrt(M_u) sqrt(M'_u) sqrt(M_w) sqrt(M'_w).
In N-type, M' = M at u and w (no shift at this layer locally).
Product: M_u M_w. Matches.
- N | U. Same, with U-formulas: (M_u + 1)(M_w + 1). Matches.
- D | V. P, R both at u; Q, S both at w. At a V-layer of
D-type, the shift is eps_P - eps_Q = -e_u + e_w (both
differentiated). So M'_u = M_u - 1, M'_w = M_w + 1.
c_P(M)^2 = M_u, c_Q(M')^2 = M'_w = M_w + 1, c_R(M)^2 = M_u,
c_S(M')^2 = M'_w = M_w + 1. Product: M_u (M_w + 1). Matches.
- D | U. Same D-type but at a U-layer: shift is +e_u - e_w.
M'_u = M_u + 1, M'_w = M_w - 1.
c_P(M)^2 = M_u + 1, c_Q(M')^2 = M'_w + 1 = M_w, c_R(M)^2 =
M_u + 1, c_S(M')^2 = M_w. Product: (M_u + 1) M_w. Matches.
Zero convention handled: in D | V, the shift decreases M_u,
so if M_u = 0, c_P(M) = 0, and M_u(M_w+1) = 0. In D | U, the
shift decreases M_w, so if M_w = 0, c_Q(M') = 0 and (M_u+1)M_w
= 0. The table is exact everywhere.
Geometric expectation table. Take expectations under INDEPENDENT
geometric occupations Z of mean A = a/v on V and B = b/u on U.
Using E[Z] = G, E[Z^2] = 2G^2 + G, E[(Z+1)^2] = 2G^2 + 3G + 1:
- N | V, u != w: E[M_u M_w] = A^2. Divide by A^2: weight 1.
- N | V, u = w: E[M_u^2] = 2A^2 + A. Divide by A^2: 1 + (1 + 1/A)
= 1 + alpha^{-1} (since alpha = A/(1+A), alpha^{-1} = 1 + 1/A).
- N | U, u != w: E[(M_u+1)(M_w+1)] = (B+1)^2. Divide by (B+1)^2: 1.
- N | U, u = w: (2B^2 + 3B + 1)/(B+1)^2
= (2B+1)(B+1)/(B+1)^2 = (2B+1)/(B+1) = 1 + B/(B+1) = 1 + beta.
- D | V: E[M_u(M_w+1)] = A(A+1). Divide by A^2: (A+1)/A
= 1 + 1/A = alpha^{-1}.
- D | U: E[(M_u+1)M_w] = B(B+1). Divide by (B+1)^2: B/(B+1) = beta.
So the normalized local weights are
| V-group | U-group
-----+---------------------------+-------------------
N | 1 + alpha^{-1} 1_{u=w} | 1 + beta 1_{u=w}
D | alpha^{-1} | beta
The product of normalizers over all n layers (V-layer: A^2,
U-layer: (1+B)^2) is A^{2k} (1+B)^{2m} = mu^2.
Relaxation and counting. Fix a TYPE WORD tau in {N, D}^n
(specifying the pairing type at each layer). ENLARGE its class
of quadruples by DROPPING the inequalities u != w at every
D-layer. Assign the same weight alpha^{-1} or beta to the newly
admitted tuples (as weights, not as actual occupation moments;
every new weight is nonnegative). So the enlarged sum is an
UPPER bound.
Count quadruples for a fixed type word. At each internal vertex
v_t (t = 1, ..., n-1), the four path labels are constrained by
the two adjacent layers t and t+1:
- Same type on both sides: two independent free labels
(n^2 choices).
- Different types: the two constraints identify all four
labels (n choices).
The two external endpoints v_0 = v_n = 1 are fixed. Summing
over all internal vertices gives
n^{2L - w(tau)}, w(tau) := #{t in [n-1] : tau_t != tau_{t+1}}.
Weight estimates. For an N|V layer t, the u = w event requires
the P=Q label to equal the R=S label at BOTH endpoints v_{t-1}
and v_t. At each endpoint v_s that is internal (1 <= s <= n-1)
and lies between two N-type layers (tau_s = tau_{s+1} = N),
the two labels are independent uniform in [n], so P(u=w) = 1/n.
At any other endpoint (external, or mixed-type), u = w is forced.
Let h_t := number of such N-N interior end vertices of layer t
(so 0 <= h_t <= 2). Averaging the local weight:
E[1 + alpha^{-1} 1_{u=w}] = 1 + alpha^{-1} n^{-h_t}.
Different V layers have disjoint end-vertex sets (no two V
layers are adjacent in the balanced schedule), so these events
are independent across N|V layers.
For N|U layers we instead bound 1 + beta 1_{u=w} <= 1 + beta
pointwise (no independence assertion needed).
Combining with the type-word count and the D-layer contributions:
T_2 / (Dim n^{2L} mu^2) <= (1 + beta)^m *
sum_tau n^{-w(tau)} alpha^{-d_V(tau)} beta^{d_U(tau)} *
prod_{t in N_V(tau)} (1 + alpha^{-1} n^{-h_t}), (7.16)
where d_V(tau), d_U(tau) count D-positions in V-layers and
U-layers respectively, and N_V(tau) is the set of N-positions
in V-layers.
Since beta <= 2/sqrt(n) and m <= n,
(1 + beta)^m <= exp(beta m) <= exp(2 sqrt(n)) = exp(O(sqrt n)).
The remaining task is to bound the tau-sum by exp(C sqrt n).
This is Lemma 7.3.
7.6 Bounding the type-word sum
Define, for a word tau in {N, D}^n,
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}).
Lemma 7.3 (word-sum bound). For all sufficiently large n,
sum_{tau} W(tau) <= exp(C sqrt(n))
for an absolute constant C.
Proof. Call a position t ISOLATED if t is an interior V-position
(2 <= t <= n-1), tau_t = N, and both neighbors of t are D.
Flip every isolated position to D, producing F(tau). By
non-adjacency of V-layers, no OTHER N|V position is affected,
so h_t is unchanged at all surviving N_V positions. An isolated
t gives, comparing weights at position t:
W(tau) factor at t: (1 + alpha^{-1}) [N|V weight] * n^{-2} [2 switches].
W(F(tau)) factor at t: alpha^{-1} [D|V weight] * n^0 [no switches].
So
W(tau) / W(F(tau)) = (1 + alpha)/n^2.
If tau has j isolated positions, W(tau) = W(F(tau)) * ((1+alpha)/n^2)^j.
Preimages. For a word y with no isolated position, its preimages
under F are obtained by flipping an arbitrary subset of its
D-isolated positions (t interior V, tau_t = D, both neighbors D).
These positions of y with type D map, upon flipping back to N, to
isolated positions of the preimage. Let E(y) be that set. 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,
where k <= n/2 (number of V layers).
So
sum_tau W(tau) <= (1 + 2/n^2)^k * sum_{y no isolated} W(y).
Words with no isolated positions. In such y, every INTERIOR N|V
position has h_t >= 1 (if both neighbors were D, y would be
isolated). An ENDPOINT N|V (t = 1 or t = n) can have h_t = 0.
Since the balanced schedule starts with V and ends with U, at
most one endpoint layer is V. So
prod_{t in N_V(y)} (1 + alpha^{-1} n^{-h_t})
<= (1 + alpha^{-1}) (1 + alpha^{-1}/n)^k.
Hence, with
Z := sum_tau n^{-w(tau)} alpha^{-d_V(tau)} beta^{d_U(tau)},
we get
sum_{y no isolated} W(y) <= (1 + alpha^{-1}) (1 + alpha^{-1}/n)^k Z.
Bounding Z. Split into pure N words (all N), pure D words
(all D), and mixed words (both types).
- Pure N word: contributes 1 to Z.
- Pure D word: contributes alpha^{-k} beta^m to Z. Using
beta <= alpha^rho exp(C/b):
alpha^{-k} beta^m <= alpha^{-k + rho m} exp(Cm/b)
= exp(Cm/b) (since k = rho m)
= exp(O(n^{-3/2})).
- Mixed words. Let r = number of INTERIOR D-runs (maximal
consecutive D-intervals not touching either endpoint), and
e = number of D-runs touching an endpoint (e in {0, 1, 2}
for a mixed word). Then w(tau) = 2r + e.
We bound the product of D-layer weights on a D-run I:
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),
where d(I) := #V(I) - rho #U(I).
Interval discrepancy. For any interval I of consecutive
layers, d(I) <= 1 + rho. Proof: write I as a union of
complete chunks (each chunk is V U^{l_i}), possibly
preceded by a terminal part of one chunk (only U's, so
d <= 0) and followed by an initial part of another chunk
(at most one V, so d <= 1). r consecutive complete chunks
contain r V-layers and r + E U-layers with
E = floor((j+r)s/k) - floor(js/k), |E - rs/k| < 1, so
their discrepancy is r - rho(r+E) = rho(rs/k - E) < rho.
Interval-in-single-chunk also gives d <= 1. Summing: for
an interval spanning multiple chunks, d(I) <= 0 + rho + 1
= 1 + rho.
Consequently, for any D-run I:
alpha^{-d(I)} <= alpha^{-(1+rho)} <= n^{(1+rho)/2} <= n,
exp(C #U(I)/b) contributes a global exp(Cn/b) factor;
product of weights on I <= n * exp(C #U(I)/b).
Runs are disjoint, so multiplying across all r + e runs:
n^{r+e} * exp(Cn/b).
Combined with the switch cost n^{-(2r+e)}:
contribution from within D-runs * switch cost
= n^{-(2r+e)} * n^{r+e} exp(Cn/b)
= n^{-r} exp(Cn/b).
Number of words with given (r, e) (and known initial type):
2 C(n-1, 2r + e). So
(mixed word contribution to Z)
<= sum_{e=0}^2 sum_{r>=0} 2 C(n-1, 2r+e) n^{-r} exp(Cn/b).
Bounding (for e in {0, 1, 2}):
sum_r C(n-1, 2r+e) n^{-r}
<= sum_r n^{2r+e}/(2r+e)!
<= n^2 sum_r (sqrt(n))^{2r}/(2r)!
<= n^2 exp(sqrt(n)),
using 1/(2r+e)! <= 1/(2r)! and sum_r x^{2r}/(2r)! = cosh(x) <=
exp(x). So the mixed contribution is at most
6 * n^2 exp(sqrt(n)) * exp(Cn/b) = exp(O(sqrt(n))).
Putting together:
Z <= 1 + exp(O(n^{-3/2})) + exp(O(sqrt(n))) = exp(O(sqrt(n))).
Finally, bound the prefactor:
log( (1 + 2/n^2)^k * (1 + alpha^{-1}) * (1 + alpha^{-1}/n)^k )
<= 2k/n^2 + log(1 + sqrt(n)) + k/sqrt(n)
<= O(log n) + O(sqrt(n)) = O(sqrt(n)).
So sum_tau W(tau) <= exp(O(sqrt(n))) * Z = exp(O(sqrt(n))).
This proves Lemma 7.3.
7.7 Completion of the proof of Proposition 7.1
From (7.12): T >= Dim * n^L * mu * exp(-O(n^{-1/2})).
From (7.16), Lemma 7.3, and (1+beta)^m <= exp(O(sqrt n)):
T_2 <= Dim * n^{2L} * mu^2 * exp(C' sqrt n).
Since T > 0 (for large n), the trace-rank inequality (7.1) gives
R(f) >= T^2/T_2
>= Dim * exp(-O(n^{-1/2}) - C' sqrt n)
= Dim * exp(-C sqrt n),
which is Proposition 7.1. Done.
================================================================
8. THE MAIN LOWER BOUND: PROOF OF THEOREM 1 OVER C
================================================================
Let f = IMM_{n,n}. Let g be the polynomial computed by any
syntactically homogeneous Sigma-Pi-Sigma-Pi-Sigma circuit
over C of size S that computes f. Then g = f.
Fix the parameters of Section 5 and the balanced schedule of
Section 7.1 for the split of the n layers into k V-layers
and m U-layers. These choices give a specific Dim and a
specific F_f.
By Proposition 7.1:
R(f) >= Dim * exp(-C_1 sqrt n).
By Proposition 6.1 (uniform in the V/U split):
R(g) <= 2 S^2 Dim exp(C_2 sqrt n) n^{-sqrt n/100}.
Since g = f and both use the same parameters:
Dim exp(-C_1 sqrt n) <= 2 S^2 Dim exp(C_2 sqrt n) n^{-sqrt n/100}.
Cancel Dim and rearrange:
S^2 >= (1/2) exp(-(C_1 + C_2) sqrt n) n^{sqrt n/100},
S >= (1/sqrt 2) exp(-(C_1 + C_2) sqrt n / 2) n^{sqrt n/200}.
For all n >= n_0 = exp(400 (C_1 + C_2)) (say), we have
(sqrt n / 400) log n - (C_1 + C_2) sqrt n / 2 >= (1/2) log 2,
which makes the RHS at least n^{sqrt n/400}. Hence
S >= n^{sqrt n/400}.
The threshold n_0 is absolute. This proves Theorem 1 with c =
1/400 for the field C. Section 9 extends the result to every
characteristic-zero field. Done.
================================================================
9. LIFTING TO EVERY CHARACTERISTIC-ZERO FIELD
================================================================
Corollary 9.1. There is an absolute integer n_0 such that,
for every field K of characteristic zero and every n >= 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 large and any characteristic-zero field K.
Field-independent rank. Recall from Section 7.2 that
F_f := f_{[k,m]}(partial_V, U) is a linear map
H_V(a) H_U(b) -> H_V(a-k) H_U(b+m).
For any field K, F_f is K-linear. The rank of F_f as a matrix
depends only on which integer minors are zero; this matches
over Z, C, and any characteristic-zero K because the natural
map Z -> K is injective.
Concretely, represent F_f as a matrix in the ORDINARY
MONOMIAL BASES of the source and target (not the Bargmann-
Fock orthonormal bases). Its entries are computed as follows:
- coefficients of f: since IMM_{n,n} is a sum of distinct
monomials, each coefficient is 0 or 1;
- the action of partial differentiation on a monomial
z^M gives c(M) z^{M - e_i} with c = M_i, an integer;
- the action of multiplication by a variable gives
z^M -> z^{M + e_i}, coefficient 1, integer.
So the matrix of F_f in monomial bases has entries in Z.
Let r_K := rank_K(F_f). For an integer matrix, r_K equals the
largest k such that some k-by-k minor is nonzero. The map
Z -> K is injective (char K = 0), so a minor is zero in K
iff it is zero in Z iff it is zero in C. Therefore
rank_K(F_f) = rank_C(F_f) >= Dim exp(-C_1 sqrt n),
using Proposition 7.1 for the last inequality.
Propagation to any small circuit. Proposition 6.1 was proved
over an arbitrary field: it uses only the syntactic
homogeneity of the circuit, the decomposition of the circuit
into upper products, and rank subadditivity. So its
conclusion holds verbatim over any field K.
Thus, if a syntactically homogeneous circuit of size S over K
computes f, then with g = f:
R(g) = rank_K(F_f) <= 2 S^2 Dim exp(C_2 sqrt n) n^{-sqrt n/100}.
Combined with rank_K(F_f) >= Dim exp(-C_1 sqrt n), the same
arithmetic as in Section 8 gives
S >= n^{sqrt n/400}
for all n >= n_0 with n_0 absolute.
The threshold n_0 is determined only by Lemma 5.1's estimates
and the constants of Propositions 6.1 and 7.1, which are
independent of K. So the corollary holds uniformly over K.
Done.
================================================================
10. A MATCHING UPPER BOUND: PROOF OF THEOREM 2
================================================================
Proposition 10.1. Let K be any field and n >= 2. Put
t := ceil(sqrt n), r := ceil(n / t).
Then there is a syntactically homogeneous
Sigma-Pi-Sigma-Pi-Sigma circuit over K computing IMM_{n,n}
whose size (including leaves) is at most
2 n^3 + r n^2 + r n^{t+1} + n^{r-1} + 1 <= n^{sqrt n + 4}.
Proof. Partition the n consecutive matrix layers into r
nonempty consecutive blocks, with lengths l_1, ..., l_r <= t
each and sum_j l_j = n (this is possible because r >= n/t).
For block j, let Y^{(j)} be the product of its matrices. For
each entry Y^{(j)}_{a,b}, the polynomial is a sum of
n^{l_j - 1} monomials, one per choice of internal indices;
each monomial is a product of l_j matrix-entry variables and
has degree l_j.
Construct the circuit as follows. Levels go from bottom
(level 5) to top (level 1).
- Level 5 (bottom sum gate per variable): use one identity
sum gate for each of the n^3 variables. That uses n^3
variable leaves and n^3 sum gates.
- Level 4 (product gates): for each block j, each entry
Y^{(j)}_{a,b}, and each monomial of that entry, add one
product gate taking, as input, the l_j variable sum-gates
that make up the monomial. For block j this gives n^2 * n^{l_j - 1}
= n^{l_j + 1} product gates. Summed over j: sum_j n^{l_j + 1}.
- Level 3 (sum gates): for each block j and each entry Y^{(j)}_{a,b},
add one sum gate taking all n^{l_j - 1} monomial-products of
that entry. That uses n^2 sum gates per block, total r n^2.
- Level 2 (product gates): for each tuple (a_1, ..., a_{r-1})
in [n]^{r-1}, add one product gate taking, as inputs, the
r block-entry values
Y^{(1)}_{1, a_1}, Y^{(2)}_{a_1, a_2}, ..., Y^{(r)}_{a_{r-1}, 1}.
That uses n^{r-1} product gates. (If r = 1, this "product
gate" would be a single block-entry value; it can be an
identity gate, absorbed into the output sum, and no separate
gate is needed.)
- Level 1 (output sum gate): add one sum gate taking all
n^{r-1} level-2 product gates. That uses 1 sum gate.
Total count (including leaves): n^3 (leaves) + n^3 (level-5
sum gates) + [sum_j n^{l_j + 1}] (level-4) + [r n^2] (level-3)
+ [n^{r-1}] (level-2) + 1 (level-1).
So the size is at most
2 n^3 + r n^2 + sum_j n^{l_j + 1} + n^{r-1} + 1
<= 2 n^3 + r n^2 + r n^{t+1} + n^{r-1} + 1,
using l_j <= t (so n^{l_j + 1} <= n^{t+1}).
Syntactic homogeneity. Assign formal degree 1 to every
variable, 0 to constants. Bottom sum gates (identity per
variable, or the level-3 sum gate inputs) have degree 1 (for
the identity sum) or degree 0 (for constant leaves); mixed
cases do not occur since each level-5 sum gate has all
variable leaves or all constant leaves (and there are no
constants here). Each level-4 product gate takes exactly l_j
degree-1 inputs, so its formal degree is l_j. Each level-3
sum gate adds monomials of a fixed block-degree l_j, so its
formal degree is l_j. Each level-2 product gate multiplies one
input of form l_j from each block, so its formal degree is
l_1 + ... + l_r = n. The level-1 output sums these degree-n
pieces. So the circuit is syntactically homogeneous of
degree n.
Size bound. Since t = ceil(sqrt n), we have t - 1 < sqrt n,
so t <= sqrt n + 1. And r = ceil(n / t). Because
n/t <= n/sqrt n = sqrt n <= t, we have r <= t.
For n >= 3, t >= 2. Using r <= t <= n (valid for n >= 3):
r n^2 <= n * n^2 = n^3
r n^{t+1} <= n * n^{t+1} = n^{t+2}
n^{r-1} <= n^{t-1} (r <= t)
so
2 n^3 + r n^2 + r n^{t+1} + n^{r-1} + 1
<= 3 n^3 + n^{t+2} + n^{t-1} + 1.
Group (n^{t-1} + 1) <= n^{t+2} (since n^{t-1} >= 2 and
n^{t-1} + 1 <= 2 n^{t-1} <= n * n^{t-1} = n^t <= n^{t+2}
for n >= 2). Also 3 n^3 <= n^{t+2} (since n^{t-1} >= 3 for
n >= 3, t >= 2). So
3 n^3 + n^{t+2} + (n^{t-1} + 1) <= n^{t+2} + n^{t+2} + n^{t+2}
= 3 n^{t+2}.
Finally 3 n^{t+2} <= n * n^{t+2} = n^{t+3} (n >= 3), and
t + 3 <= sqrt n + 4 (since t <= sqrt n + 1). Hence
size <= n^{t+3} <= n^{sqrt n + 4}.
For n = 2: t = ceil(sqrt 2) = 2, r = ceil(2/2) = 1. First
count: 2 * 8 + 1 * 4 + 1 * 8 + 1 + 1 = 30. And 2^5 = 32 >= 30,
with t = 2 = sqrt 4, so 30 <= 2^{t+3} = 2^5. Good. Done.
This proves Theorem 2.
================================================================
11. INDEX OF NOTATION
================================================================
n matrix size and number of layers
[n] {1, 2, ..., n}
L n - 1 (number of internal vertices / paths')
X^{(t)} the matrix of variables of layer t
x^{(t)}_{i,j} variable at layer t, entry (i, j)
IMM_{n,n} (X^{(1)} X^{(2)} ... X^{(n)})_{1,1}
f synonym for IMM_{n,n}
V-layers k matrix layers, |V| = v = k n^2
U-layers m matrix layers, |U| = u = m n^2
k, m |V|, |U| (with k + m = n)
s m - k = Theta(sqrt n)
H_E(t) homogeneous polys of degree t on E
h(r,t) C(r+t-1, t) = dim H_E(t) for |E| = r
h(v,a) h(u,b) source dimension for the measure
Dim h(v,a) h(u,b)
rho, lambda k/m, k/n
a, b differentiation/multiplication degrees
alpha a/(a+v)
beta b/(b+u)
q alpha^{(1+rho)/2}
mu A^k (1+B)^m, A = a/v, B = b/u
H_e sum_{i=0}^{e} q^{|i - lambda e|}
d_e dist(lambda e, Z)
t_0 n/(4s)
T_Q Q(partial_V, U): K[V, U] -> K[V, U]
F_g g_{[k,m]}(partial_V, U)
R(g) rank(F_g)
eps_P shift in exponents from path P
c_P(M) coefficient of path P at input M
T, T_2 tr(F^*F), tr((F^*F)^2)
N-type, D-type pairing types at a layer
tau a type word in {N, D}^n
w(tau) number of type switches in tau
h_t # N-N interior end vertices of layer t
W(tau) summand of the type-word sum (7.16)
THE END.