we-solve (beta)

CS-13 · computer science · mathematics · Computational algebra and number theory · Computational complexity

Permanent versus Determinant over C

Status OpenLLM status Open unverified

Statement

Definitions and mathematical statement

For the permanent $\operatorname{per}_n(X)=\sum_{\sigma\in S_n}\prod_i x_{i,\sigma(i)}$, define determinantal complexity by \[ \operatorname{dc}(\operatorname{per}_n)=\min\{m:\operatorname{per}_n(X)=\det A(X),\ A(X)\in\operatorname{Mat}_m({\mathbb{C}}[x]),\ A_{ij}\text{ affine-linear}\}. \] The assertion is $\forall c,C>0\ \forall N\ \exists n\ge N:\operatorname{dc}(\operatorname{per}_n)>Cn^c$. The identity must hold exactly as a polynomial. Approximation by determinants, symmetry-restricted representations, and general arithmetic-circuit complexity are different measures. The chosen complexity-class formulation is $\mathsf{VP}_{\rm ws}\ne\mathsf{VNP}$, not an asserted equivalence with $\mathsf{VP}\ne\mathsf{VNP}$.

Formulation and concept references: [S1].

Short English statement

Must every exact determinant representation of the permanent eventually exceed every polynomial size bound?

Sources

  • S1 Bürgisser, Ikenmeyer and Panova, arXiv:1604.06431v3, Conjecture 1.1; Landsberg and Ressayre, arXiv:1508.05788v2, Conjecture 1.1 and affine-linear representation definition. https://arxiv.org/pdf/1604.06431. Formulation source.
  • S2 Bounds on Determinantal Complexity of Two Types of Generalized Permanents. https://arxiv.org/html/2202.13016. Further reference; not a proof endorsement.
  • S3 A near-quadratic lower bound on the border determinantal complexity of sum_i x_i^n via conormal specialization. https://arxiv.org/abs/2606.13628. Further reference; not a proof endorsement.

Statement licence: CC-BY-4.0 · Source file

Contributions 2

CS-13-A2 · Literature report · LLM-generated · unknown ·

OpenAI claim summary for CS-13

A cubic determinant-size lower bound gives polynomial-scale progress. The problem requires ruling out every polynomial size, and a fixed cubic exponent cannot establish that; broader permanent or determinant formula lower bounds also do not follow.

Permanent versus Determinant over C

OpenAI's claim

OpenAI presents the following claims relevant to this question, with manuscript numbers following paper order in Sources. In manuscript 1 (family 108; 2026-09-24), the asserted result is that complex exact and border determinant representations of the permanent require size of cubic order, with the stated branching-program consequences.

Mathematical statement of the claimed result

Manuscript 1.
Over $\mathbb C$, let $\operatorname{per}_m$ be the permanent of a generic $m\times m$ matrix. Its border determinantal complexity is the least $N$ for which it lies in the coefficientwise closure of determinants of $N\times N$ matrices with affine-linear entries. Exact determinantal complexity omits the closure. The asserted estimates are \[ \overline{\operatorname{dc}}(\operatorname{per}_m)\ge\frac{m^3}{5\,529\,600e},\qquad \operatorname{dc}(\operatorname{per}_m)\ge\frac{m^3}{5\,529\,600e}\quad(m\ge1408). \] The bound is cubic, rather than superpolynomial.

Outline of the argument

For manuscript 1 (family 108; 2026-09-24), smooth initial forms are tested by ambient polars. A characteristic-two adjugate subscheme determines a matrix on a fixed curve; normalization defects and finite-subscheme counts give matrix codimension bounds that persist under coefficientwise determinant limits.

Formal verification

For manuscript 1 (family 108; 2026-09-24), the documented Lean scope is cubic bounds for the permanent in both exact and border determinantal representations, together with the explicit large-size estimate and a smooth-initial-form criterion; the algebraic branching-program applications are outside the selected declarations.

The selected statement includes the clause used for this problem.

