Random roots crowd onto the circle

Almost none of the roots are real counted the real roots of a random polynomial and found about $\tfrac{2}{\pi}\ln n$ of them among $n$. That left the other roots, the great majority, somewhere in the complex plane, and the pictures showed where: close to the unit circle, spread round it. This essay is about that picture, and about the surprise that it is not really about randomness.

The simplest polynomial whose roots lie on the unit circle is $z^n - 1$, whose roots are the $n$-th roots of unity, evenly spaced at angles $2\pi k/n$. Its coefficients are $-1$, then $n - 1$ zeros, then $1$. A random polynomial with independent normal coefficients looks nothing like it — every coefficient is non-zero and they vary wildly — and yet its roots arrange themselves in almost the same way: nearly even in angle, nearly on the circle.

Paul Erdős and Pál Turán proved in 1950 that this happens for every polynomial whose coefficients are of comparable size. Their inequality bounds how uneven the directions of the roots can be by a single number computed from the coefficients: the sum of their sizes compared with the first and last. When that number is small, the roots’ directions are nearly even, whatever else the polynomial does. Randomness only supplies coefficients that make the number small.

Every polynomial with coefficients plus and minus one #

Take every polynomial of degree 11 whose coefficients are each $+1$ or $-1$ — there are $2^{12}$, but $p$ and $-p$ have the same roots, so fixing the constant term at $+1$ leaves 2,048 — and plot all their roots at once. The result is the figure above: a thick ring of roots around the unit circle, with lace-like edges and holes.

Every root lies strictly between radius $\tfrac12$ and radius 2, and the reason takes one line. If $|z| \le \tfrac12$, the terms after the constant add up to at most $\tfrac12 + \tfrac14 + \cdots < 1$ in size, so they cannot cancel the constant term, whose size is exactly 1. So $p(z) \ne 0$. The same argument applied to $z^{11}p(1/z)$, which has the same coefficients in reverse, rules out $|z| \ge 2$. A polynomial with coefficients $\pm 1$ can only vanish in the ring between.

The ring is much narrower in practice. The polynomial $1 - z - z^2 - \cdots - z^{11}$ has a real root just above $\tfrac12$, which is why the inner boundary is reached, but it is exceptional: 42% of all the roots lie within a tenth of the unit circle. The holes are equally telling. Near $z = 1$ a polynomial with coefficients $\pm 1$ is close to its value at 1, which is a whole number — the number of plus signs minus the number of minus signs. Either the signs balance exactly, and $z = 1$ is itself a root, or the value is at least 2 in size and the polynomial cannot fall to nought until $z$ has moved some distance away. So roots near 1 but not at it are rare, and a hole opens round the point. The smaller holes sit at other roots of unity for a related reason, subtler because the value there is an algebraic integer rather than an ordinary whole number.

A random polynomial of degree three hundred #

Random coefficients from the bell curve give the same picture without the lace. The polynomial of degree 60 has no real root at all, which for an even degree is allowed; the one of degree 300 has six. Every other root sits in a thin band around the circle, and the band at degree 300 is visibly thinner than at degree 60.

The two pictures differ in their coefficients and agree in the one property the next sections isolate: the coefficients are all of roughly the same size. A normal random variable is rarely much larger than 3 or smaller than a tenth, and among 301 of them the largest and the smallest in size differ by a factor of a few hundred at most — tiny compared with the factors, like $2^{300}$, that would be needed to push roots far from the circle.

That is the mechanism in outline. A polynomial of degree $n$ with a root of size $r$ has, among its coefficients, ratios that grow like $r^n$; conversely, when the coefficients are all within a modest factor of each other, no root can stray more than a modest factor to the $1/n$-th power from the circle, and that power is nearly 1. The roots are pinned near the circle by the $n$-th root of the coefficients’ spread.

Within one over n of the circle #

The thinning of the band can be measured. For random polynomials of degree 25, 100 and 400, the figure records how far each root is from the unit circle, and then multiplies that distance by the degree. If the band’s width were fixed, the three curves would spread out as the degree grew. Instead they lie on top of each other: the half-width of the band, measured this way, is about 1.8 at every degree, so a random root sits typically within about $1.8/n$ of the unit circle.

Larry Shepp and Robert Vanderbei computed the exact density of complex roots of random polynomials with normal coefficients in 1995, and it has precisely this shape: concentrated in an annulus of width of order $1/n$ about the circle, with a profile that, after the rescaling in the figure, does not depend on $n$. Ildar Ibragimov and Dmitry Zaporozhets showed in 2013 that the concentration holds for independent identically distributed coefficients exactly when the expected value of $\ln(1 + |a_k|)$ is finite, and fails without it: a coefficient law with extremely heavy tails produces occasional enormous coefficients, and an enormous coefficient drags roots away from the circle.

