Covering rather than avoiding

Two results are both arguments against guessing. The basins interleave, so no neighbourhood of a boundary point determines anything; and some regions are traps, so no amount of care with a single guess is safe.

Both take the guess as the thing to be improved. The result here takes it as the thing to be abandoned.

Hubbard, Schleicher and Sutherland, 2001. For every degree $d$ there is a set of $O(d(\log d)^2)$ points in the plane, computable from $d$ alone, such that Newton’s method started from every point of the set finds every root of every polynomial of degree $d$ whose roots lie in the unit disc.

The fractal boundary is not avoided and the traps are not dodged. They are outnumbered.

The construction #

The set is explicit and short to state, which is most of what makes the theorem useful.

Take $s = \lceil 0.26632 \log(d-1) \rceil$ circles centred at the origin, with radii

$$r_\nu \;=\; \big(1 + \sqrt2\big)\left(\frac{d-1}{d}\right)^{\frac{2\nu - 1}{4s}}, \qquad \nu = 1, \dots, s,$$

and place $N = \lceil 8.32547\, d \log d \rceil$ equally spaced points on each. The whole set has $sN$ points, which is $O(d(\log d)^2)$.

For $d = 5$ that is one circle of sixty-seven points, which is what the hero figure draws. For $d = 100$ it is two circles of about three thousand eight hundred points each. For $d = 10^6$ it is four circles of about a hundred and fifteen million points — large, and linear-ish in $d$ rather than exponential, which is the whole claim.

The factor $(d-1)/d$ is a little under one, so every circle sits a little inside $1 + \sqrt2 \approx 2.414$ — at degree five the one circle has radius $2.283$, which is more than twice as far out as any root.

Nothing in the construction looks at the polynomial. The radii and the counts come from $d$; the only thing assumed about the polynomial is that its roots are inside the unit disc, which is arranged by scaling, since a bound on the roots is available from the coefficients in one pass — every root of a monic polynomial is within $1 + \max|a_i|$ of the origin, by an argument that is the triangle inequality applied once.

Why circles, and why those radii #

The proof’s shape explains the constants, and it is worth having because the constants otherwise look invented.

Every root has a basin, and a basin is an open set. The theorem’s work is showing that every basin reaches far enough out and is wide enough at some radius that a sufficiently fine ring of points cannot miss it.

Two facts do it. First, each basin of a Newton map is connected and unbounded — a theorem of Przytycki’s — so every basin reaches out past any circle one cares to draw. Second, a basin’s angular width at radius $r$ can be bounded below: a basin that reaches out to radius $r$ occupies at least a definite angle there, and the bound falls off in a controlled way with $r$ and $d$.

So a circle of $N$ equally spaced points meets every basin provided $N$ exceeds the reciprocal of the smallest angular width at that radius. The radii are chosen so that between them they catch every basin — a basin thin at one radius is wide at another — and the several circles are what handles the spread.

The constants $0.26632$ and $8.32547$ are what the estimates give, and they are not sharp; the theorem is about the exponent $d(\log d)^2$ and the constants are what a particular chain of inequalities produced.

The two properties the proof needs #

The argument rests on two facts about Newton basins and both were theorems before this result, which is worth noticing: the covering theorem is an assembly of geometry that already existed.

Every basin is connected. Przytycki proved in 1989 that the basin of a root under a Newton map is connected — not merely that the component containing the root is, but that the whole set of points converging to it is one piece. That is false for a general rational map and is a genuine feature of Newton maps.

Every basin is unbounded. Following from the behaviour at infinity: far from the roots the Newton map behaves like $z \mapsto z(1 - 1/d)$ — a contraction toward the origin by a fixed proportion, which is a map that shrinks everything and pulls the far field inward — and the pulling divides the far field into $d$ sectors — one heading toward each root. So each basin extends to infinity in at least one direction.

Those two together are what makes covering possible, and the reason is worth stating in the negative. A bad set with empty interior cannot be avoided by any local test; what defeats it is that the good set has structure — it is a finite number of connected pieces, each reaching out to arbitrary distance. The complement having few pieces, rather than the bad set being small, is what a covering argument needs.

The third ingredient is quantitative and is where the constants come from: a bound on how thin a connected unbounded basin can be at a given radius. Thinness is what a ring of points can miss, and the estimate says it cannot be thin at every radius at once.

