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.

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 2^n-1, it follows that for each period n there are 2^n-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 2^n-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:

N_a(n) = 2^n-1 - Σ_{(f:(f<n) and (n≡0 mod f))}N_a(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 N₆ we start with 2⁵, and then subtract the values of N₁, N₂ and N₃ because 1, 2 and 3 are divisors of 6.

Here are the first few values of the sequence:

N₁=1, N₂=1, N₃=3, N₄=6, N₅=15, N₆=27, N₇=63, N₈=120, N₉=252, N₁₀=495, N₁₁=1023, N₁₂=2010, N₁₃=4095, N₁₄=8127, N₁₅=16365, N₁₆=32640, N₁₇=65535, N₁₈=130788, N₁₉=262143, N₂₀=523770, N₂₁=1048509, N₂₂=2096127, N₂₃=4194303, N₂₄=8386440, N₂₅=16777200, N₂₆=33550335, N₂₇=67108608, N₂₈=134209530, N₂₉=268435455, N₃₀=536854005, N₃₁=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:

N_c(1) = 1 (special case)

N_c(n) = Σ_{(f:n≡0 mod f)} [N_c(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.

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:

N_m(n) = N_a(n) - N_d(n)

Descendants

Number of descendants:

N_d(n) = Σ_{(f:n≡0 mod f)} [N_a(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 N_m(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).

N_r(n) = (1/2n) Σ_{(d:(n≡0 mod d) and (d=1 mod 2))} [u(d)2^n/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 (2^1/1) = 1
n=2: 1/4 (2^2/1) = 1
n=3: 1/6 (2^3/1 - 2^3/3) = 1
n=4: 1/8 (2^4/1) = 2
n=5: 1/10 (2^5/1 - 2^5/5) = 3
n=6: 1/12 (2^6/1 - 2^6/3) = 5
n=7: 1/14 (2^7/1 - 2^7/7) = 9
n=8: 1/16 (2^8/1) = 16
n=9: 1/18 (2^9/1 - 2^9/3) = 28
n=10: 1/20 (2^10/1 - 2^10/5) = 51
n=11: 1/22 (2^11/1 - 2^11/11) = 93
n=12: 1/24 (2^12/1 - 2^12/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.

Related Algorithms

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);

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

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

Mu-ency main page — index — recent changes — DEMZ

This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2023 Jul 23.

s.27