==== TABLE OF CONTENTS ====
A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//adjugate.tex
A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//conductor.tex
A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//consequences.tex
A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//dimension.tex
A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//introduction.tex
A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//main.tex
A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//models.tex
A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//polar.tex
A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//proof-flow.tex
A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//selector-wiring.tex
A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//selector.tex
A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//transfer.tex
A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//references.bib
===========================
==== BEGIN A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//adjugate.tex ====
\section{The adjugate scheme in characteristic two}
\label{sec:adjugate}
We now study the coefficient formula \eqref{eq:selector-coefficient} over
\[
K=\overline{\mathbb F}_2.
\]
In this characteristic the permanent equals the determinant. This lets
us associate a plane curve and a finite adjugate scheme to every matrix
\(X\). Vanishing of the gradient will force this finite scheme to have
large length.
Fix an integer \(k\ge2\), pairwise distinct elements
\(\theta_1,\ldots,\theta_k\in K\), and
\(D=\operatorname{diag}(\theta_1,\ldots,\theta_k)\). Set
\begin{equation}
\label{eq:adjugate-parameters}
q=\left\lfloor\frac{k-1}{3}\right\rfloor,\qquad
r=k-2q,\qquad c=r-1,\qquad T=\binom{q+2}{2}.
\end{equation}
Thus
\begin{equation}
\label{eq:adjugate-degrees}
2q+c=k-1,\qquad 0\le q\le c.
\end{equation}
For a polynomial, brackets denote extraction of the indicated monomial
coefficient. We use the homogeneous degree-\(r\) polynomial
\begin{equation}
\label{eq:adjugate-coefficient-polynomial}
G_D(X)=[s^qt^q]\per_k(X+sI_k+tD)
=[s^qt^q]\det(X+sI_k+tD).
\end{equation}
Statements about its gradient below refer to the common zero locus of
all its \(k^2\) entrywise partial derivatives; no equation \(G_D=0\) is
included in that definition.
For each fixed \(X\in\Mat_k(K)\), put
\begin{equation}
\label{eq:adjugate-curve}
A=tD+uX,\qquad M=sI_k+A,\qquad
F_X(s,t,u)=\det M,\qquad C_X=V(F_X)\subset\PP^2_K.
\end{equation}
Here \(F_X\) has degree \(k\), with coefficient \(1\) at \(s^k\).
We abbreviate \(C_X\) to \(C\) when \(X\) is fixed.
\begin{lemma}[Projection of the auxiliary curve]
\label{lem:adjugate-projection}
For every \(X\in\Mat_k(K)\), the curve \(C_X\) is reduced and the map
\[
\pi:C_X\longrightarrow\PP^1_K,\qquad [s:t:u]\longmapsto[t:u]
\]
is finite flat of degree \(k\) and is \'{e}tale over a nonempty open
subset of the base. Every irreducible component of \(C_X\) meets the
line \(u=0\), and at each point of that intersection \(M\) has rank
\(k-1\). Moreover, \(\pi^*\cO_{\PP^1}(1)=\cO_C(1)\), and
\begin{equation}
\label{eq:adjugate-splitting}
\pi_*\cO_C=\bigoplus_{j=0}^{k-1}\cO_{\PP^1}(-j),
\qquad
\mathcal E:=\pi_*\cO_C(k-1)
=\bigoplus_{j=0}^{k-1}\cO_{\PP^1}(k-1-j).
\end{equation}
\end{lemma}
\begin{proof}
The restriction
\begin{equation}
\label{eq:adjugate-fixed-fiber}
F_X(s,t,0)=\prod_{i=1}^k(s+t\theta_i)
\end{equation}
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 \eqref{eq:adjugate-fixed-fiber}. That restriction is a
nonzero homogeneous polynomial of the same positive degree as \(H\).
Its square would divide \eqref{eq:adjugate-fixed-fiber}, 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
\[
P_i=[-\theta_i:1:0]\qquad(1\le i\le k).
\]
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
\[
K[v,y]\big/\det(yI_k+D+vX).
\]
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 \'{e}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
\[
(s/u)^j=(t/u)^j(s/t)^j\qquad(0\le j<k)
\]
on their overlap. These are exactly the transition functions of
\(\cO_{\PP^1}(-j)\). This proves the first splitting in
\eqref{eq:adjugate-splitting}; tensoring by \(\cO_{\PP^1}(k-1)\)
and using the projection formula proves the second.
\end{proof}
The fixed distinct-root fiber has established reducedness and a finite
flat, generically separable projection. We next use the adjugate to turn a vanished
coefficient into a lower bound on the length of a finite scheme.
Each entry of \(\adj M\) is a homogeneous form of degree \(k-1\).
Define its ideal on \(C\) intrinsically by
\begin{equation}
\label{eq:adjugate-ideal}
J=\operatorname{im}\bigl(\cO_C(1-k)^{k^2}
\xrightarrow{\ \text{entries of }\adj M\ }\cO_C\bigr),
\qquad Z=V_C(J).
\end{equation}
Thus a local trivialization of \(\cO_C(k-1)\) turns the adjugate
entries into generators of \(J\). Changing the trivialization
multiplies all generators by a unit and leaves the ideal unchanged.
By Lemma~\ref{lem:adjugate-projection}, each component of \(C\)
contains a point at which an adjugate entry is nonzero. The support
of \(\cO_C/J\) therefore contains no component of \(C\), so \(Z\)
is a finite scheme. It may have nonreduced structure.
\begin{lemma}[Generation by adjugate entries]
\label{lem:adjugate-generation}
Every homogeneous form of degree \(k-1\) that vanishes
scheme-theoretically on \(Z\) is a constant \(K\)-linear combination
of the entries of \(\adj M\).
\end{lemma}
\begin{proof}
All sheaves on the base in this proof are on \(\PP^1_K\).
The adjugate entries define a morphism
\[
\psi:\Mat_k(\cO)\longrightarrow\mathcal E,\qquad
Y\longmapsto\tr(Y\adj M).
\]
The trace pairs matrix entries in transposed order, so its image is
the \(\cO\)-span of all adjugate entries. We first show that
\begin{equation}
\label{eq:adjugate-image}
\operatorname{im}\psi=\pi_*(J(k-1)).
\end{equation}
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\),
\[
y\adj(yI_k+A_0)=-A_0\adj(yI_k+A_0).
\]
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 \eqref{eq:adjugate-image} 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
\[
\chi:\Mat_k(\cO(-1))\longrightarrow\Mat_k(\cO),\qquad
Y\longmapsto AY-YA.
\]
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
\[
h_i(y)=\prod_{j\ne i}(y+\theta_j)
\quad\text{in}\quad K[y]\big/\prod_j(y+\theta_j).
\]
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
\[
0\longrightarrow\ker\chi\longrightarrow
\cO(-1)^{k^2}\longrightarrow\mathcal I\longrightarrow0.
\]
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
\[
0\longrightarrow\mathcal I\longrightarrow\mathcal K
\longrightarrow\mathcal K/\mathcal I\longrightarrow0
\]
therefore gives \(H^1(\mathcal K)=0\).
Finally, the sequence
\[
0\longrightarrow\mathcal K\longrightarrow\cO^{k^2}
\longrightarrow\operatorname{im}\psi\longrightarrow0
\]
shows that constant matrices surject onto
\[
H^0(\PP^1,\operatorname{im}\psi)=H^0(C,J(k-1)),
\]
where the equality uses \eqref{eq:adjugate-image} 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.
\end{proof}
\begin{proposition}[Length forced by the gradient]
\label{prop:adjugate-length}
With the parameters in \eqref{eq:adjugate-parameters}, let
\(X\in\Mat_k(K)\) satisfy \(\nabla G_D(X)=0\).
Then its adjugate zero scheme \(Z\) satisfies
\[
\length Z\ge T=\binom{q+2}{2}.
\]
\end{proposition}
\begin{proof}
Homogeneity and entrywise differentiation give
\[
G_D(X)=[s^qt^qu^r]F_X,\qquad
\frac{\partial F_X}{\partial X_{ij}}=u(\adj M)_{ji}.
\]
Thus the gradient hypothesis is precisely the entrywise condition
\begin{equation}
\label{eq:adjugate-coefficient-zero}
[s^qt^qu^c]\adj M=0,\qquad c=r-1.
\end{equation}
This calculation uses no division by the degree \(r\).
By Lemma~\ref{lem:adjugate-generation}, 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{\l}{\k a}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
\cite[Theorem~4 and Propositions~6, 7, and~9 in arXiv:1605.08005v1]{Galazka2017}.
The complementary monomials below compute this map directly over \(K\).
Suppose that a degree-\(q\) form
\[
P=\sum_{i+j+\ell=q}a_{ij\ell}s^it^ju^\ell
\]
vanishes on \(Z\). For each triple in this sum, the monomial
\[
s^{q-i}t^{q-j}u^{c-\ell}
\]
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
\[
0=\Lambda\bigl(s^{q-i}t^{q-j}u^{c-\ell}P\bigr)=a_{ij\ell}.
\]
Hence \(P=0\). Restriction therefore induces an injection
\[
H^0(\PP^2,\cO(q))\lhook\joinrel\longrightarrow
H^0(Z,\cO_Z(q)).
\]
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.
\end{proof}
==== END A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//adjugate.tex ====
==== BEGIN A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//conductor.tex ====
\section{The conductor and the normalization defect}
\label{sec:conductor}
We next bound the length of the adjugate subscheme by the singularities
of the plane curve. For a reduced projective curve \(C\), let
\(\nu:\widetilde C\to C\) be its normalization and set
\begin{equation}
\delta(C)=
\dim_K H^0\bigl(C,\nu_*\cO_{\widetilde C}/\cO_C\bigr).
\label{eq:conductor-delta}
\end{equation}
The normalization may be disconnected. The comparison below follows the
evaluation-ideal argument of Fantechi--G\"ottsche--van Straten
\cite[Proposition C.2 and Corollary C.3]{FGvS1999}.
Their setting is over \(\C\); we give the local proof needed here in
arbitrary characteristic.
\begin{lemma}
\label{lem:conductor-local}
Let \(k\ge1\) be an integer, let \(K\) be an algebraically closed field,
and let \(S\) be a discrete
valuation ring containing \(K\), with residue field \(K\) and fraction
field \(Q\). For \(A_0\in\Mat_k(S)\), put
\[
M_0=yI+A_0,\qquad f=\det M_0,\qquad B=S[y]/(f).
\]
Suppose that \(f\) is separable over \(Q\). Let \(R\) be the normalization
of \(B\) in \(B_Q=B\otimes_S Q\), let
\[
\mathfrak c=\{a\in B:aR\subset B\},
\]
and let \(J_0\subset B\) be the ideal generated by the entries of
\(\adj M_0\). Then
\begin{equation}
\mathfrak c\subset J_0,\qquad
\length_S(B/J_0)\le
\length_S(B/\mathfrak c)=\length_S(R/B).
\label{eq:conductor-local-length}
\end{equation}
\end{lemma}
\begin{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 \cite[Tag 032L]{StacksProject} 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 \cite[Tag 00PD]{StacksProject}. 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.
\medskip
\noindent
\emph{The adjugate ideal as an evaluation ideal.}
Consider the \(B\)-module
\[
L=\operatorname{coker}(M_0:B^k\longrightarrow B^k).
\]
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
\[
\tau_B(L)=
\operatorname{im}\left(
\operatorname{Hom}_B(L,B)\otimes_B L\longrightarrow B
\right).
\]
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
\[
fb=fb'\adj M_0.
\]
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
\begin{equation}
\tau_B(L)=J_0.
\label{eq:conductor-evaluation}
\end{equation}
\medskip
\noindent
\emph{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
\[
B\subset L'\subset R:
\]
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
\[
\mathfrak c\subset\tau_B(L')
=\tau_B(L)=J_0.
\]
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.
\medskip
\noindent
\emph{The conductor colength.}
Let \(\lambda:B\to S\) extract the coefficient of \(y^{k-1}\) in
the monic remainder, and consider
\begin{equation}
\Phi:B\longrightarrow B^\vee:=\operatorname{Hom}_S(B,S),
\qquad
\Phi(a)(b)=\lambda(ab).
\label{eq:conductor-pairing}
\end{equation}
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
\[
\operatorname{Hom}_S(R,S)
\simeq
\operatorname{Hom}_B(R,\operatorname{Hom}_S(B,S))
\]
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
\begin{equation}
R^\vee=\operatorname{Hom}_S(R,S)\longrightarrow B^\vee
\quad\hbox{has image }\Phi(\mathfrak c).
\label{eq:conductor-dual-image}
\end{equation}
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 \eqref{eq:conductor-pairing} and
\eqref{eq:conductor-dual-image}, its cokernel is isomorphic to
\(B/\mathfrak c\). This proves
\[
\length_S(B/\mathfrak c)=\length_S(R/B).
\]
The inclusion \(\mathfrak c\subset J_0\) now gives
\eqref{eq:conductor-local-length}.
\end{proof}
\begin{proposition}
\label{prop:conductor-length}
For each curve \(C=C_X\) and adjugate subscheme \(Z\) constructed in
Section~\ref{sec:adjugate},
\begin{equation}
\length Z\le\delta(C).
\label{eq:conductor-global-length}
\end{equation}
\end{proposition}
\begin{proof}
By Lemma~\ref{lem:adjugate-projection}, 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
\[
B=S[y]/\bigl(\det(yI+A_0)\bigr).
\]
The stalk of \(\pi_*(\cO_C/J)\) is \(B/J_0\), with \(J_0\) as in
Lemma~\ref{lem:conductor-local}. 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 \eqref{eq:conductor-local-length} over \(b\) therefore gives
\[
\length Z
=\sum_b\length_{\cO_{\PP^1,b}}(B/J_0)
\le
\sum_b\length_{\cO_{\PP^1,b}}(R/B)
=\delta(C).
\]
Only generic separability was needed. Nonreduced closed fibers and
wild ramification are allowed by the coefficient pairing
\eqref{eq:conductor-pairing}.
\end{proof}
In particular, Proposition~\ref{prop:adjugate-length} yields
\begin{equation}
\nabla G_D(X)=0
\quad\Longrightarrow\quad
\delta(C_X)\ge T.
\label{eq:conductor-gradient-defect}
\end{equation}
==== END A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//conductor.tex ====
==== BEGIN A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//consequences.tex ====
\section{The permanent lower bound and its consequences}
\label{sec:consequences}
Proposition~\ref{prop:smooth-projection} supplies a smooth form with an
exact affine permanent projection. Combining it with
Theorem~\ref{thm:smooth-border} proves the main lower bound.
\begin{proof}[Proof of Theorem~\ref{thm:main}]
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
\[
m\ge11k\ge11k-2q.
\]
Proposition~\ref{prop:smooth-projection} 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~\ref{lem:affine-substitution} and
Theorem~\ref{thm:smooth-border} give
\[
\bdc(\per_m)\ge\bdc(G)
\ge\frac{(r-1)(d-1)}{4e}
\ge\frac{k^3}{3200e},
\]
using the two scale bounds in Proposition~\ref{prop:smooth-projection}.
The affine substitution is fixed before any determinant approximation
is chosen, so this step applies to the unrestricted coefficientwise
border model.
Finally,
\[
k\ge\frac{m}{11}-1\ge\frac{m}{12},
\]
where the last inequality holds for \(m\ge132\). Therefore
\[
\bdc(\per_m)\ge\frac{m^3}{5\,529\,600e},
\]
which proves the stated choices of \(c\) and \(m_0\).
\end{proof}
\subsection{Determinantal complexity and branching programs}
The border lower bound gives the same estimate for exact determinant
representations. A direct determinant construction also transfers it to
algebraic branching programs and their fixed-budget limits.
\begin{corollary}[Exact determinantal complexity]
\label{cor:exact-complexity}
For every integer $m\ge1408$,
\[
\dc(\per_m)\ge \frac{m^3}{5\,529\,600e}.
\]
\end{corollary}
\begin{proof}
An exact determinant representation is also a constant sequence of
approximating determinants. Hence $\bdc(f)\le\dc(f)$ for every $f$, and
Theorem~\ref{thm:main} applies.
\end{proof}
\begin{corollary}[Affine-linear algebraic branching programs]
\label{cor:abp-complexity}
Over $\C$, an algebraic branching program is a finite directed acyclic
graph with distinct designated source $s$ and sink $t$, whose edges carry
affine-linear forms; its output is the sum of the commutative products of
labels along all directed $s$-to-$t$ paths. Such a program computing
$\per_m$ requires $\Omega(m^3)$ vertices and $\Omega(m^3)$ edges, even after
trimming to the vertices and edges on source-to-sink paths. The same
bounds hold if $\per_m$ is a coefficientwise (equivalently, Zariski)
limit of outputs with a fixed vertex budget, respectively a fixed edge
budget, along the approximation.
\end{corollary}
\begin{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
\[
f=e_t^{\mathsf T}(I-A)^{-1}e_s
=\det\begin{pmatrix}I-A&e_s\\-e_t^{\mathsf T}&0\end{pmatrix}.
\]
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~\ref{sec:models}.
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~\ref{thm:main} now yields both cubic lower bounds.
\end{proof}
\subsection{Smooth initial forms}
Theorem~\ref{thm:smooth-border} also applies locally to a polynomial that
need not be homogeneous. Its first nonzero homogeneous term can be obtained
as a coefficientwise limit of translated and rescaled copies of that polynomial.
\begin{corollary}[Smooth initial form]
\label{cor:smooth-initial-form}
Let $g\in\C[x_1,\ldots,x_d]$, where $d\ge2$, and let $a\in\C^d$.
Suppose that the lowest nonzero homogeneous term $G_r(x)$ of $g(a+x)$
has degree $r\ge2$ and defines a smooth hypersurface in $\PP^{d-1}$.
Then
\[
\bdc(g)\ge\frac{(r-1)(d-1)}{4e}.
\]
The same lower bound holds for $\dc(g)$.
\end{corollary}
\begin{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~\ref{lem:affine-substitution} gives
\[
t^{-r}g(a+tx)\in\mathcal C_n.
\]
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~\ref{thm:smooth-border} 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.
\end{proof}
==== END A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//consequences.tex ====
==== BEGIN A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//dimension.tex ====
\section{From curve defects to matrix codimension}
\label{sec:dimension}
The preceding sections show that a critical matrix of the coefficient
polynomial produces a reduced plane curve with large normalization defect.
We now count these matrices by separating the choice of the curve from the
choice of a matrix that produces it.
\begin{samepage}
\begin{proposition}[Gradient codimension]\label{prop:gradient-codimension}
Let $K=\overline{\mathbb F}_2$, let $k\geq2$, and set
\[
q=\left\lfloor\frac{k-1}{3}\right\rfloor,
\qquad T=\binom{q+2}{2}.
\]
For pairwise distinct $\theta_1,\ldots,\theta_k\in K$, put
$D=\operatorname{diag}(\theta_1,\ldots,\theta_k)$ and
\[
G_D(X)=[s^qt^q]\per_k(X+sI+tD),
\qquad X\in\Mat_k(K).
\]
Then
\begin{equation}
\dim\{X\in\Mat_k(K):\nabla G_D(X)=0\}
\leq k^2+k-T.
\label{eq:gradient-dimension}
\end{equation}
\end{proposition}
\end{samepage}
For the proof, fix these parameters and write
\[
\Gamma_D=\{X\in\Mat_k(K):\nabla G_D(X)=0\}.
\]
Consider the morphism
\begin{equation}
\label{eq:determinant-curve-map}
f_D:\Mat_k(K)\longrightarrow
\PP H^0(\PP^2_K,\cO(k)),\qquad
X\longmapsto[F_X],\qquad
F_X=\det(sI+tD+uX).
\end{equation}
The coefficient of $s^k$ is one, so a projective fiber fixes the
polynomial $F_X$ itself and hence the embedded curve $C_X$.
Every curve in the image is reduced by
Lemma~\ref{lem:adjugate-projection}. For $X\in\Gamma_D$,
Propositions~\ref{prop:adjugate-length} and~\ref{prop:conductor-length}
give
\begin{equation}
\label{eq:dimension-gradient-defect}
T\leq\length Z\leq\delta(C_X).
\end{equation}
We will bound the dimension of $f_D(\Gamma_D)$ using this defect, then
bound the fibers of $f_D$ by associating a finite subscheme of the fixed
curve to each matrix in the fiber.
\subsection{Curves with large normalization defect}
Recall that, for a reduced curve $C$ with normalization
$\nu:\widetilde C\to C$,
\[
\delta(C)=\length(\nu_*\cO_{\widetilde C}/\cO_C).
\]
The normalization may be disconnected. We will keep track of its
components explicitly when applying the dimension theorem for integral
curves.
Over any algebraically closed field, let $b\geq1$ and
$0\leq g\leq(b-1)(b-2)/2$ be integers. The locus of integral plane
curves of degree $b$ and normalization genus $g$ is locally closed and,
when nonempty, has dimension $3b+g-1$
\cite[Lemma~2.6, Proposition~2.7, and Remark~2.8]{CHT2023}.
This is the cited theorem with surface $\PP^2$ and line bundle $\cO(b)$.
The locus includes every integral curve of the stated genus: the surface
has no singular points to exclude, and nodality is not a hypothesis.
\begin{lemma}
Let $K$ be an algebraically closed field\label{lem:severi-dimension}, and let $k\geq1$ and $T\geq0$
be integers. In the degree-$k$ plane linear system over $K$, the locus
of reduced curves satisfying $\delta(C)\geq T$ is constructible.
If nonempty, it has dimension at most
\[
\frac{k(k+3)}2-T.
\]
\end{lemma}
\begin{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
\[
\delta(C)=p_a(C)-\sum_{i=1}^a g_i+a-1,
\qquad p_a(C)=\frac{(k-1)(k-2)}2.
\]
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
\begin{align*}
\sum_{i=1}^a(3b_i+g_i-1)
&=3k+\sum_{i=1}^a g_i-a\\
&=\frac{k(k+3)}2-\delta(C).
\end{align*}
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.
\end{proof}
\subsection{A row subscheme determines a matrix}
Fix a curve $C$ in the image of $f_D$, and let
$\mathcal F_C=f_D^{-1}([C])$. Our remaining task is to bound this
matrix fiber. For a critical matrix, its full-adjugate scheme $Z$
supplied the defect bound \eqref{eq:dimension-gradient-defect} on its
curve. We now use a row obtained from the adjugate to distinguish all
matrices in the fixed fiber $\mathcal F_C$.
Put $N=k(k-1)/2$. For $X\in\mathcal F_C$, define
\[
R_X=(1,\ldots,1)\adj(sI+tD+uX),
\]
and define an ideal and its subscheme on the fixed curve by
\begin{equation}
\label{eq:row-adjugate-ideal}
J'_X=\operatorname{im}\bigl(
\cO_C(1-k)^k\xrightarrow{\ R_X\ }\cO_C\bigr),
\qquad Z'_X=V_C(J'_X).
\end{equation}
Thus $J'_X$ is locally generated by the row entries after trivializing
their common twist. We use the prime to distinguish this row subscheme
from the full-adjugate scheme $Z$.
After transposition, the equations $R_X=0$ say that an adjugate matrix
annihilates a fixed vector. Adams, Harnad and Hurtubise use equations
of this form for spectral divisors in a generic complex setting
\cite[Section~1b, equation~(1.29) in arXiv:hep-th/9210089v1]{AdamsHarnadHurtubise1993}.
Here we prove the uniform finite length of $Z'_X$ directly. The common
boundary frame then makes this subscheme determine the matrix uniquely
on a fixed embedded curve.
\begin{lemma}[The row subscheme]
For each $X\in\mathcal F_C$\label{lem:row-adjugate-scheme}, the scheme $Z'_X$ is finite of length $N$.
If $X,X'\in\mathcal F_C$ satisfy $Z'_X=Z'_{X'}$ as subschemes of $C$,
then $X=X'$.
\end{lemma}
\begin{proof}
The projection $\pi:C\to\PP^1_{t:u}$ and the bundle
\[
\mathcal E=\pi_*\cO_C(k-1)
=\bigoplus_{j=0}^{k-1}\cO(k-1-j)
\]
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
\begin{equation}
\label{eq:row-boundary-frame}
h_i(y)=\prod_{j\ne i}(y+\theta_j)
\quad\text{in}\quad
K[y]\big/\prod_j(y+\theta_j).
\end{equation}
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
\begin{equation}
\label{eq:row-adjugate-length}
\length(\coker\rho_X)
=\deg\mathcal E
=\sum_{j=0}^{k-1}(k-1-j)=N.
\end{equation}
On $C$, the adjugate identity gives
\[
sR_X=-R_X(tD+uX).
\]
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
\[
\operatorname{im}\rho_X=\pi_*(J'_X(k-1)).
\]
Finite pushforward is exact, so
\[
\coker\rho_X=\pi_*(\cO_{Z'_X}(k-1)).
\]
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 \eqref{eq:row-adjugate-length} 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
\[
\rho_{X'}=\rho_XU.
\]
Every such automorphism is an invertible constant matrix. Restricting
this equality to $b_0$, where both maps are the same isomorphism
\eqref{eq:row-boundary-frame}, gives $U=I$ and hence
$\rho_{X'}=\rho_X$.
Multiplication by $s$ maps $\mathcal E$ to $\mathcal E(1)$, and the
row identity says
\[
s\rho_X=-\rho_X(1)(tD+uX).
\]
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.
\end{proof}
The lemma reduces the fiber count to the possible length-$N$ subschemes
of $C$. We next bound the dimension of their Hilbert scheme in a form
valid in characteristic two.
\subsection{Finite subschemes of a plane curve}
For a punctual quotient of $\cO$, Baranovsky's construction of punctual
Quot schemes over $\C$ uses commuting nilpotent operators and a cyclic
vector after choosing a basis \cite[Section~2, Lemma~2.2]{Baranovsky1998}.
For the classical punctual-plane Hilbert dimension bound in arbitrary
characteristic, see \cite[Corollary~4.1]{Premet2003}.
The centralizer count below supplies the dimension bound needed here in
every characteristic.
\begin{lemma}\label{lem:hilbert-curve-dimension}
Let $C\subset\PP^2_K$ be a reduced curve over an algebraically closed
field $K$, and let $N\geq0$. Then
\[
\dim\operatorname{Hilb}^N(C)\leq N.
\]
\end{lemma}
\begin{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
\[
\{f\in K[x,y]:f(A,B)v=0\},
\]
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
\[
\dim P_\ell+\ell^2\leq\ell^2+\ell-1,
\qquad \dim P_\ell\leq\ell-1.
\]
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.
\end{proof}
\subsection{The matrix fibers and the gradient locus}
We now use the universal family of length-$N$ subschemes to compare the
matrix fiber with $\operatorname{Hilb}^N(C)$.
\begin{proposition}[Dimension of a matrix fiber]\label{prop:matrix-fiber}
For the morphism $f_D$ in \eqref{eq:determinant-curve-map}, every fiber
has dimension at most $N=k(k-1)/2$.
\end{proposition}
\begin{proof}
Fix a curve $C$ in the image and its fiber $\mathcal F_C$. Form
\[
\mathcal I_C=
\{(X,Z')\in\mathcal F_C\times\operatorname{Hilb}^N(C):
R_X|_{Z'}=0\}.
\]
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~\ref{lem:row-adjugate-scheme}. 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
\[
\dim\mathcal F_C
\leq\dim\mathcal I_C
\leq\dim\operatorname{Hilb}^N(C)
\leq N,
\]
where the last inequality is Lemma~\ref{lem:hilbert-curve-dimension}.
\end{proof}
\begin{proof}[Proof of Proposition~\ref{prop:gradient-codimension}]
By \eqref{eq:dimension-gradient-defect}, every curve in
$f_D(\Gamma_D)$ has normalization defect at least $T$.
Lemma~\ref{lem:severi-dimension} 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~\ref{prop:matrix-fiber}.
Consequently
\[
\dim\Gamma_D
\leq\frac{k(k+3)}2-T+\frac{k(k-1)}2
=k^2+k-T,
\]
as asserted.
\end{proof}
==== END A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//dimension.tex ====
==== BEGIN A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//introduction.tex ====
\section{Introduction}
\label{sec:introduction}
For a matrix $X=(x_{ij})$ of independent variables, the permanent is
\[
\per_m(X)=\sum_{\sigma\in S_m}\prod_{i=1}^m x_{i,\sigma(i)}.
\]
The permanent--determinant problem asks how large a determinant of
affine-linear forms is needed to express $\per_m$. Valiant connected
determinant projections to arithmetic formulas: his construction represents
a polynomial computed by a formula with $s$ addition or multiplication
operations as a determinant of order $s+2$
\cite[Theorem~1]{Valiant1979Algebra}. His algebraic completeness theorem
shows that, in characteristic different from two, polynomial families
defined by summing polynomial-size formulas over Boolean strings of
polynomial length are projections of polynomial-size permanents
\cite[Theorem~2]{Valiant1979Algebra}. Valiant's projections substitute
individual variables or field constants. The exact model below allows
every matrix entry to be an arbitrary affine-linear form.
For $f\in\C[x_1,\ldots,x_N]$, its \emph{determinantal complexity}
$\dc(f)$ is the least positive integer $n$ for which
\[
f=\det\left(A_0+\sum_{j=1}^N x_jA_j\right),
\qquad A_0,\ldots,A_N\in\Mat_n(\C).
\]
Its \emph{border determinantal complexity} $\bdc(f)$ is the least positive
integer $n$ such that $f$ lies in the coefficientwise closure of
\begin{equation}
\left\{\det\left(A_0+\sum_{j=1}^N x_jA_j\right):
A_0,\ldots,A_N\in\Mat_n(\C)\right\}.
\label{eq:border-definition}
\end{equation}
The closure is taken in the finite-dimensional space of polynomials of
degree at most $n$; a polynomial of larger degree cannot belong to it.
We allow $f$ to be constant or zero. Coefficientwise closure agrees with
Zariski closure here, as explained in Section~\ref{sec:models}. The size
$n$ stays fixed along an approximating sequence, while the complex
coefficients of its matrix entries are unrestricted.
\begin{theorem}
\label{thm:main}
There exist absolute constants $c>0$ and $m_0$ such that, for every integer
$m\ge m_0$,
\[
\bdc(\per_m)\ge c m^3.
\]
One may take $c=1/(5\,529\,600e)$ and $m_0=1408$.
\end{theorem}
The constants are not optimized. Proposition~\ref{prop:model-equivalence}
identifies this coefficientwise model with the projective determinant-orbit
closure formulation, including equal permanent and determinant orders.
The same numerical lower bound holds for exact determinantal complexity.
There is also a consequence for algebraic branching programs. An
affine-linear algebraic branching program is a finite directed acyclic
graph with a source and a sink and an affine-linear form on each edge; it
computes the sum of products of edge labels along all source-to-sink paths.
Over $\C$, computing $\per_m$ requires $\Omega(m^3)$ vertices and
$\Omega(m^3)$ edges. The same bounds hold for coefficientwise limits when
the relevant vertex or edge budget remains fixed along the approximation,
even if the graph varies. Section~\ref{sec:consequences} gives the precise
statements and determinant reductions.
\subsection{Earlier bounds and geometric methods}
The early matrix-order lower bounds were linear in the permanent order $m$.
For the variable-or-constant projection model, von zur Gathen published a
bound due to Babai and Seress with leading term $\sqrt{2}\,m$ and a loss of
$6\sqrt m$ \cite[Theorem~4.4]{vonZurGathen1987}. For arbitrary affine
representations over $\C$, Meshulam's final theorem
\cite[pp.~270--271]{Meshulam1989} and Cai's dimension argument
\cite[Theorem~1.5 and Section~2.2]{Cai1990} give the scale
$\sqrt{2}\,m-O(1)$. Their arguments compare the dimension of the affine
matrix image with the minimum rank that an exact permanent representation
must have.
Mignon and Ressayre raised the exact lower bound to
$\dc(\per_m)\ge m^2/2$ in characteristic zero
\cite{MignonRessayre2004}. Their proof compares Hessians at a zero:
affine pullback cannot increase Hessian rank, the Hessian of an order-$n$
determinant has rank at most $2n$ at a noninvertible matrix, and, for
$m\ge2$, the permanent has a zero where its Hessian has full rank $m^2$.
Cai, Chen and Li extended the quadratic scale to positive characteristic
different from two by constructing sparse zeros that avoid the large
factorial factors in the earlier Hessian calculation
\cite[Theorem~2.3]{CaiChenLi2010}.
On the upper side, Grenet's construction realizes $\per_m$ as a determinant
of order $2^m-1$, using a branching program indexed by the subsets of
$\{1,\ldots,m\}$ \cite[unnumbered Theorem, p.~3]{Grenet2012}.
Its determinant entries are individual variables and constants, so it is
also an upper bound in the unrestricted exact model.
Mulmuley and Sohoni's geometric complexity theory program studies
permanent--determinant separation through orbit closures of determinants
and padded permanents, seeking equations or representation-theoretic
obstructions to containment
\cite{MulmuleySohoni2001,MulmuleySohoni2008}.
Landsberg, Manivel and Ressayre proved the unrestricted complex border
bound $\bdc(\per_m)\ge m^2/2$ by studying hypersurfaces with degenerate
duals and the effect of padding
\cite[Theorem~1.1.1]{LandsbergManivelRessayre2010}.
Theorem~\ref{thm:main} raises the lower-bound exponent from two to three
in that same model. It remains a fixed polynomial bound. Whether the
permanent has superpolynomial determinantal complexity, or superpolynomial
border determinantal complexity, remains open.
Landsberg and Ressayre later proved exponential optima for exact
representations with symmetry requirements. Each specified projective
symmetry of the input must lift to a projective symmetry of the determinant
that fixes the pencil's constant matrix, preserves the image of its linear
part, and induces the given input action there. Over $\C$, for $m\ge3$,
requiring this for left multiplication by invertible diagonal and
permutation matrices gives minimum order $2^m-1$. Lifting the full
projective symmetry group of the permanent gives minimum order
$\binom{2m}{m}-1$ in the same range
\cite[Theorems~2.1 and~2.8; Propositions~2.9 and~2.10]{LandsbergRessayre2017}.
These hypotheses specify exact representation classes; the border model
of Theorem~\ref{thm:main} allows arbitrary affine determinant
approximations of fixed order.
Singularities also give geometric lower bounds for exact representations.
For a homogeneous polynomial of degree greater than two whose affine
singular locus has codimension greater than four, Alper, Bogart and Velasco
prove
$\dc(f)\ge\operatorname{codim}\operatorname{Sing}(f)+1$
\cite[Theorem~1.2]{AlperBogartVelasco2017}.
For the permanent, matrices with two zero columns show that this
codimension is at most $2m$, so this obstruction alone has only a linear
scale \cite[Remark~1.5]{AlperBogartVelasco2017}.
Our construction instead obtains a coefficient polynomial from a permanent
and finds a linear subspace on which its zero hypersurface is smooth. Its
degree is linear and the subspace dimension is quadratic in an auxiliary
matrix size.
For a smooth complex form of degree $r\ge2$ in $d\ge2$ variables, the classical
top polar degree is $r(r-1)^{d-2}$
\cite[Corollary~3.7]{Piene1978}.
The left and right kernel equations for the determinant matrix and the
Schur-complement reduction used below also appear in Sheshadri's June 2026
preprint \cite[Theorem~3 and Section~3.1]{SheshadriBorder2026}, as part of
its proposed conormal approach to border bounds for diagonal power sums.
Kumar and Volk's September 2026 preprint uses such kernel equations and a
multihomogeneous count to obtain a quadratic \emph{exact} lower bound for
$\sum_{i=1}^n x_i^n$
\cite[Theorem~1.1 and Section~3]{KumarVolk2026}.
Theorem~\ref{thm:smooth-border} proves the version needed here, including
persistence of finitely many simple polar intersections in one sufficiently
close determinant under an arbitrary coefficientwise approximation. Its
lower bound is proportional to the product $(r-1)(d-1)$.
\subsection{The coefficient construction and the proof}
To use this product at cubic scale, we seek an affine restriction of a
permanent of size proportional to $k$ that has degree proportional to $k$
in quadratically many variables and has a smooth projective zero set.
Let $k\ge1$ and $0\le q\le\lfloor k/2\rfloor$ be integers. With
indeterminates $\theta_1,\ldots,\theta_k$, put
$D=\diag(\theta_1,\ldots,\theta_k)$ and define
\[
G_D(X)=[s^qt^q]\per_k(X+sI+tD)
\in\mathbb Z[\theta_1,\ldots,\theta_k][X_{ij}].
\]
This polynomial is homogeneous of degree $r=k-2q$ in the $k^2$ entries
of $X$. We use the same notation after specializing the parameters in a
field. For the main construction we assume $k\ge128$ and take
$q=\lfloor(k-1)/3\rfloor$; then $r$ is linear in $k$ and
$T=\binom{q+2}{2}$ is quadratic in $k$.
The integral formula has two uses. Over $\C$, two count gates and a
cancellation gadget realize $G_D$, up to a fixed nonzero scalar, as an
affine restriction of a permanent of size $11k-2q$
(Proposition~\ref{prop:selector}). This holds for every complex choice of
the parameters. The scalar vanishes in characteristic two, so the geometric
argument specializes the integral coefficient formula itself. We will use
the complex projection at the complex parameter choice that geometry
eventually supplies.
Let $K=\overline{\mathbb F}_2$, choose pairwise distinct
$\bar\theta_1,\ldots,\bar\theta_k\in K$, and write
$\bar D=\diag(\bar\theta_1,\ldots,\bar\theta_k)$. Since permanent
and determinant agree over $K$, every matrix $X$ defines a plane curve
\[
C_X=V\bigl(\det(sI+t\bar D+uX)\bigr)\subset\PP^2_K.
\]
Its fiber on $u=0$ consists of the distinct points
$[-\bar\theta_i:1:0]$. This fixed fiber makes the curve reduced and its
projection to $[t:u]$ finite and generically separable, and it controls the adjugate
of $sI+t\bar D+uX$ on the curve. The full adjugate defines a finite
subscheme $Z\subset C_X$. If all entrywise derivatives of $G_{\bar D}$
vanish at $X$, the coefficient $[s^qt^qu^{r-1}]$ of every adjugate entry
vanishes. We prove that these
entries span all degree-$(k-1)$ forms vanishing on $Z$, so the same
coefficient vanishes on every such form. For a degree-$q$ monomial
$s^it^ju^\ell$, multiplication by $s^{q-i}t^{q-j}u^{r-1-\ell}$ lets this
functional recover its coefficient in any degree-$q$ form. These exponents
are nonnegative because $r-1\ge q$. Thus restriction of degree-$q$ forms to $Z$ is
injective, giving the length bound in Proposition~\ref{prop:adjugate-length}:
\[
K[s,t,u]_q\hookrightarrow H^0(Z,\cO_Z(q)),
\qquad \length Z\ge\dim_K K[s,t,u]_q=T.
\]
The length of $Z$ is bounded above by the \emph{normalization defect}
$\delta(C_X)$, the length of the quotient between the normalization's
structure sheaf and the curve's structure sheaf. The comparison follows
the evaluation-ideal argument of Fantechi, G\"ottsche and van Straten
over $\C$ \cite[Proposition~C.2 and Corollary~C.3]{FGvS1999};
Section~\ref{sec:conductor} proves the needed conductor inclusion and
colength identity for our generically separable pencils in arbitrary
characteristic.
Thus every critical matrix lies over a curve with $\delta(C_X)\ge T$.
Applying the arbitrary-characteristic Severi dimension theorem of Christ,
He and Tyomkin \cite[Lemma~2.6, Proposition~2.7, and Remark~2.8]{CHT2023}
to the integral components bounds the locus of curves with this defect.
Their result builds on Tyomkin's dimension bound for toric pairs
\cite[Theorem~1.2(1)]{Tyomkin2013}. The sum
$R_X=(1,\ldots,1)\adj(sI+t\bar D+uX)$ of the adjugate rows controls
the matrices over one fixed curve: its zero subscheme has length
$k(k-1)/2$, and the common
boundary frame makes that subscheme determine the matrix uniquely.
A Hilbert-scheme estimate and an algebraic incidence then bound the
dimension of each matrix fiber. Combining the curve and matrix bounds gives
\[
\dim\{X:\nabla G_{\bar D}(X)=0\}\le k^2+k-T,
\qquad
\codim\{X:\nabla G_{\bar D}(X)=0\}\ge T-k.
\]
The projective zero scheme of the raw partial derivatives forms a proper
family over the integral parameter space. Specialization transfers the
dimension bound to a nonempty open set of complex parameters. Over $\C$,
Euler's identity identifies these gradient zeros with the hypersurface's
singular scheme, and a general linear section avoids that scheme and meets
the smooth locus transversely. Proposition~\ref{prop:smooth-projection}
then supplies, for $k\ge128$ and the stated choice of $q$, a nonzero form
$G$ of degree $r$ in $d=\lfloor k^2/100\rfloor$ variables whose
projective zero set is smooth. For each $m\ge11k-2q$, it also supplies
a fixed affine map $\Phi_m$ satisfying $G=\per_m\circ\Phi_m$.
Figure~\ref{fig:proof-flow} shows how the two uses of the coefficient
formula meet and how the polar bound converts their output into the cubic
estimate.
\input{figures/proof-flow}
Sections~\ref{sec:selector}--\ref{sec:transfer} establish this
construction. Section~\ref{sec:polar} then proves the smooth-form bound
stated in Section~\ref{sec:models}, using selected simple polar
intersections and the left and right kernels of one nearby determinant.
Section~\ref{sec:consequences} combines the two results and gives the
exact, branching-program, and smooth-initial-form consequences.
\FloatBarrier
==== END A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//introduction.tex ====
==== BEGIN A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//main.tex ====
\documentclass[11pt]{article}
\def\DoNotLoadEpstopdf{}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{microtype}
\usepackage{booktabs,array}
\usepackage{placeins}
\usepackage{etoolbox}
\usepackage{xcolor}
\usepackage[colorlinks=true,linkcolor=blue!45!black,citecolor=blue!45!black,urlcolor=blue!45!black]{hyperref}
\usepackage[figure]{hypcap}
\usepackage[nameinlink,capitalize,noabbrev]{cleveref}
\makeatletter
\newcommand\chResultRefstepcounter[2][]{%
\let\chSavedCrefRefstepcounter\cref@old@refstepcounter
\let\cref@old@refstepcounter\Hy@theorem@refstepcounter
\refstepcounter[#1]{#2}%
\let\cref@old@refstepcounter\chSavedCrefRefstepcounter
}
\AddToHook{begindocument/end}{%
\patchcmd{\cref@thmnoarg}
{\refstepcounter}{\Hy@theorem@refstepcounter}
{}{\PackageError{ch418}{Could not patch the plain theorem counter path}{%
Recheck the amsthm, hyperref, and cleveref versions.}}%
\patchcmd{\cref@thmoptarg}
{\refstepcounter}{\chResultRefstepcounter}
{}{\PackageError{ch418}{Could not patch the shared theorem counter path}{%
Recheck the amsthm, hyperref, and cleveref versions.}}%
}
\makeatother
\AddToHook{cmd/thebibliography/after}{%
\addcontentsline{toc}{section}{\refname}%
}
\pdfinfoomitdate=1
\pdftrailerid{}
\pdfsuppressptexinfo=15
\hypersetup{pdftitle={A cubic lower bound for border determinantal complexity of the permanent},pdfauthor={OpenAI}}
\numberwithin{equation}{section}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\C}{\mathbb C}
\newcommand{\PP}{\mathbb P}
\newcommand{\cO}{\mathcal O}
\DeclareMathOperator{\Mat}{Mat}
\DeclareMathOperator{\per}{per}
\DeclareMathOperator{\dc}{dc}
\DeclareMathOperator{\bdc}{\overline{dc}}
\DeclareMathOperator{\adj}{adj}
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\length}{length}
\DeclareMathOperator{\Hom}{Hom}
\DeclareMathOperator{\Hilb}{Hilb}
\DeclareMathOperator{\GL}{GL}
\DeclareMathOperator{\End}{End}
\DeclareMathOperator{\Spec}{Spec}
\DeclareMathOperator{\Gr}{Gr}
\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\im}{im}
\DeclareMathOperator{\coker}{coker}
\DeclareMathOperator{\diag}{diag}
\DeclareMathOperator{\Sing}{Sing}
\DeclareMathOperator{\Supp}{Supp}
\DeclareMathOperator{\codim}{codim}
\newcommand{\dd}{\mathrm d}
\title{A cubic lower bound for border determinantal complexity of the permanent}
\author{OpenAI}
\date{September 24, 2026}
\begin{document}
\maketitle
\begin{abstract}
We prove that the complex border determinantal complexity of the $m\times m$
permanent is $\Omega(m^3)$, allowing arbitrary affine-linear determinant
representations and coefficientwise limits. It also gives cubic lower bounds
for exact determinantal complexity and for the numbers of vertices and edges
in affine-linear algebraic branching programs, including coefficientwise
limits with a fixed vertex or edge budget.
\end{abstract}
\tableofcontents
\input{sections/introduction}
\input{sections/models}
\input{sections/selector}
\input{sections/adjugate}
\input{sections/conductor}
\input{sections/dimension}
\input{sections/transfer}
\input{sections/polar}
\input{sections/consequences}
\bibliographystyle{plain}
\bibliography{references}
\end{document}
==== END A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//main.tex ====
==== BEGIN A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//models.tex ====
\section{Border models and smooth homogeneous forms}
\label{sec:models}
We first identify the two border models precisely. All closures in this
section are over $\C$. In a finite-dimensional polynomial space, coefficientwise
convergence means ordinary convergence of the coefficients of every monomial.
The image of a polynomial map is constructible
\cite[Theorem~29.23.3, Tag~054K]{StacksProject}, and a complex constructible
set has the same Euclidean and Zariski closures. For the latter fact, decompose
the set into finitely many locally closed subsets: each contains a Zariski
open dense subset of its closure, which is also Euclidean dense. These facts
apply both to the polynomial map taking an affine matrix to its determinant
and to the action map defining a linear-group orbit. Thus coefficientwise
sequences can be used for either closure below.
\begin{lemma}[Affine substitution]
\label{lem:affine-substitution}
Let $f$ be a complex polynomial, let $A$ be an affine map into its variable
space, and let $a\ne0$ be a complex scalar. Then
\[
\bdc(a f\circ A)\le \bdc(f).
\]
\end{lemma}
\begin{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.
\end{proof}
For $n\ge m$, let $W_n=\Mat_n(\C)$ and regard $\det_n$ as a degree-$n$
form on $W_n$. Choose $m^2$ independent linear coordinates $x_{ij}$ on $W_n$.
If $n>m$, choose one more independent coordinate $z$ and set
\[
P_{n,m}=z^{n-m}\per_m(x).
\]
If $n=m$, set $P_{m,m}=\per_m(x)$; no padding coordinate is needed.
Let $\mathcal D_n$ be the projective Zariski closure of the orbit of
$[\det_n]$ under invertible linear substitutions on $W_n$.
\begin{proposition}[Equivalence of the two border models]
\label{prop:model-equivalence}
For every $n\ge m\ge1$,
\[
\bdc(\per_m)\le n
\quad\Longleftrightarrow\quad
[P_{n,m}]\in\mathcal D_n.
\]
\end{proposition}
\begin{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
\[
Q_j(x)=\det\left(A_{j,0}+\sum_{a,b=1}^m x_{ab}A_{j,ab}\right)
\longrightarrow\per_m(x).
\]
For $n>m$, homogenize to degree $n$ using the independent coordinate $z$:
\[
Q_j^{\mathrm{hom}}(x,z)=\det\left(zA_{j,0}+\sum_{a,b=1}^m x_{ab}A_{j,ab}\right)
\longrightarrow z^{n-m}\per_m(x).
\]
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
\[
\det\left(\sum_{a,b=1}^m x_{ab}A_{j,ab}\right),
\]
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.
\end{proof}
The quantitative obstruction used in the proof depends on the degree and
the number of variables of a smooth homogeneous polynomial. Here smoothness
means that the projective zero set has no point at which all first partial
derivatives vanish.
\begin{theorem}[Lower bound for smooth homogeneous forms]
\label{thm:smooth-border}
Let $G\in\C[x_1,\ldots,x_d]$ be a nonzero homogeneous polynomial of degree
$r\ge2$, where $d\ge2$. If its zero set in $\PP^{d-1}$ is smooth, then
\[
\bdc(G)\ge \frac{(r-1)(d-1)}{4e}.
\]
\end{theorem}
The complete proof is in Section~\ref{sec:polar}. For a constant vector
$w\in\C^d$, write
\[
\partial_wG=\sum_{j=1}^d w_j\frac{\partial G}{\partial x_j}
\]
for the first directional derivative, or \emph{first polar}, of $G$.
If $G$ is a coefficientwise limit of affine determinants of size $n$, the proof
chooses $d-2$ first polars whose common intersection with the hypersurface
consists of $r(r-1)^{d-2}$ simple points. It then shows that these selected
points persist for one sufficiently close determinant and satisfy
\begin{equation}
r(r-1)^{d-2}
\le 2^{d-2}\binom{2n-1}{d-1}
\le \left(\frac{4en}{d-1}\right)^{d-1}.
\label{eq:smooth-count-synopsis}
\end{equation}
The binomial coefficient is understood to be zero when $d-1>2n-1$;
in that case the positive left side already rules out the approximation.
The first inequality comes from lifting the selected points to the right
and left kernel lines of the determinant matrix and counting the resulting
bilinear equations. Taking the $(d-1)$st root gives the theorem. The proof
establishes persistence and simplicity of those selected lifts using only
coefficientwise closeness of the determinant polynomials, so it allows
unbounded coefficients in the approximating matrices.
This comparison specifies our construction's target. A nonzero homogeneous
form of degree proportional to $k$ in quadratically many variables, with
a smooth projective zero set, forces cubic determinant size. We now produce
such a form as a fixed affine restriction of a permanent whose size is
linear in $k$.
==== END A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//models.tex ====
==== BEGIN A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//polar.tex ====
\section{Counting polars of a smooth hypersurface}\label{sec:polar}
We now prove Theorem~\ref{thm:smooth-border}. A smooth degree-$r$
hypersurface in $\PP^{d-1}$ supplies $r(r-1)^{d-2}$ simple intersections
with first polars. These points persist for one sufficiently close affine
determinant. Right and left kernel variables then express each selected
intersection by bilinear equations, whose multidegrees give the numerical
comparison stated in Section~\ref{sec:models}. The determinant kernel-incidence
count and its Schur-complement reduction
build on \cite[Theorem~3 and Section~3.1]{SheshadriBorder2026}. We give the
argument needed here for finitely many simple polar intersections,
including unrestricted affine limits and possible excess components of
the incidence.
For a constant vector $w\in\C^N$, write
\[
\partial_w F=\sum_{j=1}^N w_j\frac{\partial F}{\partial x_j}.
\]
We call this an ambient first polar: after restricting to an affine slice,
the direction $w$ need not be tangent to the slice. A common zero of $s$
equations in $s$ local coordinates is \emph{simple} if its full Jacobian
is invertible.
\subsection{Simple polar intersections}
The numerical count below is the classical top polar degree of a smooth
hypersurface \cite[Corollary~3.7]{Piene1978}. We give the transversality
argument to retain the individual simple points needed in the limit.
General-transversality principles of this kind are developed in
\cite[Corollary~5]{Kleiman1974}; the argument below works directly over
$\C$ with the incidence of polar directions.
\begin{lemma}\label{polar:simple-points}
Let $r,d\ge2$, and let $G\in\C[x_1,\ldots,x_d]$ be homogeneous of degree
$r$. Suppose that $Y=V(G)\subset\PP^{d-1}$ is a smooth hypersurface.
There are constant directions $w_1,\ldots,w_{d-2}\in\C^d$ for which
\begin{equation}\label{polar:projective-certificate}
G=0,\qquad \partial_{w_i}G=0\quad(1\le i\le d-2)
\end{equation}
has exactly $\mu=r(r-1)^{d-2}$ distinct simple projective solutions.
There is a linear form $L_0$ nonzero at every one of these points.
\end{lemma}
\begin{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
\[
\mathcal I=\{(x,w_1,\ldots,w_{d-2})\in Y\times\mathcal P:
\partial_{w_i}G(x)=0\text{ for every }i\}.
\]
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~\eqref{polar:projective-certificate} is
simple there.
This is a proper intersection of hypersurfaces of degrees
$r,r-1,\ldots,r-1$ in $\PP^{d-1}$. Projective B\'ezout 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.
\end{proof}
\subsection{A count that permits excess components}
The kernel equations below need not meet properly everywhere, so we count
only their selected simple zeros. The coefficient in the next lemma is
the multihomogeneous B\'ezout number. Its standard specialization bound
controls nonsingular isolated zeros even when other components are present
\cite[Sections~3--3.2]{Wampler1996}. We give a direct proof of the bilinear
case needed here.
\begin{lemma}\label{polar:product-count}
Let $Y=\prod_{j=1}^s\PP^{a_j}$, where $a_j\ge0$ and
$M=\sum_j a_j\ge1$. For each $1\le\ell\le M$, let $F_\ell$ be a
multihomogeneous polynomial of degree one in two distinct coordinate
groups, indexed by $u_\ell,v_\ell$, and degree zero in the other groups.
Any finite collection of distinct simple common zeros of these equations
has size at most
\begin{equation}\label{polar:product-coefficient}
[H_1^{a_1}\cdots H_s^{a_s}]
\prod_{\ell=1}^M(H_{u_\ell}+H_{v_\ell}).
\end{equation}
Other zeros and components of any dimension are allowed.
\end{lemma}
\begin{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
\[
z_0+t z_1+\cdots+t^{a_j}z_{a_j}
\]
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
\[
M\le\sum_j b_j\le\sum_j a_j=M.
\]
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
\eqref{polar:product-coefficient} 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
\[
F_{\ell,t}=(1-t)Q_\ell+tF_\ell\qquad(t\in\C).
\]
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$.
\end{proof}
\subsection{Ambient polars of affine determinant limits}
We next apply the product count to an arbitrary affine determinant
approximation. The directions in the statement remain ambient directions;
this permits us to use a projective polar certificate on an affine chart.
\begin{proposition}\label{polar:ambient-bound}
Let $N,n,\mu\ge1$ and $h\ge0$ be integers. Suppose that
$P\in\C[x_1,\ldots,x_N]$ is a coefficientwise limit of determinants of
$n\times n$ matrices of affine-linear forms. Let
$\Psi:\C^{h+1}\to\C^N$ be an affine map and
$w_1,\ldots,w_h\in\C^N$ constant directions. If
\begin{equation}\label{polar:affine-certificate}
P(\Psi(\xi))=0,\qquad
(\partial_{w_i}P)(\Psi(\xi))=0\quad(1\le i\le h)
\end{equation}
has at least $\mu$ distinct simple zeros, then
\begin{align}
\mu&\le [H^{h+1}U^{n-1}V^{n-1}]
(H+U)^n(H+V)^{n-1}(U+V)^h\label{polar:ambient-coefficient}\\
&\le 2^h\binom{2n-1}{h+1},\notag\\
n&\ge\frac{h+1}{4e}\mu^{1/(h+1)}.\label{polar:ambient-size}
\end{align}
The binomial coefficient is zero if $h+1>2n-1$.
\end{proposition}
\begin{proof}
\emph{Choose one sufficiently close determinant.}
Fix $\mu$ distinct simple zeros of~\eqref{polar:affine-certificate}.
All output polynomials lie in the finite-dimensional coefficient space
of degree at most $n$. With $\Psi$ and the $w_i$ fixed, the map
\[
(Q,\xi)\longmapsto
\bigl(Q(\Psi(\xi)),(\partial_{w_1}Q)(\Psi(\xi)),\ldots,
(\partial_{w_h}Q)(\Psi(\xi))\bigr)
\]
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,
\begin{equation}\label{polar:chosen-matrix}
Q(x)=\det A(x),\qquad
A(x)=A_0+\sum_{j=1}^N x_jA_j,\qquad A_j\in\Mat_n(\C),
\end{equation}
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.
\emph{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
\[
B_i=\partial_{w_i}A=\sum_{j=1}^N(w_i)_j A_j.
\]
These are constant matrices, and
$\partial_{w_i}Q=\tr(\adj(A)B_i)$.
\emph{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
\[
\PP^{h+1}_{[\xi_0:\xi]}\times\PP^{n-1}_p\times\PP^{n-1}_b
\]
use the equations
\begin{equation}\label{polar:kernel-system}
A^{\mathrm{hom}} p=0,\qquad
(b^{\mathsf T}A^{\mathrm{hom}})_j=0\quad(2\le j\le n),\qquad
b^{\mathsf T}B_i p=0\quad(1\le i\le h).
\end{equation}
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
\[
0=b^{\mathsf T}(A^{\mathrm{hom}} p)
=p_1(b^{\mathsf T}A^{\mathrm{hom}})_1+
\sum_{j=2}^n p_j(b^{\mathsf T}A^{\mathrm{hom}})_j.
\]
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
\eqref{polar:kernel-system}.
The lift is not yet known to be simple. We prove this locally before
applying Lemma~\ref{polar:product-count}; other components of the kernel
system will impose no further requirement.
\begin{samepage}
\emph{Eliminate the kernel coordinates.}
Fix one selected lift and normalize $p_1=1$. Choose a nonzero coordinate
of its left kernel vector, move that row to the first position, and
normalize the corresponding left coordinate to one. These are local
coordinate choices, which can differ between selected points. The
cofactor obtained by deleting this first row and first column is nonzero,
because it is the corresponding entry of $\rho p b^{\mathsf T}$.
In these row orders write the ambient matrix near $\Psi(\xi)$ as
\[
A(x)=\begin{pmatrix}a(x)&\beta(x)\\\gamma(x)&E(x)\end{pmatrix},
\qquad
p=\binom{1}{u},\qquad b=\binom{1}{v},
\]
where $E$ has size $(n-1)\times(n-1)$. The chosen cofactor makes $E$
invertible at the selected point, so restrict to an ambient neighborhood
on which it is invertible. When $n=1$, $E$ is the empty matrix with
determinant one, and the auxiliary vectors $u,v$ are empty.
\end{samepage}
The same row permutation is applied to every $B_i$. The last $n-1$ right
equations and all retained left equations give
\[
\gamma+Eu=0,\qquad \beta+v^{\mathsf T}E=0.
\]
Their auxiliary Jacobian has invertible diagonal blocks $E,E^{\mathsf T}$,
so they eliminate the kernel coordinates holomorphically as
\begin{equation}\label{polar:solved-kernels}
u=-E^{-1}\gamma,\qquad v^{\mathsf T}=-\beta E^{-1}.
\end{equation}
The remaining right equation, evaluated on the slice, is
\[
s(\xi)=S(\Psi(\xi))=0,
\qquad S(x)=a(x)-\beta(x)E(x)^{-1}\gamma(x).
\]
The Schur determinant identity gives
\begin{equation}\label{polar:schur-determinant}
Q(x)=\sigma\det(E(x))S(x),
\end{equation}
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~\eqref{polar:solved-kernels}, let
$g_i(\xi)$ denote the bilinear equation $b^{\mathsf T}B_i p$.
For any constant ambient direction $w$, differentiation of $S$ gives
\begin{align*}
\partial_w S
&=\partial_w a-(\partial_w\beta)E^{-1}\gamma
+\beta E^{-1}(\partial_w E)E^{-1}\gamma
-\beta E^{-1}(\partial_w\gamma)\\
&=(1,-\beta E^{-1})(\partial_w A)
\binom{1}{-E^{-1}\gamma}.
\end{align*}
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
\eqref{polar:schur-determinant} in the ambient space yields
\begin{equation}\label{polar:reduced-system}
\begin{gathered}
f=c\,s,\qquad q_i=c\,g_i+c_i s,\\
c=\sigma(\det E)\circ\Psi\ne0,\qquad
c_i=\sigma(\partial_{w_i}\det E)\circ\Psi.
\end{gathered}
\end{equation}
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
\eqref{polar:kernel-system}.
\emph{Count the selected lifts.}
The three groups of equations in~\eqref{polar:kernel-system} have
multidegrees and multiplicities
\[
\begin{array}{c|c|c}
\text{equations}&\text{multidegree}&\text{number}\\ \hline
A^{\mathrm{hom}} p &(1,1,0)&n\\
(b^{\mathsf T}A^{\mathrm{hom}})_j, j\ge2 &(1,0,1)&n-1\\
b^{\mathsf T}B_i p &(0,1,1)&h.
\end{array}
\]
Lemma~\ref{polar:product-count} gives the first inequality
in~\eqref{polar:ambient-coefficient}, 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
\[
[H^{h+1}]\,2^h(H+1)^{2n-1}
=2^h\binom{2n-1}{h+1}.
\]
Since $\mu>0$, we must have $h+1\le2n-1$. For integers $1\le b\le a$,
\[
\binom ab\le\frac{a^b}{b!}\le\left(\frac{ea}{b}\right)^b;
\]
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
\[
\mu^{1/(h+1)}
\le2^{h/(h+1)}\frac{e(2n-1)}{h+1}
\le\frac{4en}{h+1},
\]
which is~\eqref{polar:ambient-size}. No comparison between $n$ and
the number $N$ of ambient variables, or between $n$ and $h+2$, was assumed.
\end{proof}
\subsection{The smooth-hypersurface lower bound}
We have proved that a fixed finite set of simple polar intersections
persists under arbitrary affine determinant approximation, and that its
kernel lifts satisfy the multidegree bound. We now use the certificate
provided by the smooth hypersurface.
\begin{proof}[Proof of Theorem~\ref{thm:smooth-border}]
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~\ref{polar:simple-points}. 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
\[
\Psi:\C^{d-1}\longrightarrow\{x\in\C^d:L_0(x)=1\}.
\]
Restricting the homogeneous equations to this hyperplane is precisely
their dehomogenization in that projective chart. Thus the equations
\[
G\circ\Psi=0,\qquad
(\partial_{w_i}G)\circ\Psi=0\quad(1\le i\le d-2)
\]
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~\ref{polar:ambient-bound} with $N=d$, $h=d-2$, and
$P=G$. It gives
\[
n\ge\frac{d-1}{4e}
\bigl(r(r-1)^{d-2}\bigr)^{1/(d-1)}
\ge\frac{(r-1)(d-1)}{4e},
\]
where the last inequality uses $r\ge r-1>0$. This holds for every
admissible size $n$, so taking the minimum proves the theorem.
\end{proof}
==== END A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//polar.tex ====
==== BEGIN A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//proof-flow.tex ====
\begin{figure}[tbp]
\centering
\setlength{\fboxsep}{7pt}
\fbox{\begin{minipage}{0.90\linewidth}
\centering
\textbf{One integral coefficient polynomial}\\[3pt]
$\displaystyle G_D(X)=[s^qt^q]\per_k(X+sI+tD)
\in\mathbb Z[\theta_1,\ldots,\theta_k][X_{ij}]$\\[3pt]
$\displaystyle D=\diag(\theta_1,\ldots,\theta_k),\qquad
r=k-2q,\qquad T=\binom{q+2}{2}$
\end{minipage}}
\smallskip
\begin{tabular}{@{}c@{\hspace{0.025\linewidth}}c@{}}
\begin{minipage}{0.43\linewidth}\centering
$\swarrow$\quad over $\C$, every parameter choice
\end{minipage}
&
\begin{minipage}{0.43\linewidth}\centering
$\searrow$\quad over $K=\overline{\mathbb F}_2$, choose distinct parameters
\end{minipage}
\\[4pt]
\fbox{\begin{minipage}{0.405\linewidth}\centering
\textbf{Permanent projection}\\[3pt]
$\displaystyle \per_m(A_m(X))=a_0G_D(X)$\\[3pt]
$m\ge11k-2q,\qquad a_0\ne0$
\end{minipage}}
&
\fbox{\begin{minipage}{0.405\linewidth}\centering
\textbf{Plane-curve geometry}\\[3pt]
$\displaystyle \nabla G_{\bar D}(X)=0
\ \Longrightarrow\ \delta(C_X)\ge T$\\[3pt]
$\displaystyle \codim V(\nabla G_{\bar D})\ge T-k$
\end{minipage}}
\\[5pt]
\begin{minipage}{0.43\linewidth}\centering
$\searrow$\quad apply at the complex parameters supplied by geometry
\end{minipage}
&
\begin{minipage}{0.43\linewidth}\centering
$\swarrow$\quad proper specialization and a transverse linear section
\end{minipage}
\end{tabular}
\smallskip
\fbox{\begin{minipage}{0.90\linewidth}
\centering
\textbf{A smooth affine restriction over $\C$}\\[3pt]
A nonzero homogeneous form $G$ of degree $r$ in $d$ variables has a smooth
projective zero set and satisfies $G=\per_m\circ\Phi_m$ for a fixed affine map $\Phi_m$.\\[3pt]
$\displaystyle r-1\ge\frac{k}{4},\qquad
d-1\ge\frac{k^2}{200}$
\end{minipage}}
\smallskip
$\big\downarrow$\quad the polar count for smooth homogeneous forms
\smallskip
\fbox{\begin{minipage}{0.90\linewidth}
\centering
$\displaystyle
\bdc(\per_m)\ge\bdc(G)
\ge\frac{(r-1)(d-1)}{4e}
\ge\frac{k^3}{3200e}$
\end{minipage}}
\caption{The two uses of the integral coefficient formula meet over
$\C$. The graph projection applies to every complex parameter choice;
the characteristic-two branch supplies a suitable complex choice through
the proper parameter family. The displayed scale bounds use
$q=\lfloor(k-1)/3\rfloor$, $k\ge128$, and $m\ge11k-2q$.}
\label{fig:proof-flow}
\end{figure}
==== END A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//proof-flow.tex ====
==== BEGIN A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//selector-wiring.tex ====
\begin{figure}[tbp]
\centering
\begingroup
\setlength{\unitlength}{1pt}
\begin{picture}(460,202)
\linethickness{0.45pt}
\put(174,129){\framebox(112,55){}}
\put(174,25){\framebox(112,55){}}
\put(72,104){\line(1,0){316}}
\qbezier(72,104)(123,122)(174,140)
\qbezier(286,140)(337,122)(388,104)
\put(72,171){\line(1,0){102}}
\put(286,171){\line(1,0){102}}
\qbezier(72,104)(123,86)(174,68)
\qbezier(286,68)(337,86)(388,104)
\put(72,37){\line(1,0){102}}
\put(286,37){\line(1,0){102}}
\put(72,104){\circle*{3.2}}
\put(388,104){\circle*{3.2}}
\put(72,171){\circle*{3.2}}
\put(388,171){\circle*{3.2}}
\put(72,37){\circle*{3.2}}
\put(388,37){\circle*{3.2}}
\put(174,171){\circle*{3.2}}
\put(174,140){\circle*{3.2}}
\put(286,171){\circle*{3.2}}
\put(286,140){\circle*{3.2}}
\put(174,68){\circle*{3.2}}
\put(174,37){\circle*{3.2}}
\put(286,68){\circle*{3.2}}
\put(286,37){\circle*{3.2}}
\put(230,162){\makebox(0,0){\small color 1: \(H\)}}
\put(230,151){\makebox(0,0){\scriptsize 3 rows \(+\) 3 columns}}
\put(181,171){\makebox(0,0)[l]{\scriptsize \(c_2\)}}
\put(181,140){\makebox(0,0)[l]{\scriptsize \(c_1\)}}
\put(279,171){\makebox(0,0)[r]{\scriptsize \(r_2\)}}
\put(279,140){\makebox(0,0)[r]{\scriptsize \(r_1\)}}
\put(230,57){\makebox(0,0){\small color 2: \(H\)}}
\put(230,46){\makebox(0,0){\scriptsize 3 rows \(+\) 3 columns}}
\put(181,68){\makebox(0,0)[l]{\scriptsize \(c_1\)}}
\put(181,37){\makebox(0,0)[l]{\scriptsize \(c_2\)}}
\put(279,68){\makebox(0,0)[r]{\scriptsize \(r_1\)}}
\put(279,37){\makebox(0,0)[r]{\scriptsize \(r_2\)}}
\put(64,104){\makebox(0,0)[r]{\shortstack[r]{\small shared main\\[-1pt]\small row \(i\)}}}
\put(396,104){\makebox(0,0)[l]{\shortstack[l]{\small shared main\\[-1pt]\small column \(i\)}}}
\put(72,192){\makebox(0,0){\small gate 1 row \(i\)}}
\put(388,192){\makebox(0,0){\small gate 1 column \(i\)}}
\put(72,16){\makebox(0,0){\small gate 2 row \(i\)}}
\put(388,16){\makebox(0,0){\small gate 2 column \(i\)}}
\put(230,113){\makebox(0,0){\small \(X_{ii}\)}}
\put(122,132){\makebox(0,0){\small \(-2\)}}
\put(121,76){\makebox(0,0){\small \(-2\theta_i\)}}
\end{picture}
\endgroup
\caption{Wiring after the two replacements at a fixed diagonal position
\(i\). Each box is a separate copy of \(H\) on three fresh rows and
three fresh columns. Its incoming ports \(c_1,c_2\) are internal columns
and its outgoing ports \(r_1,r_2\) are internal rows; their placement is
schematic. The two copies share the main endpoints and have distinct
gate and internal vertices. Unlabeled boundary edges have weight \(1\).
The ordinary edge \(X_{ii}\) remains; other main and gate edges are omitted.}
\label{fig:selector-wiring}
\end{figure}
==== END A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//selector-wiring.tex ====
==== BEGIN A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//selector.tex ====
\section{Selecting a coefficient by a permanent projection}
\label{sec:selector}
We realize a coefficient of a diagonally shifted permanent as an affine
projection of a larger permanent. The construction selects prescribed
exponents in two auxiliary variables while keeping the larger permanent's
size linear in the order of the shifted permanent.
Fix integers $k\ge1$ and $0\le q\le\lfloor k/2\rfloor$, and put
$r=k-2q$. Let $\theta_1,\ldots,\theta_k$ be indeterminates and put
$D=\operatorname{diag}(\theta_1,\ldots,\theta_k)$. Let
$X=(X_{ij})_{1\le i,j\le k}$ be a matrix of independent variables.
Define the integral coefficient polynomial
$G_D\in\mathbb Z[\theta_1,\ldots,\theta_k][X_{ij}:1\le i,j\le k]$ by
\begin{equation}
G_D(X)=[s^qt^q]\per_k(X+sI+tD).
\label{eq:selector-coefficient}
\end{equation}
The brackets denote coefficient extraction in the auxiliary variables
$s,t$. For a tuple of values $\theta_i$ in any field, we use the same
notation $G_D$ for the specialized polynomial. Write $[k]=\{1,\ldots,k\}$.
Expanding the diagonal entries gives
\begin{equation}
G_D(X)=
\sum_{\substack{S,T\subseteq[k],\ |S|=|T|=q\\S\cap T=\varnothing}}
\left(\prod_{i\in T}\theta_i\right)\per(X_{C,C}),
\qquad C=[k]\setminus(S\cup T).
\label{eq:selector-subsets}
\end{equation}
Indeed, $S$ records the diagonal positions contributing $s$, and $T$
those contributing $t\theta_i$. The two sets are disjoint because each
row and column is used once in a permanent term. After these fixed
diagonal positions are removed, the remaining permutation is an arbitrary
permutation of $C$, and these data recover the original term uniquely.
Thus no additional factorial occurs in
\eqref{eq:selector-subsets}. Every summand is homogeneous of degree $r$
in $X$.
We use the convention that the permanent of the empty matrix is $1$.
We use the matching interpretation of a permanent. A matrix's rows and
columns form the two vertex classes of a bipartite graph, with each entry
as the weight of the edge joining its row to its column. The permanent is the
sum, over perfect matchings, of the products of their edge weights.
Negative weights are allowed. Weighted matching gadgets and cancellation are
classical tools of Valiant's projection framework \cite{Valiant1979Algebra}.
The practice of fixing external choices before summing internal
completions also appears in his permanent reduction
\cite[Lemma~3.1 and its proof]{Valiant1979Permanent}.
Signed gadgets enforcing equality of edge choices also appear in
Dell, Husfeldt, Marx, Taslaman and Wahl\'en
\cite[Section~3 and Figure~2]{DellHusfeldtMarxTaslamanWahlen2014}.
Here we give the weights and completion counts needed for a construction
of linear size.
\begin{proposition}[Coefficient projection]\label{prop:selector}
Let $k\ge1$ and $0\le q\le\lfloor k/2\rfloor$ be integers, put $r=k-2q$,
and let $D=\operatorname{diag}(\theta_1,\ldots,\theta_k)$ with
$\theta_i\in\C$. For every integer $m\ge11k-2q$, there is an $m\times m$
matrix $A(X)$ of complex affine-linear forms such that
\begin{equation}
\per_m(A(X))=a_0G_D(X),
\qquad a_0=(-2)^{2k}\big((k-q)!\big)^4\ne0.
\label{eq:selector-scalar}
\end{equation}
Its entrywise homogenization $B(X,z)$ is a matrix of homogeneous linear
forms whose permanent is the degree-$m$ homogenization of $a_0G_D$:
\begin{equation}
\per_m(B(X,z))=a_0z^{m-r}G_D(X).
\label{eq:selector-homogeneous}
\end{equation}
The construction requires no distinctness or nonvanishing assumption on
the entries of $D$.
\end{proposition}
\begin{proof}
Start with $k$ main rows and columns carrying the edges $X_{ij}$.
At each diagonal position add two labeled special edges, with weights
\[
w_{i,1}=1,\qquad w_{i,2}=\theta_i.
\]
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
\eqref{eq:selector-subsets}.
We will count each color in a separate gate and couple each special
main edge to the corresponding distinguished edge of its gate.
\emph{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
\begin{equation}
(h!)^2=((k-q)!)^2.
\label{eq:selector-gate-count}
\end{equation}
This also covers $q=0$: all original rows and columns then match across
the two groups.
\emph{A gadget equating two edge choices.}
Call the main and gate vertices \emph{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
\begin{equation}
H=\begin{pmatrix}-1&-1&1\\-1&-1&1\\1&1&1\end{pmatrix}.
\label{eq:selector-gadget}
\end{equation}
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
\begin{equation}
\Phi_w(I,O)=(-2w)^{\mathbf1_{\{1\in I\}}}
\per H_{\{1,2,3\}\setminus O,\,\{1,2,3\}\setminus I}.
\label{eq:selector-boundary-weight}
\end{equation}
The complete table of $\Phi_w$ is
\begin{equation}
\begin{array}[t]{c|rrrr}
I\backslash O&\varnothing&\{1\}&\{2\}&\{1,2\}\\\hline
\varnothing&-2&0&0&0\\
\{1\}&0&0&0&0\\
\{2\}&0&0&0&0\\
\{1,2\}&0&0&0&-2w.
\end{array}
\label{eq:selector-boundary-table}
\end{equation}
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.
\emph{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~\ref{fig:selector-wiring} shows these attachments.
\input{figures/selector-wiring}
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
\[
w_{\mathrm{out}}(E)
\prod_{i=1}^k\prod_{c=1}^2
\Phi_{w_{i,c}}(I_{i,c},O_{i,c}).
\]
Each factor $\Phi_{w_{i,c}}$ already includes its boundary edge weights;
$w_{\mathrm{out}}(E)$ contains only the remaining chosen weights.
By \eqref{eq:selector-boundary-table}, 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
\eqref{eq:selector-gate-count}, while the main matching sum is the
corresponding summand of \eqref{eq:selector-subsets}. The $2k$ gadgets
contribute $(-2)^{2k}$. This proves \eqref{eq:selector-scalar} for the
unpadded construction.
Its number of rows, and separately its number of columns, is
\begin{equation}
k+2(2k-q)+3(2k)=11k-2q.
\label{eq:selector-size}
\end{equation}
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
\[
\per_m B(X,z)
=z^m\per_m A(X/z)
=a_0z^mG_D(X/z)
=a_0z^{m-r}G_D(X).
\]
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
\eqref{eq:selector-homogeneous}.
\end{proof}
The affine identity yields a comparison for every fixed affine substitution.
\begin{corollary}\label{cor:selector-border}
Under the hypotheses of Proposition~\ref{prop:selector}, let $d\ge1$ be an
integer and let
$\Lambda:\C^d\to\Mat_k(\C)$ be any fixed affine map. Then
\[
\bdc(G_D\circ\Lambda)\le\bdc(\per_m).
\]
In particular, this holds for every fixed linear restriction of $G_D$.
\end{corollary}
\begin{proof}
Proposition~\ref{prop:selector} gives
$G_D\circ\Lambda=a_0^{-1}\per_m\circ A\circ\Lambda$.
Apply Lemma~\ref{lem:affine-substitution} to the affine map
$A\circ\Lambda$ and the nonzero scalar $a_0^{-1}$.
Both are fixed before any determinant approximation is chosen.
\end{proof}
\begin{remark}\label{rem:selector-characteristic}
The coefficient formula \eqref{eq:selector-coefficient} and the subset
formula \eqref{eq:selector-subsets} are integral and can be specialized
over any field. The projection used for the complex border comparison
requires the nonzero scalar $a_0$, whose factor $(-2)^{2k}$ vanishes in
characteristic two. The characteristic-two argument uses the integral
coefficient expression specialized directly to $\overline{\mathbb F}_2$.
\end{remark}
==== END A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//selector.tex ====
==== BEGIN A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//transfer.tex ====
\section{Characteristic transfer and smooth linear sections}
\label{sec:transfer}
Proposition~\ref{prop:gradient-codimension} bounds an affine gradient
locus in characteristic two. We now transfer that bound to complex
parameters, then choose a linear section on which the coefficient
polynomial defines a smooth projective hypersurface. The final proof
will combine the resulting affine permanent projection with
Theorem~\ref{thm:smooth-border} to obtain the cubic lower bound.
\subsection{Transferring the gradient bound}
The proper family used for specialization is the projective zero scheme
of the partial derivatives. In characteristic two this scheme need not
be the singular scheme of the hypersurface itself. After passing to
characteristic zero, Euler's identity will identify the two.
\begin{lemma}[Specialization of a gradient locus]
\label{lem:characteristic-transfer}
Let
\[
F(\theta,x)\in
\mathbb Z[\theta_1,\ldots,\theta_a][x_1,\ldots,x_v]
\]
be homogeneous of degree \(r\ge2\) in \(x\), where \(v\ge2\), and let
\(1\le\delta\le v\) be an integer. Suppose some
\(\bar\theta\in\overline{\mathbb F}_2^{\,a}\) satisfies
\[
\dim V_{\mathbb A^v_{\overline{\mathbb F}_2}}
\bigl(\partial_{x_1}F_{\bar\theta},\ldots,
\partial_{x_v}F_{\bar\theta}\bigr)
\le v-\delta.
\]
Then there is a nonempty Zariski open subset
\(U\subset\mathbb A^a_{\C}\) such that, for every \(\theta\in U\),
the polynomial \(F_\theta\) is nonzero and
\begin{equation}
\dim\operatorname{Sing}V_{\PP^{v-1}_{\C}}(F_\theta)
\le v-1-\delta.
\label{eq:transfer-singular-bound}
\end{equation}
We use dimension \(-1\) for the empty projective scheme.
\end{lemma}
\begin{proof}
Put \(R=\mathbb Z[\theta_1,\ldots,\theta_a]\) and
\(S=\operatorname{Spec}R\). The homogeneous ideal
\[
I=(\partial_{x_1}F,\ldots,\partial_{x_v}F)\subset R[x_1,\ldots,x_v]
\]
defines a closed subscheme
\begin{equation}
\mathcal Z=\operatorname{Proj}(R[x]/I)\subset\PP^{v-1}_S.
\label{eq:transfer-projective-family}
\end{equation}
Its structural morphism \(\pi:\mathcal Z\to S\) is projective, hence proper.
Differentiation commutes with specialization, and the closed projective
subscheme in \eqref{eq:transfer-projective-family} 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
\[
\dim\mathcal Z_{\bar\theta}\le v-1-\delta.
\]
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 \cite[Tag~0D4I]{StacksProject}.
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
\begin{equation}
\dim V_{\PP^{v-1}_{\C}}(\nabla F_\theta)
\le v-1-\delta.
\label{eq:transfer-complex-gradient}
\end{equation}
Since \(\delta>0\), \(F_\theta\) cannot be the zero polynomial:
otherwise the left side of \eqref{eq:transfer-complex-gradient}
would be \(v-1\). Over \(\C\), Euler's identity gives
\[
rF_\theta=\sum_{i=1}^v x_i\partial_{x_i}F_\theta.
\]
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
\[
\cO_{V(f_i)}
\xrightarrow{\,df_i\,}
\cO_{V(f_i)}^{\,v-1}
\longrightarrow\Omega_{V(f_i)/\C}\longrightarrow0.
\]
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~\eqref{eq:transfer-complex-gradient} proves
\eqref{eq:transfer-singular-bound}.
\end{proof}
All coefficients in \eqref{eq:transfer-projective-family} are integral;
in particular, the construction does not invert \(2\) or \(r\).
Division by \(r\) occurs only in characteristic zero. In applying the
lemma to \(G_D\), we use its coefficient formula
\eqref{eq:selector-coefficient}, before multiplying by the projection
scalar \(a_0\), which vanishes in characteristic two.
\subsection{A smooth section of the required dimension}
Avoiding the singular locus of a hypersurface is one condition on a
linear section. The section must also meet its smooth locus
transversely. The following incidence calculation establishes both
conditions and keeps track of the projective dimension.
\begin{proposition}[Smooth linear section]\label{prop:smooth-slice}
Let \(F\) be a nonzero homogeneous complex polynomial of degree \(r\ge2\)
on a vector space \(V\) of dimension \(v\). Set
\(Y=V_{\PP(V)}(F)\), and suppose
\[
\dim\operatorname{Sing}Y\le v-1-\delta
\]
for an integer \(\delta\ge1\). If \(2\le d<v\) and
\(d-1<\delta\), then a nonempty Zariski open subset of
\(\operatorname{Gr}(d,V)\) consists of subspaces \(H\) for which
\(F|_H\) is nonzero and defines a smooth degree-\(r\) hypersurface
in \(\PP(H)\).
\end{proposition}
\begin{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
\[
(v-1-\delta)+(d-1)(v-d)
=\dim\mathcal G+d-1-\delta
<\dim\mathcal G.
\]
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
\[
p\subset H\subset K_p.
\]
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
\[
(v-2)+(d-1)(v-d-1)=d(v-d)-1.
\]
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.
\end{proof}
\subsection{A smooth form obtained from the permanent}
We now apply the two geometric results to the coefficient polynomial.
The resulting form has linear degree and quadratically many variables,
and is an affine projection of a permanent of linear size.
\begin{samepage}
\begin{proposition}[A smooth form obtained from the permanent]
Let \(k\ge128\) be an integer\label{prop:smooth-projection}, and put
\[
q=\left\lfloor\frac{k-1}{3}\right\rfloor,\qquad
r=k-2q,\qquad d=\left\lfloor\frac{k^2}{100}\right\rfloor.
\]
There is a nonzero homogeneous polynomial
\(G\in\C[x_1,\ldots,x_d]\) of degree \(r\) such that its zero set in
\(\PP^{d-1}_{\C}\) is smooth and, for every integer \(m\ge11k-2q\),
there is an affine map \(\Phi_m:\C^d\to\Mat_m(\C)\) satisfying
\[
G=\per_m\circ\Phi_m.
\]
The parameters also satisfy
\[
r-1\ge\frac{k}{4},\qquad d-1\ge\frac{k^2}{200}.
\]
\end{proposition}
\end{samepage}
\begin{proof}
Set \(T=\binom{q+2}{2}\). Since \(k\ge128\),
\[
q\ge\frac{k-4}{3}\ge\frac{k}{4},\qquad
T\ge\frac{q^2}{2}\ge\frac{k^2}{32}.
\]
Consequently
\begin{equation}
\Delta:=T-k
\ge\frac{k^2}{32}-k
\ge\frac{k^2}{64}>0.
\label{eq:transfer-codimension-size}
\end{equation}
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~\ref{prop:gradient-codimension} gives
\[
\dim V_{\mathbb A^{k^2}_{\overline{\mathbb F}_2}}(\nabla G_{\bar D})
\le k^2+k-T=k^2-\Delta.
\]
The coefficient formula \eqref{eq:selector-coefficient}, with the
\(\theta_i\) treated as indeterminates, is integral in these parameters
and homogeneous of degree \(r\) in the \(k^2\) matrix variables.
Moreover,
\[
r-1=k-2q-1
\ge\frac{k-1}{3}\ge\frac{k}{4},
\]
so \(r\ge2\). Lemma~\ref{lem:characteristic-transfer} 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
\[
\dim\operatorname{Sing}V_{\PP^{k^2-1}_{\C}}(G_D)
\le k^2-1-\Delta.
\]
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
\eqref{eq:transfer-codimension-size} gives
\[
d-1<\frac{k^2}{100}<\frac{k^2}{64}\le\Delta.
\]
Proposition~\ref{prop:smooth-slice} 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
\[
d-1\ge\frac{k^2}{100}-2\ge\frac{k^2}{200},
\]
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~\ref{prop:selector} gives a matrix
\(A_m(X)\) of affine-linear forms with
\[
\per_m(A_m(X))=a_0G_D(X),\qquad a_0\ne0.
\]
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.
\end{proof}
==== END A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//transfer.tex ====
==== BEGIN A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//references.bib ====
@article{LandsbergManivelRessayre2010,
author = {Landsberg, Joseph M. and Manivel, Laurent and Ressayre, Nicolas},
title = {Hypersurfaces with degenerate duals and the {Geometric Complexity Theory Program}},
journal = {Commentarii Mathematici Helvetici},
volume = {88},
number = {2},
pages = {469--484},
year = {2013},
doi = {10.4171/CMH/292},
url = {https://ems.press/journals/cmh/articles/11963}
}
@article{LandsbergRessayre2017,
author = {Landsberg, Joseph M. and Ressayre, Nicolas},
title = {Permanent v. determinant: An exponential lower bound assuming symmetry and a potential path towards {Valiant}'s conjecture},
journal = {Differential Geometry and its Applications},
volume = {55},
pages = {146--166},
year = {2017},
doi = {10.1016/j.difgeo.2017.03.017},
url = {https://arxiv.org/abs/1508.05788v2}
}
@misc{SheshadriBorder2026,
author = {Sheshadri, Karthik},
title = {A near-quadratic lower bound on the border determinantal complexity of {$\sum_i x_i^n$} via conormal specialization},
howpublished = {\href{https://arxiv.org/abs/2606.13628v1}{arXiv:2606.13628v1}},
year = {2026},
note = {11 June 2026},
doi = {10.48550/arXiv.2606.13628},
url = {https://arxiv.org/abs/2606.13628v1}
}
@misc{SheshadriNoGo2026,
author = {Sheshadri, Karthik},
title = {The Exact Reach of Conormal Invariants in Determinantal Complexity: a Quadratic No-Go Theorem},
howpublished = {\href{https://arxiv.org/abs/2606.15970v1}{arXiv:2606.15970v1}},
year = {2026},
note = {14 June 2026},
doi = {10.48550/arXiv.2606.15970},
url = {https://arxiv.org/abs/2606.15970v1}
}
@article{FGvS1999,
author = {Fantechi, Barbara and G{\"o}ttsche, Lothar and van Straten, Duco},
title = {Euler number of the compactified {Jacobian} and multiplicity of rational curves},
journal = {Journal of Algebraic Geometry},
volume = {8},
number = {1},
pages = {115--133},
year = {1999},
url = {https://arxiv.org/abs/alg-geom/9708012}
}
@article{CHT2023,
author = {Christ, Karl and He, Xiang and Tyomkin, Ilya},
title = {On the {Severi} problem in arbitrary characteristic},
journal = {Publications Math\'ematiques de l'IH\'ES},
volume = {137},
pages = {1--45},
year = {2023},
doi = {10.1007/s10240-022-00135-x},
url = {https://pmihes.centre-mersenne.org/articles/10.1007/s10240-022-00135-x/}
}
@misc{StacksProject,
author = {{The Stacks Project Authors}},
title = {The {Stacks} Project},
howpublished = {\url{https://stacks.math.columbia.edu}},
year = {2026},
note = {Tags 032L, 00PD, 0D4I, and 054K; accessed 24 September 2026},
url = {https://stacks.math.columbia.edu}
}
@article{MignonRessayre2004,
author = {Mignon, Thierry and Ressayre, Nicolas},
title = {A quadratic bound for the determinant and permanent problem},
journal = {International Mathematics Research Notices},
volume = {2004},
number = {79},
pages = {4241--4253},
year = {2004},
doi = {10.1155/S1073792804142566},
url = {https://academic.oup.com/imrn/article-abstract/2004/79/4241/793411}
}
@inproceedings{Valiant1979Algebra,
author = {Valiant, L. G.},
title = {Completeness Classes in Algebra},
booktitle = {Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing},
series = {STOC '79},
publisher = {Association for Computing Machinery},
year = {1979},
pages = {249--261},
doi = {10.1145/800135.804419},
url = {https://doi.org/10.1145/800135.804419}
}
@article{Valiant1979Permanent,
author = {Valiant, L. G.},
title = {The Complexity of Computing the Permanent},
journal = {Theoretical Computer Science},
volume = {8},
number = {2},
year = {1979},
pages = {189--201},
doi = {10.1016/0304-3975(79)90044-6},
url = {https://doi.org/10.1016/0304-3975(79)90044-6}
}
@article{Tyomkin2013,
author = {Tyomkin, Ilya},
title = {On {Zariski}'s theorem in positive characteristic},
journal = {Journal of the European Mathematical Society},
volume = {15},
number = {5},
pages = {1783--1803},
year = {2013},
doi = {10.4171/JEMS/403},
url = {https://ems.press/journals/jems/articles/11402}
}
@article{Kleiman1974,
author = {Kleiman, Steven L.},
title = {The transversality of a general translate},
journal = {Compositio Mathematica},
volume = {28},
number = {3},
pages = {287--297},
year = {1974},
url = {https://www.numdam.org/item/CM_1974__28_3_287_0/}
}
@article{AlperBogartVelasco2017,
author = {Alper, Jarod and Bogart, Tristram and Velasco, Mauricio},
title = {A Lower Bound for the Determinantal Complexity of a Hypersurface},
journal = {Foundations of Computational Mathematics},
volume = {17}, number = {3}, pages = {829--836}, year = {2017},
doi = {10.1007/s10208-015-9300-x},
url = {https://arxiv.org/abs/1505.02205v1}
}
@article{Piene1978,
author = {Piene, Ragni},
title = {Polar classes of singular varieties},
journal = {Annales scientifiques de l'{\'E}cole Normale Sup{\'e}rieure},
series = {4}, volume = {11}, number = {2}, pages = {247--276}, year = {1978},
doi = {10.24033/asens.1346},
url = {https://www.numdam.org/articles/10.24033/asens.1346/}
}
@article{DellHusfeldtMarxTaslamanWahlen2014,
author = {Dell, Holger and Husfeldt, Thore and Marx, D{\'a}niel and Taslaman, Nina and Wahl{\'e}n, Martin},
title = {Exponential Time Complexity of the Permanent and the {Tutte} Polynomial},
journal = {ACM Transactions on Algorithms},
volume = {10}, number = {4}, pages = {21:1--21:32}, year = {2014},
doi = {10.1145/2635812},
note = {Preprint: arXiv:1206.1775v1; numbered locators in the text refer to this version},
url = {https://arxiv.org/abs/1206.1775v1}
}
@article{vonZurGathen1987,
author = {von zur Gathen, Joachim},
title = {Permanent and determinant},
journal = {Linear Algebra and its Applications},
volume = {96},
pages = {87--100},
year = {1987},
doi = {10.1016/0024-3795(87)90337-5},
url = {https://www.sciencedirect.com/science/article/pii/0024379587903375}
}
@article{Meshulam1989,
author = {Meshulam, Roy},
title = {On two extremal matrix problems},
journal = {Linear Algebra and its Applications},
volume = {114/115},
pages = {261--271},
year = {1989},
doi = {10.1016/0024-3795(89)90465-5},
url = {https://meshulam.net.technion.ac.il/files/2021/06/4.pdf}
}
@article{Cai1990,
author = {Cai, Jin-yi},
title = {A note on the determinant and permanent problem},
journal = {Information and Computation},
volume = {84},
number = {1},
pages = {119--127},
year = {1990},
doi = {10.1016/0890-5401(90)90036-H},
url = {https://www.sciencedirect.com/science/article/pii/089054019090036H}
}
@article{CaiChenLi2010,
author = {Cai, Jin-Yi and Chen, Xi and Li, Dong},
title = {Quadratic lower bound for permanent vs. determinant in any characteristic},
journal = {Computational Complexity},
volume = {19},
number = {1},
pages = {37--56},
year = {2010},
doi = {10.1007/s00037-009-0284-2},
url = {https://pages.cs.wisc.edu/~jyc/papers/per-det.pdf}
}
@misc{Grenet2012,
author = {Grenet, Bruno},
title = {An Upper Bound for the Permanent versus Determinant Problem},
howpublished = {Author preprint},
year = {2012},
note = {25 May 2012},
url = {https://membres-ljk.imag.fr/Bruno.Grenet/publis/Gre11.pdf}
}
@article{MulmuleySohoni2001,
author = {Mulmuley, Ketan D. and Sohoni, Milind},
title = {Geometric Complexity Theory {I}: An Approach to the {P} vs. {NP} and Related Problems},
journal = {SIAM Journal on Computing},
volume = {31},
number = {2},
pages = {496--526},
year = {2001},
doi = {10.1137/S009753970038715X},
url = {https://epubs.siam.org/doi/10.1137/S009753970038715X}
}
@article{MulmuleySohoni2008,
author = {Mulmuley, Ketan D. and Sohoni, Milind},
title = {Geometric Complexity Theory {II}: Towards explicit obstructions for embeddings among class varieties},
journal = {SIAM Journal on Computing},
volume = {38},
number = {3},
pages = {1175--1206},
year = {2008},
doi = {10.1137/080718115},
url = {https://arxiv.org/abs/cs/0612134v1}
}
@misc{KumarVolk2026,
author = {Kumar, Mrinal and Volk, Ben Lee},
title = {A Quadratic Lower Bound on Determinantal Complexity},
howpublished = {\href{https://arxiv.org/abs/2609.34462v1}{arXiv:2609.34462v1}},
year = {2026},
note = {28 September 2026},
doi = {10.48550/arXiv.2609.34462},
url = {https://arxiv.org/abs/2609.34462v1}
}
@article{Galazka2017,
author = {Ga{\l}{\k a}zka, Maciej},
title = {Vector bundles give equations of cactus varieties},
journal = {Linear Algebra and its Applications},
volume = {521},
pages = {254--262},
year = {2017},
doi = {10.1016/j.laa.2016.12.005},
note = {Preprint: arXiv:1605.08005v1; numbered locators in the text refer to this version},
url = {https://arxiv.org/abs/1605.08005v1}
}
@misc{Baranovsky1998,
author = {Baranovsky, Vladimir},
title = {On Punctual {Quot} Schemes for Algebraic Surfaces},
howpublished = {\href{https://arxiv.org/abs/alg-geom/9703038v3}{arXiv:alg-geom/9703038v3}},
year = {1998},
note = {Version of 18 July 1998; first submitted 28 March 1997},
doi = {10.48550/arXiv.alg-geom/9703038},
url = {https://arxiv.org/abs/alg-geom/9703038v3}
}
@article{AdamsHarnadHurtubise1993,
author = {Adams, M. R. and Harnad, J. and Hurtubise, J.},
title = {Darboux Coordinates and {Liouville-Arnold} Integration in Loop Algebras},
journal = {Communications in Mathematical Physics},
volume = {155},
number = {2},
pages = {385--413},
year = {1993},
doi = {10.1007/BF02097398},
note = {Preprint: arXiv:hep-th/9210089v1; numbered locators in the text refer to this version},
url = {https://arxiv.org/abs/hep-th/9210089v1}
}
@inproceedings{Wampler1996,
author = {Wampler, Charles W.},
title = {Isotropic coordinates, circularity, and {Bezout} numbers: Planar kinematics from a new perspective},
booktitle = {ASME 1996 Design Engineering Technical Conferences},
year = {1996},
note = {Paper 96-DETC/MECH-1210},
doi = {10.1115/96-DETC/MECH-1210},
url = {https://academicweb.nd.edu/~cwample1/Preprints/DETC1996_MECH1210_IsotropicCircularity.pdf}
}
@article{Premet2003,
author = {Premet, Alexander},
title = {Nilpotent commuting varieties of reductive {Lie} algebras},
journal = {Inventiones Mathematicae},
volume = {154},
number = {3},
pages = {653--683},
year = {2003},
url = {https://eprints.maths.manchester.ac.uk/494/2/comm.pdf},
note = {\href{https://eprints.maths.manchester.ac.uk/494/2/comm.pdf}{Author manuscript}, Corollary~4.1}
}
==== END A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent//references.bib ====