A cubic lower bound for border determinantal complexity of the permanent

Proof. Fix a size n and determinants Q_j=\det M_j converging coefficientwise to f, with all entries of M_j affine-linear. The entries of M_j\circ A are still affine-linear. Substitution by the fixed map A is a continuous linear map on spaces of polynomials of degree at most n, so Q_j\circ A\to f\circ A. Multiplying one row of each substituted matrix by a gives the assertion. This argument imposes no bound on the matrix entries in the approximating sequence.□

Proof. Every linear map L:W_n\to W_n is a limit of invertible ones. Consequently \det_n\circ L belongs to the affine closure of the determinant orbit. This orbit is invariant under nonzero scalar multiplication: multiplying one row of a matrix variable by a\ne0 multiplies its determinant by a and is an invertible linear substitution. Its affine closure is therefore the cone over \mathcal D_n. In particular a nonzero form belongs to this affine closure exactly when its projective class belongs to \mathcal D_n.

Suppose first that \bdc(\per_m)\le n. Identity blocks let us take every approximating matrix to have size exactly n. Write

For n>m, homogenize to degree n using the independent coordinate z:

Homogenization here is a fixed linear map of coefficient spaces. Each displayed determinant is a linear substitution of \det_n on W_n, so its limit belongs to the same closed cone. The coordinates fit because m^2+1\le n^2 when n>m.

For n=m, instead take the degree-m homogeneous component of each Q_j. It is precisely

and these components converge to \per_m. They again are linear substitutions of \det_m. This proves the forward implication without introducing an extra variable in the case n=m.

Conversely, the cone observation and equality of the two closures give determinant-orbit representatives converging coefficientwise to P_{n,m}. When n>m, set z=1 and all unused coordinates to zero; when n=m, just use the m^2 coordinates x_{ab}. Each resulting polynomial is an affine determinant of size n, and the limit is \per_m. This proves the converse. Finally, a determinant of size less than m has degree less than m, as does every polynomial in its coefficientwise closure. Thus \bdc(\per_m)\ge m, and the stated range n\ge m covers every size that can satisfy the affine condition.□

Proof. Start with k main rows and columns carrying the edges X_{ij}. At each diagonal position add two labeled special edges, with weights

We call them the first and second color. At this intermediate stage they are parallel to the ordinary edge X_{ii}. The three labels record the choices X_{ii}, s, and t\theta_i in the diagonal entry, with the factors s,t omitted from the two special weights. The coefficient of s^qt^q in the shifted permanent is therefore the weighted sum of main matchings using exactly q special edges of each color, as in (3.2). We will count each color in a separate gate and couple each special main edge to the corresponding distinguished edge of its gate.

A gate imposing one prescribed count. Put h=k-q. Take k original rows and columns, with distinguished diagonal edges of weight 1, and h additional rows and columns. Join every original row to every additional column and every additional row to every original column, all with weight 1. There are no other edges. Every additional row must occupy an original column, and every additional column must be occupied by an original row. Consequently exactly q distinguished edges occur in a perfect matching.

For each prescribed distinguished set S\subseteq[k] of size q, the remaining original rows match the additional columns in h! ways, and the additional rows match the remaining original columns in h! ways. These choices are independent. Hence the multiplicity for this exact set is

This also covers q=0: all original rows and columns then match across the two groups.

A gadget equating two edge choices. Call the main and gate vertices outer. For one special main edge of weight w and its distinguished gate edge of weight 1, write the outer row endpoints as u_1,u_2 and the outer column endpoints as v_1,v_2, respectively. These two edges have distinct endpoints. Delete them and add three fresh internal rows and three fresh internal columns, with weight matrix

For i=1,2, add an incoming edge from u_i to internal column i and an outgoing edge from internal row i to v_i. All four weights are 1, except that the first incoming edge has weight -2w.

Fix the subset I\subseteq\{1,2\} of incoming edges used and the subset O\subseteq\{1,2\} of outgoing edges used. Let \Phi_w(I,O) be the total weight of their internal completions, including the weights of those boundary edges. If |I|\ne|O|, the remaining internal row and column sets have different sizes, so there is no completion and \Phi_w(I,O)=0. Otherwise

The complete table of \Phi_w is

To verify the six balanced cases, first \per H=-2. Deleting any one row and any one column indexed in \{1,2\} leaves \left(\begin{smallmatrix}-1&1\\1&1\end{smallmatrix}\right), whose permanent is -1+1=0. This includes the crossed choices I=\{1\},O=\{2\} and I=\{2\},O=\{1\}. Deleting both interface rows and columns leaves the entry H_{33}=1; the four external edge weights then have product -2w. The ten unbalanced cases have already been excluded.

Thus \Phi_w(I,O) vanishes unless I=O=\varnothing or I=O=\{1,2\}. In these two states the weights -2 and -2w reproduce neither outer edge being used or both being used, with the common factor -2. The four balanced singleton states can have individual internal matchings; it is their sums that cancel.

Combining the two counts. Take two disjoint copies of the count gate, one for each color. For every i\in[k] and c\in\{1,2\}, replace the special main edge of weight w_{i,c} and its distinguished gate edge by the equality gadget. Use fresh internal rows and columns for all 2k gadgets. At a fixed index i, the two replacements share the main row and column, while their internal vertices and their gate endpoints remain distinct. Figure 2 shows these attachments.

Group the full matching sum by the set E of chosen edges outside the internal H-blocks. This set includes all chosen incoming and outgoing edges and must cover each outer vertex exactly once. Let w_{\mathrm{out}}(E) be the product of the weights of the chosen edges whose two endpoints are outer. For the gadget indexed by (i,c), write I_{i,c},O_{i,c} for its boundary state. Since the internal vertex sets are disjoint, the total weight of all completions of E is

