How many zeros of a random polynomial are real?

Edelman, Alan; Kostlan, Eric

doi:10.1090/S0273-0979-1995-00571-9

How many zeros of a random polynomial are real?
HTML articles powered by AMS MathViewer

by Alan Edelman and Eric Kostlan PDF

Bull. Amer. Math. Soc. 32 (1995), 1-37 Request permission

Abstract:

We provide an elementary geometric derivation of the Kac integral formula for the expected number of real zeros of a random polynomial with independent standard normally distributed coefficients. We show that the expected number of real zeros is simply the length of the moment curve $(1, t, \ldots ,t^{n})$ projected onto the surface of the unit sphere, divided by $\pi$. The probability density of the real zeros is proportional to how fast this curve is traced out. We then relax Kac’s assumptions by considering a variety of random sums, series, and distributions, and we also illustrate such ideas as integral geometry and the Fubini-Study metric.

References

Orlando Alvarez, Enzo Marinari, and Paul Windey (eds.), Random surfaces and quantum gravity, NATO Advanced Science Institutes Series B: Physics, vol. 262, Plenum Press, New York, 1991. MR 1214377, DOI 10.1007/978-1-4615-3772-4
A. T. Bharucha-Reid and M. Sambandham, Random polynomials, Probability and Mathematical Statistics, Academic Press, Inc., Orlando, FL, 1986. MR 856019

On the roots of certain algebraic equations

33

E. Bogomolny, O. Bohigas, and P. Lebœuf, Distribution of roots of random polynomials, Phys. Rev. Lett. 68 (1992), no. 18, 2726–2729. MR 1160289, DOI 10.1103/PhysRevLett.68.2726
T. Bonnesen and W. Fenchel, Theory of convex bodies, BCS Associates, Moscow, ID, 1987. Translated from the German and edited by L. Boron, C. Christenson and B. Smith. MR 920366
Ralph Philip Boas Jr., Entire functions, Academic Press, Inc., New York, 1954. MR 0068627
Paul A. Clement, A class of triple-diagonal matrices for test purposes, SIAM Rev. 1 (1959), 50–52. MR 99750, DOI 10.1137/1001006
Persi Diaconis, Group representations in probability and statistics, Institute of Mathematical Statistics Lecture Notes—Monograph Series, vol. 11, Institute of Mathematical Statistics, Hayward, CA, 1988. MR 964069, DOI 10.1007/BFb0086177
Persi Diaconis, R. L. Graham, and J. A. Morrison, Asymptotic analysis of a random walk on a hypercube with many dimensions, Random Structures Algorithms 1 (1990), no. 1, 51–72. MR 1068491, DOI 10.1002/rsa.3240010105
Alan Edelman, Eigenvalues and condition numbers of random matrices, SIAM J. Matrix Anal. Appl. 9 (1988), no. 4, 543–560. MR 964668, DOI 10.1137/0609045

Eigenvalues and condition numbers of random matrices

Math

Eigenvalues of random matrices

Alan Edelman, Eric Kostlan, and Michael Shub, How many eigenvalues of a random matrix are real?, J. Amer. Math. Soc. 7 (1994), no. 1, 247–267. MR 1231689, DOI 10.1090/S0894-0347-1994-1231689-0

Eigenvalue roulette and random test matrices

The circular law and the probability that a random matrix has k real eigenvalues

On the distribution of roots of polynomials

51

Kambiz Farahmand, On the average number of real roots of a random algebraic equation, Ann. Probab. 14 (1986), no. 2, 702–709. MR 832032

Analysis on symmetric cones

V. L. Girko, Theory of random determinants, Mathematics and its Applications (Soviet Series), vol. 45, Kluwer Academic Publishers Group, Dordrecht, 1990. Translated from the Russian. MR 1080966, DOI 10.1007/978-94-009-1858-0
I. P. Goulden and D. M. Jackson, Combinatorial constructions for integrals over normally distributed random matrices, Proc. Amer. Math. Soc. 123 (1995), no. 4, 995–1003. MR 1249878, DOI 10.1090/S0002-9939-1995-1249878-0

Table of integrals, series, and products

Phillip Griffiths and Joseph Harris, Principles of algebraic geometry, Pure and Applied Mathematics, Wiley-Interscience [John Wiley & Sons], New York, 1978. MR 507725
J. M. Hammersley, The zeros of a random polynomial, Proceedings of the Third Berkeley Symposium on Mathematical Statistics and Probability, 1954–1955, vol. II, University of California Press, Berkeley-Los Angeles, Calif., 1956, pp. 89–111. MR 0084888
Philip J. Hanlon, Richard P. Stanley, and John R. Stembridge, Some combinatorial aspects of the spectra of normally distributed random matrices, Hypergeometric functions on domains of positivity, Jack polynomials, and applications (Tampa, FL, 1991) Contemp. Math., vol. 138, Amer. Math. Soc., Providence, RI, 1992, pp. 151–174. MR 1199126, DOI 10.1090/conm/138/1199126

