A LOWER BOUND ON DETERMINANTAL COMPLEXITY

The determinantal complexity of a polynomial P is an element of F[X-1, ..., x(n)] over a field F is the dimension of the smallest matrix M whose entries are affine functions in F[x(1), ..., x(n)] such that P = Det(M). We prove that the determinantal complexity of the polynomial Sigma(n)(i=1): 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 et al. (2017) for the same polynomial.