The following three exercises deal with the analog of the shift map and the sequence space for sequences that have more than two possible entries, the space of sequences of N symbols.
The following exercises deal with the function
T(x)=
{ 3x for x <= 1/2
{ 3x-3 for x > 1/2
10) Find the fixed points for T. What is the ternary expansion of these points?
x=0 has ternary expansion 0.00000
and
x=3/4 has ternary expansion 0.202020202020repeating
To see why this is true recall from the example on page 77 of the text that
1/4 has ternary expansion .020202020202repeating so all we need to do
is multiply this quantity be 3 which effects the ternary expansion by shifting
the ternary point one place to the right.
11)Show that 3/13 and 3/28 lie on 3-cylcles for T.
T(3/13)=3(3/13)=9/13
T(9/13)=3-3(9/13)=12/13
T(12/13)=3-3(12/13)=3/13
and
T(3/28)=3(3/28)=9/28
T(9/28)=3(9/28)=27/28
T(27/28)=3-3(27/28)=3/28
12) Show that if x is in (1/3,2/3), then T^n(x)-> negative infinity as n-> infinity.
Note that T is stricly increasing on (1/3,1/2] and stricly decreasing on
[1/2,2/3).Therefore,
1/3 < x <= 1/2 -> T(1/3) < T(x) <= T(1/2) -> 1 < T(x) <= 3/2
and
1/2 < x <= 2/3 -> T(1/2) < T(x) <= T(2/3) -> 3/2 >= T(x) > 1.
So, any way you look at it 1< T(x) <=3/2 and exercise 9 shows that
if x > 1 then T^n(x)-> negative infinity as n->infinity
13) Show that if x is in (1/9,2/9) or x is in (7/9,8/9) then T^n(x)-> negative infinity as n-> infinity.
The solution to this problem requires some knowledge of T^2(x).
Note that an explicit formula for T^2(x) is given by,
T^2(x)=
{ 9x for x <= 1/6
{ 3-9x for 1/6 <= x < 1/2
{ 9x-6 for 1/2 <= x < 5/6
{ 9-9x for x >= 5/6
T^2 is strickly increasing on (1/9,1/6] and strickly decreasing on [1/6,2/9).
Therefore,
1/9 < x <= 1/6 -> T^2(1/9) < T^2(x) <= T^2(1/6) -> 1 < T^2(x) <= 3/2
and
1/6 < x <= 2/9 -> T^2(1/6) < T^2(x) <= T^2(2/9) -> 3/2 >= T^2(x) > 1
So if x is in (1/9,2/9) then T^2(x) is in (1,3/2] and by exercise 9 if follows
that T^n(x) -> negative infinity as n -> infinity.
14) Let Gamma={x in [0,1] | T^n(x) is in [0,1] for all n}. Prove that Gamma=K, the Cantor middle-third set.
Let x=0.a1a2a3... and partition the unit interval so that [0,1]=[0,1/3]U(1/3,2/3)U[2/3,1]. One of the key ides of the proof is that the value of a1 alone determines which of these three intervals contains x. If a1=0, then x is in [0,1/3]; if a1=1, then x is in (1/3,2/3); and if a1=2, then x is in [2/3,1]. At first glance, the boundary points appear to be exceptions to this general rule since 1/3=0.1000... and 2/3=0.1222..., but even these may be written as 0.0222... and 0.2000..., respectively.
Another key idea is the important result of Exercise 12: all x in the interval (1/3,2/3) have orbits which shoot of to negative infinity. But these are precisely those x whose first ternary digit is equal to 1. Indeed, the claim is that any x having some ternary digit equal to 1 has an orbit which escapes to negative infinity! This is true because
T(x)=
{ 0.a2a3a4... for 0<= x <= 1/2
{ 0.b2b3b4... for 1/2 <= x <= 1
where
bi=
{ 0 if a1=2
{ 1 if a1=1
{ 2 if a1=0
Note that this definition of T is unambiguous at x=1/2 which itself has ternary expansion 0.111...
Now the proof that Gamma=K goes as follows.
Suppose x is in Gamma=K. then the ternary expansion of x can
not have a 1 in it, for if it did,T^n(x) is in (1/3,2/3) for some n
and the orbit would excape to negative infinity. Thus, x is also in
K. Conversely, suppose x is in K. Then the ternary expansion of x
again has no 1s. Thus, T^n(x) is not in (1/3,2/3) for all n and so the
orbit of x can not escape. Hence, x is in Gamma.
15) Suppose x is in Gamma and has ternary expansion 0.a1a2a3... What is the ternary expansion fo T(x)? Be careful: there are two very different cases!
By the combined results of exercises 9 and 12, we know that either x is in [0,1/3] or x is in [2/3,1] If x is in [0,1/3], then its leading ternary digit is 0; otherwise, it's 2. These are the two cases that must be dealt with.
If a1=0, then T(x)=3x. As we've already seen in exercise 10, multiplying a ternary expansion by 3 simply shifts the ternary point one place to the right.
If a1=2, the T(x)=3-3x=3(1-x). Finally, if x=0.a1a2a3..., then 1-x=0.b1b2b3... where,
bi=
{ 0 if a1=2
{ 2 if a1=0
Putting all these facts together, we have that
T(x)=
{ 0.a2a3a4... if a1=0
{ 0.b2b3b4... if a1=2
for x in Gamma.
Page 111:
1. List all cycles of prime period 4 for the shift map.
There are three cycles, or twelve points, of prime period 4 for the shift map:
3. Compute d[s, t] where s =(100...) and t =(010...).
6. Give an example of a sequence midway between (000...) and (111...). Give a second such example. Are there any other such points? Why or why not?
One of the two points midway between (000...) and (111...) is (0111...) since
The following three exercises deal with the analog of the shift map and the sequence space for sequences that have more than two possible entries, the space of sequences of N symbols.
10. Let SIGMA_N denote the space of sequences whose entries are the positive integers 0,1,...,N-1, and let o_N be the shift map on SIGMA_N. For elements of SIGMA_N s and t, let the distance d_N be defined as in the book on page 112. Prove that ]d_N] is a metric on SIGMA_N.
The function is obviously nonnegative for all s and t in SIGMA_N since |s_i - t_i| is nonnegative for all i. Also, ]d_N][s, t]=0 only if |s_i - t_i|=0 for every i, which occurs only if s=t. Symmetry follows from the fact that |s_i - t_i|=|t_i - s_i| for every i. Finally, the triangle inequality follows from the triangle inequality for real numbers, |s_i - t_i|+|t_i - u_i| is greater than or equal to |s_i - u_i|.
11. What is the maximal distance between two sequences in SIGMA_N?
The maximum value of |s_i - t_i| is N_1. This implies that the maximum value for the distance function is dominated by the sequence N-1/N^i, which converges to N.
12. How many fixed point does o_N have? How many 2-cycles? How many cycles of prime period 2?
The fixed points are those sequences (000...), (111...), ..., (N-1N-1N-1...), so there are N fixed points. The sequences of period 2 are those sequences of the form (s_0s_1s_0s_1...). There are N^2 such points. But that number includes the N fixed points. This implies that there are N(N-1) points of prime period 2. So, there are N(N-1)/2 cycles of prime period 2 and N(N+1)/2 cycles of period 2 all together.
18. Each of the following defines a function on the space of sequences SIGMA, the space of sequences of two symbols, 0 and 1. In each case, decide if the given function is continuous. If so, prove it. If not, explain why.
To show that G is continuous we need to show that given a>0 there exists a b>0 such that whenever d[s, t] < b, then d[G(s), G(t)] < a. We can always find an n such that 1/2^n is less than a. We need to ensure that G(s) and G(t) match up for the first n places in order for their distance to be less than a. This will hapen if s and t match up for the first n/2 places. So we simply have to choose b so that b is less than 1/2^{n/2}. Therefore, G is continuous.
Given a>o, choose n such that 1/2^n is less than a. In this case, let b=a. Then if the distance between s and t is less than b, or s_i=t_1 for i less than n, then we know that (1-s_i)=(1-t_i) for i less than n. This implies that the distance between K(s) and K(t) is less than a. Therefore, K is continuous.
Given a>0, choose n as above. We need to choose b to be very small in this case, in particular we choose b<1/2^{10^n}. By choosing b in this way, if s and t match up for the first 10^n +1 places, then M(s) and M(t) will agree for the first n places, making their distance less than a. Thus, M is continuous.
This function is not continuous. This is due to the fact that "closeness" and continuity are based upon the behavior of the begining of sequences, but this function is controlled by the behavior of the tails of sequences. We can choose two sequences s and t which are arbitrarily close, or they agree for the first N places where N is very large. But then let the tail of s be 00... and the tail of t be 11... Then, P maps s and t as far away from each other as two points can be. Given a>0, we can never choose a b>0 that guarantees that the distance between P(s) and P(t) is less than a.
For more information about homework assignments, click
here