Each factor \Phi_{w_{i,c}} already includes its boundary edge weights; w_{\mathrm{out}}(E) contains only the remaining chosen weights. By (3.8), this product vanishes unless every gadget has I_{i,c}=O_{i,c}=\varnothing or I_{i,c}=O_{i,c}=\{1,2\}. Unbalanced states have no completion, and balanced singleton states cancel.

Now restrict to choices E for which every gadget has one of these two states. For each gadget with I_{i,c}=O_{i,c}=\{1,2\}, replace its four boundary edges by the original special main edge and distinguished gate edge. For an empty state, insert neither original edge. Because E covers every outer vertex exactly once, this contraction gives a perfect matching in the graph before replacement, with each special main edge used if and only if its paired gate edge is used. Conversely, each such matching determines the set E and its boundary states uniquely. The table assigns -2w_{i,c} to a used pair of original weight w_{i,c}, and -2 to an unused pair of weight 1. Hence its contribution is its original matching weight multiplied by exactly one factor -2 for each of the 2k gadgets. Shared main endpoints enter through the matching constraint enforced when E is fixed; the internal factorization uses disjoint vertices.

Each gate now forces exactly q special edges of its color. The two selected sets are disjoint by the main matching condition. For these sets, the two gates contribute ((k-q)!)^4 by (3.5), while the main matching sum is the corresponding summand of (3.2). The 2k gadgets contribute (-2)^{2k}. This proves (3.3) for the unpadded construction.

Its number of rows, and separately its number of columns, is

These terms count the main graph, the two count gates, and the fresh internal blocks. The final graph has no parallel special edges: their replacements lead to distinct internal columns. Its weight matrix therefore has entries that are variables or constants. Append an identity block to reach order m; its unique matching has weight 1, so the permanent identity is preserved.

Finally, write this padded affine matrix as A(X)=A_0+\sum_{i,j}X_{ij}A_{ij} and set B(X,z)=zA_0+\sum_{i,j}X_{ij}A_{ij}. For z\ne0, homogeneity gives

Since m\ge k\ge r, both sides are polynomials. Their equality for z\ne0 proves their identity also at z=0. The identity block is homogenized along with every other constant entry, so it contributes the additional power of z required in (3.4).□

Proof. Proposition 3.1 gives G_D\circ\Lambda=a_0^{-1}\per_m\circ A\circ\Lambda. Apply Lemma 2.1 to the affine map A\circ\Lambda and the nonzero scalar a_0^{-1}. Both are fixed before any determinant approximation is chosen.□

Proof. The restriction

is squarefree. If a positive-degree irreducible homogeneous factor H occurred at least twice in F_X, its restriction to u=0 could not vanish identically: otherwise u would divide F_X, contrary to (4.6). That restriction is a nonzero homogeneous polynomial of the same positive degree as H. Its square would divide (4.6), a contradiction. Thus C is reduced. The restriction of each irreducible factor is likewise a positive-degree binary form, so it has a projective zero over K. Hence every component meets u=0.

The points on that line are

At P_i, the matrix M is diagonal with exactly one zero entry. It has rank k-1, and its i-th diagonal adjugate entry is \prod_{j\ne i}(\theta_j-\theta_i)\ne0.

The only possible base point of the projection is [1:0:0], which does not belong to C because F_X(1,0,0)=1. On the base chart t\ne0, use v=u/t and y=s/t. The inverse image has coordinate algebra

Its defining polynomial is monic of degree k in y; consequently this algebra is free over K[v], with basis 1,y,\ldots,y^{k-1}. The chart u\ne0 gives the same conclusion, so \pi is finite flat of degree k. At v=0 the monic polynomial has the distinct roots -\theta_1,\ldots,-\theta_k. Its resultant with its y-derivative is nonzero there, and hence nonzero on an open subset of the base. Over that open subset the finite flat map is étale. In particular its generic algebra is a product of finite separable field extensions, also when k is even.

The sections t,u have no common zero on C, so they identify \pi^*\cO_{\PP^1}(1) with \cO_C(1). The two monic-polynomial bases satisfy

on their overlap. These are exactly the transition functions of \cO_{\PP^1}(-j). This proves the first splitting in (4.5); tensoring by \cO_{\PP^1}(k-1) and using the projection formula proves the second.□

Proof. All sheaves on the base in this proof are on \PP^1_K. The adjugate entries define a morphism

The trace pairs matrix entries in transposed order, so its image is the \cO-span of all adjugate entries. We first show that

Work on either standard affine chart of the base and trivialize \cO(1). Write its coordinate ring as R, the affine s-coordinate as y, and the corresponding matrix as A_0. The curve algebra is B=R[y]/(f), where f=\det(yI_k+A_0). Let Q be the R-span in B of the entries of \adj(yI_k+A_0). The adjugate identity gives, in B,

Thus Q is stable under multiplication by y. Since B is generated by y over R, Q is already the B-ideal generated by these entries. Restoring the local trivialization proves (4.8) on both charts.

Put \mathcal K=\ker\psi. To lift every global section of \operatorname{im}\psi to a constant matrix, it is enough to prove H^1(\mathcal K)=0. We obtain this vanishing by comparing \mathcal K with the image of the commutator with A.

The matrix A=tD+uX has entries in \cO(1), so the commutator defines the morphism

The adjugate commutes with A, and cyclicity of trace gives \psi\chi=0. Put \mathcal I=\operatorname{im}\chi; then \mathcal I\subset\mathcal K.

At the base point [t:u]=[1:0], the commutator is [D,-]. On the matrix unit E_{ij} it acts by multiplication by \theta_i-\theta_j. These multipliers are nonzero for i\ne j, including in characteristic two. Hence the commutator has rank k^2-k at that point. At the same point, the images under \psi of the diagonal matrix units are the classes of

