Conormal Lower Bounds for Determinantal Complexity: Fermat Slices, Tight Bounds, and a Ceiling

Abstract

The determinantal complexity of a polynomial $f$ is the smallest size of a matrix of affine linear forms whose determinant is $f$; the border version only asks for determinants converging to $f$. The polar method bounds these quantities from below by comparing an invariant of the hypersurface $V(f)$, such as the degree of its dual variety, with the number of solutions of a polynomial system built from a determinantal representation of $f$. We determine how far the method reaches. Lower bounds: if $f$ has a linear restriction to a form of degree $d$ in $N$ variables with smooth projective zero set, then the border determinantal complexity of $f$ is at least $(N-1)(d-1)/(4e)$. Setting the off-diagonal host entries to zero turns every homomorphism polynomial ${\mathrm{hom}}_{F,q}$ with a connected pattern $F$ into a Fermat polynomial, which gives the bound $(q-1)(|E(F)|-1)/(4e)$. For the VBP-complete path family $W_q$ this is tight: the border determinantal complexity of $W_q$ is $\Theta (q^3)$. The same argument gives cubic bounds for natural VP- and VNP-complete families, and a bound in terms of the codimension of the singular locus of $V(f)$. A ceiling: the method, together with every refinement in a precisely defined class, cannot prove a lower bound larger than $O(dN)$ for any polynomial of degree $d$ in $N$ variables. The proof computes the solution count exactly, as the degree of the dual of a generic determinantal hypersurface, and shows that every characteristic-cycle invariant of a hypersurface of degree $d$ is at most $8(d-1{)}^{N-1}+8N$. For the $n\times n$ permanent the ceiling is $O(n^3)$; for the power sum $x_1^N+\cdots +x_N^N$ it is $(1+o(1))N^2/(4e)$, matching the known lower bound.

arXiv commentSubstantially expanded. Adds the lower-bound side of the method, a smooth-slice criterion, a tight Theta(q^3) border bound for a VBP-complete path family, cubic bounds for VP- and VNP-complete homomorphism families, and a codimension principle