A cubic permanent–determinant lower bound

What OpenAI claims

Proves an Ω(n³) lower bound for the border determinantal complexity of the n× n permanent over ℂ. Even coefficientwise limits of determinants of affine-linear matrices require matrix size at least cn³, for an absolute c > 0 and all sufficiently large n; the same bound therefore holds for exact representations. (Lean)

Paper

1. A cubic lower bound for border determinantal complexity of the permanent

   24 September 2026 · Preprint, not peer reviewed · PDF

   We prove that the complex border determinantal complexity of the m× m permanent is Ω(m³), 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.

Status

Preprint. The paper has not been independently reviewed. Treat the result as OpenAI's claim until other mathematicians have checked it. If a video exists, it illustrates the statement; it is not the proof.