Evaluation at the k distinct roots gives a diagonal matrix with nonzero diagonal, so these classes are independent and \psi has rank k, the rank of \mathcal E. Its generic rank is therefore k, and its generic kernel has dimension k^2-k. The rank of \chi at [1:0] shows that its generic rank is at least k^2-k, while \mathcal I\subset\mathcal K gives the opposite inequality. Thus \mathcal I and \mathcal K have equal generic rank. The quotient \mathcal K/\mathcal I is therefore a coherent torsion sheaf on \PP^1.

We now use two exact sequences to compute H^1(\mathcal K). The first is

Since H^1(\PP^1,\cO(-1))=0 and coherent H^2 vanishes on \PP^1, its cohomology sequence gives H^1(\mathcal I)=0. These two facts follow, for example, from the usual computation with the two standard affine charts of \PP^1. Next, a coherent torsion sheaf on \PP^1 has finite support and vanishing H^1. The sequence

therefore gives H^1(\mathcal K)=0. Finally, the sequence

shows that constant matrices surject onto

where the equality uses (4.8) and finite pushforward.

Let P be a degree-k-1 homogeneous form vanishing on the scheme Z. Its restriction to C is a section of J(k-1), so the preceding surjectivity expresses it on C as a constant linear combination of the adjugate entries. Their difference is a degree-k-1 form vanishing on C. Since the homogeneous ideal of this plane hypersurface is generated by F_X, of degree k, the difference is zero. Thus the equality holds as an equality of homogeneous forms.□

Proof. Homogeneity and entrywise differentiation give

Thus the gradient hypothesis is precisely the entrywise condition

This calculation uses no division by the degree r. By Lemma 4.2, the functional \Lambda=[s^qt^qu^c] consequently vanishes on every degree-k-1 form that vanishes scheme-theoretically on Z.

The next comparison is the line-bundle case of Gałązka’s catalecticant bound under this annihilation condition. It uses the multiplication map P\mapsto(Q\mapsto\Lambda(PQ)), where P and Q have degrees q and k-1-q, respectively [9, Theorem 4 and Propositions 6, 7, and 9 in arXiv:1605.08005v1]. The complementary monomials below compute this map directly over K.

Suppose that a degree-q form

vanishes on Z. For each triple in this sum, the monomial

has nonnegative exponents because i,j,\ell\le q\le c. Its product with P still vanishes on Z, and has degree 2q+c=k-1. Exactly one term contributes to its selected coefficient, giving

Hence P=0. Restriction therefore induces an injection

The space on the left has dimension \binom{q+2}{2}. On a finite scheme over K, an invertible sheaf is free of rank one on each Artin local component, so its space of global sections has dimension equal to the scheme’s length. The space on the right thus has dimension \length Z, including all nonreduced multiplicities. The stated inequality follows.□

Proof. Monicity makes B free over S, with basis 1,y,\ldots,y^{k-1}. In particular, it embeds into B_Q, a product of finite separable field extensions of Q, and is reduced. The integral closures of S and B in this algebra agree, since B is integral over S. They are finite over S. One way to see the finiteness directly is to use the sum of the field trace pairings on the factors of B_Q. This pairing is nondegenerate, so the lattice dual to B is finite free over S. If z\in B_Q is integral over S, then each zy^j, for 0\le j<k, is integral because y is integral. Its trace lies in the integrally closed ring S, so z belongs to the dual lattice. The normalization is an S-submodule of that finite lattice and is therefore finite. The same finiteness conclusion follows by applying the normalization theorem [22, Tag 032L] to each field factor.

It follows that R is semilocal. Its localizations at maximal ideals are one-dimensional Noetherian normal local domains, hence discrete valuation rings [22, Tag 00PD]. All their residue fields are K. As a finite torsion-free S-module, R is free of rank k, and R/B has finite length.

The adjugate ideal as an evaluation ideal. Consider the B-module

The same cokernel over S[y] is S^k, with y acting as -A_0: polynomial-vector division by the monic matrix yI+A_0 reduces every class uniquely to a constant vector. The adjugate identity shows that f already kills this cokernel. Thus L is free of rank k over S.

Over a splitting field of f, the action of -A_0 has k distinct eigenvalues, each with a one-dimensional eigenspace. Consequently L_Q is rank one over every field factor of B_Q, and L_Q\simeq B_Q as a B_Q-module. Fixing such an isomorphism embeds the S-free module L as a lattice in B_Q.

Define its evaluation ideal by

A homomorphism L\to B is a row annihilating M_0 modulo f. Lift the row to b\in S[y]^{1\times k}, so that bM_0=fb' for another polynomial row b'. Multiplication by the adjugate gives

We may cancel the nonzero f in the domain S[y], obtaining b=b'\adj M_0. Conversely, each adjugate row annihilates M_0 modulo f. Evaluation on the standard generators of L therefore gives

The conductor is contained in the evaluation ideal. The fractional ideal I=RL\subset B_Q is free of rank one at every maximal localization of R. We claim that some h\in L generates it at all these localizations at once. Choose S-generators l_1,\ldots,l_k of L. At a maximal ideal \mathfrak m of R, their images span the one-dimensional K-space I_{\mathfrak m}/\mathfrak m I_{\mathfrak m}. The coefficients (a_1,\ldots,a_k)\in K^k for which \sum_i a_i l_i has zero image form a proper linear subspace. There are only finitely many such maximal ideals. Since K is infinite, we can avoid all these subspaces. The resulting h=\sum_i a_i l_i\in L generates every I_{\mathfrak m}, and hence I=hR.

In particular, h is nonzero in every field factor of B_Q. The rescaled module L'=h^{-1}L satisfies

it contains 1, and L\subset RL=hR. For a\in\mathfrak c, multiplication by a defines a homomorphism L'\to B whose value at 1 is a. Evaluation ideals are invariant under module isomorphism, so

