Chaos from the Logistic Map. Part 2: “Scrambled Sets.”

In our previous story about the subject we focused on finding periodic points for dynamically system with specific properties. One dynamics that revealed especially interesting patterns, turned out to be the simple looking logistic map. We illustrated that this map produces dynamics with periodic points for all orders. In this story, we will show that there exists another type of points that moreover have strong appearance in certain regions.

My intend is to make the text as readable as possible, but due to this environment’s lack of support for latex symbols, please apologize for making the following abbreviations:

f^k(x): denotes k-times composition of f, that is: f^3(x) f(f(f(x)))

A \intersect B:  means the intersection of the sets A and B

A \subset B:  means A is a subset of B

A \superset B: means A is a superset of B

A \union B: means the union of A and B

\empty: denotes the empty set

x \in B: means x is element of B

x \notin B: mean x is not element of B

For what follows we need a small result from infinite combinatorics:

The set S of sequences consisting of elements from {0, 1} and having the restriction that on a 1 follows at least two times a 0, is uncountable.

Examples:

(0, 0, 1, 0, 0, 1, 0, 0, ...)

(0, 1, 0, 0, 0, 0, ...)

Proof:

The proof is a variation of Cantor’s diagonal argument (see here) that is used to proof the set of all sequences with elements in {0, 1} is uncountable. A sequence p in S can be encoded by only enumerating the indexes that correspond to a 1. The remaining elements will be 0 and in particular the two following the an index with a 1. So for instance,

s = (a, b, c, ...)

means

s_a = 1, s_{a+1} = 0, s_{a+2} = 0

s_b = 1, s_{b+1} = 0, s_{b+2} = 0

s_c = 1, s_{c+1} = 0, s_{c+2} = 0

Moreover, we restrict our attention to the subset S' of S for that the above encoding produces infinite sequences. If we show S' to be uncountable, then S will be as well.

Now, to the contrary we assume S' is countable and denote the j'th element of the i‘th sequence by a_{i, j}.

From this we define a new sequence s by

s_j := a_{j, j} + 3

For any k the k’th sequence (a_{k, j})_j is distinct from the sequence s because the entry s_k is different from the entry a_{k, k}.

This shows, s is not included in the enumeration of S' and this contradicts S' being countable.

Constructing a scrambled set:

Remember the technique we used to construct periodic points of arbitrary large order. Especially this was based on Theorem 2 here.

We will use the same ‘aim and shoot’ technique, to find points that do another movement, that is of rather chaotic nature than periodicity.

Again let us consider an closed interval I and a function f that maps

f: I -> I

f(I) = I

An example is the logistic map: x |-> 3.7 * x * (1 — x) on I = [0, 1]

Moreover, let us assume we can divide the interval into two further intervals, K and L, like pictured

[------K------|-------L------]
a             b              c

and for that f maps like so:

f(K) = L

f(L) = I = (K \union L)

f(a) = b

f(b) = c

f(c) = a

Next, since K \union L \subset f(L), using Theorem 2 here, we can find two sub-intervals L_1, L_2 of L such that f(L_1) = L and f(L_2) = K. Clearly, these intervals must be disjoint:

[---K---|--|--L_1--|----|---L_2---|--]

Again by using Theorem 2 here, we may find and interval Q_1 \subset L_1 with f(Q_1) = L_1. Further, since f^2(Q_1) = f(L_1) = L, an interval Q_2 \subset Q_1 such that f^2(Q_2) = L_1. Because f(L_1) = L_2, there is Q_3 \subset Q_2 with f^3(Q_3) = L_2. And further, since f(L_2) = K, exists Q_4 \subset Q_3 with f^4(Q_4) = K. And once more, because of f(K) = L, we can find Q_5 \subset Q_4 with f^5(Q_5) = L_1.

As you see, we can proceed this way arbitrary many steps to yield a decreasing sequence of intervals

Q_1 \superset Q_2 \superset Q_3 ...

and having iterates of f mapping these intervals into a sequence of

L_1, L_1, L_2, K, L_1, ...

We encode this sequence like

(0, 0, 0, 1, 0, ...)

if we assign to iterates that are in L the number 0 and to iterates that are in K the number 1.

Clearly, the above technique allows us to construct almost any sort of such sequences. That is, the above example easily can be altered to yield for instance,

(0, 0, 1, 0, ...)

If we restrict the sequences after being in K to be at least two times being in L, we ensure the intersection point of the intervals K and L, i.e. b, to never be in the intersection of all Q_i's (note f^(b) \notin L).

This brings us to exactly those sequences considered in the initial theorem. So we know, there exists uncountable many of these. Since all the Q_i are compact, with an argument from topology one shows that their intersection must contain a point p.

Assume we are given two distinct sequences

s = (1, 0, 0, ...)

s' = (0, 1, 0, 0, ...)

Then the corresponding points p and p' must be different. For this to see just remember for all i we have

f^i(p) \in K or L  (but not =b)

f^i(p') \in K or L  (but not =b)

And since for some i the l.h.s deviates, it must be p != p'.

Altogether, we found an uncountable set S of points in I such that the iteration under f belongs to exactly one of the above sequences. Of course, these sequences still contain some pairs that deviate only within the first n steps and afterwards are identically. These pairs can be grouped as follows (into equivalence classes).

For each n consider all 0–1 sequences that differ in the fist n steps and afterwards are identical. For each n these are finite many sequences. The union over all n contributes to an infinite countable set. If we remove this countable set from the uncountable set S, what remain is still uncountable. Moreover, this remaining set, let us denote it again be S, consists of sequences that have differences after arbitrary large steps.

A ‘difference’ though means, for some i we have

f^i(p) \in K

f^i(p') \in L

Also, since the distance from b to L_1 resp. L_2 is fixed, we can translate this in mathematical terms to

lim sup_i |f^i(p) - f^i(p')| > 0

whenever p, p' are in S.

Since S as an uncountable set in the compact interval I, it must have accumulation points. Thus, there are regions in I where we can find points in S that are arbitrary closed to each other and during iteration will infinitely often deviate by lim sup_i |f^i(p) — f^i(p’)|. This implies bad news for computer simulations at these regions. A computer that due to rounding errors will always slightly deviate from the actual iteration, cannot ensure to make any reliable assertions on the orbits starting with a specific initial value. Of course, since the mapping f is continuous, we can always find a neighborhood sufficiently small around an initial value x such that after n iterations different points of this neighborhood produces close results. Though, we cannot conclude that they stay near over the next n iterations. It could be that even without rounding errors, the iterations do deviate like stated above.

We also can bring this into another context often used together with chaotic systems, that is, sensitive dependency on initial conditions. In that sense, there might exists two initial values, lying very close to each other and nevertheless producing substantially different results during iterations.

Excluding periodic points:

Another interesting thing in combination with the forerunner article here, is that we can exclude any periodic points from S. Obviously, a point p in S only can be periodic if it has a recurring pattern in terms of the aforementioned sequences. But such patterns easily can be seen to be a countable subset of all sequences since each of it encode a finite piece of information only. Therefore, by excluding them the resulting set S remains uncountable.

This set S is very interesting from a mathematical point of view, but it is a monster for a computer. In the next story, we will see, we can make it even worse.

Thanks for reading!