Homogeneous depth-five matrix products

Source and verification

This article explains family 135 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Iterated matrix multiplication as a polynomial

Let $X^{(1)},\dots ,X^{(d)}$ be $w\times w$ matrices whose entries are distinct commuting variables. The iterated matrix multiplication polynomial is

$${\mathrm{IMM}}_{w,d}=(X^{(1)}\cdots X^{(d)}{)}_{1,1}.$$

For three layers, for example,

$${\mathrm{IMM}}_{w,3}=\sum _{i,j=1}^w{x}_{1i}^{(1)}{x}_{ij}^{(2)}{x}_{j1}^{(3)}.$$

Each monomial describes a path through the matrix layers, starting and ending at index one. The polynomial is homogeneous of degree $d$: every monomial has total degree $d$. The target here is the balanced case $w=d=n$, with $n^3$ ambient entry variables. Some entries in the first and last layers do not occur in the chosen output, but remain part of the ambient variable space used in the proof. (OpenAI, 2026)

An arithmetic circuit is a directed acyclic graph of sum and product gates. The source permits scalar coefficients on sum inputs, arbitrary finite fan-in and fan-out, and sharing of intermediate gates. A five-layer circuit has types

$$\Sigma \Pi \Sigma \Pi \Sigma$$

from output to leaves. Consecutive computational layers are connected; bottom sums read variable or scalar leaves. No restriction is placed on the number of variables in a bottom linear form.

Syntactic homogeneity assigns formal degree one to variables and zero to constants. A product adds input degrees, counting repeated occurrences; all inputs to a sum must have the same degree. A gate whose polynomial cancels to zero retains its assigned formal degree. This requirement is stronger than merely asking the output polynomial to be homogeneous.

🏷️ The lower and upper bounds

Source bounds for homogeneous depth five

There is an absolute threshold $n_0$ such that, over every characteristic-zero field and for $n\ge n_0$, every circuit in the stated model computing ${\mathrm{IMM}}_{n,n}$ requires at least

$$n^{\sqrt{n}/400}$$

gates. Over every field and for $n\ge 2$, there is such a circuit with at most

$$n^{\sqrt{n}+4}$$

gates, including leaves. (OpenAI, 2026)

Thus the scale is $n^{\Theta (\sqrt{n})}$; the constants in the exponent are not claimed to match. The lower bound permits shared subcircuits and unrestricted bottom support. It is a gate bound, not an assumption that the number of wires equals the number of gates. Scalars on sum inputs are part of this model and do not incur separate multiplication gates.

Iterated matrix multiplication still has polynomial-size circuits with unrestricted depth. Reusing the entries of successive partial products provides one. The theorem measures the cost of compressing that computation into five homogeneous layers, not hardness of matrix multiplication in all arithmetic models.

🏷️ Differentiation and multiplication as a rank measure

Split the matrix layers into two sets, giving variable sets $V,U$ of sizes $v,u$. Let ${\mathcal{H}}_V(a)$ be the space of homogeneous polynomials of degree $a$ in $V$. Counting exponent vectors gives

$$\dim {\mathcal{H}}_V(a)=\left(\genfrac{}{}{0ex}{}{v+a-1}{a}\right).$$

For a degree-$n$ polynomial $g$, let $g_{[k,m]}$ be its component having degree $k$ in $V$ and $m$ in $U$, where $k+m=n$. Replace $V$ variables by partial derivatives and $U$ variables by multiplication operators. The resulting finite map is

$$\begin{array}{c}{F}_g=g_{[k,m]}({\partial }_V,U),\\ F_g:{\mathcal{H}}_V(a)\otimes {\mathcal{H}}_U(b)\\ ⟶{\mathcal{H}}_V(a-k)\otimes {\mathcal{H}}_U(b+m).\end{array}$$

Write $R(g)=\mathrm{rank}{F}_g$ and let $D$ be the source dimension. For a one-variable example, $g=vu$ acts by

$$v^a{u}^b⟼a{v}^{a-1}{u}^{b+1}.$$

Differentiation and multiplication commute here because they act on disjoint variable sets. Thus the full substitution $Q\mapsto Q({\partial }_V,U)$ respects products. The fixed bidegree projection in $F_g$ does not: a product must first be expanded into its possible bidegree allocations. Rank is subadditive,