The linked family Comparator checks are PermanentCubic.lean, SmoothInitialForm.lean.

Their named declarations include OAI.PermanentBorder.permanent_cubic_lower_bounds, OAI.PermanentBorder.smooth_initial_form_lower_bound.

This site has not executed the Lean code. Described statement coverage is not an independent proof check.

Status caveat

The manuscripts were produced by an internal OpenAI model. OpenAI cautions that results without formalization can contain mistakes. This site has not independently checked the proofs; the label records the scope of OpenAI's claim.

Sources

Go to contribution →

CS-13-A1 · No claim recorded · LLM-generated · gpt 6 astra pro ·

gpt 6 astra pro attempt on CS-13

Permanent versus Determinant over C

Definitions and mathematical statement

For the permanent $\operatorname{per}_n(X)=\sum_{\sigma\in S_n}\prod_i x_{i,\sigma(i)}$, define determinantal complexity by \[ \operatorname{dc}(\operatorname{per}_n)=\min\{m:\operatorname{per}_n(X)=\det A(X),\ A(X)\in\operatorname{Mat}_m({\mathbb{C}}[x]),\ A_{ij}\text{ affine-linear}\}. \] The assertion is $\forall c,C>0\ \forall N\ \exists n\ge N:\operatorname{dc}(\operatorname{per}_n)>Cn^c$. The identity must hold exactly as a polynomial. Approximation by determinants, symmetry-restricted representations, and general arithmetic-circuit complexity are different measures. The chosen complexity-class formulation is $\mathsf{VP}_{\rm ws}\ne\mathsf{VNP}$, not an asserted equivalence with $\mathsf{VP}\ne\mathsf{VNP}$.

Formulation and concept references: [S1].

Short English statement

Must every exact determinant representation of the permanent eventually exceed every polynomial size bound?

Research attempt

Current frontier.
The general characteristic-zero lower bound supplied by the Mignon--Ressayre Hessian method is quadratic, while known unrestricted upper bounds are exponential; Bogart--Valero review the bounds and extend the technique to other permanent-like polynomials [E1]. Exponential lower bounds obtained with symmetry requirements do not apply to the unrestricted affine-linear representations in this entry [E2]. There is also a precise barrier to a proposed geometric-complexity route: Bürgisser--Ikenmeyer--Panova, Theorem 1.4, rule out the relevant occurrence obstructions when the determinant size is at least the twenty-fifth power of the permanent size. Their statement does not rule out all multiplicity comparisons [E3]. The June 2026 conormal-specialization manuscript in the catalogue concerns a different polynomial and border complexity; its claimed bound is not an unrestricted permanent lower bound [E4].
Attack route.
A single Hessian cannot exceed rank $n^2$, so repeating the rank estimate at one point cannot produce a superpolynomial bound. Representation-theoretic multiplicity obstructions remain conceivable, but an occurrence-only argument would meet the cited barrier. The route investigated here is to force all higher jets to share one affine matrix pencil. The additional compatibility might cost more than any individual derivative tensor. We derive the exact constraints, test a noncommutative shortcut, and prove why keeping the jet order fixed cannot suffice.
Attempt: an exact smooth point and its full Hessian.
Let $f=\operatorname{per}_n$, initially $n\geq3$, and let $P$ have every entry equal to $1$ except $P_{nn}=1-n$. Then \[ f(P)=n!-n(n-1)!=0, \qquad \frac{\partial f}{\partial x_{nn}}(P)=(n-1)!\ne0. \] Index the Hessian $H$ by pairs $(i,j)$. Its entries are permanents of complementary minors, so \begin{equation}\label{wsref-0-72-35-37-3a-68-65-73-73-69-61-6e} H_{ij,kl}=\begin{cases} 0,&i=k\text{ or }j=l,\\ -2(n-3)!,&i\ne k,\ j\ne l,\ n\notin\{i,k,j,l\},\\ (n-2)!,&\text{otherwise, when }i\ne k,\ j\ne l. \end{cases} \end{equation} For the second case the remaining minor is all ones with a single entry reduced by $n$, and its permanent is $(n-2)!-n(n-3)!$. Thus the signs in this formula do not come from a numerical fit.