Directions spread evenly #

Radius is half of where a root is; the other half is its direction. For the 200 roots of a single random polynomial of degree 200, the figure compares the number of roots with direction between 0 and $\theta$ with the number an exactly even spread would put there, $200 \cdot \theta/2\pi$. The difference, divided by 200, is a staircase that wanders within about two hundredths of nought all the way round.

The largest discrepancy over any arc — the most by which the share of roots in some arc of directions exceeds or falls short of the arc’s share of the full turn — is $0.020$ for this polynomial. For the roots of unity it would be $1/n = 0.005$, the smallest possible for $n$ points; for 200 directions chosen independently at random it is typically about $0.085$ — the median over 400 such samples. The roots of a random polynomial are spread more evenly than random points would be, which is a first hint that something other than randomness is arranging them.

Part of the reason is local. Two roots of a random polynomial are unlikely to sit very close together: near a pair of close roots the polynomial would have to be small over a whole neighbourhood, which needs its coefficients to conspire, while independent points land close together all the time. John Hannay computed in 1996 how strongly the zeros of random analytic functions of this kind repel each other at short range, and the repulsion makes them look more like a crystal with defects than like a spray of independent points. The other part is global, and it is the subject of the next section: the coefficients as a whole limit how far the roots’ directions can drift from even.

The inequality that needs only the coefficients #

Erdős and Turán’s theorem makes the hint exact. For a polynomial $a_0 + a_1 z + \cdots + a_n z^n$ with $a_0 a_n \ne 0$, let $L = |a_0| + |a_1| + \cdots + |a_n|$ be the sum of the coefficients’ sizes. Then for every arc of directions from $\alpha$ to $\beta$, the number $N(\alpha, \beta)$ of roots in it satisfies

$$\left|\frac{N(\alpha,\beta)}{n} - \frac{\beta - \alpha}{2\pi}\right| \;\le\; 16\,\sqrt{\frac{1}{n}\,\ln\frac{L}{\sqrt{|a_0 a_n|}}}.$$

The right-hand side depends on nothing but the coefficients’ sizes, and it is small when two things hold: the degree is large, and $L$ is not much larger than $\sqrt{|a_0 a_n|}$. For $z^n - 1$ the ratio is 2 and the bound is $16\sqrt{\ln 2/n}$. The coefficients alone decide it, as what the coefficients already know found for the sum and product of the roots and every power sum, from the coefficients alone for their power sums: here the coefficients’ sizes, without their signs, fix how evenly the roots face every direction. For a polynomial with coefficients $\pm 1$ it is $n + 1$ and the bound is $16\sqrt{\ln(n+1)/n}$, which tends to nought. For random normal coefficients it is typically of order $n$ as well.

The figure tests the inequality on 92 polynomials of three kinds. Random normal and random sign coefficients give small measures and small discrepancies. The third kind is built to be uneven: $(z - c)^{n/2}(z^{n/2} + 1)$ puts half its roots at the single point $c$, so its discrepancy is at least a half. And its measure is large, because the factor $(z - c)^{n/2}$ has binomial coefficients that dwarf its first and last. The inequality charges exactly for this: a polynomial can only bunch its roots by having coefficients of very unequal sizes.

The constant 16 is far from sharp — the largest ratio of discrepancy to measure among the 92 is $0.79$. Tord Ganelius lowered the constant in 1954, and it cannot be lowered below a positive limit, since some polynomials do achieve discrepancies of the order the inequality allows. What matters is the shape: the discrepancy is at most of order $\sqrt{(\ln n)/n}$ for any polynomial with coefficients of one size, randomness or none.

A measure that counts the roots outside #

The radial half of the picture has an exact form that needs no inequality at all. Multiply together the sizes of all the roots that lie outside the unit circle, and multiply by the size of the leading coefficient. The result is called the Mahler measure of the polynomial, and Jensen’s formula from complex analysis says it equals the geometric mean of $|p(z)|$ as $z$ runs round the unit circle. A geometric mean is at most the ordinary root-mean-square, and the root-mean-square of $p$ on the circle is $\sqrt{|a_0|^2 + \cdots + |a_n|^2}$, which is at most $L$.

So the product of the sizes of the roots outside the circle is at most $L/|a_n|$. The same argument applied to the reversed polynomial bounds the product of the reciprocals of the sizes inside by $L/|a_0|$. Taking logarithms and adding, the average over all $n$ roots of $|\ln|z||$ is at most $\tfrac{2}{n}\ln\bigl(L/\sqrt{|a_0 a_n|}\bigr)$ — the very quantity inside Erdős and Turán’s square root. For the polynomials with coefficients $\pm 1$ of degree 11 the bound is $2\ln 12/11 \approx 0.45$; the actual average of $|\ln|z||$ over all 22,528 roots in the first figure is $0.17$.

