Newsgroups: sci.fractals Subject: Re: Mandelbrot interior Date: 16 Dec 1996 06:14:17 GMT Organization: "University of Washington, Mathematics, Seattle" Message-ID: <592pbp$dff@nntp1.u.washington.edu> References: <32AD6BD1.2781E494@ic.ac.uk> <19961214003100.TAA00386@ladder01.news.aol.com> Keywords: symbolic dynamics, shift map, zeta function, entropy In article <19961214003100.TAA00386@ladder01.news.aol.com>, swarsmatt@aol.com (SWars Matt) writes: |> The dynamics of the set along the real axis are conjugate to |> those of the logistic map studied by Feigenbaum, so by Sarkovskii's |> theorem there are periodic points of all periods, and at the Feigenbaum |> point chaotic dynamics begin. In these points the orbit of the critical |> point (zero of course) never is attracted to a periodic point. For c in the interior of a lobe of the Mandelbrot set, x -> x^2 + c posseses a superattracting cycle of a period which depends on the lobe. The open intervals between the points of the cycle 0, f(0), ... f^p(0) = 0 can be taken as an "alphabet" and the itinerary of a "typical" x is then associated with an infinite sequence according to which intervals it passed through. The dynamical system defined by iterating x -> x^2 + c on its Julia set then turns out to be topologically conjugate to a "shift of finite type" (sft) which is defined by studying how these intervals are mapped to one another by f_c(x) = x^2 + c. This allows one to compute the entropy, the number of points of each period, etc., by standard methods of symbolic dynamics. Because the cycles are attracting, and because the method employs only topological features of how the intervals are mapped into one another, numerical inaccuracies in determining the precise values of the roots do no harm--- only the order in which x_1, x_2, ... x_p occur on the real line matters. An example should suffice to indicate how these methods work. First take f(x) = x^2 - 1.62541. (This value of c belongs to a "period five" lobe of the Mandlebrot set which sits over the real axis, slightly behind the Feigenbaum point). This has a superattracting five cycle which is approximately (0, -1.62541, 1.01655, -0.592041, -1.2749) Notice that the order in the cycle does not correspond to the order along the real line. Diagramatically, we have A B C D -----|-------|-------|---------|--------|----------- f(0) f^4(0) f^3(0) 0 f^2(0) This gives a four letter alphabet. Since f is continuous, we can see that f maps A onto D, B onto B union C, C onto A, D onto A union B. This gives a graph A <----- C ^ | ^ | | | | V | D ------> B / ^ |_| which defines a shift of finite type which has NO three cycles at all, but does have a five cycle ... CADBBC... and thus (by Sarkovski's ordering) a point of every period other than three. Here, the SFT is the space whose points are infinite sequences of letters A, B, C, D, where each sequence is required to satisfy the "transition constraints" given by the graph. Thus, part of one sequence might look like ... ADADBBCA ... This space can be given a metric in a standard way which makes the "shift map" (which simply shifts each sequence one space to the right) into a continuous map. Moreover, the shift map acting on the space of sequences defined by the graph (aka "the sft") is topologically conjugate to f acting on its Julia set (here a Cantor set which is a subset of the real line). This means that the "interesting" dynamical behavior of f is the same as that of the sft. (The "uninteresting" behavior of f involves the behavior of points not in the Julia set, which is qualitatively easy to describe, more or less by definition.) In particular, the topological entropy (a measure of the "unpredictability") and the number of points of each period (represented by a power series called the zeta function, which is in fact related to the famous Riemann zeta hypothesis) are the same for f acting on its Julia set and for the sft. In turns out that both the entropy and zeta function of the sft are easily computed from the adjacency matrix of the graph: A B C D A 0 0 0 1 M = B 0 1 1 1 C 1 0 0 0 D 1 1 0 0 The characteristic polynomial is det(t I - M) = t^4 - t^3 - t^2 + t - 1. On the other hand, the zeta function is 1 1 zeta(t) = -------------- = ------------------------ det(I - t M) 1 - t - t^2 + t^3 - t^4 Expanding log zeta(t) in a McLaurin series gives the number of points of each period log zeta(t) = log det(I - t M) = t + 3 (t^2/2) + 1 (t^3/2) + 7 (t^4/4) + 6 (t^5/5) + 15 (t^6/6) + 15 (t^7/7) + 31 (t^8/8) + ... That is, there is one fixed point, the sequence ...BBBBB..., two points of period two, ..ADAD.. and ..DADA.. (plus the fixed point, which also has period two), no point of period three (except the fixed point), four points of period four (plus the two points of the two-cycle and the fixed point), and so forth. In other words, in addition to the superattracting five cycle we started with, f(x) = x^2 - 1.62541 also has an infinite number of repelling cycles, specifically one fixed point, one two cycle, no three cycles, one four cycle, two six cycles, two seven cycles, etc. You can verify that this is correct by examining the graph and looking for cycles. Converting between the number of p-cycles and the number of points of period p can be systematized using the Moebius inversion formula. The topological entropy turns out to be log lambda, where lambda is the largest eigenvalue of the characteristic equation, in this case about 1.51288. Because M^6 has all positive entries, we also know that this sft is "topologically mixing", a strong property which implies "topological transitivity". Since every sft has sensitive dependence on initial conditions and dense periodic points, a topologically transitive shift is chaotic according to the definition proposed by Devaney. It turns out that the sft defined as above by a graph is transitive iff the graph is transitive in the sense that you can get from any vertex to any other vertex. For a given p, it is easy (in principle) to determine the c values corresponding to superattracting cycles of period p, one of whose elements is the origin. For example, for p=3, set f_c[f_c[f_c[0]]] = 0 This can be solved numerically to find the real root -1.75488. This degree of accuracy is enough to determine the three cycle (0, -1.755, 1.325) to sufficient degree of accuracy to obtain the diagram A B ---|--------|---------|----- f(0) 0 f^2(0) This leads to the graph <------ A -----> B / ^ |_| which defines an sft called "the golden mean shift", because its entropy is log 1.61803. The entropy and zeta function for this sft can be computed from the adjacency matrix as above. This sft is conjugate to f_c(x) = x^2 + c acting on its Julia set, for c in the "period three" lobe of the Mandlebrot set. (This lobe appears as a "bug" sitting about halfway along the "tail".) In this way (a program such as Mathematica is helpful here), you can explore how the sft's change as you move down the real line, starting from the trivial one point sft defined by the graph A / ^ |_| obtained from the two cycle (0,-1) associated with x^2 - 1, which belongs to the "period two" lobe attached to main cardiod. As you move along you come next to a period four lobe. We now have the four cycle (0, -1.3107, 0.4072, -1.145) associated with x^2 - 1.3107. This gives the diagram A B C ---|--------|-----|------|----- f(0) f^3(0) 0 f^2(0) which gives the graph B ---> A <---- C / ^ ----> |_| This defines an intransitive sft with entropy zero. Continuing along the period doubling cascade, we find that the graphs become more complicated but the entropy remains zero until the Feigenbaum point at about c = -1.46692, where the entropy goes positive with the onset of chaos. For instance, x^2 - 1.47601 has a superattracting six-cycle and is conjugate to an sft with entropy about log 1.27. Continuing, we find that the entropy increases monotonically, remaining constant on the "periodic windows". A typical such periodic window begins with the golden mean shift at about x^2 - 1.75488. This is the first in a cascade of lobes with associated intransitive sft's whose entropies agree with that of x^2 - 1.75488, namely log 1.61803. Eventually, at the tip of the tail of the Mandlebrot set (c = -2), we obtain the "full two shift" which has entropy log 2. To sum up--- life inside the Mandlebrot set is indeed interesting. Hope this has been intriguing! If so, here are some references. For an introduction to sft's defined by graphs, entropy, zeta functions, full shifts, and more, see the recent undergraduate textbook Author: Lind, Douglas A. Title: An introduction to symbolic dynamics and coding / Douglas Lind, Brian Marcus. Pub. Info.: Cambridge ; New York : Cambridge University Press, 1995. LC Subject: Differentiable-dynamical-systems. Coding-theory. For more on Julia sets, superattracting and repelling cycles, the Mandelbrot set, interval maps and graphs, etc., see Title: Chaos and fractals : the mathematics behind the computer graphics / Robert L. Devaney and Linda Keen, editors ; [authors] Kathleen T. Alligood ... [et al.]. Pub. Info.: Providence, RI : American Mathematical Society, 1989, c1987. LC Subject: Computer-graphics -- Mathematics. Fractals. For a more sophisticated analysis of interval maps, the basic reference is a famous paper by Milnor and Thurston, "On Iterated Maps of the Interval I", which was written in 1977 but unpublished for many years until it finally appeared in the book Title: Dynamical systems : proceedings of the special year held at the University of Maryland, College Park, 1986-87 / J.C Alexander, ed. Pub. Info.: Berlin ; New York : Springer-Verlag, 1988. LC Subject: Topological-dynamics -- Congresses. Ergodic-theory -- Congresses. For Moebius inversion see almost any combinatorics text, for instance Author: Cameron, Peter J. (Peter Jephson), 1947-. Title: Combinatorics : topics, techniques, algorithms / Peter J Cameron. Pub. Info.: Cambridge ; New York : Cambridge University Press, 1994. LC Subject: Combinatorial-analysis. The graphical method employed here was introduced in the very readable article P. D. Straffin, Jr., "Periodic points of continuous functions", Mathematics Magazine 51 (1978), 99-105. More recent developments may be found in the book Author: Alseda, L. Libre, M. Misiureqicz, M. Title: Combinatorial Dynamics and Entrophy in Dimensions One Publisher: World Scientific Publishing Company, Incorporated Year: 1993 Series: Advanced Series in Nonlinear Dynamics Pages: 344p. ISBN/Price: 981-02-1344-1 Cloth Text $74.00 Subj (BIP): ENTROPY. COMBINATORIAL-ANALYSIS Chris Hillman