We have identified the adjugate ideal with an evaluation ideal and shown that it contains the conductor. It remains to compute the conductor colength in terms of the normalization.

The conductor colength. Let \lambda:B\to S extract the coefficient of y^{k-1} in the monic remainder, and consider

This is B-linear for the action (a\cdot\ell)(b)=\ell(ab) on B^\vee. In the basis 1,y,\ldots,y^{k-1}, its matrix has entry \lambda(y^{i+j}) in position (i,j). That entry is zero when i+j<k-1, and is one when i+j=k-1. Reversing the columns therefore gives a triangular matrix with diagonal entries one. Thus \Phi is an isomorphism in every characteristic. The trace pairing above was used over Q to prove finiteness of R. This coefficient pairing supplies the self-duality over S used below.

The adjunction

sends \ell to the map x\mapsto[b\mapsto\ell(bx)]. Using \Phi, it identifies \operatorname{Hom}_S(R,S) with \operatorname{Hom}_B(R,B). Every homomorphism in the latter module becomes a B_Q-linear endomorphism of B_Q, hence multiplication by some a\in B_Q. It takes R into B exactly when aR\subset B. Since 1\in R, this forces a\in B, and the possible multipliers are precisely \mathfrak c.

This identification respects restriction to B: for a multiplier a, the corresponding functional restricts to b\mapsto\lambda(ab)=\Phi(a)(b). Hence restriction

To compute its colength, choose bases for the two free S-lattices in which the inclusion B\subset R has elementary divisors \pi^{n_1},\ldots,\pi^{n_k}, where \pi is a uniformizer and the n_i are nonnegative. The quotient R/B has length \sum_i n_i, and the restriction on dual lattices has the same elementary divisors. By (5.4) and (5.5), its cokernel is isomorphic to B/\mathfrak c. This proves

The inclusion \mathfrak c\subset J_0 now gives (5.2).□

Proof. By Lemma 4.1, the projection \pi:C\to\PP^1_K is finite and flat, with a distinct-root fiber. It is therefore generically separable. At a closed point b of the base, take S=\cO_{\PP^1,b} and trivialize \cO(1). If y is the resulting s-coordinate and A_0 represents tD+uX, the curve algebra is

The stalk of \pi_*(\cO_C/J) is B/J_0, with J_0 as in Lemma 5.1. Its normalization R gives the stalk R/B of \pi_*(\nu_*\cO_{\widetilde C}/\cO_C). Indeed, normalization commutes with this localization. Changes of trivialization multiply the adjugate generators by units, so these are the intrinsic ideals and quotient sheaves.

Both quotient sheaves have finite support. At every closed point of the base, their finite-length S-modules have length equal to their K-dimension, because the residue field is K. Equivalently, each such length is the sum of the lengths at the curve points above that base point; no ramification factor enters. Summing (5.2) over b therefore gives

Only generic separability was needed. Nonreduced closed fibers and wild ramification are allowed by the coefficient pairing (5.4).□

Proof. Write C=C_1\cup\cdots\cup C_a, where the integral components have degrees b_i and normalization genera g_i. The Euler characteristics of the normalization and the curve are a-\sum_i g_i and 1-p_a(C). The normalization exact sequence therefore gives

In particular, the term a-1 accounts for the disconnected normalization, and the identity includes the contribution of intersections between different components.

For fixed degrees and genera, multiplying the equations of the components defines a morphism from the product of their integral curve loci to the degree-k linear system. Restricting to distinct factors gives precisely the reduced curves of this type. The image is constructible, and its dimension is at most

There are only finitely many degree and genus types: a\leq k, \sum b_i=k, and 0\leq g_i\leq(b_i-1)(b_i-2)/2. The normalization identity determines \delta(C) from each type. The required locus is therefore a finite union of constructible images with the stated dimension bound.□

Proof. The projection \pi:C\to\PP^1_{t:u} and the bundle

are fixed throughout \mathcal F_C. The entries of R_X give a map \rho_X:\cO^k\to\mathcal E on \PP^1. At b_0=[1:0], trivialize by t and put y=s/t. For every X, the map on this fiber sends the i-th standard basis vector to

Evaluation at the distinct roots -\theta_i shows that these k classes form a basis. In particular, all the maps \rho_X restrict to the same isomorphism at b_0. Each \rho_X is therefore generically full rank and injective as a sheaf map. Its cokernel is torsion of length

On C, the adjugate identity gives

On either affine base chart, the span of the row entries over the base ring is consequently stable under the affine s-coordinate. This coordinate generates the finite curve algebra over the base, so the span is already the ideal generated over the curve algebra, with its twist. Hence

Finite pushforward is exact, so

