# Multibrot

# 1 Critical Point

$$f_c'(z) = N z^{N-1} = 0$$

has the solution

$$z_0 = 0$$

which is where iteration should start from to determine the number of components that the filled-in Julia set has (1 if it remains bounded, infinitely many if it escapes to infinity).

# 2 Escape To Infinity

Suppose $|z_n| > R \ge \max(|c|, 1)$ If that implies $|z_{n+1}| > (1 + \epsilon) R$ with some $\epsilon > 0$, then $|z_{n + m}| > (1 + \epsilon)^m R \to \infty$ as $m \to \infty$.

Calculating, $$\begin{aligned} |z_{n+1}| &= |z_n^N+c| \\ &> \left||z_n^N| - |c|\right| \\ &= |z_n^N| - |c| \\ &> R^N - |c| \\ &\ge R^N - R \\ &= (R^{N-1} - 1) R \end{aligned}$$

Therefore, setting $$1 + \epsilon = R^{N-1} - 1$$ gives $$R = \sqrt[N-1]{2 + \epsilon}.$$ $\epsilon$ is arbitrarily small, so this gives bounds: $$R > \sqrt[N-1]{2} \ge |c|$$

That is, $$|z_n| > \sqrt[N-1]{2}$$ will escape to infinity, and the whole set is contained in the ball of radius $\sqrt[N-1]{2}$ centered on the origin.

# 3 Boundedness

See:

“Cross-sections of multibrot sets”, Line Baribeau, Thomas Ransford https://arxiv.org/abs/1701.05535

Relevant result:

If $|c| \le (N-1)/N^{N/(N-1)}$ then $|z_n| \le 1/N^{1/(N-1)}$, that is, $z_n$ remains bounded.

# 4 Fast Exponentiation

Simply multiplying by $z$ $N$ times is inefficient. Much better is exponentiation by squaring:

$$\begin{aligned} z^{2 N + 1} &= z^{2 N} \times z \\ z^{2 N} &= \left(z^N\right)^2 \end{aligned}$$

This takes $O(\log(N))$ operations instead of $O(N)$, which is a big improvement.

The recursive description gives the operations in the reverse order to which they need to be performed.

The execution opcodes can be captured in a table, or in unrolled inner loops of generated code. The opcodes for one iteration of $z \to z^N + c$ are $\cdot \times z$, $\cdot^2$, and $\cdot + c$.

# 5 Perturbation

Perturbing $z^N+c$ gives an expression with $O(N)$ terms: $$((Z+z)^N+(C+c)) - (Z^N+C) = c + \sum_{k=1}^N \begin{pmatrix} N \\ k \end{pmatrix} Z^{N-k} z^k$$ This is inefficient in terms of number of operations.

Images also can have glitches if care is not taken: the glitch test is no longer $|Z+z| < |z|$ but needs to be more like $|Z+z| < N |z|$ (to be verified).

For greater efficiency and robustness, combine with fast exponentiation: store the reference $Z$ before opcode step, that is, store $O(\log(N))$ values per iteration.

Then check and rebase pixel iterations using Zhuoran’s trick before each opcode step: whenever $|Z+z|<|z|$, set $z=Z+z$ and $Z=0$ (the latter by resetting the iteration index into the reference orbit; don’t reset the reference’s step index).

This works so easily because 0 is the only critical point, and $0 = 0^2 = z \times 0$ so the initial portion of the reference orbit is a sequence of $0$ steps in the first iteration until the first $c$ at the start of the second iteration. For non-zero or multiple critical points it would be more complicated.

# 6 Implementation

Example implementation:

git clone https://code.mathr.co.uk/fractal-bits.git
cd fractal-bits/mandelbrot-arbitrary-power
make
./znc >100.pgm
display 100.pgm

Browse source: znc.c.