A Visual Representation of Sequence Space

Marc Fusaro University of Scranton

June 4, 1996

Abstract

In an undergraduate course on chaotic dynamical systems one encounters a strange metric space called sequence space, (Σ, d_{∞}). As a set, Σ = { s_{0}s_{1}s_{2} … | s_{i} ∈ {0, 1} } and the distance between two elements is defined by d_{∞}(σ, τ) = Σ_{i=0}^{∞} \frac{|s_{i}−t_{i}|}{2^{i}} where σ = s_{0}s_{1}s_{2} … and τ = t_{0}t_{1}t_{2} . . .. This is a very difficult space to visualize. In fact, it can easily be shown that this space cannot be embedded isometrically in ℝ^{n} for any n. In this paper we develop a geometric model of Σ which gives a very good impression of the geometric structure of the space. The model consists of a subset of the Euclidean plane and an unusual, but easy to visualize, metric on these points making the model isometric to (Σ, d_{∞}).

1 Introduction

In an undergraduate course on dynamical systems based on Devaney’s text [Dev] one encounters a strange metric space called sequence space, defined below.

Definition 1.1 The sequence space on two symbols is the set

Σ = { s_{0}s_{1}s_{2}s_{3}... | s_{i} ∈ {0, 1} }

with the distance between two elements of this set defined by

d_{∞}(σ, τ) = ∑_{i=0}^{∞} \frac{|s_{i} − t_{i}|}{2^{i}}

where σ = s_{0}s_{1}s_{2} … and τ = t_{0}t_{1}t_{2} . . .. i.e. Σ is the set of all sequences of zeros and ones.

While the points and distances are clearly defined, it is very difficult to visualize the geometric structure of the space as a whole. The goal of this paper is to construct a geometric model of sequence space as an aide to visualizing its geometry.

In order to gain some insight into the geometry of Σ we begin by considering a family of finite subspaces of Σ.

Definition 1.2 Define the family of metric spaces (Σ_{n}, d_{n}) by

Σ_{n} = { s_{0}s_{1}s_{2}...s_{n−1} | s_{i} ∈ {0, 1} }

d_{n}(σ, τ) = ∑_{i=0}^{n−1} \frac{|s_{i} − t_{i}|}{2^{i}}

where σ = s_{0} … s_{n−1} and τ = t_{0} … t_{n−1}, i.e. Σ_{n} is what we get if we consider only the first n terms of an element of Σ.

Clearly d_{∞} and d_{n} are metrics and (Σ_{n}, d_{n}) and (Σ, d_{∞}) are metric spaces.

Perhaps the simplest model one could make for a given metric space would be to embed it isometrically into some Euclidean space (preferably ℝ or ℝ^{2} or ℝ^{3}). We will show in Section Four that even the tiny subspace Σ_{2} of Σ can not be isometrically embedded in ℝ^{n}, no matter how large we choose n. Thus ℝ^{n} with the Euclidean metric fails to contain an embedded model for Σ.

However, if we switch to the grid metric (often called the taxicab metric) we can construct a model of Σ_{n} in ℝ^{n}.

Definition 1.3 Consider ℝ^{n} with the grid metric

d_{G}(s, t) = ∑_{i=0}^{n−1} |s_{i} − t_{i}|

where s = (s_{0}, s_{1}, ..., s_{n−1}) and t = (t_{0}, t_{1}, ..., t_{n−1}).

Define γ_{n} : (∑_{n}, d_{n}) → (ℝ^{n}, d_{G}) by

γ_{n} (a_{0}a_{1} … a_{n−1}) = (s_{0}, s_{1}, ..., s_{n−1})

where s_{i} = \frac{a_{i}}{2^{i}}.

We will prove that γ_{n} is an isometry and thus that its image is a model of Σ_{n} in (ℝ^{n}, d_{G}).

For example, consider Σ_{1}. The image of Σ_{1} contains only two points, as pictured in Figure 1(a.).