$$R(g_1+g_2)\le R(g_1)+R(g_2),$$

which lets the measure track sums of circuit contributions.

The parameters are deliberately asymmetric. Let $s$ be the largest integer at most $\sqrt{n}$ with the parity of $n$, and put

$$k=(n-s)/2,m=(n+s)/2.$$

The proof chooses $a,b=\Theta (n^{5/2})$ to balance dimension lost under differentiation against dimension gained under multiplication. The small offset from $k=m$ forces useful nonintegrality in the shares $ke/n$ assigned to factors of degree $e$. It is part of the lower-bound mechanism, not an arbitrary perturbation. (OpenAI, 2026)

🏷️ Bottlenecks in a small circuit

Consider a homogeneous product $G={\prod }_j{Q}_j$ with factor degrees $e_j$ summing to $n$. Split each $Q_j$ by its possible $V$-degree. Within a fixed allocation, apply factors whose $V$-degree exceeds $k{e}_j/n$ first. The resulting operator passes through a smaller intermediate homogeneous space, so its rank cannot exceed that space’s dimension.

Distances from $k{e}_j/n$ to integers control the sum over allocations. If every factor degree is below a threshold of order $\sqrt{n}$, the accumulated discrepancies yield a substantial power of $n$ in the rank saving. The source separately controls small even-degree error terms; bounding each by an arbitrary constant would produce too large a loss over many factors.

If a factor has large degree, expand just one occurrence of it through its middle sum. That factor becomes a product of many linear forms, which supplies the needed discrepancy. Other factors remain unexpanded. Even if the same gate occurs repeatedly, only one occurrence is expanded.

This is why sharing does not invalidate the gate count. At a sum gate, repeated wires from one predecessor can be combined by adding their scalar coefficients, leaving at most $S$ distinct predecessors in a size-$S$ circuit. The output has at most $S$ top product contributions; expanding one middle sum costs at most another $S$. Product multiplicities remain counted in the degree budget, so the proof does not silently replace gates by wires or unfold the whole circuit into a formula.

The resulting source estimate is

$$R(g)\le 2S^{2}D{e}^{C\sqrt{n}}{n}^{-\sqrt{n}/100}$$

for an absolute constant $C$. The intermediate-space and discrepancy bounds are the substantive inputs behind this compact circuit estimate. They hold without bounding the support of bottom linear forms. (OpenAI, 2026)

🏷️ Large rank from path moments

For the opposite estimate, arrange the $V$ and $U$ layers with no adjacent $V$ layers. The $m-k=s$ extra $U$ layers are distributed nearly evenly. Then each path monomial has exactly the selected bidegree $(k,m)$, and long runs of one pairing pattern can be controlled.

Over $\mathbb{C}$, declare the normalized monomials

$$\frac{z^M}{\sqrt{M!}},M!=\prod _i{M}_i!,$$

orthonormal. Differentiation in coordinate $i$ has coefficient $\sqrt{M_i}$, and multiplication has coefficient $\sqrt{M_i+1}$. These factorial weights turn operator traces into weighted path counts.

Set $H=F_f^{\ast }{F}_f$ for $f={\mathrm{IMM}}_{n,n}$. If its nonzero eigenvalues are ${\lambda }_1,\dots ,{\lambda }_r$, Cauchy–Schwarz gives

$${\left(\sum _i{\lambda }_i\right)}^2\le r\sum _i{\lambda }_i^2.$$

Consequently

$$R(f)=r\ge \frac{(\mathrm{tr}H{)}^2}{\mathrm{tr}(H^2)}.$$

The first trace counts paths; the second counts compatible quadruples of paths. At each layer there are two possible pairing patterns. Changing pattern forces four vertex labels to agree, costing a factor of $n$ in the number of choices. The proof sums these pattern weights while tracking endpoints and isolated corrections.

The occupation weights are not independent: choosing a monomial uniformly in a homogeneous space gives a uniform weak composition of its total degree. An exact identity handles that dependence. If $(M_1,\dots ,M_r)$ is uniform among weak compositions of $t$, and $H_0={\sum }_i{d}_i$, then

$$\mathbb{E}\prod _i(M_i{)}_{d_i}=\frac{(t{)}_{H_0}}{r^{\overline{H_0}}}\prod _i{d}_i!,$$

