Homogeneous depth-five lower bounds for iterated matrix multiplication
From OpenAI Aftermath
Homogeneous depth-five lower bounds for iterated matrix multiplication concern the number of gates that a syntactically homogeneous arithmetic circuit with five alternating layers of sums and products needs to compute the (1,1) entry of a product of n independent n × n matrices of variables. Depth reduction sets the square-root scale nO(√n) for such circuits, and Nisan and Wigderson asked for explicit homogeneous polynomials that need superpolynomial size at constant depth, even at depth five. A manuscript dated 25 September 2026 in OpenAI's public mathematics collection (github.com/openai/math) claims the sharp bound nΘ(√n) over every field of characteristic zero, with a Lean formalization. This page summarizes the published claim and lists publicly available follow-up work. Statements are the respective authors' claims; the publication of a paper or a formal proof is not presented here as independent verification.
Background
- As recounted in the introduction of the manuscript:
- Nisan and Wigderson used dimensions of partial-derivative spaces to prove lower bounds for homogeneous depth-three circuits and constant-depth set-multilinear circuits, and asked for an explicit homogeneous polynomial requiring superpolynomial size at constant depth, even at depth five. Depth reduction of Agrawal and Vinay, sharpened by Koiran and Tavenas, converts a polynomial-size circuit for a homogeneous polynomial of degree d into a homogeneous depth-four circuit of size NO(√d), which explains the square-root scale.
- Lower bounds at this scale were previously obtained under additional restrictions: bounded product fan-in or multilinearity (Fournier, Limaye, Malod and Srinivasan), other polynomial families (Kayal, Limaye, Saha and Srinivasan), much wider matrices (Kumar and Saraf), syntactic multilinearity (Kayal, Saha and Tavenas), and, at depth five, a restriction on the support of the bottom linear forms (Bera and Chakrabarti).
The original result
- Claim. The main theorem of Homogeneous depth-five lower bounds for iterated matrix multiplication states that every syntactically homogeneous ΣΠΣΠΣ circuit over the complex numbers computing the (1,1) entry of a product of n independent n × n variable matrices has at least n√n/400 gates for all sufficiently large n; a corollary extends this to every field of characteristic zero with the same absolute threshold. Bottom linear forms may have arbitrary support, and arbitrary finite fan-in, fan-out and gate sharing are allowed. A proposition gives, over every field and for n ≥ 2, a block construction with at most n√n+4 gates, so that the gate complexity over characteristic-zero fields is nΘ(√n).
- Method, as described: a rank measure built from partial differentiation followed by multiplication bounds the contribution of each small circuit, and trace moments computed as sums over paths through the matrix layers show that iterated matrix multiplication has large rank; a field transfer extends the bound from the complex numbers to every field of characteristic zero.
- Source (openai/math repository, commit
7ef5c0c): Homogeneous depth-five lower bounds for iterated matrix multiplication, dated 25 September 2026. - Formalization, as described by the repository. The scope note lean/docs/135.md states that the formalization proves the n√n/400 lower bound over every field of characteristic zero, with a threshold independent of the field, and the n√n+4 upper bound over every field for n ≥ 2. The Comparator statement is
DepthFive.lean.
Public follow-up work
| Date | Work | Relation | Public claim | Public status (checked 30 October 2026) |
|---|---|---|---|---|
| 2026-10-07 | Homogeneous depth-five matrix products, an article of the Latent Seminar blog at lowrank.github.io | Reading (exposition) | Explains iterated matrix multiplication as a polynomial, the lower and upper bounds, differentiation and multiplication as a rank measure, bottlenecks in a small circuit, large rank from path moments, the comparison of ranks and the transfer between fields, and the block construction at the matching scale, with proof outlines. | Blog article; it states that its review covers statements, introductions and selected proof mechanisms and is not an independent verification of the complete proofs. |
| 2026-10-08 | MathVet (GitHub; review of openai/math, tables at repository commit 94c6630, 28 October 2026) |
Review (fidelity of the formal statements) | Rates this family "full" and records a sandboxed Comparator pass for DepthFive on 8 October 2026. |
MathVet states that it does not claim any theorem false and reports what was machine-checked as stated. |
| 2026-10-10 | cert-machine, openai/math lane K, run 38051470892 | Verification (two kernels) | Records that Lean's default kernel and the nanoda kernel accept the DepthFive solution, in 564 s. The project reports two-kernel certification of 398 of 416 challenges of the collection. |
Repository. |
| 2026-10-10 to 2026-10-14 | con-leche development journal (task #348) | Verification (second kernel) | In its run over all Comparator challenges of the collection at commit fd4aeeb, the journal's table of exceptions does not list DepthFive, so it was accepted by con-leche and by Lean's official kernel. |
Development journal. |
| 2026-10-13 | Depth-five circuits for iterated matrix multiplication, a course on Open Mathematics Courses (kokunoyumeto/open-math-courses-public) | Reading (exposition) | Five lessons with a complete proof: iterated matrix multiplication and depth-five circuits, a rank measure from differentiation and multiplication, the rank of a depth-five circuit, trace moments and paths, and the sum over type words that gives the lower bound. | The course states that it was written and self-checked by Claude Opus 5.5 (Anthropic) and that independent review is not complete. |
| 2026-10-16 | J. Jardine, Lattice24, referee review rank_541 in JJardine919/openai-math-audit (archived at Zenodo 10.5281/zenodo.23422995) | Review (AI-assisted audit) | Reports no gap and no minor notes. The reviewer read every section line by line and checked by hand the parameter lemma, the product-rank lemma and its binomial bounds, the low- and high-degree cases of the circuit bound, the moment identities, the four-path trace formula and the local polynomial table. | Part of an audit of the collection's manuscripts that the audit describes as complete. The reviews are published under CC BY 4.0. |
| 2026-10-16 | AI Proved What?, episode 135 Depth five, sharply?, remade version of 26 October 2026 | Reading (exposition) | Video explainer of the claim and its place among earlier restricted lower bounds. The episode states that no lower bound in positive characteristic or for circuits that are not homogeneous is claimed, that the constants are far apart and the threshold is not given, and that the lower bound exceeds the roughly n3 variables a circuit must read only once n passes about 1.4 million. | Web page and video; the site states that its scripts and animations are produced with AI assistance and that the narration is an AI-generated voice. Status record last checked 27 October 2026: posted as a preprint: OpenAI, 22 pages, dated September 25, 2026; under expert review: not yet; peer reviewed: not yet; checked in Lean: the lower bound over every characteristic-zero field and the construction, not run by the site. The page states that the formalization has 164 files and 20,323 lines and that it has seen no expert review. |
Notes
- The background summarizes the manuscript's own account of earlier work.
- The list covers follow-ups found in public sources up to the date above; it is not a priority or completeness claim.
