ABSTRACT
Title of dissertation: TWO EQUIVALENCE RELATIONS
IN SYMBOLIC DYNAMICS
Andrew Dykstra
Doctor of Philosophy, 2007
Dissertation directed by: Professor Mike Boyle
Department of Mathematics
A G-shift of finite type (G-SFT) is a shift of finite type which commutes with
the continuous action of a finite group G. We classify irreducible G-SFTs up to
right closing almost conjugacy, answering a question of Bill Parry.
Then, we derive a computable set of necessary and sufficient conditions for the
existence of a homomorphism from one shift of finite type to another. We consider
an equivalence relation on subshifts, called weak equivalence, which was introduced
and studied by Beal and Perrin. We classify arbitrary shifts of finite type up to
weak equivalence.
TWO EQUIVALENCE RELATIONS IN SYMBOLIC DYNAMICS
by
Andrew Dykstra
Dissertation submitted to the Faculty of the Graduate School of the
University of Maryland, College Park in partial fulfillment
of the requirements for the degree of
Doctor of Philosophy
2007
Advisory Committee:
Professor Mike Boyle, Chair/Advisor
Professor Michael Brin
Professor Brian Hunt
Professor Michael Jakobson
Professor Jim Purtilo
Dedication
To my parents Tim and Nancy, and to my partner John.
ii
Acknowledgements
I wish to thank a number of people whose support was essential to the writing
of this dissertation.
It was my great fortune to have Dr. Mike Boyle as my thesis advisor. Mike
always had good suggestions for problems to work on, as well as possible approaches
to solving those problems. Often I would come to him feeling discouraged, having
made only feeble progress on a particular problem; he would instantly suggest a way
to move forward with my ideas, or perhaps a new train of thought altogether. For
a couple of years we worked on some truly challenging problems, but were unable
to solve any of them completely. In this time, Mike taught me never to lose heart,
and to learn from my failures?failure is part of being a mathematician. Leading by
example, he taught me that success comes with optimism and perseverance. Thank
you, Mike, for believing in me more than I did.
My work at Maryland was also shaped by my colleagues in the Research Inter-
action Team (RIT) in symbolic dynamics. Led by Mike Boyle, the RIT consisted of
a small group of students and postdocs. Each week, we would meet to discuss our
research and significant papers from our field. I would especially like to thank RIT
participants Angela Desai, Todd Fisher, and Nick Long, who provided a sounding
board for my ideas and taught me about the problems they were working on. Angela
was especially helpful when I first joined the RIT. She had already mastered the
fundamentals of symbolic dynamics and was willing to bring me up to speed. She
initiated regular meetings with me outside of the RIT, in which we read and dis-
cussed the book, An Introduction to Symbolic Dynamics and Coding, by Lind and
iii
Marcus [33]. Todd, a postdoc, brought a tremendous amount of enthusiasm and
expertise to the RIT. Todd demonstrated an ability to explain difficult concepts in
ways that even I could understand. Also, Todd offered me a great deal of profes-
sional and career advice. Nick opened my eyes to connections between symbolic
dynamics and K-theory and was an excellent listener when I presented my ideas.
I wish to thank my former housemate and friend, Andy Kebo. Though his re-
search is in harmonic analysis and quantum computation, Andy showed tremendous
interest in my work. He would ask compelling questions, and let me bounce ideas
off of him. I have fond memories of the long walks we would take, where we would
discuss our daily challenges and victories. Andy is one of the most thoughtful and
caring people I have ever met.
Lastly, I would like to thank my former housemates and friends Aaron Lott and
Yue Xiao for their consideration and emotional support. I am especially grateful to
Aaron, who taught me to typeset my work in LATEX and spent several hours helping
me with certain technical aspects of my thesis defense.
iv
Table of Contents
1 Introduction 1
2 Right closing almost conjugacy for G-shifts of finite type 10
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Background and definitions . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.1 Shifts of finite type . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.2 G-shifts of finite type . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.3 Skew products and matrices over Z+G . . . . . . . . . . . . . 13
2.3 Some useful results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.4 Right closing almost conjugacy for mixing free G-SFTs . . . . . . . . 19
2.5 General mixing G-SFTs . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.6 The irreducible but periodic case . . . . . . . . . . . . . . . . . . . . 26
2.7 Regular isomorphism of G-Markov chains . . . . . . . . . . . . . . . . 29
3 Weak equivalence for shifts of finite type 31
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2.1 Shifts of finite type . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2.2 Edge shifts . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2.3 Irreducible shifts of finite type . . . . . . . . . . . . . . . . . . 34
3.2.4 Reducible shifts of finite type . . . . . . . . . . . . . . . . . . 35
3.3 Homomorphisms between irreducible SFTs . . . . . . . . . . . . . . . 35
3.4 Extending homomorphisms defined on a nonwandering set . . . . . . 37
3.5 Homomorphisms between reducible SFTs . . . . . . . . . . . . . . . . 44
3.6 Weak equivalence of SFTs . . . . . . . . . . . . . . . . . . . . . . . . 45
Bibliography 49
v
Chapter 1
Introduction
We work in symbolic dynamics, focusing on the classification theory of one-
dimensional shifts of finite type. This classification theory is built on invariants,
which enable us to describe the similarities and differences between systems.
We begin with a discussion of Bernoulli shifts. For a natural number n, assign
to each element i of the set {0,...,n?1} a number pi, such that p0+???+pn?1 = 1.
Let X be the set of sequences x = (xi)i?Z where each xi ? {0,...,n?1}. Give to X
the sigma algebra A which is the product of the algebra of subsets of {0,...,n?1}.
Define a probability measure ? on X, given by ? = {p0,...,pn?1}Z. The triple
(X,A,?) is a probability space.
Define the shift map ? : X ? X by ?(x)i = xi+1 for each i ? Z. Then
? is a measure-preserving transformation of (X,A,?), and the dynamical system
(X,A,?,?) is a Bernoulli shift. As an example, the Bernoulli shift with n = 2 and
p0 = p1 = 12 corresponds to tossing a fair coin infinitely often (indexed by Z).
In the 1950?s, Kolmogorov and Sinai introduced measure-theoretic entropy as
an isomorphism invariant for measure-preserving transformations on a probability
space. They showed that the measure-theoretic entropy of a Bernoulli shift (as
above) is ?
n?1summationdisplay
i=0
pilogpi. It follows that not all Bernoulli shifts are measurably iso-
morphic, as Bernoulli shifts defined by different probabilities pi typically do not
1
have the same measure-theoretic entropy. Then in 1970, Ornstein [36] proved that
Bernoulli shifts of equal measure-theoretic entropy are measurably isomorphic. In
other words, not only is measure-theoretic entropy an isomorphism invariant for
Bernoulli shifts?it is a complete isomorphism invariant.
Often we think of the elements of {0,...,n?1} as states, and each coordinate
xk of a point x ? X represents one unit of time spent at state xk. For k > 0, we
think of the state xk as occurring in the future, x?k as having occurred in the past,
and x0 as the present state of x. A Bernoulli shift X has the property that, given
a state i ? {0,...,n? 1}, the probability that a point x ? X has i as its present
state is independent of the past or future states of x (the probability that x0 = i is
simply pi).
This motivates us to consider objects, more general than Bernoulli shifts, for
which we tolerate a certain amount of dependence on the past. Let A be an n?n
stochastic matrix. Then A is the adjacency matrix for the directed labeled graph
G which has n vertices {v0,...,vn?1} and, for each A(i,j) negationslash= 0, there is a directed
edge in G beginning at vi and ending at vj, labeled A(i,j). We let X be the set
of sequences x = (xi)i?Z such that each xi is a vertex in G, and each A(xi,xi+1) negationslash=
0. Then, with the appropriate sigma algebra A and measure ?, (X,A,?,?) is a
measure-preserving transformation called a Markov chain.
Example 1.0.1. Let
A =
?
??
?
.3 .7
1 0
?
??
?.
Then A is the adjacency matrix for the following directed graph.
2
d55d54d53d52d48d49d50d51v0.3 d54d54
.7 d34d34
d55d54d53d52d48d49d50d51v1
1
d98d98
Notice here that the probability of a particular present state depends on the past.
For example, if x?1 = v0, then the probability of x0 = v0 is .3 whereas, if x?1 = v1,
then the probability of x0 = v0 is 1.
The basic building blocks of Markov chains are the irreducible Markov chains.
Generalizing [36], Friedman and Ornstein [22] classify irreducible Markov chains up
to measurable isomorphism in terms of measure-theoretic entropy and one additional
invariant?period.
But not only are we interested in Markov chains as measurable objects. Also
we may think of Markov chains topologically, as follows. For a Markov chain X
and associated directed graph G having vertex set {v0,...,vn?1}, give to X ?
{v0,...,vn?1}Z the topology T which is the relative of the product of the discrete
topology on {v0,...,vn?1}. Then (X,T ) is compact and metrizable, and the shift
map? : (X,T ) ? (X,T ) is a homeomorphism. (X,T,?) is a topological dynamical
system called a shift of finite type (SFT).
The topological analogue of measurable isomorphism is topological conjugacy.
The problem of classifying SFTs up to topological conjugacy has turned out to
be more difficult than the problem of classifying Markov chains up to measurable
isomorphism. In fact, a complete set of invariants for topological conjugacy of
irreducible SFTs has yet to be found. However there do exist a number of weaker
equivalence relations up to which SFTs have been classified.
For an irreducible SFT X, there exists a Markov measure on X with respect
3
to which the measure-theoretic entropy of X is maximized. This maximal measure-
theoretic entropy of X is also the topological entropy of X (topological entropy
having been defined in 1965 by Adler, Konheim and McAndrew [3] as the topolog-
ical analogue of measure-theoretic entropy). In light of Friedman and Ornstein?s
work [22], it is natural to ask what, if anything, can be said topologically about
irreducible SFTs of equal period which are measurably isomorphic with respect to
their maximal-entropy measures.
This question is answered in the seminal paper of Adler and Marcus [4]. Here
they introduce an equivalence relation on SFTs, called almost conjugacy (AC), for
which topological entropy and period are complete invariants. SFTs X and Y are
almost conjugate if they admit a common SFT extensionZ, where the mapsZ ?X
and Z ? Y giving the extension are surjective and one-to-one almost everywhere.
Given irreducible SFTsX andY of equal period, with measures of maximal entropy
?X and ?Y respectively, X and Y are almost conjugate if and only if there exists a
measurable isomorphism (X,?X) ? (Y,?Y).
To this point, all Markov chains we have considered have been two-sided,
in the sense that they arise as Z-products. But also it is natural to consider N-
products?the one-sided Markov chains. In contrast to the two-sided setting where
the shift map is an isomorphism, the shift map on a one-sided Markov chain is
merely an endomorphism (it is typically non-invertible). Surprisingly, whereas two-
sided Bernoulli shifts are classified in terms of measure-theoretic entropy, it follows
from [40], [42] and [43] that distinct one-sided Bernoulli shifts of equal measure-
theoretic entropy are never measurably isomorphic. What invariants are necessary
4
and sufficient to classify one-sided Markov chains up to measurable isomorphism?
The answer to this question involves a class of maps between SFTs called
closing maps. The simplest examples of closing maps are resolving maps, which arise
from certain natural matrix equations, and which play a key role in the construction
of Adler and Marcus [4]. The (more general) closing maps are important to symbolic
dynamics because of their connections to algebraic invariants, and also because all
known general constructions of maps between SFTs involve closing maps. A map
between SFTs is right closing if it is injective on each unstable set of the domain,
and left closing if it is injective on each stable set of the domain. A map is closing if
it is right or left closing. If X and Y are irreducible SFTs with the same topological
entropy and period, then maps ?X : Z ? X and ?Y : Z ? Y giving an almost
conjugacy between X and Y may be chosen to be closing maps. However, in the
construction [4], it is not possible to construct ?X and ?Y that are either both right
closing or both left closing. (If one of ?X or ?Y is right closing, then the other will
be left closing.)
The importance of closing maps is emphasized by connections to regular iso-
morphism. Bill Parry introduces (and studies) regular ismomorphisms of two-sided
Markov chains, first in [20] and also in [37]. Roughly speaking, a measurable isomor-
phism of two-sided Markov chains ? : (X,?) ? (Y,?) is regular if knowing the past
and a bounded look into the future of a point x?X determines the present state of
the point ?(x) ?Y. Recall that almost conjugacies of SFTs X and Y correspond to
measurable isomorphisms of Markov chains (X,?X) and (Y,?Y), where ?X and ?Y
are the measures of maximal measure-theoretic entropy for X and Y respectively.
5
Perhaps there is some stronger form of almost conjugacy, corresponding to regular
isomorphism?
Yes, there is, and it is called right closing almost conjugacy (RCAC): SFTs X
and Y are right closing almost conjugate if they admit a common SFT extension Z,
where the maps Z ?X and Z ?Y giving the extension are surjective, one-to-one
almost everywhere, and right closing. In [15], irreducible SFTs are classified up
to RCAC in terms of topological entropy, period, and an algebraic invariant called
ideal class. Regular isomorphisms are exactly the measurable isomorphisms that
right closing almost conjugacies induce.
In [8], Ashley, Marcus and Tuncel find computable invariants with which to
classify one-sided Markov chains up to measurable isomorphism. As Boyle and Tun-
cel point out in [18], these include in particular all invariants of regular isomorphism
of two-sided Markov chains.
In chapter 2, we investigate RCAC, but in a more general setting than was
studied in the past. The objects we consider are called G-shifts of finite type (G-
SFTs), and the maps between G-SFTs are called G-maps. For a finite group G, a
G-SFT is an SFT equipped with a continuous and shift commuting G-action. A
G-map X ?Y between G-SFTs is a map of SFTs, equivariant with respect to the
G-actions on both X and Y. So a G-SFT is in particular an SFT, and may be
thought of as an SFT by simply ignoring the G-action. Similarly a G-map is in
particular a map of SFTs. The equivalence relations AC and RCAC are defined in
our new context by simply replacing ?SFT? with ?G-SFT? and ?map? with ?G-map?
in the respective definitions.
6
Our initial motivation to classify RCAC for irreducible G-SFTs was to answer
a question of Bill Parry [38]. Additionally, a classification of AC for irreducible
G-SFTs had appeared in [1] (and also in [37]), so the problem of classifying RCAC
for irreducible G-SFTs seemed natural. Also, there is a well-defined class of G-
SFTs (the ones where the G-action is free) which arise as skew products. The study
of skew products dates all the way back to von Neumann, and is of independent
interest.
In section 2.3, we generalize a number of results from the SFT context to
the G-SFT context, most noticeably with our Z+G Masking Lemma and our ZG
Replacement Theorem. Then in section 2.4 we show, somewhat surprisingly, that
for mixing G-SFTs arising as skew products, there are no new invariants of RCAC
that weren?t already invariants in the SFT context. This is not the case in general,
however, and in sections 2.5 and 2.6 we introduce some new invariants, and use
them to classify arbitrary irreducible G-SFTs up to RCAC. We conclude chapter 2
with a discussion of regular isomorphism in the G-SFT context.
In chapter 3, my co-author Joseph Barth and I study another equivalence re-
lation, called weak equivalence. As its name suggests, weak equivalence is a weak
relation?significantly weaker than AC or RCAC. Subshifts S and T are weak equiv-
alent if there exist full shifts ?n and ?m containing S and T, respectively, and maps
f : ?n ? ?m and g : ?m ? ?n such that f?1(T) = S and g?1(S) = T.
Weak equivalence was introduced and studied by Beal and Perrin in [9]. Their
main result is a classification of a very special class of irreducible SFTs (the so-
called flower shifts) up to weak equivalence. This begs the question of what would
7
be needed to classify arbitrary SFTs up to weak equivalence.
For an answer, first we investigate the structure of the most general class of
SFTs?reducible SFTs. Reducible SFTs are classified up to flow equivalence by
Huang in [23] and [24]; with Boyle, an alternative description appears in [11] and
[14]. Kim and Roush show in [26] that a solution to the problem of classifying
arbitrary SFTs up to topological conjugacy would follow from a solution in the
irreducible case.
We contribute to the theory of reducible SFTs in section 3.4 by introducing
the notion of a phase matrix for an SFT. We show that the set of phase matrices
for an SFT is a computable conjugacy invariant and, with Theorem 3.4.5, we give
necessary and sufficient conditions in terms of phase matrices for there to exist an
extension of a given map NW(S) ?NW(T) between nonwandering sets of SFTs S
and T to a map S ?T. This enables us in section 3.5 to classify when there exists
a map from one SFT to another. Then in section 3.6 we classify weak equivalence
for SFTs, by showing that SFTs S and T are weak equivalent if and only if there
exist maps S ?T and T ?S.
The centerpiece of our work is an extension result (Theorem 3.4.5). As out-
lined in section 3.1, extension results are significant to symbolic dynamics. In section
3.6 we indicate that our work may be relevant to a difficult open problem on ex-
tensions (Problem 3.6.8). This problem is derived from the work of Maass [34], and
is formulated in terms of steady maps. We mention a certain special class of SFT
pairs (S,T) such that there exists at least one map S ?T which fails to be steady.
AnaturalquestionrelatedtoTheorem3.4.5is, givenasurjectivemapNW(S) ?
8
NW(T) from the nonwandering set of and SFT S onto the nonwandering set of an
SFT T, what are necessary and sufficient conditions for there to exist an extension
of the given map to a surjective map S ? T? We hope to answer this question in
the near future but, as of now, all we can say is that the answer to this question
will certainly be nontrivial.
Also difficult and open is the question of when there exists a surjective map
from one SFT onto another. An answer to the question posed in the preceding
paragraph would provide a reduction of this question to the irreducible case. How-
ever the irreducible case has shown itself to be extraordinarily challenging, and will
certainly involve deep algebraic invariants.
Chapter 2 was published as a paper in the journal Colloquium Mathematicum.
Chapter 3 is a paper in preprint, soon to be submitted for publication.
9
Chapter 2
Right closing almost conjugacy for G-shifts of finite type
2.1 Introduction
For a finite group G, a G-shift of finite type (G-SFT) is a shift of finite type
(X,?) together with a continuous G action on X which commutes with the shift
?. For irreducible shifts of finite type, right closing almost conjugacy is classified
in terms of entropy, period, and an algebraic invariant called ideal class [15]. Bill
Parry [38] posed the following question: what additional invariants are necessary to
classify right closing almost conjugacy for irreducible G-SFTs? With Theorem 2.4.1
we show that for mixing G-SFTs where the G action is free, there are no additional
invariants. In section 2.5 we generalize Theorem 2.4.1 to mixing G-SFTs where the
G action is no longer assumed to be free. In section 2.6 we generalize further to
irreducible but periodic G-SFTs. As a corollary to our results we classify regular
isomorphism for G-Markov chains with respect to measures of maximal entropy.
Without the right closing assumption, almost conjugacy for irreducible G-
SFTs was classified by Roy Adler, Bruce Kitchens and Brian Marcus [1]. They were
working in a more general setting, but by modifying the proofs given here we can
arrive at the same classification of almost conjugacy for irreducible G-SFTs (as was
also done in [37]).
I thank Mike Boyle for many helpful discussions about this problem.
10
2.2 Background and definitions
We assume some familiarity with shifts of finite type; [29] and [33] provide
more complete backgrounds. All of the free G-SFTs we consider arise out of skew
products, as in [16]. The study of skew products dates back to von Neumann, in
the context of ergodic measure preserving transformations on a probability space.
For an example of more recent work with skew products in ergodic theory, see [21].
Also see [39] and [41] (and their references) for recent results with skew products in
Livsic theory.
2.2.1 Shifts of finite type
Let A be an n?n matrix over the nonnegative integers Z+. Then A is the
adjacency matrix for a directed graph, GA, which has vertices {v1,v2,...,vn}, and
the number of edges from vI to vJ is AIJ. Let EA = {edges in GA}, and put
?A = {x = (xi)i?Z ? (EA)Z|each xixi+1 is a path in GA}.
With the appropriate topology (the relative of the product of the discrete topology
on EA), ?A is a compact metric space. The shift on ?A is the homeomorphism
? : ?A ? ?A given by (?x)i = xi+1. The pair (?A,?) is the edge shift of finite type
(SFT) defined by A. Where ? is understood, we write just ?A to denote (?A,?).
A map between SFTs pi: ?A ? ?B is a continuous function such that pi ?
?(x) = ??pi(x) for all x? ?A. The map pi is one block if it is induced by a function
which sends each edge of GA to an edge of GB. A factor map is a surjective map.
An injective factor map is a conjugacy.
11
The matrixAis irreducible if for each entryAIJ ofAthere is a natural number
N such that (AN)IJ > 0. If A is irreducible we say also that the graph GA and the
edge SFT ?A are irreducible. The matrix A is primitive if there is a natural number
N such that for each entry AIJ of A, (AN)IJ > 0. If A is primitive we say also that
the graph GA is primitive; in this case the edge SFT ?A is mixing.
If ? is the Perron eigenvalue of A, then the entropy of ?A is log?. If v =
[v1,v2,...,vn]T is a right Perron eigenvector with entries in the ring Z[1/?], then
the ideal class of ?A is the class of the Z[1/?]-ideal which is generated by the
components v1,...,vn of v. A point x ? ?A is periodic if there exists a natural
number p such that ?p(x) = x. In this case p is a period of x; the smallest period of
x is called the least period of x. We define the period of the edge SFT ?A to be the
greatest common divisor of the set of periods of periodic points in ?A. The period
of the graph GA is the period of ?A.
Any SFT (X,?) is conjugate to some edge SFT (?A,?). Then, the terms
irreducible, mixing, entropy, ideal class and period apply to X exactly as they apply
to ?A. A point x?X is doubly transitive if both sets {?n(x): n? 0} and {?n: n?
0} are dense in X. Two pointsx = (xn)n?Z andy = (yn)n?Z inX are left asymptotic
if there is an integer n such that xk = yk for all k ? n. A map between SFTs
pi: X ? Y is 1-1 a.e. if it is injective on the set of doubly transitive points in X.
The map pi is right closing if, for each pair x,y ? X of distinct left asymptotic
points, pi(x) negationslash= pi(y). We say the SFTs X and Y are right closing almost conjugate
as SFTs if there is a third SFT Z which factors onto both X and Y by factor maps
which are 1-1 a.e. and right closing.
12
2.2.2 G-shifts of finite type
LetGbe a finite group. AG-SFT is an SFT (X,?) together with a continuous
right G action on X such that ?(x?g) = ?(x) ?g for all x ? X and g ? G. We
say the G-SFT X (or the G action on X) is free if, for each non-identity element g
of G, x?g negationslash= x for all x ? X. We say X (or the G action on X) is faithful if, for
each non-identity element g of G, there exists some x ? X such that x?g negationslash= x. If
Y is another G-SFT, then a G-map pi: X ? Y is a map between SFTs such that
pi(x?g) = pi(x)?g for all x ? X and g ? G. A G-factor map is a surjective G-map
and a G-conjugacy is an injective G-factor map. Two G-SFTs X and Y are right
closing almost conjugate as G-SFTs if there is a third G-SFT Z which factors onto
both X and Y by 1-1 a.e. and right closing G-factor maps. We point out that right
closing almost conjugate G-SFTs are in particular right closing almost conjugate
SFTs. The terms we define above for SFTs, such as irreducible, mixing, entropy,
ideal class and period, apply to a G-SFT X as they apply to X as an SFT.
2.2.3 Skew products and matrices over Z+G
By ZG we mean the integral group ring of G. We write an element x of ZG
as x = summationtextg?Gngg, where each ng ? Z. Then for each g in G we define pig(x) = ng.
If pig(x) > 0, then g is a summand of x. If pig(x) > 0 for each g in G, then we say
x is very positive and write x greatermuch 0. The augmentation of x is |x| = summationtextg?Gpig(x).
If A is a matrix over ZG, then A greatermuch 0 if AIJ greatermuch 0 for each entry AIJ of A. The
augmentation |A| is the matrix given by |A|IJ = |AIJ| for each entry AIJ of A. We
13
let Z+G = {x?ZG: pig(x) ? 0 for each g ?G}.
If G is a directed graph and l is a labeling of the edges of G by elements
of G, then we say (G,l) is a G-labeled graph. If A is a square matrix over Z+G,
then |A| is a square matrix over Z+ which, as before, is the adjacency matrix for
a directed graph G|A|. The matrix A corresponds to a G-labeled graph (G|A|,lA),
where lA is defined as follows: for each pair I, J of vertices in G|A|, AIJ = summationtextngg
if and only if for each g ? G exactly ng of the edges from I to J are lA-labeled
g. The edge labeling lA determines a function ?A: ?|A| ? G by ?A(x) = lA(x0) for
each x = (xn)n?Z in ?|A|. The function ?A is locally constant: for each x ? ?|A|, ?A
is constant on a neighborhood of x (here ?A is constant on {y ? ?|A||y0 = x0}).
The function ?A is the skewing function defined by A. Given two locally constant
functions ?1,?2: ?|A| ?G, we say ?1 is cohomologous to ?2 if there is another locally
constant h: ?|A| ?G such that ?1(x) = [h(?x)]?1 ??2(x)?h(x) for each x? ?|A|.
The Z+G matrix A determines an automorphism SA: ?|A|?G? ?|A|?G by
SA(x,g) = (?(x),?A(x)?g), where ?A is the skewing function defined by A. We say
the dynamical system (?|A| ?G,SA) is the skew product defined by A. There is a
free right G action on (?|A| ?G,SA) which commutes with the automorphism SA,
given by g: (x,h) mapsto? (x,h?g). Often we write just SA as an abbreviation for the
skew product (?|A| ?G,SA)
We can present the skew product SA as a free G-SFT (which we also denote
by SA) as follows. As an edge SFT SA has graph G, where the vertex set of G is the
product of the vertex set of G|A| with G, and for each edge e from I to J in G|A|,
for each g in G, there is an edge from (I,g) to (J,lA(e)?g) in G. For each pair of
14
vertices v, vprime of G we choose an ordering of the edges from v to vprime, and let g in G
act by the one block map given by the unique automorphism of G which acts on the
vertex set of G by (J,h) mapsto? (J,h?g), and which is order preserving.
In this way any skew product is a free G-SFT. Conversely, any free G-SFT is
G-conjugate to a skew product SA for some Z+G matrix A. We say a matrix A over
Z+G is very primitive if there exists a natural number N such that AN greatermuch 0. One
easily checks that A is very primitive if and only if the G-SFT SA is mixing.
Square matricesAandB over Z+Gare strong shift equivalent (SSE) over Z+G
if they are connected by a string of elementary moves of the following sort: there are
R and S over Z+G such that A = RS and B = SR. Parry has shown that A and
B are SSE over Z+G if and only if the skew products SA and SB are G-conjugate
[16, Prop. 2.7.1].
2.3 Some useful results
In this section we collect some results to be used later. We begin with the
known classification of right closing almost conjugacy for irreducible SFTs, which is
a corollary of [15, Theorem 7.1].
Theorem 2.3.1. Irreducible SFTs are right closing almost conjugate as SFTs if
and only if they have the same ideal class, entropy and period.
Lemma 2.3.2 (Z+G Masking Lemma). Let A and C be matrices over Z+G such
that the skew product SA is G-conjugate to a subsystem of the skew product SC.
Then there is a matrix B over Z+G such that A is a principal submatrix of B, and
15
SB and SC are G-conjugate skew products.
Proof. If SA is G-conjugate to a subsystem of SC, then A is SSE over Z+G to a
principal submatrix of C [16, Prop. 2.7.1]. Nasu?s original Masking Lemma for
matrices over Z [35, Lemma 3.18] also holds for matrices over an arbitrary semiring
containing 0 and 1 [13, Appendix 1]; in particular it holds for matrices over Z+G.
This means there is a matrix B over Z+G such that A is a principal submatrix of
B, and B is SSE over Z+G to C; SB and SC are G-conjugate skew products by [16,
Prop. 2.7.1].
Lemma 2.3.3. Let A and B be matrices over Z+G. A G-factor map pi: SA ?SB
induces a factor map pi: ?|A| ? ?|B| such that the skewing function ?A is coho-
mologous to ?B ?pi. Conversely, if pi: ?|A| ? ?|B| is a factor map such that ?A is
cohomologous to ?B ?pi, then pi induces a G-factor map pi: SA ? SB. The G-map
pi is 1-1 a.e. and right closing if and only if the map pi is 1-1 a.e. and right closing.
Proof. Letpi: SA ?SB be aG-factor map. Writepi = pi1?pi2, so that for an element
(x,g) ? ?|A| ?G, pi(x,g) = (pi1(x,g),pi2(x,g)). Let e denote the identity element
of G. Then pi: (x,g) mapsto? (pi1(x,e),pi2(x,e) ?g), since pi intertwines G actions. For
x ? ?|A|, set pi(x) = pi1(x,e) and h(x) = pi2(x,e), so that pi(x,g) = (pi(x),h(x)?g).
Look componentwise at the equality pi?SA = SB ?pi. The first component shows
that pi: ?|A| ? ?|B| is a well-defined factor map. The second component shows that
?A(x) = [h(?x)]?1 ?(?B ?pi)(x)?h(x) for each x ? ?|A|. Hence ?A is cohomologous
to ?B ?pi.
16
Conversely, suppose pi: ?|A| ? ?|B| is a factor map such that ?A is cohomolo-
gous to ?B?pi. Then there is a locally constant map h: ?|A| ?G such that for each
x ? ?|A|, ?A(x) = [h(?x)]?1 ?(?B ?pi)(x)?h(x). Define pi: ?|A| ?G ? ?|B| ?G by
pi(x,g) = (pi(x),h(x)?g). Observe that pi is a G-factor map.
For the last statement of the lemma, consider the following commutative dia-
gram, where the mapsqA: SA ? ?A andqB: SB ? ?B are each given by (x,g) mapsto?x.
SA pi d47d47
qA
d15d15
SB
qB
d15d15
?|A| pi d47d47 ?|B|
Both maps qA and qB are |G|-to-1 everywhere. Therefore pi is 1-1 a.e. if and
only if pi is 1-1 a.e. For the closing condition, note that if ? and ? are maps between
irreducible SFTs, then ??? is right closing if and only if both ? and ? are right
closing [15, Props. 4.10 and 4.11]. Because the constant-to-one maps qA and qB are
in particular right closing [29, Prop. 4.3.4], it follows that pi is right closing if and
only if pi is right closing.
If (G,l) is a G-labeled graph, then for a cycle s = s1s2...sp in G we define the
weight of s by l(s) = l(s1)l(s2)???l(sp). The ratio group ?l is the subgroup of G
given by
?l = {l(s)?l(sprime)?1: s,sprime are cycles in G of the same length}
Theorem 2.3.4 (ZGReplacement Theorem). Let (G,l) and (Gprime,lprime) be irreducible
17
G-labeled graphs of the same period which define edge SFTs ? and ?prime (respectively)
and skewing functions ?: ? ?G and ?prime: ?prime ?G given by ?(x) = l(x0) and ?prime(x) =
lprime(x0). Let pi: ? ? ?prime be a factor map such that ? is cohomologous to ?prime ?pi. If
?l = ?lprime, then there is a 1-1 a.e. factor map pi: ? ? ?prime such that ? is cohomologous
to ?prime ?pi. Moreover, if pi is right closing, then pi can be taken to be right closing as
well.
In [5, Theorem 6.1], Ashley proves a version of his (Z) Replacement Theorem
for maps between irreducible Markov chains, which can be interpreted as follows.
Let R+ denote the multiplicative group of positive real numbers. Let (G,l) and
(Gprime,lprime) be irreducible R+-labeled graphs of the same period, which define irreducible
SFTs ? and ?prime and locally constant functions ?: ? ? R+ and ?prime: ?prime ? R+ where
?(x) = l(x0) and ?prime(x) = lprime(x0). If the ratio groups ?l and ?lprime are equal (as
multiplicative subgroups of R+), and pi: ? ? ?prime is a factor map such that ? is
cohomologous to ?prime ?pi, then there is a 1-1 a.e. factor map pi: ? ? ?prime such that ?
is cohomologous to ?prime ?pi. Moreover, if pi is right closing, then pi can be taken to be
right closing as well.
If instead of R+-labeled graphs we consider G-labeled graphs, then we have
the statement of Theorem 2.3.4. To prove Theorem 2.3.4, one can easily check that
Ashley?s proof for R+-labeled graphs goes through for G-labeled graphs as well.
Theorem 2.3.5. Let X and Y be mixing free G-SFTs. Let pi: X ?Y be a G-factor
map which is right closing. Then there is a G-factor map piprime: X ? Y which is 1-1
a.e. and right closing.
18
Proof. Since X and Y are mixing free G-SFTs, assume without loss of generality
that X = SA and Y = SB for very primitive matrices A and B over Z+G. By
Lemma 2.3.3 the G-factor map pi induces a map pi: ?|A| ? ?|B| such that ?A is
cohomologous to ?B ?pi. Since A and B are very primitive the periods of G|A| and
G|B| are both 1, and furthermore ?lA = ?lB = G. So assume (by Theorem 2.3.4)
that the map pi is 1-1 a.e. and right closing. Again apply Lemma 2.3.3 to obtain a
G-factor map piprime: SA ?SB which is 1-1 a.e. and right closing.
2.4 Right closing almost conjugacy for mixing free G-SFTs
For mixing SFTs, entropy and ideal class are a complete set of invariants
of right closing almost conjugacy (Theorem 2.3.1). We show that there are no
additional invariants of right closing almost conjugacy for mixing free G-SFTs.
Theorem 2.4.1. Let X and Y be mixing free G-SFTs. Then the following are
equivalent.
1. X and Y are right closing almost conjugate as G-SFTs.
2. X and Y are right closing almost conjugate as SFTs.
3. X and Y have the same entropy and ideal class.
Moreover, assuming (2) or (3), the common extension of X and Y in (1) can be
taken to be a free G-SFT.
Proof. (2) ? (3) follows from Theorem 2.3.1. Right closing almost conjugate G-
SFTs are in particular right closing almost conjugate as SFTs, so (1) ? (2). It
19
remains to show (2) ? (1).
Let X and Y be mixing free G-SFTs which are right closing almost conjugate
as SFTs. Without loss of generality, assume thatX andY are skew productsSA and
SB for very primitive matrices A and B over Z+G. Let lA, lB, ?A and ?B denote the
edge labelings and skewing functions defined by A and B, respectively (see section
2.2). Since SA and SB are right closing almost conjugate as SFTs, they have the
same entropy and ideal class (Theorem 2.3.1). The factor maps qA: SA ? ?|A| and
qB: SB ? ?|B| given by (x,g) mapsto? x are |G|-to-1 everywhere. In particular they
preserve entropy and ideal class, so ?|A| and ?|B| have the same entropy and ideal
class. Hence ?|A| and ?|B| are right closing almost conjugate as SFTs (Theorem
2.3.1). Let ?|C| be a common extension of ?|A| and ?|B| by 1-1 a.e. right closing
factor maps pi1: ?|C| ? ?|A| and pi2: ?|C| ? ?|A|.
SA
qA
d33d33d66d66
d66d66d66
d66d66d66
?|C|
pi1
d124d124d122d122d122d122
d122d122d122d122 pi2
d34d34d68d68
d68d68d68d68
d68d68 SBq
B
d125d125d123d123d123
d123d123d123
d123d123
?|A| ?|B|
Without loss of generality, assume the factor maps pi1 and pi2 are one block.
Define edge labelings l1 and l2 on G|C| by l1 = lA ? pi1 and l2 = lB ? pi2. The
labelings l1 and l2 correspond to matrices C1 and C2 (respectively) over Z+G such
that |C1| = |C2| = |C|. Define skewing functions ?1: ?|C| ? G and ?2: ?|C| ? G
by ?1(x) = l1(x0) and ?2(x) = l2(x0). Define G-factor maps pi1: SC1 ? SA and
pi2: SC2 ?SB by pi1(x,g) = (pi1(x),g) and pi2(x,g) = (pi2(x),g). Let q1: SC1 ? ?|C|
and q2: SC2 ? ?|C| be the factor maps (x,g) mapsto? x. Then the following diagram
commutes.
20
SC1
pi1
d125d125d123d123d123
d123d123d123
d123d123 q1
d34d34d69d69
d69d69d69d69
d69d69 SC2q
2
d124d124d121d121d121d121
d121d121d121d121 pi2
d33d33d67d67
d67d67d67
d67d67d67
SA
qA
d33d33d66d66
d66d66d66
d66d66d66
?|C|
pi1
d124d124d122d122d122d122
d122d122d122d122 pi2
d34d34d68d68
d68d68d68d68
d68d68 SBq
B
d125d125d123d123d123
d123d123d123
d123d123
?|A| ?|B|
The factor maps pi1 and pi2 are 1-1 a.e. and right closing, so the factor maps
pi1 and pi2 are as well (Lemma 2.3.3). In particular SC1 and SC2 are mixing free
G-SFTs, so C1 and C2 are very primitive. Let l be the (G?G)-labeling l = l1 ?l2.
Then l corresponds to a Z+(G?G) matrix whose augmentation is |C|. Call this
matrix C. Let ?: ?|C| ?G?G denote the skewing function given by ?(x) = l(x0).
Claim 2.4.2. There is a vertex I in G|C| and a natural number N such that there
is a collection U of paths of length N from I to I with the following properties:
1. for each g in G there are at least |G| paths u? U with weights l1(u) = g.
2. for each g in G there are at least |G| paths u? U with weights l2(u) = g.
3. for each u = u1u2???uN ? U the point xu ? ?|C|, defined by xui = uj if
i?j mod N, has least period N.
4. if u and v are distinct paths in U, then xu and xv are in different orbits under
the shift.
To prove the claim, let ? be the element of Z+G given by ? = summationtextg?Gg. Fix
a vertex I in G|C|. Let ? be the number of cycles of length 1 in G|C|, and choose
a positive integer k large enough so that k ?? ? |G|. Since C1 and C2 are very
primitive matrices there is a positive integer M = M(k) such that, for i = 1,2 and
21
for all m?M, k?? is a summand of (Cmi )II. Let N ?M be a prime number. Let
V be the set of all N-paths from I to I. Each v = v1v2???vN ? V defines a point
xv ? ?|C| by xvi = vj if i ? j mod N. Since N is prime, each such xv has least
period either N or 1. Let V1 = {v ?V : xv has least period 1} and U = V ?V1.
It remains to verify that U satisfies the properties of the claim. Note that, for
i = 1,2, each monomial summand g of (CNi )II corresponds to a path v ? V with
weight li(v) = g. Also, N was chosen so that k?? is a summand of each (CNi )II.
So for i = 1,2 and for each g ? G, there are at least k paths v ? V with weight
li(v) = g. There are only ? cycles of length 1 in G|C|, so in particular |V1| ??. But
k?? ? |G|. Hence, for i = 1,2 and for each g ?G, there are at least k paths u? U
with weight li(u) = g, which verifies properties (1) and (2). Properties (3) and (4)
are true by construction of U. This proves the claim.
Now consider all points xu ? ?|C| such that u ? U. Let ?|C| denote the
smallest closed ?-invariant subset of ?|C| containing all points of this form. Then
?|C|?G is a closed SC-invariant subset of ?|C|?G, so it is a subsystem of the skew
product SC. Let SC denote this subsystem of SC.
Construct a (G?G)-labeled graph (H,lH) as follows. The vertex set of H
consists of N vertices, I1,I2,...,IN. For j = 1,2,...,N ? 1, draw exactly one
edge starting at Ij and ending at Ij+1, and give this edge the lH-label (e,e), where
e is the identity element of G. From IN to I1 draw exactly |U| edges, call them
s1,s2,...,s|U|. Let S = {s1,s2,...,s|U|}, and fix a set bijection ?: S ? U. For
si ? S, put lH(si) = l(?(si)) = (l1(?(si)),l2(?(si))).
LetDbetheZ+(G?G)adjacencymatrixforthe(G?G)-labeledgraph(H,lH).
22
Observe that the set bijection ?: S ? U induces a (G?G)-conjugacy between SD
and SC. Assume without loss of generality that D is a principal submatrix of C
(Lemma 2.3.2), so that (H,lH) is an induced sub-labeled graph of (G|C|,l).
For each g ? G, at least |G| of the edges si ? S have l-labels of the form
(g,?), and at least |G| of the si ? S have l-labels of the form (?,g) (by definition).
Therefore there is a way to permute the second coordinates of the l-labelings of
edges in S such that each (g,h) ? G?G labels at least one si ? S. Equivalently,
there exists a graph isomorphism P of G|C| which fixes all edges except those in
S, and permutes the set S such that for any (g,h) ? G?G, there is at least one
edge si ? S with (l1(si),l2 ?P(si)) = (g,h). Fix a graph isomorphism P with this
property and set lprime to be the (G?G)-labeling of G|C| given by lprime = l1 ? (l2 ?P).
Let P denote the automorphism of ?|C| induced by P. Let Cprime2 be the Z+G matrix
defined by the edge labeling l2 ?P of G|C|. Note that the map ?: SCprime2 ? SC2 given
by (x,g) mapsto? (P(x),g) is a G-conjugacy.
Let Cprime be the Z+(G?G) matrix defined by the edge labeling lprime of G|C|, and
let ?prime: ?|C| ? G?G be the skewing function given by ?prime(x) = lprime(x0). Then SCprime
is the skew product (?|C| ? G ? G,SCprime), where SCprime(x,g,h) = (?(x),?prime(g,h)) =
(?(x),?1(x)?g,(?2?P)(x)?h), and G?G acts by (k,l): (x,g,h) mapsto? (x,gk,hl). Note
that Cprime is very primitive. (This is because, with I = I1 and N as above, (CprimeN)II has
as a summand every element ofG?G.) ThereforeSCprime is a mixing free (G?G)-SFT.
From now on, regard SCprime as a mixing free G-SFT by restricting the (G?G)-
action to the diagonal: let an element g ? G act by (x,h,k) mapsto? (x,hg,kg). Let
p1: SCprime ?SC1 be the |G|-to-one factor map (x,g,h) mapsto? (x,g), and letp2: SCprime ?SCprime2
23
be the |G|-to-one factor map (x,g,h) mapsto? (x,h). Note that p1 and p2 are G-factor
maps; they are right closing because they are constant-to-one [29, Prop 4.3.4]. This
gives a diagram of right closing G-factor maps:
SCprime
p1
d125d125d123d123d123
d123d123d123
d123d123 p2
d33d33d67d67
d67d67d67d67
d67d67
SC1
pi1
d125d125d124d124d124
d124d124d124
d124d124
SCprime2
d33d33d66d66
d66d66
d33d33d66d66
d66d66
?
pi2
d33d33
SA SB
SCprime is a mixing free G-SFT, so by Theorem 2.3.5, the right closing G-factor
maps pi1 ?p1 and pi2 ???p2 can be replaced by 1-1 a.e. and right closing G-factor
maps. This proves the theorem.
2.5 General mixing G-SFTs
In this section we classify right closing almost conjugacy for mixing G-SFTs
where the G action is no longer assumed to be free. We will need this generalization
to classify the irreducible but periodic case in section 2.6. We begin with a result
for faithful G-SFTs, which were defined in section 2.2.
Lemma 2.5.1. Any irreducible faithful G-SFT is a 1-1 a.e. right closing G-factor
of an irreducible free G-SFT.
Lemma 2.5.1 is a corollary of [1, Theorem 3]. If X is a G-SFT, we let HX
denote the normal subgroup of G which acts by the identity map. Then X is a
faithful (G/HX)-SFT where, for all g ?G and x?X, x?(gHX) = x?g.
24
Theorem 2.5.2. Let X and Y be mixing G-SFTs. Then the following are equiva-
lent.
1. X and Y are right closing almost conjugate as G-SFTs
2. X and Y are right closing almost conjugate as SFTs, and HX = HY.
3. X and Y have the same entropy and ideal class, and HX = HY.
Proof. (2) ? (3) follows from Theorem 2.3.1. If X and Y are right closing almost
conjugate as G-SFTs, then in particular they are right closing almost conjugate as
SFTs. Moreover, if Z is a common 1-1 a.e. right closing G-extension of X and
Y, then HX = HZ and HY = HZ, because 1-1 a.e. G-factor maps preserve the
subgroup HZ. This proves (1) ? (2).
Conversely, suppose X and Y are right closing almost conjugate as SFTs, and
H = HX = HY. Then X and Y are faithful (G/H)-SFTs, where for all x ? X,
y ?Y and g ?G, x?(gH) = x?g and y?(gH) = y?g. Hence there are free (G/H)-
SFTs hatwideX and hatwideY, and 1-1 a.e. right closing (G/H)-factor maps ?X: hatwideX ? X and
?Y : hatwideY ? Y (Lemma 2.5.1). Since X and Y are right closing almost conjugate as
SFTs, they have the same entropy and ideal class. Since ?X and ?Y are right closing
factor maps between irreducible SFTs, they preserve entropy and ideal classes. So hatwideX
and hatwideY have the same entropy and ideal class, and are therefore right closing almost
conjugate as SFTs. Thus hatwideX and hatwideY are right closing almost conjugate as (G/H)-
SFTs, and the common extension can be taken to be a free (G/H)-SFT (Theorem
2.4.1). Let Z be a free (G/H)-SFT with 1-1 a.e. right closing (G/H)-factor maps
piX: Z ? hatwideX and piY : Z ? hatwideY.
25
Z
piX
d127d127 d127d127
d127d127d127
d127 pi
Y
d31d31d62d62
d62d62d62
d62d62
hatwideX
?X
d15d15
hatwideY
?Y
d15d15
X Y
For all hatwidex ? hatwideX, hatwidey ? hatwideY and g ? G, put hatwidex?g = hatwidex? (gH) and hatwidey?g = hatwidey? (gH).
With these G actions, hatwideX and hatwideY are G-SFTs, and ?X and ?Y are now G-maps. For
all z ? Z and g ? G, put g ?z = z ? (gH). This G action makes Z a G-SFT as
well, and piX and piY are now G-maps. Thus Z together with the maps ?X ?piX and
?Y ?piY give a right closing almost conjugacy between X and Y as G-SFTs.
2.6 The irreducible but periodic case
Here we classify right closing almost conjugacy for irreducible but periodic G-
SFTs. If (X,?) is an irreducible G-SFT of period p, then we let X0,X1,...,Xp?1
denote the cyclically moving subsets ofX under?. Then for 0 ?n?p?1, (Xn,?p)
is a mixing SFT. The (Xn,?p) are pairwise conjugate SFTs and the action of G on
(X,?) permutes the (Xn,?p). If the entropy of (X,?) is log(?), then the entropy of
each (Xn,?p) is log(?p). The ideal class (in Z[1/?p]) of (Xn,?p) is determined by
the ideal class (in Z[1/?]) of (X,?). We let X = X0 and ? = ?p|X. Then as SFTs,
X is conjugate to X ?{0,...,p?1}, where the shift for the latter is given by
26
?(x,n) =
?
????
???
?
(x,n+ 1) if 0 ?n?p?2,
(?(x),0) if n = p?1.
(2.6.1)
We give toX?{0,...,p?1} theG action which is the image under conjugacy
of the G action on X, so that X is G-conjugate to X?{0,...,p?1}. Without loss
of generality, we assume from now on that irreducible but periodic G-SFTs are of
the form (X,?) = (X ?{0,...,p?1},?), where the shift ? is given by 2.6.1.
By Zp we mean the group of integers {0,1,...,p? 1} with addition mod p.
The G action on X determines a homomorphism ?X: G?Zp, given by ?X(g) = k
if and only if g: (X,0) mapsto? (X,k). We refer to ?X as the action homomorphism for
the G-SFT (X,?). Note that for 0 ? n ? p? 1 and for each g ? G, g: (X,n) mapsto?
(X,n+?X(g)(mod p)), where the action on the first coordinate is given by some
automorphism Ug of (X,?). The first coordinate automorphisms {Ug}g?G define a
G action on (X,?), given by g: x mapsto? Ug(x). This G action on X is not necessarily
free, even if the G action on X is free. We refer to the G-SFT X as the base G-SFT
forX. We point out that baseG-SFTs are mixing, so right closing almost conjugacy
of base G-SFTs is classified by Theorem 2.5.2.
Theorem 2.6.2. Let X and Y be irreducible G-SFTs. Then the following are
equivalent.
1. X and Y are right closing almost conjugate as G-SFTs.
2. The base G-SFTs X and Y for X and Y are right closing almost conjugate as
G-SFTs, and the action homomorphisms ?X and ?Y are the same.
27
Proof. Suppose (X,?) and (Y,?) are right closing almost conjugate as G-SFTs.
Then there is a G-SFT (Z,?) and 1-1 a.e. right closing G-factor maps piX: Z ?X
and piY : Z ? Y. The maps piX and piY preserve period, so Z must have period
p, where p is the period of both X and Y. Furthermore Z must be irreducible
because X and Y are irreducible. Without loss of generality, assume that Z =
Z ? {0,...,p? 1} where Z is the base G-SFT for Z. Further assume (X,0) =
piX(Z,0) and (Y,0) = piY(Z,0), where X and Y are the base G-SFTs for X and Y
respectively. Observe that for 0 ?n?p?1,
piX(Z,n) = piX ??n(Z,0)
= ?n ?piX(Z,0)
= ?n(X,0)
= (X,n).
In particular ?X = ?Z (since piX intertwines G actions). Similarly ?Y = ?Z.
Let PZ: Z ? Z be the G-factor map (z,n) mapsto? z and let PX: X ? X be the
G-factor map (x,n) mapsto? x. Since piX(Z,n) = (X,n) for 0 ? n ? p? 1, there is a
G-factor map piX: Z ?X which makes the following diagram commute.
Z piX d47d47
PZ
d15d15
X
PX
d15d15
Z piX d47d47X
piX is 1-1 a.e. and right closing because piX is. Similarly construct a 1-1 a.e.
right closing G-factor map piY : Z ? Y. Then X and Y are right closing almost
conjugate as G-SFTs.
28
Conversely, supposethebaseG-SFTs(X,?)and(Y,?)arerightclosingalmost
conjugate as G-SFTs, and ? = ?X = ?Y. In particular, X and Y have the same
period p. Let (Z,?) be a G-SFT with 1-1 a.e. right closing G-factor maps piX: Z ?
X and piY : Z ? Y. Let Z = Z ? {0,...,p ? 1} with the shift defined as in
2.6.1. Define a G action on Z by g: (z,n) mapsto? (z?g,n+?(g)(mod p)). Define maps
piX: Z ? X and piY : Z ? Y by piX(z,n) = (piX(z),n) and piY(z,n) = (piY(z),n).
Then piX and piY are G-factor maps. They are 1-1 a.e. and right closing because piX
and piY are.
2.7 Regular isomorphism of G-Markov chains
Let (X,?) and (Y,?) be irreducible Markov chains with Markov measures ?
and ?. Let ? and ? be the time zero partitions of X and Y, respectively. Consider
the past?-algebras?? =logicalortext?n=0?n? and?? =logicalortext?n=0?n?. Then (X,?) and (Y,?) are
regularly isomorphic if there is a measurable isomorphism ?: (X,?) ? (Y,?) such
that
??1(??) ???N?? = ?? ???1????????N?,
?(??) ???N?? = ?? ???1????????N?
for some non-negative integer N. The idea of regular isomorphism was introduced
and studied by Parry, first in [20] and also in [37]. For a regular isomorphism ?
(in contrast to an arbitrary measurable isomorphism), to code the present (?x)0, it
29
suffices to know the past and a bounded look into the future x(??,N]. Boyle and
Tuncel [17] show this measurable coding relation has a more finite and continuous
formulation, as follows.
Theorem 2.7.1. Irreducible Markov chains (X,?) and (Y,?) are regularly isomor-
phic if and only if there exists an irreducible Markov chain (Z,?) and 1-1 a.e. right
closing factor maps piX: (Z,?) ? (X,?) and piY : (Z,?) ? (Y,?).
AG-Markov chain is a Markov chain (X,?) such thatX is aG-SFT and?is a
G-invariant Markov measure onX. Say that irreducibleG-Markov chains (X,?) and
(Y,?) areG-regularly isomorphic if there is a regular isomorphism?: (X,?) ? (Y,?)
such that ? is G-equivariant. By Theorems 2.4.1 and 2.7.1 we have the following.
Corollary 2.7.2. Mixing free G-Markov chains (X,?X) and (Y,?Y), with unique
measures of maximal entropy ?X and ?Y, are G-regularly isomorphic if and only if
(X,?X) and (Y,?Y) are regularly isomorphic as Markov chains.
In the general irreducible case, G-regular isomorphism with respect to mea-
sures of maximal entropy can be classified in terms of the invariants of Theorem
2.6.2.
30
Chapter 3
Weak equivalence for shifts of finite type
3.1 Introduction
In [9], Beal and Perrin introduce an equivalence relation on subshifts called
weak equivalence, and classify a special collection of irreducible shifts of finite type
(SFTs) up to weak equivalence. We classify arbitrary SFTs up to weak equivalence.
For this, first we prove an extension theorem: Given a homomorphism from the
nonwandering set of an SFT S to the nonwandering set of an SFT T, we give
necessary and sufficient conditions for the existence of an extension of the given
homomorphism to a homomorphism from S to T. We use this extension result to
give necessary and sufficient conditions for the existence of a homomorphism from
one SFT to another.
Extension results are significant in symbolic dynamics. Boyle?s extension re-
sult [10, Extension Lemma 2.4] is the key to characterizing when there exists an
epimorphism from one mixing SFT onto another of lower entropy, and has had
other applications as well. (For example, a refinement of that result, [17, Theorem
5.3], establishes that the Markovian property of a homomorphism is in a certain
sense not local.) The extension theorem for inert automorphisms of Kim and Roush
[25] is a central tool in the study of automorphisms of an SFT. (See [12], [27] and
[28].) The study [7] provides a variety of surjective extension results. It follows from
31
the work of Maass [34] that an open problem on extensions, Problem 3.6.8 below, is
very closely related to the problem of characterizing the limit sets of stable cellular
automaton maps.
As a consequence of Lightwood?s machinery for extending certain classes of
homomorphisms of Z2 SFTs, we know that for a large class of examples the key issue
for existence of an embedding between Z2 SFTs is the existence of a homomorphism
between them [31, 32]. This provides some additional motivation for our existence
result in the more tractable d = 1 case.
We thank Danrun Huang for calling our attention to the paper of Beal and
Perrin, and we thank Mike Boyle for many helpful discussions about this problem.
3.2 Preliminaries
3.2.1 Shifts of finite type
We assume some familiarity with shifts of finite type. See [29] and [33] for
more complete background.
Given n > 0, let ?n = {0,...,n? 1}Z denote the set of doubly-infinite se-
quences (xi)i?Z where each xi ? {0,...,n ? 1}. Give to ?n the product of the
discrete topology on {0,...,n?1}. Then ?n is compact and metrizable. The shift
is the homeomorphism ? : ?n ? ?n given by ?(x)i = xi+1. The pair (?n,?) (or
just ?n for short) is the full n-shift. A full shift is a full n-shift for some n. If S is
a closed, ?-invariant subset of a full shift, then the pair (S,?) (or just S for short)
is a subshift.
32
A word on {0,...,n?1} is a finite concatenation w1...wk, where each wi ?
{0,...,n?1}. Given a subshift S, a point x ? S, and coordinates i<j, often we
write x[i,j] to denote the word xi???xj.
If a subshift S may be written
S = ?n \{x? ?n : no word in F appears in x}
for a finite set of words F, then S is a shift of finite type (SFT).
A homomorphism f : S ? T from one SFT to another is a ?-equivariant
function such that, for each x?S, f(x)0 is determined by x?i???x0???xj for some
i,j ? 0. Thenf isr-block wherer = i+j+1. Iff is surjective it is an epimorphism.
An injective epimorphism is an isomorphism. Any homomorphism f : S ? T is
isomorphic to a one-block homomorphism, in the sense that there exists an SFT Sprime
and an isomorphism ? : Sprime ?S such that f ?? is one-block.
3.2.2 Edge shifts
Let A be an n?n matrix over the non-negative integers which has no 0-row
or 0-column. Then A is the adjacency matrix for a directed graph G(A): G(A)
has vertex set {v1,...,vn} where the number of edges from vi to vj is A(i,j). Let
E(A) = {edges in G(A)} and V(A) = {vertices in G(A)}. Put
?A = {x = (xi)i?Z ? E(A)Z | each xixi+1 is a path in G(A)}.
Give to ?A the relative of the product of the discrete topology on E(A). Then, by
thinking of edges in E(A) as numbers in {0,...,|E(A)|?1}, ?A is a special type of
33
subshift, called an edge shift. Any edge shift is an SFT. Also, any SFT is isomorphic
to an edge shift.
3.2.3 Irreducible shifts of finite type
Let A be as in section 3.2.2. Then A, G(A), and ?A are irreducible if, for each
1 ?i,j ?n, there existsL = L(i,j) such thatAL(i,j) > 0. If there exists a uniform
L> 0 such that AL(i,j) > 0 for all 1 ?i,j ?n, then A and G(A) are primitive . If
A is primitive, then ?A is mixing.
A point x ? ?A is periodic if there exists p > 0 such that ?p(x) = x. In this
case p is a period of x. When A is irreducible, we define the period of A, G(A) and
?A to be the greatest common divisor of the set of periods of the periodic points in
?A. Note that for primitive A, the period of A is 1.
Given a path w = w0???wl?1 of edges in G(A), the length of w is |w| = l.
Denote by in(w) and ter(w) the initial and terminal vertices of w, respectively. If A
is irreducible, say that vertices vi and vj in V(A) are period equivalent if there is a
path w in G(A) with in(w) = vi and ter(w) = vj such that |w| is divisible by p = the
period of A. This defines an equivalence relation on V(A), and induces a partition
of V(A) into a disjoint union of p sets
V(A) = V0(A)unionsq???unionsqVp?1(A).
The Vi(A) are called the cyclically moving vertex sets of V(A). This partition of
V(A) induces a partition of ?A into p sets
?A = ?0A unionsq???unionsq?p?1A ,
34
where ?iA = {x ? ?A : in(x0) ? Vi(A)}. The ?iA are called the cyclically moving
subsets of ?A. By re-labelling if necessary, we may assume that?(?iA) = ?(i+1) mod pA
for 0 ?i?p?1. Each ?iA is both invariant and mixing under ?p.
3.2.4 Reducible shifts of finite type
Let A be as in section 3.2.2. The nonwandering set of ?A, denoted NW(A),
is the closure of the set of periodic points in ?A. The nonwandering set NW(A) is
an SFT, and is a disjoint union
NW(A) = C(A)1 unionsq???unionsqC(A)K,
where each C(A)i is an irreducible SFT. The C(A)i are called the irreducible com-
ponents of ?A. If K > 1, then ?A is reducible.
For 1 ? i ? K, let pi denote the period of C(A)i. Then C(A)i is partitioned
into cyclically moving subsets C(A)0i,...,C(A)pi?1i , each of which is both invariant
and mixing under ?pi, as in Section 3.2.3. Therefore we can find li ? 1 such that
if q and qprime are any two vertices in the same cyclically moving subset of the graph
G(C(A)i), then there exists a path w in G(C(A)i) of length |w| = pi ?li such that
in(w) = q and ter(w) = qprime. Such li is called a cyclic transition length for C(A)i.
3.3 Homomorphisms between irreducible SFTs
Let S and T be subshifts. Write S PER?? T if, for each periodic point x ? S of
period p, there is a periodic point y ?T of period q, such that q divides p.
35
Theorem 3.3.1. Given irreducible SFTs S and T, there exists a homomorphism
f : S ? T if and only if S PER?? T. Moreover, assuming S PER?? T, then given any
pair of cyclically moving subsets S0 and T0 in S and T respectively, f : S ?T may
be chosen so that f(S0) ?T0.
Proof. If f : S ?T is a block code and x?S is a periodic point of period p, then
f(x) ?T must be a periodic point of some period dividing p, by the ?-equivariance
of f.
Conversely, first suppose S PER?? T and T is mixing. In this case, let S be the
empty subshift, and let f : S ?T be the empty homomorphism. By [10, Extension
Lemma 2.4], f extends to a homomorphism f : S ?T.
Now supposeS PER??T whereT is no longer assumed to be mixing. Decompose
S and T into disjoint unions of cyclically moving subsets, each of which is invariant
and mixing under the pth power of the shift, where p is the period of S (the period
of T divides p by assumption). Fix cyclically moving subsets S0 of S and T0 of T,
and let X = (S0,?p) and Y = (T0,?p). Then X PER?? Y and Y is mixing so, by
the previous paragraph, there exists a homomorphism f0 : X ? Y. Every other
cyclically moving subset of S is equal to ?i(S0) for some unique 1 ? i < p. So
define a homomorphism fi on ?i(S0) by fi = ?i ?f0 ???i, and define f : S ?T by
f(x) = fi(x) where x??i(S0).
36
3.4 Extending homomorphisms defined on a nonwandering set
Let ?A be a reducible edge shift. Write the nonwandering set NW(A) =
C(A)1unionsq???unionsqC(A)K as a disjoint union of irreducible components, and let pi denote
the period of C(A)i. Fix in each C(A)i one cyclically moving subset C(A)0i, and
enumerate the remaining cyclically moving subsets inC(A)i byC(A)1i,...,C(A)pi?1i ,
where C(A)ki = ?k(C(A)0i).
Given this enumeration of the cyclically moving subsets, for each i,j, define
the set of connection paths from C(A)i to C(A)j, denoted CPA(i,j), to be the set of
paths in G(A) of the form x0???xt?1 which have initial vertex in some C(A)si, and
terminal vertex in some C(A)rj. The number s+t?r, taken mod gcd(pi,pj), is the
phase change of the path x0???xt?1.
Now define a K?K matrix PA as follows. The entries of PA are sets. Specif-
ically, PA(i,j) ? Zgcd(pi,pj) is the set of phase changes of paths in CP(Ai,Aj). Let
M(A) denote the set of phase matrices for A. Note that the finitely many possible
enumerations of the cyclically moving subsets determine the finitely many matrices
in M(A). By a phase matrix for A we mean a matrix PA determined by some
enumeration of cyclically moving subsets.
Given x and xprime in ?A, say that x and xprime are backwardly asymptotic if there
exists k ?Z such that xi = xprimei for all i?k, and forwardly asymptotic if there exists
k ?Z such that xi = xprimei for all i?k.
Remark 3.4.1. Let PA be a phase matrix for A. Then c ? PA(i,j) if and only if
there exist x, y and z in ?A such that
37
? z is backwardly asymptotic to x and forwardly asymptotic to y,
? x?C(A)si and y ?C(A)rj, and
? s?r ?c mod gcd(pi,pj).
It follows that, if ? : ?A ? ?C is an isomorphism which respects the numberings
of the irreducible components and cyclically moving subsets, then the associated
phase matrices PA and PC are equal. In particular, the set M(A) of possible phase
matrices for A is an isomorphism invariant.
Example 3.4.2. Let A be the adjacency matrix for the following graph.
v11
d11d11
v22
d11d11
v21 d55d55v01
d107d107
d47d47
d47d47
? d47d47v02 d55d55v12
d107d107
Let C(A)1 correspond to the cycle on the left and let C(A)2 correspond to the
cycle on the right. Choose the cyclically moving subset C(A)01 to be those points
x ? C(A)1 such that the initial vertex of x0 is v01, and C(A)02 to be those points
x ? C(A)2 such that the initial vertex of x0 is v02. Then the phase matrix for this
choice is
PA =
?
??
?
{0} {2}
? {0}
?
??
?.
Remark 3.4.3. Let D(A) denote the set ofK?K diagonal matricesD, where each
D(i,i) is an element of the group Zpi. Note that, if M and Mprime are any two phase
38
matrices in M(A), then there is a matrix D ? D(A) such that Mprime = DMD?1, by
which we mean that, for each i,j,
Mprime(i,j) = {D(i,i) +s?D(j,j) : s?M(i,j)}. (3.4.4)
Conversely, given M ? M(A) and D ? D(A), the matrix DMD?1 is in M(A).
Thus the set M(A) is computable via the following finite process:
1. Arbitrarily choose an enumeration of the cyclically moving subsets for A.
2. Construct the phase matrix PA for this choice, as defined above, and include
this PA in M(A).
3. For each D ? D(A), add to M(A) the matrix DPAD?1.
Now let ?B be another reducible edge shift with nonwandering set NW(B) =
C(B)1 unionsq ??? unionsqC(B)L, and let qi denote the period of the irreducible component
C(B)i. Suppose there exists a homomorphism f0 : NW(A) ? NW(B). Then f0
induces a set function g : {1,...,K} ? {1,...,L} by the following rule: C(B)g(i)
is the irreducible component of ?B which contains f0(C(A)i).
In each irreducible component C(B)i, arbitrarily choose one cyclically moving
subset C(B)0i, and enumerate the remaining cyclically moving subsets in C(B)i by
C(B)ki = ?k(C(B)0i). Let PB be the phase matrix determined by this choice. Say
that a phase matrix PA for A is compatible with (PB,f0) if PA is the phase matrix
determined by a choice of the cyclically moving subsets C(A)0i in C(A)i such that
each f0(C(A)0i) ? C(B)0g(i). For such PA let PA be the matrix such that each
PA(i,j) is the set of elements in PA(i,j) taken mod gcd(qg(i),qg(j)).
39
Theorem 3.4.5. Let ?A and ?B be reducible edge shifts, as above, and let f0 :
NW(A) ? NW(B) be a homomorphism. Let g : {1,...,K} ? {1,...,L} be the
set function induced by f0. Choose a phase matrix PB for B, and let PA be a phase
matrix for A compatible with (PB,f0).
Then f0 extends to a homomorphism f : ?A ? ?B if and only if each PA(i,j)
is contained in PB(g(i),g(j)).
Proof. Suppose f0 extends to f : ?A ? ?B. Let c ? PA(i,j) and let c ? PA(i,j)
satisfy c ? c mod gcd(qg(i),qg(j)). By Remark 3.4.1 there exist x, y and z in ?A
such that
? z is backwardly asymptotic to x and forwardly asymptotic to y,
? x?C(A)si and y ?C(A)rj, and
? s?r ?c mod gcd(pi,pj).
Let s (r, respectively) denote s (r, resp.) taken modulo qg(i) (qg(j), resp.). Then
? f(z) is backwardly asymptotic to f(x) and forwardly asymptotic to f(y),
? f(x) ?C(B)sg(i) and f(y) ?C(B)rg(j), and
? s?r ?c mod gcd(qg(i),qg(j)).
Hence c?PB(g(i),g(j)).
For the converse first note that we may assume, without loss of generality, that
f0 is one-block. For, if not, then we can choose an SFT ?C and an isomorphism
? : ?C ? ?A such thatf0??|NW(C) is one-block. The isomorphism?can be taken to
40
respect the numberings of the irreducible components and cyclically moving subsets,
which implies PC = PA, by Remark 3.4.1. It follows that f0 extends to all of ?A if
and only if f0 ??|NW(C) extends to all of ?C.
For the converse, we will use the following.
Claim 3.4.6. Suppose each PA(i,j) ? PB(g(i),g(j)). Then there exists M > 0
such that, for each i,j and for each path Q ? CPA(i,j) of length |Q| ? M, there
exists a path Qprime ? CPB(g(i),g(j)) such that |Qprime| = |Q|, in(Qprime) = f0(in(Q)), and
ter(Qprime) = f0(ter(Q)).
To prove Claim 3.4.6, first recall that each C(A)i has a cyclic transition length
li. WLOG assume that li is a cyclic transition length for C(B)g(i) as well. (If not,
just make li larger.) Let
l = max
i
{li},
and let
p =
productdisplay
i
pi.
Note that if v and vprime are any two vertices in the same cyclically moving subset of
some C(B)g(i), then there is a path in C(B)g(i) of length lp from v to vprime.
Next, pick T large enough so that, for each i,j and for each c?PA(i,j), there
exists a path Q?CPB(g(i),g(j)) of length at most T with phase change c.
Then, for each i,j, pick Ri,j large enough so that all integers r greater than
Ri,j and divisible by gcd(qg(i),qg(j)) are contained in the N-ideal
<qg(i),qg(j) >N := {mqg(i) +nqg(j) : m?N, n?N}.
41
Let R = maxi,jRi,j, and set
M = T +R+ 2lp+ 2max
i
qg(i).
To see thatM satisfies the requirements of Claim 3.4.6, letQ?CPA(i,j) have
length|Q| ?M and phase changec. Assume that in(Q) is in someC(A)si and ter(Q)
is in some C(A)rj, so that c?s+|Q|?r mod gcd(pi,pj). Let Q1 ?CPB(g(i),g(j))
have phase change c?c mod gcd(qg(i),qg(j)) and |Q1| ?T.
Extend Q1 to the left in G(C(B)g(i)) by at most qg(i) and to the right in
G(C(B)g(j)) by at most qg(j) to a path Q2 ?CPB(g(i),g(j)) with in(Q2) ?C(B)sg(i)
and ter(Q2) ?C(B)rg(j), where s?s mod qg(i) and r ?r mod qg(j). Note that Q2
has phase change c. Also, |Q|?2lp?|Q2| is divisible by gcd(qg(i),qg(j)) and greater
than R, so
|Q|?2lp?|Q2| ? <qg(i),qg(j) >N .
Hence
|Q|?2lp = |Q2|+aqg(i) +bqg(j)
for some a,b ? 0. So we may extend Q2 to the left in G(C(B)g(i)) by aqg(i) and to
the right in G(C(B)g(j)) by bqg(j) to a path Q3 ?CPB(g(i),g(j)) with
? in(Q3) ?C(B)sg(i),
? ter(Q3) ?C(B)rg(j), and
? |Q| = |Q3|+ 2lp.
Finally, by choice of l, we may extend Q3 to the left in G(C(B)g(i)) by lp and to the
right in G(C(B)g(j)) by lp to a path Qprime ?CPB(g(i),g(j)) with
42
? in(Qprime) = f0(in(Q)),
? ter(Qprime) = f0(ter(Q)), and
? |Q| = |Qprime|.
This completes the proof of Claim 3.4.6
Now define f : ?A ? ?B as follows. Let M > 0 be as in Claim 3.4.6, and let
Q ? Qprime be a chosen associated map on connection paths Q of length at least M.
Consider the set of paths VWX in G(A) which satisfy
1. V is in a component C(A)i and |V| = M,
2. X is in a component C(A)j and |X| = M,
3. the only C(A)i-vertex of W is its initial vertex, and the only C(A)j-vertex of
W is its terminal vertex, and
4. W does not contain any path of length M from NW(A).
Let x? ?A. For each k ?Z such that x[k,k+|VWX|?1] is a path satisfying
(1)?(4) above, set f(x)[k,k+|VW|?1] = (VW)prime. Elsewhere in x, define f(x)i =
f0(x)i. As there is an upper bound on the lengths of paths VWX which satisfy
(1)?(4) above, f is a homomorphism. By construction, f0 is the restriction of f to
NW(A).
43
3.5 Homomorphisms between reducible SFTs
Our main theorem below characterizes when there exists a homomorphism
between arbitrary SFTs.
Theorem 3.5.1. Let ?A and ?B be reducible edge shifts with nonwandering sets
NW(A) = C(A)1 unionsq???unionsqC(A)K and NW(B) = C(B)1 unionsq???unionsqC(B)L. Let PB be a
phase matrix for B. Then there exists a homomorphism f : ?A ? ?B if and only if
we may choose a set function g : {1,...,K} ? {1,...,L} and a phase matrix PA
for A such that, for 1 ?i,j ?K,
1. C(A)i PER??C(B)g(i), and
2. PA(i,j) ?PB(g(i),g(j)).
Proof. Given a homomorphism f : ?A ? ?B, let C(B)g(i) be the irreducible com-
ponent of ?B containing f(C(A)i). This defines a set function g : {1,...,K} ?
{1,...,L}. Then, for 1 ? i ? K, f|C(A)i : C(A)i ? C(B)g(i) is a homomorphism,
so C(A)i PER??C(B)g(i), by Theorem 3.3.1.
For 1 ?j ?Landi?g?1(j), chooseC(A)0i to be a cyclically moving subset of
C(A)i such that f(C(A)0i) ?C(B)0j. Let PA be the phase matrix for A induced by
this choice of the cyclically moving subsets C(A)0i in C(A)i. Then PA is compatible
with (PB,f0), wheref0 = f|NW(A). By Theorem 3.4.5 eachPA(i,j) ?PB(g(i),g(j)).
Conversely suppose we may choose a set function g : {1,...,K} ? {1,...,L}
and a phase matrix PA for A such that conditions (1) and (2) of Theorem 3.5.1
are satisfied for 1 ? i,j ? K. By condition (1) and Theorem 3.3.1, there exists a
44
homomorphism f0 : NW(A) ? NW(B) such that C(B)g(i) is the irreducible com-
ponent of ?B containing f0(C(A)i). Moreover, by Theorem 3.3.1, f0 may be chosen
so that each C(B)0g(i) contains f0(C(A)0i) (i.e. PA is compatible with (PB,f0)). It
then follows from Theorem 3.4.5 that f0 extends to a homomorphism f : ?A ? ?B.
3.6 Weak equivalence of SFTs
Definition 3.6.1. Let S and T be subshifts. If ? : ?n ? ?m is a homomor-
phism between full shifts ?n and ?m which contain S and T respectively, such that
??1(T) = S, then write ? : S ??T. If such a ? exists, write S ??T
Definition 3.6.2 (Beal and Perrin). Subshifts S and T are weak equivalent if
S ??T and T ??S.
A flower shift is an SFT presented by a directed graph made up of loops that
all begin and end at a single vertex. If the lengths of the loops of a flower shift S are
s := (s1,...,sn), then we define < s >N to be the N-ideal s1N+???+snN. Given
flower shifts S and T, which define ideals < s >N and < t >N, Beal and Perrin [9]
prove that S and T are weak equivalent if and only if <s>N=<t>N.
Proposition 3.6.3. The following are equivalent for subshifts S and T.
1. S ??T.
2. There exists an SFT Sprime containing S, a subshift Tprime containing T, and a ho-
momorphism f : Sprime ?Tprime such that f?1(T) = S.
45
Proof. (1) ? (2): Let (f,Sprime,Tprime) be (?,?n,?m) from Definition 3.6.1.
(2) ? (1): Choose r ? 2 so that f is r-block. We may assume WLOG that
Sprime is a 1-step SFT, which means that a point x is in Sprime if and only if xixi+1 is an
allowed word of length 2 in Sprime for each i ? Z. Let ?n?1 and ?m?1 be full shifts
containing Sprime and Tprime respectively. Define an r-block homomorphism ? : ?n ? ?m
by:
?(x0???xr?1) =
?
????
???
?
f(x0???xr?1) if x0???xr?1 is allowed in Sprime
m?1 if x0???xr?1 is not allowed in Sprime
Then ? : ?n ? ?m is well-defined, and ??1(T) = S.
Theorem 3.6.4. Let S be an SFT and let T be a subshift. Then S ??T if and only
if there exists a homomorphism f : S ?T.
Proof. If ? : S ?? T, then f = ?|S is a homomorphism. Conversely, if f : S ? T
is a homomorphism, then letting Sprime = S and Tprime = T, condition (2) of Proposition
3.6.3 is satisfied. Hence S ??T.
The requirement that S be an SFT can not be removed from Theorem 3.6.4.
To see this note that, if S is a non-SFT subshift and T is an SFT, then it can not
be the case that S ?? T. However there are plenty of examples of homomorphisms
from non-SFT subshifts to SFT subshifts.
Corollary 3.6.5. Let S and T be SFTs. Then S and T are weak equivalent if and
only if there exist homomorphisms f : S ?T and g : T ?S.
46
Corollary 3.6.5 follows directly from Theorem 3.6.4. Corollary 3.6.5 combined
with Theorem 3.5.1 provide a classification of weak equivalence for SFTs.
The next proposition is an easy observation which we record to further empha-
size the local nature of the weak equivalence relation. For a subshift S, let Wk(S)
denote the set of words of length k occurring in points in S. Given n ? N, let Sn
denote the largest SFT such that Wn(Sn) = Wn(S). If f : S ? T is an R-block
homomorphism between subshifts then, for r ?R, the R-block rule defining f also
defines a homomorphism fr : Sr ?Tr?R.
Proposition 3.6.6. Suppose ? : S ?? T, and let f = ?|S. Then there exists a
positive integer R such that, for all r ?R, fr is well-defined and f?1r (T) = S.
Proof. We have ? : ?n ? ?m for some n and m. Choose R so that ? is R-block.
Observe that S ? SR ? ?n because SR ? S1 and S1 is the smallest full shift
containing S. Also ?|SR = fR because ? and f are defined by the same R-block
rule. Therefore ?|Sr = fr for all r ? R. We know ??1(T) = S, so (?|Sr)?1(T) = S
and hence f?1r (T) = S for all r ?R.
Say that a homomorphism f defined on a subshift S is steady if there is an
SFT Sprime containing S such that f is well-defined on Sprime, and f applied to Sprime has
the same image as does f. A subshift S is sofic if there exists an SFT R and an
epimorphism R?S.
Remark 3.6.7. If S ?? T where S is a non-SFT subshift, then there exists a
homomorphism f : S ? T which fails to be steady. This is true in particular if S
is strictly sofic. To see this, suppose ? : S ?? T and let f = ?|S. If f were steady,
47
then there would exist an SFT Sprime containing S such that f is well-defined on Sprime
and f(Sprime) = T. Then, for all r sufficiently large, fr is well-defined and Sr ? Sprime, so
f?1r (T) = Sr. But Sr negationslash= S because S is non-SFT, contradicting Proposition 3.6.6.
Remark 3.6.7 points to a seeming resemblance between Proposition 3.6.6 and
the following difficult open problem.
Problem 3.6.8. Give necessary and sufficient conditions for a homomorphism de-
fined on a sofic shift to be steady.
One motivation for Problem 3.6.8 is to characterize the limit sets of stable
cellular automaton maps. These limit sets are the subshifts T for which there exists
a cellular automaton map f and a positive integer r such that T = Image(fr) =
Image(fr+1). In [34], Maass studies such limit sets, and shows that they are precisely
the mixing sofic shifts S which contain a receptive fixed point and which admit a
steady epimorphism f : S ?S.
48
Bibliography
[1] R. Adler, B. Kitchens and B. Marcus, Finite group actions on shifts of
finite type, Ergodic Theory & Dynamical Systems 5 (1985), 1-25.
[2] R. Adler, B. Kitchens and B. Marcus, Almost topological classification of
finite-to-one factor maps between shifts of finite type, Ergodic Theory &
Dynamical Systems 5 (1985), 485-500.
[3] R. L. Adler, A. G. Konheim and M. H. McAndrew, Topological entropy,
Trans. Amer. Math. Soc. 114 (1965), 309-319.
[4] R. Adler and B. Marcus, Topological entropy and equivalence of dynamical
systems, Mem. Amer. Math. Soc., 20, No. 219 (1979).
[5] J. Ashley, Bounded-to-1 factors of an aperiodic shift of finite type are 1-to-
1 almost everywhere factors also, Ergodic Theory & Dynamical Systems
10 (1990), 615-625.
[6] J. Ashley, An extension theorem for closing maps of shifts of finite type,
Trans. Amer. Math. Soc. 336 (1993), no. 1, 389-420.
[7] J. Ashley, B. Marcus, D. Perrin and S. Tuncel, Surjective extensions of
sliding-block codes, SIAM J. Discrete Math. 6 (1993), no. 4, 582-611.
[8] J. Ashley, B. Marcus and S. Tuncel, The classification of one-sided Markov
chains, Ergodic Theory & Dynamical Systems 17 (1997), no. 2, 269-295.
[9] M.-P. Beal and D. Perrin, A weak equivalence between shifts of finite type,
Adv. in Appl. Math. 29 (2002), 162-171.
[10] M. Boyle, Lower entropy factors of sofic systems, Ergodic Theory & Dy-
namical Systems 3 (1983), no. 4, 541-557.
[11] M. Boyle, Flow equivalence of shifts of finite type via positive factorizations,
Pacific J. Math. 204 (2002), no. 2, 273-317.
[12] M. Boyle and U. Fiebig, The action of inert finite-order automorphisms
on finite subsystems of the shift, Ergodic Theory & Dynamical Systems 11
(1991), no 3, 413-425.
[13] M. Boyle and D. Handelman, The spectra of nonnegative matrices via sym-
bolic dynamics, Annals of Math. 133 (1991), 249-316.
[14] M. Boyle and D. Huang, Poset block equivalence of integral matrices, Trans.
Amer. Math. Soc. 335 (2003), no. 10, 3861-3886.
49
[15] M. Boyle, B. Marcus and P. Trow, Resolving maps and the dimension group
for shifts of finite type, Mem. Amer. Math. Soc. 70 (1987).
[16] M. Boyle and M. Sullivan, Equivariant flow equivalence for shifts of finite
type, by matrix equivalence over group rings, Proc. London Math. Soc. 91
(2005), 184-214.
[17] M. Boyle and S. Tuncel, Infinite-to-one codes and Markov measures, Trans.
Amer. Math. Soc. 285 (1984), no. 2, 657-684.
[18] M. Boyle and S. Tuncel, Regular isomorphism of Markov chains is almost
topological, Ergodic Theory & Dynamical Systems 10 (1990), 89-100.
[19] M. Boyle and J. B. Wagoner, Positive algebraic K-theory and shifts of finite
type, Modern Dynamical Systems and Applications (2004) 45-66.
[20] R. Fellgett and W. Parry, Endomorphisms of Lebesgue space II, Bull. Lon-
don Math. Soc. 7 (1975), 151-158.
[21] M. Field and M. Nicol, Ergodic theory of equivariant diffeomorphisms:
Markov partitions and stable ergodicity, Mem. Amer. Math. Soc. 169, No.
803 (2004).
[22] N. Friedman and D. Ornstein, On the isomorphism of weak Bernoulli trans-
formations, Adv. Math. 5 (1970), 365-394.
[23] D. Huang, Flow equivalence of reducible shifts of finite type, Ergodic Theory
& Dynamical Systems 14 (1994), no. 4, 695-720.
[24] D. Huang, Flow equivalence of reducible shifts of finite type and Cuntz-
Krieger algebras, J. Reine Angew. Math. 462 (1995), 185-217.
[25] K. H. Kim and F. W. Roush, On the structure of inert automorphisms of
subshifts, Pure Math. Appl. Ser. B 2 (1991), no. 1, 3-22.
[26] K. H. Kim and F. W. Roush, Topological classification of reducible subshifts
Pure Math. Appl. Ser. B 3 (1992), no. 2-4, 87-102.
[27] K. H. Kim, F. W. Roush and J. B. Wagoner, Characterization of inert
actions on periodic points. I., Forum Math. 12 (2000), no. 5, 565-602.
[28] K. H. Kim, F. W. Roush and J. B. Wagoner, Characterization of inert
actions on periodic points. II., Forum Math. 12 (2000), no. 6, 671-712.
[29] B. Kitchens, Symbolic dynamics: one-sided, two-sided and countable state
Markov shifts, Springer (1991).
[30] W. Krieger, On the subsystems of topological Markov chains, Ergodic The-
ory & Dynamical Systems 2 (1982), 195-202.
50
[31] S. Lightwood, Morphisms from non-periodic Z2 subshifts. I. Constructing
embeddings from homomorphisms, Ergodic Theory & Dynamical Systems
23 (2003), no. 2, 587-609.
[32] S. Lightwood, Morphisms from non-periodic Z2 subshifts. II. Construct-
ing homomorphisms to square-filling mixing shifts of finite type, Ergodic
Theory & Dynamical Systems 24 (2004), no. 4, 1227-1260.
[33] D. Lind and B. Marcus, An introduction to symbolic dynamics and coding,
Cambridge Univ. Press (1995).
[34] A. Maass, On the sofic limit sets of cellular automata, Ergodic Theory &
Dynamical Systems 15 (1995), no. 4, 663-684.
[35] M. Nasu, Topological conjugacy for sofic systems and extensions of auto-
morphisms of finite subsystems of topological Markov shifts, Springer Lec.
Notes in Math 1342 (1988), 564-607.
[36] D. S. Ornstein, Bernoulli shifts with the same entropy are isomorphic, Adv.
Math. 4 (1970), 337-352.
[37] W. Parry, Notes on coding problems for finite state processes, Bull. London
Math. Soc. 23 No. 1 (1991), 1-33.
[38] W. Parry, Unpublished communication, 2003.
[39] W. Parry, The Liv?sic periodic point theorem for non-abelian cocycles, Er-
godic Theory & Dynamical Systems 19 (1999), 687-701.
[40] W. Parry and P. Walters, Endomorphisms of a Lebesgue space, Bull. Amer.
Math. Soc. 78 (1972), 272-276.
[41] K. Schmidt, Remarks on Liv?sic? theory for nonabelian cocycles, Ergodic
Theory & Dynamical Systems 19 (1999), 703-721.
[42] S. Tuncel, Conditional pressure and coding, Israel J. Math. 39 (1981), 101-
112.
[43] P. Walters, Some results on the classification of non-invertible measure-
preserving transformations, Lecture Notes in Mathematics 318. Springer,
Berlin, Heidelberg and New York (1973), 266-276.
51