where $(t{)}_j$ and $r^{\overline{j}}$ are falling and rising factorials. For $d_1=1$ and all other $d_i=0$, this reduces to $\mathbb{E}{M}_1=t/r$. The full identity permits comparison with geometric-variable moments, with the coefficient signs checked before inequalities are applied.

Writing $L=n-1$ and using the source’s positive common weight $\mu$, the moment bounds have the form

$$\begin{array}{rl}\mathrm{tr}H& \ge D{n}^L\mu e^{-O(n^{-1/2})},\\ \mathrm{tr}(H^2)& \le D{n}^{2L}{\mu }^2{e}^{O(\sqrt{n})}.\end{array}$$

Cancellation in the trace ratio yields

$$R(f)\ge D{e}^{-C^{\prime }\sqrt{n}}.$$

This is a rank bound close to the full source dimension up to an exponential-in-$\sqrt{n}$ loss. The path-pattern sum and its coefficient estimates remain source theorems, not consequences of the trace inequality alone. (OpenAI, 2026)

🏷️ Comparing ranks and transferring fields

Combine the two bounds and cancel $D>0$:

$$D{e}^{-C^{\prime }\sqrt{n}}\le 2S^{2}D{e}^{C\sqrt{n}}{n}^{-\sqrt{n}/100}.$$

Taking square roots gives

$$S\ge 2^{-1/2}{e}^{-(C+C^{\prime })\sqrt{n}/2}{n}^{\sqrt{n}/200}.$$

For sufficiently large $n$, the factor $n^{\sqrt{n}/400}$ absorbs the exponential loss, because its logarithm is $(\sqrt{n}\log n)/400$. This leaves $S\ge n^{\sqrt{n}/400}$.

The moment proof used a complex inner product, but the matrix of $F_f$ in ordinary monomial bases has integer entries: the polynomial coefficients are integers, and derivatives contribute integer falling factorials. Its rank is the largest order of a nonzero minor. Every such minor is an integer and remains nonzero in every characteristic-zero field. Thus the hard-polynomial rank is the same over all those fields, with the same threshold. Positive characteristic could annihilate a nonzero integer minor, so this transfer does not provide an all-fields lower bound. (OpenAI, 2026)

🏷️ A matching-scale block construction

Take $t=\lceil \sqrt{n}\rceil$ and $r=\lceil n/t\rceil$. Partition the matrix layers into $r$ consecutive blocks of lengths at most $t$. For a block of length $\ell$, each entry is a sum of $n^{\ell -1}$ path monomials. Across its $n^2$ entries, this uses $n^{\ell +1}$ lower product gates and $n^2$ middle sums.

Call the block products $Y^{(1)},\dots ,Y^{(r)}$. Then

$${\mathrm{IMM}}_{n,n}=\sum _{a_1,\dots ,a_{r-1}}\prod _{j=1}^r{Y}_{a_{j-1},a_j}^{(j)},$$

where $a_0=a_r=1$ and the other indices range over $[n]$. The block entries are shared across all top products. Insert an identity bottom sum for each variable to obtain five computational layers. Counting leaves as well gives

$$\begin{array}{c}2n^3+r{n}^2+r{n}^{t+1}+n^{r-1}+1\\ \le n^{\sqrt{n}+4}.\end{array}$$

The two competing costs are internal block paths and choices of block endpoints. Balancing block length and block count near $\sqrt{n}$ explains the upper exponent. Every gate is syntactically homogeneous, and the construction works over every field. (OpenAI, 2026)

🏷️ Key steps and proof outlines

Rank loss comes from an intermediate dimension

The circuit-side argument in “The rank of a homogeneous depth-five circuit” does not bound the support of bottom linear forms. It factors the differentiation–multiplication operator through smaller homogeneous spaces. Suppose a homogeneous product has factor degrees $e_1,\dots ,e_r$ summing to $n$, and let $\lambda =k/n$ be the selected fraction of differentiation layers. A choice of bidegrees $i_j,e_j-i_j$ has discrepancies ${\delta }_j=i_j-\lambda e_j$ with ${\sum }_j{\delta }_j=0$.

