Chaos

Subsection 2.8.2 Chaos

We can now prove three claims about the doubling map that, together, assert that the doubling map displays some of the essential features of chaos. First, we'll need to state and prove a lemma.

Lemma 2.36.

Suppose that

\begin{equation*} x=0_{\dot 2}b_1 b_2 b_3 \cdots \: \text{ and } \: y=0_{\dot 2}b_1' b_2' b_3' \cdots \end{equation*}

are elements of \(H\) that satisfy \(b_1\neq b_1'\) but \(b_2=b_2'\text{.}\) Then \(|x-y| \geq 1/4\text{.}\)

Proof.

Computing the difference using the binary representations, taking into account that the terms disagree in the first spot and agree in the second, and finally applying the reverse triangle inequality, we get

\begin{align*} |x-y| &= \left|\sum_{i=1}^{\infty} \frac{b_i-b_i'}{2^n}\right| = \left|\pm\frac{1}{2} + \sum_{i=3}^{\infty} \frac{b_i-b_i'}{2^n}\right|\\ &\geq \left|\left|\pm\frac{1}{2}\right|-\left|\sum_{i=3}^{\infty} \frac{b_i-b_i'}{2^n}\right|\right| \geq \left|\frac{1}{2} - \frac{1}{4}\right| = \frac{1}{4}. \end{align*}

A geometric interpretation of this lemma is as follows. The fact that the two points disagree in the first spot means that they cannot lie in the same half of \(H\text{.}\) The fact that they do agree in the second spot means that they lie in the same quarter relative to their half, as shown in Figure 2.37. Clearly, any two such points cannot be within \(1/4\) of one another.

Figure 2.37. Possible positions of points in lemma Lemma 2.36

Claim 2.38. Sensitive dependence on initial conditions.

For every \(x\in H\) and for every \(\varepsilon > 0\text{,}\) there is some \(y\in H\) and an \(n\in\mathbb N\) such that \(|x-y| < \varepsilon\) yet \(|d^n(x)-d^n(y)| \geq 1/4\text{.}\)

Proof.

Choose \(n\in\mathbb N\) large enough so that \(1/2^n < \varepsilon\text{.}\) Now suppose that \(x\in H\) has binary expansion

\begin{equation*} x = 0_{\dot 2}b_1 b_2\cdots b_n b_{n+1} b_{n+2} \cdots. \end{equation*}

Define \(y\in H\) so that

\begin{equation*} y = 0_{\dot 2}b_1 b_2\cdots b_n (1-b_{n+1}) b_{n+2} \cdots. \end{equation*}

That is, the bits of \(y\) agree with those of \(x\) in the first \(n\) spots, disagree with \(x\) in the \((n+1)^{\text{st}}\) spot, and finally agree with \(x\) again in the \((n+2)^{\text{nd}}\) spot.

Then, the numbers \(d^n(x)\) and \(d^n(y)\) satisfy the hypotheses of lemma Lemma 2.36, thus \(|d^n(x)-d^n(y)| \geq 1/4\text{.}\)

Claim 2.39. Denseness of periodic orbits.

For every open interval \(I\subset H\text{,}\) there is some periodic orbit with an element in \(I\text{.}\)

Proof.

Let \(x\in I\) and choose \(n\in\mathbb N\) large enough so that

\begin{equation*} (x,x+1/2^n)\subset I. \end{equation*}

Now suppose that

\begin{equation*} x = 0_{\dot 2}b_1 b_2\cdots b_n\cdots. \end{equation*}

Then,

\begin{equation*} \hat{x} = 0_{\dot 2}\overline{b_1 b_2\cdots b_n} \end{equation*}

is a periodic point in \(I\text{.}\)

Claim 2.40. A dense orbit.

There is a point \(x\in H\) with the property that, for every open interval \(I\subset H\text{,}\) there is some iterate of \(x\) in \(I\text{.}\)

Proof.

We'll define \(x\) by specifying its binary expansion. We begin by writing down all possible finite binary strings:

\begin{equation*} 0,\,1, \:\: 00,\,01,\,10,\,11, \:\: 000,\,001,\,010,\,011,\,100,\,101,\,110,\,111,\ldots \end{equation*}

We then concatenate these to obtain the binary representation of \(x\)

\begin{equation*} x = 0_{\dot 2}0\,1\,00\,01\,10\,11\,000\,001\,010\,011\,100\,101\,110\,111\ldots \end{equation*}

Now, let \(I\subset H\) be an open interval. We claim that there is some iterate of \(x\) in \(I\text{.}\) To see that, let \(L\) denote the length of \(I\) and choose \(n\in\mathbb N\) large enough so that

\begin{equation*} \frac{1}{2^n} < \frac{1}{2}L. \end{equation*}

Let \(i\) be the smallest integer such that \(i/2^n \in I\text{.}\) Note that we must also have \((i+1)/2^n \in I\text{.}\) Thus, the dyadic interval \([i/2^n,(i+1)/2^n)\) is wholly contained in \(I\) and the first \(n\) bits of every point in that interval agree with \(i/2^n\text{.}\) So, let

\begin{equation*} \frac{i}{2^n} = 0_{\dot 2}b_1 b_2 \cdots b_n \end{equation*}

and note that, by construction, the string \(b_1 b_2 \cdots b_n\) appears somewhere in the binary expansion of \(x\text{.}\) Thus, we can apply the doubling function to the point \(x\) some number, say \(m\text{,}\) times to obtain

\begin{equation*} d^m(x) = 0_{\dot 2}b_1 b_2 \cdots b_n \cdots. \end{equation*}

The number \(d^m(x)\) is then an iterate of \(x\) that lies in \(I\text{.}\)

While there is no truly universally accepted definition of chaos, claims Claim 2.38, Claim 2.39, and Claim 2.40 are generally agreed to express some of the essential features of chaos. We might think of them as representing:

Instability,
Structure, and
Indecomposability