30
$\begingroup$

I generated random quadratic and cubic polynomials with coefficients in $\mathbb{C}$ uniformly distributed in the unit disk $|z| \le 1$. The distribution of the roots of 10000 of these polynomials are shown below (left: quadratic; right: cubic).
Poly23
What explains these distributions? In particular: (1) Why the relative paucity of roots near the origin. (2) Why is the density concentrated in $\frac{1}{2} \le |z| \le 1$? (3) Why is the cubic distribution sharper than the quadratic? (The roots of polynomials of higher degree distribute (visually) roughly like the cubic distribution.)


In a comment to an earlier posting of this question on MSE, Niels Diepeveen suggested I look at the $\log$ of the roots instead, for they "show a density that is independent of the imaginary part and symmetric w.r.t. the real part":
     Poly23Log
To (naive) me, this raises more questions than it answers: (4) Why the uniformity in the imaginary direction? (5) Why does the $\log$ seemingly obliterate the distinction between the quadratic and cubic distributions?

$\endgroup$
4
  • 4
    $\begingroup$ Have you seen the paper ams.org/journals/proc/2002-130-09/S0002-9939-02-06340-2/… which deals with this problem but for polynomials of very large degree? The authors show that for large degrees the zeros tend to accumulate on the unit circle in an equidistributed fashion. $\endgroup$ Aug 19, 2013 at 12:41
  • 6
    $\begingroup$ Clearly, the distribution without log is rotationally invariant, and the logarithm maps the argument on the imaginary axis. Therefore, you have uniformity on the imaginary axis after taking log. $\endgroup$ Aug 19, 2013 at 12:50
  • 1
    $\begingroup$ just wondering, if that observation could be utilized to visually judge the quality of generators for equidistributed random numbers. $\endgroup$ Aug 20, 2013 at 6:14
  • $\begingroup$ Related: math.ucr.edu/home/baez/week285.html $\endgroup$
    – Alice Ryhl
    May 17, 2014 at 8:32

4 Answers 4

15
$\begingroup$

Letting $\mu_n$ be the distribution of a randomly chosen root of a random polynomial $f=c_0+c_1X+\cdots+c_nX^n$ in $\mathbb{C}[X]$ for IID random variables $c_i\in\mathbb{C}$, each chosen with some probability distribution $\lambda$ on $\mathbb{C}\setminus\{0\}$ we can show the following just about immediately.

  1. $\mu_n$ is invariant under the map $z\mapsto z^{-1}$.In particular, the distribution of the logarithm of a random root is invariant under reflection about the origin.
  2. If $\lambda$ is rotationally invariant then so is $\mu_n$. In particular, the distribution of the logarithm of a random root is invariant under translation by an imaginary number.
  3. If $\int\lvert z\rvert d\lambda(z)$ is finite, then as $n$ tends to infinity $\mu_n$ becomes concentrated on the unit circle. That is, for each $\epsilon\gt0$, $\mu_n(\{z\colon 1-\epsilon\lt\lvert z\rvert\lt1+\epsilon\})\to1$ as $n\to\infty$.

In the case asked about here, $\lambda$ is uniform on the unit ball so that all of the conditions hold, and $\mu_n$ tends weakly to the uniform measure on the unit circle as $n\to\infty$.

For (1), note that the zeros of $g=c_n+c_{n-1}X+\cdots+c_0X^n$ are precisely $\alpha^{-1}$ as $\alpha$ runs through the zeros of $f$, but that $g$ has the same distribution as $f$.

For (2) note that for real $\theta$, the zeros of $g=c_0+c_1e^{-i\theta}X+\cdots+c_ne^{-in\theta}X^n$ are precisely $e^{i\theta}\alpha$ as $\alpha$ runs through the zeros of $f$, but $g$ has the same distribution as $f$.

For (3), note that if $c_0,c_1,c_2,\ldots$ is an infinite IID sequence, each with distribution $\lambda$, and if $0\lt r\lt 1$ then, $$ \sum_{k=0}^\infty\lvert c_k\rvert r^k $$ has finite mean $\int\lvert z\rvert d\lambda(z)/(1-r)$, so the sum is finite with probability 1. Hence the sequence of polynomials $f_n=c_0+c_1X+\cdots+c_nX^n$ converge uniformly on the ball of radius $r$ (with probability 1). So, the number of zeros of $f_n$ in the ball of radius $r$ is almost surely bounded as $n\to\infty$. This implies that $\mu_n(\{z\colon\lvert z\rvert\le r\})\to0$ as $n\to\infty$. Applying (1) to this also gives $\mu_n(\{z\colon\lvert z\rvert\ge1/r\})\to0$ as $n\to\infty$.

$\endgroup$
14
$\begingroup$

The 1950's Mark Kac studied polynomials with independent random normal coefficients in $\mathbb{R}$:

$$ f(z) = \sum_{n = 0}^N a_n z^n $$

He shows we can expect $N_f = \frac{2}{\pi} \log n $ roots in $\mathbb{R}$ arguing

\[ \#\{ a < x < b : f(x) = 0 \} = \frac{1}{2\epsilon} \int_a^b \mathbf{1}\big[-\epsilon < f(x) < \epsilon\big]\,\big|f'(x)\big| \; dx = \mathbb{E}\big[|f'(x)|\; \big| \; f(x) = 0 \big] \]

You can imagine doing this for any distribution on coefficients up to rescaling.

Let $a_i$ be uniform in the unit disk $\mathbb{D} = \{ |z| < 1\}$, $i = 1, \dots, n$.
For arbitrary vectors $\vec{x}, \vec{y}$, you can ask for the conditional expectation:

\[ \mathbb{E} \big[ \vec{a}\cdot \vec{x} \big| \vec{a}\cdot \vec{y} = 0\big] \]


Kac notes he couldn't find a similar paper by Littlewood and Offord from 1938 (didn't have Google!)

Recently this kind of problem has been discussed by Tao (various estimates) or Zelditch (holomorphic sections on Riemann surfaces.


Edelman and Kostlan count solutions for Gaussian random polynomials in a geometric way via the Crofton formula.

We are counting the number of intersections of a curve on the sphere with a random hyperplane.

Finding the zero of a polynomial is like showing two vectors are orthogonal: $$ \sum a_n z^n = (a_0, a_1, a_2, \dots, a_n) \cdot (1, z, z^2, \dots, z^n) = 0 $$ where $z \in \mathbb{R}$ and $\vec{a} \in \mathbb{R}P^{n+1}=S^n$.

The Gaussian joint distribution of coefficients amounts to the uniform distribution $\vec{a}$ on the sphere.

The Crofton formula says your expected number of real zeros in an interval is equal to the arc length of your curve projected onto the sphere.

$$N_f = \frac{1}{\pi} \int_I \left( \frac{\partial^2}{\partial x \partial y} \log [v(x)\cdot v(y) ]\right)^{\frac{1}{2}}_{x=y=t}dt $$

The Edelman-Kostlan paper has a version of this function for $\mathbb{C}$.

For iid Gaussian coefficients, Peres-Virag work this out to be $\rho(z) = \frac{1}{(1 - |z|^2)^2}$ in the limit that the degree gets large. At least you can see a concentration around the unit circle $|z| = 1$.


For polynomials Edelman-Kostlan propose rescaling - this is related to the $SU(2)$ lie group:

\[ f(z) = \sum_{n=0}^L \binom{L}{k}^{1/2} z^n \]

Then $\mathbb{E}[f(z)\overline{f(w)}] = (1 + z\overline{w})^N$ is covariance for values between two points. This example is discussed by Bleher.

If you are looking for roots of polynomials uniformly scattered in the plane, I recommend recaling the coefficients by $\sqrt{n!}$

$$ f(z) = \sum_{n = 0}^\infty a_n \sqrt{\frac{L^n}{n!}} z^n$$

This is discussed by Krishnapur

$\endgroup$
1
  • 1
    $\begingroup$ Thank you, John, for this thorough answer and rich set of references. The reference to Tao's article "Local universality of zeroes of random polynomials" was especially useful to me. $\endgroup$ Aug 19, 2013 at 20:55
6
$\begingroup$
  1. Roots of polynomials of large degree tend to be uniformly distributed on a circle, as degree tends to infinity. But here we deal with polynomials of fixed degree.

  2. That the distribution must be rotation-invariant seems evident because the distribution of coefficients (uniform in the unit disc) is rotation invariant.

  3. To find distribution of moduli of zeros (which will depend on the fixed degree) is harder, but after all, when $d=2$ we have a simple explicit formula for the roots, and using this explicit formula, we can find an explicit formula for the density of the distribution. It will be complicated, of course.

EDIT: 4. One more remark: the distribution is symmetric in the unit circle because the distribution of coefficients is invariant with respect to reversing: $(a_0,...a_d)\mapsto (a_d,...,a_0)$.

  1. That there is a white spot inside can be qualitatively explained: the probability of very large zero is small, because this means that $a_d$ is very small. Property 4 then shows that the probability of small zero is also small.
$\endgroup$
5
$\begingroup$

A very nice paper on the subject is:

Mezincescu, G. Andrei(F-CENS-MT); Bessis, Daniel(F-CENS-MT); Fournier, Jean-Daniel(F-CENS-MT); Mantica, Giorgio(F-CENS-MT); Aaron, Francisc D.(R-BUCHFP) Distribution of roots of random real generalized polynomials. (English summary) J. Statist. Phys. 86 (1997), no. 3-4, 675–705. 60G99 (26C10 30B20 60F05)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.