Cubic lower bounds for permanent determinant representations

Source and verification

This article explains family 108 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Permanent and determinant representations

For an $m\times m$ matrix of variables, the permanent sums one monomial for every permutation, with no alternating signs:

$${\mathrm{per}}_m(X)=\sum _{\sigma \in S_m}\prod _{i=1}^m{x}_{i,\sigma (i)}.$$

The determinant has the same monomials weighted by permutation signs. This small-looking change leads to a representation problem: how large a determinant of affine-linear forms is required to express the permanent?

For a complex polynomial $f(x_1,\dots ,x_N)$, its determinantal complexity $\mathrm{dc}(f)$ is the least positive matrix size $n$ such that

$$f(x)=\det \left(A_0+\sum _{j=1}^N{x}_j{A}_j\right)$$

for fixed complex matrices $A_j$ of order $n$. Entries may be arbitrary affine-linear forms, rather than just individual variables or constants.

The border version $\underline{\mathrm{dc}}(f)$ allows coefficientwise limits of such polynomials with the matrix size fixed throughout the approximation. Matrix coefficients may become unbounded. Since an exact representation is a constant approximating sequence,

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

This is a question about one computational representation model. A lower bound for it is not a lower bound for every arithmetic algorithm.

🏷️ A small example and the cubic claim

For order two,

$$ad+bc=\det \left(\begin{array}{cc}a& b\\ -c& d\end{array}\right).$$

Both exact and border determinantal complexity are therefore at most two. They cannot be one, because an affine polynomial, or a coefficientwise limit of affine polynomials, has degree at most one.

Manuscript statement

Over $\mathbb{C}$, for every $m\ge 1408$,

$$\underline{\mathrm{dc}}({\mathrm{per}}_m)\ge \frac{m^3}{5529600e}.$$

The same bound holds for exact determinantal complexity. The constant is not asserted to be optimal. (OpenAI, 2026)

This is a cubic polynomial lower bound. It does not settle whether determinantal complexity is superpolynomial. The manuscript also derives branching-program consequences, but its family scope page selects the determinant bounds and a supporting initial-form theorem.

🏷️ Two proof interfaces

The proof combines a representation obstruction with a construction inside the permanent. The specialized algebraic geometry is treated here as an input, rather than developed as a separate subject.

First, let $G$ be a nonzero homogeneous complex polynomial of degree $r\ge 2$ in $d\ge 2$ variables. Assume it has no nonzero singular zero: whenever $G(z)=0$ and $z\ne 0$, at least one first partial derivative is nonzero. The manuscript proves the obstruction

$$\underline{\mathrm{dc}}(G)\ge \frac{(r-1)(d-1)}{4e}.$$

Second, it constructs a fixed affine substitution of a permanent of size $O(k)$ that equals such a $G$ with degree of order $k$ in order $k^2$ variables. The product in the displayed obstruction then has cubic order in $k$.

Why does an affine substitution preserve the lower-bound direction? If $G=f\circ \Phi$ and $f$ has a size-$n$ affine determinant representation, composing its entries with the affine map $\Phi$ gives a size-$n$ representation of $G$. Coefficientwise convergence is preserved by a fixed substitution, since every resulting coefficient is a fixed linear combination of the original coefficients. Therefore

$$\underline{\mathrm{dc}}(G)\le \underline{\mathrm{dc}}(f).$$

This elementary monotonicity transfers the obstruction from the constructed polynomial to the permanent.

🏷️ Why the border argument needs persistence

The representation obstruction compares a count associated with $G$ to one permitted by a size-$n$ determinant. The geometric input produces $r(r-1{)}^{d-2}$ selected simple intersections of $G=0$ with directional-derivative equations. The source then proves that these intersections persist for one sufficiently close approximating determinant. Left and right kernel equations for that determinant give

$$\begin{array}{rl}r(r-1{)}^{d-2}& \le 2^{d-2}\left(\genfrac{}{}{0ex}{}{2n-1}{d-1}\right)\\ & \le {\left(\frac{4en}{d-1}\right)}^{d-1}.\end{array}$$

Taking the $(d-1)$st root of the left side gives at least $r-1$, yielding the stated bound. If $d-1>2n-1$, the binomial coefficient vanishes and the positive count is already impossible.

The essential border issue is selecting one nearby determinant that retains all required intersections. A lower bound established separately for exact representations does not automatically pass to their limits. Nor can one assume the representing matrices converge merely because their determinant polynomials do. The paper’s persistence argument is designed to require only coefficientwise closeness of those polynomials.

🏷️ Extracting a polynomial of the required scale

For a diagonal parameter matrix $D$ and an auxiliary order $k$, consider the coefficient polynomial

$$\begin{array}{c}Y=X+sI+tD,\\ G_D(X)=[s^q{t}^q]{\mathrm{per}}_k(Y).\end{array}$$

Every term of the original permanent has degree $k$ in all entries and auxiliary variables. Extracting $s^q{t}^q$ therefore leaves degree $r=k-2q$ in the matrix entries. Taking $q=\lfloor (k-1)/3\rfloor$ makes this degree proportional to $k$.

The source’s finite construction realizes $G_D$, up to a nonzero scalar, as an affine restriction of a permanent of size $11k-2q$. A separate geometric argument supplies a complex parameter choice and a linear section on which the polynomial has no nonzero singular zero, while retaining $d=\lfloor k^2/100\rfloor$ variables for $k\ge 128$.

