AI Proved What?

Episode 108, October 2026

Cubic at last?

A claimed proof that the permanent needs determinants of size of order m³, even approximately

Covers result 108 in OpenAI’s catalog: its one paper. See its connections to other results and the work it cites.

Play Episode 108: Cubic at last? A log-log chart where a cubic lower bound overtakes a quadratic one, with m² → m³.

6:00. English captions available. The video loads from YouTube when you press play.

Chapters

  1. 0:00Permanent versus determinant
  2. 1:41The claim
  3. 2:54How the proof goes
  4. 5:23Where it stands

The claims, in plain words

The determinant and the permanent of a square matrix are sums of the same products, one entry from each row and each column; the determinant attaches signs, the permanent does not. Determinants are computed quickly by elimination, while computing permanents exactly is #P-hard. Valiant’s algebraic version of P versus NP asks how large a determinant must be to express the m × m permanent; in the standard modern form, every entry of the determinant’s matrix may be any affine-linear form in the permanent’s variables. The smallest such size is the determinantal complexity of the permanent, and Valiant’s conjecture says it grows faster than any polynomial in m.

Grenet showed that size 2m − 1 suffices. Lower bounds were linear in m until Mignon and Ressayre proved m²/2 in 2004 by comparing Hessians: at a singular matrix, the determinant’s Hessian has rank at most twice the matrix size, while the permanent vanishes at a point where its Hessian has full rank m², and substituting affine-linear forms cannot raise a Hessian’s rank. Landsberg, Manivel and Ressayre proved the same m²/2 for border determinantal complexity, where determinants need only approach the permanent as a limit, the setting of geometric complexity theory.

Result 108 is one OpenAI preprint (35 pages) dated September 24, 2026. It claims that for m ≥ 1408, every matrix of complex affine-linear forms whose determinant equals the m × m permanent, or tends to it coefficient by coefficient, has size at least m³/(5,529,600 e). The same bound follows for exact representations, and the paper derives cubic lower bounds for algebraic branching programs. The constant is not optimized: the cubic bound beats m²/2 only beyond m ≈ 7.5 million. But the exponent rises from 2 to 3.

What it doesn’t claim

It does not prove Valiant’s conjecture: a superpolynomial lower bound, which would separate the permanent from the determinant in Valiant’s sense, remains open. The bound is over the complex numbers, and it is a polynomial improvement, from m² to m³, with a very small constant.

Where it stands

Posted as a preprint
OpenAI, 35 pages, dated September 24, 2026
Peer reviewed
Not yet
Checked in Lean
OpenAI published a Lean proof of the exact and border bounds and the smooth-form bound; we have not run the check

Last checked October 19, 2026. The preprint has not been revised. OpenAI published a Lean formalization in its Determinantal folder, matched against the cubic bounds for exact and border representations and the general bound for smooth initial forms: 51 files and 20,739 lines in the theorems’ import closure, nothing outside Mathlib, with no unproved steps that we could find. The algebraic-branching-program consequences are not part of it. By our reading, the polar half follows the paper, but the characteristic-two step uses its own weaker dimension bound in place of the Severi-type theorem, with different intermediate constants that reach the same final bound. We have not run the check. The paper is not among those OSVerify reviewed, and we have seen no expert review.

How the proof goes

  1. Smooth forms need large determinants. Let G be a homogeneous polynomial of degree r in d variables whose zero set is smooth. Then d − 2 general first polars, derivatives in fixed directions, meet the hypersurface G = 0 in exactly r(r − 1)d−2 simple points. These persist for one nearby determinant of size n; lifting them to the left and right kernels of its matrix bounds their number by 2d−2·C(2n − 1, d − 1) ≤ (4en/(d − 1))d−1. Hence n ≥ (r − 1)(d − 1)/(4e), for exact and border representations alike.
  2. A coefficient inside the permanent. Add s times the identity and t times a diagonal matrix D of parameters to a k × k matrix of variables X, and take the coefficient of sqtq in the permanent: GD(X), homogeneous of degree k − 2q in k² variables. Two counting gates and a cancellation gadget realize it, up to a nonzero constant, as an affine restriction of the permanent of size 11k − 2q.
  3. Smoothness from curves in characteristic two. In characteristic 2, the permanent equals the determinant, and each X defines the plane curve det(sI + tD + uX) = 0. If every derivative of GD vanishes at X, the adjugate cuts out a subscheme of length at least C(q + 2, 2) on that curve, which forces a large normalization defect. A Severi-type dimension bound of Christ, He and Tyomkin shows such curves are rare, and a count of matrices per curve shows such matrices are rare too. Specialization carries this to the complex numbers, where a general linear slice of dimension ⌊k²/100⌋ gives a smooth form.
  4. The cubic bound. With q = ⌊(k − 1)/3⌋, the degree minus one is at least k/4 and the number of variables minus one at least k²/200, so the smooth-form bound gives at least k³/(3200e). Taking k = ⌊m/11⌋ ≥ m/12, the permanent of size m ≥ 11k − 2q inherits it: m³/(12³·3200e) = m³/(5,529,600 e).

