On the number of minima of a random polynomial

Abstract

We give an upper bound in O(d ^((n+1)/2)) for the number of critical points of a normal random polynomial with degree d and at most n variables. Using the large deviation principle for the spectral value of large random matrices we obtain the bound O(exp(-beta n^2 + (n/2) log (d-1))) (beta is a positive constant independent on n and d) for the number of minima of such a polynomial. This proves that most normal random polynomials of fixed degree have only saddle points. Finally, we give a closed form expression for the number of maxima (resp. minima) of a random univariate polynomial, in terms of hypergeometric functions.

22 pages. We learned since the first version that the probability that a matrix in GOE(n) is positive definite is known. This follows from the theory of large deviations (reference in the paper). Therefore, we can now state a precise upper bound (Theorem 2) for the number of minima of a random polynomial, instead of a bound depending on that probability