ASSIGNMENT 5 SOLUTIONS

MA 471-671

ASSIGNMENT 5 SOLUTIONS

Assignment: Page 131: Nos. 1-4, 6-13, 15, 16, 21, 22, 24.

For each of the following sets , decide whether or not the set is dense in [0,1].

1. S1 is the set of all real numbers in [0,1] except those of the form 1/2^n for n=1,2,3...
Yes, S1 is dense in [0,1]. One way to show this is to first let w=1/2^n for some integer n (w is not in S1) , and then produce of points xk in S1 such that xk -> w as k -> infinity.
We will do this by using a bisection technique on the interval [w,2w].
Begin by letting x0 = 2w = 1/2^n-1 and form the sequence
xk = ( w + x(k-1) )/ 2 for k>0
=> x1=3/2^n+1, x2=5/2^n+2, x3=9/2^n+3 and in general
xk=(2^k + 1)/2^n+k {note xk is in S1 for each k>0}
Claim, xk -> w as k -> infinity.
To see this, consider the function Fw(x)= (w+x)/2 where w is any real number. Notice that Fw is a linear map with attracting fixed pt w and basin of attraction all of [0,1].
In Summary, let w = 1/2^n be a point not in S1, x0=2w and Fw(x)=(w+x)/2. Then Fw^k(x) -> w as k -> infinity, and Fw^k(x) is in S1 for all k>0. This proves that S1 is dense in [0,1].
2. S_2 is the set of all rationals in [0,1] of the form p/(2^n) where p and n are natural numbers.
Note that S_2 contains all multilples of 1/2, all multiples of 1/4, etc. In fact, x is in S_2 if and only if x has a terminating binary expansion. Assuming this to be true for the moment, we may easily show that S_2 is dense in [0,1] as follows: let w = 0.b1b2b3... be an arbritary point in [0,1]. If w terminates, then we are done, so suppose it dies not. Then the sequence,
0.b_1, 0.b_1b_2, 0.b_1b_2b_3, ... obviously converges to w, and each element of this sequence is in S_2.
Using a bisection technique, we now exhibit such a sequence in S_2 converging to w. Take the unit interval, divide it in half, and determine which half contains w. Discard the half which does not. Halve the remaining interval, and again ask which half contains w. Continue this halving process, each time throwing away the half interval which does not contain w. This binary search technique, as it's called, captures w to any degree of precision one cares to specify.
3. S3 is the Cantor middle-third set.
S3 is not dense. There can not possibly be a sequence in K converging to 1/2, for example, sincde the interval (1/3,2/3) was removed at the first stage of the Cantor set construction.
4. S_4 is the complement of the Cantor middle-thirds set.
Recall that the ternary expansion of x in S_4 has no 1's. Any point which does have a 1 in its ternary expansion is in S_4's complement. Moreover, any finite string can be prepended to such a point, and the result is still in S_4's complement. Thus the complement of S_4 is dense in [0,1] since there are (uncountably many) pints in S_4's complement arbitrarily close to any point x in the Cantor set.

For each of the following sets, decide whether or not the set is dense in Sigma. Give reason.

