Results on homogeneous depth-five circuits, a rank measure from derivatives and multiplications, and iterated matrix multiplication

The course proves the statements below; each link leads to the statement with its assumptions and its proof. The lessons are self-checked by the writing AI; independent mathematical review is not complete.

• What a syntactically homogeneous circuit with five layers computes — Lemma 4.1. A nonzero polynomial computed by a syntactically homogeneous Sigma-Pi-Sigma-Pi-Sigma circuit of size S with output of formal degree n is a sum of at most S scalar multiples of products Q_1 ... Q_r of homogeneous polynomials of degrees e_j >= 1 with sum n, and each Q_j is a sum of at most S scalar multiples of products of e_j linear forms. No condition on the bottom sums.
• A homogeneous circuit for iterated matrix multiplication — Proposition 5.1. Over every field and for n >= 2 there is a syntactically homogeneous Sigma-Pi-Sigma-Pi-Sigma circuit computing IMM_(n,n) of size at most 2n^3 + r n^2 + r n^(t+1) + n^(r-1) + 1 <= n^(sqrt(n)+4), with t = ceil(sqrt n), r = ceil(n/t).
• The rank measure of a product through intermediate spaces — Lemma 3.2. For homogeneous Q_1, ..., Q_r of degrees e_j with sum n: R(Q_1 ... Q_r) is at most the sum, over the assignments (i_1, ..., i_r) with 0 <= i_j <= e_j and sum k, of dim H(a - I, b + J), where I and J are the degrees in V and in U of the factors with i_j > lambda e_j.
• The numbers of the proof and their estimates — Lemma 4.1. For s about sqrt(n), k = (n-s)/2, m = (n+s)/2, a = ceil(v/(sqrt(n)-1)), b = ceil(u alpha^rho/(1-alpha^rho)): n^(-1/2) <= alpha <= n^(-1/2) exp(4 n^(-5/2)), alpha^rho <= beta <= alpha^rho exp(2/b), beta <= 2/sqrt(n), n^(-1/2) <= q <= n^(-2/5), for large n.
• The product bound — Proposition 5.1. For homogeneous Q_1, ..., Q_r of degrees e_j >= 1 with sum n: R(Q_1 ... Q_r) <= 2 D prod_j H_(e_j), with H_e = sum_(i=0)^e q^|i - lambda e|, for every division of the layers.
• H_e and the distance to the integers — Lemma 1.1. H_e <= q^(d_e) (1 + 4 q^(1 - 2 d_e)) <= 5, where d_e is the distance from lambda e to the nearest integer.
• The corrections for small even degrees — Lemma 2.2. For positive integers e_1, ..., e_r with sum at most n, the sum of q^(1 - s e_j/n) over the even e_j < n/(4s) is at most sqrt(n), for large n.
• The rank measure of a depth-five circuit — Proposition 3.1. For large n, every field, and every division of the layers: a polynomial g that is 0 or homogeneous of degree n and is computed by a syntactically homogeneous Sigma-Pi-Sigma-Pi-Sigma circuit of size S has R(g) <= 2 S^2 D exp(11 sqrt n) n^(-sqrt(n)/100).
• Two traces bound the rank — Lemma 2.1. For a linear map F between finite-dimensional complex inner product spaces with T = tr(F*F) > 0 and T_2 = tr((F*F)^2): rank F >= T^2/T_2.
• Factorial moments of a uniformly random composition — Lemma 4.1. For M uniform among the compositions of t into r parts and d_1, ..., d_r >= 0 with sum h: E prod (M_i)_(d_i) = (t)_h / (r (r+1) ... (r+h-1)) * prod d_i!.
• Comparison with independent geometric variables — Lemma 4.2. For a polynomial p with nonnegative coefficients in the products of falling factorials: E p(M) <= E p(Z) for independent geometric Z_i of mean t/r, and E p(M) >= exp(-h_0^2/t - h_0^2/(2r)) E p(Z) if the order of p is at most h_0 <= t/2.
• The first trace for iterated matrix multiplication — Proposition 5.1. T = tr(F_f* F_f) >= D n^(n-1) mu exp(-6/sqrt(n)) with mu = (a/v)^k (1 + b/u)^m, for large n.
• The second trace as a sum over type words — Proposition 7.1. T_2 <= D n^(2(n-1)) mu^2 (1+beta)^m sum over words tau in {N, D}^n of n^(-w(tau)) alpha^(-d_V(tau)) beta^(d_U(tau)) prod over the V layers t of type N of (1 + alpha^(-1) n^(-h_t)).
• The balanced division of the layers — Lemma 1.1. For the division V U^(l_1) ... V U^(l_k) with l_i = 1 + floor(i s/k) - floor((i-1) s/k), every interval of consecutive layers has (number of V layers) - rho (number of U layers) <= 1 + rho.
• The rank measure of iterated matrix multiplication — Proposition 4.1. Over the complex numbers and for the balanced division of the layers: R(IMM_(n,n)) >= D exp(-6 sqrt n) for large n.
• Depth-five lower bound for iterated matrix multiplication — Theorem 5.1. There is n_0 such that for n >= n_0 and every field of characteristic zero, every syntactically homogeneous Sigma-Pi-Sigma-Pi-Sigma circuit computing IMM_(n,n) has size at least n^(sqrt(n)/400).

Reading order

Five lessons, to be read in order. The theorem is proved in full, with no theorem taken from the literature: the first lesson gives the circuits and the upper bound, the second and third bound a rank measure for every small circuit, the fourth and fifth show that the measure of iterated matrix multiplication is almost maximal. The theorem holds for all n from some n_0 on; with the constants of the lessons the final comparison needs log n >= 3401. Nothing is proved over fields of positive characteristic.