% ============================================================
% permanent_border_determinantal_v2.tex
%
% A self-contained rewrite of:
%   "A cubic lower bound for border determinantal complexity of the permanent"
%
% The original was 13 separate .tex fragments plus a .bib. This file
% merges them, introduces the background a motivated high-school reader
% needs, and keeps every proof idea of the original. Compile with pdflatex.
% ============================================================

\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{booktabs}
\usepackage{hyperref}

\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{\Gr}{Gr}
\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\im}{im}
\DeclareMathOperator{\coker}{coker}
\DeclareMathOperator{\diag}{diag}
\DeclareMathOperator{\Sing}{Sing}
\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}
The permanent and the determinant are the two most famous polynomials
attached to a square matrix. The determinant can be evaluated by Gaussian
elimination; the permanent is hard. Valiant asked whether the $m\times m$
permanent can be expressed as a determinant of polynomial size. We prove a
cubic lower bound on that size, even after allowing limits: the border
determinantal complexity of the $m\times m$ permanent satisfies
$\bdc(\per_m)\ge c\,m^3$ for an absolute constant $c>0$, and one may take
$c=1/(5529600\,e)$ and $m_0=1408$. The same cubic estimate holds for exact
determinants and, after a standard reduction, for the numbers of vertices
and edges of affine-linear algebraic branching programs.
\end{abstract}

\tableofcontents

% ============================================================
\section{Introduction}\label{sec:intro}
% ============================================================

\subsection{The permanent, the determinant, and the question}

To a square matrix $X=(x_{ij})$ of size $m\times m$ one attaches two
polynomials:
\[
\per_m(X)=\sum_{\sigma\in S_m}\prod_{i=1}^m x_{i,\sigma(i)},
\qquad
\det_m(X)=\sum_{\sigma\in S_m}\operatorname{sgn}(\sigma)\prod_{i=1}^m x_{i,\sigma(i)}.
\]
Both are multilinear in the rows and both are sums of $m!$ monomials, so
at first sight they look alike. They behave very differently. The
determinant is computable in polynomial time by Gaussian elimination. The
permanent is \#P-hard: it counts the perfect matchings of a bipartite
graph with edge weights $x_{ij}$, and no polynomial-time algorithm is
known or expected.

Valiant \cite{Valiant1979Algebra} turned this contrast into an algebraic
version of the $P$ versus $NP$ problem. A \emph{determinant of size $n$}
is any polynomial of the shape
\[
\det_n\!\bigl(A_0+\textstyle\sum_{j=1}^{N} x_j A_j\bigr),
\qquad A_0,\ldots,A_N\in\Mat_n(\C),
\]
that is, a determinant whose entries are arbitrary affine-linear
functions of the input variables. The \emph{determinantal complexity}
$\dc(f)$ of a polynomial $f$ is the least $n$ for which $f$ has such a
representation. Valiant conjectured that $\dc(\per_m)$ grows faster than
any polynomial in $m$. The best known construction is Grenet's
$2^m-1$ \cite{Grenet2012}, and every polynomial lower bound is progress
towards the conjecture.

This paper proves the first \emph{cubic} lower bound, in the slightly
weaker but more natural \emph{border} model that allows taking limits.

\subsection{Border determinantal complexity}

Fix a degree bound $n$. The set of affine $n\times n$ determinants is the
image of a polynomial map from the coefficient space
$\C^{n^2(n^2+1)}$ to polynomials of degree at most $n$; its
\emph{coefficientwise closure} is the set of polynomials whose
coefficients are limits of coefficients of such determinants, with the
size $n$ fixed along the sequence.

\begin{definition}\label{def:bdc}
The \emph{border determinantal complexity} $\bdc(f)$ is the least $n$ for
which $f$ lies in the coefficientwise closure of the affine $n\times n$
determinants. Equivalently, $f$ lies in the Zariski closure; the two
closures agree because the image is constructible, see
Section~\ref{sec:models}.
\end{definition}