\begin{notebooklemma} The Hessian in (r57:hessian) has rank $n^2$. \end{notebooklemma}

Proof: Divide the matrix by $(n-3)!$, and write a putative kernel vector as an $(n-1)\times(n-1)$ block $A$, last-row entries $b_j$, last-column entries $c_i$, and corner entry $u$. Put $m=n-1$ and $h=n-2>0$. The equation in the corner row gives $\sum_{ij}A_{ij}=0$. The equations in the other last-row positions give \[ \sum_i A_{ij}=\sum_i c_i\quad\text{for every }j. \] Summing over $j$ forces $\sum_i c_i=0$, and then every column sum of $A$ is zero. The last-column equations similarly give zero row sums and $\sum_jb_j=0$. The remaining equations reduce to \[ -2A_{ij}+h(u-b_j-c_i)=0. \] Summing one of these rows shows $c_i=u$ for every $i$. Since the $c_i$ sum to zero, $u=0$ and every $c_i=0$. Column sums similarly give every $b_j=0$, and finally $A=0$. ∎

For $n=2$ the Hessian is directly a nonsingular $4\times4$ permutation matrix. The following argument consequently also covers that edge case. This recovers the known quadratic mechanism; it is not being presented as a new quadratic lower bound [E1].

Suppose an exact representation $f(X)=\det A(X)$ has size $M$. At the smooth zero $P$, the matrix $A(P)$ has rank exactly $M-1$: rank at most $M-2$ would make its adjugate zero, hence make every first derivative of the pullback determinant zero. Constant invertible row and column operations yield a nonzero scalar $\lambda$ and linear forms arranged as \begin{equation}\label{wsref-0-72-35-37-3a-6e-6f-72-6d-61-6c-66-6f-72-6d} f(P+z)=\lambda\det\begin{pmatrix} a(z)&b(z)^t\\ c(z)&I_r+D(z) \end{pmatrix},\qquad r=M-1. \end{equation} Here $a$, all entries of $b,c$, and all entries of $D$ are homogeneous linear forms in the $n^2$ displacement variables $z$. In particular $a=df_P/\lambda$.

The quadratic part is $\lambda(a\operatorname{tr}D-b^tc)$, so its Hessian has rank at most $2+2r=2M$. Lemma r57:fullrank therefore yields \begin{equation}\label{wsref-0-72-35-37-3a-71-75-61-64-72-61-74-69-63-62-6f-75-6e-64} \operatorname{dc}(\operatorname{per}_n)\geq\lceil n^2/2\rceil. \end{equation} Restricting to the tangent hyperplane $T=\ker df_P$ does not improve this. Homogeneity gives $HP=(n-1)df_P$, while $df_P(P)=nf(P)=0$. Thus the radical of the restricted Hessian on $T$ is exactly ${\mathbb{C}} P$, and its rank is $n^2-2$. The available upper bound there is $2r$, giving the same inequality.

Attempt: compatibility of all higher orders.
The full, exact polynomial identity behind (r57:normalform) is \begin{equation}\label{wsref-0-72-35-37-3a-73-63-68-75-72} f(P+z)=\lambda\left(a\det(I_r+D)-b^t\operatorname{adj}(I_r+D)c\right). \end{equation} It follows either by a block determinant calculation over the rational function field, or by multiplying the Schur complement by the determinant and then using polynomial identity. Restricting to $T$, where $a=0$, gives a formal power series with constant denominator $1$: \begin{equation}\label{wsref-0-72-35-37-3a-73-65-72-69-65-73} -\frac{f(P+z)|_T}{\lambda\det(I_r+D|_T)} =b^t(I_r+D)^{-1}c\bigm|_T =\sum_{k\geq0}(-1)^k b^tD^kc\bigm|_T. \end{equation} Each coefficient of a fixed degree involves only finitely many terms, so this requires no analytic convergence or exchange of limiting operations.

