betaFeedback

WorksComputer Science

Cubic lower bounds for the permanent in odd characteristic, for Pfaffian representations, and for polynomial entries

Abstract

The determinantal complexity of a polynomial is the order of the smallest matrix whose entries are polynomials of degree at most one and whose determinant equals the polynomial. A lower bound for the permanent in this measure is the algebraic form of the question whether the permanent is harder to compute than the determinant. Over the complex numbers, the best known lower bound grows cubically in the size of the permanent. It holds even when the permanent only has to be a limit of such determinants. I prove that the cubic lower bound holds over every algebraically closed field of odd characteristic pp, with a constant that depends on pp. Hence the cubic bound does not depend on characteristic zero. I also prove the bound for Pfaffians, which are square roots of determinants of skew symmetric matrices. Lower bounds for Pfaffians imply the same bounds for determinants. Further, I prove the bound, divided by aa, for matrices whose entries are polynomials of degree at most aa. All three results come from one lower bound for smooth hypersurfaces. I prove it in every characteristic by counting intersection points together with their multiplicities.

Introduction

The permanent of an n×nn \times n matrix YY is

per⁡n(Y)=∑σ∏i=1nYi,σ(i),\operatorname{per}_{n}(Y)=\sum_{\sigma}\prod_{i=1}^{n}Y_{i,\sigma(i)},

where σ\sigma runs over the permutations of {1,…,n}\{1,\ldots,n\}. The determinant is the same sum with the sign of σ\sigma attached to each term. The determinant can be computed quickly by Gaussian elimination. However, no fast method is known for the permanent. Valiant [6] gives this gap an algebraic form. He shows that a polynomial computed by a formula of size ss is the determinant of a matrix of order linear in ss whose entries are affine linear forms, i.e., polynomials of degree at most one. He also shows that, in characteristic other than two, the permanent is complete under such substitutions for the class VNP, an algebraic analogue of NP.

A determinantal representation of a polynomial F(x1,…,xN)F(x_1,\ldots,x_N) is a square matrix M(x)M(x) whose entries are affine linear forms in xx and whose determinant is FF. The determinantal complexity dc⁡(F)\operatorname{dc}(F) is the smallest order of such a matrix. Because of Valiant’s results, the question whether the permanent is harder than the determinant becomes the question whether dc⁡(per⁡n)\operatorname{dc}(\operatorname{per}_n) grows faster than every polynomial in nn. The border determinantal complexity dc⁡‾(F)\overline{\operatorname{dc}}(F) is the smallest mm such that FF is a limit of determinants of m×mm \times m matrices with affine linear entries. Here the limit is taken coefficient by coefficient. Every representation is also such a limit. Hence dc⁡‾(F)≤dc⁡(F)\overline{\operatorname{dc}}(F) \leq\operatorname{dc}(F), and a lower bound on dc⁡‾(F)\overline{\operatorname{dc}}(F) is the stronger statement.

Mignon and Ressayre [3] show that dc⁡(per⁡n)≥n2/2\operatorname{dc}(\operatorname{per}_n) \ge n^2/2 in characteristic zero. Cai, Chen and Li [1] extend this quadratic bound to every characteristic other than two. In characteristic two the permanent equals the determinant, so no bound beyond nn is possible there. A manuscript from September 2026 [4] gives the first cubic bound, dc⁡‾C(per⁡n)=Ω(n3)\overline{\operatorname{dc}}_{\mathbb{C}}(\operatorname{per}_n) = \Omega(n^3). Its proof has two parts. Firstly, it restricts the permanent to a linear subspace on which the permanent becomes a smooth hypersurface of degree about n/3n/3 in about n2/100n^2/100 variables. Secondly, it shows that a smooth hypersurface of degree dd in NN variables has border determinantal complexity at least (N−1)(d−1)/(4e)(N-1)(d-1)/(4e), where ee is Euler’s number.

Both parts of that proof use characteristic zero. The first part selects one coefficient inside a permanent, and it uses factorials as weights to do so. In characteristic pp, every factorial j!j! with j≥pj \ge p is zero, so this selection breaks down. The second part counts the points where the hypersurface meets several of its first derivatives, and it assumes that these points are simple. In positive characteristic this can fail. For example, in characteristic pp every first derivative of x1p+1+⋯+xNp+1x_1^{p+1}+\cdots+x_N^{p+1} is the ppth power of a linear form. Hence every intersection point is repeated.

Two other models of representation are natural. The first uses Pfaffians. A square matrix MM is alternating if MT=−MM^{T}=-M and its diagonal is zero. Its Pfaffian Pf⁡M\operatorname{Pf} M is a polynomial in the entries whose square is det⁡M\det M. A Pfaffian representation of FF of half order mm is an alternating matrix of order 2m2m with affine linear entries whose Pfaffian is FF. Every determinantal representation of order mm gives a Pfaffian representation of half order mm, by (1) below. Therefore a lower bound for Pfaffians is also a lower bound for determinants. The second model allows entries that are polynomials of degree at most aa. It lies between Valiant’s model and the trivial representation [F][F], which has a single entry. I write pc⁡‾(F)\overline{\operatorname{pc}}(F) for the border complexity of Pfaffian representations, and dc⁡‾a(F)\overline{\operatorname{dc}}_a(F) and pc⁡‾a(F)\overline{\operatorname{pc}}_a(F) for the border complexities with entries of degree at most aa. To the best of my knowledge, nothing in the published literature addresses the cubic bound in positive characteristic, for Pfaffians, or for polynomial entries.

My contributions are three cubic lower bounds. Firstly, the cubic bound holds over every algebraically closed field of odd characteristic pp, with a constant that depends on pp. Secondly, it holds for Pfaffian representations, both over C\mathbb{C} and in odd characteristic. Thirdly, it holds for representations whose entries have degree at most aa, divided by aa. Note that the order of the permanent in the first result matters. Valiant’s completeness theorem already makes a determinant of order kk a restriction of a permanent of order polynomial in kk. However, a permanent of order kck^c would only give a bound of order n3/cn^{3/c}. My construction has order linear in kk for each fixed pp. Note also that the third result does not follow from the first. An entry of degree two can have many terms. For example, the 1×11 \times1 matrix [x12+⋯+xN2][x_1^2+\cdots+x_N^2] has one entry of degree two. However, every representation of x12+⋯+xN2x_1^2+\cdots+x_N^2 with affine entries has order at least (N−1)/(4e)(N-1)/(4e) in characteristic other than two, by Theorem 3.1.

The precise statements use the constant Bp=5p+38B_p=5p+38.

Theorem 1.1. Let pp be an odd prime and KK an algebraically closed field of characteristic pp. For every n≥128Bpn \ge128B_p,

dc⁡‾K(per⁡n)≥n3270eBp3,pc⁡‾K(per⁡n)≥n3540eBp3.\overline{\operatorname{dc}}_{K}(\operatorname{per}_n) \ge\frac{n^3}{270eB_p^3}, \qquad\overline{\operatorname{pc}}_{K}(\operatorname{per}_n) \ge\frac{n^3}{540eB_p^3}.

Over the complex numbers, pc⁡‾C(per⁡n)≥n3/(8.8⋅106e)\overline{\operatorname{pc}}_{\mathbb{C}}(\operatorname{per}_n) \ge n^3/(8.8 \cdot10^6e) for every n≥1408n \ge1408. The same bounds hold for the exact complexities.

Theorem 1.2. Let k=⌊n/11⌋k=\lfloor n/11\rfloor over C\mathbb{C} and k=⌊n/Bp⌋k=\lfloor n/B_p\rfloor in odd characteristic pp, and suppose k≥128k \ge128. For every integer 1≤a≤k/61 \le a \le k/6, over C\mathbb{C},

dc⁡‾a(per⁡n)≥log⁡(4/3)9600⋅k3a,pc⁡‾a(per⁡n)≥log⁡(4/3)19200⋅k3a.\overline{\operatorname{dc}}_a(\operatorname{per}_n) \ge\frac{\log(4/3)}{9600}\cdot\frac{k^3}{a}, \qquad\overline{\operatorname{pc}}_a(\operatorname{per}_n) \ge\frac{\log(4/3)}{19200}\cdot\frac{k^3}{a}.

and in characteristic pp the same bounds hold with 1008 and 2016 in place of 9600 and 19200. Both are therefore Ω(n3/a)\Omega(n^3/a) over C\mathbb{C} for a≤n/72a \le n/72, and Ωp(n3/a)\Omega_p(n^3/a) in characteristic pp for a≤n/(12Bp)a \le n/(12B_p).

The constants are poor and depend on pp. Note also that some bound on aa in Theorem 1.2 is necessary. Indeed, the 1×11 \times1 matrix [per⁡n][\operatorname{per}_n] is a representation with one entry of degree nn.

All three results rest on one lower bound for smooth hypersurfaces, Theorem 3.1, which holds in every characteristic. To prove it, I intersect the hypersurface with N−2N-2 general first derivatives of its equation. The intersection is a finite set of points with multiplicities, and the sum of the multiplicities is d(d−1)N−2d(d-1)^{N-2}. I follow this sum through the limit. I then bound it from above by a Bézout count on a larger space, which also records the kernel vectors of the matrix. Since the count uses multiplicities throughout, repeated points do no harm.

For Pfaffians I do not need a second argument. Let MM be alternating of order 2m2m, and let EE be its submatrix on the rows and columns 3,…,2m3,\ldots,2m. Let M′M' be MM with its first row and second column deleted. Then det⁡M′=−Pf⁡(E)Pf⁡(M)\det M'=-\operatorname{Pf}(E)\operatorname{Pf}(M) (Lemma A.2). After a constant change of coordinates, Pf⁡E\operatorname{Pf} E is nonzero at every point of the count. Hence, near these points, Pf⁡M\operatorname{Pf} M is a nonzero multiple of a determinant of order 2m−12m-1, and the count for determinants applies.

For the permanent in characteristic pp, I need two more ingredients. Firstly, the smooth hypersurface is a general linear section of GD(X)=[sqtq]det⁡(X+sI+tD)G_D(X)=[s^q t^q]\det(X+sI+tD), the coefficient of sqtqs^q t^q in a determinant. This section is smooth because the set of matrices XX where every derivative of GDG_D vanishes is small. Theorem 3.2 proves this in every characteristic. Secondly, GDG_D must be a restriction of a permanent of order linear in kk. Recall that p−1=−1p-1=-1 in characteristic pp. Hence, if a permanent gives each cycle of a permutation one of p−1p-1 colours, it counts the permutation (−1)c(-1)^c times, where cc is its number of cycles. Up to sign, this is the determinant. A permanent that forces exactly qq of LL marked entries to be used then extracts the coefficient (Theorem 4.3).

