A cubic lower bound for the border determinantal complexity of the permanent (beyond the quadratic Mignon-Ressayre barrier)

The determinantal complexity $\mathrm{dc}(f)$ of a polynomial $f$ is the least $n$ with $f=\det(A_0+\sum_j x_jA_j)$ for $n\times n$ complex matrices, and the border determinantal complexity $\mathrm{bdc}(f)$ is the least $n$ such that $f$ is a coefficientwise limit of such determinants. Valiant's algebraic completeness theory (1979) makes the growth of $\mathrm{dc}(\mathrm{per}_m)$ the algebraic analogue of P versus NP: it is conjectured to be superpolynomial, and the Mulmuley-Sohoni geometric complexity program targets $\mathrm{bdc}$ . The best lower bounds were quadratic: $\mathrm{dc}(\mathrm{per}_m)\ge m^2/2$ (Mignon-Ressayre 2004) and $\mathrm{bdc}(\mathrm{per}_m)\ge m^2/2$ (Landsberg-Manivel-Ressayre 2010). How fast must $\mathrm{bdc}(\mathrm{per}_m)$ grow; in particular, can the quadratic lower bound be improved?

Result: Proved(see note)
Status: Partial result
AI contribution: AI-discovered
Method: Argument
Field: Algebraic complexity; permanent versus determinant, geometric complexity theory
Posed by: Leslie Valiant (permanent versus determinant, algebraic completeness); border version from the Mulmuley-Sohoni geometric complexity program
Year posed: 1979
Years open: 47y
Solved: 2026-09-24
Model: Unreleased internal OpenAI model
Vendor: OpenAI
Collaborators: —
Verification: Lean-checked, statement unaudited
Publication: Announced
Collection: OpenAI math release (October 2026), version adc7f12
Significance: 42 / 100
Disclosed cost: —
Wikipedia: No dedicated article

What was actually shown

Theorem 1.1: $\mathrm{bdc}(\mathrm{per}_m)\ge cm^3$ for $m\ge m_0$ , with $c=1/(5529600e)$ and $m_0=1408$ , over $\mathbb C$ with arbitrary affine-linear entries and coefficientwise limits at fixed size; the same bound holds for $\mathrm{dc}$ , and affine-linear algebraic branching programs for $\mathrm{per}_m$ need $\Omega(m^3)$ vertices and edges (also in the border sense at fixed budget). The route is a smooth-hypersurface bound $(r-1)(d-1)/(4e)$ for forms of degree $r$ in $d$ variables, applied to a coefficient polynomial extracted from a permanent. It remains a fixed polynomial bound: superpolynomial $\mathrm{dc}$ or $\mathrm{bdc}$ for the permanent, and VP versus VNP, stay open.

What the AI did

The release README says the vast majority of results were obtained with one fixed procedure using an unreleased internal OpenAI model, on average about three hours of ChatGPT Pro thinking compute per result, and that some outputs build on earlier results produced by the models. This result is not among the README's exceptions (the Hodge conjecture for CM abelian varieties and the Re(s) > 11/12 zero-free region, whose write-up was human edited). The manuscripts are authored 'OpenAI' and name no human author. The family is a single manuscript (September 24, 2026), with a Lean formalization of the two headline bounds.

Verification

No independent mathematician has checked this yet. Checked here: Theorem 1.1 ( $\mathrm{bdc}(\mathrm{per}_m)\ge m^3/(5529600e)$ for $m\ge1408$ ) was read against the permanent-determinant question. Lean: the comparator challenge lean/ComparatorChallenges/PermanentCubic.json exists with solution module OAI.Algebra.Determinantal.Main present at the pinned commit; this challenge is not listed in lean/formalization.yaml. Its statement OAI.PermanentBorder.permanent_cubic_lower_bounds was read here: for $m\ge1408$ , any $n$ with a sequence of affine $n\times n$ pencils whose determinant coefficients converge to those of $\mathrm{per}_m$ (and any exact representation) satisfies $m^3/(5529600e)\le n$ . This is the headline claim. Not rebuilt here. The paper's branching-program consequences are outside the formal statement.

A cubic lower bound for the border determinantal complexity of the permanent (beyond the quadratic Mignon-Ressayre barrier)

What was actually shown

What the AI did

Verification

Sources

Discussion