6. T1= {(s0s1s2...) | s4=0}.
Any point s not in T1 is of the form (s0s1s2s31s5s6...). The point in T1 closest to s is (s0s1s2s30s5s6...) and the distance between these points is 1/2^4. Therefore, T1 cannot possibly be dense in Sigma.
7. T2 is the complement of T1.
T2 is not dense in Sigma. Observe that T2 = {(s0s1s2...) | s4=1}. By an argument virtually identical to the one in exercise 6, T2 can not possibly be dense in Sigma.
8. T3 = {(s0s1s2...) | the sequence ends in all 0's}.
T3 is dense in Sigma. To show this, take an arbitrary s=(s0s1s2...) in Sigma and construct a sequence of poins sn (in T3) such that
sn=(s0s1...sn000...repeating 0's)
sn -> s as n -> infinity, thus T3 is dense in Sigma.
9. T4 = {(s0s1s2...) | at most one of the sj's=0}.
T4 is not dense in Sigma. Consider the point (00111...repeating 1's) in Sigma which is not in T4. There is no sequence of points in T4 converging to this point. Indeed, the closet point in T4 to (00111...repeating 1's) is (0111...repeating 1's) and the distance between these two points is 1/2.
10. T5 = {(s0s1s2...) | infinitely many of the sj's=0}.
T5 is dense in Sigma. To see this, take a point in Sigma not in T5 which has but finitely many 0's. This point has infinitely many 1's, and in fact, the tail of the sequence must be all 1's and hence of the form (s0s1...sn111..repeating 1's) for some n. But the sequence of points in T5
(s0s1s2...sn000...repeating0's),(s0s1s2...sn100...repeating0's),(s0s1s2...sn 110...repeating0's),...
converges to (s0s1s2...111..repeating 1's), thus T5 is dense in Sigma.
11. T6 is the complement of T5.
T6 is dense in Sigma. As argued in exercise 10, a point in T6 must end in all 1's. Consequently, we proceed as in exercise 8 by constructing a sequence of points, each ending in all 1's, converging to any point in Sigma. Note that T6 is not the same as
{(s0s1s2...) | infinitely many of the sj's=1}
since there are strings in the latter which are not in T6. The string (010101...repeating01's) is one such example.
12. T7={(s0s1s2...) | no two consecutive sj's=0} .
T7 is not dense in Sigma. In words, T7 consists of those strings in which every 0 is followed by a 1. The complement of this set consists of all strings with a consecutive pair of 0's. The string (00111...repeating 1's) is one such example. Unfortunately, there is no string in T7 close to this string - in fact, the element in T7 closest to (00111...repeating 1's) is (011...repeating 1's), and the distance between these two points is 1/2.
13. T8 is the complement of T7.
T8 is dense in Sigma. As mentioned in exercise 12, T8 is the set of strings containing a consecutive pair of 0's. Now take any point in Sigma and construct a sequence in T8 converging to it. (The sequence in exercise 8 works fine).
15. Is the orbit of the point (01 001 0001 00001...) under the shift map dense in SIGMA?
No-in fact, the orbit of (01 001 0001 00001 ...) stays away from M_11={sequences with s_0=1,s_1=1} altogether. and there's really nothing special about the systematically increasing number of 0's in this string. No element of
{strings of 0's and 1's not having 11 as a substring} has an orbit which is dense in SIGMA.
16.Is it possible to give an exampple of an orbit under the shift map that accumulates on (i.e., comes arbitrarily close to but never equals) the two fixed points of the shift map, but which is not dense?
Consider the orbit of

(01 0011 000111 00001111 ...)

under the shift map. This orbit comes arbitrarily close to either of the fixed points, but it is not dense since it stays away from all other periodic points, for example.
21. Prove that the function
T(x) ={ 2x if x<=1/2
{2 - 2x if x>1/2
is chaotic in [0,1].
We will show that the doubling map D is semi-conjugate to the tent map T via T itself! That is, we will show that
T*T = T*D. (Note that the doubling map D needs to be defined on the closed unit interval for this work, D: [0,1] -----> [0,1].) Thus T will be chaotic. This is because orbits under iteration of D map to dynamically equivalent orbits under T. In fact, we now prove by induction that
T*D^(n-1) = T^n
for all n>0. Suppose this equation is true for n:=k. The
T*D^(k-1)=T^k => T*T*D^(k-1) = T*T^k,
and since T*D=T*T (this will be verified in a moment) we have
T*D^k=T^(k+1)
which completes the inductive proof. We remark that this equation gives an explicit forumula for T^n(x) since we already know that D^(n-1)(x) = 2^(n-1)x mod 1.
We now show that D is semi-conjugate to T via T, or in other words, that T*D=T*T. There are four cases to consider for T*T:

0<=x<=1/4 => 0<=T(x)<+1/2 => T*T(x)=T(2x)=2(2x)=4x.
1/4<=x<=1/2 => 1/2<=T(x)<=1 => T*T(x)=T(2x)=2-2(2x)=2-4x.
1/2<=x<=3/4 => 1/2<= T(x)<=1 => T*T(x)=T(2-2x)=2-2(2-2x)=4x-2.
3/4<=x<=1 => 0<=T(x)<=1/2 => T*T(x)=T(2-2x)=2(2-2x)=4-4x.

Similarly, there are four cases for T*D:

0<=x<=1/4 => 0<=D(x)<=1/2 => T*D(x)=T(2x)=2(2x)=4x.
1/4<=x<1/2 => 1/2<=D(x)<1 => T*D(x)=T(2x)=2-2(2x)=2-2(2x)=2-4x.
1/2<=x<=3/4 => 0<=D(x)<=1/2 => T*D(x)=T(2x-1)=2(2x-1)=4x-2.
3/4<=x<1 => 1/2<=D(x)<1 => T*D(x)=T(2x-1)=2-2(2x-1)=4-4x.

We have to be a little bit careful at x=1/2 since D is not continuous there, and also at x=1 since we haven't yet defined D(1). But it is easy to check that T*D(1/2)=T*T(1/2)=0, and that T*D(1)=T*T(1)=0 provided we define D(1) to be either 0 or 1. It is also straightforward to check that both T*T and T*D are continuos on [0,1]. So what we have shown is that

{ 4x if 0<=x<=1/4
T*D(x)=T*T(x)= { 2-4x if 1/4<=x<=1/2
{ 4x-2 if 1/2<=x<=3/4
{ 4-4x if 3/4<=x<=1 and so D is conjugate to T via T.
22.Use the results of previous exercise to construct a conjugacy between T on the interval [0,1] and G(x)=2x^2-1 on the interval [-1,1].
We eill show that

U*T=G*U
where U: [0,1] ----> [-1,1] is defined by U(x)=cos(pi.x). Note that U is a homeomorphism. Now,

U*T(x)={ cos(2pi x) if 0<=x<=1/2
{ cos(2pi x - 2pi) if 1/2<=x<=1.
But cos(2pi x - 2pi)= cos(2pi x), and so
U*(x) = G*U(x).
Hence, G is chaotic since T is chaotic (see Exercise 21).
24. Prove that F_4(x)=4x(1-x) is chaotic in [0,1].
Our goal si to find a linear map W:[-2,2] -->[0,1] such that

F_4*W=W*Q_-2
where Q_-2(x)= x^2 -2. Suppose W(x)=ax+b. Then
F_4*W(x) = 4(ax+b)(1-ax-b)= 4(ax-a^2x^2-abx+b-abx-b^2)=
=4((a-2ab)x-a^2x^2+b-b^2)
whereas
W*Q_-2(x)=a(x^2-2)+b=ax^2-2a+b.
Equating coefficients in these two equations, we arrive at the following system of equations:
-4a^2=a (1)
4(a-2ab)=0 (2)
4(b-b^2)= -2a+b (3).
From (1), we see that a=0 or a=-1/4. Plugging the latter into (2), we find -1+2b=0 which says that b=1/2. Cheking these results against (3), we have
4(1/2-1/4)=-2(-1/4)+1/2 => 2-1=1/2+1/2 => 1=1.
Thus, W(x)=(-1/4)x+1/2=(2-x)/4, and then easy to check that F_4*W(X)=W*Q_-2(x). Hence, F_4 is chaotic.