Now let us consider Σ_{2}. Its image consists of four points in the plane arranged as shown in Figure 1(b.). γ_{3}(Σ_{3}) is pictured in Figure 1(c.). Continuing this way we could easily model Σ_{n} in n-space. However this n-dimensional model is more difficult to visualize for large n, and the analogous model for Σ would be a subspace of ℝ^{∞}, hardly an easy thing to visualize. So we would like to find a way of “compressing” the entire space into three or fewer dimensions. In fact we will be able to fit it into two dimensions.

To do this we should first consider γ_{3}(Σ_{3}). Think of it as a box sitting on the floor in front of you. The box has length one unit, width one half unit, and height one quarter unit. You can find the distance between any two points in Σ_{3} by measuring the length of any shortest path which travels along the edges of the box between the corresponding points in γ_{3}(Σ_{3}). Now take your Swiss Army knife out of you pocket and cut off the \frac{1}{2} by \frac{1}{4} sides. Step on the box gently. Don’t bend the sides; let it bend at the edges. You have just transformed a three dimensional model into a two dimensional model. In an analogous manner we can “crush” our higher dimensional models of Σ_{n} into ℝ^{2}.

In this paper we develop a model which “crushes” Σ into the real plane in an analogous manner. However, before we consider this model we will look at a model for a much simpler space to develop our intuition for what we mean by a “geometric model.”

2 Modeling the Discrete Metric

To illustrate the kind of geometric model we have in mind, let us first consider a similar model for a simpler metric space: the discrete metric on a set X. Under the discrete metric the distance between any two distinct points of X is one. Our model will have four key ingredients: 1) a set of points, P (corresponding to the points of X), 2) a set of line segments (providing paths between any two points), 3) a definition of a unique “proper” path between any two points, and 4) a metric induced on P (by measuring the Euclidean lengths of the line segments in the proper path between two points). In the case of the discrete metric we can define these four items as follows.

2.1 The Points

Let the set of points, P ⊂ ℝ^{2}, consist of the n equally spaced points on a circle of radius \frac{1}{2} (i.e. in polar coordinates P = \{ (r, θ) | r = \frac{1}{2} and θ = \frac{2π}{k}, k ∈ 0, 1, …, n − 1 \}) as shown in Figure 2(a.).

2.2 The Line Segments

Define a set of line segments, S, to consist of all those segments connecting points of P to the center of the circle, as shown in Figure 2(b.).

2.3 The Paths

We define a proper path between the points of P, to be the shortest path (in the Euclidean metric) from one point to another along line segments of S.

2.4 The Metric

Finally, define a metric on P induced by the proper paths, namely the distance between two points is the sum of the lengths of the line segments in the unique shortest path between the points. With this metric, P is isomorphic to our original discrete metric space, X.

We can think of this model as the spokes and hub of a wagon wheel. The points lie at the end of the spokes. To get from one point to another, one must travel down the spoke to the center and then out along the other spoke.

Having modeled the discrete metric we now turn our attention to sequence space to develop a similar model, i.e. one which isometrically maps each sequence to a point in the real plane.

3 Modeling Sequence Space

In order to model sequence space we will follow a pattern analogous to the one we created for the discrete metric. Thus we will define points and line segments between those points, such that the lengths of certain paths using the segments induces a metric on the set of points, making it isometric to sequence space.

3.1 The Points

Definition 3.1 For x ∈ [0, 2) ⊂ ℝ define α_{n} (x) to be the coefficient of \frac{1}{2^{n}} in the binary expansion of x, i.e.

x = ∑_{n=0}^{∞} α_{n}(x)\frac{1}{2^{n}}

and α_{n} (x) ∈ {0, 1}.

[Note: If x has two binary expansions we consider only the one which ends in repeating zeros, e.g. 1.0000 … instead of 0.1111 . . ..]

Definition 3.2 Let P ⊂ [0, 2) × [0, 2) by

P = { (x, y) | ∀n ∈ ℕ, α_{2n}(x) = 0 and α_{2n+1}(y) = 0 }

The set P is pictured in Figure 3. We are now ready to define our Crush Map, κ, which will identify points of P with those of Σ.

Definition 3.3 Define the Crush Map κ : Σ → P by