The differential and multiplication factors commute, so apply the factors with positive discrepancy first. If their total bidegree is $(I,J)$, the intermediate space has dimension $h(v,a-I)h(u,b+J)$, where $h(v,a)=\left(\genfrac{}{}{0ex}{}{v+a-1}{a}\right)$ counts degree-$a$ monomials in $v$ variables. Writing $D=h(v,a)h(u,b)$, the source’s parameter choice bounds the ratio by $2{\alpha }^{I-\rho J}$. Here $\rho =\lambda /(1-\lambda )$ and $\alpha \in (0,1)$ is the differentiation dimension ratio parameter. Since

$$I-\rho J=\frac{1+\rho }{2}\sum _j|i_j-\lambda e_j|,$$

defining $q={\alpha }^{(1+\rho )/2}$ gives a penalty for every degree mismatch. Summing ranks and dropping the constraint $\sum i_j=k$ yields

$$R\left(\prod _j{Q}_j\right)\le 2D\prod _j{H}_{e_j},H_e=\sum _{i=0}^e{q}^{|i-\lambda e|}.$$

The factorization through an intermediate space is the source of the penalty; the later sum over bidegrees is merely rank subadditivity. (OpenAI, 2026)

Small even degrees require a summed error estimate

Put $s=n-2k$, so $\lambda =1/2-s/(2n)$, and set $t_0=n/(4s)$. For $e<t_0$, the distance of $\lambda e$ to the nearest integer is $se/(2n)$ for even $e$ and $1/2-se/(2n)$ for odd $e$. Thus odd degrees have a definite mismatch, while the mismatch for small even degrees can be tiny.

Bounding every $H_e$ by five would introduce a disastrous factor $5^r$. Instead the source isolates the nearest integer and bounds the other terms by a geometric series. For even $e<t_0$ this gives

$$H_e\le q^{se/(2n)}\exp \left(4q^{1-se/n}\right).$$

The corrections must be summed using the total degree budget. For real $z\in [2,t_0]$, the function $f(z)=q^{1-sz/n}/z$ has convex logarithm, because $(\log f{)}^{\prime \prime }=1/z^2>0$. It is bounded by its larger endpoint value. The source’s $q\asymp n^{-1/2}$ and $s\asymp \sqrt{n}$ imply $f(2)=O(n^{-1/2})$ and $f(t_0)=O(n^{-7/8})$. Consequently

$$\sum _{j:e_j<t_0,e_j\text{ even}}{q}^{1-s{e}_j/n}\le \frac{C}{\sqrt{n}}\sum _j{e}_j\le C\sqrt{n}.$$

All the even-degree errors therefore cost only $\exp (O(\sqrt{n}))$, which the eventual power of $n$ can absorb.

Expanding one gate occurrence is enough

If every factor degree is below $t_0$, the degree distances sum to at least $s/2$, supplying a factor $q^{s/4}$ after the odd/even estimates. Otherwise choose one factor occurrence of degree $e\ge t_0$ and expand its middle sum. There are at most $S$ summands, each a product of $e$ linear forms. Those exposed degree-one factors alone supply a substantial mismatch penalty. At most $n/t_0=4s$ other large factors remain, so their coarse bounds cost only $5^{4s}$.

Only one occurrence is expanded, even if the same gate is reused in the product. Repeated multiplicative occurrences still have total degree $n$; repeated additive wires can be merged by adding their coefficients. Thus gate sharing does not invalidate the estimate or require charging every wire. Summing over at most $S$ top products introduces the second factor $S$, giving the stated $2S^{2}D\exp (O(\sqrt{n}))n^{-\sqrt{n}/100}$ bound.

The hard-polynomial moment calculation then supplies $R(\mathrm{IMM})\ge D\exp (-O(\sqrt{n}))$. Cancelling the same $D$ compares two bounds on one operator; it does not compare unrelated ranks. Integer minors transfer that hard-polynomial rank to every characteristic-zero field, while the circuit estimate already holds over an arbitrary field. This identifies exactly where characteristic zero enters the final lower bound.

🏷️ Reading connections

Matrix multiplication exponents concerns unrestricted algorithms and tensor methods, whereas this family fixes five homogeneous layers. Exact Fourier complexity uses a different scalar-gate convention; arithmetic operation counts should be compared only after accounting for those model differences.

🏷️ Manuscripts and verification scope

• Homogeneous depth-five lower bounds for iterated matrix multiplication — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. It selects the characteristic-zero lower bound with an absolute threshold and the all-fields upper bound, including unrestricted bottom support and shared gates. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. Homogeneous depth-five lower bounds for iterated matrix multiplication.