A Lower Bound on Determinantal Complexity

Abstract

The determinantal complexity of a polynomial $P\in \mathbb{F}[x_1,\dots ,x_n]$ over a field $\mathbb{F}$ is the dimension of the smallest matrix $M$ whose entries are affine functions in $\mathbb{F}[x_1,\dots ,x_n]$ such that $P=Det(M)$. We prove that the determinantal complexity of the polynomial ${\sum }_{i=1}^n{x}_i^n$ is at least $1.5n-3$. For every $n$-variate polynomial of degree $d$, the determinantal complexity is trivially at least $d$, and it is a long standing open problem to prove a lower bound which is super linear in $\max \{n,d\}$. Our result is the first lower bound for any explicit polynomial which is bigger by a constant factor than $\max \{n,d\}$, and improves upon the prior best bound of $n+1$, proved by Alper, Bogart and Velasco [ABV17] for the same polynomial.

v2: corrected a few typos and added references