A cubic permanent–determinant lower bound

← All digests

Family 108 · Theoretical computer science
Importance 4/5 · Provisional editorial rating
Sources consulted 2026-10-09

The determinant and permanent look almost identical on paper: both sum products that choose one entry from every row and column. Removing the determinant’s alternating signs, however, changes the computational problem profoundly. Family 108 studies how large a determinant must become before it can represent a permanent, even through a limiting construction.

1. The question

For a square matrix $X=(x_{ij})$ of order $m$, let $S_m$ denote the permutations of $\{1,\ldots,m\}$. The two polynomials are

$$\operatorname{per}_m(X)=\sum_{\sigma\in S_m}\prod_{i=1}^{m}x_{i,\sigma(i)}, \qquad \det(X)=\sum_{\sigma\in S_m}\operatorname{sgn}(\sigma)\prod_{i=1}^{m}x_{i,\sigma(i)}.$$

The sign in the second expression is either plus or minus one, according to the permutation. For a two-by-two matrix, the permanent is $ad+bc$, whereas the determinant is $ad-bc$.

Although both definitions list factorially many terms, elimination computes determinants efficiently without expanding that list. The corresponding cancellation does not automatically give an efficient permanent algorithm.

One possible route would be to construct a larger matrix whose entries are simple expressions in the original variables and whose determinant equals the permanent. How much larger must that matrix be? The manuscript claims a cubic lower bound on its order, improving the previously established quadratic scale in the unrestricted complex setting.

2. Background and essential definitions

Affine determinant representations

An affine-linear expression has the form $a_0+a_1x_1+\cdots+a_Nx_N$, with constant coefficients. A determinant representation of a polynomial $f$ is an identity

$$f(x_1,\ldots,x_N)=\det\!\left(A_0+\sum_{j=1}^{N}x_jA_j\right),$$

where all the $A_j$ are constant square matrices of one common order $s$. Entries may use arbitrary affine combinations of the variables. There is no restriction to inserting a single variable in each position.

The least possible order $s$ is the determinantal complexity, written $\operatorname{dc}(f)$. It measures the size of this representation, not the number of operations in every conceivable algorithm for $f$.

Why limits make a stronger challenge

A polynomial might fail to have a small exact representation while still being a limit of polynomials that do. For example, a difference quotient of polynomials can converge coefficient by coefficient even when coefficients inside its representation grow without bound.

The border determinantal complexity $\underline{\operatorname{dc}}(f)$ permits such limits of determinants of a fixed order. Coefficientwise convergence means that the coefficient of every monomial converges to the corresponding coefficient of $f$. It is an algebraic limiting notion, not an approximation guarantee for numerical evaluations on a bounded set of inputs.

Since an exact representation is also a constant limiting sequence,

$$\underline{\operatorname{dc}}(f)\le\operatorname{dc}(f).$$

A lower bound on the border quantity therefore applies to exact representations too. It rules out more possible shortcuts.

A geometric dictionary

The zero set of a polynomial is a hypersurface. A point is singular when the relevant first derivatives vanish there; otherwise the hypersurface is smooth locally. For a homogeneous polynomial, which has terms all of the same total degree, one can study its projective zero set by treating nonzero scalar multiples of coordinates as the same point.

These ideas allow the paper to compare algebraic expressions through their geometry. The reader need not know algebraic geometry to understand the goal: extract a polynomial whose zero set is too geometrically complicated to come from a small determinant.

3. Development history and previous partial results

Valiant’s 1979 work connected the permanent–determinant problem with algebraic complexity. One of his constructions converts a polynomial computed by a small arithmetic formula into a determinant of a correspondingly small matrix. His completeness results explain why the permanent represents a broad family of algebraic counting problems. The original reference is Completeness classes in algebra, cited in M1.

Early unrestricted lower bounds grew only linearly with the permanent’s order. A major change came from Mignon and Ressayre in 2004, who proved the exact characteristic-zero bound $\operatorname{dc}(\operatorname{per}_m)\ge m^2/2$.

Their method compares Hessians: matrices of second derivatives. At a suitable zero, the permanent has a Hessian of rank $m^2$, while the Hessian structure of a determinant of order $s$ constrains that rank by $2s$. A local geometric invariant thus forces a global representation-size bound.

The border problem requires care because a property of one exact representation need not survive an arbitrary limiting sequence. Landsberg, Manivel, and Ressayre established a quadratic complex border bound through the geometry of hypersurfaces and their duals. Their work belongs to the broader geometric complexity theory program of Mulmuley and Sohoni.

Much stronger bounds were known when representations had to preserve specified symmetries. Landsberg and Ressayre’s symmetry results include exponential lower bounds in those restricted models. Such assumptions cannot simply be removed: an efficient representation might break the visible symmetries of the polynomial it computes.

The new manuscript addresses arbitrary affine determinant representations and their limits. Its claimed advance is therefore a change from quadratic to cubic growth in the unrestricted border model, rather than an improvement on every previously studied restricted model.

4. What the new manuscripts claim

