A cubic permanent–determinant lower bound

1 · The essentials

The permanent and the determinant are two mathematical rules for turning a square table of numbers into a single expression. This result asks how large a determinant must be to express the permanent of an $n \times n$ table. The allowed construction uses a larger table whose entries are constants plus weighted sums of the original entries. The main result says that, for sufficiently large $n$ , the larger table must have at least $c n^{3}$ rows for some fixed positive constant $c$ . This requirement still applies if a sequence of such constructions only approaches the permanent, with each coefficient approaching the desired value. It therefore also applies when the construction gives the permanent exactly. The main result has a Lean formalization, although the supplied material does not specify its detailed coverage.

A picture to help (an imperfect image, not to be taken literally)

As an imperfect image, imagine trying to reproduce a particular recipe using a restricted kind of kitchen machine. The result says that the machine must be large enough even if you allow successive versions of its output to approach the recipe rather than match it exactly.

Why it matters

The bound rules out small determinant representations under both exact equality and the specified form of approximation. The manuscript also reports cubic lower bounds for two size measures of affine-linear algebraic branching programs: their numbers of vertices and edges. Thus the reported obstruction concerns more than one way of representing the permanent.

2 · Going further

The precise problem concerns the permanent of an $n \times n$ matrix over $C$ . A determinant representation uses an $r \times r$ matrix whose entries are arbitrary affine-linear expressions in the original variables. Border determinantal complexity allows coefficientwise limits of these determinant expressions, rather than requiring one expression to equal the permanent exactly. The main result is the lower bound $r \geq c n^{3}$ for an absolute constant $c > 0$ and all sufficiently large $n$ .

The distinction between exact and border representations is essential: allowing limits enlarges the permitted class of representations. A lower bound that survives this enlargement also applies to exact representations. The supplied abstract states the cubic bound but does not describe the argument's main construction or technique, so an account of that mechanism cannot be given from this source.

The same manuscript reports cubic lower bounds for the numbers of vertices and edges in affine-linear algebraic branching programs, including coefficientwise limits with a fixed vertex or edge budget. Only one manuscript is supplied; no companion manuscripts or relationships between them are described. The main result has a Lean formalization, but the supplied material does not establish whether that formalization also covers all of these additional claims.

Useful notions

Square matrices and their size
Permanents and determinants
Polynomials and coefficients
Affine-linear expressions
Limits over the complex numbers

What was known before / what is new

Before

The source frames the question in terms of exact determinant representations and the more permissive setting of coefficientwise limits. It does not give earlier lower bounds, historical milestones, or a prior best result.

New

The reported main result is an $Ω (n^{3})$ lower bound for the complex border determinantal complexity of the permanent, allowing arbitrary affine-linear determinant representations. The exact determinantal lower bound follows as well. The manuscript also reports cubic vertex and edge lower bounds for affine-linear algebraic branching programs, including the stated fixed-budget limits.

Limits and assumptions

The result is over the complex numbers and concerns determinants of matrices with affine-linear entries. The inequality uses an unspecified absolute constant c > 0 and applies for all sufficiently large n; no numerical constant or threshold is supplied. Approximation means coefficientwise convergence, and the branching-program limit claims retain a fixed vertex or edge budget. The main result has a Lean formalization, but its detailed scope is not specified here, so formal verification of every additional claim should not be assumed. The source does not state whether the cubic bound is optimal or identify further open questions.

Mini glossary

Affine-linear expression: An expression consisting of a constant plus a weighted sum of the input variables.
Exact determinantal complexity: The smallest matrix size needed to express a polynomial exactly as a determinant with affine-linear entries.
Border determinantal complexity: The smallest matrix-size budget allowing a polynomial to be obtained as a coefficientwise limit of determinants with affine-linear entries.
Coefficientwise limit: A limit in which each polynomial coefficient converges to the corresponding coefficient of the target polynomial.
Cubic lower bound: A requirement that a size measure be at least a fixed positive constant times the cube of the input dimension, once that dimension is sufficiently large.

Keywords : Permanent · Border determinantal complexity · Algebraic branching programs

AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.

3 · Technical details and sources

Claim made in the manuscript (source text)

Proves an $Ω (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 $c n^{3}$ , for an absolute c > 0 and all sufficiently large n; the same bound therefore holds for exact representations.

Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.

Scope of the Lean formalization (source text)

…

lean/docs/108.md

Manuscripts in this family

★

A cubic lower bound for border determinantal complexity of the permanent

24/09/2026

To be verified

We prove that the complex border determinantal complexity of the $m \times m$ permanent is $Ω (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.

PDF GitHub folder