n 2n

k k+1

point x ∈ [ 2n , 2n ] which is mapped into itself. In other words, every interval

[ 2k , k+1 ] contains a point of period n for T . But any non-empty open interval

n 2n

I contains an interval of the type [ 2k , k+1 ] for su¬ciently large n. Hence T is

n 2n

chaotic.

From the above propositions it follows that L4 , Q’2 , and V are all chaotic.

3.4 The saw-tooth transformation and the shift

De¬ne the function S by

1 1

S(x) = 2x, 0 ¤ x < S(x) = 2x ’ 1, ¤ x ¤ 1.

, (3.4)

2 2

The map S is discontinuous at x = .5. However, we can ¬nd a continuous,

surjective map, h, such that h —¦ S = T —¦ h. In fact, we can take h to be T itself!

In other words we claim that

S

I ’’’ I

’’

¦ ¦

¦ ¦

T T

I ’’’ I

’’

T

commutes where I = [0, 1]. To verify this, we successively compute both T —¦ T

and T —¦ S on each of the quarter intervals:

0 ¤ x ¤ 0.25

T (T (x)) = T (2x) = 4x for

0 ¤ x ¤ 0.25

T (S(x)) = T (2x) = 4x for

= ’4x + 2

T (T (x)) = T (2x) for 0.25 < x < 0.5

= ’4x + 2 0.25 ¤ x < 0.5

T (S(x)) = T (2x) for

= T (’2x + 2) = 4x ’ 2 0.5 ¤ x ¤ 0.75

T (T (x)) for

= T (2x ’ 1) = 4x ’ 2 0.5 ¤ x ¤ 0.75

T (S(x)) for

= T (’2x + 2) = ’4x + 4 0.75 < x ¤ 1

T (T (x)) for

= T (2x ’ 1) = ’4x + 4 0.75 < x ¤ 1

T (S(x)) for

The h that we are using (namely h = T ) is not one to one. That is why our

diagram can commute even though T is continuous and S is not.

68 CHAPTER 3. CONJUGACY

1

0.9

0.8

0.7

0.6

S(x)

0.5

0.4

0.3

0.2

0.1

0

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

x

Figure 3.4: The discontinuous function S.

69

3.4. THE SAW-TOOTH TRANSFORMATION AND THE SHIFT

We now give an alternative description of the saw-tooth function which

makes it clear that it is chaotic. Let X be the set of in¬nite (one sided) se-

quences of zeros and ones. So a point of X is a sequence {a1 a2 a3 . . . } where

each each ai is either 0 or 1. However we exclude all points with a tail con-

sisting of in¬nite repeating 1 s. So a sequence such as {00111111111 . . .} is

excluded. We will identify X with the half open interval [0, 1) by assigning to

each point x ∈ [0, 1) its binary expansion, and by assigning to each sequence

a = {a1 a2 a3 . . . } the number

ai

h(a) = .

2i

The map h : X ’ [0, 1) just de¬ned is clear. The inverse map, assigning to

each real number between 0 and 1 its binary expansion deserves a little more

discussion: Take a point x ∈ [0, 1). If x < 1 the ¬rst entry in its binary

2

1

expansion is 0. If 2 ¤ x then the ¬rst entry in the binary expansion of x is 1.

Now apply S. If S(x) < 2 (which means that either 0 ¤ x < 1 or 1 ¤ x < 3 )

1

4 2 4

1

then the second entry of the binary expansion of x is 0, while if 2 ¤ S(x) < 1

then the second entry in the binary expansion of x is 1. Thus the operator S

provides the algorithm for the computation of the binary expansion of x. Let

7

us consider, for example, x = 16 . Then the sequence {S k (x)}, k = 0, 1, 2, 3, . . .

is

7 731

, , , , 0, 0, 0, . . . .

16 8 4 2

In general it is clear that for any number of the form 2k , after n ’ 1 iterations

n

1

of the operator S the result will be either 0 or 2 . So all S k (x) = 0, k ≥ n.

In particular, no in¬nite sequence with a tail of repeating 1™s can arise. We

see that the binary expansion of h(a) gives us a back, so we may (and shall)

identify X with [0, 1). Notice that we did not start with any independent notion

of topology or metric on X. But now that we have identi¬ed X with [0, 1), we

can use use standard notions of distance on the unit interval but expressed in

terms of properties of the sequences. For example, if the binary expansions of

x and y agree up to the kth position, then

|x ’ y| < 2’k .

So we de¬ne the distance between to sequences a and b to be 2’k where k is

the ¬rst place they do not agree. (Of course we de¬ne the distance from an a

to itself to be zero.)

The expression of S in terms of the binary representation is very simple:

S : .a1 a2 a3 a4 . . . ’ .a2 a3 a4 a5 . . . .

It consists of throwing away the ¬rst digit and then shifting the entire sequence