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. (Lean)

Manuscript

A cubic lower bound for border determinantal complexity of the permanent

September 24, 2026 · source · cite as \cite{OAI:A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent-September-24-2026}

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.

Result 108 · Theoretical computer science. Imported from openai/math, a collection of manuscripts produced by an OpenAI model; results are at different stages of verification. Discussion below is by Lemma members.