Almost none of the roots are real

A polynomial of degree $n$ has exactly $n$ roots in the complex numbers, counted with multiplicity, and what the coefficients already know is how much the coefficients say about them before any is found: their sum, their product, and every symmetric combination. A loop that cannot miss the middle proved it by watching the image of a large circle wind round the origin $n$ times. How many of those roots are real is a different question, and for a particular polynomial it can be anything from $n$ down to nought or one, depending on the parity of $n$. The polynomial $(x-1)(x-2)\cdots(x-n)$ has all its roots real; $x^n + 1$ has at most one.

So ask it of a typical polynomial. Choose each coefficient independently from the standard normal distribution — the bell curve of mean nought and spread one — and count the real roots. A quadratic $ax^2 + bx + c$ has two real roots when $b^2 > 4ac$ and none otherwise, and with normal coefficients the average count is about $1.30$. A polynomial of degree thirty might be expected to have many more. It usually has two or four.

The average number of real roots of a random polynomial of degree $n$ grows like $\tfrac{2}{\pi} \ln n$. Mark Kac proved it in 1943, and it means that almost all the roots of a random polynomial leave the real line: of a thousand roots, about five are real. This essay computes the average exactly, checks it against samples, and then finds the reason for the logarithm in where on the line the real roots sit.

Thirty roots and two of them real #

The two polynomials in the figure were drawn at random and their roots found numerically. Every root reported was checked by substituting it back, and every root called real was checked again by the polynomial changing sign across it. The degree-30 polynomial has two real roots, at $-2.335$ and $-1.074$. The degree-100 polynomial also has two, at $-0.327$ and $0.994$. All the other roots come in pairs $a \pm bi$, mirror images across the real line, as the roots of any polynomial with real coefficients must.

Two features stand out beyond the count. The complex roots are not scattered across the plane: they sit close to the unit circle, closer for the higher degree. And the real roots that do occur tend to be near $+1$ or $-1$ — the circle’s two points on the real line. The first feature is the subject of a separate essay. The second turns out to explain the count.

A polynomial with real coefficients crosses the real axis at each real root. A polynomial of high degree with random coefficients oscillates, but the oscillation of a sum of many random terms is mostly cancellation, and a sign change of the whole requires the terms to line up in a particular way. The question is how often that happens across the line, and the answer is a density.

Two small cases by hand #

The smallest cases can be settled without any formula for the density, and they already show the count falling behind the degree. A quadratic $ax^2 + bx + c$ with independent normal coefficients has real roots exactly when its discriminant $b^2 - 4ac$ is positive. The product $4ac$ of two independent normals is as often negative as positive, and when it is negative the discriminant is certainly positive; when it is positive, $b^2$ has to beat it. A simulation of two million quadratics finds real roots in 64.9% of them, so the average number of real roots is about $1.30$ — the first point of the curve below, where the exact integral gives $1.297$.

A cubic always has at least one real root, and has three exactly when its discriminant is positive. Among 400,000 random cubics the discriminant was positive in about a quarter, and the average count was $1.49$. So the quadratic realises $65\%$ of its possible real roots on average, and the cubic only half: already at degree three, most of the room the degree allows is going unused.

The pattern continues, and the sections below show why it continues in exactly the way it does. At degree $n$ the share of roots that are real is the average count divided by $n$: about one in eight at degree twenty, one in twenty-eight at degree a hundred, one in two hundred at degree a thousand.

The count computed exactly, and a logarithm #

Kac’s method is to count sign changes in expectation. At each point $x$ of the real line, the value $p(x) = a_0 + a_1 x + \cdots + a_n x^n$ is itself a normal random variable, since it is a fixed combination of independent normal coefficients; so is its derivative $p'(x)$. The chance that $p$ crosses nought in a tiny interval $[x, x + dx]$ depends only on the joint distribution of $p(x)$ and $p'(x)$, which is a pair of correlated normals, and working it out gives an expected number of crossings per unit length. This is now called the Kac–Rice formula, after Kac and Stephen Rice, who found the same principle for random signals in 1944.

For coefficients all of variance one the formula reads

$$\mathbb{E}\,N_n = \frac{4}{\pi} \int_0^1 \sqrt{\frac{1}{(1-x^2)^2} - \frac{(n+1)^2 x^{2n}}{(1-x^{2n+2})^2}}\;dx,$$

the factor four accounting for the four stretches $(-\infty,-1)$, $(-1,0)$, $(0,1)$ and $(1,\infty)$, which carry the same expected number of roots by symmetry. The solid curve in the figure is this integral evaluated numerically for every degree from 2 to 1,024. The dots are averages over 120 random polynomials at each marked degree, and every one lies within two standard errors of the curve.