The remainder of this paper is organized as follows. Section 2 fixes the representations. Section 3 states the two geometric results that the proof needs. Section 4 builds the permanents in characteristic pp, and Section 5 proves Theorems 1.1 and 1.2. Section 6 describes how I used artificial intelligence. Appendices A and B prove the two geometric results, and Appendix C builds the selectors. A reader who accepts the geometric results can skip the appendices.

Representations, limits and Pfaffians

In this section, I fix the matrices that are allowed and say what it means for a polynomial to be a limit of their determinants or Pfaffians.

Notation. Throughout, KK is an algebraically closed field of any characteristic, unless I say otherwise, and e=exp⁡(1)e=\exp(1). For a form FF in NN variables, V(F)⊂PN−1V(F)\subset\mathbb{P}^{N-1} is its zero scheme, i.e., its zero set together with multiplicities. For w∈KNw\in K^N, the first polar ∂wF=∑jwj∂F/∂xj\partial_wF=\sum_j w_j\partial F/\partial x_j is the derivative of FF in the direction ww. A bracket such as [sitj]P[s^i t^j]P denotes the coefficient of sitjs^i t^j in PP. A zero dimensional scheme is a finite set of points, each with a finite dimensional local ring. Its length is the dimension of its coordinate ring over KK, and the length of a point is the dimension of its local ring. For a set of simple points, the length is just the number of points. Finally, ere_r is the elementary symmetric polynomial of degree rr.

Definition 2.1. Fix a≥1a\ge1. Let Dm,aD_{m,a} be the set of polynomials det⁡M(x)\det M(x), where MM is an m×mm\times m matrix whose entries are polynomials in x1,…,xNx_1,\ldots,x_N of degree at most aa. Let P2m,aP_{2m,a} be the set of polynomials Pf⁡M(x)\operatorname{Pf} M(x), where MM is alternating of order 2m2m with entries of the same kind. Both sets

lie in the space of polynomials of degree at most amam, and I take Zariski closures there. Put

dc‾a(F)=min⁡{m:F∈D‾m,a},pc‾a(F)=min⁡{m:F∈P‾2m,a}.\overline{\mathrm{dc}}_a(F)=\min\{m:F\in\overline{D}_{m,a}\},\qquad\overline{\mathrm{pc}}_a(F)=\min\{m:F\in\overline{P}_{2m,a}\}.

The exact complexities dca\mathrm{dc}_a and pca\mathrm{pc}_a are defined in the same way without the closure. For a=1a=1 I drop the subscript.

Three simple facts about these classes are used later. Firstly, an affine substitution x↦Λx+x0x\mapsto\Lambda x+x_0 keeps entry degrees at most aa. Secondly, a nonzero scalar can be absorbed into one row of a determinant, or into an alternating matrix by a constant congruence. Thirdly, for every m×mm\times m matrix MM over a commutative ring,

Pf⁡(0M−MT0)=(−1)m(m−1)/2det⁡M.(1)\operatorname{Pf}\begin{pmatrix}0&M\\-M^{T}&0\end{pmatrix}=(-1)^{m(m-1)/2}\det M. \tag*{(1)}

Hence all four complexities can only decrease under affine restriction, and pc‾a≤dc‾a\overline{\mathrm{pc}}_a\leq\overline{\mathrm{dc}}_a. Note also that perr\mathrm{per}_r is an affine restriction of pern\mathrm{per}_n for r≤nr\leq n. To see this, put an identity block in one corner.

The two geometric ingredients

The proof needs two results from algebraic geometry. The first is a lower bound for smooth hypersurfaces. The second gives a smooth hypersurface with many variables and large degree. I state both here, so that the rest of the paper can be read without their proofs. Appendix A proves the first, and Appendix B proves the second.

A lower bound for smooth hypersurfaces

Let FF be a form of degree d≥2d\geq2 in N≥2N\geq2 variables. I say that V(F)V(F) is smooth if the partial derivatives of FF have no common zero on V(F)V(F). The proof of the next theorem is in Appendix A. The idea is as follows. Firstly, the hypersurface meets N−2N-2 general first polars in a finite scheme of length d(d−1)N−2d(d-1)^{N-2}. Secondly, suppose that FF is a determinant. At each point of this scheme the matrix loses rank, and the vanishing of a polar there becomes a condition on the left and right kernel vectors of the matrix. Thirdly, I add the kernel vectors as new coordinates. The scheme then becomes a set of isolated points of a system of equations of low degree. A Bézout count bounds the total length of these points by a coefficient that grows only polynomially with the order of the matrix.

Theorem 3.1. Let FF be a form of degree d≥2d\geq2 in N≥2N\geq2 variables over an algebraically closed field of any characteristic, with V(F)V(F) smooth.

(i) If dc‾(F)≤m\overline{\mathrm{dc}}(F)\leq m, then d(d−1)N−2≤2N−2(2m−1N−1)d(d-1)^{N-2}\leq2^{N-2}\binom{2m-1}{N-1}, and if pc‾(F)≤m\overline{\mathrm{pc}}(F)\leq m, the same holds with 4m−34m-3 in place of 2m−12m-1. Consequently

dc‾(F)≥(N−1)(d−1)4e+12,pc‾(F)≥(N−1)(d−1)8e+34.\overline{\mathrm{dc}}(F)\geq\frac{(N-1)(d-1)}{4e}+\frac{1}{2},\qquad\overline{\mathrm{pc}}(F)\geq\frac{(N-1)(d-1)}{8e}+\frac{3}{4}.

(ii) If 0<c<10<c<1 and a≤cda\leq cd, then with Lc=log⁡(2/(1+c))L_c=\log(2/(1+c)),

dc‾a(F)≥(N−1)(1−c)Lc8⋅da+12,pc‾a(F)≥(N−1)(1−c)Lc16⋅da+34.\overline{\mathrm{dc}}_a(F)\geq\frac{(N-1)(1-c)L_c}{8}\cdot\frac{d}{a}+\frac{1}{2},\qquad\overline{\mathrm{pc}}_a(F)\geq\frac{(N-1)(1-c)L_c}{16}\cdot\frac{d}{a}+\frac{3}{4}.

In addition, dc‾a(F)\overline{\mathrm{dc}}_a(F) and pc‾a(F)\overline{\mathrm{pc}}_a(F) are at least ⌈d/a⌉\lceil d/a\rceil.

Proposition A.9 in Appendix A shows that these bounds have the right order of growth.

A smooth hypersurface of large degree

Theorem 3.1 applies to any smooth hypersurface. To reach the permanent, I need one particular smooth hypersurface with large NdNd that is a restriction of a small permanent. It comes from the polynomial GDG_D below, restricted to a general linear subspace. Such a restriction is smooth when the critical set of GDG_D is small. Here the critical set is the set of points at which every partial derivative of GDG_D vanishes. Theorem 3.2 below bounds the dimension of the critical set in every characteristic. Its proof in Appendix B follows the determinant side of [4]. The only outside input is a dimension bound for plane curves of given genus [2].

Fix k≥2k \ge2 and put

q=⌊k−13⌋,d=k−2q,c=d−1,T=(q+22),q = \left\lfloor\frac{k-1}{3} \right\rfloor,\qquad d = k - 2q,\qquad c = d - 1,\qquad T = \binom{q+2}{2},

so that 2q+c=k−12q+c=k-1 and c≥qc\ge q. I choose distinct θ1,…,θk∈K\theta_1,\ldots,\theta_k \in K and let D=diag⁡(θ1,…,θk)D=\operatorname{diag}(\theta_1,\ldots,\theta_k). Define

GD(X)=[sqtq]det⁡(X+sIk+tD),ΓD={X∈Mat⁡k(K):∇GD(X)=0},G_D(X) = [s^q t^q]\det(X+sI_k+tD),\qquad\Gamma_D = \{X\in\operatorname{Mat}_k(K):\nabla G_D(X)=0\},

where the gradient is taken with respect to all k2k^2 entries of XX.

Theorem 3.2. In every characteristic, dim⁡ΓD≤k2+k−T\dim\Gamma_D \le k^2+k-T.

The idea of the proof is as follows. To each matrix XX I attach a plane curve CXC_X of degree kk. Its normalisation defect δ(CX)\delta(C_X) measures its singularities. It is the length of ν∗OC~/OC\nu_*\mathcal{O}_{\widetilde{C}}/\mathcal{O}_C, where ν:C~→C\nu:\widetilde{C}\to C is the normalisation, i.e., the smooth curve that maps onto CC and is an isomorphism over the smooth points of CC. For example, a node contributes one to δ\delta. Firstly, if X∈ΓDX\in\Gamma_D, then δ(CX)≥T\delta(C_X)\ge T. Secondly, the curves of degree kk with δ≥T\delta\ge T form a set of codimension at least TT. Thirdly, the matrices with a given curve form a set of dimension at most k(k−1)/2k(k-1)/2.

I now use Theorem 3.2 to obtain the smooth hypersurface. Since ΓD\Gamma_D has codimension at least T−kT-k, a general linear section can have up to T−kT-k variables and still be smooth. I take all of them.

Corollary 3.3. Let k≥128k\ge128, let qq, dd and TT be as above, and put N=T−kN=T-k. For a general linear map Λ:KN→Mat⁡k(K)\Lambda:K^N\to\operatorname{Mat}_k(K), the form F=GD∘ΛF=G_D\circ\Lambda is nonzero of degree dd, and V(F)⊂PN−1V(F)\subset\mathbb{P}^{N-1} is smooth. Moreover

N−1≥k221,d−1≥k−13,d≥k3.(2)N-1\ge\frac{k^2}{21},\qquad d-1\ge\frac{k-1}{3},\qquad d\ge\frac{k}{3}. \tag*{(2)}

Appendix B proves Theorem 3.2 and Corollary 3.3.

Permanents in odd characteristic

Corollary 3.3 gives a smooth restriction of GDG_D. However, GDG_D is not yet a restriction of a permanent. Over C\mathbb{C}, the manuscript [4] selects the coefficient of sqtqs^qt^q inside a permanent, using factorials as weights. In characteristic pp this fails once p≤qp\le q. In this section, I replace that step by two constructions. The first is a permanent of linear order that forces exactly qq of LL marked entries to be used. The second writes the determinant of order kk as a permanent of order (5p−4)k(5p-4)k. From now on, pp is an odd prime and KK has characteristic pp.