The numbers in the video

  • Permanent and determinant on 200 random integer matrices of sizes 3 to 5: they differed on 195 and agreed modulo 2 on all 200. For the matrix with rows (1, 2, 0), (3, 1, 4), (0, 5, 2), the permanent is 34 and the determinant −30.
  • The determinant’s Hessian at a random singular matrix had rank 6, 8 and 10 for sizes 3, 4 and 5; the permanent vanishes at the all-ones matrix with corner entry 1 − m, where its Hessian has rank 9 and 16 for m = 3 and 4.
  • GD came out homogeneous of degree k − 2q for (k, q) = (3, 1), (4, 1), (5, 1) and (5, 2).
  • c = 1/(5,529,600 e) ≈ 6.65 × 10−8; c m³ overtakes m²/2 at m ≈ 7,515,506.
  • For m = 1408 and k = 128: q = 42, degree r = 44, slice dimension d = 163; the construction fits in size 11k − 2q = 1324. The polar count then needs n ≥ 699, while the simple bound (r − 1)(d − 1)/(4e) gives about 641.

Read the source

The paper

OpenAI groups related papers into one result; this one has a single paper.

Transcript

Read the full script

0:00Permanent versus determinant

The determinant and the permanent of a square matrix are built from the same terms: products of one entry from each row and each column. The determinant gives each term a sign; the permanent simply adds them up. That one difference matters. Determinants are computed quickly by elimination, while computing permanents exactly is hard. Valiant’s algebraic version of the question asks how large a determinant must be to express the m by m permanent; in the standard modern form, every entry of its matrix may be any affine-linear form in the permanent’s variables. That size is the determinantal complexity. Valiant’s conjecture, an algebraic cousin of P versus NP, says it grows faster than any polynomial in m. In our check, the two differed on most random integer matrices, and always agreed modulo two. The known bounds are far apart. Grenet showed that a determinant of size 2^m − 1, suffices. Lower bounds were linear in m until Mignon and Ressayre proved m²/2 in 2004, by comparing Hessians: at a singular matrix the determinant’s Hessian has rank at most twice the matrix size, while the permanent has a zero where its Hessian has full rank m², and substituting affine-linear forms cannot raise a Hessian’s rank. Landsberg, Manivel and Ressayre proved the same m²/2 in the border version, where determinants need only approach the permanent as a limit, the setting of geometric complexity theory. In our check, the determinant’s Hessian ranks were 6, 8 and 10 for sizes 3, 4 and 5, and the permanent’s were 9 and 16.

1:41The claim

Result 108 is one OpenAI preprint, 35 pages, dated September 24. It claims that the border determinantal complexity of the m by m permanent is at least a constant times m³. For m at least 1408, every determinant of complex affine-linear forms that equals the permanent, or approaches it coefficient by coefficient, has size at least m³/(5,529,600 e). The paper also gives cubic bounds for exact representations and for algebraic branching programs. The constant is tiny, and the paper says it is not optimized: the cubic bound overtakes m²/2 only when m exceeds about 7.5 million. But the exponent rises from two to three, after about twenty years at two. A superpolynomial bound, which Valiant’s conjecture predicts, remains open. OpenAI published a Lean formalization of the exact and border bounds, and of the general bound for smooth forms, in about 50 files and 21,000 lines. We have not run the check.

2:54How the proof goes

The proof has two halves. The first is a general bound. Take a homogeneous polynomial of degree r in d variables whose zero set is smooth. Suitable derivatives in fixed directions, d − 2 of them, called first polars, meet the hypersurface in exactly r(r − 1)^(d − 2) simple points. These points persist for one nearby determinant of size n, and lifting them to the left and right kernels of its matrix bounds their number by at most (4en/(d − 1))^(d − 1). So n is at least (r − 1)(d − 1)/(4e). The second half finds such a smooth polynomial inside the permanent, with degree proportional to k and a number of variables proportional to k². The candidate is a coefficient. Add s times the identity and t times a diagonal matrix of parameters to a k by k matrix of variables, take the permanent, and keep the coefficient of s^q t^q. It has degree k − 2q. Two counting gates and a cancellation gadget realize it, up to a nonzero constant, as an affine restriction of a permanent of size 11k − 2q. In our check, this coefficient came out homogeneous of the predicted degree in every small case. Smoothness comes from geometry in characteristic two, where the permanent equals the determinant. Each matrix X defines a plane curve: the zero set of det(sI + tD + uX). If every derivative of the coefficient vanishes at X, the adjugate cuts out a long subscheme on that curve, and the curve must have a large normalization defect. A Severi-type dimension bound of Christ, He and Tyomkin shows that such curves are rare, and a count of matrices per curve shows such matrices are rare too. Specialization carries this to the complex numbers, and a general linear slice of dimension about k²/100 gives a smooth form. Putting the halves together: the degree minus one is at least k/4, and the number of variables minus one at least k²/200, so the smooth-form bound gives at least k³/(3200e). The permanent of size m inherits it whenever m is at least 11k − 2q; taking k as ⌊m/11⌋, gives the cubic bound.

5:23Where it stands

The preprint is not peer reviewed and has not been revised. The Lean formalization covers the exact and border bounds and the smooth-form bound, but not the branching-program consequences; we have not run it. It is not among the papers OSVerify reviewed, and we have seen no expert review. If it holds, the permanent needs determinants of size at least a constant times m³, even approximately: a polynomial step, not yet the superpolynomial separation that Valiant’s conjecture predicts.

Spot a mistake?

This episode simplifies on purpose, but it shouldn’t be wrong. If something is, open an issue on GitHub or leave a comment on YouTube. Corrections are noted here with a date.