Web toy: fractal explorer for polynomial-roots plot

If you plot, in the complex plane, all the roots of polynomials whose coefficients all lie in a finite set of complex numbers, the result forms a fractal.

This page is an interactive demonstration of that fractal, using just two possible coefficient values (initially $\pm1$). You can click and drag the white dots to change the coefficients, and the fractal re-plots itself in real time as you go.

The code works by using a recursive bounding argument (see below) to rule out a particular point being a root of any such polynomial. So the black area is an over-estimate: all the true roots should fall within it, but it covers more area than really necessary.

The input below the display allows you to adjust the recursion depth. Turning it up will make your browser run much more slowly!

DISCLAIMER: this is Baby's First WebGL Program. As of 2023-10-07, it seems to work for me on both Firefox and Chromium, running on desktop Linux. That's all the testing it's had, and if it doesn't work somewhere else, I probably don't know how to fix it.

Credit to Mark Sherry for the algorithm; my own work is just the translation into shoddy WebGL.

Details of the recursive algorithm

$\def\C{\mathbb{C}}\renewcommand{\leq}{\leqslant}\renewcommand{\geq}{\geqslant}$Suppose we have a finite set $S\subset\C$ of permitted polynomial coefficients, and a candidate point $z\in\C$. We want to rule out the possibility that $z$ can be the root of any polynomial with coefficients in $S$.

We begin by generalising the problem to be solved: let us also choose $w\in\C$, and ask whether any polynomial $P$ can have $P(z)=w$. (So the original problem is recovered by setting $w=0$.)

Suppose $|z|<1$. Let $m$ be the maximum modulus of any coefficient, that is, $m=\max\{|s|:s\in S\}$. Then we have an upper bound on the modulus of $P(z)$: $$|P(z)| \leq \sum_{i=0}^\infty |p_i z^i| \leq \sum_{i=0}^\infty m\,|z^i| = m \sum_{i=0}^\infty |z^i| = \frac{m}{1 - |z|}$$

Therefore, if $\frac{m}{1-|z|} < |w|$, all possible values of $P(z)$ are bounded away from $w$, and so we know $P(z)\neq w$.

Supposing that $z$ is not ruled out by this test, we now consider all possible values for the constant term of $P$. For each $s\in S$, can there exist $P$ with $P(z)=w$ such that the constant term of $P$ is $s$? Put another way, can there exist $Q$ such that $s + zQ(z) = w$?

But this is another case of the same question: it's equivalent to asking whether $Q(z)$ can possibly equal $\frac{w-s}{z}$. So we recursively invoke the same algorithm to ask that question, with the same $z$ but a modified value of $w$.

To obtain a totally precise answer we'd have to recurse to infinity in an impossible manner. So instead we bound the recursion depth. Points in the above diagram are coloured according to the maximum recursion depth that was reached before discovering that they couldn't possibly be a root. The black area represents the region where the recursion depth limit was reached.

At the start of the recursion (when $w=0$), we can assume WLOG that $|z|\leq 1$, because if $z\neq 0$ is the root of any polynomial with coefficients in $S$, then so is $1/z$, by reversing the order of the coefficients.

Unlike the most standard complex-plane fractals like Mandelbrot and Julia sets, this procedure must potentially recurse more than once at each step. But the search tree is pruned as much as possible by repeating the bounding argument at every step, so that we only recurse deeply in the promising-looking branches.