Figure 3.2: A portion of a sample element of
This time, the problem is not with the conclusion, but the hypotheses. Topological
transitivity is not nearly a strong enough hypothesis in several dimensions to get
the type of result that we are after, and in fact we will see that topological mixing
is not nearly good enough either. To show this, we consider a subshift called the
checkerboard island shift, which we call , defined by Quas and §ahin in [QS]. is
a -Markov shift, on an alphabet with thirteen letters. is also topologically
mixing; for a proof see [QS].
All letters of and elements of are displayed in Figure 3.2. In other words,
a two-by-two word of symbols is in if and only if it appears as a subword of the
word in Figure 3.2. Consider the word with shape in Figure 3.3, which we call .
It will not be shown here (details are in [QS]), but an occurrence of in any element
of forces the arrows and diagonal lines surrounding in Figure 3.2, along with
a boundary of thickness one filled with empty spaces. In other words, wherever ,
77
which has shape , appears, it forces a word, which we call , of shape .
appears in Figure 3.4.
Figure 3.3:
Figure 3.4:
In fact, for every , there is an analogous word (a checkerboard of size
with a boundary filled with arrows and diagonal lines in an analogous way to that
78
of ) which forces a word of size around it. We claim that for any , the
shift obtained by removing from and the shift obtained by removing
from are equal. Since is a subword of , it is obvious that .
Suppose that . Then there exists which has an occurrence of
, but no occurrence of , which, as has already been stated, is not possible. So,
. This implies that . However, since
and , we have a contradiction to Possible Theorem 3.1.18
for the same reason as we did before. Since this is true for all , if we wish to adjust
the conditions of the conclusion again, we will have to change our "tolerance range"
from to something like , which would weaken the result
considerably. To obtain a conclusion of the strength we want, we need a stronger
mixing property than topological mixing. The notion which we use is that of strong
irreducibility.
Definition 3.1.19. -subshift X is strongly irreducible with uniform filling
length R if for any trvo subsets S, T of , and for all p such that
R (that is, for all q and r , d ( q, ), and for any elements x, ,
there exists y such that and .
For the sake of comparing, we also include a definition of topological mixing whose
formulation looks similar to that of strong irreducibility:
Definition 3.1.20. -subshift X is topologically mixing if for any trvo subsets
S and T of , there exists such that for all p with the property that
79
, and for any elements , , there exists such that
and .
The difference in the two definitions is subtle but important: for strong irreducibility,
the distance that must be present between two shapes in order to make interpolation
possible is independent of the shapes involved, whereas in topological mixing, this
distance can depend on the shapes. This distinction is irrelevant in one dimension,
since strong irreducibility and topological mixing are the same concept for -subshifts.
(To see this, note that for a -shift of finite type, a distance sufficient for interpolating
between two letters of the alphabet is sufficient to interpolate between any two words.)
However, strong irreducibility is a strictly stronger notion in more than one dimension.
Pertinent for our purposes is the fact that if for some in a stongly
irreducible shift of finite type , then the occurrence of at can only "force"
letters to appear in the region of wrttnn distance of . This is because for any
with and any , by the definition of strong irreducibility
there is some with and . For this reason, the checkerboard
island system is topologically mixing but not strongly irreducible. Armed with this
stronger hypothesis, we can now refine Possible Theorem 3.1.18 a bit more:
Possible Theorem 3.1.21. For any d and any strongly irreducible shift X
of finite type with uniform filling length R and positive topological entropy ,
there exist constants , , , , and such that for any n
and any word w , if we denote by the shift of finite type , then
80
.
In fact the above is now provable with correct choices for the pertinent constants,
and so we state our main result:
Theorem 3.1.22. For any d and any strongly irreducible shift X of finite
type with uniform filling length R and positive topological entropy , there exist
constants and such that for any n and any word w ,
if we denote by the shift of finite type , then
.
Before beginning with the preliminaries of a proof, we make an observation: our
example shifts of finite type used above to show the necessity of the constants
and in this statement did not actually show that and are not the
same; it is possible that , for all . However, we may now introduce
another example to show that in fact and must be distinct for certain .
Consider, again for any , and any dimension , the shift of finite type on
the alphabet {0, 1} defined by the set of forbidden words :
has at least two ones}. In other words, consists of all infinite words of zeroes
and ones on such that any two ones are a -distance of at least from each other.
By definition, is clearly a shift of finite type. We also claim that it is strongly
irreducible with : consider any words and such
that . Take defined by , , and
81
for any . We claim that : suppose, on the contrary, that .
Then there exist , such that , and . If , ,
then contains two ones a -distance less than apart and cannot be in , a
contradiction. We arrive at a similar contradiction if , . Clearly we cannot
have and since , and similarly it cannot be the case that
and . But since the only ones in are in or , we have exhausted
all possible cases. Therefore, . By definition, is strongly irreducible with
. We claim that in the language of Possible Theorem 3.1.21, it must be the
case that , and in fact that .
To prove this, we first make a definition: for any , we define the word with
shape by if and only if all coordinates of are equal to one modulo
. since it contains no two ones a -distance of less than apart. Let
us also for any define the word with shape where has as
a subword occupying the central , and has zeroes on all of . By the
definition of , any occurrence of in an element of forces an occurrence of
containing it. Therefore, as argued for , for any . However,
the size of the shape of is bigger than that of for any , and so for any
, , , and which satisfy Possible Theorem 3.1.21, it must be the case
that - for any . Although this does not show that the
bounds in Theorem 3.1.22 are optimal, it does show that must be at least
linear in , and so the value of for - attained in Theorem 3.1.22
can be improved by at most additive and multiplicative constants.
82
Before beginning to prove our main result, we now briefly outline the content of this
paper. The main idea in the proof of Theorem 3.1.22 is to use strong irreducibility
to find a word where and agree on , and then define a map which
replaces all occurrences of by in large words . In order to know how
many-to-one this map is, it is important to know how many times and appear in
a "typical" . In Section 3.2, we use ergodic measures of maximal entropy
to show that for fixed , any , and large , there are "many" words
in for which we have good bounds from above and below on the number of
occurrences of in . Namely, for a large set of , the number of occurrences of is
roughly , where is an ergodic measure of maximal entropy on . We then
use a result of Burton and Steif ([BuSl], ) to give upper and lower bounds on
of the type
There is a slight problem though; it is entirely possible that a replacement of
by could create a new occurrence of , which could make this replacement map
extremely unwieldy and hard to deal with. What we would like is a word such
that replacing by can never create a new occurrence of . Unfortunately, this
is impossible for some choices of . In Section 3.3, we prove a slightly weaker fact
that is still sufficient for our purposes; for any , there exists a subword
with not much smaller than for which there exists where
and agree on and where a replacement of by can never create a new
occurrence of .
Section 3.4 contains the proof of Theorem 3.1.22. The proof is done by considering
83
maps between and which either introduce or destroy occurrences of
(which is done by using the result of Section 3.3 to perform various replacements) , and
estimating the sizes of images or preimages under these maps. We can make certain
helpful assumptions about the words in which these replacements take place (such as
the approximate number of occurrences of ) by using the results of Section 3.2.
In Section 3.5, we deal with a simplified version of our main result where the word in
question is already chosen to have a nice property. (namely, that there exists such
that replacing by can neither accidentally create new or or destroy existing
or ) In this case, we prove that (In )
for any an ergodic measure of maximal entropy on and an ergodic measure
of maximal entropy on . We then show that it is not possible to prove a lower
bound on of the form for constant .
In Section 3.6, we prove a corollary using our methods: for any alphabet , and
given any set of words , . . . , where the size of is much greater than that
of for , , where is the full shift. This can be seen
to be related to some of the so-called undecidability questions in shifts of finite
type; given a set of words, it is algorithmically undecidable whether or not
is nonempty. The corollary described gives a condition under which this question is
easily answered.
Finally, in Section 3.7, we give some open questions that arise in the course of proving
our results.
84
3.2 Some measure-theoretic preliminaries
We will now move towards proving Theorem 3.1.22. We first need a lemma about
strongly irreducible systems:
Lemma 3.2.1. For any -subshift which is strongly irreducible with uniform fill-
ing length and for any rectangular prism , , '
.
Proof: We first prove the first inequality: take any rectangular prism . For
any , since can be partitioned into disjoint copies of ,
, ' , ' Take natural logarithms of both sides and divide by
:
,
and by letting approach infinity, we see that , which implies
that , ' .
We prove the second inequality in almost the same way: again consider any rect-
angular prism . For any positive integer , can be
broken into copies of , and we can choose copies of inside each
so that the -distance between any pair of these is greater than
. This is illustrated in Figure 3.5.
(A note on figures: all figures in this paper are drawn with , but this is in some
sense without loss of generality; all of the ideas that we use can be illustrated via
85
Figure 3.5:
two-dimensional pictures. All constructions and descriptions are carried out in full
generality. )
By strong irreducibility, for any way of filling these copies of with words in
, the remainder can be filled to make a word in , ' . This
implies that , ' , ' . Take natural logarithms of
both sides and divide by :
,
and by letting approach infinity, we see that , or that
, ' .
86
To prove Theorem 3.1.22, we will be repeatedly using the concept of a measure of
maximal entropy.
Definition 3.2.2. A shift-invariant probability measure on a subshift X is called
a measure of maximal entropy if .
Such measures are said to have maximal entropy because of the following Variational
Principle:
Theorem 3.2.3. For any -subshift X, , where ranges over
all shift-invariant Borel probability measures on X. This supremum is achieved for
some .
See [M] for a proof. A useful observation is that since the extreme points of the
set of measures of maximal entropy are ergodic, and since the set of measures of
maximal entropy is nonempty for subshifts, any subshift also has an ergodic measure
of maximal entropy. (See [Wal] for details.) We need the following proposition:
Proposition 3.2.4. ( , p. 281, Proposition 1.20) Let be a measure of maximal
entropy for -shift of finite type . Then for any shape , the conditional
distribution of on given a fixed word is uniform over all words
such that the word rvith shape (& ) defined by and
is in .
We have the following convenient restatement:
Proposition 3.2.5. For any -shift X of finite type t, and for any measure of
maximal entropy on X, and for any word w , and for any shape
87
, . In other words, any trvo words with the same shape which
agree on have the same measure under .
Proof: Consider any two words , with . We claim that
. Consider By definition,
and there exists such that . Suppose that . Then,
since and since , by definition, , a contradiction. Therefore,
. Since , this implies that . Therefore,
. We define and . Since , and since
, . Therefore, if we de-
fine , then since either or could fill while fills
, we may take and use Proposition 3.2.4 to see that
.
Lemma 3.2.6. For any strongly irreducible shift X of finite type t with uniform
filling length R, and for any measure of maximal entropy on X, and for any word
u with shape S a subset of ,
.
Proof: Before we begin the proof, we recall that for any positive integer , is
the boundary of thickness of , and that is the boundary of thickness of
88
the complement of , i.e. the set of all points for which there exists with
.
Fix . We begin by bounding from below. Choose any word
. We claim that . Consider any
and . By definition, there exists such that
. Also by definition, . Therefore, by the triangle inequality,
, as claimed. This means that by strong irreducibility, there exists a
word such that and .
By Proposition 3.2.5, .
The inequality comes from the fact that the number of words in with shape
with the fixed word on is clearly less than or equal
to the number of words in with shape For
clarity, we rewrite:
, (3.3)
If we sum (3.3) over all possible choices for , then we get
(3.4)
Note that all are distinct, and for all , . Therefore,
,
89
and so . Since ,
. By combining these facts with (3.4), we see that
,
We now bound from above. Choose any word with .
We wish to use Proposition 3.2.5 with as our . To do so, we need to know that
. The second containment is trivial. To prove the
first, suppose that . By definition, there then exists
such that . Since , in particular , or . Therefore,
since , by definition. We now apply Proposition 3.2.5:
(3.5)
We claim that ; choose any and .
Clearly . If , then , a contradiction. Thus, . This
implies that for any , and for any , there exists with
and . Therefore,
. By using this fact and summing (3.5) over all possible , we get
. (3.6)
Note that since all are distinct, , and so
90
. Also note that since all are distinct, but all have
, it must be the case that all are distinct, and so
.
Combining these facts with (3.6), we see that
,
which, along with the lower bound on already achieved, completes the proof.
To avoid confusion, from now on we use to denote an ergodic measure of maximal
entropy on a subshift , and to denote a shift-invariant probability measure which
may or may not be of maximal entropy.
Lemma 3.2.7. For any -subshift , and for any shift-invariant ergodic probability
measure on , and for any finite set of words , , ,
and , if we denote by the set of words in which
have be rween and occurrences of for all ,
then .
Proof: (For brevity, we use the shorthand notation for the mea-
sure of the union of all cylinder sets corresponding to words in Fix
any . Firstly, we notice that it is a simple consequence of Birkhoff's ergodic
theorem that : for each ,
91
for almost every ,
where a represents the by shifts on . Convergence almost everywhere
implies convergence in measure, meaning that
({ : for } . (3.7)
Denote by the set whose measure is taken on the lefthand side of
(3.7). Then whether or not lies in depends only on its values
on , where is the minimum integer such that all are subsets of some copy
of . Therefore, is a union of cylinder sets of words in .
It is not hard to see that for large , any word whose cylinder set is a subset of
is an element of . Combining this with the fact
that (3.7) is true for any , we see that .
We now write out the formula for the measure-theoretic entropy of :
,
where for and . Since is a measure-theoretic
generator for the a-algebra of Borel sets in , we know that . (For
more information on measure-theoretic and topological generators, see now
partition into the two pieces , , , , , and , , , , , :
92
, '
, ' .
To estimate each summand, we use the easily checkable fact that for any set of
nonnegative reals , , . . ., ( whose sum is , the maximum value of
occurs when all terms are equal, and is In . Using this, we see that the above sum
is bounded from above by
.
Since, as , approaches 1 and approaches
, the second term approaches zero as . By replacing by
1 in the limit in the first term, we see that
In ,
which was exactly what needed to be shown.
Corollary 3.2.8. For any strongly irreducible -shift X of finite type t with uniform
filling length R, for any , and for any positive integers k and M, denote by
the set of words u in (X) with be rween
93
and occurrences of
(X) for every word with shape . Then,
.
Proof: Using a combination of Lemmas 3.2.6 and 3.2.7 for any fixed an ergodic
measure of maximal entropy on shows that
.
And by the definition of topological entropy,
.
3.3 A replacement theorem
We must prove an auxiliary theorem about replacements which is mostly combinato-
rial in nature, and which will be integral in the proof of the upper bound portion of
Theorem 3.1.22.
Theorem 3.3.1. For any strongly irreducible -Markov shift with uniform filling
length , there exists depending on such that for any choice of
with , there exists a subword of , where , and
so that and agree on the boundary, and with the property that
94
replacing an occurrence of by in any element of cannot possibly create a nerv
occurrence of .
Proof: First let us make sure that the statement of Theorem 3.3.1 is totally clear.
What this means is that we find , such that is a subword of ,
and agree on the boundary, and such that the following is true: for any
with for some a copy of , if one defines by replacing
by , then for any a copy of such that , it must be the case that
1
1
. We define or
, whichever is
odd. Then, , (X) is, by Lemma 3.2.1, at least . This is
greater than the number of words with shape which occur as subwords of , and
so therefore there exists a word , (X) which is not a subword of . This allows
us to make a definition:
Definition 3.3.2. Given a subword u of w, choose a subword of u of shape
which does not contain any portion of the boundary of u, and use strong irreducibil-
ity to replace this subword by any word of shape which has a as the subword
occupying its central . The word that u has become after this replacement is called
a standard replacement of u, and so is any word created in this way.
Choosing the to be replaced to be disjoint from the boundary of ensures that
any standard replacement of agrees on the boundary with . This means that since
is a Markov shift, any occurrence of in a point can be replaced by a
standard replacement , and the resulting element of is still in .
Definition 3.3.3. A subword u of w has Property A if for every standard
95
Figure 3.6: A standard replacement of
replacement of , replacing by in some could possibly create a nerv
occurrence of . In other words, for every standard replacement of , there exists
and , copies of such that , , and if we define
by replacing by , then .
Clearly, if we can find a subword of which is large enough and does not have
Property , we will be done.
The organization of this induction is a bit odd, so we give a quick overview. We will
construct a sequence of subwords of , where and each is a subword of
the previous. Each has shape a cube. We will be able to show that one of these
does not have Property , and that it is large enough in the sense of Theorem 3.3.1.
However, the construction of these depends on a fact about periodicity of subwords
of which have Property , which we must prove first. We will set up and prove
96
this periodicity fact for any even though has not yet been defined for .
This is not a problem though; this proof depends only on being a subword of ,
which will be clearly true once the definitions of are able to be made.
Let's assume that has Property A for some . For the purpose of the following
constructions, it is helpful to picture as fixed in space, so say that has shape
, i.e. the cube with size which lies entirely within the positive octant of
and has a vertex at (1, 1, , 1). To make sure to distinguish it from other copies of
, we call the shape that this fixed occurrence of occupies . We take a copy
of or (call it , and its size ), where the size
is chosen to have the same parity as , and which is central in , and partition
it into or disjoint copies of . Consider only
the interior copies of in this partition, i.e. the ones which are disjoint from the
boundary of . For large , there are more than of these, and to each one
we may associate a standard replacement of , and since has Property , also
a copy of which overlaps which could somehow be filled with at the same
time that is filled with the standard replacement in question. We use to denote
the set (possibly with repetitions) of these copies of .
Recall that each of these represents a possible new occurrence of created by per-
forming a standard replacement. Since any of the standard replacements that we
would perform is done by changing only letters in a particular in , it must
be the case that every element of contains some portion of its associated .
(Otherwise, the supposed "new" occurrence of would have already existed before
97
Figure 3.7: A sample element of
the replacement.) Also, since every standard replacement results in some occurrence
of in , and since is not a subword of , none of the elements in contains
all of its associated . In Figure 3.7, the element of shown, which we call
, is associated to the standard replacement given by changing the letters in the
highlighted .
We first make the claim that contains no repeated elements, i.e. that two distinct
copies of must be associated to distinct elements of .
In Figure 3.8, suppose that is associated to the standard replacements correspond-
ing to each of and , the two highlighted copies of . This means that there
98
Figure 3.8: An element of associated to two standard replacements
exists a word with and , where is a standard
replacement of made by changing only the letters in . The letters in must
be changed from their values in in order for the occurrence of in to be "new."
Therefore, , and . Similarly, there exists
a word with , , and
. Since and are disjoint, this implies that and
, and so that . But ,
and since we have a contradiction. Now we know that consists of more
than 2 distinct copies of .
99
Definition 3.3.4. A suboctant of is a subcube of which shares vertices with
both and , is co ntained in , and whose intersection with contains only the
shared vertex. (See Figure 3.9.)
Figure 3.9: The suboctants of
It is fairly clear upon observation that each element of must contain some suboc-
tant of , since each element of contains some portion of . Since has more
than distinct elements, there is ssoomm suboctant which is contained in more
than of the copies of in .
We now prove a fact about the periodicity of a set which is contained in two elements
of . Suppose that two distinct elements and of are given such that ,
which we denote by , is a multiple of for some . We make the additional
too
assumption that both S and contain some suboctant O of , and assume without
loss of generality that is the least suboctant lexicographically of , i.e. has the
point (1, , 1) as a vertex, and that is a negative multiple of . (This is without
loss of generality because one can make these assumptions simply by renaming and
reflecting several times, which does not affect our proof.) We will show
that certain portions of must be periodic based just on these hypotheses.
Figure 3.10: Elements , of whose difference is a multiple of
In Figure 3.10, is any point of such that is also in , is the suboctant
of opposite , is the vertex shared by and , is the vertex of opposite
101
, is the vertex of corresponding to in , and . and are
subcubes of and , respectively, which share vertices with and whose size is
, or the size of minus the size of . (The dotted line portions are copies
of to remind us of the definition of and , but are themselves irrelevant and
are not named.) We define to be , giving us two new points and .
Since , , they may each be filled with when is filled with the correct
standard replacement of . Call the copy of on which is altered to make
the standard replacement which allows to be filled with , and the copy of
on which is altered to make the standard replacement which allows to be
filled with . (A quick note: in several figures in this paper, we represent a point
by the vector which points from 0 to )
We first claim that if , , then , . Suppose that
, . Since contains some portion of , but does not contain all of , the
same can be said of ; contains some portion of , but not all of . Therefore,
some coordinate of is between and . (We always use the word
"between" in the inclusive sense.) The fact that has nonempty intersection with
also implies that all coordinates of are between and , since all
coordinates of all elements of are at lleuausutt . Since , every coordinate
of is between and . This implies that every coordinate of is nonpositive
and at least , and also that one coordinate of is at least . Then,
is in , and has one coordinate at least , and therefore does not
lie in , and so is not in or . Since , the same argument shows that
102
is in , but does not lie in or . Clearly, since and are disjoint from
the boundary of by their construction, , are not in or either.
Suppose that , , , . Then by noting that can be filled with
when is filled with a standard replacement of which agrees with outside
of , we can infer that (this is because corresponds
to ), and by noting that can be filled with when is filled with
a standard replacement of which agrees with outside of , we infer that
and . (This is because corresponds to
, and corresponds to ) This implies that .
This conclusion was dependent only on the fact that , , , .
We have already shown that this is true for any , , and so is periodic
with respect to .
Note that in the course of this argument, we have also shown that .
We claim that any pair of points in which are separated by are and
for some choice of , . To do this, we just determine from :
if , then every coordinate of is between and . As already
mentioned, all coordinates of are between and , and one coordinate
is between and . This implies that has all coordinates
between 1 and , and so is in , and that one coordinate is between 1 and ,
which implies that either does not lie in or lies in the boundary of , and, in
either case does not lie in or . Since , the same argument shows that
is in , but does not lie in or . We have then shown that and could
103
be any pair of points in separated by , and so the fact that in
the above argument shows that is also periodic with respect to .
We will use this fact momentarily; for now let's recall that we earlier showed that
some suboctant of is contained in more than distinct elements of . As
before, denote by the vertex of shared by and , and by the vertex of
opposite . It is clear upon observation that for any element of which contains
, the vertex of which corresponds to in must be contained in . Fix any
in . can be partitioned into sets where ranges over all
points in with , and by tthllee above comments, there are more than
distinct points in which are vertices of elements of which contain . By the
pigeonhole principle, this implies that one of the sets contains more
than of these vertices. Again by the pigeonhole principle, this implies that there
are two elements of , call them and , which contain and where is a
multiple of whose length is less than . We make the notation .
This in turn implies that is periodic with respect to on the regions above
described as and , and since these regions are dependent on and , we call
them and . Since this can be done for all , and are
periodic with respect to , , . . . , where for each , is a multiple
of with length less than . This implies that their lengths are less than as
well, since .
Definition 3.3.5. A word w is purely periodic if for some positive integers , ..., ,
it is periodic with respect to for .
104
We have then shown that if has Property , then there are regions and
as described above so that and are purely periodic with all periods
less than . In particular, the preceding is true for and . For
each 1 , we can then choose a multiple of which is a period for
and and which has length less than . We now choose a subword
of . For sufficiently large , we take to be the subword of with shape
and which still has , the vertex shared by and
, as a vertex. The purpose of this is to cause the forced purely periodic portion
of to contain a purely periodic central cube within . We will choose subsequent
to be purely periodic on a central cube as well, which we will denote by , and
so will always be a purely periodic subword of . In fact, for each , we will
choose so that is a subword of , and so each will be
periodic with respect to for . Due to the construction of , we can
take to have shape in . We also move in space to lie
entirely within the positive octant of with one vertex at (1, , 1) (in other words,
, so that the phrasing of the earlier arguments still works.
This choice of was done to create : from now on we will follow a different
inductive procedure. We need one more definition:
Definition 3.3.6. A superoctant of any (j 1) is a subcube which shares
vertices with both and , is contained in , and contains .
There is then a natural one-to-one correspondence between the superoctants and
suboctants of ; for every superoctant, there is exactly one suboctant which is a
105
subset of it. For each where has Property , we now describe how to
construct . For each such , we define to be the set of superoctants of
such that is periodic with respect to for . We denote the size of
by . Since is periodic with respect to each , and since
for a superoctant of , we have then already shown that contains , and
. We assume that for all , and
in fact this will be clear once the construction is finished.
Let's now suppose that for some , has Property A. The idea is that we take
to be a suitable subword of where is smaller than , but is strictly
larger than . To show this, we have to prove a couple of claims. Firstly, we claim
that any superoctant of on which is purely periodic with periods less than
and which contains must be periodic with respect to each , i.e. must be in .
Since , clearly for all .
We now claim that if contains any pair of opposite superoctants and of ,
then neither of the suboctants and associated to them can possibly be contained
in any element of .
We again assume without loss of generality that is the least suboctant lexicograph-
ically of . In Figure 3.11, (the portion of shaded) is purely periodic
with periods , and is the which is changed to make the standard replace-
ment corresponding to . We assume that and derive a contradiction.
We have denoted by the region , i.e. in corresponds to
in S. because , and for some , it is the case that
106
Figure 3.11: An element of which contains
consists of points whose coordinate is between and . We then
choose which is a multiple of such that is a subset of and
is a subset of which is disjoint from (this can be done since has length less
than ; some multiple of it is greater than , but still less than ) and take
and &|"1 . It must be the case that filling with a standard
replacement for in which no letters of are changed and at least some letters
in are changed can be done simultaneously with filling with . Call the
word with shape with this property . We can restate our assumptions then
107
by saying , , and . Since
in corresponds to in , and since , it must be the case that
. By periodicity of with respect to , .
Since in corresponds to in , and since , . Since
and and are disjoint, . Finally, by period-
icity of with respect to , . But we have then shown that
, a contradiction. Therefore, if two opposite superoctants are
contained in , then neither of the suboctants associated to them may be contained
in any element of .
'
'
Figure 3.12:
Finally, we may make our inductive step. Consider any and with Property
A. By the earlier argument, we may then conclude that there are subcubes and
108
as defined above so that and are purely periodic with periods at most
. However, in the proof of this, we made use of the fact that the suboctant of
corresponding to is contained in many elements of . Therefore, by the fact
just shown, one of or corresponds to a superoctant of which is not in .
First, we take a subword of , call it , obtained by removing the boundary of
thickness from . In other words, we take to be the subword whose shape is
the central of , which we call .
'
Figure 3.13:
and are now subwords of occupying suboctants of . By construc-
tion, and are also purely periodic with periods at most . However,
109
one of them is associated with a superoctant which is not in , and we may as-
sume that without loss of generality it is . Also, since the size of is at
least 10(2R+l) , and since the size of is at most , the overlap
between and is a cube whose size is at least . Denote this cube by .
is defined to be a subcube of which shares the same vertex with that
shares with , with the correct size so that the overlap between and is
central. In doing this, we reduce the size of by at most . is defined to be
. Then, since is a subword of , it is also purely periodic
with respect to each , and by construction, is central in , so indeed
has the necessary properties. Each superoctant in corresponds to a superoctant
in , and now occupies a superoctant of , call it , on which
is purely periodic with periods at most . We claim that this means that
as well. For each , choose a period of which is a multiple
of whose length is less than . For every , as already mentioned,
is periodic with respect to for . Now, consider any such that
for some fixed . Since the size of is much greater
than , there exists some linear combination with , call it , such
that and . Then, since is
a sum of periods for . since 1s
periodic with respect to Finally, since is
a sum of periods for , and therefore is itself a period of . Then, by
definition, is periodic with respect to as well, and since was arbitrary,
with respect to every for . By definition, this shows that .
110
Since corresponds to a superoctant of that is not in , contains at least
one more element than , and . We again move in space so that it
lies entirely within the positive octant of and has one vertex at (1, , 1). Since
, this implies that for .
We will show that this induction never need proceed beyond , and so in the
process will justify the claim already used that for all that
we consider.
If each for has Property , this means that must have more
than elements. But, there are only superoctants of , and so we have a
contradiction. This implies that some must not have Property , which we call
. is created by at most truncations of , each of which reduces the size by at
most , and so since for large enough , the size of is at least
n-1O . Since for large , for some constant
, we can then say that there exists for which In for
and some constant . Then, take so that A for . This
implies that for , . Since does not have Property , there
exists a standard replacement of , call it , which agrees on the boundary with
by definition of standard replacement, and with the property that replacing by
in some cannot possibly create a new occurrence of . Thus, Theorem 3.3.1
is proved.
nt
We can prove as a corollary a version of Theorem 3.3.1 for any strongly irreducible
shift of finite type:
Corollary 3.3.7. For any strongly irreducible -shift of finite type with uniform
filling length , there exists depending on such that for any choice of
with , there exists a subword of , with shape , where , and
so that and agree on the boundary of thickness , and with the
property that replacing an occurrence of by in an element of cannot possibly
create a nerv occurrence of .
Proof: Fix a strongly irreducible -shift of finite type and uniform filling length
. Take the alphabet whose letters are the elements of , i.e. the words
in the language of whose shape is , and then define a map from to
where for any , is the subword of which occupies , i.e. the
copy of whose least vertex lexicographically is . Then, is a Markov shift
with alphabet . The reader can check that is still strongly irreducible, but
with a uniform filling length of . In short, this is because two shapes which
are a distance of apart in an element of correspond to shapes a distance of
apart in for C.
Since is a strongly irreducible Markov shift, by Theorem 3.3.1 there exists
such that for any with , there exist a subword of
, with , and with the same shape as and which agrees on the
boundary with such that replacing with in cannot result in the
creation of a new occurrence of .
112
Now, take any word with . Although is defined
as a map from one subshift to another, it should be fairly clear that as defined,
it can also function as a map from to . So we can define
. For ease of notation, we define , so .
Then, by Theorem 3.3.1, we can find a subword of , with
, and which agrees with on the boundary so that replacing
with in any element of cannot create a new occurrence of . and
are then subwords of with shape which agree on the boundary
of thickness . We wish to show that replacing by in some
cannot possibly result in a new occurrence of . Suppose that this is not the
case. Then there is and two copies of , call them and , such that
, , and if we define by replacing by ,
then . If we apply to all of the objects in the above description,
we arrive at a contradiction to the definition of and . It is therefore the case
that replacing with in any cannot create a new occurrrence of
. Since is a subword of , is a subword of . ,
and the size of the shape of is , and so we
are done.
Corollary 3.3.7 is the main tool in the proof of Theorem 3.1.22; very roughly, the
idea is that for each occurrences of in some large word in , we destroy this
occurrence of by replacing the occurrence of which is a subword of it by .
113
The requirement that new occurrences of the destroyed words not appear during this
process is to ensure that the process of getting rid of these occurrences of takes
as few steps as possible. It is natural to wonder why we go to the trouble of dealing
with subwords in the statement of Corollary 3.3.7; i.e., why is it not possible, instead
of dealing with the intermediate step of taking a subword of , to just find a word
such that replacing by can never result in a new occurrence of being
created? The answer is that there are examples of strongly irreducible shifts of finite
type and words for which this is impossible! Here is a quick example.
Consider, for any dimension and any , the full shift , and the word
defined by if , and if
for and for some . then has zeroes at every point of
except the least lexicographically. We claim that for any , there is some
such that , and replacing by creates a new occurrence of
. Consider any . Suppose that contains a one, i.e. there is some
such that . Since , we can assume that . Consider
defined by taking 1, 1, , and for all other . Then,
. Create a new by replacing by . Then, it is not hard to
check that , and that is the
word consisting of all zeroes, and so not equal to . This means that the replacement
involved in changing to created a new occurrence of . The only other possibility
for is that is the word consisting of all zeroes, i.e. for all . If
this is the case, then define by taking 0, 1, , and
for all other . Again, . Create by replacing
114
by . Then, it is not hard to check that , and that had two
ones, and is thus not equal to . This means that in this case also, the replacement
involved in changing to created a new occurrence of . We have then shown
that for any , it is possible that a replacement of by could create a new
occurrence of , and therefore the extra step of taking subwords in Theorem 3.3.1
and Corollary 3.3.7 is in fact necessary.
3.4 The proof of the main result
Proof of Theorem 3.1.22: We take to be a strongly irreducible shift of finite
type . For any word in , we call the shift of finite type resulting
from removing from the language of . We begin by proving an upper bound
on for sufficiently large . By Corollary 3.3.7, as long as is
sufficiently large, there exists a subword of with and
with the same shape as and which agrees with on with the property
that replacing by cannot create new occurrences of .
For any , we will define a mapping : . will
actually be defined as a composition of three maps: ( : ,
: (, and : ( . To
define these we need a definition:
Definition 3.4.1. Trvo overlapping occurrences of the word which occur in copies
S and of are said to have overlap of type B if |S .
115
We point out an important property of this definition: given a fixed occurrence of ,
there are at most copies of which could be filled with an overlapping , and
so there are at most words which are made up of a pair of whose overlap is of
type B. Call these words , , . . . , , where , and call the shape of for
any . Given any , we define ( by finding each occurrence
of any of the within , and in each one, replacing the first lexicographically of
the two occurrences of which make up by . In order to make this operation
well-defined, we must specify an order for these replacements to be done in; let us
just choose the usual lexicographic order, and search for and replace each in turn.
(This means that we first replace the lexicographically first occurrence of , then
find the new lexicographically first occurrence of and replace it, and continue until
no remain. We then perform the same procedure for , , etc.) Since replacing
by can never create a new occurrence of , the resulting -word, which
we call (, contains no , i.e. contains no pair of occurrences of with overlap
of type B.
For any (, we define ( as follows: find the first
occurrence of lexicographically in (, and replace the which is a subword of
this occurrence of by . Denote by the word that becomes when its subword
is replaced by . Repeat this procedure until there are no occurrences of left,
and call the resulting word ( . There is one fact that we must check;
namely that when performing any of these replacements, we do not accidentally create
a new occurrence of . For a contradiction, assume that a particular replacement of
by could create a new occurrence of .
116
Figure 3.14: Intersecting occurrences of
In Figure 3.14, is a copy of which is filled with , is a copy of which is
filled with , is the on which letters are changed to change the word on
from to , is a copy of which will be filled with once the replacement
is done, is the copy of in corresponding to in , which will therefore be
filled with once the replacement is done, and is the copy of or
central in in which must lie, which comes from the proof
of Theorem 3.3.1. For the same reasons as in the proof of Theorem 3.3.1, cannot
contain all of , but must contain some nonempty subset of . Since the replacement
cannot possibly create a new occurrence of , must have already been filled with
117
before the replacement occurred. This implies that before the replacement,
and were filled with overlapping occurrences of . We claim that these two
occurrences had overlap of type . Since , and since the size of is at most
, the distance in the -direction between the center of and the
center of is less than for each . is central in , so
the center of is the same as the center of . Since is a subcube of whose
size is at most shorter the distance in the -direction between the center of
and the center of is less than for each . For the same reason, the
distance in the -direction between the center of and the center of is less than
for each . Finally, since intersects the boundary of , and since
has size , there exists for which the distance in the -direction
between the center of and the center of&is between and .
Putting all of these facts together, we see that there exists so that the
distance in the -direction between the center of and the center of is between
and , which
implies that for large enough , it is between and , which
implies that before the replacement, and were indeed filled with occurrences
of with overlap of type B. However, ( contained no pair of occurrences of
with overlap of type , and so since all replacements in the definition of involve
replacing some with , no new occurrences of can be created during these
replacements. Therefore, there can never be a pair of occurrences of with overlap
of type during the application of to a member of (. We therefore have
a contradiction. Our original assumption was wrong, and none of these replacements
ns
can create a new occurrence of . So, when these replacements are finished, we have
a word with shape , which we called ( , which has no occurrences of
.
The definition of is much simpler: for any , is the subword of
occupying its central . For any , we define .
We now claim that is in , i.e. can be extended to a configuration on
which is in and contains no occurrences of . To do this, we inductively define
a sequence of words , where and each has no occurrences of
. Take and . For any for , define as
follows: since , it can be extended to an infinite configuration in . Use
this fact to create a word which has as the word occupying
its central . We then create by performing the same replacements as
in the definitions of ( and then , in other words first finding and replacing any
occurrences of for any , and then finding and replacing any occurrences
of . For the same reasons as above, has no occurrences of . Since agrees
on the boundary of thickness with , , completing the inductive step
and allowing us to define for all . We also note that for any , since contained
no occurrences of or for any , any occurrences of these words in
must have had nonempty overlap with the newly created portion, i.e. must have been
contained in the boundary of thickness of . As a result, and
must agree on their respective central , since no replacements could have
affected that portion. This means that we may define the "limit" of the : for each
119
, since , there exists with . Since and agree
on their respective central , the limit of the exists, call it . Since
is a subshift, it is closed and so . Since the central of each is equal to
, is a subword of . Finally, since each has no occurrences of and
is a limit of the , has no occurrences of . This means that as
claimed.
We have now defined on all of . For any , we can then deal
with the restriction of to . Since the shape of is , any
element of has fewer than occurrences of ,
and since each has shape a subset of , any element of has fewer
than occurrences of for each . By Lemma 3.2.1,
We now bound in a similar fashion. First
let's look at a picture of for any . Recall that is the union of
two overlapping copies of , so is the union of two overlapping copies of
concentric with the original copies of . By the definition of type overlap,
there exists for which the distance in the -direction between the centers
of these two is between and .
In Figure 3.15, we denote the directio in question by , the two copies of
by and , and the distance in the -direction between the centers of and
by . We then define to be a rectangular prism which is a subset of a distance
of away from . The sizes of are in every direction but , and
in the direction
120
Figure 3.15:
Clearly by just taking very large we can assume that this dimension is greater
than . Since and , , by strong irreducibil-
ity . , , and
are all small in relation to for large enough , and asympotically ap-
proaches as , so for large , this bound is greater than Using
these bounds, we can rewrite the above statement about a little more
easily: every element of has fewer than
occurrences of and fewer than occurrences of any
for .
121
We now prove the upper bound on . We do this by proving
upper bounds on for any , on
( for any , and on for any . The
first upper bound is fairly straightforward: consider any . Since
, the total number of letters in which are part of an occurrence of any
is at most , which for large is less than
. Now, consider any . By
the previous reasoning, any differs from on less than
letters, and so the number of possible is at most
for large values of .
The second upper bound, the one on for any ,
is slightly more difficult. Consider any . Since is in the image
of ( has no occurrences of any . Consider any pair of overlapping occurrences of
in , say at and copies of . Then these occurrences of contain occurrences
of as subwords, say at and copies of with , , and
. Also define to be the copy of in which would be changed to change
to , and to be the corresponding copy of in . Since there are no
122
occurrences of , it must be the case that |T . This implies
that contains the central of for large , and so that contains .
Similarly, contains . Therefore, if is replaced by sometime during the
replacements defining , then will be changed to something other than , and if
is replaced by at some point in these replacements, then will be changed
to something other than . In other words, in any replacement involved in changing
to , if is changed from to , then all occurrences of with nonempty
overlap with are also changed. Since new occurrences of cannot be created during
these replacements, this implies that for any such . Note that we
have also shown that the copies of where replacements occur in the application of
must be disjoint. We now wish to bound from above the number of occurrences
of in for any . By the definition of , for
any , has at most occurrences of
. We now claim that each of the replacements involved in ( and could create at
most new occurrences of , which rests on an aperiodicity property of : namely,
for large , and for any with for and copies of ,
.
To show this, recall that in the definition of , we ensure that contains a sub-
word , (X) which is not a subword of . In addition, lies in the central
in . Also recall that is asubword of whose shape has size at
least . Together, these imply that for large , contains as a subword of its
central . Since and agree outside this central , and since is not a subword
of , this implies that any occurrences of in have nonempty intersection with its
123
central , and that there is at least one such occurrence of . Now consider
such that , where . Also consider a copy of such that
. There are two possibilities: either lies inside or does not lie inside
. If lies inside , then since , must have nonempty intersection with
the central of . Again since , must have nonempty intersection with
the central of as well. This implies that . However,
then is a period of . Since for large
, there is some positive integer so that lies in , but has empty
intersection with the empty central of . But by periodicity of with respect to
, , which gives a contradiction. Therefore, it must
be the case that does not lie inside . Since has nonempty intersection with the
central of , this implies that for large .
Now consider any replacement of by in the replacements defining ( and ,
and suppose that this replacement occurs at a copy of . Specifically, suppose
that , where , , and and agree outside of .
Also assume that a copy of is a location for an occurrence of newly created
in this replacement, i.e. , . Since and agree outside , and
must have nonempty intersection, meaning that any possible location for given
a fixed lies in a copy of concentric with . However, by the aperiodicity
fact about above, any , both of which contain newly created occurrences of
must satisfy . This means that at each replacement, there are no
more than newly created occurrences of . We now bound from above the total
number of replacements performed in applying ( to . As already
124
shown, for large the total number of occurrences of any in is
smaller than , and so the total number of occurrences
of created during these replacements is less than
, which is less than for large . We now
bound from above the total number of replacements performed in applying to
(. For this, we need to bound from above the total number of occurrences
of in ( itself had at most occurrences of
by definition of . While changing to (, less than
replacements are made. Each one of these could create at
most new occurrences of by the same reasoning we used for (we
just don't have any aperiodicity facts about to use.) Therefore, ( has less than
occurrences
of , which is less than for large . This
means that the number of replacements involved in changing ( to
is less than as well. Since each of these can
create at most new occurrences of , the number of occurrences of created
during these replacements is less than .
So, the total number of occurrences of created in the process of changing to
( is less than .
Since itself contained at most occurrences of
by definition of , this means that ( contains less than
occurrences of .
We now collect the three facts we need to bound from
125
above for any . Firstly, for any , we know that for any
a copy of which is the location of a replacement during the process of changing
( to . In other words, once is changed to
during the application of to (, that occurrence of will not be changed during
future replacements. Secondly, all replacements perfromed in the application of
to ( are disjoint. This means that knowing ( , along with knowing the
locations of all copies of where replacements occur in changing ( to ,
is enough to uniquely determine (. Finally, ( contains fewer than
occurrences of . This implies that for any
, , the
total number of subsets of the locations of occurrences of in which could have
been the locations of replacements in the application of .
Finally, we give an upper bound on for any , which is straight-
forward: any must have its central filled with . This means that
for large .
Putting all of these upper bounds together, we see that
. .
for constants independent of and and independent of . This implies that
.
126
We then take natural logarithms of both sides, divide by , and let
to get
,
and by using the definition of entropy and Corollary 3.2.8, we are left with
.
was arbitrary, so we may let it approach zero, leaving
.
A different tactic must be used to prove a lower bound for . We
in a sense proceed in the opposite way from our upper bound: we will define a
map which sends any word in to a subset of such that for any
, and are disjoint. This map will create occurrences of
instead of eliminating them.
We first need another auxiliary combinatorial theorem, again about a sort of lack of
periodicity.
Theorem 3.4.2. For any and any strongly irreducible -shift of finite
type with uniform filling length , there exists a constant dependent on such
that for all suffiffifficiently large , there is a word with the following
aperiodicity condition: there cannot exist trvo overlapping occurrences of such
that one has nonempty intersection with the empty central of the other.
127
Figure 3.16: Disallowed and allowed pairs of overlapping
Proof: To make the statement of Theorem 3.4.2 more clear, we refer to Figure 3.16,
which gives an example of a pair of overlapping occurrences of which is ruled out
by the given aperiodicity condition (left) and a pair which is not. (right)
We begin by giving a concrete example, for any fixed and , of an aperiodic
word in . For any , we define if any for
is not equal to 1 or . This leaves only where each of , , . . . , are 1 or
to be defined. We think of this undefined portion as a set of one-dimensional j-
letter words: for every , we think of the yet-to-be-defined
, , ,
as the letters of a -letter word. Now, to fill these portions in,
we define -letter words, which we will call , , . . . , , such that no two
may overlap each other, i.e. if the final letters of are equal to the initial letters
128
of for some , then and . We do this in the following way: the first
four letters of any are defined to be 0001, and the final four letters are defined to
be Ottt. The letters following the initial 0001 in any are defined as follows:
concatenate d-l th -letter words, determined by -digit binary expansion:
each 0 in the binary expansion corresponds to the word 001, and each 1 in the binary
expansion corresponds to Of 1. The remaining letters of which precede
the final Ottt are alternating zeroes and ones, beginning with a zero.
An example should be helpful: suppose that and . Then we create
four 18-letter words , , , and . The initial four letters of are 0001. The
next letters are dependent on the two-digit binary expansion of the
subscript 0: since it is 00, the next six letters are 001001. The next
letters are alternating zeroes and ones beginning with a zero, i.e. 0101, and the
final four letters are Otll. This gives . Using similar
reasoning, we see that , , and
000101101101010111.
We claim that this set of words has the nonoverlapping property described earlier.
Suppose that for some and , , the initial letters of are the
same as the final letters of . cannot equal 1 or 2, because the first letters
of would then be 0 or 00, and does not end with either of those words. So,
. Then the initial letters of begin with 000, and since the only place that
000 occurs in is at the beginning, this implies that , and since
contains distinct words, that .
129
We now, for every choice of , choose an , and define
for . Assigning the to the choices
for in a one-to-one way completes the definition of . We now make
the claim that is aperiodic. Suppose not; then there exists
with for such that for all such that
. Since could serve as a period as well, we may assume without loss of
generality that . We choose a vertex of based on : for each ,
if , . If , . In this way, we ensure that , and
therefore that . Since for and ,
by construction . Therefore, . However, again due to
construction, the only zeroes in lie at points whose first -1 coordinates are
either 1 or . This implies that the first coordinates of are either 1 or .
Let's denote by the -letter word where for ,
and by the -letter word where . Due to the
supposed periodicity of , the first letters of are the same as the final
letters of . Since no two distinct words in may overlap, and
. This implies that the first -1 coordinates of are the same as the first
Z-t coordinates of , and therefore that the first Z-t coordinates of are zero,
implying that , a contradiction. Thus, is aperiodic.
We now use as a tool to create, for any , a word with
the aperiodicity property outlined in the conclusion of Theorem 3.4.2: there cannot
exist two overlapping occurrences of such that one has nonempty intersection
with the empty central of the other. is defined to be 0 if or 2,
130
and defined to be 1 if . If , then .
Suppose that is periodic with respect to . Since our supposed overlap is of
the form described it must be the case that for . We can again
assume without loss of generality that . Choose a point of as follows:
for each , take if , and - 1 if . Choose
if , and if . Finally, take .
For any all of whose coordinates are zero or one the first Z-t coordinates of
are between 1 and , and the dth coordinate is 1 or 2, implying that .
This means that a copy of with its least vertex lexicographically at is a subset of
, call it . Since is composed entirely of points whose dth coordinate is 1 or 2,
is filled with zeroes. Again, for any point all of whose coordinates are zero or
one, the first coordinates of are between 1 and , the Z-dth coordinate
is 1, 2, , or , and the dth coordinate is between 1 and . Therefore, any such
is in , rmplying that a copy of with its least vertex lexicograhically at
is a subset of as well, which is then . By periodicity, must
be filled with zeroes as well. However, by construction, for any copy of which is
filled with zeroes in , the dth coordinate of its least vertex lexicographically is 1.
Since , it must be the case that . This implies that is periodic
with period , which implies that for as well, and
so , a contradiction. Therefore, has the desired aperiodicity property. Note,
however that this does not prove Theorem 3.4.2, since is a word in the full shift,
and there is no reason for it to be in .
We now turn to our shift of finite type . First, we will be constructing a word
131
for which is nonempty. Obviously, finding a word such that
is nonempty could be done by using the already proven upper bound for
, but this may require to have shape with very large size. We need the
shape of to have a small size to prove as tight a lower bound as possible, and for
our proof, we need a lower bound on for relatively small . For large ,
Lemma 3.2.1 gives an exponential lower bound for , but doesn't really tell us
anything about small . For this reason, we prove the following lemma:
Lemma 3.4.3. For any -subshift X with , and finite S ,
|S|.
Proof: We write where comes before in the usual lex-
icographical order for , and make the notation for all
. Suppose that . Then, since , it must
be the case that for some , . Since , this
means that for every word , there is a unique way to extend it to a word
in . In other words, for any , given , is forced. By shift-
invariance of , for any , given , is forced. Since is finite,
take . Then, consists of elements of within a d-distance
of less than from 0 and lexicographically less than 0. For this reason, we make
the notation { - n) : is less than 0 lexicographically}, where
. It is then clear that , and so we note that
forces . We need a few more pieces of notation; ,
{ : for , }, and
132
. We quickly note a few useful facts about these sets which can be checked by
the reader: , and . a
now claim that if forces for all , then forces for
any . We prove this claim by induction on .
For , the claim is fairly easy to check (and is in fact a classical theorem due
to Hedlund and Morse ([HeM]) ; it amounts to showing that if any consecutive
letters of any force the next, then any consecutive letters of force the next for
any . But this is clear; if , , . . . , force , then , . . . ,
force , and we can proceed like this indefinitely. Thus, the claim is proven
for . Now suppose that it is true for a fixed , and we will prove it for .
This proof will also be by induction; since we wish to show that forces
, and since , it suffices to show that
forces for every
. Fix any such , and suppose that
is given. We will show that is forced. Consider any
. We claim that
. Since , it suffices to
show that for
. Since
for , and
for , and since for
, it suffices to show that ( - n) for
. Consider any and any . By definition of
133
, , and for . By choice of ,
for . Therefore, for , and
. There are then two cases; if
any coordinate of is nonpositive, then , and if all coordinates are
positive, then by definition, . So, indeed
n) , and so for any ,
. This means that since ,
for any , forces . But now since
, by the inductive hypothesis 1s
in fact forced by . Since was arbitrary here, as
described above this shows that forces as claimed, and so by
induction we see that for any , if forces for all , then
forces for any .
We finally return to our original example of for which . Recall that
we showed that there is then some such that forces for all . By
the claim just shown, then forces for all . This then shows that
for any . Note that for all . Therefore,
for all . Since
for large and a constant independent
of , we see that for all , and so by definition of entropy,
. Therefore, , a
contradiction to the hypotheses. Our initial assumption was therefore wrong, and so
for all finite shapes .
134
Before moving on with our proof, we must comment on Lemma 3.4.3. In the course
of the proof, we show that if for some total order on which is preserved under
addition, some finite set , and some with for all , forces
, then the topological entropy of is zero. It is natural to wonder whether the
assumption about ordering is necessary. In fact it is:
Lemma 3.4.4. For any finite and such that there is no addition-
preserved total order on with respect to which is greater than all elements of ,
there exists a subshift such that forces for all , but .
Proof: Suppose that for some finite and , it is the case that for no
addition-preserved total order on is greater than all elements of . We claim
that this implies that lies in the convex hull of . To see this, suppose that does
not lie in the convex hull of . Then clearly there is a -dimensional hyperplane
of such that and lie on opposite sides of . Define the subspace of
which equals for any . Without loss of generality, we may assume that
, since such an assumption requires only a small rotation of . Then,
define an addition-preserved total order on by arbitrarily fixing one of the open
half-spaces that splits into and defining if . Then,
since and are on opposite sides of , for all , is on the same side of ,
and so either for all or for all . By reversing if necessary, we
may assume without loss of generality that is greater than all elements of under
. This is a contradiction, and so lies in the convex hull of .
135
To make things easier, by shift-invariance, we can without loss of generality assume
that . We will, for any such that 0 lies in the convex hull of ,
construct a subshift with positive topological entropy such that forces
for any . By decomposing the convex hull of into simplices, we can, for some
, find a linearly independent subset of of cardinality such that
the convex hull of contains 0 and is contained in a -dimensional subspace of ,
call it . Denote the elements of by , , , . Then there exist positive
reals , . . . , such that . Since all elements of are in , we can
take all to be rational, and so without loss of generality integers. This implies that
. Take for all . Take the d'-dimensional
parallelepiped contained in . One may then tessellate
with copies of . (Intersecting with on both sides
leads to a similar tessellation of by copies of ) If ' then choose
linearly independent , , in such that . We
will define , a subshift with alphabet , such that forces
for any , which clearly implies that forces for any as well.
Choose any Q. We define as follows: for any and ,
define . Due to the already mentioned
tessellation of by copies of and tessellation of by copies of ,
this defines on all of . Take to be the set of all elements of constructed in
this way. is not necessarily shift-invariant, but by the construction, it is invariant
under shifts by for and for . Since the collection
is linearly independent, this means that a finite
136
union of shifts of , call it X, is a shift-invariant set. It is also clear that X is closed,
and thus it is a subshift.
We first show that forces for any . By the definition of , it is
sufficient to show that forces for any and . Since ,
there exists some and such that .
Since , for some positive reals . For any , is
in unless the coefficient of is greater than or equal to . Therefore,
if for all 1 , then it must be the case that for
all . But then since as noted earlier, and since
for all , , with all coefficients
in . This implies that . We then showed that if for all
, then . In other words, there is some such
that . Fix this . Then, .
Say that for some . Then by definition of , since
and lie in the same copy of , it must be the case that . This
means that forced Since , this shows that
forces for any , and so that forces for any .
It remains to show that . Choose , for ,
. Then,
, for any . By the definition of , there are at least
ways to fill letters of on , and so we
see that This means that
137
for all , and therefore, by letting approach infinity, we see that
.
We claim that for a strongly irreducible shift of finite type , .
We define and
. Then , and so by strong irreducibility
, which is greater than by Lemma 3.4.3.
Since ,
4 .
Therefore, . Consider any . Then, since there
are copies of contained in , there are at most different
words in which are subwords of . Since , this means
that there is such that is not a subword of . Then, again using strong
irreducibility, we create such that for any , .
(See Figure 3.17.) Then, for any a copy of , contains a , and therefore
. Thus, is not a subword of , and so contains at least one point and
1s nonempty.
138
Figure 3.17: A point
We will use and to create, for , and for any , a word
such that there cannot exist two overlapping occurrences of
where one has nonempty intersection with the empty central of the other.
To do this, we first partition into disjoint copies of . The disjoint copies of
then have an obvious bijective correspondence to tthllee points of , illustrated in
Figure 3.18.
We then use each entry of to assign entries of to the corresponding in
For , if , then the least copy lexicographically of in
the corresponding to is filled with any word in , i.e. a word without
any occurrences of . If , then the least copy lexicographically of in
the corresponding to has occurrences of placed inside it, each one sharing
a vertex with it.
139
The remainder of I is then filled to make a word in by using strong irre-
ducibility, since all of the filled portions are a distance of at least from each
other. We claim that this word has the desired aperiodicity con-
dition. Suppose not; then there exist two overlapping occurrences of such that
one has nonempty overlap with the empty central of the other, which implies
that is periodic with respect to some with for .
We then define by defining to be the closest multiple of to for .
If two are equally close, choose either. In this way, we ensure that for
each . We make the notation . Since each coordinate of is
divisible by , has integer coordinates.
Figure 3.18: The correspondence between copies of and points in
140
Figure 3.19: How a copy of is filled if
Since for all , every coordinate of has absolute value at most
. This implies that either or is the difference between two overlapping
occurrences of , one of which has nonempty intersection with the empty central
of the other. Assume that the latter is the case. Then, by the already proven
aperiodicity condition on , this implies that there exist , such that
. Without loss of generality, we assume that and
.
Let's call the central in the in corresponding to and the
central in the in corresponding ttoo . Then , and
is periodic with respect to , .
. Since every coordinate of is at most , ,
and hence , is nonempty. In fact, it is a rectangular prism where
. Therefore, contains one of
141
the copies of in which share a vertex with . Since , and since
is the central in the corresponding to , every one of these subcubes
of contains an occurrence of in . Therefore, has as a
subword. However, since , is a subword of .
Since , and since is the central of the corresponding to
, contains no occurrences of . Therefore, contains
no occurrences of either. Since , we have a
contradiction.
The only remaining case is when , i.e. for . We then simply
take an integer multiple of such that some coordinate of is greater than ,
but at most . Then, is also a period of , and we can repeat the argument
just made for the same contradiction.
Figure 3.20:
142
We now return to our proof of the lower bound on . We suppose
that our word which we are removing from has .
Take to be the smallest integer such that (0-4)W . Then, (0-4)W
, and so . We also define . By the definition of ,
. Take to be any ergodic measure of maximal
entropy on . Since
,
there must exist some word , such that . We note that
since , , , (X). By Lemma 3.2.1, ,
Therefore,
This means that by using Lemma 3.2.7, we see that if, for any , we denote
by the set of words in which have at least
occurrences of , then .
In Figure 3.20, we show a word constructed as follows: the copy of
is filled with as constructed in Theorem 3.4.2, and the central is filled
with . The remaining shaded portion is filled using strong irreducibility to create a
word .
We may now finally describe our map . Consider any . By definition,
has at least occurrences of . We choose a set of disjoint
occurrences of using a simple algorithm: choose any occurrence of to begin, call
it . At most 3 occurrences of overlap , and so we choose any occurrence
143
of which does not overlap , and call it . is any occurrence of which
does not overlap or , and we continue in this fashion. We are able to choose
at least disjoint occurrences of in in this way. We
then choose any nonempty subset of this chosen set of occurrences of , and for each
chosen occurrence of , if its shape is a copy of , we use strong irreducibility to
replace the central of by . is defined to be the set of words which
could be created by performing such replacements on . The cardinality of is
then at least for any .
We claim that for any . To show this, we
first show an auxiliary claim: that no occurrence of is ever incidentally created
in the replacement process of . In other words, when some occurrences of in
are replaced by words containing to create an element of , the
only occurrences of in the result are the ones which are subwords of each replaced
occurrence of . Suppose that this is not the case; that for some and
, contains an occurrence of which occupies a copy of , which we
call , which was not the central of a copy of which was occupied by one
of the replaced occurrences of in . Denote by the central of and by the
copy of in which is central. Then . Since , .
This implies that one of the replacements made had nonempty intersection with ,
otherwise , a contradiction. Call the where this replacement
was made , and call its central . By our hypothesis, was not one
of the replaced copies of , and so . Since all of the replacements made
were disjoint, . We know that as well. Since ,
144
. But, . Since ,
. It was part of the definition of that (0-4)W
, so . Therefore, .
We have then shown that . Since is central in and
is central in , and so as well. We make
one more notation: call the boundary of thickness of and the boundary
of thickness of . Since , . Then, since ,
. Also, , so ,
which implies that has nonempty intersection with the central of , a
contradiction to the aperiodicity property of .
We have then shown that the only occurrences of in any for some
are those which occupy the central of replaced occurrences of .
We also have a sort of converse result: for any such , , and for every a copy
which is filled with an occurrence of in which is replaced, the central of
is filled with in . This fact rests on the disjointness of the replacements made in
the definition of ; since these replacements are disjoint, each letter is changed at
most once.
Now, consider any for . Since , has at least one
occurrence of . Since the only occurrences of in come from replacements during
the application of , we know that for every a copy of with , if
we call the copy of in which is central, it must be the case that .
We also know that these are the only replacements performed in turning into ,
145
since any others would have resulted in more occurrences of . So, determines the
set of replacements which were made in . However, trivially outside of the
regions where replacements occurred, and so determines the letters of outside
regions where replacements occurred, as well. Therefore, is uniquely determined by
, and so we know that for , .
Since for
, we have shown that
for large . Take natural logarithms of both sides, divide by , and let to
see that
.
Since was arbitrary, we allow it to approach zero, and so
III 2 . ,
which for large enough , gives
,
or, by replacing by its maximum possible value ,
.
146
Combining this with the earlier upper bound on , we have
.
3.5 A closer look at the main result
We here wish to briefly review the proof of Theorem 3.1.22, and point out that most
of the complications encountered in the proof were due to possible problems with
periodicity of . If some assumptions about aperiodicity are made, the proof can
be simplified significantly. We will skip some of the details of these proofs, as they
are just simplified versions of arguments already made in the main text.
Theorem 3.5.1. For any strongly irreducible shift X of finite type with uniform
filling length R and positive topological entropy , and for any words w,
(X) such that w and agree on the boundary of thickness t and any replacement
of w by or vice versa cannot create or destroy any other occurrences of w and ,
if we denote by the shift of finite type , then for any an ergodic measure
of maximal entropy on and any an ergodic measure of maximal entropy on X,
.
Proof: To prove an upper bound on , define a mapping (similar
to from the upper bound portion of the proof of Theorem 3.1.22) on :
147
given , one replaces the occurrences of by , going in order lexico-
graphically. Since none of these replacements can make new occurrences of , this
process terminates. The word occupying the central of the resulting word is then in
for the same reasons as before, and we call this word . We then wish to
bound from above the size of 0 , , , , for any and any
ergodic measure of maximal entropy on . Recall that , , , , is the set of
words in which have between and
occurrences of for , .
Consider any , , , , . Because of the fact that occurrences of
and are not incidentally created nor destroyed during the replacements made in
the process of changing to , the word occupying a shape a copy of will be
changed from to at some point during these replacements if and only if .
If , then , since once an occurrence of is created, it cannot
be eliminated in any of the other replacements made in the process of changing
to . Therefore, any replacements made are at copies of such that
. We have then shown that if we denote by , . . . , the set of copies
of such that , then agrees with on , and for each ,
or . This shows that there are at most choices for , and
so since there are at most ways to fill with letters, that
But, , and . Therefore, , the number
of occurrences of in , is equal to , where is the number of occurrences of
in and is the number of occurrences of in . By definition of ,
and . By Proposition 3.2.5,
148
since and agree on their boundary of thickness . Therefore,
, and so we see that if 0 , , , , is nonempty,
then it has cardinality at most This implies that
.
Take natural logarithms of both sides, divide by , and let to get
,
and by using the definition of entropy and Lemma 3.2.7, we see that
.
Since is a measure of maximal entropy, and since can be arbitrarily small, we may
rearrange to arrive at
.
We could then use Lemma 3.2.6 to further bound this from above, but we leave the
bound as it is for now, to emphasize the fact that our upper bound comes from .
We can also give a similarly shortened proof of a lower bound on .
Define a map (similar to from the proof of the lower bound portion of Theo-
rem 3.1.22) from to as follows: for any which has
at least one occurrence of , take any nonempty subset of the occurrences of in
149
and replace them all by . It is possible to perform all of these replacements simulta-
neously because the hypotheses of Theorem 3.5.1 imply that the portions of any two
occurrences of which would need to be changed to turn them into are disjoint.
(If not, then a replacement of one of them by would destroy the other.) Therefore,
for any ergodic measure of maximal entropy on and for any , , , ,
. For exactly the same reasons as in the earlier lower bound
proof, for . Therefore,
.
Take natural logarithms of both sides, divide by , and let to see that
,
and by using Lemma 3.2.7 and letting approach zero since it is arbitrary,
(In ) .
Finally, we use the fact that is a measure of maximal entropy on to rewrite as
.
We recall that the upper and lower bounds in Theorem 3.1.16 (the one-dimensional
case) have a ratio bounded away from zero and infinity, but that we showed that it is
150
impossible to have such close bounds in the multidimensional case which depend only
on the size of . It is then natural to wonder whether or not it is possible, at least
under the hypotheses on from Theorem 3.5.1 and for large , to have a lower bound
of the form for . It turns out that this cannot be true if
there are multiple measures of maximal entropy. In one dimension, the uniqueness
of a measure of maximal entropy of any mixing shift of finite type is well-known,
but Burton and Steif ([BuSl], ) have shown that there are multidimensional
strongly irreducible shifts of finite type which have more than one measure of maximal
entropy. In order to show that this type of lower bound is too good to be true, we
need a lemma:
Lemma 3.5.2. If X is a strongly irreducible -shift of finite type t and if we denote
by the set of words w for which there exists where
and agree on the boundary of thickness t and such that replacing w by or vice
versa can never incidentally create nor destroy an occurrence of w or , then for
any ergodic measure of maximal entropy on X, .
Proof: We claim that as long as is sufficiently large, and has the property
that given any two disjoint copies and of contained in , ,
then . Consider any with the property just described. Then create
a standard replacement of in the same way as in the proof of Theorem 3.3.1, by
1
changing only on a central copy of . (Recall that or
and that is chosen so that there exists , (X) so that
is not a subword of . We before chose to be odd, but here we take it to have the
151
same parity as so that there is a central within ) We denote by the central
copy of on which is changed to create , and so .
We have four cases that we would like to show are impossible:
Case 1: Suppose that a replacement of by could possibly create a new occur-
rence of . More rigorously, that there exists and copies and of such
that , and if we define by the element of created by replacing by
, then , but . This means that and .
Since the central in is occupied by , this implies that , or else
would have to contain this occurrence of . However, in order for
to be a newly created occurrence of , it must be the case that has nonempty
overlap with , and so . By this upper bound on
, contains a cube of size at least , which must contain a copy
of disjoint from the very small sets and , call it .
Since , . Since is disjoint from ,
. Since , .
Therefore, . But, since , which
is greater than for large , and are disjoint copies of
, and so we have a contradiction.
Case 2: Suppose that a replacement of by could possibly destroy an existing
occurrence of . More rigorously, that there exists and copies and of
such that , and if we define by the element of created by replacing
152
by , then , but . This means that and
. Everything from here proceeds to a contradiction exactly as in Case 1.
Case 3: Suppose that a replacement of by could possibly destroy an existing
occurrence of . More rigorously, that there exists and copies and of
such that , and if we define by the element of created by replacing
by , then , but . This means that and .
However, since , it must be the case that has nonempty
intersection with . This again implies that . It is then possible
to choose a positive integer so that . Then choose
any a copy of so that , . Since , .
Since , . So, . In the same
way, we can see that , and since , and
are disjoint and so we have a contradiction.
Case 4: Suppose that a replacement of by could possibly create a new occur-
rence of . More rigorously, that there exists and copies and of such
that , and if we define by the element of created by replacing by
, then , but . This means that and .
However, since , it must be the case that has nonempty
intersection with . This again implies that . It is then pos-
sible to choose a positive integer so that . Then,
choose any a copy of so that , , and both are disjoint
from . Then, since , . Since ,
153
. So, . In the same way, we can
see that . Since and are disjoint from
, and . Therefore,
. Since , and are disjoint
and so we have a contradiction.
Therefore, as long as has for and disjoint copies of in ,
. This implies that
.
(3.8)
We can now use Lemma 3.2.6 to see that for any , any with
, and any ergodic measure of maximal entropy on ,
,
Since ,
.
Since , for
large , and so by strong irreducibility,
,
154
which is at least by Lemma 3.2.1. Combining this with shift-invariance
of and (3.8), we see that
Again by Lemma 3.2.1, Therefore,
,
which clearly approaches zero as .
Now, suppose that for any strongly irreducible -shift of finite type , there exist
constants , and an ergodic measure of maximal entropy on such that
for any with , . For a contradiction,
choose any with more than one measure of maximal entropy. Since the extreme
points of the set of measures of maximal entropy are the ergodic measures of maximal
entropy, there must exist some ergodic measure of maximal entropy on .
Then we have
(3.9)
for all with . However, since and are ergodic, they must be
mutually singular. Therefore, for any , there exists some open set such that
and . By Lemma 3.5.2, for large enough ,
155
and obviously . Since is an open set in , it is a union of cylinder
sets. This means that there exists so that for any , there exists some
a union of cylinder sets of words in with , and
again . However, we assumed that
(2 In ) for all and , and so since is a union of cylinder
sets associated to -words, for any we may sum (3.9) over to see
that ( In ) , and so ( In 2) , a contradiction
for small enough . This implies that if , then there does not exist a lower
bound on of the form which holds for all words
for sufficiently large .
3.6 An application to an undecidability question
One of the complexities of multidimensional symbolic dynamics is that it is algorith-
mically undecidable, given just the set of forbidden words, whether or not a shift
of finite type in is nonempty. (See [B], [R], [Wan] for details.) One application of
Corollary 3.3.7 is a condition under which is nonempty:
Theorem 3.6.1. For any alphabet , there exist , such that for any
and any finite set of words satisfying
and for , .
To prove this, we need the following lemma:
Lemma 3.6.2. For any strongly irreducible -shift of finite type with
uniform filling length , there exist , dependent only on such that for
156
any with , if we denote by the shift of
finite type , then there is some a subword of such that , is
nonempty and strongly irreducible with uniform filling length at most .
Proof: Suppose that such a shift is given. By Corollary 3.3.7, there exists such
that for any with , there exist , such that is a
subword of , and agree on , and replacing an occurrence of by in an
element of cannot possibly create a new occurrence of . (We are not using the
full force of Corollary 3.3.7 here, in that we do not care about the size of , only
that exists.) By reviewing the proof of Corollary 3.3.7, we see that a sufficient
condition for the existence of is that
'
for some constant depending only on . Some algebraic manipulation shows that
the above is implied if . By Lemma 3.2.1,
, so . Therefore, it is sufficient to have
In . Since and , for any a sufficient
condition is . There is a constant dependent
only on so that if , . For such , it would be enough to have
, or by dividing both sides by and then squaring
both sides, for some constant dependent only on . So, as long as
, such a exists.
Consider any two shapes , such that , and any words
157
and . Since , there exists such
that . Similarly, there exists such that . For
any , by definition there exists such that . Similarly,
for any , there exists such that . But ,
so . By the triangle inequality, . Therefore, since , were
arbitrary, , and so by strong irreducibility of there
exists such that and . We now fix any
ordering of the elements of with a least element (say lexicographically with respect
to polar coordinates) and replace each element of by in turn with respect to
this order. In this way, we eventually arrive at which has no occurrences of
and is thus an element of . Note that since and
are words in , they had no occurrences of . Therefore, any of the replaced
occurrences of had nonempty intersection with
Consider such a replaced occurrence which occupies a copy of . From the fact
just noted, there exists such that . This implies that
and . Therefore, since the size of is , is disjoint
from both and . Since is an arbitrary replaced occurrence of , this implies
that remained unchanged on and throughout the process of changing it to ,
and so and . By definition, we have shown that
, is nonempty and strongly irreducible with uniform filling length at most .
Proof of Theorem 3.6.1: We prove Theorem 3.6.1 by induction. Our inductive
158
hypothesis is that for any as described in the hypotheses, contains a strongly
irreducible shift of finite type with uniform filling length less than . First note
that by Theorem 3.1.22 and Lemma 3.6.2, there certainly exists such that for
any word with , there is a subword of such that is
nonempty and strongly irreducible with uniform filling length . We take
this to be greater than the from Lemma 3.6.2, and take our to be ,
where is from Lemma 3.6.2. Now suppose the hypothesis to be true for , and
consider any , , . . . , satisfying the hypotheses of Theorem 3.6.1.
By the inductive hypothesis, contains a strongly irreducible shift
of finite type with uniform filling length . There are two cases: either
or not. If , then , and so since
, in this case contains a strongly irreducible shift
of finite type with uniform filling length and the inductive
hypothesis is verified for . So, we suppose that . We will show
that . By the hypotheses of Theorem 3.6.1, we see
that Since the largest
size of a word in is , , and so . Finally,
. Therefore, satisfies the hypotheses of Lemma 3.6.2 and so there
is a subword of such that is nonempty and strongly irreducible
with uniform filling length less than 42 . Also, ,
and so the induction is complete. We have then shown that for any , contains
a nonempty shift and is therefore nonempty itself.
159
3.7 Questions
A few questions suggest themselves based on our results. The first, and perhaps most
obvious, is simply how the bounds in Theorem 3.1.22 could be improved. (We suspect
that at least the lower bound is far from optimal.)
Question 3.7.1. Can the constants and in the statement of Possible Theo-
rem 3.1.21 be improved from their values in Theorem 3.1.22 l.?
We know at least that the gap between and can be improved only up to
possible additive and multiplicative constants; we showed earlier that there are ex-
amples which force for strongly irreducible shifts of finite type with
arbitrarily large , and our Theorem 3.1.22 has . However, it
would be nice to achieve optimal values.
Next, recall that we showed in the introduction that no result nearly as strong as
Theorem 3.1.22 can be true for shifts of finite type which are only assumed to be
topologically mixing. However, it is probable that something can be said. So, we can
ask
Question 3.7.2. If is a topologically mixing -shift of finite type with
positive topological entropy , and if we denote by the shift of finite type
, then is it true that for every , there exists such that for all
with , ? If so, can anything be said about
the rate at which approaches zero as the size of
approaches infinity ?
160
If it is the case that approaches zero as , then it seems
likely that some new techniques would be necessary for a proof, since there exist
non-strongly irreducible shifts of finite type whose languages contain words for
which there exists no word agreeing with on its border. For example,
in the checkerboard island shift , any square word which is a finite portion of a
checkerboard is forced by its boundary.
161
BIBLIOGRAPHY
[B] ROBERT BERGER, The undecidability of the domino problem, Mem. Amer.
Math. Soc. 66 (1966)
[Be] VITALY BERGELSON, Ergodic Ramsey Theory- an Update, Ergodic Theory
of -actions, M. Pollicott and K. Schmidt, editors, London Math. Soc.
Lecture Notes Series 228, Cambridge University Press (1996), 1-61.
[BeL] VITALY BERGELSON AND ALEXANDER LEIBIVIAN, Polynomial extensions
of van der Waerden's and Szemeredi's theorems, Journal of AMS 9 (1996),
no. 3, 725-753.
[Bi] G.D. BIRKHOFF, Proof of the ergodic theorem, Proc. Nat. Acad. Sci. USA,
17 (1931) 656-660.
[Bou] JEAN BOURGAIN, Poin rwise ergodic theorems for arithmetic sets, Publ.
Math. IHES 69 (1989), no. 3, 5-45.
[Bou2] JEAN BOURGAIN, On poin rwise ergodic theorems for arithmetic sets, C. R.
Acad. Sci. Paris Sir. I Math. 305 (1987), no. 10, 397-402.
[BoyLR] MICHAEL BOYLE, DOUGLAS LIND, AND DANIEL RUDOLPH, The auto-
morphism group of a shift of finite type, Trans. Amer. Math. Soc., 306
(1988), no. 1, 71-114.
[BuSl] ROBERT BURTON AND JEFFREY STEIF, Non-uniqueness of measures of
maximal entropy, Ergodic Theory Dynam. Systems, 14 (1994), no. 2. 213-
235.
[BuS2] ROBERT BURTON AND JEFFREY STEIF, Nerv results on measures of
imal entropy, Israel J. Math. 89 (1995), nos. 1-3, 275-300.
[Fa] BASSAIVI FAYAD, Analytic mixing reparametrizations of irrational florvs, Er-
godic Theory Dynam. Systems 22 (2002), no. 2, 437-468.
162
[Fu]
HILLEL FURSTENBERG, Strict ergodicity and transformation of the torus,
Amer. J. Math. 83 (1961), 573-601.
[GO1] LEO GUIBAS AND ANDREW ODLYZKO, 6aximal prefix-synchronized codes,
SIAM J. Appl. Math. 35 (1978), 401-418.
[GO2] LEO GUIBAS AND ANDREW ODLYZKO, Periods in strings, J. Combin. The-
ory Ser. A, 30 (1981), 19-42.
[HaK] FRANK HAHN AND YITZHAK KATZNELSON, On the entropy of uniquely
ergodic transformations, Trans. Amer. Math. Soc. 126 (1967), 335-360.
[HaW] G.H. HARDY AND E.IVI. WRIGHT, An introduction to the theory of num-
bers, Clarendon Press, 1979.
[HeM] GUSTAV HEDLUND AND MARSTON Morse, Symbolic dynamics, Amer. J.
Math., 60 (1938), no. 4, 815-866.
[L] DOUGLAS LIND, Perturbations of shifts of finite type, Siam J. Discrete
Math. 2 (1989), no. 3, 350-365.
[LM DOUGLAS LIND AND BRIAN Marcus, An Introduction to Symbolic Dy-
namics and Coding, Cambridge University Press, 1995.
[M] MICHAEL MISIUREWICZ, A short proof of the variational principle for
-action on a compact space, Asterisque 40 (1975), 147-157.
[QS] ANTHONY QUAS AND A.A. §AHIN, Entropy gaps and locally maximal en-
tropy in subshifts, Ergodic Theory Dynam. Systems 23 (2003), 1227-
1245.
[QT] ANTHONY QUAS AND PAUL Trow, Subshifts of multi-dimensional shifts
of finite type, Ergodic Theory Dynam. Systems 20 (2000), no. 3, 859-874.
[R] RAPHAEL IVI. ROBINSON, Undecidability and nonperiodicity for tilings of
the plane, Invent. Math 12 (1971), 177-209.
[Wal] PETER WALTERS, An Introduction to Ergodic Theory, Springer-Verlag,
1982.
[Wan] HAO WANG, Proving theorems by pattern recognition II, AT&T Bell Labs.
Tech. J. 40 (1961), 1-41.
163
[Wi]
MAacuteTEacute WIERDL, Poin rwise ergodic theorem along the prime numbers, Israel
J. Math. 64 (1988), no. 3, 315-336.
164