Enumeration of Features
Robert P. Munafo, 2023 Jul 23.
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), or pixel 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 Farey addition property : if two mu-atoms are at internal angles a/b and c/d, with b relatively prime to d, and if the lowest-period mu-atom between them is e/f, and if e<a and e<c, then a+c=e and b+d=f. For a formal description of this, see the link in the Robert Devaney article.
- Period scaling : The mu-unit belonging to a hyperbolic component of period p possesses a full set of higher period components of periods that are all multiples of p. This is mentioned as property 2.3 in the 1986 article by John Milnor.
The rest of the current discussion assumes the above properties as truth.
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, ...
All Continental Mu-Atoms
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, ...
In 2022 Schinella d’Souza wrote a paper on this enumeration, going into more detail for specific subsequences, numbers, e.g. when n is a product of two distinct primes.
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)
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, ...
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
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, ...
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.
In addition to Farey addition which has its own article, see the Lavaurs algorithm article for an algorithm that allows finding all the mu-atoms along with some information about their positions in relation to each other.
Appendix: 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);
revisions: 20000206 oldest on record; 20070127 add maxima code; 20091029 update the maxima code; 20100405 describe prerequisites; 20101021 add note about numerical methods; 20230615 link to Lavaurs algorithm; 20230723 link to d’Souza paper
From the Mandelbrot Set Glossary and Encyclopedia, by Robert Munafo, (c) 1987-2023.
This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2023 Jul 23. s.27