The integral grows like $\tfrac{2}{\pi} \ln n$ plus a constant, $0.6257$ to four places, which is the dashed line. The approach is quick: the two differ by $0.07$ of a root at degree eight, by $0.02$ at degree 32 and by less than a hundredth from degree 128 on, and at degree a thousand the exact value is $5.024$. Doubling the degree adds $\tfrac{2}{\pi} \ln 2 \approx 0.44$ of a real root, whatever the degree already is.

The constant was computed by J. Ernest Wilkins in 1988, together with further terms of the expansion. Kac’s own proof gave the leading term. What neither the formula nor its expansion says, by itself, is why the logarithm appears — why the real roots are so scarce and yet not bounded. For that the density has to be looked at along the line.

Crowded towards plus and minus one #

The density of real roots is far from even. It is low near the origin, rises steeply towards $\pm 1$, peaks there at $3.77$ roots per unit length for degree 40, and falls away beyond. The histogram of 1,168 real roots from 400 random polynomials follows it closely.

The reason for the peaks is a competition between terms. For $|x|$ well below 1, the powers $x^k$ decay quickly, the first few terms dominate, and $p(x)$ behaves like a polynomial of small degree, which has few roots. For $|x|$ well above 1 the last few terms dominate and the same is true in reverse. Only near $|x| = 1$ are all $n + 1$ terms of comparable size, and only there can the sum oscillate rapidly. At $x = 1$ itself the polynomial is simply the sum of its coefficients, a normal variable with variance $n + 1$; a little way from 1 the terms are weighted by slowly changing powers, and the sum becomes a slightly different combination of the same coefficients — correlated with the value at 1, but not identical. How quickly that correlation decays as $x$ moves away from 1 sets how often the sum can change sign, and it decays over a distance comparable to $1 - |x|$ itself.

The two halves of the line mirror each other. The polynomial $x^n p(1/x)$ has the coefficients of $p$ in reverse order, which for independent identically distributed coefficients is another polynomial with the same distribution. Its roots are the reciprocals of the roots of $p$, so a root of $p$ at $x$ inside $(-1, 1)$ is as likely as one at $1/x$ outside it. The same reversal pairs the power sums of the roots with those of their reciprocals, the quantities every power sum, from the coefficients alone computed without finding a single root. That is why 576 of the 1,168 sampled roots lie between $-1$ and $1$: in expectation exactly half do.

Even on a logarithmic ruler #

The peaks become intelligible in the right coordinate. Measure a root’s position not by $x$ but by how close it is to $\pm 1$, on a logarithmic scale: $t = -\ln(1 - |x|)$, which is nought at the origin, 1 at $|x| \approx 0.63$, 2 at $|x| \approx 0.86$, and $\ln n$ at a distance $1/n$ from $\pm 1$. In this coordinate the real roots spread almost evenly.

Near $\pm 1$ but not too near, the Kac–Rice density is approximately $1/(\pi(1 - x^2))$, and changing variable to $t$ turns that into a constant. Counting the two signs and the two sides of $\pm 1$ gives four copies, so the real roots arrive at a steady rate of about $2/\pi$ per unit of $t$ — the dashed line in the figure, which the exact curve approaches after starting higher at the origin. The histogram from 150 random polynomials of degree 200 follows the curve.

The even spread stops at $t \approx \ln n$. Closer to $\pm 1$ than a distance $1/n$, the terms of the polynomial no longer look like a sum of independent pieces — $x^k$ hardly changes over the whole range of $k$ — and the polynomial there behaves like a single smooth random function with no room to oscillate. So the real roots occupy a stretch of length about $\ln n$ in the logarithmic coordinate, at a rate of $2/\pi$ per unit, and the total is about $\tfrac{2}{\pi} \ln n$.

The logarithm is the length of the region in which a polynomial of degree $n$ can oscillate, measured on the scale that makes its oscillation uniform. Each doubling of the degree lets the roots come a factor of two closer to $\pm 1$, which adds $\ln 2$ to the length of the region and $\tfrac{2}{\pi} \ln 2$ to the count.

The logarithm belongs to equal variances #

The count depends on the law chosen for the coefficients, and the logarithm is a feature of giving every coefficient the same spread. Alan Edelman and Eric Kostlan showed in 1995 that the Kac–Rice density has a geometric meaning, and with it computed the answer for other laws. If coefficient $a_k$ has variance equal to the binomial coefficient $\binom{n}{k}$, the expected number of real roots is exactly $\sqrt n$, for every $n$ — the figure’s middle curve passes through 2, 4, 8 at degrees 4, 16, 64 to four decimal places. That law is the natural one from a geometric point of view: it is the only one whose distribution is unchanged by rotating the real projective line, so no point of the line is special.

With variances $1/k!$, the coefficients of the exponential series, the count grows like $\tfrac{2}{\pi}\sqrt n$. At degree 128 the ratio to $\sqrt n$ is still $0.715$ and falls towards $2/\pi \approx 0.637$ only slowly. The real roots of such a polynomial spread roughly evenly over an interval of length about $2\sqrt n$ centred at the origin, rather than crowding near $\pm 1$.