I read a matrix as a weighted bipartite graph between its rows and its columns. A perfect matching pairs every row with a distinct column, and its weight is the product of the entries that it uses. The permanent is the sum of the weights of all perfect matchings. A marked entry is an entry that I single out, and its selection bit records whether a given matching uses it. If a marked entry is one summand of an entry, only that summand is meant. All constants below lie in Z[1/2]\mathbb{Z}[1/2]. Hence every identity below holds in every odd characteristic.

Both constructions need a way to force two marked entries to be used together or not at all. The equality gadget does this. It adds three new rows and three new columns, and Appendix § 9 gives it.

A selector of linear order

I now state the selector. It must check that exactly qq of LL bits are equal to one. I do this the way one adds numbers in binary. A circuit of full adders adds the bits, and its output is fixed to the binary digits of qq. Appendix § 9 builds the circuit and proves the following proposition.

Proposition 4.1. For L≥1L \ge1 and 0≤q≤L0 \le q \le L there is a matrix EL,q(z)E_{L,q}(z) of order at most 17L17L, with entries in Z[1/2]∪{z1,…,zL}\mathbb{Z}[1/2] \cup\{z_1,\ldots,z_L\}, such that per⁡EL,q=eq(z1,…,zL)\operatorname{per} E_{L,q}=e_q(z_1,\ldots,z_L). Each ziz_i occurs in one entry, and no row or column contains two of them.

Remark 4.2. Let e1,…,eLe_1,\ldots,e_L be marked entries of weights wiw_i in some matrix. Couple each eie_i by an equality gadget to the ziz_i entry of a disjoint copy of EL,qE_{L,q}, with ziz_i set to 1. The permanent of the result is the sum of the weights of the matchings of the original matrix that use exactly qq of the eie_i. The order grows by at most 20L20L.

The determinant as a permanent

I now write the determinant as a permanent. Recall that p−1=−1p-1=-1 in characteristic pp. Suppose that each cycle of a permutation σ∈Sk\sigma\in S_k receives one of r=p−1r=p-1 colours. Then σ\sigma is counted rcyc⁡(σ)=(−1)cyc⁡(σ)r^{\operatorname{cyc}(\sigma)}=(-1)^{\operatorname{cyc}(\sigma)} times, where cyc⁡(σ)\operatorname{cyc}(\sigma) is the number of cycles of σ\sigma. Since (−1)cyc⁡(σ)=(−1)ksgn⁡σ(-1)^{\operatorname{cyc}(\sigma)}=(-1)^k\operatorname{sgn}\sigma, this count gives the determinant up to sign. I realise the colours by rr copies of the matrix, and a small gate makes each index available in exactly one copy. The count gate is

Cr(z)=(diag⁡(z1,…,zr)11T0),per⁡Cr(z)=er−1(z).C_r(z)=\begin{pmatrix}\operatorname{diag}(z_1,\ldots,z_r)&1\\ \mathbf{1}^{T}&0\end{pmatrix},\qquad\operatorname{per} C_r(z)=e_{r-1}(z).

To see the formula, note that a perfect matching leaves out exactly one diagonal entry, say the jjth. It is then completed in one way, through the last row to column jj and from row jj to the last column.

Theorem 4.3. Let pp be an odd prime and r=p−1r=p-1.

(i) For every k×kk \times k matrix AA over a commutative KK-algebra there is a matrix B(A)B(A) of order (5p−4)k(5p-4)k, whose entries are entries of AA or constants, with per⁡B(A)=(−1)kdet⁡A\operatorname{per} B(A)=(-1)^k\det A.

(ii) For q=⌊(k−1)/3⌋q=\lfloor(k-1)/3\rfloor, the polynomial (−1)kGD(X)(-1)^kG_D(X) is the permanent of a matrix of order at most (5p+38)k(5p+38)k whose entries are entries of XX or constants. In particular, GDG_D is an affine restriction of per⁡n′\operatorname{per}'_n for some n′≤(5p+38)kn'\le(5p+38)k.

Proof. For (i), I take rr disjoint copies of AA, with rows and columns (c,i)(c,i) in copy cc. I add to each diagonal entry (c,i)(c,i) a marked summand 11, called the bypass. For each index ii, I add a count gate, and I couple the bypass at (c,i)(c,i) to the ccth diagonal entry of that gate by an equality gadget, for c=1,…,rc=1,\ldots,r. The gate makes exactly r−1r-1 of the bypasses at ii be used. Hence exactly one copy has the index ii free for the entries of AA. Let JcJ_c be the set of indices that are free in copy cc. Then (J1,…,Jr)(J_1,\ldots,J_r) runs over the ordered partitions of {1,…,k}\{1,\ldots,k\}, with empty parts allowed, and

per⁡B(A)=∑J1⊔⋯⊔Jr={1,…,k}∏c=1rper⁡AJc,Jc=∑σ∈Skrcyc⁡(σ)∏iAi,σ(i).\operatorname{per} B(A)=\sum_{J_1\sqcup\cdots\sqcup J_r=\{1,\ldots,k\}}\prod_{c=1}^{r}\operatorname{per} A_{J_c,J_c}=\sum_{\sigma\in S_k}r^{\operatorname{cyc}(\sigma)}\prod_i A_{i,\sigma(i)}.

The second equality holds because a term on the left is a permutation together with a colour for each of its cycles. In characteristic pp the right side is (−1)kdet⁡A(-1)^k\det A. The order is rkrk for the copies, (r+1)k(r+1)k for the gates and 3rk3rk for the gadgets, which is (5r+1)k(5r+1)k in all.

For (ii), I apply (i) to XX. For each ii, I add two vertices sis_i and tit_i, each with its own row and column, carrying marked loops of weights ziz_i and wiw_i. For every copy cc, I add the entries 11 from (c,i)(c,i) to sis_i and back, θi\theta_i from (c,i)(c,i) to tit_i, and 11 from tit_i to (c,i)(c,i). A new vertex can attach only to the copy in which ii is free. There it acts as an extra diagonal entry, equal to 11 for sis_i and to θi\theta_i for tit_i. Otherwise it uses its loop. Note that sis_i and tit_i cannot both attach at ii. With all zi=zz_i=z and all wi=ww_i=w, the colouring count of (i) gives

H(X,z,w)=(−1)kzkwkdet⁡(X+z−1I+w−1D),[zk−qwk−q]H=(−1)kGD(X).H(X,z,w)=(-1)^kz^kw^k\det(X+z^{-1}I+w^{-1}D),\qquad[z^{k-q}w^{k-q}]H=(-1)^kG_D(X).

Remark 4.2, applied to the loops ziz_i with Ek,k−qE_{k,k-q} and to the loops wiw_i with a second copy, selects this coefficient. The order is at most (5r+1)k+2k+2⋅20k=(5p+38)k(5r+1)k+2k+2\cdot20k=(5p+38)k. Finally, a row scaling removes the sign. □

The following were also checked by exact computation: the identities for JJ, the eight minors of CC used in Appendix C, (7), Lemma A.2 in orders 2, 4 and 6, part (i) over Q\mathbb{Q} for (p,k)=(3,2),(3,1),(5,1)(p,k)=(3,2),(3,1),(5,1), and the formula for HH with p=3p=3 and k≤2k\le2. The proofs do not depend on these checks.

Proofs of the main theorems