\begin{theorem}[Main 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/(5529600\,e)$ and $m_0=1408$.
\end{theorem}

Since an exact representation is a constant sequence of approximations,
$\bdc\le\dc$, so Theorem~\ref{thm:main} also bounds $\dc(\per_m)$ from
below. Section~\ref{sec:consequences} records this and the corresponding
bounds for affine-linear algebraic branching programs.

The constants above are not optimized. They come from very loose
inequalities of the form $2<e$, and any improvement in the geometry
would improve them.

\subsection{The engine: smooth homogeneous forms}

The first half of the proof is a geometric statement, due to \cite{Piene1978} in its
count and to \cite{SheshadriBorder2026,KumarVolk2026} in the kernel
lifts we need. A homogeneous polynomial
$G\in\C[x_1,\ldots,x_d]$ of degree $r$ is called \emph{smooth} if its
projective zero set $V(G)\subset\PP^{d-1}$ is a smooth hypersurface, that
is, if the gradient $(\partial G/\partial x_1,\ldots,\partial G/\partial x_d)$
does not vanish at any nonzero point of $G=0$.

\begin{theorem}[Lower bound for smooth forms]\label{thm:smooth-border}
Let $G\in\C[x_1,\ldots,x_d]$ be a nonzero homogeneous polynomial of
degree $r\ge2$ with $d\ge2$. If the zero set of $G$ in $\PP^{d-1}$ is
smooth, then
\[
\bdc(G)\ \ge\ \frac{(r-1)(d-1)}{4e}.
\]
\end{theorem}

The proof, in Section~\ref{sec:polar}, is a count of polar intersections.
Let $w_1,\ldots,w_{d-2}\in\C^d$ be constants. The \emph{first polar} of
$G$ in direction $w_i$ is $\partial_{w_i}G=\sum_j (w_i)_j\,\partial G/\partial x_j$,
a form of degree $r-1$. For a general choice of the $w_i$, the system
\[
G=0,\qquad \partial_{w_1}G=0,\ \ldots,\ \partial_{w_{d-2}}G=0
\]
has exactly $r(r-1)^{d-2}$ distinct simple solutions in $\PP^{d-1}$, by
B\'ezout's theorem applied to hypersurfaces of degrees $r,r-1,\ldots,r-1$.

Now suppose $G$ is a coefficientwise limit of $n\times n$ affine
determinants. Each selected solution persists for one sufficiently close
determinant $Q=\det A$. At such a point $A$ has rank $n-1$ and hence
unique right and left kernel lines $\PP^{n-1}_p$ and $\PP^{n-1}_b$. The
condition that $Q$ and its polars vanish becomes $h+2n-1$ bilinear
equations of bidegrees $(1,1,0)$, $(1,0,1)$, $(0,1,1)$ in the variables
$[\xi_0:\xi]$, $p$, $b$, where $\xi$ are the affine coordinates and $h=d-2$.
A multihomogeneous B\'ezout count, valid even with excess components,
bounds the number of simple zeros by
\[
r(r-1)^{d-2}\ \le\ 2^{d-2}\binom{2n-1}{d-1}.
\]
Taking the $(d-1)$-th root gives
$n\ge (r-1)(d-1)/(4e)$, which is Theorem~\ref{thm:smooth-border}.

The count has one striking feature: it allows the approximating matrices to
have arbitrarily large entries, because coefficientwise closeness is the
only analytic input. This is what makes Theorem~\ref{thm:smooth-border}
apply to the border model with no uniformity hypothesis on the sequence.

\subsection{Producing a smooth form from the permanent}

Theorem~\ref{thm:smooth-border} is useful only if one has a smooth form
whose domain is large and whose degree is high, and which is known to be
an affine restriction of $\per_m$ for small $m$. We build one directly
from the permanent.

Fix $k\ge1$ and $0\le q\le\lfloor k/2\rfloor$, put $r=k-2q$, and let
$\theta_1,\ldots,\theta_k$ be scalars. With
$D=\diag(\theta_1,\ldots,\theta_k)$ and $X=(X_{ij})$ a $k\times k$ matrix
of variables, set
\[
G_D(X)\ =\ [s^q t^q]\,\per_k(X+sI+tD).
\]
Here $[s^q t^q]$ extracts the coefficient of $s^q t^q$ in the auxiliary
variables $s,t$. Expanding the diagonal entries gives the concrete formula
\[
G_D(X)\ =\ \sum_{\substack{S,T\subseteq[k]:\ |S|=|T|=q\\ S\cap T=\varnothing}}
\Bigl(\prod_{i\in T}\theta_i\Bigr)\per(X_{[k]\setminus(S\cup T),\ [k]\setminus(S\cup T)}),
\]
so $G_D$ is homogeneous of degree $r$ in the $k^2$ entries of $X$.

The construction splits into four steps.

\begin{enumerate}
\item \textbf{Valiant-type projection} (Section~\ref{sec:selector}). Over
  $\C$, $G_D$ is an affine restriction of $\per_m$ with
  $m=11k-2q$. Two count gates force exactly $q$ selected diagonal positions
  of each ``color'', and $2k$ small $3\times3$ gadgets couple the two colors.
  This uses only additions and multiplications, so the construction is
  uniform in $k$ and $q$.
\item \textbf{Characteristic 2} (Sections~\ref{sec:adjugate}--\ref{sec:dimension}).
  Over $K=\overline{\mathbb F}_2$ the permanent equals the determinant.
  Each $X$ then defines the plane curve
  $C_X=V(\det(sI+tD+uX))\subset\PP^2_K$. The adjugate of $sI+tD+uX$
  defines a finite subscheme $Z\subset C_X$ of length
  $\ge T=\binom{q+2}{2}$ whenever $\nabla G_D(X)=0$. The length of $Z$ is
  also bounded by the normalization defect $\delta(C_X)$ of the curve,
  so $\delta(C_X)\ge T$. A Severi-dimension count for plane curves with
  large defect and a Hilbert-scheme count for the matrix fiber then give
  \[
  \operatorname{codim}\{X:\nabla G_D(X)=0\}\ \ge\ T-k\ \ge\ k^2/64.
  \]
\item \textbf{Transfer to $\C$} (Section~\ref{sec:transfer}). The
  gradient locus is the fiber of a proper family; upper semicontinuity
  transfers the codimension bound to a nonempty complex open set. A
  general linear subspace $H\subset\Mat_k(\C)$ of dimension
  $d=\lfloor k^2/100\rfloor$ avoids the singular locus of $G_D$, so
  $G=G_D|_H$ has a smooth zero set in $\PP^{d-1}$.
\item \textbf{Assembly}. By Proposition~\ref{prop:selector}, $G$ is an
  affine restriction of $\per_m$ for every $m\ge11k-2q$, so
  $\bdc(\per_m)\ge\bdc(G)$. Theorem~\ref{thm:smooth-border} now gives
  \[
  \bdc(\per_m)\ge\bdc(G)\ge\frac{(r-1)(d-1)}{4e}\ge\frac{k^3}{3200\,e},
  \]
  and $k\ge m/12$ for $m\ge132$ yields $c=1/(5529600\,e)$ as in
  Theorem~\ref{thm:main}.
\end{enumerate}

\subsection{Consequences}

The same machinery gives three corollaries, all proved in
Section~\ref{sec:consequences}.

\begin{itemize}
\item \textbf{Exact determinants.} $\dc(\per_m)\ge m^3/(5529600\,e)$ for
  $m\ge1408$, since $\bdc\le\dc$.
\item \textbf{Algebraic branching programs.} An affine-linear ABP with $N$
  vertices and output $f$ satisfies $\bdc(f)\le N+1$, and an ABP with $E$
  edges satisfies $\bdc(f)\le E+2$ after trimming. Hence computing
  $\per_m$ requires $\Omega(m^3)$ vertices and $\Omega(m^3)$ edges, even
  after allowing limits with a fixed budget.
\item \textbf{Smooth initial forms.} If $g\in\C[x_1,\ldots,x_d]$ has a
  smooth lowest nonzero homogeneous term $G_r$ of degree $r\ge2$ at some
  point $a$, then $\bdc(g)\ge (r-1)(d-1)/(4e)$.
\end{itemize}

\subsection{Related work}\label{sec:earlier}

Early lower bounds for the permanent were linear in $m$. For variable-or-constant
projections, von zur Gathen reported a Babai--Seress bound with leading
term $\sqrt2\,m$ and a loss $6\sqrt m$ \cite{vonZurGathen1987}; for
arbitrary affine representations over $\C$, Meshulam and Cai obtain
$\sqrt2\,m-O(1)$ \cite{Meshulam1989,Cai1990}. The comparison in both
arguments is between the dimension of the affine matrix image and the
minimum rank an exact representation must have.

Mignon and Ressayre raised the bound to $m^2/2$ in characteristic zero by
comparing Hessian ranks \cite{MignonRessayre2004}: affine pullback cannot
increase Hessian rank, the Hessian of an order-$n$ determinant has rank at
most $2n$ at a noninvertible matrix, and the permanent has a full-rank
Hessian at some zero. Cai, Chen and Li extended $m^2/2$ to positive
characteristic different from two \cite{CaiChenLi2010}.

Landsberg, Manivel and Ressayre proved $\bdc(\per_m)\ge m^2/2$ in the
unrestricted border model, using degeneracy of the dual variety
\cite{LandsbergManivelRessayre2010}. Theorem~\ref{thm:main} raises the
exponent from $2$ to $3$ in the same model. Whether $\bdc(\per_m)$, or
$\dc(\per_m)$, is superpolynomial remains open.

Landsberg and Ressayre also proved exponential optima for exact
representations with symmetry hypotheses \cite{LandsbergRessayre2017}.
Alper, Bogart and Velasco gave $\dc(f)\ge\operatorname{codim}\Sing(f)+1$
for forms of degree $>2$ with $\operatorname{codim}\Sing(f)>4$
\cite{AlperBogartVelasco2017}; for the permanent this is only linear.
The present paper uses the opposite strategy: a coefficient of a diagonal
shift of $\per_k$ produces a smooth form in quadratically many variables.

The polar count used here is classical \cite{Piene1978}. The kernel-lift
and Schur-complement reduction resemble those in
\cite{SheshadriBorder2026}, and a related bilinear count appears in
\cite{KumarVolk2026}.

\subsection{Roadmap}

Section~\ref{sec:models} fixes the border model and the equivalence with
orbit closures. Section~\ref{sec:selector} builds the affine permanent
projection. Sections~\ref{sec:adjugate}--\ref{sec:dimension} carry out
the characteristic-2 computation and the dimension count.
Section~\ref{sec:transfer} transfers the count to $\C$ and takes a
smooth linear section. Section~\ref{sec:polar} proves
Theorem~\ref{thm:smooth-border}. Section~\ref{sec:consequences}
assembles everything and records the corollaries.