The geometric analysis temporarily studies the integral coefficient formula in characteristic two, where permanent and determinant agree. The finite complex representation has a scalar that vanishes in characteristic two, so that representation itself cannot simply be reduced modulo two. The source instead transfers information about the raw coefficient polynomial and only afterward uses the complex representation. This order prevents the two uses of the formula from being conflated.

Combining the affine restriction with the smooth-form obstruction gives the cubic scale. The explicit threshold and numerical constant come from the manuscript’s parameter accounting. The local Taylor variant similarly uses a first nonzero homogeneous term satisfying the same nonsingularity condition. No general theory of algebraic varieties is needed to understand the model or the monotonicity deduction, while the construction and persistence inputs remain substantial specialized results.

🏷️ Key steps and proof outlines

Selecting coefficients by counting perfect matchings

The section “Selecting a coefficient by a permanent projection” supplies a concrete combinatorial mechanism behind the affine restriction. Expand each diagonal entry of $X+sI+tD$ by choosing the ordinary variable, the $s$ term, or the $t{\theta }_i$ term. If $S$ records the $s$ positions and $T$ the $t$ positions, a permanent term uses each row and column once, so $S\cap T=\varnothing$. Removing those positions leaves a permutation of their complement $C$. Consequently

$$G_D(X)=\sum _{\begin{array}{c}|S|=|T|=q\\ S\cap T=\varnothing \end{array}}\left(\prod _{i\in T}{\theta }_i\right)\mathrm{per}(X_{C,C}).$$

There is no extra factorial in this expansion: the sets and the remaining permutation reconstruct the original term uniquely. (OpenAI, 2026)

To enforce exactly $q$ choices of one special color, introduce a gate with $k$ original rows and columns, $h=k-q$ additional rows and columns, distinguished original diagonal edges, and complete cross connections between original and additional classes. Every additional row must consume an original column, and every additional column must consume an original row. Exactly $q$ original diagonal edges remain in any perfect matching. For each prescribed set of those edges, the cross connections have $(h!{)}^2$ completions. A second gate enforces the second color count.

An equality gadget whose unwanted states cancel

The remaining problem is synchronizing a special edge in the main matching with its distinguished gate edge. The source uses three internal rows and columns with matrix

$$H=\left(\begin{array}{ccc}-1& -1& 1\\ -1& -1& 1\\ 1& 1& 1\end{array}\right).$$

Two interfaces connect the main and gate edges to the first two internal rows and columns. If the main edge has weight $w$, one interface edge receives weight $-2w$. Fix the incoming and outgoing interface choices before summing internal matchings. Unequal numbers of incoming and outgoing choices leave unequal internal row and column counts, so they have no completion. For a singleton on each side, the remaining $2\times 2$ matrix has permanent $-1+1=0$.

The only nonzero total states are therefore “neither selected,” of weight $\mathrm{per}(H)=-2$, and “both selected,” of weight $-2w$. This is weighted cancellation, not a claim that every forbidden state has no individual matching. Fixing all external choices first allows independent internal sums to multiply, because different gadgets have disjoint internal vertices even when their external endpoints are shared.

With two gadgets per main position, every valid matching acquires the same factor $(-2{)}^{2k}$. The two counting gates contribute $((k-q)!{)}^4$. The row count is

$$k+2(2k-q)+3(2k)=11k-2q.$$

This proves the advertised linear-size permanent representation of the coefficient polynomial, up to a fixed nonzero scalar over the complex numbers. It also explains precisely why that scalar cannot be reduced modulo two to obtain the separate characteristic-two argument.

Multiplying degree and dimension into a cubic obstruction

The geometric section produces a nonsingular homogeneous restriction with degree $r=k-2q$ and number of variables $d=\lfloor k^2/100\rfloor$. Those are different resources: degree comes from the number of unselected matching positions, while dimension comes from the surviving linear section. The representation obstruction multiplies them through $(r-1)(d-1)$.

Its final estimate uses the elementary binomial bound $\left(\genfrac{}{}{0ex}{}{N}{k}\right)\le (eN/k{)}^k$. Thus the selected intersection count forces

$$r(r-1{)}^{d-2}\le {\left(\frac{4en}{d-1}\right)}^{d-1}.$$

Since $r\ge r-1$, the left side is at least $(r-1{)}^{d-1}$. Taking roots gives $n\ge (r-1)(d-1)/(4e)$. With $r$ linear and $d$ quadratic in $k$, this is cubic. The border conclusion still depends on the source’s persistence theorem, which places all the selected intersections in one sufficiently close approximating determinant; the matching gadget alone addresses only the restriction construction.

See Also

• Matrix-multiplication exponents concerns upper bounds for arithmetic algorithms, rather than determinant representation size.
• Perfect-matching counting explains the permanent’s counting interpretation in bipartite graphs and distinguishes exact representation from randomized relative approximation.

🏷️ Manuscripts and verification scope

• A cubic lower bound for border determinantal complexity of the permanent — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The selected statements cover exact and border permanent bounds, and an obstruction using a smooth first nonzero homogeneous Taylor term. The branching-program consequences are outside that selected scope. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. A cubic lower bound for border determinantal complexity of the permanent.