This pushforward has finite support, and \pi is finite, so \cO_{Z'_X} has finite support as well. Twisting preserves length, as does finite pushforward over the algebraically closed ground field. Equation (6.6) thus proves that Z'_X is finite of length N.

Suppose now that Z'_X=Z'_{X'}. Their ideal sheaves on the fixed curve are equal, so \rho_X and \rho_{X'} have the same image inside the same bundle \mathcal E. Since both maps are injective, there is an automorphism U of \cO^k with

Every such automorphism is an invertible constant matrix. Restricting this equality to b_0, where both maps are the same isomorphism (6.5), gives U=I and hence \rho_{X'}=\rho_X.

Multiplication by s maps \mathcal E to \mathcal E(1), and the row identity says

The analogous equation for X' now gives \rho_X(1)u(X-X')=0. The map \rho_X(1) is injective, so u(X-X')=0 as a matrix of sections of \cO(1). Since u is a nonzero section and X-X' is constant, this forces X=X'. The same argument works after extending the ground field, so the uniqueness statement also holds for geometric points.□

Proof. Fix a point of the affine plane and an integer \ell\geq1, and translate the point to the origin. Inside \operatorname{Hilb}^{\ell}(\mathbb A^2_K), let P_\ell be the closed locus of quotients on which (x,y)^\ell acts by zero. Its geometric points are precisely the punctual subschemes supported at the origin: in a length-\ell local algebra, the \ell-th power of the maximal ideal is zero.

The frame bundle of the tautological quotient algebra over P_\ell has dimension \dim P_\ell+\ell^2. In a frame, multiplication by the two coordinates gives commuting nilpotent matrices A,B of size \ell, and the unit gives a cyclic vector v\in K^\ell, meaning K[A,B]v=K^\ell. These data recover the ideal as

and recover its frame. Thus the resulting morphism from the frame bundle to the finite-type scheme of such triples is injective on geometric points. Its geometric fibers have dimension zero, which suffices for a dimension upper bound.

There are finitely many nilpotent Jordan types for A. If its linear centralizer has dimension j, then its group centralizer is the open set of invertible elements in that vector space. The conjugacy orbit of A therefore has dimension \ell^2-j. Within its centralizer, the nilpotent choices of B have dimension at most j-1: they satisfy \det B=0, whereas the determinant is one at the identity matrix in the same centralizer. This argument works in every characteristic. Consequently the commuting nilpotent pairs have dimension at most \ell^2-1. The choice of the cyclic vector adds at most \ell parameters, so

Fix p\in C and choose an affine plane chart around it, translated so that p is the origin. Inside the Hilbert scheme of this affine part of C, impose the same condition that the \ell-th power of the maximal ideal of p acts by zero. The resulting locus is a closed subscheme of P_\ell, and its geometric points are exactly the length-\ell subschemes of C supported at p. Its dimension is therefore at most \ell-1, including when p is singular. Fix a positive length type \ell_1+\cdots+\ell_a=N. Consider ordered distinct points (p_1,\ldots,p_a) of C together with subschemes of lengths \ell_i supported at p_i. This incidence is algebraic: containment in the \ell_i-th infinitesimal neighborhood of the moving point can be imposed using the \ell_i-th power of the diagonal ideal on C\times C. The support parameters have dimension at most a, and the fibers have dimension at most \sum_i(\ell_i-1)=N-a. The incidence therefore has dimension at most N. Taking disjoint unions of its subschemes maps it to \operatorname{Hilb}^N(C). Finitely many length types cover all geometric points of this Hilbert scheme, proving the claim. The case N=0 is immediate.□

Proof. Fix a curve C in the image and its fiber \mathcal F_C. Form

This is a closed incidence. Indeed, restrict the row entries to the universal finite flat subscheme over the Hilbert scheme and push forward their common twist. This produces sections of a vector bundle on the product, whose zero locus is \mathcal I_C.

Every matrix X occurs in the incidence with its subscheme Z'_X. Conversely, row vanishing on Z' means J'_X\subset I_{Z'}, so Z'\subset Z'_X. The scheme Z' has length N by its membership in the Hilbert scheme, and Z'_X has length N by Lemma 6.3. Therefore they are equal. The same lemma shows that each fiber of \mathcal I_C over \operatorname{Hilb}^N(C) has at most one geometric point. Such a finite-type fiber has dimension zero when nonempty, even if it is nonreduced. Projection to \mathcal F_C is surjective on geometric points, so

where the last inequality is Lemma 6.4.□

Proof of Proposition 6.1. By (6.3), every curve in f_D(\Gamma_D) has normalization defect at least T. Lemma 6.2 bounds the dimension of this constructible image by k(k+3)/2-T. Each fiber of the restriction of f_D to \Gamma_D is contained in a full matrix fiber and has dimension at most N by Proposition 6.5. Consequently

as asserted.□

Proof. Put R=\mathbb Z[\theta_1,\ldots,\theta_a] and S=\operatorname{Spec}R. The homogeneous ideal

defines a closed subscheme

Its structural morphism \pi:\mathcal Z\to S is projective, hence proper. Differentiation commutes with specialization, and the closed projective subscheme in (7.2) commutes with base change. Thus its geometric fibers are exactly the projective gradient-zero schemes of the specialized polynomials.

The derivatives have positive homogeneous degree r-1. At \bar\theta, their affine zero set is a cone. If its projectivization is nonempty, its dimension is one less than that of the cone: on each projective coordinate chart the corresponding punctured cone is a product with \mathbb G_m. If the projectivization is empty, the same upper bound holds with our convention. Hence

Let s\in S be the image of the geometric point \bar\theta. The dimension of a scheme of finite type over a field is unchanged by extending that field, so the same bound holds for \mathcal Z_s. If v-1-\delta\ge0, upper semicontinuity of fiber dimension for the proper morphism \pi gives an open neighborhood U_S of s on which this bound holds [22, Tag 0D4I]. If v-1-\delta=-1, the fiber \mathcal Z_s is empty. Properness makes \pi(\mathcal Z) closed, so U_S=S\setminus\pi(\mathcal Z) is an open neighborhood of s whose fibers are all empty. Thus the required neighborhood exists in every case, without a flatness assumption.

Since S is integral, U_S contains its generic point, which has characteristic zero. To see explicitly that the open has complex points, choose a nonempty principal open D(h)\subset U_S, with 0\ne h\in R. The polynomial h remains nonzero over \C, so D(h)_\C is nonempty. We may take U=(U_S)_\C. The same invariance under field extension shows that every complex fiber over U satisfies

Since \delta>0, F_\theta cannot be the zero polynomial: otherwise the left side of (7.3) would be v-1. Over \C, Euler’s identity gives

Thus the ideals (F_\theta,\nabla F_\theta) and (\nabla F_\theta) agree. These equations describe the actual projective hypersurface singular scheme. Indeed, on the chart x_i\ne0, put z_j=x_j/x_i for j\ne i and f_i=F_\theta/x_i^r. The hypersurface has equation f_i=0 and cotangent presentation

Its (v-2)-nd Fitting ideal is generated by the local partial derivatives of f_i. On f_i=0, these are the homogeneous gradient equations in this chart: Euler’s identity supplies the derivative in the omitted x_i direction. The Jacobian criterion therefore identifies this scheme with the singular scheme. Equation (7.3) proves (7.1).□

Proof. Write \mathcal G=\operatorname{Gr}(d,V), so \dim\mathcal G=d(v-d). A point of \mathcal G is a vector subspace of dimension d, whose projectivization has dimension d-1.

First consider pairs (p,H) with p\in\operatorname{Sing}Y and p\in\PP(H). For fixed p, the choices of H form \operatorname{Gr}(d-1,V/p), of dimension (d-1)(v-d); here p also denotes its line in V. This incidence has dimension at most

Its projection to \mathcal G is closed because \operatorname{Sing}Y is projective. It is a proper subset, so outside it the section avoids every singular point of Y.

For p=[x]\in Y_{\rm reg}, the nonzero differential dF_x has a kernel K_p\subset V of dimension v-1. Euler’s identity at F(x)=0 shows that p\subset K_p. If p\subset H, the restricted equation is singular at p exactly when

The homogeneous partial derivatives define the Gauss morphism Y_{\rm reg}\to\PP(V^*), p=[x]\mapsto[dF_x]. The pairs above form a closed incidence in Y_{\rm reg}\times\mathcal G: they are the inverse image of the closed flag incidence p\subset H\subset\ker\ell under (p,H)\mapsto(p,H,[dF_x]). For fixed p, these subspaces form \operatorname{Gr}(d-1,K_p/p), of dimension (d-1)(v-d-1). Since \dim Y_{\rm reg}\le v-2, this tangency incidence has dimension at most

Its image in \mathcal G is constructible, and the closure of that image has dimension at most \dim\mathcal G-1. Removing this closure and the preceding singular-point incidence image leaves a nonempty open subset of the irreducible Grassmannian.

For H in that open, every zero of F|_H has nonzero differential on H. The restriction cannot vanish identically: if it did, every point p\in\PP(H) would lie in Y, singular avoidance would put it in Y_{\rm reg}, and differentiation of the zero restriction would force H\subset K_p, contrary to the tangency exclusion.

Thus F|_H is a nonzero homogeneous polynomial of degree r. Since d\ge2, it defines a nonempty hypersurface of dimension d-2 in \PP(H). The nonzero differentials prove its smoothness.□

Proof. Set T=\binom{q+2}{2}. Since k\ge128,

Consequently

Also T\le(k+2)(k+5)/18<k^2 for these k, so 1\le\Delta\le k^2.

Choose pairwise distinct \bar\theta_1,\ldots,\bar\theta_k\in\overline{\mathbb F}_2 and put \bar D=\operatorname{diag}(\bar\theta_1,\ldots,\bar\theta_k). Proposition 6.1 gives

The coefficient formula (3.1), with the \theta_i treated as indeterminates, is integral in these parameters and homogeneous of degree r in the k^2 matrix variables. Moreover,

so r\ge2. Lemma 7.1 supplies a nonempty open subset U\subset\mathbb A^k_{\C}. Choose \theta=(\theta_1,\ldots,\theta_k)\in U(\C) and put D=\operatorname{diag}(\theta_1,\ldots,\theta_k). Then G_D\ne0 and

The complex coefficient projection permits arbitrary diagonal entries for this D.

For d=\lfloor k^2/100\rfloor, we have 2\le d<k^2, and (7.4) gives

Proposition 7.2 therefore supplies a subspace H\subset\Mat_k(\C) of dimension d such that G_D|_H is nonzero and defines a smooth degree-r hypersurface in \PP(H). Choose a linear isomorphism \Lambda:\C^d\to H and set G=G_D\circ\Lambda. This gives the asserted smooth form. The remaining scale estimate is

where the last inequality holds for k\ge20.

Finally, 0\le3q\le k-1, so 0\le q\le\lfloor k/2\rfloor. For each integer m\ge11k-2q, Proposition 3.1 gives a matrix A_m(X) of affine-linear forms with

Compose A_m with \Lambda and multiply its first row by a_0^{-1}. The resulting affine map \Phi_m:\C^d\to\Mat_m(\C) satisfies \per_m\circ\Phi_m=G, as required.□

Proof. The sections \partial_wG of \cO_Y(r-1) have no common zero on Y: otherwise all partial derivatives of G would vanish at a point of the smooth hypersurface. We spell out why general choices give simple points. If d=2, the smooth degree-r hypersurface in \PP^1 already consists of r distinct points, and there are no polar equations. Assume d\ge3.

Put \mathcal P=(\C^d)^{d-2} and consider

For each x, the equation in each separate w_i block is a nonzero linear equation. Thus \mathcal I is the total space of a vector bundle of rank (d-1)(d-2) over Y. In particular it is smooth, and \dim\mathcal I=d(d-2)=\dim\mathcal P. The incidence is closed in Y\times\mathcal P, so its projection to \mathcal P is proper because Y is projective. It is surjective: G and any d-2 chosen polars are d-1 positive-degree homogeneous equations in d variables, so the projective dimension theorem gives a common projective zero.

Characteristic-zero generic smoothness makes the generic fiber of each dominating component smooth. Remove the proper images of the non-dominating components and of the locus where the projection is not smooth. Properness makes these images closed, and generic smoothness ensures that they omit the generic point of \mathcal P. The resulting nonempty open subset has smooth zero-dimensional fibers. Each such fiber is a finite set of reduced points. At each point the differentials of the polar sections on Y are independent. Since dG\ne0 in local projective coordinates, the full system (8.1) is simple there.

This is a proper intersection of hypersurfaces of degrees r,r-1,\ldots,r-1 in \PP^{d-1}. Projective Bézout therefore gives exactly r(r-1)^{d-2} points, each of multiplicity one. Finally, the linear forms vanishing at at least one of these finitely many points form a finite union of proper hyperplanes in (\C^d)^*. Choose L_0 outside that union.□

Proof. First construct a system with the displayed number of zeros, all simple. Give each occurrence of a coordinate group in an equation a different label. On \PP^{a_j} choose the labeled linear forms so that every subfamily of at most a_j+1 coefficient vectors is independent. In coordinates [z_0:\cdots:z_{a_j}], forms

with distinct values of t have this property by the Vandermonde determinant. When a_j=0, use the nowhere-zero form z_0 on \PP^0. Replace equation \ell by Q_\ell=L_\ell R_\ell, using its two labeled forms on factors u_\ell and v_\ell.

At a common zero of all Q_\ell, let b_j count the labeled forms vanishing in factor j. General position implies b_j\le a_j. Each of the M equations requires at least one vanishing form, and no label occurs in two equations. Hence

Exactly one labeled factor vanishes in each equation, and exactly a_j forms vanish in factor j. Conversely, choosing one factor of each equation, with exactly a_j choices assigned to factor j, determines one point of Y: the selected a_j hyperplanes in that factor meet in one point. No additional labeled form vanishes there, because a_j+1 such hyperplanes have empty intersection. Different choices therefore give different points. Expanding the product in (8.2) counts exactly these choices; denote that coefficient by B.

Every comparison zero is simple. In equation \ell, one factor is zero and the other is nonzero, so its differential is a nonzero multiple of the selected linear form’s differential. In each projective factor the selected hyperplanes have independent differentials. The full Jacobian is therefore invertible. This construction also covers B=0, when the comparison system has no common zero.

It remains to compare an arbitrary system with this one. Interpolate by

The common-zero incidence is closed in Y\times\C. On it, rank deficiency of the differential in the Y directions is a closed algebraic condition. Indeed, it is given by maximal Jacobian minors in each projective chart. Coordinate changes act invertibly on the differential, and changing a trivialization multiplies an equation by a unit. At a common zero the derivative of that unit contributes zero, so the rank condition is independent of the chart.

Since Y is projective, the parameter values having a rank-deficient common zero form a Zariski-closed subset \mathcal B\subset\C. The comparison system shows that 0\notin\mathcal B, so \mathcal B is finite. For t\notin\mathcal B, all zeros are isolated by the implicit function theorem. Their set is closed in the compact space Y, hence finite. The number of zeros is locally constant on \C\setminus\mathcal B: the implicit function theorem preserves each zero in a disjoint neighborhood, and compactness prevents additional zeros from appearing outside those neighborhoods as the parameter varies. The same argument covers an empty fiber. Because the complement of a finite subset of \C is connected, this number is always the number at t=0, namely B.

Finally, choose any finite set of simple zeros at t=1. They persist in disjoint neighborhoods for parameters sufficiently close to 1. Such parameters can be chosen outside \mathcal B, where the total count is B. The selected set has at most B members. This conclusion does not assign multiplicities to, or impose conditions on, any excess components at t=1.□

Proof. Choose one sufficiently close determinant. Fix \mu distinct simple zeros of (8.3). All output polynomials lie in the finite-dimensional coefficient space of degree at most n. With \Psi and the w_i fixed, the map

is polynomial in the coefficients of Q and the coordinates of \xi. At every selected zero for P, its \xi-Jacobian is invertible. The complex implicit function theorem preserves that simple zero for all sufficiently close coefficient vectors. Take disjoint neighborhoods of the \mu zeros and intersect their finitely many coefficient neighborhoods. There is an actual determinant in the resulting neighborhood,

for which the same polar system has \mu distinct simple zeros. This choice constrains only the coefficients of Q. The matrix entries may be arbitrary complex numbers, however large; no bound on an approximation order or on coefficients of a parametrized family is used.

Choose a common chart for the right kernels. At each selected zero, the first row of the polar Jacobian is nonzero, so d(Q\circ\Psi)\ne0. If A(\Psi(\xi)) had rank at most n-2, its adjugate would vanish and the determinant derivative in every direction would be zero. Since its determinant is zero, its rank is exactly n-1. It has unique right and left projective kernel lines.

Choose a linear functional nonzero on every one of the finitely many right kernel lines. Such functionals are the complement of a finite union of proper hyperplanes. A fixed change of basis in the matrix domain makes this functional the first coordinate. Equivalently, replace A by AS for a suitable invertible constant matrix S. This multiplies Q and all its polars by the same nonzero constant and preserves simplicity. Continue to write A,Q for the resulting matrix and polynomial. Every selected right kernel now has a representative with first coordinate one. Put

These are constant matrices, and \partial_{w_i}Q=\tr(\adj(A)B_i).

Lift to a square system of bilinear equations. Let A^{\mathrm{hom}}(\xi_0,\xi) be the entrywise homogenization of the affine matrix A\circ\Psi, so A^{\mathrm{hom}}(1,\xi)=A(\Psi(\xi)). On

use the equations

There are n+(n-1)+h=h+2n-1 equations, equal to the product dimension. In the chart p_1\ne0, the omitted first left-kernel equation follows from the others, since

At a selected point, rank n-1 implies \adj(A)=\rho p b^{\mathsf T} for normalized kernel representatives and some \rho\ne0: every column of the adjugate is in the right kernel, every row is in the left kernel, and some cofactor is nonzero. Consequently \partial_{w_i}Q=\rho b^{\mathsf T}B_i p there. Each selected affine zero therefore has a unique lift satisfying (8.7).

The lift is not yet known to be simple. We prove this locally before applying Lemma 8.2; other components of the kernel system will impose no further requirement.

The same row permutation is applied to every B_i. The last n-1 right equations and all retained left equations give

Their auxiliary Jacobian has invertible diagonal blocks E,E^{\mathsf T}, so they eliminate the kernel coordinates holomorphically as

The remaining right equation, evaluated on the slice, is

The Schur determinant identity gives

where \sigma\in\{1,-1\} is the sign of the row permutation. It follows by subtracting \beta E^{-1} times the lower block rows from the first row. Here S is defined on an ambient neighborhood where E is invertible, so it can be differentiated in each ambient direction w_i.

After substituting (8.8), let g_i(\xi) denote the bilinear equation b^{\mathsf T}B_i p. For any constant ambient direction w, differentiation of S gives

Thus g_i=(\partial_{w_i}S)\circ\Psi. In particular this computation does not identify an ambient derivative with a derivative along the slice. If f=Q\circ\Psi and q_i=(\partial_{w_i}Q)\circ\Psi, differentiating (8.9) in the ambient space yields

The original equation vector (f,q_1,\ldots,q_h) and the reduced vector (s,g_1,\ldots,g_h) therefore differ by a triangular holomorphic matrix with diagonal entries c. At a common zero their Jacobians differ by the value of that invertible matrix. The original zero was simple, so the reduced Jacobian is invertible.

Finally, a tangent vector annihilated by the full kernel-system Jacobian first satisfies the differentials of the eliminated equations. Their invertible auxiliary block determines its (u,v) component from its \xi component. The remaining equations and the invertible reduced Jacobian force that \xi component to be zero, and hence the auxiliary component is zero as well. The full square Jacobian is invertible. All \mu selected lifts are thus distinct simple zeros of (8.7).

Count the selected lifts. The three groups of equations in (8.7) have multidegrees and multiplicities

Lemma 8.2 gives the first inequality in (8.4), regardless of other zeros or components. The product has nonnegative coefficients. Setting U=V=1 sums the coefficients with the same H-exponent, and hence bounds the particular coefficient by

Since \mu>0, we must have h+1\le2n-1. For integers 1\le b\le a,

the last bound follows from \log(b!)\ge\int_1^b\log t\,dt\ge b\log b-b. Taking (h+1)st roots gives

which is (8.5). No comparison between n and the number N of ambient variables, or between n and h+2, was assumed.□

Proof of Theorem 2.3. Let n be any size for which G is a coefficientwise limit of affine n\times n determinants. Choose the directions and L_0 from Lemma 8.1. The affine hyperplane L_0=1 identifies with the projective chart L_0\ne0 and contains representatives of all \mu=r(r-1)^{d-2} selected points. Parametrize it by an affine isomorphism

Restricting the homogeneous equations to this hyperplane is precisely their dehomogenization in that projective chart. Thus the equations

have \mu distinct simple affine solutions. The directions remain constant vectors in \C^d; they need not be tangent to L_0=1. Apply Proposition 8.3 with N=d, h=d-2, and P=G. It gives

where the last inequality uses r\ge r-1>0. This holds for every admissible size n, so taking the minimum proves the theorem.□

Proof of Theorem 1.1. Let m\ge1408 be an integer and put k=\lfloor m/11\rfloor. Then k\ge128. With q=\lfloor(k-1)/3\rfloor, we have q\ge0 and

Proposition 7.3 supplies a nonzero homogeneous form G of degree r in d variables, with smooth projective zero set, and a fixed affine map \Phi_m such that G=\per_m\circ\Phi_m. Lemma 2.1 and Theorem 2.3 give

using the two scale bounds in Proposition 7.3. The affine substitution is fixed before any determinant approximation is chosen, so this step applies to the unrestricted coefficientwise border model.

Finally,

where the last inequality holds for m\ge132. Therefore

which proves the stated choices of c and m_0.□

Proof. An exact determinant representation is also a constant sequence of approximating determinants. Hence \bdc(f)\le\dc(f) for every f, and Theorem 1.1 applies.□

Proof. Let a program with N vertices have output f. Sum parallel-edge labels and topologically order the vertices. With adjacency convention A_{v,u}=\text{label}(u\to v), the matrix A is strictly triangular, \det(I-A)=1, and (I-A)^{-1}=I+A+\cdots+A^{N-1}. The path-sum formula and the block determinant identity give

This is an affine-linear determinant of size N+1. Padding with isolated vertices covers all programs with at most N vertices. Taking closures therefore gives \bdc(f)\le N+1 for every output in the fixed-budget border model, even when the graph varies. After summing parallel edges, there are finitely many graph types for a fixed vertex budget, and each output depends polynomially on the affine-label coefficients. Hence the output set is constructible, so its two closures agree by the argument in Section 2.

For a nonzero output, trim away all vertices and edges outside source-to-sink paths. The remaining underlying graph is connected, so N\le E+1, where E is its edge count. Thus \bdc(f)\le E+2. For a fixed-edge-budget approximation to the nonzero permanent, discard any zero outputs and trim each remaining program separately; the same uniform determinantal bound passes to the limit. The finite graph-type argument also applies to this trimmed edge-budget model. Theorem 1.1 now yields both cubic lower bounds.□

Proof. Fix a size n for which g belongs to the coefficientwise closure \mathcal C_n of affine determinants of size n. Then \deg g\le n, and \mathcal C_n is closed in the space of polynomials of degree at most n. For every fixed t\in\C\setminus\{0\}, Lemma 2.1 gives

Writing g(a+x)=\sum_{j=r}^{\deg g}G_j(x) as a sum of homogeneous terms, the polynomial on the left is \sum_{j=r}^{\deg g}t^{j-r}G_j(x). It converges coefficientwise to G_r as t\to0. Closedness therefore gives G_r\in\mathcal C_n. Theorem 2.3 now bounds this same size n below by (r-1)(d-1)/(4e). Taking the least admissible n proves the border assertion, and \dc(g)\ge\bdc(g) proves the exact assertion.□