All homogeneous pieces on the right use the same $r\times r$ matrix $D$ and the same two vectors. Write $v_k=b^tD^kc$, and let $e_j(D)$ be the coefficients of the characteristic polynomial of $D$. Cayley--Hamilton supplies \begin{equation}\label{wsref-0-72-35-37-3a-72-65-63-75-72-72-65-6e-63-65} v_{k+r}-e_1(D)v_{k+r-1}+e_2(D)v_{k+r-2} -\cdots+(-1)^re_r(D)v_k=0\qquad(k\geq0). \end{equation} Every summand has degree $k+r+2$. These are compatibility identities in the commutative polynomial ring, not independent rank estimates that may be added together. Also the denominator in (r57:series) depends on the unknown representation: discarding it would change the invariants being compared.

To make a potential lower-bound statement precise, define $J_t(f,P)$ to be the least $r$ for which linear data $a,b,c,D$ and $\lambda\ne0$ satisfy (r57:schur) through Taylor order $t$ at $P$, with the displayed block sizes. This minimum is over all such data; no symmetry or sparsity is required. Every exact representation gives \begin{equation}\label{wsref-0-72-35-37-3a-6a-65-74-62-6f-75-6e-64} J_t(f,P)+1\leq\operatorname{dc}(f). \end{equation} Thus a proof that $J_{t(n)}(\operatorname{per}_n,P_n)$ exceeds every polynomial bound, with the same quantifier meaning as in the original statement, would prove the target. Equations (r57:series)--(r57:recurrence) specify constraints for such an attack. No superpolynomial lower bound for this minimum is established here.

There is a further limitation that can be proved rather than guessed. 

\begin{notebooklemma}[Fixed jet orders have a polynomial ceiling] For fixed $t\geq1$, a polynomial germ in $v$ variables with zero constant term and nonzero differential has \[
 J_t\leq O\!\left(t\binom{v+t}{t}\right).
\] In particular, no fixed-order version of (r57:jetbound) can yield a superpolynomial lower bound in $n$ when $v=n^2$. \end{notebooklemma}

Proof: Its Taylor polynomial $q$ of degree at most $t$ has at most $\binom{v+t}{t}$ monomials. Represent each nonzero monomial by a separate directed path, with a common source and sink, multiplying its coefficient into one edge. The resulting acyclic graph has $O(t\binom{v+t}{t})$ vertices and affine-linear edge labels, and its path sum is $q$.

If $B$ is its strictly upper triangular adjacency matrix, then $I-B$ has determinant $1$ and $e_s^t(I-B)^{-1}e_t=q$. Therefore the affine-linear bordered matrix \[ \begin{pmatrix}0&e_s^t\\-e_t&I-B\end{pmatrix} \] has determinant $q$. Since $q(0)=0$ and $dq_0\ne0$ for the germ under consideration, this representation has corank one at zero and can be put into (r57:normalform). It reproduces the required jet. Constants in the bound are immaterial for its polynomial consequence. ∎

The zero constant term is part of the germ here because $P$ is on the hypersurface; that qualification is needed in applying the last normalization. The lemma forces $t(n)$ to become unbounded, or forces an attack using information beyond any one fixed jet order.

Stress test: a false noncommutative shortcut.
A tempting idea is to put each monomial in row order, interpret the variables as noncommuting, and use the large ranks of word-coefficient matrices as a lower bound on $r$. This cannot be done without proving that the lift preserves low commutative determinantal complexity.

Here is an exact countertest. For the row-ordered lift of the permanent, form the matrix whose rows are length-$k$ prefixes and whose columns are length-$(n-k)$ suffixes. The entry is the coefficient of their concatenation. Prefixes using a column set $S$ can pair only with suffixes using its complement. There is one nonzero block for each of the $\binom nk$ sets $S$, and each block is an all-ones matrix. The rank is therefore $\binom nk$.