The test matrix toolbox for Matlab

M. Kac, On the average number of real roots of a random algebraic equation, Bull. Amer. Math. Soc. 49 (1943), 314–320. MR 7812, DOI 10.1090/S0002-9904-1943-07912-8
M. Kac, On the average number of real roots of a random algebraic equation. II, Proc. London Math. Soc. (2) 50 (1949), 390–408. MR 30713, DOI 10.1112/plms/s2-50.5.390
Jean-Pierre Kahane, Some random series of functions, D. C. Heath and Company Raytheon Education Company, Lexington, Mass., 1968. MR 0254888

Foundations of differential geometry, Volume

Random polynomials and the statistical fundamental theorem of algebra

E. Kostlan, On the distribution of roots of random polynomials, From Topology to Computation: Proceedings of the Smalefest (Berkeley, CA, 1990) Springer, New York, 1993, pp. 419–431. MR 1246137

On the expected number of real roots of a system of random polynomial equations

On the expected volume of a real algebraic variety

On the number of real roots of a random algebraic equation

13

Froim Marcus, On the metrics of G. Fubini, Proceedings of the mathematical congress in celebration of the one hundredth birthday of Guido Fubini and Francesco Severi (Turin, 1979), 1981, pp. 235–242 (1982). MR 727500
N. B. Maslova, The distribution of the number of real roots of random polynomials, Teor. Verojatnost. i Primenen. 19 (1974), 488–500 (Russian, with English summary). MR 0368136
Madan Lal Mehta, Random matrices, 2nd ed., Academic Press, Inc., Boston, MA, 1991. MR 1083764
Robb J. Muirhead, Aspects of multivariate statistical theory, Wiley Series in Probability and Mathematical Statistics, John Wiley & Sons, Inc., New York, 1982. MR 652932, DOI 10.1002/9780470316559
C. M. Newman, Lyapunov exponents for some products of random matrices: exact expressions and asymptotic distributions, Random matrices and their applications (Brunswick, Maine, 1984) Contemp. Math., vol. 50, Amer. Math. Soc., Providence, RI, 1986, pp. 121–141. MR 841087, DOI 10.1090/conm/050/841087
A. M. Odlyzko and B. Poonen, Zeros of polynomials with $0,1$ coefficients, Enseign. Math. (2) 39 (1993), no. 3-4, 317–348. MR 1252071
S. O. Rice, The Distribution of the Maxima of a Random Curve, Amer. J. Math. 61 (1939), no. 2, 409–416. MR 1507385, DOI 10.2307/2371510
S. O. Rice, Mathematical analysis of random noise, Bell System Tech. J. 24 (1945), 46–156. MR 11918, DOI 10.1002/j.1538-7305.1945.tb00453.x
Luis A. Santaló, Integral geometry and geometric probability, Encyclopedia of Mathematics and its Applications, Vol. 1, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1976. With a foreword by Mark Kac. MR 0433364
Rolf Schneider, Convex bodies: the Brunn-Minkowski theory, Encyclopedia of Mathematics and its Applications, vol. 44, Cambridge University Press, Cambridge, 1993. MR 1216521, DOI 10.1017/CBO9780511526282
A. N. Shiryayev, Probability, Graduate Texts in Mathematics, vol. 95, Springer-Verlag, New York, 1984. Translated from the Russian by R. P. Boas. MR 737192, DOI 10.1007/978-1-4899-0018-0
M. Shub and S. Smale, Complexity of Bezout’s theorem. II. Volumes and probabilities, Computational algebraic geometry (Nice, 1992) Progr. Math., vol. 109, Birkhäuser Boston, Boston, MA, 1993, pp. 267–285. MR 1230872, DOI 10.1007/978-1-4612-2752-6_{1}9
Herbert Solomon, Geometric probability, Conference Board of the Mathematical Sciences Regional Conference Series in Applied Mathematics, No. 28, Society for Industrial and Applied Mathematics, Philadelphia, Pa., 1978. Ten lectures given at the University of Nevada, Las Vegas, Nev., June 9–13, 1975. MR 0488215, DOI 10.1137/1.9781611970418

A comprehensive introduction to differential geometry

Olga Taussky and John Todd, Another look at a matrix of Mark Kac, Proceedings of the First Conference of the International Linear Algebra Society (Provo, UT, 1989), 1991, pp. 341–360. MR 1102076, DOI 10.1016/0024-3795(91)90179-Z
D. V. Voiculescu, K. J. Dykema, and A. Nica, Free random variables, CRM Monograph Series, vol. 1, American Mathematical Society, Providence, RI, 1992. A noncommutative probability approach to free products with applications to random matrices, operator algebras and harmonic analysis on free groups. MR 1217253, DOI 10.1090/crmm/001
Elias Wegert and Lloyd N. Trefethen, From the Buffon needle problem to the Kreiss matrix theorem, Amer. Math. Monthly 101 (1994), no. 2, 132–139. MR 1259826, DOI 10.2307/2324361