What the guarantee is, exactly #

Three qualifications are doing real work and each is worth stating, because the theorem is often quoted more strongly than it is.

It finds every root, not efficiently. The statement is that each root has at least one starting point in the set that converges to it. It says nothing about how many steps that takes, and the number can be large — the bound on the total work is much worse than the bound on the set’s size.

It is about exact arithmetic. The theorem is a statement about the dynamics of a rational map on the complex plane. Rounding is not modelled, and a starting point that would converge in exact arithmetic may not in floating point.

And it needs the roots in a known region. Scaling handles that, and the scaling needs a bound on the root sizes — Cauchy’s bound from the coefficients gives one immediately, so this is a preprocessing step rather than a hypothesis. It is a hypothesis with teeth all the same: handing the construction a polynomial whose roots are at $1$, $2$ and $3$ leaves the outermost root reached by none of the twenty-eight starts, and the mode refuses to draw it. The circles are placed for a unit disc and mean nothing without one.

What it does settle is the question those two results leave open. Those say a guess may fail; this says a list cannot, and the list is short. That is a different kind of answer, and it is the kind that turns an algorithm with a known failure mode into one with a proof of termination.

The measurement the figures make #

Each figure runs the construction, runs the method from every point of it, and requires every root to be reached. That is a check on the theorem at one polynomial, and it is worth saying what it does and does not establish.

It establishes that the set works here. Five roots, sixty-seven starts, and the least-found root reached from several of them.

It does not establish the theorem, which is about all polynomials of the degree, including the ones with roots nearly coincident where the basins are thinnest. The figures draw the easy cases because those are the ones a figure can hold.

And the count beside each root is the interesting number. For $z^5-1$ the sixty-seven starts divide nearly evenly among the five roots, because the polynomial is symmetric. For a polynomial with one root far from the others the division is lopsided, and the theorem’s content is that the smallest share is never zero.

Why the points are put far out #

The last figure makes visible the one design decision the construction contains, and it is the opposite of what an implementer would guess.

The starting points are placed well outside the region the roots occupy. The roots sit inside the unit disc by hypothesis, and the single circle at degree five has radius $2.283$ — more than twice as far out as any root, and outside every basin’s complicated part.

The instinct is to start near where the answer is. That is exactly wrong here, and the two results say why: near the roots the basins interleave, the boundary is dense, and the traps live there. Far out, the picture is simple. Each basin, being connected and unbounded, has reached out and settled into a broad sector by the time the radius is large, and the sectors are what a ring of points cannot miss.

The three-basin figure makes the same observation from the other side: seen from far enough out, the three basins of $z^3-1$ settle into three broad regions and a guess made anywhere sensible lands where intuition says. What was drawn there as reassurance is here the mechanism.

That is worth carrying, because it generalises. Where an object’s structure is complicated near its features and simple far from them, the useful place to sample is far away — and the instinct to look where the answer is can be precisely the wrong one.

The other way to do it, and why this one is remarkable #

Root-finding is a solved problem in practice and it is worth saying what this result competes with, because the comparison is what makes it a curiosity rather than a tool.

What is actually used is the Jenkins–Traub algorithm, or a companion-matrix eigenvalue computation, or Aberth’s method, and none of them is Newton’s method run from a fixed set. They are reliable, fast, and have no comparable proof of global convergence — their reliability is empirical, refined over decades. The companion-matrix route is the most instructive of the three here, since it converts the problem into finding the numbers a linear map leaves alone and then uses fifty years of work on that instead.

What this result supplies is a guarantee rather than a method. It says the simplest conceivable strategy — take Newton’s method, run it from a list — provably works, which nobody expected: the two results are exactly the reasons to expect it not to. That the fractal structure can be defeated by covering is the surprise, and it is a statement about the geometry of the basins rather than about computation.

It is worth adding what the result is a descendant of. Smale asked in 1981 how often Newton’s method fails and what a good starting point costs; the answer developed through the 1980s into a theory of approximate zeros and their cost, and this theorem is the global end of it. The question was about the efficiency of an algorithm and the answer was a theorem about connected sets in the plane.

How many points, in numbers #

The formula is short and the numbers it gives are worth writing out, because the whole claim is that they are manageable.