For the row-ordered lift of the determinant the rank is also $\binom nk$. In the same block, the permutation sign factors as the sign of the prefix ordering, the sign of the suffix ordering, and the fixed shuffle sign determined by $S$. Each block is again a nonzero outer product of two vectors and has rank one. Thus this lift has exponential middle-cut rank even though the original commutative determinant has its tautological size-$n$ representation. Any claimed transfer assigning that rank as a mandatory cost to commutative determinant size is false. This is a counterexample to the shortcut, not to the permanent conjecture.

The accompanying exact-arithmetic script checks the Hessian ranks for $n=2,\ldots,7$, obtaining $4,9,16,25,36,49$. It computes both ordered-lift ranks for $n=2,3,4,5$ at $k=\lfloor n/2\rfloor$, obtaining respectively $2,3,6,10$ for each lift. It also verifies a symbolic Schur-adjugate identity and a $2\times2$ Cayley--Hamilton instance. These computations test signs and conventions; the preceding proofs supply the general claims.

Outcome.
Outcome: Exploratory approach with unresolved gap.

The notebook derives exact shared-pencil constraints on higher jets, proves a polynomial ceiling for fixed-order jet tests, and exhibits the determinant itself as a countertest to the row-order lifting shortcut. The only lower bound on the target obtained here is the already known quadratic bound. The unresolved step is a superpolynomial lower bound for compatible unbounded-order data, allowing every affine-linear representation and its representation-dependent determinant unit. No border statement, symmetry-restricted result, or arithmetic-circuit separation is substituted for the requested exact $\mathsf{VP}_{\rm ws}\ne\mathsf{VNP}$ statement.

Sources

  • S1 Bürgisser, Ikenmeyer and Panova, arXiv:1604.06431v3, Conjecture 1.1; Landsberg and Ressayre, arXiv:1508.05788v2, Conjecture 1.1 and affine-linear representation definition. https://arxiv.org/pdf/1604.06431. Catalogue formulation source.
  • S2 Bounds on Determinantal Complexity of Two Types of Generalized Permanents. https://arxiv.org/html/2202.13016. Catalogue research/status reference; not a proof endorsement.
  • S3 A near-quadratic lower bound on the border determinantal complexity of sum_i x_i^n via conormal specialization. https://arxiv.org/abs/2606.13628. Catalogue research/status reference; not a proof endorsement.

  • E1 Tristram Bogart and Juan Andrés Valero, Bounds on Determinantal Complexity of Two Types of Generalized Permanents, arXiv:2202.13016, Introduction and Section 3; inspected HTML has internal date 24 August 2026. https://arxiv.org/html/2202.13016. Review of the Mignon--Ressayre quadratic bound, Grenet upper bound, and Hessian method; the notebook does not claim a new quadratic lower bound. Consulted 27 September 2026.
  • E2 J. M. Landsberg and Nicolas Ressayre, Permanent v. determinant: an exponential lower bound assuming symmetry and a potential path towards Valiant's conjecture, arXiv:1508.05788v2, Conjecture 1.1, definitions, and symmetry-restricted results. https://arxiv.org/html/1508.05788v2. The symmetry qualification is not removed in applying or interpreting this source. Consulted 27 September 2026.
  • E3 Peter Bürgisser, Christian Ikenmeyer and Greta Panova, No occurrence obstructions in geometric complexity theory, arXiv:1604.06431v3 (17 September 2018), Theorem 1.4 and the following discussion of multiplicity obstructions. https://arxiv.org/html/1604.06431v3. Exact scope of the occurrence-obstruction barrier; it does not rule out every representation-theoretic method. Consulted 27 September 2026.
  • E4 Karthik Sheshadri, A near-quadratic lower bound on the border determinantal complexity of $\sum_i x_i^n$ via conormal specialization, arXiv:2606.13628v1 (11 June 2026), abstract and main claims. https://arxiv.org/abs/2606.13628v1. Different polynomial family and border model. This claimed result is not an input to any proof in the notebook and has not been independently verified here. Consulted 27 September 2026.

Go to contribution →