Editing Dyadic transformation (section)

==Periodicity and non-periodicity==
Because of the simple nature of the dynamics when the iterates are viewed in binary notation, it is easy to categorize the dynamics based on the initial condition:

If the initial condition is [[irrational number|irrational]] (as [[almost all]] points in the unit interval are), then the dynamics are non-periodic—this follows directly from the definition of an irrational number as one with a non-repeating binary expansion. This is the chaotic case.

If ''x''<sub>0</sub> is [[rational number|rational]] the image of ''x''<sub>0</sub> contains a finite number of distinct values within [0,&thinsp;1) and the [[orbit (dynamics)|forward orbit]] of ''x''<sub>0</sub> is eventually periodic, with period equal to the period of the [[Binary numeral system|binary]] expansion of ''x''<sub>0</sub>.  Specifically, if the initial condition is a rational number with a finite binary expansion of ''k'' bits, then after ''k'' iterations the iterates reach the fixed point 0;
if the initial condition is a rational number with a ''k''-bit transient (''k''&nbsp;≥&nbsp;0) followed by a ''q''-bit sequence (''q''&nbsp;>&nbsp;1) that repeats itself infinitely, then after ''k'' iterations the iterates reach a cycle of length&nbsp;''q''. Thus cycles of all lengths are possible.

For example, the forward orbit of 11/24 is:

: <math>\frac{11}{24} \mapsto \frac{11}{12} \mapsto \frac{5}{6} \mapsto \frac{2}{3} \mapsto \frac{1}{3} \mapsto \frac{2}{3} \mapsto \frac{1}{3} \mapsto \cdots, </math>

which has reached a cycle of period 2.  Within any subinterval of [0,&thinsp;1), no matter how small, there are therefore an infinite number of points whose orbits are eventually periodic, and an infinite number of points whose orbits are never periodic. This sensitive dependence on initial conditions is a characteristic of [[list of chaotic maps|chaotic maps]].

===Periodicity via bit shifts===
The periodic and non-periodic orbits can be more easily understood not by working with the map <math>T(x)=2x\bmod 1</math> directly, but rather with the [[bit shift]] map <math>T(b_0,b_1,b_2,\dots) = (b_1, b_2,\dots)</math> defined on the [[Cantor space]] <math>\Omega=\{0,1\}^\mathbb{N}</math>.

That is, the [[homomorphism]]
:<math>x=\sum_{n=0}^\infty \frac{b_n}{2^{n+1}}</math>
is basically a statement that the Cantor set can be mapped into the reals. It is a [[surjection]]: every [[dyadic rational]] has not one, but two distinct representations in the Cantor set. For example, 
:<math>0.1000000\dots = 0.011111\dots</math>
This is just the binary-string version of the famous [[0.999...|0.999... = 1]] problem. The doubled representations hold in general: for any given finite-length initial sequence <math>b_0,b_1,b_2,\dots,b_{k-1}</math> of length <math>k</math>, one has
:<math>b_0,b_1,b_2,\dots,b_{k-1},1,0,0,0,\dots = b_0,b_1,b_2,\dots,b_{k-1},0,1,1,1,\dots</math>
The initial sequence <math>b_0,b_1,b_2,\dots,b_{k-1}</math> corresponds to the non-periodic part of the orbit, after which iteration settles down to all zeros (equivalently, all-ones).

Expressed as bit strings, the periodic orbits of the map can be seen to the rationals. That is, after an initial "chaotic" sequence of <math>b_0,b_1,b_2,\dots,b_{k-1}</math>, a periodic orbit settles down into a repeating string <math>b_k,b_{k+1},b_{k+2},\dots,b_{k+m-1}</math> of length <math>m</math>.  It is not hard to see that such repeating sequences correspond to rational numbers. Writing
:<math>y = \sum_{j=0}^{m-1} b_{k+j}2^{-j-1}</math>
one then clearly has
:<math>\sum_{j=0}^\infty b_{k+j}2^{-j-1} = y\sum_{j=0}^\infty 2^{-jm} = \frac{y}{1-2^{-m}}</math>
Tacking on the initial non-repeating sequence, one clearly has a rational number. In fact, ''every'' rational number can be expressed in this way: an initial "random" sequence, followed by a cycling repeat.  That is, the periodic orbits of the map are in one-to-one correspondence with the rationals.

This phenomenon is note-worthy, because something similar happens in many chaotic systems. For example, [[geodesic]]s on [[compact space|compact]] [[manifold]]s can have periodic orbits that behave in this way.

Keep in mind, however, that the rationals are a set of [[measure zero]] in the reals. [[Almost all]] orbits are ''not'' periodic! The aperiodic orbits correspond to the irrational numbers. This property also holds true in a more general setting. An open question is to what degree the behavior of the periodic orbits constrain the behavior of the system as a whole.  Phenomena such as [[Arnold diffusion]] suggest that the general answer is "not very much".