κ(s_{0}s_{1}s_{2} …) = ( ∑_{i odd} \frac{s_{i}}{2^{i}} , ∑_{i even} \frac{s_{i}}{2^{i}}).

For example, consider the sequence σ = 111111¯0 ∈ Σ. The corresponding x-coordinate of κ(σ) would be 0.10101¯0 and the y-coordinate would be 1.01010¯0 in base two. So in base ten the coordinates would be \frac{1}{2} + \frac{1}{8} + \frac{1}{32} + 0 + ⋯ = \frac{21}{32} and 1 + \frac{1}{4} + \frac{1}{16} + 0 + ⋯ = \frac{21}{16} respectively. So κ(σ) is (\frac{21}{32}, \frac{21}{16}).

Lemma 3.1 κ is a bijection.

Proof: First we will show that κ is injective. Let σ = (s_{0}s_{1}s_{2} …), τ = (t_{0}t_{1}t_{2} …) ∈ Σ and assume κ(σ) = κ(τ). Then

κ(s_{0}s_{1}s_{2} …) = κ(t_{0}t_{1}t_{2} …)

(0+ \frac{s_{1}}{2^{1}} +0+ \frac{s_{3}}{2^{3}} +0+⋯, \frac{s_{0}}{2^{0}} +0+ \frac{s_{2}}{2^{2}} +0+⋯) = (0+ \frac{t_{1}}{2^{1}} +0+ \frac{t_{3}}{2^{3}} +0+⋯, \frac{t_{0}}{2^{0}} +0+ \frac{t_{2}}{2^{2}} +0+⋯)

so,

0 + \frac{s_{1}}{2^{1}} + 0 + \frac{s_{3}}{2^{3}} + 0 + ⋯ = 0 + \frac{t_{1}}{2^{1}} + 0 + \frac{t_{3}}{2^{3}} + 0 + ⋯

and

\frac{s_{0}}{2^{0}} + 0 + \frac{s_{2}}{2^{2}} + 0 + ⋯ = \frac{t_{0}}{2^{0}} + 0 + \frac{t_{2}}{2^{2}} + 0 + ⋯

But two numbers are equal if and only if the digits of their binary expansions are equal, so

s_{1} = t_{1}, s_{3} = t_{3}, …, and s_{0} = t_{0}, s_{2} = t_{2}, ….

Thus s_{i} = t_{i} for all i, and so σ = τ. Thus κ is injective.

To see that κ is surjective let p ∈ P. Then p = (x, y) where α_{2n}(x) = 0 and α_{2n+1}(y) = 0 for all n. Define π ∈ Σ to be π = s_{0}s_{1}s_{2} … where

s_{i} = \{ \begin{matrix}α_{i}(x) & if i is even \\ α_{i}(y) & if i is odd \end{matrix}

Clearly κ(π) = p. Therefore κ is surjective. So κ is a bijection. □

Now that we have a mapping of points from Σ to P ⊂ ℝ^{2} we need to define the distances between those points in a way which preserves the distances in (Σ, d_{∞}). We begin by defining a set of line segments whose endpoints are points of P.

3.2 The Line Segments

Definition 3.4 Let S be the set of all line segments connecting those points of P whose inverse images under the crush map differ by only one digit, i.e.

S = { l(p, q) | ∃!n, κ^{−1}(p)_{n} ≠ κ^{−1}(q)_{n} }

where θ_{n} denotes the nth term of the sequence θ ∈ Σ, and l(p, q)denotes the line segment joining p to q in ℝ^{2}.

Notice that every point in P is the endpoint of a unique segment of length \frac{1}{2^{k}} for all k ∈ ℕ. This is easy to see by analogy in Σ_{3}. Go and get the box that you stepped on earlier. Decompress it so that it is a box again. Notice that each vertex of the box has three edges connected to it. One has length one, another has length one half, and the third has length one quarter. This can also be seen by referring to Figure 1(c.).

Lemma 3.2 Let |l (p, q)| denote the length (in the Euclidean metric) of the line segment l (p, q) ∈ S. Then

|l(p, q)| = d_{∞}(κ^{−1}(p), κ^{−1}(q)).

Proof: Since the points κ^{−1}(p) and κ^{−1}(q) differ by only one term, either the x or the y coordinate will be the same for both p and q. Assume they have the same y coordinate, the other case being similar.

|l(p, q)| = | ∑_{i odd} \frac{κ^{−1}(p)_{i}}{2^{i}} − ∑_{i odd} \frac{κ^{−1}(q)_{i}}{2^{i}} |

= | ∑_{i odd} \frac{κ^{−1}(p)_{i} − κ^{−1}(q)_{i}}{2^{i}} |

= |0 + 0 + ⋯ + \frac{κ^{−1}(p)_{n} − κ^{−1}(q))_{n}}{2^{n}} + 0 + 0 + ⋯|

