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 f^{k}(λ)=λ 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 f^{i}(λ) 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 "Rparity" of the pattern. Rparity 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 "paritypreserving", while the harmonic operation is "paritychanging". They give two more definitions:
The Hextension of a pattern P is the pattern generated by iterating the harmonic construction applied j times to P, where j increases indefinitely.
The Aextension 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 k_{1} and k_{2} respectively, and patterna P_{1} and P_{2} respectively, such that λ_{1} and λ_{2} are already known to be the only solutions of periods less than or equal to max(k_{1}, k_{2}) in the range [λ_{1}, λ_{2}]. Then there is at most one solution of period k_{s} and pattern P_{s}, with k_{s}>max(k_{1}, k_{2}). P_{s} is either the common leading subpattern of Hx(P_{1}) and Ax(P_{2}) or it is H(P_{1}), depending on whether the period of that common leading subpattern is or is not less than 2k_{1}. 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 RL^{k2} (corresponding to a solution of period k), we can append the pattern RL^{k1} "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:
P_{1} = R, k_{1} = 2 (odd Rparity)
P_{2} = RL, k_{2} = 3 (odd Rparity)
Hx(P_{1}) = R L R R R L R ...
Ax(P_{2}) = RL R RL R RL ...
common leading expression = RLRR, k* = 5
k* > 2k_{1} so we use H(P_{1}):
→ RLR is the solution of minimal period between P_{1} and P_{2}
and k_{s} = 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:
P_{1} = R, k_{1} = 2 (odd Rparity)
P_{2} = RLR, k_{2} = 4 (even Rparity)
Hx(P_{1}) = R L R R R L R ...
Ax(P_{2}) = RLR L RLR L RLR ...
common leading expression = RLR, k* = 4
k* = 2k_{1} so we again use H(P_{1}):
→ RLR is the solution of minimal period between P_{1} and P_{2}
and k_{s} = 4.
Here we got a solution that we already knew about; this tells us that there are no higherperiod solutions between R and RLR. Continuing:
P_{1} = RLR, k_{1} = 4 (even Rparity)
P_{2} = RL, k_{2} = 3 (odd Rparity)
Hx(P_{1}) = RLR R RLR L RLR ...
Ax(P_{2}) = RL R RL R RL ...
common leading expression = RLRR, k* = 5
k* < 2k_{1} so we use the common leading expression we just found:
→ RLRR is the solution of minimal period between P_{1} and P_{2}
and k_{s} = 5.
Continuing:
P_{1} = RL, k_{1} = 3 (odd Rparity)
P_{2} = RLL, k_{2} = 4 (odd Rparity)
Hx(P_{1}) = RL L RL R RL ...
Ax(P_{2}) = RLL R RLL R RLL ...
common leading expression = RLLR, k* = 5
k* < 2k_{1} so we use the common leading expression we just found:
→ RLLR is the solution of minimal period between P_{1} and P_{2}
and k_{s} = 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 nondecreasing over values in an initial portion of their range, and nonincreasing thereafter. The Mandelbrot iteration z^{2}+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 viceversa. 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 muatom and most of those are the cardioid component of an island mumolecule. 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) 19872024.
Muency 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