Browse › Theoretical computer science › 108 A cubic permanent–determinant lower bound
A cubic lower bound for border determinantal complexity of the permanent
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
We prove that the complex border determinantal complexity of the $m\times m$ permanent is $\Omega(m^3)$, allowing arbitrary affine-linear determinant representations and coefficientwise limits. It also gives cubic lower bounds for exact determinantal complexity and for the numbers of vertices and edges in affine-linear algebraic branching programs, including coefficientwise limits with a fixed vertex or edge budget.
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.
Follow-up works
- Karthik Sheshadri, Conormal Lower Bounds for Determinantal Complexity: Fermat Slices, Tight Bounds, and a Ceiling (arXiv:2606.15970v2, revised 14 Oct 2026). The October revision cites this paper as [OAI26] and proves an $O(n^3)$ ceiling for polar/conormal (characteristic-cycle and kernel-system) arguments on the $n\times n$ permanent, stating that "the cubic lower bound of [OAI26] shows that this order is attained for the permanent".
- Jizhou Guo, An n^2 log log n Lower Bound for Permanent Circuits with Valid Division (arXiv:2609.29568v2, 8 Oct 2026). Version 2 cites this manuscript (release commit adc7f12) and uses twelve machine-checked declarations from its Lean development, deriving one weaker bound by "assuming Proposition 7.3 of that manuscript".
- Ying Xie, Smooth slices and superquadratic border determinantal complexity of the permanent (Zenodo, doi:10.5281/zenodo.23108131, 2 Oct 2026). This preprint claims an Ω(n^2 log n) border determinantal complexity bound for the permanent, combining "the matching-polynomial restrictions of OpenAI with Sheshadri's determinantal kernel incidence".
Formalization
- OpenAI math release, A cubic permanent–determinant lower bound: Lean formalization scope (release repository mirror, 6 Oct 2026). The scope note reports formalizations of the exact and border bounds $n\ge m^3/(5529600e)$ for $m\ge1408$ and the supporting smooth-initial-form bound (r−1)(d−1)/(4e), excluding the algebraic-branching-program consequences. [family-level]
- OpenAI math release, PermanentCubic.lean comparator statement (openai/math, commit adc7f12). Statement-only comparator file (proof left as
sorry) forpermanent_cubic_lower_bounds, with border and exact versions of the bound m^3/(5529600e) ≤ n.
Related prior literature mentioned by others
- OpenAI, Ten Advances in Mathematics and Theoretical Computer Science, Chapter 5 "Arithmetic circuit complexity" (OpenAI PDF, updated 6 Aug 2026). Guo (arXiv:2609.29568) cites this chapter alongside the present manuscript as the source of the permanent "block construction and critical-locus estimate". [AI-generated per source]
- Joseph M. Landsberg, Laurent Manivel and Nicolas Ressayre, Hypersurfaces with degenerate duals and the Geometric Complexity Theory Program (Commentarii Mathematici Helvetici 88(2), 2013). Sheshadri's October revision identifies this quadratic border determinantal lower bound as the predecessor to the paper's cubic bound.
Possibly relevant literature (found by the agent, not checked)
- Karthik Sheshadri, A short proof of a quadratic lower bound on the border determinantal complexity of x_1^n+⋯+x_n^n over ℂ: A simple human exposition (arXiv:2606.11090v2, revised 18 Oct 2026). Proves a border bound of (n−1)^2/(4e) for the power sum via kernel equations and multihomogeneous Bézout counting, comparable to the paper's smooth-form border bound (r−1)(d−1)/(4e); not in the paper's bibliography.
- Prerona Chatterjee, Mrinal Kumar, Adrian She, Ben Lee Volk, A Quadratic Lower Bound for Algebraic Branching Programs and Formulas (arXiv:1911.11793, 2019/2020). Gives an earlier Ω(n^2) vertex lower bound for general ABPs, relevant to the paper's Ω(m^3) ABP consequence; not in the paper's bibliography.
Digests and expositions
- Latent Seminar, Cubic lower bounds for permanent determinant representations (2026-10-07). Exposition of the smooth-form obstruction, coefficient-selection construction and persistence under border limits; it states that it does not independently verify the proof or rebuild the Lean development. [family-level]
News and blogs
- Azmat, Permanent vs Determinant Problem: How OpenAI's Proof Broke the Quadratic Barrier (BinaryVerse AI, 2026-10-16). Article outlining the characteristic-two geometry and polar-intersection argument, distinguishing the determinant-size bound from running-time bounds and superpolynomial separation.
Elsewhere
- VibeMathed: Problem record
- Emergent Mind: family 108
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent-September-24-2026,
author = {{OpenAI}},
title = {{A cubic lower bound for border determinantal complexity of the permanent}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent-September-24-2026/A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent-September-24-2026.pdf}{OAI:A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent-September-24-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/108.md. The Lean statements have not been checked by people against the paper's claims.
Family 108: A cubic permanent–determinant lower bound
Proves an $\Omega(n^3)$ lower bound for the border determinantal complexity of the $n\times n$ permanent over ℂ. Even coefficientwise limits of determinants of affine-linear matrices require matrix size at least $cn^3$, for an absolute c > 0 and all sufficiently large n; the same bound therefore holds for exact representations.
This is the only paper in this family.