= d_{∞}(κ^{−1}(p), κ^{−1}(q))

where n is the index of the unique term in which κ^{−1}(p) and κ^{−1}(q) differ. Thus the length of the line segment equals the distance in Σ between inverse images of p and q. □

The entire set of line segments, S, is pictured in Figure 4. Notice that wherever perpendicular line segments in the figure cross, the point of intersection is in P. Notice also that many distinct line segments in S overlap each other in the figure. For example there is a line segment connecting κ(¯0) = (0, 0) and κ(1¯0) = (0, 1). There is also one connecting κ(¯0) = (0, 0) and κ(001¯0) = (0, \frac{1}{4}). Further note that the segments in the figure enclose infinitely many rectangular regions. In this respect it has a fractal-like nature.

We are now ready to define the proper paths along line segments of S.

3.3 The Path

Definition 3.5 Let p, q ∈ P. A path from p to q is a (possibly infinite) sequence of points of P

p_{0}, p_{1}, p_{2}, p_{3}, …

where p_{0} = p, satisfying

l(p_{j}, p_{j+1}) ∈ S

for all j and

lim_{n→∞} p_{n} = q

(or p_{k} = q in the case where the sequence is finite of length k + 1, i.e. when κ^{−1}(p) and κ^{−1}(q) differ in k digits.

The length of a path from p to q is defined to be the sum of the lengths of its line segments, ∑_{j=0}^{∞} |l (p_{j}, p_{j+1})| . A path from p to q is said to be a proper path if κ^{−1}(p_{j−1}) and κ^{−1}(p_{j}) differ in the jth term that κ^{−1}(p) differs from κ^{−1}(q) and in no other terms.

Note that the series in the definition of length of proper path must converge since a proper path can contain a line segment of length \frac{1}{2^{j}} at most once.

For an example consider the proper path from κ(000111¯0) to κ(110100¯0). The proper path is

(0.15625, 0.0625), (0.15625, 1.0625), (0.65625, 1.0625), (0.65625, 1), (0.625, 1)

since these points are equal to κ(000111¯0), κ(100111¯0), κ(110111¯0), κ(110101¯0), and κ(110100¯0) respectively. The segments which comprise this path are shown on a graph of P in Figure 5.

As can be seen in the preceding example, traveling along a proper path and measuring the distances traveled is comparable to comparing the terms (in order) of the corresponding points in sequence space. This is further explained in the following theorem.

Lemma 3.3 For any p, q ∈ P, there is a unique proper path from p to q.

Proof: Suppose σ = κ^{−1}(p) = s_{0}s_{1}s_{2} … and τ = κ^{−1}(q) = t_{0}t_{1}t_{2} . . .. Let p_{0}, p_{1}, p_{2}, … be a proper path from p to q. We will prove the case where σ and τ differ in infinitely many terms, the finite case being similar. Let j ≥ 1 and assume i is the index of the jth term in which σ and τ differ. We will show that

κ^{−1}(p_{j}) = t_{0}t_{1}t_{2} … t_{i−1}t_{i}s_{i+1}s_{i+2} …  (1)

We proceed by induction on j.

Let j = 1 so i is the index of the first term where σ and τ differ. Since the path is proper, κ^{−1}(p_{0}) and κ^{−1}(p_{1}) must differ in the ith term, and in no other. Therefore, κ^{−1}(p_{1}) = s_{0}s_{1} … s_{i−1}t_{i}s_{i+1} … (since t_{i} ≠ s_{i}) and further, since the ith term is the first term which they differ, s_{m} = t_{m} for m < i. Therefore κ^{−1}(p_{1}) = t_{0}t_{1} … t_{i−1}t_{i}s_{i+1}s_{i+2} . . ..

Now for the induction step. Let j > 1. Assume (1) is true. Let i be the index of the jth term in which σ and τ differ. Let I be the index of the (j + 1)th term in which they differ. Then

κ^{−1}(p_{j}) = t_{0}t_{1}t_{2} … t_{i−1}t_{i}s_{i+1}s_{i+2} … s_{I−1}s_{I}s_{I+1} …

Since t_{I} ≠ s_{I},

κ^{−1}(p_{j+1}) = t_{0}t_{1}t_{2} … t_{i−1}t_{i}s_{i+1}s_{i+2} … s_{I−1}t_{I}s_{I+1} …

and since the Ith term is the next term (after the ith term) in which they differ, s_{m} = t_{m} for i < m < I. Therefore,

κ^{−1}(p_{j+1}) = t_{0}t_{1}t_{2} … t_{i−1}t_{i}t_{i+1}t_{i+2} … t_{I−1}t_{I}s_{I+1}s_{I+2} …

This completes the induction. Therefore the proper path is unique, as it is the one prescribed by (1). □

We can now use the lengths of the proper paths to induce a metric on P.

3.4 The Metric

Definition 3.6 Let d_{P} : P × P → ℝ by d_{P} (p, q) = the length of the unique proper path from p to q.

Theorem 3.4 (P, d_{P}) is a metric space and the Crush Map, κ : (Σ, d_{∞}) → (P, d_{P}), is an isometry.

Proof: By Lemma 3.1 κ is a bijection, so it suffices to show that d_{∞}(σ, τ) = d_{P} (κ(σ), κ(τ)).

d_{P} (κ(σ), κ(τ)) = the distance of the proper path from κ(σ) to κ(τ)

= ∑_{j=1}^{∞} |l(p_{j−1}, p_{j})|

= ∑_{j=1}^{∞} d_{∞}(κ^{−1}(p_{j−1}), κ^{−1}(p_{j}))

Since κ^{−1}(p_{j−1}) and κ^{−1}(p_{j}) differ by only one digit in i th_{j} place, (where i_{j} is the index of the jth term in which σ differs from τ) we have d_{∞}(κ^{−1}(p_{j−1}), κ^{−1}(p_{j})) = \frac{1}{2^{i_{j}}} so

= ∑_{j=1}^{∞} \frac{1}{2^{i_{j}}}

= ∑_{i=1}^{∞} \frac{|s_{i} − t_{i}|}{2^{i}}

= d_{∞}(σ, τ)

□ Thus, (P, d_{P}) is a geometric model of sequence space.

4 Additional Theorems

We close by proving some of the claims stated in the introduction.

Theorem 4.1 There does not exist an isometric embedding from (Σ, d_{∞}) into (ℝ^{n}, d_{E}) where d_{E} denotes the Euclidean metric, d_{E}(x, y) = |x − y|.

Proof: Since (Σ_{2}, d_{2}) can be considered to be a subspace of (Σ, d_{∞}) it suffices to show that Σ_{2} does not embed isometrically into ℝ^{n}. Suppose k : Σ_{2} → ℝ^{n} be an isometric bijection. Then d_{2}(α, β) = |k(α) − k(β)| for any α, β ∈ Σ_{2}. Consider the points:

σ = k(00)
τ = k(01)
ρ = k(10)
υ = k(11)

|σ − τ| = d_{2}(00, 01) = \frac{1}{2}

|τ − υ| = d_{2}(01, 11) = 1

|σ − υ| = d_{2}(00, 11) = \frac{3}{2}

Thus σ, τ, and υ are collinear as depicted in Figure 6(a.).

Now let’s consider the point ρ.

|σ − ρ| = d_{2}(00, 10) = 1

|ρ − υ| = d_{2}(10, 11) = \frac{1}{2}

Thus ρ is collinear with σ and υ, as shown in Figure 6(b.) and, therefore, collinear with τ also. Since ρ, τ, and σ are collinear

|τ − ρ| = |σ − ρ| − |σ − τ|

|τ − ρ| = 1 − \frac{1}{2} = \frac{1}{2}

However |τ − ρ| = d_{2}(01, 10) = \frac{3}{2} ≠ \frac{1}{2}. So we have a contradiction. Thus there does not exist an isometric embedding of Σ_{2} into ℝ^{n}, and consequently there does not exist an isometric embedding of Σ into ℝ^{n}. □

Theorem 4.2 γ_{n} is an isometry (between Σ_{n} and its image).

Proof: First we show that γ is a bijection. It is obviously surjective so now we must show that γ is injective. Assume γ_{n}(a) = γ_{n}(b).

γ_{n}(a_{0}a_{1}a_{2} … a_{n−1}) = γ_{n}(b_{0}b_{1}b_{2} … b_{n−1})

(\frac{a_{0}}{2^{0}} , \frac{a_{1}}{2^{1}} , \frac{a_{2}}{2^{2}} , …, \frac{a_{n}}{2^{n−1}} ) = (\frac{b_{0}}{2^{0}} , \frac{b_{1}}{2^{1}} , \frac{b_{2}}{2^{2}} , …, \frac{b_{n}}{2^{n−1}} )

\frac{a_{0}}{2^{0}} = \frac{b_{0}}{2^{0}} , \frac{a_{1}}{2^{1}} = \frac{b_{1}}{2^{1}} , …, \frac{a_{n}}{2^{n−1}} = \frac{b_{n}}{2^{n−1}}

a_{0} = b_{0}, a_{1} = b_{1}, …, a_{n−1} = b_{n−1} (a_{0}a_{1}a_{2} … a_{n−1}) = (b_{0}b_{1}b_{2} … b_{n−1})

a = b

Thus γ is a bijection. We now must show that γ preserves distances. Consider the points a and b in Σ_{n}. By the definition of d_{n}

d_{n}(a_{0}a_{1}a_{2} … a_{n−1}, b_{0}b_{1}b_{2} ⋯ b_{n−1}) = \frac{|a_{0} − b_{0}|}{2^{0}} + \frac{|a_{1} − b_{1}|}{2^{1}} + ⋯ + \frac{|a_{n−1} − b_{n−1}|}{2^{n−1}}.

And by the definition of the grid metric the distance between γ_{n}(a) and γ_{n}(b) is:

d_{G}((\frac{a_{0}}{2^{0}} , \frac{a_{1}}{2^{1}} , …, \frac{a_{n−1}}{2^{n−1}} ), (\frac{b_{0}}{2^{0}} , \frac{b_{1}}{2^{1}} , …, \frac{b_{n−1}}{2^{n−1}} )) = |(\frac{a_{0}}{2^{0}} − \frac{b_{0}}{2^{0}} )|+|(\frac{a_{1}}{2^{1}} − \frac{b_{1}}{2^{1}} )|+⋯+|(\frac{a_{n−1}}{2^{n−1}} − \frac{b_{n−1}}{2^{n−1}} )|

= \frac{|a_{0} − b_{0}|}{2^{0}} + \frac{|a_{1} − b_{1}|}{2^{1}} + … + \frac{|a_{n−1} − b_{n−1}|}{2^{n−1}}

Thus γ preserves distances. So γ is an isometry between Σ_{n} and its image. □

5 Acknowledgements

The material for this paper was conceived in an undergraduate course on chaotic dynamical systems taught by Dr. Ken Monks at the University of Scranton, who challenged me to come up with a geometric model for sequence space. This paper is the result of my response to that challenge. I would like to thank him for his help with this paper and for his contributions to it.

References

[Dev] Devaney, R.; A First Course in Chaotic Dynamical Systems, Addison-Wesley Publishing Company, (1992) ISBN: 0-201-55406-2