Browse › Theoretical computer science › 135 Homogeneous depth-five lower bounds for iterated matrix multiplication
Homogeneous depth-five lower bounds for iterated matrix multiplication
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
Let $\mathop{\mathrm{IMM}}\nolimits _{n,n}$ be the $(1,1)$ entry of a product of n independent $n\times n$ matrices of variables. Over every field of characteristic zero, every syntactically homogeneous $\Sigma\Pi\Sigma\Pi\Sigma$ circuit computing $\mathop{\mathrm{IMM}}\nolimits _{n,n}$ has at least $n^{\sqrt n/400}$ gates for all sufficiently large n, with an absolute threshold independent of the field. Bottom linear forms may have arbitrary support, and arbitrary finite fan-in, fan-out, and gate sharing are allowed. Over every field, a block expansion gives such circuits with at most $n^{\sqrt n+4}$ gates for n ≥ 2. Thus the gate complexity over characteristic-zero fields is $n^{\Theta(\sqrt n)}$.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Formalization
- OpenAI, Homogeneous depth-five lower bounds for iterated matrix multiplication: Lean scope note (OpenAI math release, lean/docs/135.md, 2026-10-06). The scope note says the formalization covers the $n^{\sqrt n/400}$ lower bound over every characteristic-zero field (field-independent threshold, unrestricted bottom support and sharing) and the $n^{\sqrt n+4}$ upper bound over every field, and it points to the comparator statement
lean/ComparatorChallenges/DepthFive.lean.
Possibly relevant literature (found by the agent, not checked)
- Neeraj Kayal and Chandan Saha, Lower Bounds for Depth Three Arithmetic Circuits with Small Bottom Fanin (ECCC TR14-089, 2014; CCC 2015, pp. 158–182). Theorem 1.2 gives characteristic-zero homogeneous depth-five lower bounds of $N^{\Omega(\sqrt d)}$ for Nisan–Wigderson design polynomials with bottom fan-in restricted to $O(N^\mu)$ for fixed $\mu<1$, a restricted-bottom-fan-in precursor to this paper's claim of removing bottom-support restrictions for balanced IMM.
- S. Chillara, N. Limaye and S. Srinivasan, Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications (arXiv:1710.05481, 2017). It gives depth-dependent lower bounds for IMM in small-depth multilinear formulas, complementing the paper's survey of restricted-model IMM lower bounds (Fournier–Limaye–Malod–Srinivasan, Kayal–Saha–Tavenas), which does not list it.
Digests and expositions
- Latent Seminar, Homogeneous depth-five matrix products (2026-10-07). This exposition explains the differentiation–multiplication rank measure, circuit-side dimension estimates, path moments, field transfer, and block upper bound, and states that it does not independently verify the complete proof.
- Open Mathematics Courses, Results on homogeneous depth-five circuits, a rank measure from derivatives and multiplications, and iterated matrix multiplication (undated). This guide links five lessons developing the paper's upper and lower bounds and identifies them as written and self-checked by Claude Opus 5.5, with independent mathematical review incomplete. [AI-generated per source]
Elsewhere
- VibeMathed: Problem record
- Emergent Mind: family 135
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:Homogeneous-depth-five-lower-bounds-for-iterated-matrix-multiplication-September-25-2026,
author = {{OpenAI}},
title = {{Homogeneous depth-five lower bounds for iterated matrix multiplication}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Homogeneous-depth-five-lower-bounds-for-iterated-matrix-multiplication-September-25-2026/Homogeneous-depth-five-lower-bounds-for-iterated-matrix-multiplication-September-25-2026.pdf}{OAI:Homogeneous-depth-five-lower-bounds-for-iterated-matrix-multiplication-September-25-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/135.md. The Lean statements have not been checked by people against the paper's claims.
Family 135: Homogeneous depth-five lower bounds for iterated matrix multiplication
Over every characteristic-zero field, the $(1,1)$ entry of a product of n independent $n\times n$ variable matrices requires $n^{\Theta(\sqrt n)}$ gates in homogeneous depth-five sum–product circuits. This sharp bound allows shared gates and bottom linear forms involving all variables.
This is the only paper in this family.