On the number of minima of a random polynomial

DOI10.1016/J.JCO.2007.09.003zbMATH Open1143.65039arXivmath/0702360OpenAlexW3121892946MaRDI QIDQ2483199FDOQ2483199

Authors: Jean-Pierre Dedieu, Gregorio Malajovich 

Publication date: 28 April 2008

Published in: Journal of Complexity (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/math/0702360

Recommendations

• The expected number of local maxima of a random algebraic polynomial
• What is the Least Expected Number of Real Roots of a Random Polynomial?
• scientific article; zbMATH DE number 1859213
• Random polynomials having few or no real zeros
• Betti numbers of random real hypersurfaces and determinants of random symmetric matrices

zbMATH Keywords

critical pointsrandom polynomialsnumber of maximanumber of minima

Mathematics Subject Classification ID

Large deviations (60F10) Random matrices (algebraic aspects) (15B52) Computational methods for stochastic equations (aspects of stochastic analysis) (60H35) Random operators and equations (aspects of stochastic analysis) (60H25) Numerical computation of solutions to single equations (65H05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the average number of real roots of a random algebraic equation
• Title not available (Why is that?)
• Distribution of roots of random polynomials
• Large deviations and stochastic calculus for large random matrices
• On the roots of a random system of equations. The theorem of Shub and Smale and some extensions
• On the Kostlan-Shub-Smale model for random polynomial systems. Variance of the number of roots
• On the Average Number of Real Roots of a Random Algebraic Equation (II)
• Large Deviations of Extreme Eigenvalues of Random Matrices
• Title not available (Why is that?)
• High probability analysis of the condition number of sparse polynomial systems
• Random systems of polynomial equations. The expected number of roots under smooth analysis
• Erratum to “How many zeros of a random polynomial are real?”

Cited In (14)

• Betti numbers of random real hypersurfaces and determinants of random symmetric matrices
• Statistics of stationary points of random finite polynomial potentials
• On the probability distribution of data at points in real complete intersection varieties
• Expected topology of random real algebraic submanifolds
• Statistics on Hilbert's 16th problem
• Random systems of polynomial equations. The expected number of roots under smooth analysis
• Expected number of critical points of random holomorphic sections over complex projective space
• Quantitative singularity theory for random polynomials
• On the topological degree of the gradient of homogeneous Gaussian random polynomial
• On the complex points of random polynomials
• On the measure of polynomials attaining maxima on a vertex
• Extrema of a real polynomial
• Low-degree approximation of random polynomials
• On the expected number of zeros of nonlinear equations

This page was built for publication: On the number of minima of a random polynomial

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2483199)