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