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?

Authors: Alan Edelman and Eric Kostlan
Journal: Bull. Amer. Math. Soc. 32 (1995), 1-37
MSC: Primary 60G99; Secondary 30B20, 42A05
DOI: https://doi.org/10.1090/S0273-0979-1995-00571-9
MathSciNet review: 1290398
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

[1] 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
[2] A. T. Bharucha-Reid and M. Sambandham, Random polynomials, Probability and Mathematical Statistics, Academic Press, Inc., Orlando, FL, 1986. MR 856019
[3] A. Bloch and G. Pólya, On the roots of certain algebraic equations, Proc. London Math. Soc. (3) 33 (1932), 102-114.
[4] 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, https://doi.org/10.1103/PhysRevLett.68.2726
[5] 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
[6] Ralph Philip Boas Jr., Entire functions, Academic Press Inc., New York, 1954. MR 0068627
[7] Paul A. Clement, A class of triple-diagonal matrices for test purposes, SIAM Rev. 1 (1959), 50–52. MR 99750, https://doi.org/10.1137/1001006
[8] 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
[9] 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, https://doi.org/10.1002/rsa.3240010105
[10] Alan Edelman, Eigenvalues and condition numbers of random matrices, SIAM J. Matrix Anal. Appl. 9 (1988), no. 4, 543–560. MR 964668, https://doi.org/10.1137/0609045
[11] -, Eigenvalues and condition numbers of random matrices, Ph.D. thesis, Department of Mathematics, MIT, 1989.
[12] -, Math 273e: Eigenvalues of random matrices, Personal Lecture Notes, University of California, Berkeley, Spring 1993, unpublished.
[13] 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, https://doi.org/10.1090/S0894-0347-1994-1231689-0
[14] A. Edelman, Eigenvalue roulette and random test matrices, Numerical Linear Algebra, Digital Signal Processing and Parallel Algorithms (G.H. Golub and P. Van Dooren, eds.), NATO Adv. Sci. Inst. Ser. F: Comput. Systems Sci., vol. 70, Springer-Verlag, New York, 1991, pp. 485-488.
[15] -, The circular law and the probability that a random matrix has k real eigenvalues, preprint.
[16] P. Erdös and P. Turán, On the distribution of roots of polynomials, Ann. of Math. (2) 51 (1950), 105-119.
[17] Kambiz Farahmand, On the average number of real roots of a random algebraic equation, Ann. Probab. 14 (1986), no. 2, 702–709. MR 832032
[18] J. Faraut and A. Koranyi, Analysis on symmetric cones, draft of book.
[19] 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
[20] 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, https://doi.org/10.1090/S0002-9939-1995-1249878-0
[21] I. Gradshteyn and I. Ryzhik, Table of integrals, series, and products, Academic Press, New York, 1980.
[22] Phillip Griffiths and Joseph Harris, Principles of algebraic geometry, Wiley-Interscience [John Wiley & Sons], New York, 1978. Pure and Applied Mathematics. MR 507725
[23] 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 and Los Angeles, 1956, pp. 89–111. MR 0084888
[24] 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, https://doi.org/10.1090/conm/138/1199126
[25] N. Higham, The test matrix toolbox for Matlab, Numerical Analysis Report No. 237, University of Manchester, England, December 1993.
[26] M. Kac, On the average number of real roots of a random algebraic equation, Bull. Amer. Math. Soc. 49 (1943), 314–320. MR 7812, https://doi.org/10.1090/S0002-9904-1943-07912-8
[27] 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, https://doi.org/10.1112/plms/s2-50.5.390
[28] Jean-Pierre Kahane, Some random series of functions, D. C. Heath and Co. Raytheon Education Co., Lexington, Mass., 1968. MR 0254888
[29] S. Kobayashi and K. Nomizu, Foundations of differential geometry, Volume 2, Wiley, New York, 1969.
[30] E. Kostlan, Random polynomials and the statistical fundamental theorem of algebra, unpublished, 1987.
[31] 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
[32] -, On the expected number of real roots of a system of random polynomial equations, in preparation.
[33] -, On the expected volume of a real algebraic variety, in preparation.
[34] J. Littlewood and A. Offord, On the number of real roots of a random algebraic equation, J. London Math. Soc. 13 (1938), 288-295.
[35] 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
[36] 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
[37] Madan Lal Mehta, Random matrices, 2nd ed., Academic Press, Inc., Boston, MA, 1991. MR 1083764
[38] Robb J. Muirhead, Aspects of multivariate statistical theory, John Wiley & Sons, Inc., New York, 1982. Wiley Series in Probability and Mathematical Statistics. MR 652932
[39] 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, https://doi.org/10.1090/conm/050/841087
[40] 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
[41] S. O. Rice, The Distribution of the Maxima of a Random Curve, Amer. J. Math. 61 (1939), no. 2, 409–416. MR 1507385, https://doi.org/10.2307/2371510
[42] S. O. Rice, Mathematical analysis of random noise, Bell System Tech. J. 24 (1945), 46–156. MR 11918, https://doi.org/10.1002/j.1538-7305.1945.tb00453.x
[43] Luis A. Santaló, Integral geometry and geometric probability, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1976. With a foreword by Mark Kac; Encyclopedia of Mathematics and its Applications, Vol. 1. MR 0433364
[44] Rolf Schneider, Convex bodies: the Brunn-Minkowski theory, Encyclopedia of Mathematics and its Applications, vol. 44, Cambridge University Press, Cambridge, 1993. MR 1216521
[45] 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
[46] 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, https://doi.org/10.1007/978-1-4612-2752-6_19
[47] Herbert Solomon, Geometric probability, Society for Industrial and Applied Mathematics, Philadelphia, Pa., 1978. Ten lectures given at the University of Nevada, Las Vegas, Nev., June 9–13, 1975; Conference Board of the Mathematical Sciences—Regional Conference Series in Applied Mathematics, No. 28. MR 0488215
[48] M. Spivak, A comprehensive introduction to differential geometry, 2nd ed., Publish or Perish, Berkeley, CA, 1979.
[49] 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, https://doi.org/10.1016/0024-3795(91)90179-Z
[50] 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
[51] 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, https://doi.org/10.2307/2324361