MSS Algorithm
2023 Mar 27.
A method for discovering a period cycle in a real quadratic iteration (like the Mandelbrot iteration for points on the real axis) given two other period cycles. It is described in a 1973 paper by Metropolis, Stein, and Stein and cited in several papers by Romera et al.
The algorithm can be performed on "strings" of letters R and L. Where P is taken to mean any sequence of R's and L's, they give the following definitions:
A solution of an iterated function with period k exists when fk(λ)=λ for some value λ. The pattern P of the solution consists of a sequence of letters L and/or R corresponding to each of the iterates of the function: the ith letter is L or R according to whether fi(λ) is less than or greater than λ (respectively).
The harmonic H of a pattern P is
PLP if P contains an odd number of Rs
PRP if P contains an even number of Rs
The antiharmonic A of a pattern P is
PRP if P contains an odd number of Rs
PLP if P contains an even number of Rs
At this point they make a note about how these transformations affect the "R-parity" of the pattern. R-parity is even if the pattern has an even number of R's and odd otherwise. Notice, for example, that the antiharmonic of "R" is "RRR", and the parity of both is odd; while the antiharmonic of "L" is "LLL", so the parity of both is even. Thus, the antiharmonic operation is "parity-preserving", while the harmonic operation is "parity-changing". They give two more definitions:
The H-extension of a pattern P is the pattern generated by iterating the harmonic construction applied j times to P, where j increases indefinitely.
The A-extension of a pattern P is the pattern generated by iterating the antiharmonic construction applied j times to P, where j increases indefinitely.
The MSS algorithm shows how to build up a complete list of solutions of periods up to some number k+n, starting with a complete list with periods only up to k. Thus, given a small starting list (say, just the patterns with periods 2 and 3) one can derive all patterns of any finite period.
Given two solutions λ1 < λ2 with period k1 and k2 respectively, and patterna P1 and P2 respectively, such that λ1 and λ2 are already known to be the only solutions of periods less than or equal to max(k1, k2) in the range [λ1, λ2]. Then there is at most one solution of period ks and pattern Ps, with ks>max(k1, k2). Ps is either the common leading subpattern of Hx(P1) and Ax(P2) or it is H(P1), depending on whether the period of that common leading subpattern is or is not less than 2k1. Hx() and Ax() represent the harmonic and antiharmonic extensions as defined above.
As an additional rule, if our set of patterns ends with anything of the form RLk-2 (corresponding to a solution of period k), we can append the pattern RLk-1 "for free" corresponding to a solution of period k+1.
Example Constructions
Let us start with two known solutions: R (k=2) and RL (k=3). We'll use the rules to build it up to the sequence of all solutions of periods 5 or less.
We can start by finding what to insert between R and RL:
P1 = R, k1 = 2 (odd R-parity)
P2 = RL, k2 = 3 (odd R-parity)
Hx(P1) = R L R R R L R ...
Ax(P2) = RL R RL R RL ...
common leading expression = RLRR, k* = 5
k* > 2k1 so we use H(P1):
→ RLR is the solution of minimal period between P1 and P2
and ks = 4
Now we have {R, RLR, RL}. To this we can use the "free rule" to append RLL (a solution with period 4) and we have {R, RLR, RL, RLL}.
Now we start at the beginning of the list looking for solutions of period 5. First, interpolate between R and RLR:
P1 = R, k1 = 2 (odd R-parity)
P2 = RLR, k2 = 4 (even R-parity)
Hx(P1) = R L R R R L R ...
Ax(P2) = RLR L RLR L RLR ...
common leading expression = RLR, k* = 4
k* = 2k1 so we again use H(P1):
→ RLR is the solution of minimal period between P1 and P2
and ks = 4.
Here we got a solution that we already knew about; this tells us that there are no higher-period solutions between R and RLR. Continuing:
P1 = RLR, k1 = 4 (even R-parity)
P2 = RL, k2 = 3 (odd R-parity)
Hx(P1) = RLR R RLR L RLR ...
Ax(P2) = RL R RL R RL ...
common leading expression = RLRR, k* = 5
k* < 2k1 so we use the common leading expression we just found:
→ RLRR is the solution of minimal period between P1 and P2
and ks = 5.
Continuing:
P1 = RL, k1 = 3 (odd R-parity)
P2 = RLL, k2 = 4 (odd R-parity)
Hx(P1) = RL L RL R RL ...
Ax(P2) = RLL R RLL R RLL ...
common leading expression = RLLR, k* = 5
k* < 2k1 so we use the common leading expression we just found:
→ RLLR is the solution of minimal period between P1 and P2
and ks = 5.
Finally, we can append RLLL "for free", and our list is {R, RLR, RLRR, RL, RLLR, RLL, RLLL}.
Applicability to the Mandelbrot Set
Metropolis et al. were considering the iteration of functions that are non-decreasing over values in an initial portion of their range, and non-increasing thereafter. The Mandelbrot iteration z2+c does the opposite (it decreases, then increases). All of their results apply, but the solutions appear in reverse order with all L's changed to R's and vice-versa. Also, Metropolis used the value 1/2 as their critical point, and did not include it in the list of iterates summarised by the sequence of L's and R's; but for the Mandelbrot set it is better to follow the style of Romera et al. and include the critical point as an initial letter C. With all these changes the list of 7 solutions of period 5 or less which we above showed to be {R, RLR, RLRR, RL, RLLR, RLL, RLLL} becomes {CLRRR, CLRR, CLRRL, CLR, CLRLL, CLRL, CL}. Each is the nucleus of a mu-atom and most of those are the cardioid component of an island mu-molecule. Here they are listed as they appear on the real axis, starting with the tip and going towards the right:
|
From the Mandelbrot Set Glossary and Encyclopedia, by Robert Munafo, (c) 1987-2024.
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 Apr 15.
s.27