In this section, I combine the smooth restriction of Section B, its realisation as a permanent from Section 4, and the bounds of Section A.3. I begin with the smooth restriction in each characteristic. In odd characteristic pp and for k≥128k\ge128, Corollary 3.3 gives a form F=GD∘ΛF=G_D\circ\Lambda with V(F)V(F) smooth and the parameters (2). By Theorem 4.3(ii), FF is an affine restriction of per⁡n′\operatorname{per}_{n'} with n′≤Bpkn'\le B_pk. Over C\mathbb{C}, the construction of [4] gives a smooth form of the same degree dd in NC=⌊k2/100⌋N_{\mathbb{C}}=\lfloor k^2/100\rfloor variables as an affine restriction of per⁡n\operatorname{per}_n whenever n≥11kn\ge11k. Here NC−1≥k2/200N_{\mathbb{C}}-1\ge k^2/200. Whereas that construction selects a coefficient inside a permanent and moves the critical set bound to the permanent through characteristic two, the construction in characteristic pp uses GDG_D directly and then Theorem 4.3. In particular, no bound over C\mathbb{C} is reduced modulo pp.

Proof of Theorem 1.1. In characteristic pp, (2) gives (N−1)(d−1)≥k2(k−1)/63≥k3/64(N-1)(d-1)\ge k^2(k-1)/63\ge k^3/64. Hence Theorem 3.1(i) gives dc⁡(F)≥k3/(256e)\operatorname{dc}(F)\ge k^3/(256e) and pc⁡(F)≥k3/(512e)\operatorname{pc}(F)\ge k^3/(512e). The restrictions are fixed before any representation is chosen, and affine restriction preserves the closures of the classes. Hence these bounds hold for per⁡n\operatorname{per}_n whenever FF is a restriction of per⁡n\operatorname{per}_n.

I take k=⌊n/Bp⌋k=\lfloor n/B_p\rfloor. If n≥128Bpn\ge128B_p, then k≥128k\ge128 and k≥n/Bp−1≥127128⋅nBpk\ge n/B_p-1\ge\frac{127}{128}\cdot\frac{n}{B_p}. Padding with an identity block makes the permanent of order at most B‾pk≤n\overline{B}_pk\le n a restriction of per⁡n\operatorname{per}_n. Since 256⋅(128/127)3<270256\cdot(128/127)^3<270, this gives the two bounds.

Over C\mathbb{C}, I take k=⌊n/11⌋k=\lfloor n/11\rfloor. If n≥1408n\ge1408, then k≥128k\ge128 and k≥127128⋅n11k\ge\frac{127}{128}\cdot\frac{n}{11}. Further, (NC−1)(d−1)≥(k2/200)(k/4)=k3/800(N_{\mathbb{C}}-1)(d-1)\ge(k^2/200)(k/4)=k^3/800, so pc⁡‾(per⁡n)≥k3/(6400e)\overline{\operatorname{pc}}(\operatorname{per}_n)\ge k^3/(6400e). Since 113⋅6400⋅(128/127)3<8.8⋅10611^3\cdot6400\cdot(128/127)^3<8.8\cdot10^6, this gives the bound over C\mathbb{C}. Finally, exact complexity is at least border complexity. □

Proof of Theorem 1.2. I use the same FF. Since d≥k/3d \ge k/3, the condition a≤k/6a \le k/6 gives a≤d/2a \le d/2. Hence Theorem 3.1(ii) with c=1/2c = 1/2 gives dca⁡‾a(F)≥log⁡(4/3)(N−1)d/(16a)\overline{\operatorname{dca}}_a(F) \ge\log(4/3)(N-1)d/(16a) and pca⁡‾a(F)≥log⁡(4/3)(N−1)d/(32a)\overline{\operatorname{pca}}_a(F) \ge\log(4/3)(N-1)d/(32a). In characteristic pp, (2) gives (N−1)d≥k3/63(N-1)d \ge k^3/63. Over C\mathbb{C}, (NC−1)d≥k3/600(N_{\mathbb{C}}-1)d \ge k^3/600. Affine restriction keeps entry degrees, so the bounds pass to per⁡n\operatorname{per}_n. The ranges in nn follow from k≥n/12k \ge n/12 and k≥n/(2Bp)k \ge n/(2B_p). □\square

I end with the limits of these results. The constants in characteristic pp depend on pp through Bp3B_p^3. Hence the bounds improve on the quadratic bound of [1] only when pp is small compared with n1/3n^{1/3}. I claim nothing that is uniform in pp. I also claim nothing in characteristic two. Further, the cubic order is the limit of this method. A preliminary manuscript by Sheshadri [5] shows that arguments which read an invariant of a hypersurface through a corank one kernel system cannot prove more than a constant times NdNd for a form of degree dd in NN variables. For the restrictions used here, NdNd is of order n3n^3.

Use of artificial intelligence

The mathematics was developed with ChatGPT Astra during a discussion on OpenAI’s cubic bound. Some proofs were later refined in conversation with Claude Opus 5.5

Proof of the bound for smooth hypersurfaces

In this appendix, I prove Theorem 3.1. I begin by realising a border representation by a single matrix, and I prove two identities for Pfaffians.

Limits and Pfaffians

A border representation is a limit of matrices, and I want a single matrix that represents it. The next lemma provides one, with entries in a field of Laurent series.

Lemma A.1. If F∈D‾m,aF \in\overline{D}_{m,a}, respectively F∈P‾2m,aF \in\overline{P}_{2m,a}, then there is a matrix M(t,x)M(t,x), square of order mm, respectively alternating of order 2m2m, with entries in K((t))[x]K((t))[x] of xx-degree at most aa, such that P=det⁡MP = \det M, respectively P=Pf⁡MP = \operatorname{Pf} M, lies in K[[t]][x]K[[t]][x] and P(0,x)=FP(0,x) = F.

Proof. The class is the image of a space of matrices under a polynomial map. Hence its closure is irreducible, and it contains a curve through FF on which the image is dense. I lift this curve to a curve of matrices, complete the normalisation of the lifted curve, and choose a point over FF. After replacing the uniformiser by one of its roots if necessary, the completed local ring at this point is K[[t]]K[[t]]. The matrix entries then become Laurent series in tt. The coefficients of the image polynomial are regular at the chosen point, and there they equal the coefficients of FF. □\square

I write L‾\overline{L} for an algebraic closure of K((t))K((t)). Points over the field K((t))K((t)) are taken over L‾\overline{L}, and lengths are compared over K[[t]]K[[t]].

I now turn to Pfaffians. The Pfaffian of an alternating matrix MM of order 2m2m is a signed sum over the perfect matchings of {1,…,2m}\{1,\ldots,2m\}. A perfect matching splits these indices into mm pairs, and its term is the product of the entries MijM_{ij} over its pairs {i,j}\{i,j\} with i<ji<j. The Pfaffian has integer coefficients, so it makes sense in every characteristic. The matchings that contain a fixed pair {i,j}\{i,j\} contribute MijM_{ij} times the Pfaffian of the remaining indices, with one common sign. Therefore, as a polynomial in the independent entries MijM_{ij} with i<ji<j,

∂Pf⁡M∂Mij=±Pf⁡Mi^j^,(3)\frac{\partial\operatorname{Pf} M}{\partial M_{ij}}=\pm\operatorname{Pf} M_{\hat{i}\hat{j}}, \tag*{(3)}

where Mi^j^M_{\hat{i}\hat{j}} is MM with rows and columns ii and jj removed.

The next identity lets me reduce Pfaffians to determinants. It writes a Pfaffian, up to a factor, as the determinant of a submatrix of one order less.

Lemma A.2. Let MM be an alternating matrix of order 2m≥22m\ge2 over a commutative ring. Let EE be its principal submatrix on the indices 3,…,2m3,\ldots,2m, with Pf⁡E=1\operatorname{Pf} E=1 when m=1m=1, and let M′M' be the matrix of order 2m−12m-1 obtained from MM by deleting row 1 and column 2. Then

det⁡M′=−Pf⁡(E)Pf⁡(M).\det M'=-\operatorname{Pf}(E)\operatorname{Pf}(M).

Proof. Both sides are polynomials with integer coefficients in the entries MijM_{ij} with i<ji<j. Hence I may take these entries to be independent indeterminates over Q\mathbb{Q}. Then EE is invertible. Write

M=(AB−BTE)M=\begin{pmatrix} A & B \\ -B^{T} & E \end{pmatrix}

with AA of order two, and let B1B_1 and B2B_2 be the rows of BB. Put Σ=A+BE−1BT\Sigma=A+BE^{-1}B^{T} and

G=(I20E−1BTI).G=\begin{pmatrix} I_2 & 0 \\ E^{-1}B^{T} & I \end{pmatrix}.

Since ET=−EE^{T}=-E, multiplying out gives GTMG=Σ⊕EG^{T}MG=\Sigma\oplus E. Since det⁡G=1\det G=1, it follows that Pf⁡M=Σ12Pf⁡E\operatorname{Pf} M=\Sigma_{12}\operatorname{Pf} E. On the other hand,

M′=(M21B2−B1TE).M'=\begin{pmatrix} M_{21} & B_2 \\ -B_1^{T} & E \end{pmatrix}.

The Schur complement formula therefore gives det⁡M′=det⁡E⋅(M21+B2E−1B1T)=det⁡E⋅Σ21\det M'=\det E\cdot(M_{21}+B_2E^{-1}B_1^{T})=\det E\cdot\Sigma_{21}. Finally, det⁡E=(Pf⁡E)2\det E=(\operatorname{Pf} E)^2 and Σ21=−Σ12\Sigma_{21}=-\Sigma_{12}. Hence det⁡M′=−(Pf⁡E)2Σ12=−Pf⁡(E)Pf⁡(M)\det M'=-(\operatorname{Pf} E)^2\Sigma_{12}=-\operatorname{Pf}(E)\operatorname{Pf}(M). □\square

Note that the congruence in this proof also proves the identity Pf⁡M=Pf⁡E⋅Σ12\operatorname{Pf} M=\operatorname{Pf} E\cdot\Sigma_{12} in general.

The count for smooth hypersurfaces

In this subsection, I prove the count for smooth hypersurfaces that all three results rest on. Throughout, F∈K[x1,…,xN]F\in K[x_1,\ldots,x_N] is a form of degree d≥2d\ge2 with N≥2N\ge2, and V(F)⊂PN−1V(F)\subset\mathbb{P}^{N-1} is smooth, i.e., the partial derivatives of FF have no common zero on V(F)V(F).

Two lemmas make this count survive the passage to a limit. The first says that an isolated point of a limit does not disappear before the limit. Instead, its length is shared among isolated points of the family over K((t))K((t)).

Lemma A.3. Let YY be a smooth variety of dimension rr over an algebraically closed field, and let Z⊂Y×Spec⁡K[[t]]Z\subset Y\times\operatorname{Spec} K[[t]] be cut out locally by rr equations. Let bb be an isolated point of the special fibre Z0Z_0, i.e., of the member at t=0t=0, and let ℓ(b)\ell(b) be its length. Then the generic fibre ZηZ_\eta, i.e., the member over K((t))K((t)), has a finite set S(b)S(b) of isolated points over LL whose lengths add up to ℓ(b)\ell(b). The sets S(b)S(b) for different bb are disjoint. Further, a function on ZZ that does not vanish at bb vanishes at no point of S(b)S(b).

Proof. In local coordinates uu on YY at bb, the completed local ring of ZZ is B=K[[t,u]]/(f1,…,fr)B = K[[t,u]]/(f_1,\ldots,f_r). The ring B/tBB/tB is Artinian of length ℓ(b)\ell(b). Hence t,f1,…,frt,f_1,\ldots,f_r is a system of parameters of a regular local ring, and therefore a regular sequence in any order. In particular, tt is a nonzerodivisor on BB. Since BB is complete in the tt-adic topology and B/tBB/tB is finite, BB is a free K[[t]]K[[t]]-module of rank ℓ(b)\ell(b). Since bb is isolated in its fibre and K[[t]]K[[t]] is henselian, Spec⁡B\operatorname{Spec} B is an open and closed part of a neighbourhood of bb that is finite over K[[t]]K[[t]]. Its generic fibre consists of isolated points of ZηZ_\eta of total length ℓ(b)\ell(b), and I let S(b)S(b) be the set of these points. A point of a finite K[[t]]K[[t]]-scheme specialises to exactly one closed point, which gives disjointness. Finally, a unit of BB stays a unit after tt is inverted.

The second lemma is a form of Bézout’s theorem that counts only isolated points. It allows the intersection to have extra components, which I cannot rule out.

Lemma A.4. Let Y=Pb1×⋯×PbcY = \mathbb{P}^{b_1} \times\cdots\times\mathbb{P}^{b_c} over an algebraically closed field, let r=dim⁡Yr = \dim Y, and let D1,…,DrD_1,\ldots,D_r be effective divisors with multidegrees δ1,…,δr∈Z≥0c\delta_1,\ldots,\delta_r \in\mathbb{Z}_{\ge0}^c. Then the isolated points of D1∩⋯∩DrD_1 \cap\cdots\cap D_r have total length at most the coefficient β\beta of H1b1⋯HcbcH_1^{b_1}\cdots H_c^{b_c} in ∏i=1r(δi1H1+⋯+δicHc)\prod_{i=1}^r(\delta_{i1}H_1+\cdots+\delta_{ic}H_c). This holds whatever the rest of the intersection looks like.

Proof. Suppose first that rr divisors of these multidegrees meet in a finite scheme. Then their equations form a regular sequence at each point, and the local lengths are intersection multiplicities. Hence the total length is the intersection number β\beta, computed in Z[H1,…,Hc]/(H1b1+1,…,Hcbc+1)\mathbb{Z}[H_1,\ldots,H_c]/(H_1^{b_1+1},\ldots,H_c^{b_c+1}). The systems ∣OY(δi)∣|\mathcal{O}_Y(\delta_i)| are base point free, so general members Di′D'_i meet in a finite scheme. Let sis_i and si′s'_i be sections defining DiD_i and Di′D'_i, and let Di(λ)D_i(\lambda) be the divisor of si+λsi′s_i+\lambda s'_i. These divisors meet in a finite scheme at λ=1\lambda=1. Hence they also meet in a finite scheme over the generic point of the λ\lambda-line, and there the total length is β\beta. By Lemma A.3, with λ\lambda in place of tt, each isolated point of D1∩⋯∩DrD_1 \cap\cdots\cap D_r accounts for a separate part of that total, equal to its own length.

I now return to FF. The next lemma gives the scheme that I count.

Lemma A.5. For general w1,…,wN−2∈KNw_1,\ldots,w_{N-2} \in K^N, the scheme Z=V(F,∂w1F,…,∂wN−2F)⊂PN−1Z = V(F,\partial_{w_1}F,\ldots,\partial_{w_{N-2}}F) \subset\mathbb{P}^{N-1} is finite of length μ=d(d−1)N−2\mu= d(d-1)^{N-2}.

Proof. Since V(F)V(F) is smooth, the polars ∂wF\partial_wF have no common zero on V(F)V(F). Hence they form a base point free system on V(F)V(F), and general members cut V(F)V(F) properly. Bézout’s theorem for this proper intersection gives the length.

Note that ZZ need not be reduced. In characteristic pp it can have fewer points than its length. I never pass from ZZ to its set of points.

Now suppose that FF lies in D‾m,a\overline{D}_{m,a} or in P‾2m,a\overline{P}_{2m,a}, and let P=det⁡MP=\det M or P=Pf⁡MP=\operatorname{Pf}M be as in Lemma A.1. I choose coordinates in which xNx_N vanishes at no point of ZZ, and I put Π={xN=1}⊂AN\Pi=\{x_N=1\}\subset\mathbb{A}^N. Let

Z=V(P,∂w1P,…,∂wN−2P)⊂Π×Spec⁡K[[t]].\mathcal{Z}=V(P,\partial_{w_1}P,\ldots,\partial_{w_{N-2}}P)\subset\Pi\times\operatorname{Spec}K[[t]].

Here each derivative is taken on AN\mathbb{A}^N in the direction wj∈KNw_j\in K^N, and then restricted to Π\Pi. The special fibre of Z\mathcal{Z} is ZZ.

Lemma A.6. The generic fibre ZηZ_\eta has a finite set SS of isolated points over L\mathbb{L} whose lengths add up to μ\mu. At each z∈Sz\in S there is w0∈KNw_0\in K^N with ∂w0P(z)≠0\partial_{w_0}P(z)\ne0.

Proof. I apply Lemma A.3 to the N−1N-1 equations on Π\Pi at every point bb of ZZ, and I let SS be the union of the sets S(b)S(b). Since V(F)V(F) is smooth, there is w0w_0 with ∂w0F(b)≠0\partial_{w_0}F(b)\ne0. Since ∂w0P\partial_{w_0}P specialises to ∂w0F\partial_{w_0}F, the last part of Lemma A.3 gives ∂w0P(z)≠0\partial_{w_0}P(z)\ne0 for z∈S(b)z\in S(b).

:::

The next lemma lifts the points of SS to a space that also records kernel vectors. I state it for any square matrix whose determinant is a nonzero multiple of PP near SS. This is all that the Pfaffian case needs.

Lemma A.7. Let M′M' be a square matrix of order hh whose entries are polynomials in xx of degree at most aa with coefficients in K((t))K((t)). Suppose that det⁡M′=gP\det M'=gP for a polynomial gg that vanishes at no point of SS. Then

d(d−1)N−2≤βa(h):=[HN−1Uh−1Vh−1](aH+V)h(aH+U)h−1((a−1)H+U+V)N−2.(4)d(d-1)^{N-2}\leq\beta_a(h):=[H^{N-1}U^{h-1}V^{h-1}](aH+V)^h(aH+U)^{h-1}((a-1)H+U+V)^{N-2}. \tag*{(4)}

Proof. Let z∈Sz\in S. Since P(z)=0P(z)=0, the derivative of det⁡M′\det M' at zz in the direction w0w_0 is g(z) ∂w0P(z)g(z)\,\partial_{w_0}P(z), which is nonzero. The derivative of a determinant with respect to an entry is a cofactor. Hence some cofactor of M′(z)M'(z) is nonzero, and M′(z)M'(z) has rank exactly h−1h-1. Its right and left kernels are lines [vz][v_z] and [uz][u_z], and adj⁡M′(z)=c vzuzT\operatorname{adj}M'(z)=c\,v_z u_z^T with c≠0c\ne0. A constant change of basis in the column space multiplies det⁡M′\det M' by a nonzero constant. Hence I may assume that the last coordinate of every vzv_z is nonzero.

I homogenise the entries of M′M' to degree aa with xNx_N, and those of Mw′=∂wM′M'_w=\partial_wM' to degree a−1a-1. On Y=PN−1×Puh−1×Pvh−1Y=\mathbb{P}^{N-1}\times\mathbb{P}^{h-1}_u\times\mathbb{P}^{h-1}_v consider

M′v=0,(uTM′)j=0 (j<h),uTMwi′v=0 (1≤i≤N−2).(5)M'v=0,\qquad(u^TM')_j=0\ (j<h),\qquad u^TM'_{w_i}v=0\ (1\leq i\leq N-2). \tag*{(5)}

