A near-quadratic lower bound on the border determinantal complexity of $\sum_i x_i^n$ via conormal specialization
2026-06-11 • Computational Complexity
Computational Complexity
AI summaryⓘ
The authors study how complicated a polynomial is by measuring how big a matrix of simple formulas it takes to approximate the polynomial as a determinant. They focus on the sum of powers polynomial and show that this complexity grows at least roughly with the square of the number of variables. Their method uses geometric tools involving special varieties related to derivatives of determinants and special degenerations to a simpler polynomial shape called the Fermat cone. This is the first time such lower bounds that grow faster than linearly with variables have been shown for an explicit polynomial family.
border determinantal complexitydeterminantal representationFermat hypersurfaceconormal varietydual varietyGauss mapmultidegreeBézout's theoremdegenerationaffine-linear form
Authors
Karthik Sheshadri
Abstract
The border determinantal complexity $\dcb(f)$ of a polynomial $f$ is the least $m$ such that $f$ is a limit of determinants of $m\times m$ matrices of affine-linear forms. We prove that for every $n\ge3$, over $\CC$, \[ \dcb\Big(\sum_{i=1}^n x_i^n\Big)\ \ge\ \frac{(n-1)^2}{4e}, \qquad \sdcb\Big(\sum_{i=1}^n x_i^n\Big)\ \ge\ \frac{(n-1)^2}{2e} \] in the ordinary and symmetric models respectively; both match the known $O(n^2)$ upper bounds up to the constant. To our knowledge these are the first border determinantal lower bounds for an explicit family that are superlinear in the number of variables: the known quadratic border bound for the permanent reads the \emph{dimension} of the dual variety and is linear in its number of variables, whereas we transfer the dual \emph{degree}. The proof has two ingredients. The first is an unconditional bound on the slot-$(n-2)$ conormal multidegree of the multiplicity-one Gauss-graph cycle of an arbitrary affine-linear determinant -- singular, reducible, and non-reduced fibers allowed -- by a multihomogeneous Bézout count of a lifted kernel incidence. The second is a specialization argument: along any degeneration $\det A_c\to\sum_ix_i^n$, the flat limit of these Gauss-graph cycles contains the conormal variety of the Fermat cone with positive coefficient. A cone-shift identity converts that conormal multidegree into the classical dual degree $n(n-1)^{n-2}$ of the smooth Fermat hypersurface, and an $(n-1)$-st root yields the quadratic bound. The exact lower bounds of the author's companion manuscripts follow as corollaries.