M1 states that there are absolute constants $c>0$ and $m_0$ such that

$$\underline{\operatorname{dc}}(\operatorname{per}_m)\ge c m^3 \qquad\text{for every }m\ge m_0.$$

Everything here is over the complex numbers. The paper supplies the explicit choices

$$c=\frac{1}{5\,529\,600e},\qquad m_0=1408,$$

where $e$ is the base of the natural logarithm. These constants are not optimized; the main statement concerns the power three.

The same cubic bound consequently holds for exact determinantal complexity. The paper also derives cubic lower bounds on the numbers of vertices and edges of affine-linear algebraic branching programs computing the permanent.

Such a branching program is a directed graph without directed cycles, with designated starting and ending vertices. Each edge carries an affine-linear expression. The program sums the products of edge labels over all directed paths between the designated vertices. The bound also covers coefficientwise limits when the relevant vertex or edge budget is fixed, even if the graph changes along the sequence.

5. Why the advance matters

Importance: 4/5, provisional. Unrestricted algebraic lower bounds are difficult, and a larger exponent in the border model addresses an obstacle that survives approximation by small algebraic representations.

The permanent connects enumeration, algebra, and complexity. On a zero–one matrix describing a bipartite graph, it counts perfect matchings: ways to pair every vertex on one side with a distinct adjacent vertex on the other. Understanding why its algebraic representation is expensive illuminates the difference between easily evaluating a determinant and counting these combinatorial objects.

The border formulation also matters methodologically. Many fast algebraic constructions use limiting identities before converting them into exact asymptotic procedures. A lower bound robust under coefficientwise limits addresses this flexibility directly.

The score is below the exceptional category because the claimed bound remains a fixed polynomial. It does not establish the superpolynomial separation that motivates the broadest permanent–determinant questions, and it does not resolve Boolean $\mathsf P$ versus $\mathsf{NP}$.

6. The main idea

Extract a smoother polynomial

Directly examining the permanent’s singularities offers limited leverage: simple matrices with zero columns already produce a large singular set. The paper instead constructs a carefully selected coefficient of a modified permanent.

For an auxiliary matrix size $k$, introduce parameters $s,t$ and a diagonal matrix $D$. The expression

$$G_D(X)=[s^q t^q]\operatorname{per}_k(X+sI+tD)$$

means “take the coefficient of $s^q t^q$.” Here $I$ is the identity matrix and $q$ is chosen near $k/3$. The resulting polynomial has degree $k-2q$, still proportional to $k$, in entries of $X$.

The manuscript constructs this coefficient polynomial as an affine restriction of a permanent whose order is only a constant multiple of $k$. Thus a small determinant representation of the original permanent would also give one for the extracted polynomial.

Use characteristic two as an intermediate tool

In characteristic two, plus and minus signs coincide, so permanent and determinant agree. The paper uses this simplification to study plane curves defined by a determinant involving $sI+tD+uX$, with one additional parameter $u$.

It relates vanishing derivatives of the coefficient polynomial to a measure of the curve’s singularity called its normalization defect. Normalization separates algebraic branches that meet at singularities; the defect records how much local algebra changes in that process.

Bounds on the dimensions of families of curves with large defects then constrain where the coefficient polynomial can be singular. A specialization argument transfers the needed information to complex parameters. The paper chooses a linear section avoiding the singularities, obtaining a smooth homogeneous polynomial in quadratically many variables and of linearly growing degree.

Characteristic two is used inside the construction. The final permanent lower bound is still the stated complex theorem.

Multiply degree by dimension

The final ingredient counts polar intersections, geometric conditions involving a hypersurface and its tangent directions. For the smooth forms used in the argument, the manuscript establishes a border determinant lower bound proportional to

$$(\text{degree}-1)(\text{number of variables}-1).$$

The constructed degree is proportional to $k$, while the number of variables is proportional to $k^2$. Their product has cubic order. The comparison also accounts for persistence under coefficientwise determinant limits, which is essential for the border conclusion.

7. Scope, limitations, and open questions

The theorem concerns arbitrary complex affine determinant representations. It does not claim a corresponding cubic lower bound over every finite field. Indeed, in characteristic two the permanent itself is a determinant of the original size, illustrating why the field cannot be ignored.

Cubic growth leaves a large gap to known exponential-size constructions and to the hoped-for superpolynomial lower bound. It also does not lower-bound all arithmetic circuits without restriction: determinantal representations and the stated branching programs are specific computational models.

The explicit constant is small and the threshold large. The result should therefore be read as an asymptotic structural advance, rather than a sharp answer for a particular small permanent.

8. Sources and further reading

M1’s introduction compares the exact, border, and symmetry-restricted models; its final section gives the branching-program consequences. The historical papers linked above explain why moving a geometric obstruction from one representation to an entire closure is a substantial part of the problem.

Source manuscripts

• M1. OpenAI, A cubic lower bound for border determinantal complexity of the permanent (September 24, 2026).

Sources consulted on 9 October 2026 at repository revision fd4aeeb. Download the manuscript citations.