. That is, if x Î
X then x is a function x(n):Z+ ®
{0,1}. In words, X is the set of all one-sided infinite sequences
of 0's and 1's. X will be our symbol space.
In symbolic dynamics we study sequences of symbols. These symbols may represent the state of some system at a certain point in time. A transformation in this space represents the change in the system from one moment to the next. Certain questions about the properties of these transformations are central to the study of any dynamical system. One such property is called minimality, in which the orbit of every point in the space is dense in the space. In this paper, we look at a method for constructing sequences that generate minimal spaces and also include a method whereby any sequence can be interpolated into such a sequence.
Let X = . That is, if x Î
X then x is a function x(n):Z+ ®
{0,1}. In words, X is the set of all one-sided infinite sequences
of 0's and 1's. X will be our symbol space.
Definition. Let T be a transformation on X given by Tx(n)
= x(n+1). T is called a left-shift. The notation Tjx
will represent the usual composition of transformations. The
set {Tj : j Î
Z+} is a semi-group of transformations
on X.
The pair (X, T) is a dynamical system. It is possible to introduce
a topology in which all the transformations Tk
are continuous.
Definition. Let x, y Î X and define the distance d by
In other words, given e > 0, d(x, y) < e if and only if there exists N (depending on e) such that x(n) = y(n) for all n < N. Clearly N = e-1.
In general, we classify a point x Î
X by the type of dynamical system found in the topological closure
of the orbit of x under the action of the semi-group of transformations.
The term minimal implies that any point in this orbit
closure will generate the same dynamical system under the semi-group
action. In terms of a single point x, we may offer the following
equivalent definition.
Definition. x Î X is
minimal if for each e > 0
and for each j, M Î Z+,
there exists m > M such that d(Tm+jx, Tjx)
< e.
An alternate form of this definition would be: Given j and M,
there exists m > M such that
x(n + i) = x(n + i + m) for 0 _ i _ j, and any n _ 0. In words,
this means that any block of characters found in x will appear
infinitely often in x.
Definition. Any finite set A of symbols is called an alphabet.
A word in A, of length n, is a string of n elements of
A.
Because a word is a finite string, it can be thought of as a piece
of a sequence. We construct infinite sequences by choosing a
succession of words from different alphabets so that each new
word is a longer extension of the previous word. This process
is easily described using induction.
Initialization:
Let A0 = {0,1} be our initial alphabet and
n0 _ 2 be chosen as our initial length (in
the application, lengths will be chosen in a prescribed manner).
Choose an element x0 Î
A0 as the seed of our final sequence.
Note. If the sequence under construction is x, then x(0)
= x0.
Inductive step:
Assume a succession of alphabets A0 ... Ak,
lengths n0 ... nk, and
words x0 ... xk have been
defined. Construct Ak+1 by forming all words
of length nk from Ak whose
first character is xk (additional criteria
may be used in this construction). Choose xk+1
from Ak+1 and select nk+1
_ 2 by whatever process is necessary.
Note. xk is also a word from A0
of length Nk = (nk-1)(nk-2)...(n1)(n0)
_ 2k. Further, the sequence x(n) is defined
for n _ Nk. When xk+1
is constructed, x(n) is extended so that it is defined for
n _ nkNk.
The ambiguity in the choice of n in the inductive construction
of x(n) is clarified by an application of the process. We use
this ambiguity in two different sequence constructions.
This application constructs a minimal sequence. We begin with
a variation of the law of large numbers.
Lemma 1. Let A be an alphabet with m characters. Given
e > 0, there exists a length n so
that the probability that a random word of length n from A will
begin with a specified character and contain all the other characters
in A at least once is greater than 
(1
- e).
proof The proof follows once we realize that the probability of a word of length n satisfying the given properties is at least
.
We now modify inductive construction of x(n) as follows:
Initialization:
Let A0 = {0,1} be our initial alphabet. Choose
an element x0 Î
A0 as the seed of our final sequence. Select
n0 _ 2, as in Lemma 1, so that every word
of length n0 has x0 as
its first character and contains both 0 and 1 with probability
at least 
.
Inductive step:
Assume a succession of alphabets A0 ... Ak,
lengths n0 ... nk, and
words x0 ... xk have been
defined. Construct Ak+1 by forming all words
of length nk from Ak whose
first character is xk and contain every other
character of Ak at least once. Choose xk+1
from Ak+1. Suppose that Ak+1
has mk+1 characters and select nk+1
_ 2, as in Lemma 1, so that every word of length nk+1
from Ak+1 has xk+1 as
its first character and contains every other character of Ak+1
at least once with probability at least 
.
Theorem. The sequence x(n) constructed in the inductive
process is minimal.
proof Using the alternate form of the definition of a
minimal sequence, a block x(n+i) for
0 _ i _ j is part of a character in some alphabet Ak.
By the construction, this character, and hence the block will
then appear in every word used to form the alphabet Ak+1.
The consequence of the inductive construction is that the final
sequence x(n) can be broken up into letters from Ak+1.
We need only pick a letter beyond M and the property is satisfied.
In this application, we construct a minimal sequence that satisfies the property that values in positions along the sequence are predetermined.
Let {en} be a sequence of positive integers, and let y(n) Î X. If x(n) satisfies the property that x(en) = y(en) for all n then we say that x agrees with y, along the sequence {en}.
Definition. For any n Î Z+, define k(n) := card{i : ei _ n}.
One interesting choice of {en} is en
= n2. In this case, k(n)
= ëÖ(n-1)û
+ 1. As usual, ëxû
represents the greatest integer function.
Lemma 2. Let A be an alphabet with m characters. If 
,
there exists n so that we may find word of length n from A which
contains all characters of A at least once and agrees with y(n).
proof As in the proof of Lemma 1, it is clear that the probability of a word satisfying the first property (notice that the initial character restriction is removed) is at least
.On the other hand, the probability that a word satisfies the second property is exactly
.If no word satisfies both properties simultaneously then
.It follows that
for all n. This clearly contradicts the hypothesis so that such
a word must surely exist.
Note. Although Lemma 2 establishes the existence of only
one word, it follows that other words may be constructed by permuting
the letters in the free positions.
Once again we modify the original inductive construction of x(n).
Initialization:
Let A0 = {0,1} be our initial alphabet. Choose
an element x0 Î
A0 as the seed of our final sequence. If
e0 = 0, we must select x0
= y(0). Otherwise, the choice is random. Select
n0 _ 2, as in Lemma 2, so that some word of
length n0 contains both 0 and 1 and agrees
with y. Rename y(n) as y0(n) and {en}
as {e0,n}.
Inductive step:
Assume a succession of alphabets A0 ... Ak,
lengths n0 ... nk, sequences
{ek,n}, symbol sequences yk(n)
Î 
, and
words x0 ... xk have been
defined. Construct Ak+1 by forming all words
of length nk from Ak that
contain every character of Ak at least once.
Choose xk+1 from Ak+1
as in Lemma 2 so that xk+1 agrees with yk(n).
Define {ek+1,n} from {ek,n}
by
.
The relationship between {ek+1,n} and {ek,n}
is linear so that 
is preserved. (k
is a function specific to the sequence {ek,n}
in question. It serves to mark the number of free positions we
may use in the construction. Because it is only used in Lemma
2, subscript notation has not been adopted.) yk+1(n)
is defined from yk(n) by partitioning yk(n)
into blocks of length nk and replacing them
with appropriate characters from Ak+1. Suppose
that Ak+1 has mk+1 characters
and select nk+1 _ 2, as in Lemma 2, so that
some word of length nk+1 from Ak+1
contains every character of Ak+1 at least
once and agrees with yk+1(n).
This final construction is important because one could ask the question: "If an observer does not record the state of the system at every moment, can the total system be determined?" If the moments occur at regular intervals the answer may be yes. In general, the answer is no. As a result of our construction we may offer a counter-example. Form y(n) so that in positions corresponding to perfect squares we fix values from a sequence that is not minimal, then fill in the rest of the values randomly. Following the construction in Application #2, we may construct x(n) so that x(n2) = y(n2) and x(n) is minimal. In such a system, an observer looking at the moments corresponding to perfect squares would get a completely incorrect impression.