These are hh, h−1h-1 and N−2N-2 equations of multidegrees (a,0,1)(a,0,1), (a,1,0)(a,1,0) and (a−1,1,1)(a-1,1,1), so there are dim⁡Y\dim Y equations in all. I claim that ζz=(z,[uz],[vz])\zeta_z=(z,[u_z],[v_z]) is an isolated point of (5), and that its local scheme is isomorphic to that of ZηZ_\eta at zz. The points ζz\zeta_z are distinct, since their first coordinates are. Hence the claim, Lemma A.6 and Lemma A.4 give μ≤βa(h)\mu\leq\beta_a(h).

To prove the claim, I work in the local ring of YY at ζz\zeta_z, on the charts xN=1x_N=1, vh=1v_h=1 and ui=1u_i=1 for an index ii with (uz)i≠0(u_z)_i\ne0. The identity

vh(uTM′)h=uT(M′v)−∑j<hvj(uTM′)jv_h(u^TM')_h=u^T(M'v)-\sum_{j<h}v_j(u^TM')_j

puts the omitted equation (uTM′)h=0(u^TM')_h=0 in the ideal of (5). The (i,h)(i,h) cofactor of M′(z)M'(z) is c(vz)h(uz)ic(v_z)_h(u_z)_i, which is nonzero. Hence, after moving row ii and column hh to the front, I can write

M′=(αργE′),u=(1u′),v=(1v′),M'=\begin{pmatrix}\alpha&\rho\\\gamma&E'\end{pmatrix},\qquad u=\begin{pmatrix}1\\u'\end{pmatrix},\qquad v=\begin{pmatrix}1\\v'\end{pmatrix},

with E′E' invertible near zz. The kernel equations say that v′=−E′−1γv'=-E'^{-1}\gamma, that u′T=−ρE′−1u'^T=-\rho E'^{-1}, and that σ=0\sigma=0, where σ=α−ρE′−1γ\sigma=\alpha-\rho E'^{-1}\gamma. Differentiating gives ∂wσ=uT(∂wM′)v\partial_w\sigma=u^T(\partial_wM')v for every direction ww. Therefore, after u′u' and v′v' are eliminated, the system on the base is σ=∂w1σ=⋯=∂wN−2σ=0\sigma=\partial_{w_1}\sigma=\cdots=\partial_{w_{N-2}}\sigma=0. Finally, det⁡M′=±det⁡E′⋅σ=gP\det M'=\pm\det E'\cdot\sigma=gP, where det⁡E′\det E' and gg are units. Hence σ\sigma is a unit multiple of PP, and the ideals (σ,∂w1σ,…)(\sigma,\partial_{w_1}\sigma,\ldots) and (P,∂w1P,…)(P,\partial_{w_1}P,\ldots) coincide.

Proposition A.8. If dca‾a(F)≤m\overline{\mathrm{dca}}_a(F)\leq m, then d(d−1)N−2≤βa(m)d(d-1)^{N-2}\leq\beta_a(m). If pca‾a(F)≤m\overline{\mathrm{pca}}_a(F)\leq m, then d(d−1)N−2≤βa(2m−1)d(d-1)^{N-2}\leq\beta_a(2m-1).

Proof. For determinants, I take M′=MM'=M and g=1g=1 in Lemma A.7. For Pfaffians, fix z∈Sz\in S. Since ∂w0P(z)≠0\partial_{w_0}P(z)\ne0, the chain rule and (3) give indices i<ji<j with Pf⁡Mij^(z)≠0\operatorname{Pf}M_{\widehat{ij}}(z)\ne0. Replacing MM by QTMQQ^TMQ for a constant Q∈GL2m(K)Q\in GL_{2m}(K) multiplies PP by det⁡Q\det Q. This changes none of the schemes above, and it keeps the entry degrees. For each zz, the Pfaffian of the principal submatrix of QTM(z)QQ^TM(z)Q on the indices 3,…,2m3,\ldots,2m is a polynomial in QQ. It does not vanish at a permutation matrix that sends ii and jj to 11 and 22. Since SS is finite, one QQ makes all of these Pfaffians nonzero. With this QQ, let EE be that principal submatrix and M′M' the matrix MM with row 1 and column 2 deleted. By Lemma A.2, det⁡M′=−Pf⁡(E)P\det M'=-\operatorname{Pf}(E)P. Hence Lemma A.7 applies with h=2m−1h=2m-1 and g=−Pf⁡Eg=-\operatorname{Pf}E.

Numerical bounds and sharpness

Proposition A.8 is an inequality between dd, NN and the order of the matrix. In this subsection, I solve it for the order, which proves Theorem 3.1. I then check on Fermat forms that the answer has the right size. For affine linear entries, the coefficient β1(h)\beta_1(h) is bounded by a single binomial coefficient.

Proof of Theorem 3.1. Put r=N−1r=N-1 and κ=2h−1\kappa=2h-1. All coefficients of the polynomial in (4) are nonnegative. Hence setting U=VU=V and then dehomogenising can only increase the coefficient, and

βa(h)≤[tr](1+at)κ(2+(a−1)t)r−1.\beta_a(h) \le[t^r](1+at)^\kappa(2+(a-1)t)^{r-1}.

For a=1a=1 the right hand side is 2r−1(κr)2^{r-1}\binom{\kappa}{r}. With h=mh=m for determinants and h=2m−1h=2m-1 for Pfaffians, Proposition A.8 gives the two inequalities in (i). Note that d(d−1)r−1≥(d−1)rd(d-1)^{r-1}\ge(d-1)^r and (κr)≤(eκ/r)r\binom{\kappa}{r}\le(e\kappa/r)^r. Hence the inequalities imply d−1≤2(r−1)/reκ/r≤2eκ/rd-1\le2^{(r-1)/r}e\kappa/r\le2e\kappa/r, i.e., κ≥r(d−1)/(2e)\kappa\ge r(d-1)/(2e). Substituting κ=2m−1\kappa=2m-1 and κ=4m−3\kappa=4m-3 gives the bounds on dc⁡‾\overline{\operatorname{dc}} and pc⁡‾\overline{\operatorname{pc}}.

For (ii), nonnegativity gives [tr]f(t)≤f(τ)/τr[t^r]f(t)\le f(\tau)/\tau^r for every τ>0\tau>0. I take τ=4/(d−a)\tau=4/(d-a), which is positive because a≤cd<da\le cd<d. Then a−1+2/τ=(d+a−2)/2a-1+2/\tau=(d+a-2)/2, and rearranging gives

κlog⁡(1+4ad−a)≥(N−2)log⁡2(d−1)d+a−2+log⁡4dd−a.\kappa\log\left(1+\frac{4a}{d-a}\right)\ge(N-2)\log\frac{2(d-1)}{d+a-2}+\log\frac{4d}{d-a}.

Since a≤cda\le cd, it follows that 2(d−1)/(d+a−2)≥2/(1+c)2(d-1)/(d+a-2)\ge2/(1+c). Further, the last term is at least log⁡4\log4, which is at least LcL_c, and the left side is at most 4aκ/((1−c)d)4a\kappa/((1-c)d). Hence κ≥(N−1)(1−c)Lcd/(4a)\kappa\ge(N-1)(1-c)L_cd/(4a), which is (ii). The bound ⌈d/a⌉\lceil d/a\rceil holds because a determinant of order mm, or a Pfaffian of half order mm, with entries of degree at most aa has degree at most amam, and so do its limits. □

I now show that these bounds have the right order of growth. To do so, I use the Fermat forms.

Proposition A.9. If the characteristic does not divide dd, the Fermat form FN,d=x1d+⋯+xNdF_{N,d}=x_1^d+\cdots+x_N^d defines a smooth hypersurface, and both dc⁡‾a(FN,d)\overline{\operatorname{dc}}_a(F_{N,d}) and pc⁡‾a(FN,d)\overline{\operatorname{pc}}_a(F_{N,d}) are at most N(⌈d/a⌉−1)+1N(\lceil d/a\rceil-1)+1. So Theorem 3.1(i) is tight up to the factor 4e4e for determinants and 8e8e for Pfaffians, and (ii) is tight up to a constant depending on cc.

Proof. The gradient (dxid−1)i(d x_i^{d-1})_i vanishes only at the origin, so V(FN,d)V(F_{N,d}) is smooth. Let h=⌈d/a⌉h=\lceil d/a\rceil. Take NN directed paths of hh edges from a source to a sink that share no other vertices. Label the iith path by h−1h-1 copies of xiax_i^a and one copy of xid−a(h−1)x_i^{d-a(h-1)}. Then the sum over the paths of the products of their labels is FN,dF_{N,d}. Let AGA_G be the adjacency matrix of this graph in a topological order. Then det⁡(I−AG)=1\det(I-A_G)=1, and the (source, sink) entry of (I−AG)−1(I-A_G)^{-1} is FN,dF_{N,d}. By the cofactor formula, deleting the row of the sink and the column of the source gives, up to sign, a determinantal representation of order N(h−1)+1N(h-1)+1 with entries of degree at most aa. Equation (1) gives the Pfaffian bound. □

Recall the forms ∑ixip+1\sum_i x_i^{p+1} from the introduction. More generally, in characteristic pp the forms ∑ixipb+1\sum_i x_i^{p^b+1} are smooth, and their general polars are pbp^bth powers of linear forms. Hence their polar scheme has pb+1p^b+1 points, but its length is (pb+1)pb(N−2)(p^b+1)p^{b(N-2)}. Note that a count of points instead of lengths would lose the factor pb(N−2)p^{b(N-2)} here. Theorem 3.1 applies to these forms, and by Proposition A.9 it is tight on them.

Proof of the critical set bound

In this appendix, I prove Theorem 3.2 and Corollary 3.3. I keep the notation of Section 3.

The spectral curve. For a matrix XX, let

M=sIk+tD+uX,FX(s,t,u)=det⁡M,CX=V(FX)⊂P2.M=sI_k+tD+uX,\qquad F_X(s,t,u)=\det M,\qquad C_X=V(F_X)\subset\mathbb{P}^2.

Note that det⁡(X+sI+tD)=FX(s,t,1)\det(X+sI+tD)=F_X(s,t,1), and that the coefficient of sqtqs^qt^q there has degree dd in XX. Hence GD(X)=[sq+tud]FXG_D(X)=[s^{q+t}u^d]F_X. I need three properties of C=CXC=C_X. Firstly, CC is reduced. Indeed, on the line u=0u=0 the form FXF_X equals ∏i(s+tθi)\prod_i(s+t\theta_i), a product of distinct linear forms. A repeated factor of FXF_X would either be divisible by uu or restrict to a repeated factor on u=0u=0. Hence FXF_X has no repeated factor. Secondly, every component of CC passes through one of the points Pi=[−θi:1:0]P_i=[-\theta_i:1:0]. At PiP_i the matrix MM is diagonal with exactly one zero entry, so it has rank k−1k-1. Thirdly, FXF_X is monic in ss. Hence the projection π:C→P1\pi:C\to\mathbb{P}^1, [s:t:u]↦[t:u][s:t:u]\mapsto[t:u], is finite and flat of degree kk, and π∗OC=⨁j=0k−1OP1(−j)\pi_*\mathcal{O}_C=\bigoplus_{j=0}^{k-1}\mathcal{O}_{\mathbb{P}^1}(-j). A general fibre of π\pi consists of kk distinct points, because the discriminant in ss does not vanish at u=0u=0. I put E=π∗OC(k−1)=⨁jOP1(k−1−j)\mathcal{E}=\pi_*\mathcal{O}_C(k-1)=\bigoplus_j\mathcal{O}_{\mathbb{P}^1}(k-1-j).

The adjugate scheme. The adjugate adj⁡M\operatorname{adj}M is the transposed matrix of cofactors, so Madj⁡M=det⁡M⋅IM\operatorname{adj}M=\det M\cdot I. Its entries are forms of degree k−1k-1. Let J⊆OC\mathcal{J}\subseteq\mathcal{O}_C be the ideal that they generate on CC, and let Z=VC(J)Z=V_C(\mathcal{J}) be the subscheme of CC where they all vanish. Since adj⁡M\operatorname{adj}M is nonzero at the points PiP_i, the scheme ZZ is finite. I keep its full scheme structure.

The next lemma shows that, in degree k−1k-1, the forms that vanish on ZZ are exactly the linear combinations of the adjugate entries.

Lemma B.1. Every form of degree k−1k-1 in s,t,us,t,u that vanishes on ZZ is a KK-linear combination of the entries of adj⁡M\operatorname{adj}M.

Proof. Put A=tD+uXA=tD+uX, and let ψ:Mat⁡k(OP1)→E\psi:\operatorname{Mat}_k(\mathcal{O}_{\mathbb{P}^1})\to\mathcal{E} send YY to tr⁡(Yadj⁡M)\operatorname{tr}(Y\operatorname{adj}M). On CC, Madj⁡M=0M\operatorname{adj}M=0, so sadj⁡M=−Aadj⁡Ms\operatorname{adj}M=-A\operatorname{adj}M. Hence, over each chart, the span of the adjugate entries is stable under multiplication by the affine coordinate ss. Since ss generates the coordinate ring of CC over the chart, this span is already the ideal that the entries generate. Therefore the image of ψ\psi is π∗(J(k−1))\pi_*(\mathcal{J}(k-1)).

Next I study the kernel of ψ\psi. The commutators AY−YAAY-YA with Y∈Mat⁡k(O(−1))Y\in\operatorname{Mat}_k(\mathcal{O}(-1)) lie in ker⁡ψ\ker\psi, because adj⁡M\operatorname{adj}M commutes with AA. At the point [t:u]=[1:0][t:u]=[1:0] these commutators fill the image of the map Y↦DY−YDY\mapsto DY-YD, which has dimension k2−kk^2-k. At the same point ψ\psi has rank kk. Indeed, it sends the diagonal matrix units to the polynomials ∏j≠i(y+θj)\prod_{j\ne i}(y+\theta_j), which are linearly independent modulo ∏j(y+θj)\prod_j(y+\theta_j). Hence the sheaf I\mathcal{I} of commutators and ker⁡ψ\ker\psi have the same generic rank, and ker⁡ψ/I\ker\psi/\mathcal{I} is a torsion sheaf. As a quotient of O(−1)k2\mathcal{O}(-1)^{k^2}, the sheaf I\mathcal{I} satisfies H1(I)=0H^1(\mathcal{I})=0. Hence H1(ker⁡ψ)=0H^1(\ker\psi)=0 as well. Therefore the constant matrices map onto H0(P1,im⁡ψ)=H0(C,J(k−1))H^0(\mathbb{P}^1,\operatorname{im}\psi)=H^0(C,\mathcal{J}(k-1)).

Now let PP be a form of degree k−1k-1 that vanishes on ZZ. Then PP is a section of J(k−1)\mathcal{J}(k-1), so it agrees on CC with a constant combination of adjugate entries. Their difference is a form of degree k−1k-1 that is divisible by FXF_X, which has degree kk. Hence the difference is zero. □

The next lemma is where the condition X∈ΓDX\in\Gamma_D enters. It shows that ZZ is large.

Lemma B.2. If X∈ΓDX\in\Gamma_D, then length⁡Z≥T\operatorname{length}Z\ge T.

Proof. The derivative of a determinant with respect to an entry is a cofactor. Hence ∂FX/∂Xji=u(adj⁡M)ji\partial F_X/\partial X_{ji}=u(\operatorname{adj}M)_{ji} over any ring. Consider the linear functional λ(P)=[sqtquc]P\lambda(P)=[s^qt^qu^c]P on forms of degree k−1k-1. The equations of ΓD\Gamma_D say that λ\lambda kills every adjugate entry. By Lemma B.1, λ\lambda therefore kills every form of degree k−1k-1 that vanishes on ZZ.

Now let P=∑aijℓsitjuℓP=\sum a_{ij\ell}s^it^ju^\ell be a form of degree qq that vanishes on ZZ, and fix an exponent (i,j,ℓ)(i,j,\ell). The form sq−itq−juc−ℓPs^{q-i}t^{q-j}u^{c-\ell}P has degree $2q+c=k-1$, and it vanishes on ZZ. Note that its exponents are nonnegative, since c≥qc\ge q. Its value under λ\lambda is aijℓa_{ij\ell}, which must therefore be zero. Hence $P=0.

In other words, the forms of degree qq restrict injectively to ZZ. They form a space of dimension TT, so T≤length⁡ZT \le\operatorname{length} Z. Note that this argument never divides by an integer.

The scheme ZZ lies over the singular points of CC. The next lemma bounds its length by the normalisation defect.

Lemma B.3. length⁡Z≤δ(C)\operatorname{length} Z \le\delta(C).

Proof. Both sides are sums of contributions over the points of P1\mathbb{P}^1, so I may work over one point. Let SS be the local ring of P1\mathbb{P}^1 at that point. It is a discrete valuation ring with residue field KK. Over SS the curve is Spec⁡B\operatorname{Spec} B, where B=S[y]/(f)B = S[y]/(f) and f=det⁡(yI+A0)f = \det(yI + A_0) for some A0∈Mat⁡k(S)A_0 \in\operatorname{Mat}_k(S). Further, OC/J\mathcal{O}_C/J becomes B/JB/J, where JJ is the ideal generated by the entries of adj⁡(yI+A0)\operatorname{adj}(yI + A_0). Let RR be the normalisation of BB. It is finite over SS, since ff has distinct roots over the fraction field of SS. The conductor c={x∈B:xR⊆B}\mathfrak{c} = \{x \in B : xR \subseteq B\} is the largest ideal of RR that lies in BB. It suffices to show that c⊆J\mathfrak{c} \subseteq J and that length⁡S(B/c)=length⁡S(R/B)\operatorname{length}_S(B/\mathfrak{c}) = \operatorname{length}_S(R/B).

I begin with the inclusion. Let L\mathcal{L} be the cokernel of yI+A0yI + A_0 on BkB^k. Since ff has distinct roots over the fraction field of SS, L\mathcal{L} is a torsion free BB-module of rank one. A BB-linear map L→B\mathcal{L} \to B is a row bb with b(yI+A0)≡0b(yI + A_0) \equiv0 modulo ff. Lifting bb to S[y]S[y] and multiplying by the adjugate shows that bb is a combination of the rows of adj⁡(yI+A0)\operatorname{adj}(yI + A_0). Hence JJ is the image of the evaluation map Hom⁡B(L,B)⊗L→B\operatorname{Hom}_B(\mathcal{L}, B) \otimes\mathcal{L} \to B. Since KK is infinite, some ℓ0∈L\ell_0 \in\mathcal{L} generates RLR\mathcal{L} at every maximal ideal of RR. Then L′=ℓ0−1L\mathcal{L}' = \ell_0^{-1}\mathcal{L} satisfies B⊆L′⊆RB \subseteq\mathcal{L}' \subseteq R. For x∈cx \in\mathfrak{c}, multiplication by xx maps L′≅L\mathcal{L}' \cong\mathcal{L} into BB and sends 11 to xx. Hence x∈Jx \in J.

For the lengths, let λ0:B→S\lambda_0 : B \to S read off the coefficient of yk−1y^{k-1} in the remainder modulo ff. In the basis 1,y,…,yk−11,y,\ldots,y^{k-1}, the pairing (x,x′)↦λ0(xx′)(x,x') \mapsto\lambda_0(xx') has a Gram matrix that is zero above the antidiagonal and equal to one on it. Hence the pairing identifies BB with its dual over SS. Under this identification, Hom⁡B(R,B)\operatorname{Hom}_B(R,B) becomes the dual of RR. Further, evaluation at 11 identifies Hom⁡B(R,B)\operatorname{Hom}_B(R,B) with c\mathfrak{c}. Comparing the elementary divisors of B⊆RB \subseteq R now gives length⁡(B/c)=length⁡(R/B)\operatorname{length}(B/\mathfrak{c}) = \operatorname{length}(R/B).

The next lemma counts the curves with a large defect. It is the only place where I use an outside result.

Lemma B.4. In PH0(P2,O(k))\mathbb{P}H^0(\mathbb{P}^2,\mathcal{O}(k)), the reduced curves CC with δ(C)≥T\delta(C) \ge T form a constructible set of dimension at most k(k+3)/2−Tk(k+3)/2 - T.

Proof. In every characteristic, the integral plane curves of degree bb whose normalisation has genus gg form a locally closed set. When this set is nonempty, its dimension is 3b+g−13b+g-1 [2]. Now consider a reduced curve of degree kk with components of degrees bib_i and normalisation genera gig_i, for 1≤i≤α1 \le i \le\alpha. Comparing the Euler characteristics of OC\mathcal{O}_C and ν∗OC~\nu_*\mathcal{O}_{\widetilde{C}} gives δ(C)=(k−1)(k−2)2−∑igi+α−1\delta(C) = \frac{(k-1)(k-2)}{2} - \sum_i g_i + \alpha- 1. By multiplying equations, the reduced curves of a given type form a set of dimension at most ∑i(3bi+gi−1)=3k+∑igi−α\sum_i(3b_i+g_i-1) = 3k+\sum_i g_i-\alpha. This number equals k(k+3)/2−δ(C)k(k+3)/2-\delta(C). Since there are finitely many types, the lemma follows.

Finally, I show that few matrices share the same curve.

Lemma B.5. For a fixed curve CC, the matrices XX with CX=CC_X = C form a set of dimension at most N0=k(k−1)/2N_0 = k(k-1)/2.

Proof. Let rX=(1,…,1)adj⁡Mr_X = (1,\ldots,1)\operatorname{adj} M, a row of kk forms of degree k−1k-1, and let ZX′⊂CZ'_X \subset C be the subscheme where its entries vanish. I first show that ZX′Z'_X has length N0N_0 and that it determines XX. The row defines a map ρX:OP1k→E\rho_X : \mathcal{O}_{\mathbb{P}^1}^k \to\mathcal{E}. At [1:0][1:0] this map sends the iith basis vector to ∏j≠i(y+θj)\prod_{j \ne i}(y+\theta_j). This is an isomorphism, and it does not depend on XX. Hence ρX\rho_X is injective, and its cokernel has length χ(E)−k=N0\chi(\mathcal{E}) - k = N_0. As in the proof of Lemma B.1, srX=−rX(tD+uX)s r_X = -r_X(tD + u_X) on CC. Therefore the image of ρX\rho_X is π∗\pi_* of the twisted ideal of ZX′Z'_X, and length⁡ZX′=N0\operatorname{length} Z'_X = N_0. Now suppose that ZX′=ZX′′Z'_X = Z'_{X'}. Then ρX\rho_X and ρX′\rho_{X'} have the same image, so they differ by a constant automorphism of Ok\mathcal{O}^k. This automorphism is the identity, because the two maps agree at [1:0][1 : 0]. Hence rX=rX′r_X = r_{X'}. Subtracting the relations sr=−r(tD+uX)s r = -r(tD + u_X) for XX and for X′X' gives urX(X−X′)=0u r_X(X - X') = 0. Since ρX\rho_X is injective, X=X′X = X'.

It remains to show that dim⁡Hilb⁡N0(C)≤N0\dim\operatorname{Hilb}_{N_0}(C) \leq N_0, where Hilb⁡N0(C)\operatorname{Hilb}_{N_0}(C) is the space of subschemes of CC of length N0N_0. Consider a subscheme of A2\mathbb{A}^2 of length ℓ\ell supported at one point, together with a basis of its coordinate ring. These data determine two commuting nilpotent ℓ×ℓ\ell\times\ell matrices, namely multiplication by the two coordinates, and a cyclic vector, namely the image of 11. Conversely, the matrices and the vector determine the subscheme and the basis. Now let AA be nilpotent with a centraliser of dimension jj. Its conjugacy class has dimension ℓ2−j\ell^2 - j. The nilpotent matrices that commute with AA satisfy det⁡=0\det= 0, which is a nontrivial equation on the centraliser. Hence these triples form a set of dimension at most ℓ2−1+ℓ\ell^2 - 1 + \ell. The basis accounts for ℓ2\ell^2 of these dimensions, so the subschemes form a family of dimension at most ℓ−1\ell- 1. Adding one parameter for each support point on CC gives dim⁡Hilb⁡N0(C)≤N0\dim\operatorname{Hilb}_{N_0}(C) \leq N_0. Finally, the pairs (X,Z′)(X, Z') with rX∣Z′=0r_X|_{Z'} = 0 form a closed set. This set maps onto {X:CX=C}\{X : C_X = C\}. It has at most one point over each Z′Z', since Z′⊆ZX′Z' \subseteq Z'_X and both have length N0N_0.

Proof of Theorem 3.2. By Lemmas B.2 and B.3, the map X↦CXX \mapsto C_X sends ΓD\Gamma_D into the set of reduced curves with δ≥T\delta\geq T. By Lemma B.4, this set has dimension at most k(k+3)/2−Tk(k + 3)/2 - T. By Lemma B.5, the fibres of the map have dimension at most k(k−1)/2k(k - 1)/2. Hence dim⁡ΓD≤k(k+3)/2−T+k(k−1)/2=k2+k−T\dim\Gamma_D \leq k(k + 3)/2 - T + k(k - 1)/2 = k^2 + k - T.

Note that none of these steps depends on the characteristic. The kk distinct points of a general fibre of π\pi come from the fixed fibre at u=0u = 0. The pairing in Lemma B.3 uses a coefficient and not a trace. Lemma B.5 uses a fixed basis at [1:0][1 : 0] and Jordan forms.

Proof of Corollary 3.3. Put v=k2v = k^2 and Δ=T−k=N\Delta= T - k = N. The singular set of V(GD)⊂Pv−1V(G_D) \subset\mathbb{P}^{v-1} lies in the projectivisation of ΓD\Gamma_D. By Theorem 3.2, it has dimension at most v−1−Δv - 1 - \Delta. In the Grassmannian of NN dimensional subspaces, the subspaces through a singular point form a set of dimension at most N(v−N)+N−1−Δ=N(v−N)−1N(v - N) + N - 1 - \Delta= N(v - N) - 1. At a smooth point [x][x], Euler’s identity gives x∈ker⁡dGD(x)x \in\ker dG_D(x) in every characteristic. Over all smooth points, the subspaces HH with x∈H⊆ker⁡dGD(x)x \in H \subseteq\ker dG_D(x) form a set of dimension at most N(v−N)−1N(v - N) - 1. Hence a general subspace meets V(GD)V(G_D) only at smooth points and is tangent nowhere. Therefore V(F)V(F) is smooth. Further, F≠0F \neq0, since otherwise the subspace would be tangent everywhere.

For (2), note that 3q≤k−13q \leq k - 1 and q+1≥k/3q + 1 \geq k/3. Hence T≥(q+1)2/2≥k2/18T \geq(q + 1)^2/2 \geq k^2/18, and N−1≥k2/18−k−1≥k2/21N - 1 \geq k^2/18 - k - 1 \geq k^2/21, where the last step uses k≥127k \geq127. Further, d=k−2q≥(k+2)/3d = k - 2q \geq(k + 2)/3, which gives the other two inequalities.

Construction of the selectors

In this appendix, I build the equality gadget and the selector of § 4, and I prove Proposition 4.1.

An equality gadget

Take two marked entries of weights ww and 11 in distinct rows and distinct columns. Delete them, and add three new rows and three new columns carrying

J=(−1−11−1−11−12−12−12).J=\begin{pmatrix} -1 & -1 & 1\\ -1 & -1 & 1\\ -\frac{1}{2} & -\frac{1}{2} & -\frac{1}{2} \end{pmatrix}.

Join the row of the first entry to new column 1 with weight ww, and the row of the second entry to new column 2 with weight 1. Join new row 1 to the column of the first entry with weight −2-2, and new row 2 to the column of the second entry with weight 1.

A direct check gives three facts. Firstly, per⁡J=1\operatorname{per} J=1. Secondly, each of the four 2×22 \times2 permanents left after deleting one of the first two rows and one of the first two columns of JJ is 0. Thirdly, deleting the first two rows and columns of JJ leaves J33=−12J_{33}=-\frac{1}{2}. Now fix a matching of everything outside the gadget. The gadget contributes 1 if neither marked entry is used, and w⋅(−2)⋅(−12)=ww\cdot(-2)\cdot\left(-\frac{1}{2}\right)=w if both are used. In the two mixed cases it contributes 0. Hence the gadget forces the two selection bits to agree, and it introduces no other factor. Since the computation is entrywise, several gadgets may share outside rows and columns.

The full adder and the circuit

A full adder takes three bits aa, bb, cc and outputs two bits ss, uu with a+b+c=s+2ua+b+c=s+2u, where the sum is taken in the integers. My full adder is a permanent of order eleven, built from

C=(0011101000011101).C=\begin{pmatrix} 0 & 0 & 1 & 1\\ 1 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ 1 & 1 & 0 & 1 \end{pmatrix}.

For a set II of the first three columns and a set OO of the first three rows, delete them from CC. Suppose that OO is one of ∅\emptyset, {1}\{1\}, {2,3}\{2,3\}, {1,2,3}\{1,2,3\}, and that ∣I∣=∣O∣|I|=|O|. Then the permanent of what remains is 1. Read the deleted columns as the input bits aa, bb, cc, and the deleted rows as the output bits (s,u,u)(s,u,u). Then these eight cases are exactly the solutions of a+b+c=s+2ua+b+c=s+2u. Table 1 lists them.

Rows deletedColumns deleteda+b+ca+b+c(s,u)(s,u)Term in (7)
∅\emptyset∅\emptyset0(0,0)(0,0)1
{1}\{1\}one column1(1,0)(1,0)sasa, sbsb, scsc
{2,3}\{2,3\}two columns2(0,1)(0,1)uabuab, uacuac, ubcubc
{1,2,3}\{1,2,3\}all three3(1,1)(1,1)suabcsuabc

Table 1. The eight cases of the full adder.

To turn CC into a full adder, I put a copy of CC and a copy of CTC^{T} side by side. For j=1,2,3j=1,2,3, I join row jj of the second copy to column jj of the first by an input edge, and row jj of the first copy to column jj of the second by an output edge. The completions inside the two copies then contribute the square of a permanent of the kind above. I give the input edges the weights aa, bb, cc and output edge 1 the weight ss. Finally, I couple output edges 2 and 3 by an equality gadget, with uu on the first of them. In blocks of sizes 4, 4 and 3, the result is

A=(CsE11U(u)Δ(a,b,c)CT00VJ)(6)\mathcal{A}= \begin{pmatrix} C & sE_{11} & U(u)\\ \Delta(a,b,c) & C^{T} & 0\\ 0 & V & J \end{pmatrix} \tag*{(6)}
U(u)=(000u00010000),V=(0−20000100000),U(u)= \begin{pmatrix} 0 & 0 & 0\\ u & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 0 \end{pmatrix}, \qquad V= \begin{pmatrix} 0 & -2 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 \end{pmatrix},

where Δ(a,b,c)=diag⁡(a,b,c,0)\Delta(a,b,c)=\operatorname{diag}(a,b,c,0) and E11E_{11} is a 4×44 \times4 matrix unit. The gadget keeps only the four output sets listed above, and the row and column counts force ∣I∣=∣O∣|I|=|O|. Hence

per⁡A=1+s(a+b+c)+u(ab+bc+ca)+suabc.(7)\operatorname{per}\mathcal{A}=1+s(a+b+c)+u(ab+bc+ca)+suabc. \tag*{(7)}

Note that the five variables lie in five different rows and five different columns.

Next I describe the circuit. I put the LL input bits in the column of weight 1, and I treat the columns from the lowest weight up. While a column holds at least three live bits, I feed three of them to a full adder. Its sum bit stays in the column, and its carry moves to the next column. Each adder removes one live bit, and every column ends with one or two bits. What remains are two binary numbers of some length HH. A ripple carry adder of HH further full adders turns them into the H+1H+1 binary digits of y1+⋯+yLy_1+\cdots+y_L. If the first phase leaves B≥HB\ge H bits, it has used L−BL-B adders. Hence there are at most LL adders in all. Note that the circuit is acyclic, and that every intermediate bit is used exactly once.

Proof of Proposition 4.1. I replace each adder by a copy of A\mathcal{A}, and I couple the two ends of every internal wire by an equality gadget. I delete the marked entries that carry a constant input 0 or an output digit 0 of qq. I delete the row and column of each output digit 1 of qq, which forces that entry to be used. Finally, I put ziz_i on the input entry of the bit yiy_i. By (7) and the gadget, an assignment of all selection bits has weight one if it is consistent at every adder and every wire, and weight zero otherwise. An input vector y∈{0,1}L\mathbf{y}\in\{0,1\}^{L} has exactly one consistent extension. This extension matches the fixed outputs exactly when y\mathbf{y} has qq ones, and it then contributes ∏iziyi\prod_i z_i^{y_i}. With at most LL adders and 2L2L wires, the order is at most 11L+6L11L+6L.

Table 2 lists the eight minors of CC that the full adder uses, with their permanents.

Rows deletedColumns deletedRemaining matrixPermanent
∅\varnothing∅\varnothing(0011101000011001)\begin{pmatrix}0&0&1&1\\1&0&1&0\\0&0&0&1\\1&0&0&1\end{pmatrix}1
{1}\{1\}{1}\{1\}(010001101)\begin{pmatrix}0&1&0\\0&0&1\\1&0&1\end{pmatrix}1
{1}\{1\}{2}\{2\}(110001101)\begin{pmatrix}1&1&0\\0&0&1\\1&0&1\end{pmatrix}1
{1}\{1\}{3}\{3\}(100001111)\begin{pmatrix}1&0&0\\0&0&1\\1&1&1\end{pmatrix}1
{2,3}\{2,3\}{1,2}\{1,2\}(0101)\begin{pmatrix}0&1\\0&1\end{pmatrix}1
{2,3}\{2,3\}{1,3}\{1,3\}(1101)\begin{pmatrix}1&1\\0&1\end{pmatrix}1
{2,3}\{2,3\}{2,3}\{2,3\}(0111)\begin{pmatrix}0&1\\1&1\end{pmatrix}1
{1,2,3}\{1,2,3\}{1,2,3}\{1,2,3\}(1)\begin{pmatrix}1\end{pmatrix}1

Table 2. The minors of CC used by the full adder.

References

  1. [1]J.-Y. Cai, X. Chen and D. Li. Quadratic lower bound for permanent vs. determinant in any characteristic. Computational Complexity 19 (2010), 37–56.DOI
  2. [2]K. Christ, X. He and I. Tyomkin. On the Severi problem in arbitrary characteristic. Publications Mathématiques de l’IHÉS 137 (2023), 1–45.DOI
  3. [3]T. Mignon and N. Ressayre. A quadratic bound for the determinant and permanent problem. International Mathematics Research Notices 2004, no. 79, 4241–4253.
  4. [4]OpenAI. A cubic lower bound for border determinantal complexity of the permanent. Preprint, 24 September 2026. https://github.com/openai/math/blob/fd4aeeb2ee4fc729c18d9844fed42fd0529eeeb/preprints/A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent-September-24-2026/A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent-September-24-2026.pdfhub.valency.io/works/W_jy7u9k7r
  5. [5]K. Sheshadri. Conormal lower bounds for determinantal complexity: Fermat slices, tight bounds, and a ceiling. arXiv:2606.15970v2, 2026.arxiv.org/abs/2606.15970
  6. [6]L. G. Valiant. Completeness classes in algebra. Proceedings of the 11th ACM Symposium on Theory of Computing (1979), 249–261.DOI

Paper details

vlnc:W_mqhtycfr
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 18

downloads · 3

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

ChatGPT Astra, Claude Opus 5.5

View statement
Looking for related papers…
Contents