# Relationship between symbolic dynamics and chaotic map : confusion and basics

From concepts of symbolic dynamics which I am trying to understand from the document https://web.math.rochester.edu/people/faculty/edummit/docs/dynamics_3_chaotic_dynamics.pdf

and using notations from this document,

Questions :

• Can somebody please explain with a commutative diagram as given on Page 10 and page 11, what is the meaning of conjugacy and what is going on?
• It isn't very clear which you are having trouble with. I'm guessing you are trying to understand the chaos paper in order to understand the compression and encryption paper?
– hkr
Apr 5 '17 at 13:57
• @hkr: I am trying to understand the connection between the itenaray map $S$ in symbolic dynamics theory and its inverse $S^{-1}$ in symbolic dynamics with the map $f^{-1}$ applied in the paper. The source of confusions are (1) that $S^{-1}$ and $f^{-1}$ seem to be doing the same thing which is generating the chaotic numeric sequence based on the symbolic sequence.
– SKM
Apr 5 '17 at 16:59
• (2) Since, these 2 maps appear to be doing the same thing, then can we say using conjugacy that $\sigma^n = S o f^n o S^{-1}$ where $S$ is the symbolic sequence called as the itenarary, $S^{-1}$ (= $f^{-1}$, don't know) adn $f^n(.)$ is the chaotic map. Then we have $\sigma^n$ to be chaotic based on theory of symbolic dynamics.
– SKM
Apr 5 '17 at 16:59
• That isn't how conjugacy works but now I understand your problem. BTW, the Latex function \circ is used for doing the composition symbol.
– hkr
Apr 5 '17 at 20:04

First let's start with the commutative diagram, and the definition of conjugacy. We have two dynamical systems: $f$ which is a system on space $X$, and $g$ which is a dynamical system on space $Y$. We need a way to decide that they have enough similarities to be able to infer things about one by examining the other. So the method is to find a homeomorphism between the two spaces such that you can take a point in space $X$ over to a point in space $Y$, operate on it with dynamical system $g$, bring it back again, and you will be where you would have been if you just stayed in $X$ and operated on it with system $f$. Call the homeomorphism $h$. Then that whole process is captured by the commutative diagram shown in the first paper you cited, namely $$\require{AMScd} \begin{CD} X @>{f}>> X\\ @VV{h}V @VV{h}V \\ Y @>{g}>> Y \end{CD}$$ Follow the arrows around the diagram, going from $X \rightarrow X$ with $f$ is the same as going over to $Y$ and back, which can be read off the diagram as $f = hgh^{-1}$, which can also be written as $fh = hg$.

Now to the theorem in the tutorial, "Conjugacy of Shift Map and Quadratic Map," on p.14, the proof does just this. First it shows that $S$ does function as $Sq_c = \sigma S$, and then it proves that $S$ is a homeomorphism (injective, surjective, and continuous with continuous inverse). So it takes each point in the Cantor set to a string of symbols, and shows that one iteration of the quadratic map on the Cantor set is the equivalent (under conjugation) of a shift on two symbols. More importantly for the Hadoop paper you're trying to understand, it shows each string of symbols can be looked at as an address in the Cantor set, on the real line.

Now to the other paper. The tent map is used to generate a chaotic string because it is very simple. For an explanation of this, please look at the Wikipedia article for the Logistic map. They use a parabola there, it can be simplified to just a tent map which is faster computationally. Especially look at the animations and the other diagrams.

The process of using a point on the real line to encode information and compress it, treating the information as an expansion of a real number is called arithmetic coding if you add symbols together, Huffman coding if you put one after another, and there are other encodings. It compresses the information by using the statistically best symbols for the most frequent strings instead of fixed length symbols for all of them.

What the paper is doing is encrypting at the same time by treating the string as a position not on the real line, but on a specially designed Cantor set that the two communicators know the parameters to, one could have designed such a system with your quadratic map on the classical Cantor set.

Is there a conjugation between that set up and the shift map? Yes, you will find the conjugacy set up at the end of the Wikipedia article I referenced. Each starting condition maps to (in general) to a non-repeating set of binary digits. What the paper does is take that string as being the information and encode it as the initial condition, since that is the way arithmetic encoding works and therefore there is a fast algorithm for it.

Hope this helps.

• $f$ appears in such a diagram in the same place as $q_c$. An "itinerary function", similar to $S$ would conjugate it with $\sigma$. This means, as I said in my answer, that the scheme outlined in the paper is actually a (different) conjugation map. The point is that maps like $S$ can be looked at as encoding strings (the $d_0d_1\cdots d_n \cdots$ in your tutorial) into positions on $\mathbb R$, which are shorter strings, but you need to know which tent map did the encoding, so it is encrypted to those who don't know.
– hkr
Apr 6 '17 at 13:33