Equal variances concentrate the action near the unit circle, because that is where equal coefficients make all the terms the same size. Change the weights, and the region where the terms balance moves and changes shape, and the count changes with it. The logarithm is not a universal fact about random polynomials; it is what happens when every power of $x$ is given the same importance.

Signs as good as bell curves #

Kac’s argument uses the normal distribution in an essential way: a fixed combination of normal variables is normal, which is what makes the joint law of $p(x)$ and $p'(x)$ computable. It is natural to ask whether the answer depends on that. Take the simplest possible random coefficients instead — each $+1$ or $-1$ with equal chance.

At low degree the counts differ. A random polynomial of degree four with coefficients $\pm 1$ has about $1.2$ real roots on average, against $1.64$ for normal coefficients. But the gap closes as the degree grows, and at degree 128 the two samples average $3.70$ and $3.58$. Paul Erdős and Cyril Offord proved in 1956 that polynomials with coefficients $\pm 1$ follow the same law: the number of real roots is $\tfrac{2}{\pi}\ln n + o(\ln n)$ with probability tending to one.

The universality has a reason visible in the logarithmic picture. What sets the rate of $2/\pi$ per unit is how $p(x)$ behaves on a stretch where many terms contribute comparably, and there the sum of many independent coefficients looks normal whatever the coefficients are, by the principle the bell curve from coin flips made visible. Near the origin only the first few coefficients matter and their actual distribution shows through, which is why small degrees differ. Terence Tao and Van Vu extended the universality in 2015 to a wide class of coefficient laws: the average is $\tfrac{2}{\pi}\ln n$ to within an error bounded independently of $n$, whatever the law, so long as it has mean nought and a little more than a finite variance.

What the count does not settle #

The average is one number about a distribution, and as the average settles and the wobble does not showed for sums of coin tosses, the spread around it carries information the average cannot. The spread is known here too: Nina Maslova showed in 1974 that the variance grows like $\tfrac{4}{\pi}(1 - \tfrac{2}{\pi}) \ln n$, and that the count, suitably scaled, is asymptotically normal. So a random polynomial of degree a thousand has about $5.0 \pm 1.8$ real roots, and a degree-$n$ polynomial almost never has more than a few times $\ln n$.

The count also says nothing about which roots are real in a given polynomial. For that the tool is exact and not statistical: the remainders of the Euclidean algorithm applied to $p$ and $p'$, which the remainders that count the roots turned into Sturm’s theorem, count the real roots of any particular polynomial in any interval. The random theory predicts what that count will usually be; Sturm’s sequence finds it for the one polynomial at hand.

And there is a relation to the derivative’s roots. The roots of the slope stay inside showed that the critical points lie inside the convex hull of the roots. For a random polynomial the roots hug the unit circle, so the hull is nearly the whole disc and the theorem says little; the real critical points obey their own law of the same logarithmic kind, since $p'$ is again a polynomial with independent normal coefficients, of unequal variances $k^2$.

Still open: the chance of no real root at all #

A polynomial of odd degree must have at least one real root, since it tends to opposite infinities at the two ends of the line. A polynomial of even degree can have none. How likely is that for a random polynomial of even degree $n$?

The answer decays like a power of the degree, $n^{-b}$, for some exponent $b$. Amir Dembo, Bjorn Poonen, Qi-Man Shao and Ofer Zeitouni proved in 2002 that such a law holds, with $b$ between $0.4$ and $2$, and their simulations put it at about $0.76$. The exact value of $b$ is not known, and it is not even known whether it is a simple number. The same exponent governs the chance that a certain smooth random process stays positive for a long time — a persistence probability — and the corresponding exponents for many such processes are known only numerically.

The difficulty is that the event is global and rare. The Kac–Rice formula counts crossings on average and is blind to their correlations, while the absence of every crossing on the whole line is a statement about all of them at once. A random polynomial with no real root has to stay on one side of the axis across the whole region of length $\ln n$ where it would ordinarily oscillate, and computing the probability of that demands exactly the correlation structure the average ignores.

What the pictures cannot settle #

Every count here was obtained by finding every root numerically and checking it, and every real root was confirmed by a change of sign. The exact curves come from evaluating the Kac–Rice integral numerically to high accuracy, and the samples agree with them within their sampling error. None of that is a proof of the asymptotic law; it is the law observed where it can be computed, and the proofs are Kac’s, Erdős and Offord’s, and Edelman and Kostlan’s.

The pictures show averages over some hundreds of polynomials. Individual polynomials vary: among the samples at degree 128 some had one real root and some had eight. The theorem describes what the typical polynomial does, and it leaves room for every atypical one — including the polynomials with all their roots real, which are exactly the ones that the textbooks, choosing their examples by hand, tend to show.