Enumeration of Features  

Robert P. Munafo, 2010 Oct 21.



This is a description of how to determine the number of each different type of feature in the Mandelbrot Set.

These integer sequences can be found without using any numerical computation techniques, such as root finders (e.g. maxima's allroots or Mathematica's NRoots functions), orpixel counting surveys (such as was used to locate the largest islands).

In fact, the formulas below are fairly easy to prove if the following two properties have already been established:

The rest of the current discussion assumes the above properties as truth.

Mu-Atoms

We start by considering the lemniscates as polynomials set equal to zero, and solving them, i.e. "finding the roots". Each root gives the nucleus of some mu-atom. Since the nth lemniscate is of order 2n-1, it follows that for each period n there are 2n-1 roots.

However, a root of period 3 (for example) also shows up as a root of period 6, 9, etc. but we don't count it that way. It only counts as a root of period 3. So, from 2n-1 we must subtract the number of roots of all lower periods that are divisors of n. This gives the following formula for the number of Mu-Atoms of period n:

Na(n) = 2n-1 - Σ(f:(f<n) and (n≡0 mod f))Na(f)

where n≡0 mod f means "f is a divisor of n". The extra condition f < n is there to exclude f equal to n.

For example, when computing N6 we start with 25, and then subtract the values of N1, N2 and N3 because 1, 2 and 3 are divisors of 6.

Here are the first few values of the sequence:

N1=1, N2=1, N3=3, N4=6, N5=15, N6=27, N7=63, N8=120, N9=252, N10=495, N11=1023, N12=2010, N13=4095, N14=8127, N15=16365, N16=32640, N17=65535, N18=130788, N19=262143, N20=523770, N21=1048509, N22=2096127, N23=4194303, N24=8386440, N25=16777200, N26=33550335, N27=67108608, N28=134209530, N29=268435455, N30=536854005, N31=1073741823, ...

(This is Sloane's sequence A0740.)

Secondary Continental Mu-Atoms

There is one secondary continental mu-atom for each rational number between 0 and 1. The secondary continental mu-atoms of period n correspond to the rational numbers with n in the denominator. Because of this, the number of secondary continental mu-atoms is equal to Euler's Totient function:

Φ(n) = n - Σ(f:gcd(n,f)=1)1

That is, take n and subtract 1 for every number that is relatively prime to n. This sequence is Sloane's sequence A0010. It starts:

0, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12, 10, 22, 8, 20, 12, 18, 12, 28, 8, 30, ...

Because of period scaling, each mu-atom has children that have the same distribution as the secondary continental mu-atoms, but with scaled-up periods. From this, we can derive the formula for the number of continental mu-atoms of period n:

Nc(1) = 1 (special case)

Nc(n) = Σ(f:n≡0 mod f) [Nc(f) . Φ(n/f)]

This sequence (Sloane's A6874) starts:

1, 1, 2, 3, 4, 6, 6, 9, 10, 12, 10, 22, 12, 18, 24, 27, 16, 38, 18, 44, 36, 30, 22, 78, 36, 36, 50, 66, 28, 104, 30, ...

The Islands

Next we consider the number of island mu-molecules. So far we have a total number of mu-atoms, and a number of continental mu-atoms, for each period. All mu-atoms that are not continental are part of an island.

However, some of these mu-atoms are descendants of the seeds of the island mu-molecules. So, first we have to look at the relation between descendants in general (which includes continental descendants) and mu-molecule seeds (including the continent seed).

The number of mu-molecules is equal to the number of seeds, since each mu-molecule has one seed. Furthermore, every mu-atom is either a seed or a descendant, but not both. Therefore, we have this relation between mu-molecules and descendants:

Nm(n) = Na(n) - Nd(n)

Descendants

Number of descendants:

Nd(n) = Σ(f:n≡0 mod f) [Na(f).Φ(n/f)]

The sequence is Sloane's A6875, and starts:

0, 1, 2, 3, 4, 7, 6, 12, 12, 23, 10, 51, 12, 75, 50, 144, 16, 324, 18, 561, 156, 1043, 22, 2340, 80, 4119, 540, 8307, 28, 17521, 30, ...

Mu-Molecules

From this we get the values of Nm(n), which is Sloane's sequence A6876:

1, 0, 1, 3, 11, 20, 57, 108, 240, 472, 1013, 1959, 4083, 8052, 16315, 32496, 65519, 130464, 262125, 523209, 1048353, 2095084, 4194281, 8384100, 16777120, 33546216, 67108068, 134201223, 268435427, 536836484, 1073741793, ...

Mu-Atoms on the Real Axis

This calculation is unrelated to the others and is due to Rogers and Weiss (see reference below).

Nr(n) = (1/2n) Σ(d:(n≡0 mod d) and (d=1 mod 2)) [u(d)2n/d]

where "u(d)" is the Moebius function (Sloane's A8683), and the sum is over all odd divisors d, where 1 and n can be counted as divisors. So for example:

n=1: 1/2 (21/1) = 1
n=2: 1/4 (22/1) = 1
n=3: 1/6 (23/1 - 23/3) = 1
n=4: 1/8 (24/1) = 2
n=5: 1/10 (25/1 - 25/5) = 3
n=6: 1/12 (26/1 - 26/3) = 5
n=7: 1/14 (27/1 - 27/7) = 9
n=8: 1/16 (28/1) = 16
n=9: 1/18 (29/1 - 29/3) = 28
n=10: 1/20 (210/1 - 210/5) = 51
n=11: 1/22 (211/1 - 211/11) = 93
n=12: 1/24 (212/1 - 212/3) = 170
etc.

The sequence is:

1, 1, 1, 2, 3, 5, 9, 16, 28, 51, 93, 170, 315, 585, 1091, 2048, 3855, 7280, 13797, 26214, 49929, 95325, 182361, 349520, 671088, 1290555, 2485504, 4793490, 9256395, 17895679, 34636833, 67108864, 130150493, 252645135, 490853403, 954437120, 1857283155, ...

(Sloane's A0048)

Reference:

A. Weiss and T. D. Rogers, The number of orientation-reversing cycles in the quadratic map, CMS Conference Proc., Vol. 8, Amer. Math. Soc., Providence, 1987, pp. 703–711.


The functions in maxima

Here are each of the functions implemented in maxima.

Na(p) := block( [a:2^(p-1),f:0], for f in divisors(p) do if p>f then a : a - Na(f), return(a) );   phi(n) := block( [a:n,f:0], if n=1 then return(0), for f:1 thru n do if gcd(f,n)>1 then a : a - 1, return(a) );   Nc(n) := block( [a:0,d:1], if n=1 then return(1), for d in divisors(n) do if n>d then a : a + Nc(d) * phi(n/d), return(a) );   Nd(n) := block( [a:0,d:1], for d in divisors(n) do if n>d then a : a + Na(d) * phi(n/d), return(a) );   Nm(n) := Na(n) - Nd(n);   List31: makelist(i,i,1,31);   map(Na, List31);   map(phi, List31);   map(Nc, List31);   map(Nd, List31);   map(Nm, List31);


See also Exploring, largest mu-atoms, largest islands, Phi(N), and this page that lists various integer sequences.


revisions: 20070127 oldest on record; 20091029 update the maxima code; 20100405 describe prerequisites; 20101021 add note about numerical methods




From the Mandelbrot Set Glossary and Encyclopedia, by Robert Munafo, (c) 1987-2017.     Mu-ency index


Robert Munafo's home pages on HostMDS   © 1996-2017 Robert P. Munafo.
aboutcontact    mrob    mrob27    @mrob_27    mrob27
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. Details here.

This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2017 Feb 02. s.11