Press "Enter" to skip to content

Roots of random polynomials

Mark Kac

The Girko circular law theorem states that if \( {X} \) is a \( {n\times n} \) random matrix with independent and identically distributed entries (i.i.d) of variance \( {1/n} \) then the empirical measure

\[ \frac{1}{n}\sum_{i=1}^n\delta_{\lambda_i(X)} \]

made with the eigenvalues of \( {X} \), converges, as the dimension \( {n} \) tends to infinity, to the uniform law on the unit disk \( {\{z\in\mathbb{C}:|z|\leq1\}} \). This is to me the most beautiful spectral theorem in random matrix theory (well, I also like the Voiculescu asymptotic freeness theorem).

The random matrix \( {X} \) has i.i.d. entries and its eigenvalues are the roots of its characteristic polynomial. The coefficients of this random polynomial are neither independent nor identically distributed. Beyond random matrices, let us consider a random polynomial

\[ P(z)=a_0+a_1z+\cdots+a_nz^n \]

where \( {a_0,\ldots,a_n} \) are independent random variables. By analogy with random matrices, one may ask about the behavior as \( {n\rightarrow\infty} \) of the roots

\[ \lambda_1(P),\ldots,\lambda_n(P) \]

of \( {P} \) in \( {\mathbb{C}} \) and in particular the behavior of their empirical measure

\[ \frac{1}{n}\sum_{i=1}^n\delta_{\lambda_i(P)}. \]

The literature on this subject is quite rich and can be traced back to the works of Littlewood and Offord, Rice, and Kac. We refer to Shub and Smale, Azaïs and Wschebor, and Edelman and Kostlan (see also this paper) for (partial) reviews. As for random matrices, the case where the coefficients are real is more subtle due to the presence of real roots. Regarding the complex case, the zeros of Gaussian analytic functions is the subject of a recent monograph in connection with determinantal processes. Various cases are considered in the literature, including the following three families:

  • Kac polynomials, for which \( {(a_i)_{0\leq i\leq n}} \) are i.i.d.
  • Binomial polynomials, for which \( {a_i=\sqrt{\binom{n}{i}}b_i} \) for all \( {i} \) and \( {{(b_i)}_{0\leq i\leq n}} \) are i.i.d.
  • Weyl polynomials, for which \( {a_i=\frac{1}{\sqrt{i!}}b_i} \) for all \( {i} \) and \( {{(b_i)}_{0\leq i\leq n}} \) are i.i.d.

Geometrically, the complex number \( {z} \) is a root of \( {P} \) if and only if the vectors

\[ (1,z,\ldots,z^n) \quad\mbox{and}\quad (\overline{a_0},\overline{a_1},\ldots,\overline{a_n}) \]

are orthogonal in \( {\mathbb{C}^{n+1}} \), and this connects the problem to Littlewood-Offord type problems and small balls probabilities estimates, see this 1943 paper for instance.

Regarding Kac polynomials, Kac (see also the errata) has shown in the real Gaussian case that the asymptotic number of real roots is about \( {\frac{2}{\pi}\log(n)} \) as \( {n\rightarrow\infty} \). Kac obtained the same result when the coefficients are uniformly distributed. Hammersley derived an explicit formula for the \( {k} \)-point correlation of the roots of Kac polynomials. Shparo and Shur have shown that the empirical measure of the roots of Kac polynomials with light tailed coefficients tends as \( {n\rightarrow\infty} \) to the uniform law one the unit circle \( {\{z\in\mathbb{C}:|z|=1\}} \) (the arc law). If the coefficients are heavy tailed then the limiting law concentrates on the union of two centered circles, see Götze and Zaporozhets and references therein.

Regarding Weyl polynomials, various simulations and conjectures have been made, see e.g. Galligo and Emiris, Galligo, and Tsigaridas. For instance, if \( {(b_i)_{0\leq i\leq n}} \) are i.i.d. standard Gaussian, it was conjectured that the asymptotic behavior of the roots of the Weyl polynomials is analogous to the Ginibre Ensemble. Namely, the empirical distribution of the roots tends as \( {n\rightarrow\infty} \) to the uniform law on the centered disc of the complex plane (circular law), and moreover, in the real Gaussian case, there are about \( {\frac{2}{\pi}\sqrt{n}} \) real roots as \( {n\rightarrow\infty} \) and their empirical distribution tends as \( {n\rightarrow\infty} \) to a uniform law on an interval, as for the real Ginibre Ensemble. The complex Gaussian case was considered by Leboeuf and by Peres and Virág, while the real roots of the real Gaussian case were studied by Schehr and Majumdar. Beyond the Gaussian case, it is tempting to try the logarithmic potential approach with the companion matrix of \( {P} \). Recall that the companion matrix of the monic polynomial

\[ Q(z):=c_0+c_1z+\cdots+c_{n-1}z^{n-1}+z^n \]

is the \( {n\times n} \) matrix

\[ \begin{pmatrix} 0 & 1 & 0 & \cdots & 0\\ 0 & 0 & 1 & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & 1\\ -c_0 & -c_1 & -c_2 & \cdots & -c_{n-1}\\ \end{pmatrix}. \]

Its characteristic polynomial is \( {Q} \). Numerical simulations reveal strange phenomena depending on the law of the coefficients but we ignore it they are purely numerical. Note for instance that if the coefficients of \( {P} \) are all real positive then the roots cannot be real positive. The heavy tailed case is also of interest (rings?).

5 Comments

  1. Djalil Chafaï 2012-01-14

    According to Bloom, one may deduce the circular law for the roots of universal Weyl polynomials by using his potential theoretic approach. On the other hand, according to Zeitouni, one may deduce this result from a large deviation principle with speed \(n^2\) similar to the one for Gaussian Kac polynomials obtained in his paper with Zelditch (we have here \(n\) degree of freedom, one for each coefficient, instead of \(n^2\) for random matrices with i.i.d. entries). For additional references, see Around the circular law page 71.

  2. van vu 2013-08-24

    Hi Djalil,

    Terry and I just proved universality for real zeroes: http://arxiv.org/pdf/1307.4357.pdf. Thus, for cases such as Weyl polynomial or binomial polynomial, the number of real zeroes are
    (approximately) the same as in the gaussian.

  3. Djalil Chafaï 2013-08-25

    Dear Van, yes, thanks, congratulations for this impressive progress!

Leave a Reply

Your email address will not be published. Required fields are marked *