The Mahler measure has a life of its own. For polynomials with whole-number coefficients it is at least 1, and it equals 1 exactly when every root is a root of unity or nought — Kronecker’s theorem, which on the circle and never home followed to the famous gap above 1 that Lehmer asked about. Here the same quantity plays a gentler part: it is the budget of distance from the circle that a polynomial’s coefficients allow its roots, and balanced coefficients leave almost none.

Why the coefficients know the angles #

The proof runs through the same device as a loop that cannot miss the middle: the change in the argument of $p(z)$ as $z$ moves round a circle counts the roots inside. Erdős and Turán compare the polynomial on the unit circle with its behaviour on slightly larger and smaller circles. If the coefficients are balanced, $|p(z)|$ cannot be enormous anywhere on the circle — it is at most $L$ — and it cannot be tiny everywhere either, since its average square on the circle is the sum of the squared coefficients. A polynomial whose size on the circle is controlled from above and below cannot have its argument racing ahead in one arc and dawdling in another, and the argument’s rate of change is the density of root directions.

The same idea explains the one-over-$n$ band. A root at radius $1 + \delta$ contributes a factor $(1+\delta)^n$ to the sizes of some coefficients relative to others, which is $e^{n\delta}$ approximately. Balanced coefficients forbid large $n\delta$, and so $\delta$ must be of order $1/n$. The pictures are the inequalities made visible: the radius from the balance of first and last coefficients against the total, the angle from the size of the polynomial on the circle.

The same reasoning says what the roots of the derivative do. The roots of the slope stay inside placed them inside the convex hull of the roots, which for a random polynomial is nearly the whole unit disc and so says little. But the derivative of a polynomial with balanced coefficients again has balanced coefficients — $k a_k$ in place of $a_k$, weighted more heavily towards the top, but with $L$ and the first and last coefficients changed only by factors polynomial in $n$ — so the Erdős–Turán bound applies to it too, and its roots also crowd onto the circle with evenly spread directions.

The picture of roots of unity is thus the extreme case of a general law. The sums of roots of unity that add to nothing studied the roots of $z^n - 1$ in detail; the random polynomial is a noisy $z^n - 1$ whose noise has moved each root a little, but, by Erdős and Turán, never a lot. The exact structure is lost — the sums that obey a smaller equation depended on the roots being precisely the powers of one root — and what survives the noise is only the statistics: nearly on the circle, nearly evenly spaced.

Still open: how flat a polynomial of signs can be #

The polynomials with coefficients $\pm 1$ in the first figure are called Littlewood polynomials, after John Edensor Littlewood, who asked how their size on the unit circle can be controlled. By the average-square identity, a Littlewood polynomial of degree $n$ has average square size $n + 1$ on the circle, so its typical size there is $\sqrt{n+1}$. Littlewood asked whether one can be flat — bounded between two constant multiples of $\sqrt{n}$ everywhere on the circle. Paul Balister, Béla Bollobás, Robert Morris, Julian Sahasrabudhe and Marius Tiba proved in 2020 that the answer is yes, for every degree.

Whether one can be ultraflat is open. Erdős conjectured that every Littlewood polynomial reaches at least $(1 + c)\sqrt{n+1}$ somewhere on the circle, for a fixed $c > 0$ independent of the degree — that is, none can be flat to within a factor tending to one. With complex coefficients of size one, rather than $\pm 1$, Jean-Pierre Kahane showed in 1980 that ultraflat polynomials exist; for real signs, no one has either found them or ruled them out. The question is how closely a polynomial with the crudest possible coefficients can imitate the smooth, even behaviour that $z^n - 1$ has only at its roots — the same imitation this essay has watched the roots perform.

What the pictures cannot settle #

Every root in the figures was found numerically and checked by substitution, and the ring from $\tfrac12$ to 2 was checked on all 22,528 roots of the first figure, as the one-line argument requires. The Erdős–Turán inequality was checked on 92 polynomials, all of which satisfy it with room to spare; that is evidence about those polynomials and says nothing about the constant’s sharp value.

The scaled distance profiles and the angular staircase are samples. The exact root density that Shepp and Vanderbei derived, and the proofs of Erdős and Turán and of their successors, are what turn the pictures into theorems. The lace at the edges of the first figure is another matter: the fine structure of the closure of the roots of all Littlewood polynomials, with its fractal boundaries and its holes at roots of unity, has been studied since the 1990s and is still only partly understood.