# # Multibrot

Generalisation of Mandelbrot set to arbitrary power $$N$$.

$f_c(z) = z^N + c$

Here only integer $$N \ge 2$$ are considered.

## # 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.