Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)



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
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.

References [Enhancements On Off] (What's this?)

  • [1] O. Alvarez, Enzo Marinari, and Paul Windey, eds., Random surfaces and quantum gravity, NATO Advanced Research Workshop on Random Surfaces and Quantum Gravity, NATO Adv. Sci. Inst. Ser. B: Phys., vol. 262, Plenum Press, New York, 1991. MR 1214377 (96e:81004)
  • [2] A.T. Bharucha-Reid and M. Sambandham, Random polynomials, Academic Press, New York, 1986. MR 856019 (87m:60118)
  • [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. Bohias, and P. Leboeuf, Distribution of roots of random polynomials, Phys. Rev. Lett. 68 (1992), 2726-2729. MR 1160289 (92m:81054)
  • [5] T. Bonnesen and W. Fenchel, Theory of convex bodies, BCS Associates, Moscow, Idaho, 1987. MR 920366 (88j:52001)
  • [6] R.P. Boas, Entire functions, Academic Press, New York, 1954. MR 0068627 (16:914f)
  • [7] P.A. Clement, A class of triple-diagonal matrices for test purposes, SIAM Rev. 1 (1959), 50-52. MR 0099750 (20:6188)
  • [8] P. Diaconis, Group representations in probability and statistics, Institute of Mathematical Statistics, Hayward, CA, 1988. MR 964069 (90a:60001)
  • [9] P. 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), 51-72. MR 1068491 (91g:60078)
  • [10] A. Edelman, Eigenvalues and condition numbers of random matrices, SIAM J. Matrix Anal. Appl. 9 (1988), 543-560. MR 964668 (89j:15039)
  • [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] A. Edelman, E. Kostlan, and M. Shub, How many eigenvalues of a random matrix are real?, J. Amer. Math. Soc. 7 (1994), 247-267. MR 1231689 (94f:60053)
  • [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] K. Farahmand, On the average number of real roots of a random algebraic equation, Ann. Probab. 14 (1986), 702-709. MR 832032 (87k:60140)
  • [18] J. Faraut and A. Koranyi, Analysis on symmetric cones, draft of book.
  • [19] V.L. Girko, Theory of random determinants, Kluwer, Boston, 1990. MR 1080966 (91k:60001)
  • [20] I.P. Goulden and D.M. Jackson, Combinatorial constructions for integrals over normally distributed random matrices, Proc. Amer. Math. Soc. (to appear). MR 1249878 (95j:05169)
  • [21] I. Gradshteyn and I. Ryzhik, Table of integrals, series, and products, Academic Press, New York, 1980.
  • [22] P. Griffiths and J. Harris, Principles of algebraic geometry, Wiley, New York, 1978. MR 507725 (80b:14001)
  • [23] J. Hammersley, The zeros of a random polynomial, Proc. Berkeley Symp. Math. Statist. Probab., vol. 2 (J. Neyman, ed.), Univ. of California Press, Berkeley, CA, 1956, pp. 89-111. MR 0084888 (18:941c)
  • [24] P.J. Hanlon, R.P. Stanley, and J.R. Stembridge, Some combinatorial aspects of the spectra of normally distributed random matrices, Contemp. Math. 138 (1992), 151-174. MR 1199126 (93j:05164)
  • [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 and 938. MR 0007812 (4:196d)
  • [27] -, On the average number of real roots of a random algebraic equation (II), Proc. London Math. Soc. (3) 50 (1949), 390-408. MR 0030713 (11:40e)
  • [28] J.-P. Kahane, Some random series of functions, Heath, Lexington, 1968. MR 0254888 (40:8095)
  • [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] -, On the distribution of roots of random polynomials, From Topology to Computation: Proceedings of the Smalefest (M.W. Hirsch, J.E. Marsden, and M. Shub, eds.), Springer-Verlag, 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] F. 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, Atti Accad. Sci. Torino Cl. Sci. Fis. Mat. Natur. 115 (1982), 235-242. MR 727500 (85g:53001)
  • [36] N. Maslova, On the distribution of the number of real roots of random polynomials, Teor. Veroyatnost. i Primenen. 19 (1974), 488-500. (Russian) MR 0368136 (51:4378)
  • [37] M.L. Mehta, Random matrices, Academic Press, New York, 1991. MR 1083764 (92f:82002)
  • [38] R.J. Muirhead, Aspects of multivariate statistical theory, Wiley, New York, 1982. MR 652932 (84c:62073)
  • [39] C. M. Newman, Lyapunov exponents for some products of random matrices: Exact expressions and asymptotic distributions, Random Matrices and Their Applications (J.E. Cohen, H. Kesten, and C.M. Newman, eds.), Contemp. Math., vol. 50, Amer. Math. Soc. Providence, RI, 1986, pp. 121-141. MR 841087 (88a:60020)
  • [40] A.M. Odlyzko and B. Poonen, Zeros of polynomials with 0, 1 coefficients, Enseign. Math. 39 (1993), 317-348. MR 1252071 (95b:11026)
  • [41] S.O. Rice, The distribution of the maxima of a random curve, Amer. J. Math. 61 (1939), 409-416. MR 1507385
  • [42] -, Mathematical analysis of random noise, Bell Syst. Tech. J. 24 (1945), 45-156. MR 0011918 (6:233i)
  • [43] L.A. Santaló, Integral geometry and geometric probability, Volume 1, Encyclopedia Math. Appl., vol. 1, Addison-Wesley, Reading, 1976. MR 0433364 (55:6340)
  • [44] R. Schneider, Convex bodies: The Brunn-Minkowski Theory, Encyclopedia Math. Appl., vol. 44, Cambridge Univ. Press, Cambridge, 1993. MR 1216521 (94d:52007)
  • [45] A.N. Shiryayev, Probability, Graduate Texts in Math., vol. 95, Springer-Verlag, New York, 1984. MR 737192 (85a:60007)
  • [46] M. Shub and S. Smale, Complexity of Bezout's Theorem II: Volumes and Probabilities, Computational Algebraic Geometry (F. Eyssette and A. Galligo, eds.), Progr. Math., vol. 109, Birkhauser, Boston, 1993, pp. 267-285. MR 1230872 (94m:68086)
  • [47] H. Solomon, Geometric probability, CBMS-NSF Regional Conf. Ser. in Appl. Math., vol. 28, SIAM, Philadelphia, PA, 1978. MR 0488215 (58:7777)
  • [48] M. Spivak, A comprehensive introduction to differential geometry, 2nd ed., Publish or Perish, Berkeley, CA, 1979.
  • [49] O. Taussky and J. Todd, Another look at a matrix of Mark Kac, Linear Algebra Appl. 150 (1991), 341-360. MR 1102076 (92k:15030)
  • [50] D.V. Voiculescu, K.J. Dykema, and A. Nica, Free random variables: A noncommutative probability approach to free products with applications to random matrices, operator algebras, and harmonic analysis on free groups, CRM Monograph Ser., vol. 1, Amer. Math. Soc., Providence, RI, 1992. MR 1217253 (94c:46133)
  • [51] E. Wegert and L.N. Trefethen, From the Buffon needle problem to the Kreiss matrix theorem, Amer. Math. Monthly 101 (1994), 132-139. MR 1259826 (95b:30036)

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC: 60G99, 30B20, 42A05

Retrieve articles in all journals with MSC: 60G99, 30B20, 42A05

Additional Information

Keywords: Random polynomials, Buffon needle problem, integral geometry, random power series, random matrices
Article copyright: © Copyright 1995 American Mathematical Society

American Mathematical Society