The circle count grows like $\log d$ and the points per circle like $d\log d$, so the total is $d(\log d)^2$ — at a million, about four hundred and sixty times the degree.

That is large and it is the right kind of large. A degree-$d$ polynomial has $d$ roots, so $d$ starting points is the absolute floor; the construction pays a factor of $(\log d)^2$ over that floor, which at a million is about four hundred and sixty and at a thousand is about a hundred and fifteen.

Compare what the alternative would be. A method with no guarantee, restarted from random points until every root is found, has no bound at all — there is no argument that it terminates, and the two results give reasons to doubt it. The factor of $(\log d)^2$ buys a proof, and a proof of termination is the thing none of the practical algorithms has.

What is still not known #

The constants are not sharp. How many starting points are really needed is open; the lower bound available is about $d$, the upper bound is $d(\log d)^2$, and the gap has not closed.

The floating-point question is open in the form that matters. Whether the guarantee survives rounding, and at what precision, is not settled — and for an algorithm this is the question, since exact complex arithmetic is not available.

And the cost is not bounded usefully. The theorem bounds how many starts are needed and not how many iterations, and the iteration bound that is known is far worse than anything observed. So the result guarantees termination without guaranteeing a useful running time, which is the same shape as an existence proof that names no object — here the object exists and is exhibited, and what is missing is the cost.

One polynomial at a time #

One polynomial at a time. Every figure runs the construction on a specific polynomial and checks it there. The theorem quantifies over every polynomial of the degree, and the hard cases — roots nearly equal, basins thin — are exactly the ones that cannot be drawn at any useful scale, because the interesting structure is smaller than a pixel.

The colouring records where a start finished and not how long it took. Several of the sixty-seven take hundreds of iterations; none of that is visible, and the figure’s cap of six hundred is chosen so that all of them finish rather than because six hundred means anything.

And the circles are drawn and their radii are not explained by the drawing. The one circle at degree five sits at $(1+\sqrt2)(d-1)^{1/4}$, which is about $3.6$, and nothing in the picture says why that radius rather than another. The reason is the angular-width bound, which is prose.

Still open: where the remaining questions are #

The three results together answer a question about starting points and open two more.

The dynamics of Newton maps as a family. Which rational maps arise as Newton maps of polynomials is completely characterised, and their parameter spaces are the analogues of the Mandelbrot set, with the same unresolved questions the quadratic family’s parameter plane has about local connectivity and about whether the hyperbolic components are dense.

And the same question for other methods. Newton’s method is one of a family — Halley’s, Chebyshev’s, the higher-order Householder methods — each with its own basins, its own traps, and no known universal starting set. Whether the covering result extends is not settled, and the proof’s ingredients are specific enough to Newton maps that nobody expects it to transfer without work.

The same move elsewhere #

Covering a bad set rather than detecting it is a general strategy and two other instances in this collection are worth setting beside it, because the three have the same shape and completely different subjects.

Randomised algorithms that repeat. A method that succeeds with probability a half on any input is turned into one that succeeds with probability $1 - 2^{-k}$ by running it $k$ times, and no individual run is improved. The bad set is not characterised and does not need to be; what is needed is that it is not the same bad set each time.

Covering codes and testing. Checking every pair of parameter settings rather than every combination, which the design theory of the computation field supplies, is the same trade: a small set arranged so that nothing of interest can escape all of it.

The difference here is that the covering is deterministic and provable. The sixty-seven points are the same sixty-seven every time; no randomness is involved; and the guarantee is not a probability but a theorem. That is rare, and it is rare because it needs the structural facts of the section above — a random covering argument would need only a counting bound, and a deterministic one needs to know the shape of what is being covered.

Outnumbering a pathology #

The habit is worth stating because it is the opposite of the usual response to a bad set.

Faced with a region where an algorithm fails, the instinct is to detect it and avoid it. Both results are reasons that cannot work here: the bad set has empty interior in one case and is a fractal in the other, and no local test distinguishes a good starting point from a bad one.

The move that works is to give up on any one attempt succeeding and arrange that not all of them can fail. That requires knowing something about the shape of the good set rather than about its size — here, that every basin is connected, unbounded, and not too thin — and the whole proof is establishing those three properties.

So the question to ask of an unavoidable failure region is not how to detect it. It is what is known about the complement’s geometry, and whether that is enough to cover it with a list.