%Version 4/22/96 \input amstex \input epsf.tex %\magnification=1200 \input psfig \define\A{\roman A} \redefine\B{\roman B} \define\C{\roman C} \redefine\D{\roman D} \redefine\E{\roman E} \redefine\P{\roman P} \redefine\o{\roman o} \define\p{\roman p} \define\q{\roman q} \define\r{\roman r} \define\s{\roman s} \redefine\a{\roman a} \redefine\b{\roman b} \redefine\c{\roman c} \redefine\d{\roman d} \redefine\e{\roman e} \redefine\u{\roman u} \redefine\v{\roman v} \redefine\w{\roman w} \define\R{\Cal R} \documentstyle{amsppt} \Monograph \topmatter \title SYMBOLIC DYNAMICS AND MARKOV PARTITIONS \endtitle \author{Roy L. Adler \\ Mathematical Sciences Department \\ IBM, Thomas J. Watson Research Center \\ Yorktown Heights, NY 10598} \endauthor \email adler@watson.ibm.com \endemail \abstract The decimal expansion real numbers, familiar to us all, has a dramatic generalization to representation of dynamical system orbits by symbolic sequences. The natural way to associate a symbolic sequence with an orbit is to track its history through a partition. But in order to get a useful symbolism, one needs to construct a partition with special properties. In this work we develop a general theory of representing dynamical systems by symbolic systems by means of so-called Markov partitions. We apply the results to one of the more tractable examples: namely hyperbolic automorphisms of the two dimensional torus. While there are some results in higher dimensions, this area remains a fertile one for research. \endabstract \endtopmatter \document \subhead 1. Introduction \endsubhead \newline\newline We address the question: how and to what extent can a dynamical system be represented by a symbolic one? This has roots in a concept of basic arithmetic familiar to us all: namely, the representation of real numbers by infinite binary expansions. As the example of Section 3.2 shows this is related to partitions with special properties which is the theme of this work. K. Berg \cite{B} in his Ph.D thesis discovered partitions (now called Markov) of the two dimensional torus which give rise to discrete time Markov processes under the action of hyperbolic automorphisms. Shortly after the B. Weiss and the author \cite{AW} proved that such automorphisms are measure theoretically isomorphic if and only if they have the same entropy. Their proof was based on two ideas: \roster \item symbolic representations of dynamical systems by means of Markov partitions; \item coding between symbolic systems having equal entropy. \endroster Each of these two aspects has undergone extensive development since. The present work is concerned with a systematic treatment of the first idea within the framework of point set topology: that is, we develop the notion of a discrete time topological Markov process without any recourse to measure theory and use it to obtain symbolic representations of dynamical systems. A future paper is planned expanding on the second item above incorporating it in a general isomorphism theory of abstract dynamical systems. A disquieting aspect of the result of Adler-Weiss was a certain vagueness where one expects certainty: namely, not quite knowing how to compute the numerical entries of an certain integral matrices proven to exist. Theorem 8.4, the main one of Section 8, is an improvement on the results of Berg and Adler-Weiss, and does not suffer from this difficulty. The proof involves four cases: Case I, the simplest, was done by Anthony Manning many years ago as the author learned from Peter Walters and still may be unpublished. \newpage In Section 2, we briefly introduce the concept of an abstract dynamical system and then go on to give three important concrete examples of such systems: namely multiplication maps, toral automorphisms, and symbolic shifts. In Section 3, we discuss symbolic representations of dynamical systems and illustrate them for the three concrete systems introduced in the previous section. In Section 4, we present some general notions needed for our theory of symbolic representation of dynamical systems. In Section 5, we introduce the notion of topological partition. and show how one gets a symbolic representation from such an object. In order to simplify notation, an improvement in the choice of elements for such partitions was suggested by D Lind: namely replacing \lq\lq proper sets with disjoint interiors", a {\it proper} set being one that is the closure of its interior, by "disjoint open sets whose closures cover the space". There is a difference between an open set and the interior of its closure, and exploiting this seemingly slight difference leads not only to notational conveniences but also to pleasant simplifications in subsequent proofs. In Section 6 we define topological Markov partitions and prove Theorem 6.5, the main theorem of this work. This result concerns getting by means of Markov partitions the best that can be expected as far as symbolic representations of a dynamical systems is concerned. Also in this section we prove a converse to the main theorem, Theorem 6.10, by which one gets Markov partitions from symbolic representations. This leads to the question: does one construct Markov partitions to get symbolic representations or does one produce a symbolic representations to get Markov partitions? The answer to this riddle as far as the current evidence seems to indicate is discussed in Section 9. In Section 7, we provide results useful for constructing Markov partitions, particularly the final theorem of the section, Theorem 7.12. In Section 8, we apply Theorem 7.12 to construct certain special Markov partitions for arbitrary hyperbolic automorphisms of the two dimensional torus, which is the content of Theorem 8.4. These partitions have the virtue that a matrix specifying a hyperbolic automorphism is also the one that specifies a directed graph from which the symbolic representation is obtained. The proof we present, though involved, is quite elementary using mainly plane geometry. The spirit of this work is to rely solely on point set topology. We avoid any measure theory in this discussion. Perhaps a course in point set topology might be spiced up by using items in this work as exercises. In addition, our style of presentation is an attempt to accommodate students as well as experts. The research behind this work was carried out over many years, in different places, and with help from a number of colleagues, particularly Leopold Flatto and Bruce Kitchens. Work was done at the Watson Research Center, University of Warwick, and MSRI. Most of the research for Sections 5-7 was done in the MSRI 1992 program in Symbolic Dynamics. \subhead 2. Abstract and Concrete Dynamical Systems \endsubhead \newline\newline At its most simplistic and abstract a dynamical system is a mathematical structure capable of generating orbits which evolve in discrete time. A map of a space into itself will achieve this. Depending on one's purpose additional structure is imposed: our requires some topology. Consequently, for us an {\it abstract dynamical system} is a pair $( X , \phi ) $ where $X$ is a compact metric space with metric, say, $ d ( \cdot \, , \cdot ) $ and $\phi$ is a continuous mapping of a $X$ into itself. We shall refer to $X$ as the {\it phase} space of the dynamical system. The {\it orbit} of a point $\p \in X$ is defined to be the sequence $(\phi^n \p )_{n = 0 , 1, 2, \dots} .$ We shall consider systems where $\phi$ is onto. Also we shall be mainly, though not exclusively, interested in invertible maps-- {\it i.e.} where $\phi$ is a homeomorphism--in which case the {\it orbit} of a point $\p \in X$ is defined to be the bilaterally infinite sequence $(\phi^n \p )_{n \in {\Bbb Z}} .$ For invertible maps we can speak of past, present, or future points of an orbit depending on whether $n$ is negative, zero or positive; while for non-invertible maps there is only the present and future. For the above category of abstract systems, we have the following notion of total topological equivalence. \definition{Definition 2.1}Two systems $( X , \phi )$, $( Y , \psi ) $ are said to be {\it topologically conjugate}, $( X , \phi ) \simeq ( Y , \psi ) ,$ if there is a homeomorphism $\theta$ of $X$ onto $Y$ which {\it commutes} with $\phi$ and $\psi$: {\it i.e.}, $\phi \theta = \theta \psi .$ \enddefinition We introduce some classical concrete dynamical systems. The first type is most elementary. Though non-invertible, it illustrates admirably some essential ideas which we shall discuss later. \subsubhead 2.1 Multiplication maps \endsubsubhead \newline Let $ ( X , f )$ be the system whose phase space is the complex numbers of modulus one-- {\it i.e.} elements of the unit circle--acted upon by the mapping $f:z \rightarrow z^n$ for some integer $n > 1.$ For our purposes it is more convenient to consider a topologically and algebraically equivalent formulation. Let $X = {\Bbb R} / {\Bbb Z}$ where ${\Bbb R}$ is the real line and ${\Bbb Z}$ the subgroup of integers. Recall that elements in $X$ are cosets modulo ${\Bbb Z}.$ The {\it coset} of $x \in {\Bbb R}$ modulo ${\Bbb Z},$ which we denote by $\{ x \},$ is the set $\{ x + z | z \in {\Bbb Z} \}$ of {\it lattice translates} of $x.$ Invoking some standard terminology, the real line ${\Bbb R}$ can be referred to as the {\it universal cover} of the the circle $X$. In view of the fact that ${\Bbb Z}$ acts as a group of transformations on the universal cover ${\Bbb R,}$ a coset is also called a $ {\Bbb Z}-${\it orbit}. Two points $ x, x' $ in the same coset or $ {\Bbb Z}-$orbit are said to be {\it equivalent\/} mod ${\Bbb Z}.$ The {\it metric} is given by defining the {\it distance} between pairs of cosets as the smallest Euclidean distance between pairs of members. Recall that the coset of $x+y$ depends only on the coset of $x$ and that of $y$: that is, if $x'\in \{ x \}$ and $y'\in \{ y \},$ then $\{x'+ y'\} = \{ x + y \}.$ Thus {\it addition} of cosets given by $ \{ x \} + \{ y\} \equiv \{ x + y \}$ is well defined and so is the {\it multiplication-by-$n$} map $f: \{ x \} \mapsto \{ x \} + \dots + \{ x \}$ (n-times) $= \{ nx \}.$ This map is continuous with respect to the metric. It is not invertible: every coset $\{ x \}$ has $n$ pre-images which are $\{(x + m)/n \},\ m = 1 , \dots, n.$ The closed unit interval $\lbrack 0 , 1 \rbrack$ is a set referred to as a fundamental region for the action of ${\Bbb Z} $ on ${\Bbb R}.$ \definition{Definition 2.1.1}A {\it fundamental region} is defined as a closed set such that \roster \item it is the closure of its interior; \item every orbit under the action has at least one member in it (this is equivalent to the statement that the translates of the unit interval by elements of ${\Bbb Z}$ tile ${\Bbb R}$); \item no point in the interior is in the same ${\Bbb Z}$-orbit as another one in the closed region (this restriction does not apply to two boundary points-- {\it e.g.} the points 0 and 1 are in the same one). \endroster \enddefinition Fundamental regions are not unique: for example, the interval $\lbrack 1 , 2 \rbrack$ is also a fundamental region for the action of ${\Bbb Z} $ on ${\Bbb R},$ though not a particularly useful one. One can give another equivalent reformulation of the phase space of these systems in terms of a fundamental region with boundary points identified. Let $X$ be the closed unit interval with 0 identified with 1. We define a metric on $X$ by $$d(x, y) = \text{min} ( |x-y|, |x-y-1|, |x-y+1| ).$$ From now on let us take the notation $\{ x \}$ to mean fractional part of a real number $x.$ On $X$ the map $f$ takes the form $$f( x ) = \{ nx \}.$$ Since all numbers in a coset have the same fractional part and that number is the unique member of the intersection of the coset and $X,$ this new interpretation of $\{ x \}$ is consistent with the old. A more serious set of examples are continuous automorphisms of certain compact Abelian groups--namely the n-dimensional tori. For simplicity we restrict the discussion to the case of dimension two, generalization to higher dimensions being quite analogous. \subsubhead 2.3 Toral Automorphisms \endsubsubhead \newline Consider the two dimensional torus ${\Bbb R}^2 / {\Bbb Z}^2 $ and a continuous group automorphism $\phi$. Here the universal cover of the 2-torus is ${\Bbb R}^2 .$ The description of the action of the integers on the real line generalizes in a straight-forward manner to the action of the subgroup ${\Bbb Z}^2 $ of points with integer coordinates on the universal cover ${\Bbb R}^2.$ The definitions of cosets, lattice translates, orbits, addition, and the metric are quite similar. A continuous automorphism $\phi$ is specified by a a $2 \times 2$ matrix $\A : $ with integer entries and determinant $\pm 1 .$ Let $$\A = \left( \matrix a & b\\ c & d \endmatrix \right).$$ The matrix $\A$ determines an invertible linear transformation on ${\Bbb R^2}.$ We represent the points in the plane by row vectors and the action of the linear transformation by right \footnote{ Right multiplication on row vectors turns out to be a little more convenient than left multiplication on column vectors.} matrix multiplication. The map $\phi$ is then defined as follows: the image of the coset containing $(x,y)$ is the one containing $( a x +c y , b x +d y ) . $ This map is well-defined-- {\it i.e.}, the image does not depend on the choice of coset representative $(x, y)$-- because $\A$ is invertible and maps ${\Bbb Z}^2$ onto itself. Some things to note. The map $\phi$ is a homeomorphism. The coset $ \{ 0 \} = {\Bbb Z}^2$ is a fixed point of $\phi.$ There may of course be other fixed points. A pair $(x,y)$ is in a coset which is a fixed point if and only if it satisfies the two linear equations given by $$ (x,y)\A = (x,y) +(m,n)$$ for some pair of integers $(m,n).$ The only solutions are rational. In addition, a coset is periodic under $\phi $ if and only if it is fixed under some iterate $\A^n.$ Furthermore, if a coset contains a point with rational coordinates, then it is periodic which follows from the fact that the product of the denominators in a rational pair $(x , y)$ bounds the denominators in the sequence $(x,y), (x,y) \A, (x,y) \A^2, \dots $ which implies that the orbit of $(x,y)$ is finite. The plane ${\Bbb R}^2$ is the universal cover of the 2-torus, and any closed unit square with lattice points as corners is a fundamental region. We shall call the one with its lower left corner at the origin the {\it principal fundamental region}. Like the one dimensional case, we can formulate the system in terms of it. Let $X$ be the closed unit square with each point on one side identified with its opposite on the other. The coset of $(x, y)$ intersects $X$ in a unique point: namely, $(\{ x \} , \{ y \} ) .$ On $X$ the map $\phi$ takes the form $$\phi( x , y ) = ( \{a x + c y \} , \{ b x + d y \}).$$ Unlike the case of one dimension, other fundamental regions, as we shall see, play a crucial role in studying the action of automorphisms. Finally we come to the most basic of concrete systems. Ultimately we shall show to what extent they model others, in particular multiplication maps and hyperbolic toral automorphisms. \subsubhead 2.4 Symbolic Shifts \footnote{For comprehensive treatment of this area we refer the reader to the book by Lind and Marcus \cite{LM}.} \endsubsubhead \newline Let ${\Cal A}$, called an {\it alphabet}, denote an ordered set of $N$ symbols, often taken to be $ \{ 0,1, \dots ,N-1\}$. The domain of this system is the space $$\Sigma_N = {\Cal A}^{\Bbb Z} = \{ s = (s_n )_{n \in {\Bbb Z}} | s_n \in {\Cal A} \} \tag 2.4.1$$ of all bi-infinite sequences of elements from a set of N symbols. One can think of an element of this space as a bi-infinite walk on the complete directed graph of $N$ vertices which are distinctly labelled. Sometimes it is more convenient to label edges, in which case the picture is a single node with $N$ oriented distinctly labelled loops over which to walk. In Figure 2.I we have depicted the full 2-shift by both types of graph labelling. \midinsert %\vspace{ 1.5 in} %\hbox{\hskip 1in vertices labelled \hskip 2.3in edges labelled} \centerline{ \epsfbox{fig2i.eps}} \botcaption{Figure 2.I} Full 2-shift \endcaption \endinsert The {\it shift transformation\/} $\sigma$ is defined by shifting each bi-infinite sequence one step to the left. This is expressed by $$ (\sigma s )_n = s_{n+1}.$$ We define the distance $d(s,t)$ between two distinct sequences $s$ and $t$ as $1 / (|n|+ 1) $ where n is the coordinate of smallest absolute value where they differ. Thus if $d(s,t) < 1/n$ for $n>0$ then $ s_k = t_k$ for $-n < k < n.$ This metric makes the space $\Sigma_N$ one of the important compact ones--namely, the Cantor discontinuum-- and the shift a homeomorphism. The symbolic system $ ( \Sigma_N , \sigma )$ is called the {\it full N-shift}. Restricting the shift transformation of a full shift $\Sigma_N$ to a closed shift-invariant subspace $\Sigma,$ we get very general kind of dynamical system $(\Sigma, \sigma)$ called a {\it subshift.} Given a symbolic sequence $ s = (s_n )_{n \in {\Bbb Z}}$ and integers $m 1 $ and $-1 < \mu < 0 .$ Associated with these eigenvalues are the eigenvectors ${\v}_\lambda$ pointing into the first quadrant and ${\v}_\mu$ into the second. In Figure 3.III we have drawn two lines through the origin in the eigenvector directions. The action of $\A$ on a vector is to contract its ${\bold v}_\mu$-component by $|\mu|$ and expand its ${\v}_\lambda$-component by $\lambda.$ Note $\mu$ is negative, which causes a direction reversal besides a contraction in the ${\v}_\mu$-component. We refer to the direction of ${\v}_\lambda$ as the {\it expanding} direction and that of ${\v}_\mu$ as the {\it contracting} direction. In Figure 3.IV we draw another region with sides parallel to the expanding and contracting directions. That it is a fundamental region is verified by noting that each of the three triangles sticking out of the unit square is a translation by an element of ${\Bbb Z}^2$ of one of the three missing triangles inside. \midinsert \centerline{\epsfbox{fig3iv.eps}} \botcaption{Figure 3.IV} Another fundamental region of 2-torus \endcaption \endinsert \vskip.2truein We call this fundamental region the {\it principal} one, and draw within it the collection of open rectangles ${\Cal R} = \{ R_i \ : i = 1, 2, 3 \}$ as depicted in Figure 3.V. This family is an example of a type of partition we shall later describe as {\it Markov.} We label significant points using the same letters for those which are equivalent. \midinsert \vspace{1.5in} \centerline{\epsfbox{fig3v.eps}} \botcaption{Figure 3.V} Partition of 2-torus \endcaption \endinsert \vskip.2truein The image of this partition under the linear transformation determined by $\A$ is depicted in Figure 3.VI. In drawing it the following calculations come into play: $ (1 , 0) \A = (1 , 1) , \ ( 1 , 1) \A = (2 ,1), \ (2 ,1) \A = (3 ,2 ).$ \midinsert \centerline{ \epsfbox{fig3vi.eps}} \botcaption{Figure 3.VI} Its image \endcaption \endinsert Along with the image we have included an outline of the original partition. Notice that $\phi R_3$ is actually the same as $R_2.$ Also notice how the other $\phi R_i$ overlap $R_1$ and $R_3.$ The manner in which the image partition intersects the original partition can be summed up as follows: $\phi R_i \cap R_j \ne \emptyset$ according to whether $j$ follows $i$ in the edge graph in Figure 3.VII. \midinsert \centerline{\epsfbox{fig3vii.eps}} \botcaption{Figure 3.VII} Edge graph for $\phi$ acting on ${\Cal R}$ \endcaption \endinsert The boundary of the sets in ${\Cal R} , \ \partial R_i = \overline{R_i} - R_i ,$ consists of various line segments in the ${\v}_\lambda$ and ${\v}_\mu$ directions. The union of those of the $R_i$'s in the ${\v}_\lambda$-direction is called the {\it expanding boundary of the partition} and those in the ${\v}_\mu$-direction, the {\it contracting boundary}. By lattice translations of the various bounding segments, we can reassemble their union into two intersecting line segments through the origin, $o\bar \b$ and $\a\bar \d,$ as shown in Figure 3.VI. The behavior of the boundary under the action $\A$ leads to a topological Markov shift representation. The essential properties are that $\a\bar \d $ contains its image under $\A$; whereas $o\bar \b$ is contained in its image, or equivalently $o\bar \b$ contains its inverse image. Because $\A$ preserves eigen-directions and keeps the origin fixed, it is easy to see that $o\bar \b $ gets stretch over itself; but because there is a reflection involved it is not enough to know that the length of $\a\bar \d $ is contracted by $\A.$ We must show that the points $\a$ and $\bar \d $ on the line segment $\a\bar \d$ have their images within that segment. These points are the projections to $\l_\mu$ in the ${\bold v}_\lambda$-eigen-direction from $(0,1)$ and $(1 ,0 )$ respectively: so their images are the projections from the images of these lattice points which are $(1, 0)$ and $(1,1)$ respectively. Thus the image of $\bar \d $ is $\a,$ and the image of $a$ is $c.$ These facts about the expanding and contracting boundaries imply that refinements of the original partition under positive iterates of $\phi$ do not have any new boundary segments in the ${\v}_\mu$-direction that aren't already contained in $\a\bar \d$, while under negative iterates of $\phi$ there are no new ones in the ${\v}_\lambda$-direction not already in $o\bar \b.$ From this we obtain that for $n \in {\Bbb N}$ a set $ \phi^n R_i \cap R_j$, if non-empty, is a union of rectangles stretching in the expanding direction all the way across $R_j$. Similarly, a non-empty $ R_i \cap \phi^{-n} R_j $ is a union of rectangles stretching in the contracting direction all the way across $R_i.$ When $n=1,$ it can be seen that these each of these unions consists of a single rectangle. This implies that if $\bigcap_{k=-n}^{0} \phi^{-k} R_{s_k} \ne \emptyset,$ then this intersection is a single rectangle stretching all the way across $R_{s_0}$ in the expanding direction. Similarly, if $\bigcap_{k=0}^{n} \phi^{-k} R_{s_k}\ne \emptyset , $ then this set is a single rectangle stretching all the way across $R_{s_0}$ in the contracting direction. \midinsert \centerline{\epsfbox{fig3viii.eps}} \botcaption{Figure 3.VIII} Intersections \endcaption \endinsert Combining these two results we have that a non-empty closed set of the form $\overline{\bigcap_{k=-n}^{n} \phi^{-k} R_{s_k}}$ is a closed rectangle. The diameter of these sets is uniformly bounded by $\text{constant}\times |\mu|^n$. Thus as $n \rightarrow \infty,$ a sequence of such sets decreases to a point in $X.$ Consequently, such a point can be represented by a sequence $s = (s_n)_{n \in {\Bbb Z}}.$ If fact, all points of the torus can be so represented. If $\bigcap_{k=-n}^{n} \phi^{-k} R_{s_k} \ne \emptyset,$ then it is clear that $R_{s_i} \cap \phi^{-1}R_{s_{i+1}} \ne \emptyset$ for $-n \le i \le n-1. $ The converse which is the Markov property is really the main one we are extracting from the geometry of this example. As we have seen $R_{s_i} \cap \phi^{-1}R_{s_{i+1}} \ne \emptyset$ if and only if edge $ s_{i+1} $ follows edge $s_i$ according to the the graph of Figure 3.VII. This means that the sequences $s = (s_n)_{n \in {\Bbb Z}}$ are elements is a topological Markov shift. Once again sets $R_i$ have an obvious product structure. For $\p \in R_i$ we call the segment $h_i(\p)$ specified by intersection of $ R_i$ and the line through $p $ in the expanding direction the {\it horizontal \/} through $\p.$ Similarly, we refer to $v_i(\p)$ given by the intersection of $R_i$ and the line through $p$ in the contraction direction as the {\it vertical}. Each rectangle is homeomorphic to the Cartesian product of any one of its horizontals with any one of its verticals. Just like for topological Markov shifts, the toral automorphism respects this structure: namely, for $ \p \in R_i \cap \phi^{-1} R_j$ the following holds: $$ \phi v_i(\p) \subset v_j(\phi \p ) , $$ $$ \phi h_i(\p) \supset h_j(\phi \p) . $$ We shall incorporate we have just described in a comprehensive theory. \subhead 4. More on Abstract Dynamical Systems \endsubhead \definition{Definition 4.1}A dynamical system $(X ,\phi)$ is said to be {\it irreducible} if for every pair of open sets $U , V $ there exists $n \ge 0$ such that $\phi^n U \cap V \ne \emptyset .$ \enddefinition Another concept we need is the following \definition{Definition 4.2} A point $\p$ is said to be {\it bilaterally transitive} if the forward orbit $\{ \phi^n \p \vert \ n \ge 0 \}$ and the backward orbit $\{ \phi^n \p \vert \ n < 0 \}$ are both dense in $X$. \enddefinition \remark{Remark.} A symbolic sequence in a topological Markov shift is bilaterally transitive if every admissible block appears in both directions and infinitely often. \endremark We use the notation $BLT ( A) $ to denote the subset of bilaterally transitive points in $A \subseteq X .$ In an irreducible system the bilaterally transitive points turn out to be everywhere dense. To prove this, we recall the following theorem of point set topology. The theorem is more general, but can be slightly simplified in the case where the space $X$ is a compact metric space. \proclaim{Baire Category Theorem 4.3} Let $\{ U_n \} $ be a countable collection of open dense subsets of $X .$ Then $\bigcap U_n$ is nonempty. In fact $\bigcap U_n$ is dense in $X .$ Equivalently, a compact metric space in not the union of a countable collection of nowhere dense sets. \endproclaim \demo{Proof} Choose inductively balls $B_n$ such that $B_n \subset \overline{B_n} \subset U_n ,$ and $\overline{B_n} \subset B_{n-1} .$ The first property is easily achieved in a metric space; the second because $U_n$ is dense which implies that $B_{n-1} \cap U_{n}$ is a non-empty open set. The sequence $(\overline{B_n})_{n \in {\Bbb N}}$ has the finite intersection property: so by compactness $ \bigcap \overline{ B_n}$ is nonempty. But $ \bigcap \overline {B_n} \subset \bigcap B_n \subset \bigcap U_n .$ Thus the intersection $\bigcap U_n$ is not empty. It is also dense which is a consequence of replacing $ U_n$ in the above argument by $U_n \cap B $ and $X$ by $\overline{B}$ where $B$ is any ball. \qed \enddemo \proclaim{Proposition 4.4}If $(X,\phi)$ is irreducible, then the set of bilaterally transitive points is dense in $X .$ \endproclaim \demo{Proof} Let $\{ U_n \}$ be a countable basis for $X.$ Since $X$ is irreducible, $\bigcup_{k \ge 0} \phi^kU_n$, as well as $\bigcup_{k < 0} \phi^kU_n$, is dense in $X $ for each $n .$ The set $ BLT(X)$ of bilaterally transitive points can be expressed as $$BLT(X) = \bigcap_{n}( \bigcup_{k \ge 0} \phi^kU_n \cap \bigcup_{k < 0} \phi^kU_n ) .$$ We apply the Baire Category Theorem to get $BLT(X) \ne \emptyset .$ But $BLT(X)$ contains the whole orbit of any of its points and the orbit of any of its points is dense in $X .$ \qed \enddemo The three examples we have discussed exhibit a certain property which is easily verified. It is concerns the divergence of orbits and is defined as follows. \definition {Definition 4.5}A homeomorphism ${\phi}$ is said to be {\it expansive} if there exists a real number $c>0$ such that if $ d (\phi^n \p , \phi^n \q ) < c$ for all $n \in {\Bbb Z}$ then $\p = \q$. \enddefinition In the theory of Markov partitions this property plays a key role. Representation of dynamical systems by shifts of finite type, while possible for certain non-expansive systems, really only seems natural for expansive ones. Next we formalize a property of mappings between dynamical systems previously alluded to in connection with binary expansions. \definition{Definition 4.6}For two general dynamical systems $(X , \phi)$ and $(Y , \psi)$ we call the second a {\it factor} of the first and the first and {\it extension} of the second, if there exists a map $\pi$ of $X$ into $Y$, which we call a {\it factor map}, such that \roster \item"{(i)}" $ \psi \pi = \pi \phi $, \item"{(ii)}" $\pi$ is continuous, \item"{(iii)}"$\pi$ is onto. \endroster Furthermore, we say $\pi$ is a {\it finite} factor map or that it is {\it bounded-to-one} if \roster \item"{(iv)}" there is a bound on the number of pre-images; \endroster and {\it essentially \footnote{{\rm This term is used because in irreducible systems the non-doubly transitive points are negligible in both the sense of category and measure.}} one-to-one} if \roster \item"{(v)}" every doubly transitive point has a unique pre-image. \endroster \enddefinition \midinsert \centerline{\epsfbox{fig4i.eps}} \botcaption{Figure 4.I} Commutative diagram illustrating a factor map \endcaption \endinsert \vskip.2truein We remark that a topological conjugacy \footnote{Ther term derives from the group theory notion of conjugate elements and its usage is standard in the subject. In the sense we are using it, better would have been {\it homomorphism} for {\it factor map} and {\it isomorphism} for {\it topological conjugacy}. These are the terms which denote the property of preserving structure.} is a finite factor map where the bound on the number of pre-images is one in condition 1.2(iv). As we shall see, the seemingly slight weakening of the chains of topological conjugacy, which is what the definition of an essentially one-to-one finite factor map is meant to do, allows the necessary freedom to get symbolic representations for smooth dynamical systems. \proclaim{Proposition 4.7} Let $\pi$ be a factor map of $(X , \phi)$ and $(Y , \psi):$ {\it i.e.} $\pi$ satisfies properties (i), (ii), and (iii) of Definition 4.6. If $(X , \phi)$ is irreducible, then so is $(Y, \psi);$ and $Y = \overline{BLT( Y)} .$ \endproclaim \demo{Proof} Let $U ,V $ be non-empty open subsets of $Y .$ By properties (i) and (iii) of factor maps, $\pi^{-1}U , \pi^{-1}V$ are also non-empty and open. Since $(X, \phi) $ is irreducible,there exists $n > 0$ such that $\phi^n (\pi^{-1}U )\cap \pi^{-1}V \ne \emptyset . $ By 4.6(i), $$\emptyset \ne \pi[\phi^n(\pi^{-1} U )\cap \pi^{-1} V] =\pi [ \pi^{-1} (\phi^n U \cap V)] = \psi^n U \cap V .$$ Thus $(Y , \psi)$ is irreducible and from Proposition 4.4 follows that $Y = \overline{BLT( Y)}.$ \qed \enddemo \proclaim{Proposition 4.8}Let $(X,\phi)$ be irreducible and $\pi$ an essentially one-to-one factor map of $(X,\phi)$ onto $(Y,\psi)$: {\it i.e.} $\pi$ satisfies (i),(ii),(iii), and (v) of Definition 4.6. Then $\pi$ maps $ BLT(U)$ homeomorphically onto $BLT(\pi(U))$ for any open subset $U$ of $X.$ \endproclaim \demo{Proof} From the properties of $\pi,$ if the forward orbit of $x$ hits every nonempty open subset of $X,$ then the forward orbit of $\pi (x)$ hits every nonempty open subset of $Y.$ Thus $\pi BLT(U) \subset BLT(\pi (U)).$ We have that $\pi$ is a continuous one-to-one map of $BLT(U)$ into $BLT(\pi(U)).$ We prove next that its inverse is continuous also. The proof is a standard compactness argument which goes as follows. Suppose $y_n \rightarrow y,$ where $y_n ,y \in BLT(\pi(U)).$ We shall prove that $\pi^{-1} y_n \rightarrow \pi^{-1} y.$ By compactness the sequence $(\pi^{-1} y_n )_{n \in {\Bbb N}}$ has limit points in $X.$ Let $x$ be any one of these limit points. By continuity $\pi x = y .$ But the pre-image of $y$ is unique: so the sequence $(\pi^{-1} y_n )_{n \in {\Bbb N}}$, having only one limit point, has a limit which is $\pi^{-1} y.$ Now let $x\in \pi^{-1}BLT(\pi(U))\subset U$ and let $V$ be any non-empty open subset of $X.$ Choose $v\in BLT(V).$ Then by what we have already shown $\pi (v) \in BLT(\pi(V)).$ Then there exists a sequence of positive integers $k_n$ such that $\psi^{k_n} \pi(x) \rightarrow \pi (v).$ Thus $$ \phi^{k_n}( x ) = \pi^{-1} \psi^{k_n} \pi(x)\rightarrow \pi^{-1} \pi (v)=v.$$ Thus $x \in BLT(U).$ We have therefore established $ \pi^{-1} BLT(\pi(U)) \subset BLT(U):$ in other words, $BLT(\pi(U)) \subset \pi BLT(U).$ \qed \enddemo \proclaim{Proposition 4.9} Under the hypothesis of Proposition 4.8, if $U$ is an open subset of $X$, then $BLT(\pi U)= BLT \lbrack \pi U \rbrack^o$ and $\pi \overline{U} = \overline{\lbrack \pi U\rbrack^o}.$ \endproclaim \demo{Proof} Let $y \in BLT( \pi U).$ Then the unique pre-image of $y$ lies in $BLT(U),$ and $\pi y$ is not therefore in the closed set $\pi (X-U).$ Hence, $\pi y \in Y-\pi(X-U) \subset \lbrack \pi U \rbrack^o.$ Therefore, $BLT(\pi U)= BLT \lbrack \pi U \rbrack^o.$ From the continuity properties of $\pi,$ Proposition 4.8, and what was just proven, we get the following string of equalities: $\pi (\overline{U}) = \pi(\overline{BLT(U)}) =\overline{BLT(\pi U)} = \overline{BLT\lbrack \pi U \rbrack^o}= %\overline{\lbrack \pi U \rbrack^o}. $ \qed \enddemo \subhead Exercises \endsubhead \roster \item"{4.1}" We call a directed graph $G$ {\it irreducible} if given any pair of nodes $i,j$ there is a directed path from $i$ to $j$. Show that if $G$ is irreducible as a graph, then the dynamical system $(\Sigma_G, \sigma)$ is irreducible. Conversely, show that if the dynamical system $(\Sigma_G, \sigma)$ is irreducible then there is an irreducible sub-graph $G^\prime$ such that $\Sigma_G =\Sigma_{G^\prime}.$ \item"{4.2}" Given any topological Markov shift system $(\Sigma_G)$ there exists irreducible sub-graphs $G_1, \dots, G_M$ such that $$\Sigma_G = \Sigma_{G_1} \cup \dots \cup \Sigma_{G_M} \text{(disjoint)}.$$ \endroster \subhead 5. Topological Partitions \endsubhead \definition{Definition 5.1}We call a finite family of sets ${\Cal R} = \{ R_0, R_1 , \dots , R_{N-1} \}$ a {\it topological partition} for a compact metric space $X$ if: \roster \item"{(1)}" Each $R_i$ is open \footnote{Previous authors have taken these sets to be closed sets with the property that each is the closure of its interior. The present variation is slightly more general, just enough to make some notation and certain arguments simpler. In fact, an important example is presented in section 9 of a partition whose elements are not the interiors of their closures.} \item"{(2)}" $R_i \cap R_i = \emptyset , i \ne j $ \item"{(3)}"$X = \overline{R_0 }\cup \overline{ R_1} \cup \dots \cup \overline{ R_{N-1}} .$; \endroster \enddefinition {\bf Remark.} For open sets $U , V, \overline{U} \cap V \ne \emptyset \Rightarrow U \cap V \ne \emptyset .$ So for members of a topological partition we get the following string of implications: $R_i \cap R_j = \emptyset \Rightarrow \overline{R_i} \cap R_j = \emptyset \Rightarrow \overline{R_i}^o \cap R_j = \emptyset \Rightarrow \overline{R_i}^o \cap \overline{R_j} = \emptyset \Rightarrow \overline{R_i}^o \cap \overline{R_j}^o = \emptyset.$ Thus $\overline{R_i}^o \cap \overline{R_j}^o = \emptyset$ for $ i \ne j .$ \definition{Definition 5.2} Given two topological partitions ${\Cal R} = \{ R_0, R_1 , \dots , R_{N-1} \}$ and ${\Cal S} = \{ S_0, S_1 , \dots , S_{M-1} \}$ we define their {\it common topological refinement} ${\Cal R} \vee {\Cal S}$ as $${\Cal R} \vee {\Cal S} = \{ {R_i \cap S_j} : R_i \in {\Cal R} , S_j \in {\Cal S} \} .$$ \enddefinition \proclaim{Proposition 5.3} The common topological refinement of two topological partitions is a topological partition. \endproclaim \demo{Proof} Let ${\Cal R}$ and ${\Cal S}$ be the two partitions in question. First of all, it is clear that the elements of ${\Cal R} \vee{\Cal S}$ are disjoint. We show that the closure of elements of ${\Cal R} \vee{\Cal S}$ cover $X$. Let $\p \in X$. We have that $\p \in \overline{R_i}$ for some $i$. Thus there exists a sequence of points $ \p_n \in R_i$ such that $d(\p_n , \p) < 1/n$. Since ${\Cal S}$ is a topological partition, for each $n$ there exists $S_{j_n} \in {\Cal S}$ such that $\p_n \in \overline{S_{j_n}}.$ Since ${\Cal S}$ is finite, there exists an index $j$ such that $j_n = j $ for an infinite number of $n$ so that we can assume that the $\p_n$ were chosen in the first place such that each $j_n = j.$ Since $\p_n \in R_i \cap \overline{S_j}$ we can choose a sequence of points $ \q_{m , n } \in R_i \cap S_j$ such that $d(\q_{m , n } , \p_n) < 1/m$. Thus $d (\q_{n , n}, \p) < 2/n $ whence $\q_{n , n} \rightarrow \p$ as $n \rightarrow \infty$. Therefore $\p \in \overline{R_i \cap S_j}$. \qed \enddemo \proclaim{Proposition 5.4} For dynamical system $(X , \phi)$ with topological partition ${\Cal R}$ of $X$, the set $\phi^n {\Cal R} $ defined by $\phi^n {\Cal R} = \{ \phi^n R_1, \dots , \phi^n R_{N-1} \}$ is again a topological partition. \endproclaim \demo{Proof} This is an immediate consequence of the following: (1)the image of a union is the union of images for any map; (2) a homeomorphism commutes with the operation of taking closures; (3)the image of an intersection is the intersection of images for a one-one map. \qed \enddemo From Proposition 5.3 and 5.4 we have that for $ m \le n , \ \bigvee_m^n \phi^k {\Cal R} = \allowmathbreak \phi^{m} {\Cal R} \vee \phi^{m-1} {\Cal R} \vee \dots \vee \phi^{n} {\Cal R}$ is again a topological partition. We shall use the notation $${\Cal R}^{(n)} \equiv \bigvee_{k=0}^{n-1} \phi^{-k} {\Cal R} .$$ Thus $ {\Cal R}^{(2)} = {\Cal R} \vee \phi^{-1} {\Cal R} = \{ R_i \cap \phi^{-1} R_j : R_i , R_j \in {\Cal R} \} .$ Observe that $({\Cal R}^{(2)})^{(2)} = {\Cal R}^{(3)} ,$ or more generally $ ({\Cal R}^{(n)})^{(m)} = {\Cal R}^{(n+m-1)} .$ The collection $\bigcup \phi^n {\Cal R} : n \in {\Bbb Z}$ is a collection of open dense sets to which we can apply the Baire theorem, but due to its special nature we can achieve a slightly stronger result with the same sort of proof. \proclaim{Proposition 5.5}Let ${\Cal R}$ be a topological partition for dynamical system $(X , \phi) .$ For every $\p \in X$ there exists a sequence $ ( R_{s_k})_{k \in {\Bbb Z}} $ of sets in ${\Cal R}$ such that $\p \in \bigcap_{n = 0}^\infty \overline{\bigcap_{-n}^{n} \phi^{-k} R_{s_k}}.$ \endproclaim \demo{Proof} Since $\bigvee_m^n \phi^k {\Cal R}, \ m \le n ,$ is a topological partition, there is a set in it whose closure contains $\p ,$ say $\overline{\bigcap_{m}^{n} \phi^{-k} R_{s_k}}.$ We next show that in the refinement $\bigvee_{m-1}^{n+1} \phi^k {\Cal R}$ the elements of the form ${ \bigcap_{m-1}^{n+1} \phi^{-k} R_{t_k}}$ where $ t_k = s_k \text{ for } m \le k \le n $ comprise a subfamily which is a topological partition of $\ \overline{\bigcap_{m}^{n} \phi^{-k} R_{s_k}} .$ Because $\bigvee_{m-1}^{n+1} \phi^k {\Cal R}$ satisfies 5.1(1) and (2), so does any subfamily. Condition 5.1(3) is a consequence of $$\bigcup \Sb 0 \le t_{m-1} \le N-1 \\ 0 \le t_{n+1} \le N-1 \\ t_k=s_k, \ m \le k \le n \endSb \bigcap_{m-1}^{n+1} \phi^{-k} R_{t_k} = \bigcap_{m}^{n} \phi^{-k} R_{s_k} $$ and the fact that the closure of a union is the union of closures. Thus we can choose by induction the sets $R_{s_k}$ as follows. Once having specified sets $ R_{s_{-n}} , \dots , R_{s_n} $ such that $\p \in \overline{\bigcap_{-n}^{n} \phi^{-k} R_{s_k}},$ we can find sets $R_{s_{-n-1}}$ and $R_{s_{n+1}}$ such that $\p \in \overline{\bigcap_{-n-1}^{n+1} \phi^{-k} R_{s_k}}.$ Hence there exists a sequence $ ( R_{s_k})_{k \in {\Bbb Z}}$ of sets in ${\Cal R}$ such that $\p \in \bigcap_{n = 0}^\infty \overline{\bigcap_{-n}^{n} \phi^{-k} R_{s_k}}.$ \qed \enddemo \remark{Remark.} With a slight modification of this proof somewhat more can be established: namely, a finite sequence of sets $ R_{s_m} , R_{s_{m+1}} , \dots , R_{s_n} $ can be extended to a bi-infinite sequence $(R_{s_n})_{n \in {\Bbb Z}}$ such that if $\p \in \overline{\bigcap_{m}^{n} \phi^{-k} R_{s_k}} , \ m\le n ,$ then $\p \in \bigcap_{n = 0}^\infty \overline{\bigcap_{-n}^{n} \phi^{-k} R_{s_k}}.$ We can even go further and make the same claim about extending a one-sided infinite sequence $R_{s_m}, R_{s_{m+1}} , \dots$ to a bi-infinite one. \endremark \definition{Definition 5.6}We define the {\it diameter} $d ({\Cal R})$ of a partition ${\Cal R}$ by $$d({\Cal R}) = \max_{R_i \in {\Cal R}} d( R_i) $$ where $d (R_i) \equiv \sup_{x,y \in R_i} d (x , y).$ \enddefinition \definition{Definition 5.7}We call a topological partition a {\it generator} for a dynamical system $(X , \phi)$ if $\lim_{n \to \infty} d \left( \bigvee_{-n}^{n} \phi^k {\Cal R} \right) = 0 .$ \enddefinition If ${\Cal R}$ is a generator then clearly $\lim_{n \to \infty} d \left( \bigcap_{-n}^{n} \phi^{-k} R_{s_k} \right) = 0 $ for any sequence of symbols $(s_i)_{i \in {\Bbb Z}} \in \{ 0 , \dots , N-1 \}^{\Bbb Z} .$ The converse is also true (see exercise 5.1). In addition $d \left( \bigcap_{n = 0}^\infty \overline{\bigcap_{-n}^{n} \phi^{-k} R_{s_k}} \right) = 0.$ Hence in Proposition 5.5, if ${\Cal R}$ is a generator and $\p \in \bigcap_{n = 0}^\infty \overline{\bigcap_{-n}^{n} \phi^{-k} R_{s_k}} ,$ then $\p = \bigcap_{n = 0}^\infty \overline{\bigcap_{-n}^{n} \phi^{-k} R_{s_k}} .$ The following proposition gives sufficient conditions on a topological partition in terms of its diameter for it to be a generator. \proclaim{Proposition 5.8.} Let $(X ,\phi)$ be expansive and ${\Cal R}$ be a topological partition such that $d ( {\Cal R} ) < c $ where $c$ is the expansive constant. Then ${\Cal R}$ is a generator; \endproclaim \demo{Proof}The set $\bigcap_{-\infty}^{\infty} \phi^{-k} \overline{R_{s_k}}$ contains at most one point and thus has zero diameter: for if there exists $\p , \q \in \bigcap_{-\infty}^{\infty} \phi^{-k} \overline{R_{s_k}} ,$ then $ d ( \phi^n \p , \phi^n \q ) < c $ for $ n \in {\Bbb Z } $ implying $\p = \q .$ Since $\bigcap_{-n}^{n} \phi^{-k} R_{s_k} \subset \bigcap_{-n}^{n} \phi^{-k} \overline{R_{s_k}} , \allowmathbreak d \left( \lim_{n \to \infty} \bigcap_{-n}^{n} \phi^{-k} R_{s_k} \right) = d\left( \bigcap_{-\infty}^{\infty} \phi^{-k} \overline{R_{s_k}}\right) = 0 .$ From Exercise 5.1 we get that ${\Cal R}$ is a generator. \qed \enddemo \remark{Remarks} Generally we merely have the inclusion relation $$\bigcap_{n = 0}^\infty \overline{\bigcap_{-n}^{n} \phi^{-k} R_{s_k}} \subset \bigcap_{-\infty}^{\infty} \phi^{-k} \overline{R_{s_k}} \tag 5.9$$ but not equality. However, when the sets of the partition are small enough-- namely, when the hypothesis of Proposition 5.8 is satisfied-- we do have equality: that is, if $\bigcap_{n = 0}^\infty \overline{\bigcap_{-n}^{n} \phi^{-k} R_{s_k}} \ne \emptyset $ then $\bigcap_{n = 0}^\infty \overline{\bigcap_{-n}^{n} \phi^{-k} R_{s_k}} = \allowmathbreak \bigcap_{-\infty}^{\infty} \phi^{-k} \overline{R_{s_k}} .$ From the inclusion relation (5.9) we see that if $\pi(s) = \p , $ then $ \p \in \overline{R_{s_0}}.$ Thus if $x$ belongs only to $\overline{R_i}$, then $s_0 = i .$ In particular, by the remark following Definition 5.1, if $\p \in R_i$ or $\p \in \overline{R_i}^o ,$ then $s_0 = i .$. In addition, if there exists sequences $s , t$ such that $\pi(s) = \pi(t) = \p $ and $ s_0 = i \ne j = t_0 ,$ then $ \p \in \overline{R_i} \cap \overline{R_j} , \ i \ne j ;$ and conversely. In which case $\p \in (\overline{R_i} - \overline{R_i}^o )\cap (\overline{R_j} - \overline{R_j}^o) = \partial R_i \cap \partial R_j :$ {\it i.e.} $\p$ belongs to the boundary of partition elements. \endremark Let ${\Cal R} = \{ R_1, \dots , R_N \}$ be a generator for a dynamical system $(X ,\phi)$ Let $\Sigma$ be the subset of the full $N$-shift defined by $$ \Sigma \equiv \{ s = ( \dots, s_n, \dots) : \bigcap_{n = 0}^\infty \overline{\bigcap_{-n}^{n} \phi^{-k} R_{s_k}} \ne \emptyset \}. \tag 5.10$$ Because the topological partition ${\Cal R}$ is a generator, the non-empty infinite intersection $\bigcap_{ n = 0}^\infty \overline{\bigcap_{k=-n}^{n} \phi^{-k} R_{s_k}}$ consists of a single point. Therefore, we can define a map $\pi : \Sigma \longrightarrow X$ by $$ \pi(s) = \bigcap_{ n = 0}^\infty \overline{\phi^{n} R_{s_{-n}} \cap \phi^{n-1} R_{s_{-n+1}} \cap \dots \cap \phi^{-n} R_{s_n}} . \tag 5.11$$ \midinsert \centerline{\epsfbox{fig5i.eps}} \botcaption{Figure 5.I} Commutative diagram for symbolic representation \endcaption \endinsert \vskip.2truein \proclaim{Proposition 5.12.} Let the dynamical system $(X ,\phi)$ have a topological partition ${\Cal R}$ which is a generator. Then $\Sigma$ as defined by (5.10) is a closed shift-invariant subset of $\Sigma_N$ and the map $\pi$ given by (5.11) is a factor map of the dynamical system $(\Sigma , \sigma)$ onto $(X, \phi)--$ {\it i.e.}, $\pi$ satisfies the following items of Definition 4.6: \roster \item"{(i)}" $ \sigma \pi = \pi \phi $, \item"{(ii)}" $\pi$ is continuous, \item"{(iii)}"$\pi$ is onto. \endroster \endproclaim \demo{Proof} To prove $\Sigma$ is closed we must show that if $s = (\dots, s_k, \dots ) \in \overline{\Sigma}$ then $$\bigcap_{n = 0}^\infty \overline{\bigcap_{-n}^{n} \phi^{-k} R_{s_k}} \ne \emptyset,\tag 5.13$$ which then implies that $s \in \Sigma.$ For each $n > 1$ there is a sequence $t = ( \dots, t_k, \dots) \in \Sigma$ such that $d(t,s)<1/n.$ This means that $ t_k = s_k, -n \le k \le n $ so that $$\overline{\bigcap_{-n}^{n} \phi^{-k} R_{t_k}} = \overline{\bigcap_{-n}^{n} \phi^{-k} R_{s_k}}.$$ Because $t\in \Sigma,$ this set is non-empty. Since this is so for arbitrary $n$ and these sets form a decreasing sequence of non-empty closed sets, applying compactness we get 5.13. To prove $\Sigma$ is $\sigma-$invariant we must show that if $s\in \Sigma $ then $\sigma s \in \Sigma:$ in other words, for $n \ge 0,$ if $\bigcap_{-n}^{n} \phi^{-k} R_{s_k} \ne \emptyset$ then $\bigcap_{-n}^{n} \phi^{-k} R_{s_{k+1}} \ne \emptyset.$ This follows from using the distributive property of $\phi^{-1}$ with respect to intersections and reindexing: {\it i.e.} $$\phi^{-1}\left( \bigcap_{-n}^{n} \phi^{-k} R_{s_{k+1}} \right) = \bigcap_{-n+1}^{n+1} \phi^{-k} R_{s_k} \supset \bigcap_{-n+1}^{n-1} \phi^{-k} R_{s_k}. $$ We now turn our attention to the properties of $\pi.$ \newline {\it (i) $\pi$ satisfies $\pi \sigma = \phi \pi .$} This follows from reindexing after applying the property that a homeomorphism commutes with the closure operation and preserves intersections: to wit, $$ \align \phi \pi (s) &= \phi\bigcap_{n=0}^\infty\overline{\bigcap_{-n}^{n} \phi^{-k} R_{s_k}}\\ &=\bigcap_{n=0}^\infty\overline{\bigcap_{-n}^{n} \phi^{-k+1} R_{s_k}}\\ &=\bigcap_{n=0}^\infty \overline{\bigcap_{-n-1}^{n-1}\phi^{-k}R_{s_{k+1}}}\\ &=\bigcap_{n=0}^\infty \overline{\bigcap_{-n+1}^{n-1}\phi^{-k}R_{s_{k+1}}} = \pi(\sigma s). \endalign $$ {\it (ii) $\pi$ is continuous.} From the generating property of ${\Cal R}$, given $\epsilon >0 $ there is a positive integer $n$ such that $d \bigl( \overline{\bigcap_{-n}^{n} \phi^{-k} R_{s_k}} \bigr) < \epsilon.$ Thus, for $s , t \in \Sigma_G$, there is a $\delta > 0$, namely $ \delta = 1/(n+1)$, such that if $d ( s , t ) < \delta$ then $ \pi (s), \pi(t) \in \overline{\bigcap_{-n}^{n} \phi^{-k} R_{s_k}}.$ \bigskip {\it (iii) $\pi$ is onto.} This follows immediately from Proposition 5.5. \bigskip \qed \enddemo \subhead Exercises \endsubhead \roster \item"{5.1}" Let ${\Cal R}$ be a topological partition for a dynamical system $(X , \phi)$. Prove that if $\lim_{n \to \infty} d \left( \bigcap_{-n}^{n} \phi^{-k} R_{s_k} \right) = 0 $ for any sequence of symbols $(s_i)_{i \in {\Bbb Z}} \in \{ 0 , \dots , N-1 \}^{\Bbb Z} $ then $\lim_{n \to \infty} d \left( \bigvee_{-n}^{n} \phi^k {\Cal R} \right) = 0. $ \endroster \newline\newline\newline \subhead 6. Markov partitions and symbolic extensions \endsubhead \newline\newline \definition{Definition 6.1}We say that a topological partition ${\Cal R}$ for a dynamical system $(X , \phi)$ satisfies {\it the $n$-fold intersection property} for a positive integer $n \ge 3,$ if $R_{s_k} \cap \phi^{-1} R_{s_{k+1}} \ne \emptyset , \ 1 \le k \le n-1 \Rightarrow \bigcap_{k=1}^{n} \phi^{-k} R_{s_k} \ne \emptyset .$ Furthermore, we call a topological partition {\it Markov} if it satisfies the $n$-fold intersection property for all $n \ge 3 .$ \enddefinition \remark{Remark.}In section 3.1 and before the term "Markov" topological generator was defined, we considered the partition ${\Cal C} = \{ C_a: a \in A \}$ consisting of the elementary cylinder sets $C_a = \{ s \in \Sigma_G : s_0 = a \}$ for a dynamical system $( \Sigma_G , \sigma)$ where $\Sigma_G$ is a shift of finite type base on an alphabet $A$. As one might have guessed this partition is the prototype of a topological Markov generator. \endremark \proclaim{Proposition 6.2} If ${\Cal R}$ is a Markov partition, then so is $\bigvee_{m}^{n} \phi^k {\Cal R} $ for any $ m \le n .$ \endproclaim \demo{Proof} We leave the proof as an exercise. \qed \enddemo If a topological partition ${\Cal R}$ satisfies the $n$-fold intersection property, then it satisfies $k$-fold ones for all smaller $k$. To increase the order we shall utilize the following. \proclaim{Bootstrap Lemma 6.3} If ${\Cal R}$ satisfies the 3-fold and ${\Cal R}^{(2)}$ satisfies the $n$-fold intersection properties, $n \ge 3 ,$ then ${\Cal R}$ satisfies the $(n+1)$-fold intersection property. \endproclaim \demo{Proof}Suppose $ R_{i_k} \cap \phi^{-1} R_{i_{k+1}} \ne \emptyset , \ 1 \le k \le n .$ Because ${\Cal R}$ satisfies the 3-fold intersection property, we have $$ R_{i_k} \cap \phi^{-1} R_{i_{k+1}} \cap \phi^{-2} R_{i_{k+2}} \ne \emptyset , \ 1 \le k \le n-1 .$$ In other words, $$( R_{i_k} \cap \phi^{-1} R_{i_{k+1}})\cap \phi^{-1} ( R_{i_{k+1}} \cap \phi^{-1} R_{i_{k+2}}) \ne \emptyset , \ 1 \le k \le n-1 .$$ Because ${\Cal R}^{(2)}$ satisfies the $n$-fold intersection property, we obtain $$ \bigcap_1^{n+1} \phi^{-k} R_{i_k} = \bigcap_1^{n} \phi^{-k} ( R_{i_k} \cap \phi^{-1}R_{i_{k+1}}) \ne \emptyset.$$ \qed \enddemo Suppose a dynamical system $(X ,\phi)$ has a Markov generator ${\Cal R} = \{ R_0, \dots , R_{N-1} \} $. We define an associated topological Markov shift given by the directed graph $G$ whose vertices are labelled by ${\Cal A} = \{ 0 , 1 , \dots , N-1 \}$ and in which the $i$-the vertex is connected to the $j$-th, $i \rightarrow j$, iff $R_i \cap \phi^{-1} R_j \ne \emptyset .$ So by definition of the Markov shift associated with a transition matrix of a directed graph, $$\Sigma_G = \{ s = (s_n)_{n \in {\Bbb Z}} : R_{s_{n-1}} \cap \phi^{-1} R_{s_{n}} \ne \emptyset , s_n \in {\Cal A} , n \in {\Bbb Z} \} . \tag 6.4$$ This set coincides with the subsystem defined by 5.10 which is easily seen as follows. On one hand, for $s \in \Sigma_G$, each of the closed sets $$\{ \overline{ \bigcap_{k=-n}^{n} \phi^{-k} R_{s_k}} \ | \ n = 1 , 2 \dots \}$$ for any $n \ge 0 $ is nonempty since the finite intersection under the closure sign is nonempty due to the Markov property. For increasing $n$ these closed intersections form a decreasing sequence of non-empty sets; and therefore by compactness $\bigcap_{ n = 0}^\infty \overline{\bigcap_{k=-n}^{n} \phi^{-k} R_{s_k}} \allowmathbreak \ne \emptyset .$ On the other hand, if $\bigcap_{ n = 0}^\infty \overline{\bigcap_{k=-n}^{n} \phi^{-k} R_{s_k}} \allowmathbreak \ne \emptyset,$ then each finite intersection under the closure sign is non-empty which in turn implies that each pair of intersections $R_{s_k} \cap \phi^{-1} R_{s_k} \ne \emptyset,$ for arbitrary $k \in {\Bbb Z}.$ \subsubhead Main Theorem \endsubsubhead \proclaim{Theorem 6.5} Suppose the dynamical system $(X , \phi)$ is expansive and has a Markov generator ${\Cal R} = \{ R_0 , \dots , R_{N-1} \}$. Then the map $\pi$, as defined by (5.11), is an essentially one-to-one finite factor map of the shift of finite type $\Sigma_G$, as defined by (6.1), onto $X$. Furthermore, If $(X,\phi )$ is irreducible, then so is $(\Sigma_G, \sigma).$ \endproclaim \demo{Proof}We must establish (i) - (v) in Definition 4.6. That $\pi$ is a factor map--namely, it satisfies items (i), (ii), and (iii)--is the content of theorem 5.12. In order to establish {\it (iv)}--namely, a bound on the number of pre-images under $\pi$--we introduce the following concept. \definition{Definition 6.6} A map $\pi$ from $\Sigma_G$ to $X$ said to have a {\it diamond} if there are two sequences $s , t \in \Sigma_G$ for which $\pi(s) = \pi(t)$ and for which there exist indices $k 0 ,$ the family of sets $$\{ \overline {\phi^n R_{s_{-n}} \cap \dots \cap R_{s_0} \cap \dots \phi^{-n} R_{s_n}} : s \in \Sigma_G \quad \text{where}\quad s_0 = a \}$$ covers $\overline{R_a} ;$ and the family $$\{ \overline {\phi^n R_{t_{-n}} \cap \dots \cap R_{t_0} \cap \dots \phi^{-n} R_{t_n}} : t \in \Sigma_G \quad \text{where}\quad t_0 = b \}$$ covers $\overline{R_b} .$ Thus, by compactness, there exists $s , t \in \Sigma_G$ with $s_0 = a , t_0 = b $ such that $$\p \in \bigcap_{n = 0}^\infty \overline{\bigcap_{-n}^{n} \phi^{-k} R_{s_k}} $$ and $$\p \in \bigcap_{n = 0}^\infty \overline{\bigcap_{-n}^{n} \phi^{-k} R_{t_k}} $$ Since $\p$ is bilaterally transitive and $R_0$ is open, $\phi^n \p \in R_0$ for some positive $n$ and $\phi^m \p \in R_0 $ for some negative $m.$ Thus by the remark following (5.8), $s_m = t_m = 0 , s_0 = a \ne b = t_0 , s_n = t_n = 0 , $ which is a diamond for $\pi.$ \qed \enddemo \proclaim{Lemma 6.9} If $d ({\Cal R}) < c/2 ,$ then $\pi$ has no diamonds. \endproclaim \demo{proof} Since $\pi \sigma = \phi \pi ,$ we can asume without loss of generality that $k=1$ in the definition of diamond. Assume that $ \p = \pi(s) =\pi(t)$ where $$ s= ( \dots , s_{-2} , a , b_0 , b_1 , \dots , b_{m-1} , d , s_{m+1} , \dots ) ,$$ $$ t= ( \dots , t_{-2} , a , c_0 , c_1 , \dots , c_{m-1} , d , t_{m+1} , \dots ) .$$ We must show that $b_l=c_l$ for $0 \le l \le m-1.$ Because $[ a , b_0 , b_1 ,\dots , b_{m-1} , d ]$ is an allowable block in $\Sigma_G$, $$\phi R_a \cap R_{b_0} \cap \phi^{-1} R_{b_1} \cap \dots \cap \phi^{-m+1} R_{m-1} \cap \phi^{-m} R_d \ne \emptyset .$$ Choose a point $\q$ in this open set. Because $\pi$ is onto, there is a sequence $$u = ( \dots , u_{-2} , a , b_0 , b_1 , \dots , b_{m-1} , d , u_{m+1} , \dots ) \in \Sigma_G $$ such that $\pi ( u ) = \q .$ Also since $[ a , c_0 , c_1 ,\dots , c_{m-1} , d ]$ is an allowable block and $\Sigma_G$ is a shift of finite type, there is a sequence $v \in \Sigma_G$ such that $$v = ( \dots , u_{-2} , a , c_0 , c_1 , \dots , c_{m-1} , d , u_{m+1} , \dots ).$$ Thus $$ \r \equiv \pi ( v ) \in \overline{\phi R_a \cap R_{c_0} \cap \phi^{-1} R_{c_1} \cap \dots \cap \phi^{-m+1} R_{m-1} \cap \phi^{-m} R_d} .$$ From $d ( R_i) < c/2$ and $\phi^l (x) \in \overline{R_{b_l}} \cap \overline{R_{c_l}}$ for $0 \le l \le m-1 ,$ we conclude by the triangle inequality that $d ( \phi^l \q , \phi^l \r) < c.$ Furthermore, $d ( \phi^n \q , \phi^n \r ) < c/2 $ for $ n < 0$ and $ n > m-1 .$ The expansive property then implies that $ \q = \r .$ Thus $R_{b_l} \cap \overline{R_{c_l}} \ne \emptyset $ which implies that $R_{b_l} \cap R_{c_l} \ne \emptyset .$ However, elements of ${\Cal R}$ are pairwise disjoint: so $b_l =c_l$. \qed \enddemo {\it (iv) There is a bound on the number of pre-images of $\pi$.} {\it (v) A BLT point has a unique pre-image.} Because ${\Cal R}$ is a generator, $n$ can be chosen so that $ d \left( \bigvee_{-n}^{n} \phi^k {\Cal R} \right) < c/2 .$ By Proposition 6.2, $\bigvee_{-n}^{n} \phi^k {\Cal R}$ is again a topological Markov partition. For this partition the associated shift of finite type of (6.4) is given by the higher edge graph $G^{(2n+1)}$. Let $\pi^{(2n+1)}$ be the map of $\Sigma_{G^{(2n+1)}}$ onto $X$ according to (5.11). It has no diamonds: so by Lemma 6.7 a point has at most $N^{2(2n+1)}$ pre-images, and by Lemma 6.8 a BLT point has only one. The original $\pi$ satisfies $\pi = \pi^{(2n+1)} \psi \sigma^n $ where $\psi$ a conjugacy of $\Sigma_G$ onto $\Sigma_{G^{(2n+1)}} .$ Thus we have that under $\pi$ a point has at most $N^{2(2n+1)}$ pre-images, and a BLT point has a unique pre-image. We defer the proof of irreducibility to Exercise 6.2 \qed \enddemo \subsubhead Converse to the Main Theorem \endsubsubhead \newline Recall that we introduced in 3.1 the partition ${\Cal C} = \{ C_i: i = 0 , \dots , N-1 \}$ consisting of the elementary cylinder sets $C_i = \{ s \in \Sigma_G : s_0 = i \}$ for a dynamical system $( \Sigma_G , \sigma)$ where $\Sigma_G$ is a shift of finite type base on an alphabet $A = \{0 , 1 , \dots , N-1 \} .$ This partition is a topological Markov generator. \proclaim{Theorem 6.10}Let $(X , \phi)$ be a dynamical system, $(\Sigma_G ,\sigma)$ an irreducible shift of finite type based on $N$ symbols; and suppose there exists an essentially one-to-one factor map $\pi$ from $\Sigma_G$ to $X$. Then the partition ${\Cal R}$ defined by ${\Cal R} = \{ R_i = \pi ( C_i)^o : i = 0 , \dots , N-1 \} $ is a topological Markov generator. \endproclaim \remark{Remark} Note we assume $\pi$ is a factor map which has a unique inverse for each bilaterally transitive point, but no bound is assumed on the number of pre-images of arbitrary points: {\it i.e.}, $\pi$ satisfies (i),(ii),(iii), and (v) of Definition 4.6 but not (iv). However, in Corollary 6.12 we shall show that (iv) follows from the others under the hypothesis of expansivity. However, as Exercise 6.3 shows property (v) is essential: we cannot obtain it from expansivity and (i) through (iv). \endremark \demo{Proof} We must prove the following items \roster \item Elements of ${\Cal R}$ are disjoint: \item The closure of elements of ${\Cal R}$ cover $X.$ \item ${\Cal R}$ is a generator. \item ${\Cal R}$ satisfies the Markov property. \endroster {\it (1) Elements of ${\Cal R}$ are disjoint: i.e., $R_i \cap R_j = \emptyset, i \ne j .$} The idea of the proof is to use bilaterally transitive points to overcome a difficulty: namely, maps in general do not enjoy the property that the image of an intersection is equal to the intersection of images, but one-to-one maps do. Suppose $R_i \cap R_j \ne \emptyset$ for $i \ne j.$ Then, by Proposition 4.7 $BLT(R_i \cap R_j) \ne \emptyset.$ By Propositions 4.8 and 4.9, $\pi^{-1}$ maps $ BLT(R_i)$ and $BLT(R_j)$ homeomorphically onto $ BLT(C_i)$ and $ BLT(C_j)$ respectively. Therefore $\pi^{-1}$ maps $BLT(R_i \cap R_j) = BLT(R_i) \cap BLT(R_j)$ homeomorphically onto $ BLT(C_i \cap C_j) = BLT(C_i) \cap BLT(C_j),$ which implies that $\emptyset \ne BLT(C_i \cap C_j) \subset C_i \cap C_j,$ a contradiction. {\it (2) $X = \cup_{i = 0}^{N-1} \overline{R_i} .$} $X= \pi(\Sigma_G) = \pi \cup_{i = 0}^{N-1} C_i= \cup_{i = 0}^{N-1} \pi(C_i)= \cup_{i = 0}^{N-1} \overline {R_i},$ the last inequality following from Proposition 4.9. For the next two items we need a lemma. \proclaim{Lemma 6.11} Under the hypothesis of 6.10, $ \pi ( \bigcap_{m}^{n} \sigma^{-k} C_{s_k}) = \overline{\bigcap_{m}^{n} \phi^{-k} R_{s_k}} $ for $ m < n .$ \endproclaim \demo{Proof} Once again we use the bilaterally transitive points to deal with images of intersections. We have the following string of equalities. $$\align \pi( \bigcap_{m}^n \sigma^{-k} C_{s_k} ) &= \pi \left( \overline{BLT(\bigcap_{m}^n \sigma^{-k} C_{s_k})}\right) = \overline{\pi(\bigcap_{m}^n BLT(\sigma^{-k} C_{s_k}))} \\ \intertext{which by injectivity of $\pi$ and shift-invariance of bilateral transitive points} &= \overline{\bigcap_{m}^{n} \pi(BLT( \sigma^{-k}C_{s_k}))} = \overline{\bigcap_{m}^{n} \pi \sigma^{-k}BLT((C_{s_k}))}\\ \intertext{which by commutativity of $\pi$ and Proposition4.8} &= \overline{\bigcap_{m}^{n} \phi^{-k}\pi(BLT (C_{s_k}))} = \overline{\bigcap_{m}^{n} \phi^{-k}(BLT \pi(C_{s_k}))}\\ \intertext{which by Proposition 4.9} &= \overline{\bigcap_{m}^{n} \phi^{-k}(BLT(R_{s_k}))} = \overline{BLT(\bigcap_{m}^{n} \phi^{-k}(R_{s_k}))}\\ &= \overline{\bigcap_{m}^{n} \phi^{-k}(R_{s_k})} . \endalign$$ Q.E.D. \enddemo {\it (3) ${\Cal R}$ is a generator.} Because $\Cal C$ is a generator, $ d \left( \bigcap_{-n}^{n} \sigma^{-k} C_{s_k} \right) \rightarrow 0 .$ By Lemma 6.11 , $ \allowmathbreak \pi ( \bigcap_{-n}^{n} \sigma^{-k} C_{s_k}) = \overline{\bigcap_{-n}^{n} \phi^{-k} R_{s_k}} .$ So, by continuity of $\pi ,$ we get $$ d \left( \overline{\bigcap_{-n}^{n} \phi^{-k} R_{s_k}} \right) = d \left( \bigcap_{-n}^{n} \phi^{-k} R_{s_k} \right) \rightarrow 0.$$ {\it (4) ${\Cal R}$ satisfies the Markov property.} Suppose $R_{s_i} \cap \phi^{-1} R_{s_{i+1}} \ne \emptyset , 1 \le k \le n-1 .$ By Lemma 6.11 we have $\pi \lbrack C_{s_i} \cap \sigma^{-1} C_{s_{i+1}} \rbrack = \overline{R_{s_i} \cap \phi^{-1} R_{s_{i+1}}} \ne \emptyset , 1 \le k \le n-1 .$ Thus $C_{s_i} \cap \sigma^{-1} C_{s_{i+1}} \ne \emptyset , 1 \le k \le n-1 .$ Since ${\Cal C}$ satisfies the Markov property, $\bigcap_{k=1}^{n} \phi^{-k} C_{s_k} \ne \emptyset $ for all $n > 1 .$ So $\pi(\bigcap_{k=1}^{n} \phi^{-k} C_{s_k})$ $ = \overline{\bigcap_{k=1}^{n} \phi^{-k} R_{s_k}} \ne \emptyset $ for all $n > 1 .$ Therefore, $ \bigcap_{k=1}^{n} \phi^{-k} R_{s_k} \ne \emptyset $ for all $n > 1 .$ \qed \enddemo \proclaim{Corollary 6.12} If in addition to the hypotheses of Theorem 4.18 the dynamical system $(X ,\phi)$ is expansive, then $\pi$ is finite. \endproclaim \demo{Proof} We derive 4.6(iv) from from the assumption that the domain of $\pi$ is irreducible, $\pi$ satisfies 4.6(i), (ii), (iii), and (v), and $\phi$ is expansive. This is an immediate consequence of Theorems 6.10 and 6.5. \qed \enddemo \subhead Exercises \endsubhead \roster \item"{6.1}" A topological partition ${\Cal R}$ for a dynamical system $(X , \phi)$ is Markov if and only if $$\bigcap_{k=0}^{n} \phi^{-k} R_{s_k} \ne \emptyset, \bigcap_{k=-n}^{0} \phi^{-k} R_{s_k} \ne \emptyset \Rightarrow \bigcap_{k=-n}^{n} \phi^{-k} R_{s_k} \ne \emptyset, $$ for $n \ge 0. $ \item"{6.2}" Under the hypothesis of Theorem 6.5 show that if $(X,\phi )$ is irreducible, then so is $(\Sigma_G, \sigma).$ \item"{6.3}" Show that in Theorem 6.10, condition (v) cannot be replaced by condition (iv). Hint consider the following example. Let $$\A = \left( \matrix 1 & 1 & 0\\ 1 & 0 & 1\\ 1 & 1 & 0 \endmatrix \right) , $$ and $\pi : X_\A \rightarrow X_2$ be defined by $$\pi [1 ,1]= \pi [2 , 3] = \pi [3 , 2] = 1$$ $$\pi [1 ,2]= \pi [2 , 1] = \pi [3 , 1] = 0 .$$ \midinsert \centerline{ \epsfbox{fig6ii.eps}} \botcaption{Figure 6.II} $\pi$ indicated by edge-labels \endcaption \endinsert Show disjointness is violated in the image partition of the elementary cylinder sets. \item"{6.3}" Let $\pi$ be a factor map from a topological Markov shift $(\Sigma_\A , \sigma)$ to an expansive dynamical system $( X , \phi)$ with expansive constant $c$ and let the partition ${\Cal R}$ defined by ${\Cal R} = \{ R_i = \pi ( C_i)^o : i = 0 , \dots , N-1 \} $ satisfy $d ({\Cal R}) < c/2$. Show if $\pi$ has a diamond, then there exists a point $\p \in X$ with a continuum of pre-images. \endroster \newline\newline\newline \subhead 7. Product Structure\endsubhead \newline \newline The Markov property for a topological partition is an infinite set of conditions. It is the crucial one for obtaining a topological Markov shift representation of a dynamical system, but it could be difficult to verify. However there is another more useful criterion for getting it to which we now now turn our attention. It involves exchanging one set infinite set of conditions for another of a different sort which are more readily checkable. Once more we looked to our concrete systems as as guide. The sets of the partitions in examples 3.1 and 3.3 have a product structure whose behavior with respect to action of a mapping is intimately tied up with the Markov property. A general notion of partition without regard to any other consideration is the following. \definition{Definition 7.1} A {\it partition} of a set $R$ is defined to be a family ${\Cal H} = \{ h(\p) : \p \in R \} $ of subsets of $R$ such that for $\p,\q \in R$ \roster \item $\p \in h(\p) $ \item $h(\p) \cap h(\q) \ne \emptyset \Rightarrow h(\p) = h(\q).$ \endroster \enddefinition \definition{Definition 7.2} We call two partitions $${\Cal H} = \{ h(\p) : \p \in R\},$$ $${\Cal V} = \{ v(\p) : \p \in R\}$$ of $R$ {\it transverse} if, $h(\p) \cap v(\q) \ne \emptyset $ for every $\p , \q \in R.$ \enddefinition A set $R$ with two transverse partitions ${\Cal H},$ ${\Cal V},$ can be viewed as having a product structure something like that of a rectangle which suggests the following graphic terminology: we shall refer to the elements ${\Cal H}$ as {\it horizontals} and those of ${\Cal V}$ as {\it verticals}. When we are dealing with elements $R_i$ of a topological partition ${\Cal R} = \{ R_i: i= 1, \dots, N \}$, each of having a pair of transverse partitions ${\Cal H}_i,{\Cal V}_i,$ we refer to $h_i(\p),$ as the {\it horizontal through $\p$ in $R_i$ \/} and to $v_i(\p)$ as the {\it vertical\/}. Next we introduce notions concerned with the behavior of horizontals and verticals under the map associated with a dynamical system. We shall stick to the convention that under the action of a map verticals seem to contract and horizontals seem to expand. While we don't insist that the diameters of the images of these sets actually increase or decrease, this will generally be the case. In the literature one encounters the term {\it stable} set for what we call a vertical and {\it unstable} set for a horizontal. \definition{Definition 7.3}Suppose a dynamical system $(X, \phi)$ has a topological partition ${\Cal R}$ = $ \{ R_i \}, $ each member of which has a pair of transverse partitions. We say {\it alignment} of verticals and horizontals are respectively {\it maintained by } by $\phi$ and $\phi^{-1}$ if for all $i, j$ \roster \item $\p \in R_i \cap \phi^{-1} R_j \Rightarrow R_j \cap \phi v_i(\p) \subset v_j(\phi \p ) ;$ \item $\p \in R_i \cap \phi R_j \Rightarrow R_j \cap \phi^{-1} h_i(\p) \subset h_j(\phi^{-1} \p) .$ \endroster \enddefinition We actually require something stronger. \definition{Definition 7.4}In a dynamical system $(X, \phi)$ we say a topological partition ${\Cal R}$ = $ \{ R_i \} $ has {\it property M} if each set $R_i$ has a pair of transverse partitions such that alignments of horizontals and verticals are maintained by $\phi$ and its inverse respectively in such a manner that the image of any vertical and the pre-image of any horizontal is contained in a unique element of ${\Cal R}.$ In other words 7.3 (1) and (2) are replaced by: \roster \item $\p \in R_i \cap \phi^{-1} R_j \Rightarrow \phi v_i(\p) \subset v_j(\phi \p ) , $ \item $\p \in R_i \cap \phi R_j \Rightarrow \phi^{-1} h_i(\p) \subset h_j(\phi^{-1} \p) .$ \endroster \enddefinition We remark that with respect to horizontals 7.6(2) can be expressed alternatively as follows: $$ \p \in R_i \cap \phi^{-1} R_j \Rightarrow \phi h_i(\p) \supset h_j(\phi \p) . $$ \midinsert \centerline{\epsfbox{fig7i.eps}} \botcaption{Figure 7.I} Property M \endcaption \endinsert \midinsert \centerline{\epsfbox{fig7ii.eps}} \botcaption{Figure 7.II} Violations \endcaption \endinsert \proclaim{Proposition 7.5} If ${\Cal R}$ has property M, then so does ${\Cal R}^{(2)}. $ \endproclaim \midinsert \centerline{\epsfbox{fig7iii.eps}} \botcaption{Figure 7.III} Property M on ${\Cal R}^{(2)} $ \endcaption \endinsert \demo{Proof} Let $R_i \cap \phi^{-1} R_j \ne \emptyset $ be a member of ${\Cal R^{(2)}}.$ Since a partition of a set induces one on a subset, the horizontals and verticals of $R_i$ induce corresponding partitions of $R_i \cap \phi^{-1} R_j :$ namely, \roster \item ${\Cal H} (R_i \cap \phi^{-1} R_j ) = \{ h_{ij}(\p) = h_i(\p) \cap \phi^{-1}R_j : \p \in R_i \cap \phi^{-1} R_j \} ,$ \item ${\Cal V} (R_i \cap \phi^{-1} R_j ) = \{ v_{ij}(\p) = v_i(\p): \p \in R_i \cap \phi^{-1} R_j \} .$ \endroster First to verify that this pair of partitions is transverse, we observe that if $\p,\q \in R_i \cap \phi^{-1}R_j $ then by 7.4(1) $$ v_i(\q) \subset \phi^{-1}v_j( \phi \q) \subset \phi^{-1}R_j .$$ From definition (1) we have $$h_{ij}(\p) \cap v_{ij}(\q) = h_i(\p) \cap \phi^{-1}R_j \cap v_i(\q) =h_i(\p)\cap v_i(\q) \ne \emptyset .$$ Second, we show that $\phi$ and its inverse map verticals and horizontals so as to satisfy property M. Let $\p \in R_i \cap \phi^{-1} R_j \cap \phi^{-1}(R_j \cap \phi^{-1}R_k) .$ On one hand, it is immediate from definition that $$\phi v_{ij}(\p) = \phi v_i(\p) \subset v_j(\phi\p) = v_{ij}(\phi\p).$$ On the other, $$\phi h_{ij}(\q) = \phi (h_i(\q) \cap \phi^{-1} R_j ) \supset h_j(\phi \q) \supset h_j(\phi \q) \cap \phi^{-1} R_k = h_{jk}(\phi \q).$$ \qed \enddemo \proclaim{Corollary 7.6} If ${\Cal R}$ has property M then so does ${\Cal R}^{(n)} $ for $ n = 1 , 2, \dots .$ \endproclaim \demo{Proof} Repeated use Proposition 7.5 using the identity $({\Cal R}^{(n)})^{(2)} = {\Cal R}^{(n+1)} .$ \qed \enddemo \proclaim{Proposition 7.7}For a dynamical system $(X , \phi)$ if a topological partition ${\Cal R}$ has property M, then ${\Cal R}$ satisfies the 3-fold intersection property. \endproclaim \midinsert \centerline{\epsfbox{fig7iv.eps}} \botcaption{Figure 7.IV} 3-fold Intersection Property \endcaption \endinsert \demo{Proof} Let $\p \in \phi R_i \cap R_j \ne \emptyset$ and $\q \in R_j \cap \phi^{-1} R_k \ne \emptyset .$ Then by transversality $v_j(\q) \cap h_j(\p) \ne \emptyset.$ Futhermore, $v_j(\q) \cap h_j(\p) \subset R_j $ and $v_j(\q) \cap h_j(\p) \subset \phi^{-1} v_k(\phi \q) \cap \phi h_i(\phi^{-1} \p) \subset \phi^{-1} R_k \cap \phi R_i:$ So $\phi R_i \cap R_j \cap \phi^{-1} R_k \ne \emptyset.$ Thus we have $$ R_i \cap \phi^{-1} R_j \ne \emptyset , R_j \cap \phi^{-1} R_k \ne \emptyset \Rightarrow R_i \cap \phi^{-1} R_j \cap \phi^{-2} R_k .$$ \qed \enddemo \proclaim{Corollary 7.8} Given a dynamical system $(X, \phi),$ if a topological partition ${\Cal R}$ has property M, then ${\Cal R}^{(n)}$ is satisfies the 3-fold intersection property for $ n = 1 , 2, \dots .$ \endproclaim \demo{Proof}Follows from Corollary 7.6 and Proposition 7.7. \qed \enddemo \proclaim{Theorem 7.9} Given a dynamical system $(X , \phi),$ if a topological partition ${\Cal R}$ has property M, then ${\Cal R}$ is Markov. \endproclaim \demo{Proof}Follows from Corollaries 7.6, 7.8, and the Bootstrap Lemma 6.3. For instance, ${\Cal R}^{(n-1)}$ and ${\Cal R}^{(n)}$ satisfies the 3-fold intersection property. so ${\Cal R}^{(n-1)}$ satisfies the 4-fold one. Working our way back, we get ${\Cal R}^{(n-2)}$ satisfies the 5-fold one, etc. Finally, we get that ${\Cal R}$ satisfies the $(n+2)-$fold intersection property; but this is true for any $n$. \qed \enddemo We conclude this section with a theorem which is useful in applications to dynamical systems having smooth manifolds as phase spaces. For that theorem boundaries of partition members will play a role. In addition we shall need more topological structure than that provided by mere existence of a pair of transverse partitions. First we turn our attention to boundaries. In certain problems the burden of establishing the Markov property for a partition via property M can be eased by merely verifying a similar property for boundaries. The reader will get a good illustration of this when we discuss in detail Markov partitions for automorphisms of the two torus. Employing the usual notation, we have that the boundary of an element $R_i$ in a topological partition ${\Cal R}$ is given by $\partial R_i \equiv \overline{R_i}-R_i .$ We denote the union of all boundaries of elements of ${\Cal R}$ by $\partial{\Cal R} \equiv \bigcup_i \partial R_i .$ Suppose the boundary $\partial R_i$ of each element of ${\Cal R}$ is the union of two subsets: one, $\partial_V R_i$ which we shall call the {\it vertical boundary} of $R_i$, the other, $\partial_H R_i,$ the {\it horizontal boundary} of $R_i.$ We denote the union of all vertical boundaries of elements of ${\Cal R}$ by $\partial_V {\Cal R} \equiv \bigcup_i \partial_V R_i, $ and the union of all horizontal ones by $\partial_H {\Cal R} \equiv \bigcup_i \partial_H R_i. $ \definition{Definition 7.10} We say that a topological partition ${\Cal R}$ has {\it boundaries satisfying property M} if the following hold for each $i:$ \roster \item $\partial R_i = \partial_V R_i \cup \partial_H R_i ,$ \item $\overline{v_i(\p)}\cap \partial R_i \subset \partial_H R_i ,$ \item $\overline{h_i(\p)}\cap \partial R_i \subset \partial_V R_i ,$ \item $\phi \partial_V {\Cal R} \subset \partial {\Cal R} ,$ \item $\phi^{-1} \partial_H {\Cal R} \subset \partial {\Cal R} . $ \endroster \enddefinition We introduce the additional topological structure needed for the next theorem. \definition{Definiton 7.11} We call a metric space $R$ an {\it abstract rectangle} if it is homeomorphic to the Cartesian product two metric spaces-- {\it i.e.} there exist two metric spaces $H ,V$ and a homeomorphism $\Phi$ of the Cartesian product $H \times V $ onto $R.$ \enddefinition \midinsert \centerline{ \epsfbox{fig7v.eps}} \botcaption{Figure 7.V} Abstract rectangle \endcaption \endinsert Sets with a pair of transverse partitions usually arise in this way. Let $ \Phi (\p^1 , \p^2 ) = \p ,$ where $ \p \in R$ and $ (\p^1 , \p^2 ) \in H \times V .$ Define the following horizontal and vertical sets of $R:$ $$h(\p) \equiv \Phi \{ (x , p^2 ) : x \in H \}, $$ $$v(\p) \equiv \Phi \{ (p^1 , y) : y \in V \} . $$ Naturally the two partitions $${\Cal H} = \{ h(\p) : \p \in R\},$$ $${\Cal V} = \{ v(\p) : \p \in R\}$$ of $R$ are transverse since $$v(\p) \cap h(\q) = \{ \Phi (\p^1,\q^2) \} \ne \emptyset.$$ In addition, for each pair of points $ \p , \q \in R$ the map $(\p,\q) \mapsto v(\p) \cap h(\q)$ is continuous, onto, and maps $h(\p) \times v(\q)$ homeomorphically onto $R_i.$ Thus we could have assumed that $H, V$ were subsets of $R$ in the first place. We use the letters we do to designate these subsets in order to suggest horizontal and vertical lines. \proclaim{Theorem 7.12} In a dynamical system $ (X , \phi)$, if each element of a topological partition ${\Cal R}$ is a connected abstract rectangle, the alignments of which are maintained by $\phi$ and its inverse respectively, and if ${\Cal R}$ has boundaries with property M, then ${\Cal R}$ itself has property M-- {\it i.e.} ${\Cal R}$ is a Markov partition. \endproclaim \demo{Proof} \midinsert %\vspace{1.5in} \centerline{\epsfbox{fig7vi.eps}} \botcaption{Figure 7.VI} Impossible boundary picture \endcaption \endinsert We give the proof only for verticals which consists in proving $$p \in R_i \cap \phi^{-1} R_j \Rightarrow \phi v_i(p)\subset R_j.$$ Our proof involves one proof by contradiction established by means of a second. The main one is a contradiction to the assumption that $\phi v_i(p) \nsubseteq R_j.$ The other one contradicts the connectivity of $\phi v_i(p),$ which is a consequence of the the following. Since $R_i$ homeomorphic to $h_i(p) \times v_i(p),$ the vertical $v_i(p)$ is connected: for otherwise $R_i$ would not be. Therefore, the homeomorphic image $\phi v_i(p)$ is connected as well. Thus, if $\phi v_i(p) \nsubseteq R_j,$ then we would have that $\phi v_i(p) \cap \partial R_j \ne \emptyset.$ Hence there would exist a point $q \in \phi v_i(p) \cap \partial R_j $ which is also in $\overline{\phi v_i(p) \cap R_j}:$ for if not, then there would be an open set $U \supset \phi v_i(p) \cap \partial R_j $ such that $U \cap \phi v_i(p) \cap R_j = \emptyset ,$ and the open sets $R_j$ and $U \cup (X-\overline{R_j}) $ would disconnect $\phi v_i(p).$ By preservation of alignments, we have $\phi v_i(p) \cap R_j \subset v_j(\phi p)$ so that $q \in \overline{v_j(\phi p)}.$ Thus $q \in \partial_H {\Cal R}$ from which follows by property M for boundaries that $\phi^{-1}(q) \in \partial {\Cal R}.$ However, $ \phi^{-1}(q) \in v_i(p)\subset R_i ,$ which contradicts $R_i \cap \partial R_i = \emptyset.$ \qed \enddemo We now turn our attention to 2-dimensional toral automorphisms in generality. While there exists non-measurable automorphisms, for us toral automorphisms will mean continuous ones. \subhead 8. Markov Partitions for Automorphisms of the 2-torus \endsubhead \newline\newline Let $X = {\Bbb R}^n / {\Bbb Z}^n $ be the n-dimensional torus and $\A$ a $n \times n$ matrix with integer entries and determinant $\pm 1.$ Such a matrix defines an automorphism of the n-torus in the manner described in Section 2.3. The set of such matrices forms a group called the {\it general linear group} $GL(n,{\Bbb Z}).$ Both a matrix $\A$ and the automorphism $\phi$ it defines are called {\it hyperbolic}, if $A$ has no eigenvalue of modulus one. We shall devote the rest of this section to the two dimensional case; {\it i.e.} $n=2.$ Let $$\A = \left( \matrix a & b\\ c & d \endmatrix \right) \in GL(2,{\Bbb Z}).$$ Eigenvalues of $A$ are are the solutions of the quadratic equation $$ x^2 - (\text{trace} \A) x+ \text{det} \A= 0.$$ Here hyperbolicity means that $A$ has two distinct eigenvalues, say $\lambda $ and $\mu$ which are irrational numbers. Since $\lambda \mu = \text{det} A = \pm 1,$ we can assume that $|\lambda | > 1$ and $|\mu| < 1 .$ An easy calculation shows that the row vectors $$\align {\v}_\lambda &= (c,\lambda - a)\\ {\v}_\mu &= (c,\mu - a) \endalign$$ are eigenvectors associated with $\lambda$ and with $\mu$ respectively. The action of $\A$ on a vector $\v$ is to contract its ${\v}_\mu$-component by $\mu$ and expand its ${\v}_\lambda$-component by $\lambda.$ Directions may or not be reversed depending on the signs of the eigenvalues. We refer to the direction of ${\v}_\lambda$ as the {\it expanding} direction and that of ${\v}_\mu$ as the {\it contracting} one. Finally let $\ell_\lambda$ be a line through the origin in the expanding direction and $\ell_\mu$ the one in the contracting direction. We call these lines, which are invariant under the action of $\A$ on the plane, the {\it expanding } and {\it contracting eigen-line} respectively. The slopes of these lines are $m_\lambda = (\lambda - a)/c$ and $m_\mu = (\mu - a)/c.$ From these formulae one sees that these lines pass through no lattice points other than the origin: for if they did then the slopes $m_\lambda$ and $m_\mu$ would be rational numbers and so would $\lambda$ and $\mu.$ \proclaim{Theorem 8.1} A hyperbolic toral automorphism is expansive. \endproclaim \demo{Proof} Let $\phi$ be an automorphism and $\p, \q \in X $ be any two different points of the two dimensional torus. Let $ c = |\mu| /8.$ We shall show that there exists $n \in {\Bbb Z}$ such that $d( \phi^n \p , \phi^n \q ) > c .$ By translation invariance of the metric we have $d(\p,\q) = d(\{ 0 \}, \p-\q):$ so it suffices to show that $d( \{ 0 \} , \phi^n \r ) > c ,$ for any $\r \ne \{ 0 \}$ in $X .$ \midinsert %\vspace{1.5in} \centerline{\epsfbox{fig8i.eps}} \botcaption{Figure 8.I} A fundamental region and eigen-directions of $A$ \endcaption \endinsert \vskip.2truein We take the torus to be given by the fundamental region $$X = \{ (x,y) :|x| \le 1/2 , \ |y| \le 1/2 \} $$ with the appropriate boundary identifications. In this region the metric on the torus coincides with the Euclidean one: namely, $ d(\p,\q) = ||\p-\q||$ where $||(x,y)|| = \sqrt{x^2 + y^2}.$ Let $\r=\p-\q \ne (0,0).$ Let $\r_\lambda$ and $\r_\mu$ be the $\v_\lambda-$component and the $\v_\mu-$component of $\r$ respectively. Then from the triangle inequality $$|\lambda^n \r_\lambda| - |\mu^n \r_\mu| \le ||\phi^n \r || \le |\lambda^n \r_\lambda| + |\mu^n \r_\mu|.$$ One of the components $\r_\lambda ,\r_\mu$ is not zero. We can assume that $\r_\lambda \ne 0:$ otherwise replace $\phi$ by $\phi^{-1}$ in the argument. We can also assume that $|\mu| < \frac12 :$ for, if not, replace $\phi$ by $\phi^k$ for large enough $k.$ If $||\r|| > \frac{|\mu|}4 ,$ then $||\phi^n \r||> c$ for $n=0.$ If $||\r|| \le \frac{|\mu|}4,$ choose $n \ge 1$ such that $$ \frac{|\mu|^{n+1}}4 \le |r_\lambda|\le \frac{|\mu|^{n}}4.$$ Then the following inequalities inequality show that $\phi^n \r$ is in the fundamental region and that $||\phi^n \r|| > c.$ $$ |\lambda^n \r_\lambda| + |\mu^n \r_\mu| \le \frac14 + \frac{|\mu|^{n+1}}4 < \frac12 ,$$ $$\frac{|\mu|}8 \le \frac{|\mu|}4-\frac{|\mu|^{n+1}}4 \le |\lambda^n \r_\lambda| - |\mu^n \r_\mu| .$$ \qed \enddemo \remark{Remark}We now have all the ingredients for a formal proof that the toral automorphism of example 3.3 enjoys the conclusions of theorem 6.5 about representing dynamical systems by topological Markov shifts. In this case the automorphisms $\phi$ be given by the matrix $$\A = \left( \matrix 1 & 1\\ 1 & 0 \endmatrix \right) $$ and the topological Markov shift $(\Sigma_G, \sigma)$ by the edge-graph $G$ of figure 3.VIII. Theorem 8.1 shows that $\phi$ is expansive, a necessary item in the hypothesis of the main theorem, Theorem 6.5. Theorem 7.13 can be applied to show that the partition in example 3.3 is Markov, another necessary item. Finally in 3.3 we have already shown that the partition in question is a generator, the remaining requirement of the main theorem. \endremark Returning our attentions to the general case, we shall exploit one of the properties of a hyperbolic automorphisms: namely, a matrix in the group $GL(2,{\Bbb Z})$ specifying a hyperbolic automorphism is conjugate to another one all of whose entries bear the same sign. More specifically we have the following theorem of Williams \cite{W} proved by entirely elementary methods of plane geometry. \proclaim{Theorem 8.2} Let $\A \in GL(2,{\Bbb Z})$ be hyperbolic. Then there exists $\C ,\P \in GL(2,{\Bbb Z})$ such that $\C\A\C^{-1} = \epsilon \P $ where $\epsilon = \pm 1,$ the choice of sign being the same as that of $\lambda,$ and the entries of the matrix $$\P = \left( \matrix p & q\\ r & s \endmatrix \right)$$ are non-negative. \endproclaim \demo{Proof} Choose a pair of lattice points $(\alpha , \beta)$ , $(\gamma , \delta) $ such that \roster \item"{(i)}" The angle $(\alpha , \beta) (0,0) (\gamma , \delta) $ is acute and $\ell_\lambda$ lies in it but $\ell_\mu$ does not. \item"{(ii)}" The closed parallelogram with vertices the origin, the two lattice points, and the lattice point $(\alpha + \gamma, \beta + \delta)$ contains no other lattice point. \endroster This can always be done. One way is to use continued fractions to approximate slopes of lines, a discussion of which shall be deferred to a remark. An even more elementary way is the following. First, chose initial lattice points $(\alpha ,\beta)$ and $(\gamma , \delta)$ so close to $\ell_\lambda$ that (i) is satisfied and no other lattice points lie between them and the origin on a direct line. Then if the parallelogram in (ii) contains another lattice point in its interior, connect it to the origin with a line segment. Form a new pair of lattice points by taking the closest lattice point to the origin on this segment and selecting the one from the previous pair for which (i) holds. Continue this process until condition (ii) is satisfied. Condition (ii) is equivalent to the area of the parallelogram equalling 1. Consider the linear map given by the matrix $$ \C= \left( \matrix \gamma & \delta\\ \alpha & \beta \endmatrix \right). $$ Since $$(0,1)\C = (\alpha, \beta)$$ $$(1,0)\C = (\gamma, \delta),$$ $\C$ maps the principal fundamental region--namely, the closed unit square--onto the parallelogram. We shall show that $\C$ provides the sought after conjugating transformation. \midinsert %\vspace{2.0in} \centerline{\epsfbox{fig8ii.eps}} \botcaption{Figure 8.II} Parallelogram and expanding direction \endcaption \endinsert \vskip.2truein The two lines $\overline{\ell}_\lambda , \overline{\ell}_\mu $ that are the images under $C^{-1}$ of $\ell_\lambda ,\ell_\mu $ are the expanding and contracting eigen-lines for each of the transformations $ \pm \C\A\C^{-1}. $ Choose $P$ to be the one that preserves the orientation of $ \overline{\ell}_\lambda,$ the choice of sign being that of $\lambda .$ This means that the matrix $\P$ has $|\lambda|$ as the expanding eigenvalue and either $\pm \mu $ as the contracting. Furthermore, because $\C^{-1}$ maps the parallelogram onto the unit square and $\ell_\lambda $ passes through the parallelogram while $\ell_\mu$ does not, the line $\overline{\ell}_\lambda$ passes through the first quadrant and the line $\overline{\ell}_\mu$ the second. To prove that $\P$ is non-negative, or equivalently, that $\P$ maps the first quadrant into itself, we must just show $(0,1)\P$ and $(1,0)\P $ lie in the first quadrant. We shall give the proof only for $(0,1)\P:$ the arguments which follow work equally well for the other lattice point $ (1,0)\P.$ There are two cases depending whether the contracting eigenvalue $\mu$ of $\P$ is positive or negative. In the second case ($\mu < 0$), the linear map $\P$ reflects the first quadrant about the eigen-line $\overline{\ell}_\lambda$, while in the first case ($\mu > 0$) no reflection takes place. Let $\c$ denote the origin, $\a$ the lattice point $(0,1) $, and $\a^\prime$ its image under $P.$ Let $\b$ be the projection of $\a$ on the line $\overline{\ell}_\lambda$ in the direction parallel to $\overline{\ell}_\mu$ and $\b^\prime$ its image under $\P.$ The point $\b^\prime$ is also the projection of $\a^\prime$ on the line $\overline{\ell}_\lambda.$ \midinsert %\vspace{2.0in} \centerline{\epsfbox{fig8iii.eps}} \botcaption{Figure 8.III} Geometrical figure for proof without reflection \endcaption \endinsert \vskip.2truein We deal first with the case without reflection. Let $\overline{\ell}_\lambda^\prime ,\overline{\ell}_\mu^\prime $ be the lines through $a$ parallel to $\overline{\ell}_\lambda , \overline{\ell}_\mu$ respectively. The notation $|\p\q|$ stands for the length of the line segment with end-points $ \p , \q .$ On one hand, since $ |a^\prime b^\prime| =|\mu|^{-1}\centerdot |\a\b| < |\a\b| ,$ the point $\a^\prime$ lies between the lines $\overline{\ell}_\lambda^\prime , \overline{\ell}_\lambda .$ On the other, since $|\c\b^\prime| = |\lambda| \centerdot |\c\b| > |\c\b| ,$ the point $a^\prime$ lies to the left of $\overline{\ell}_\mu^\prime .$ The region bounded by these three lines, in which $a^\prime$ thus lies, is contained in the first quadrant. \midinsert %\vspace{2.0in} \centerline{\epsfbox{fig8iv.eps}} \botcaption{Figure 8.IV} Geometrical figure for proof with reflection \endcaption \endinsert \vskip.2truein For the case with reflection, let $c^\prime$ be the intersection of the line $\overline{\ell}_\lambda$ and the vertical through $\a^\prime .$ Suppose that $\a^\prime$ belongs to the fourth quadrant but not the first. The point $a^\prime$ being a lattice point implies that $|\a^\prime \c^\prime| > 1 .$ However, because triangle $\c^\prime \a^\prime \b^\prime$ is similar to $\c\a\b$, $|\a^\prime \c^\prime| = |\mu| \centerdot |\a\c| < |\a\c| < 1 ,$ a contradiction. \qed \enddemo \remark{Remark} By means of continued fractions we can somewhat augment the conclusion of Theorem 8.2: namely, {\it we can conjugate so that the following two conditions to hold simultaneously. \roster \item $\overline{m}_\mu < -1,$ \item $0<\overline{m}_\lambda < 1,$ \endroster where $\overline{m}_\mu $ is the slope of the contracting eigenline $\overline{\ell}_\mu$ and $\overline{m}_\lambda$ is the slope of the expanding one $\overline{\ell}_\lambda$ for $\P.$} \endremark The first inequality indicates that the contracting eigen-line for $\P$ passes through the second quadrant between the lattice points $(0,1)$ and $(-1,1);$ and the second that the expanding one passes through the first quadrant under the lattice point $(1,1).$ For Theorem 8.4, the main one of this section, one does not need more than what is provided by Theorem 8.2. These extra properties make life a little less difficult. The first one makes Figure 8.VI easier to draw. The second one obviates repeating proofs covering slightly different geometrical figures. Not taking advantage of it multiplies the number of cases in the proof, and we shall have enough of them as it is. Since we shall not be using the full strength of this remark one can skip the remainder of it and proceed to directly Theorem 8.4. We shall be using the second property which is very easy to achieve by itself. From the theory of continued fractions, we know that every irrational number can be written uniquely as an infinite continued fraction $\lbrack a_0, a_1, \dots \rbrack = a_0 + 1/(a_1 + 1/ \dots)$ where $a_n \in {\Bbb Z}$ for all $n$ and $a_n > 0$ for $n > 0.$ In addition, the continued fraction of a quadratic surd has a periodic tail: namely the tail can be written as $\lbrack \overline{b_1, \dots, b_m} \rbrack > 1,$ where the overbar means infinite repetition of $b_1$ through $b_m.$ In \cite{ATW} the following was proved. \proclaim{Theorem 8.3} Let $\A \in GL(2,{\Bbb Z})$ be hyperbolic. The slope $m_\lambda,$ being a quadratic surd, can be written $m_\lambda = \lbrack a_0, a_1, \dots, a_n, \overline{b_1, \dots, b_m} \rbrack,$ where $m$ is as small as possible. If $$\C = \pmatrix 0 & 1\\ 1 & a_0 \endpmatrix \pmatrix 0 & 1\\ 1 & a_1 \endpmatrix \dots \pmatrix 0 & 1\\ 1 & a_n \endpmatrix, $$ then $\C\A\C^{-1} = \epsilon \P $ where $$\P = \left( \pmatrix 0 & 1\\ 1 & b_1 \endpmatrix \dots \pmatrix 0 & 1\\ 1 & b_m \endpmatrix \right)^N, $$ for some positive integer $N$ and $\epsilon$ is the same as in Theorem 8.2. Furthermore, the slopes the eigen-lines of $\P$ satisfy $\overline{m}_\lambda = \lbrack \overline{b_1, \dots, b_m} \rbrack > 1$ and $ -1/\overline{m}_\mu =\lbrack \overline{b_m, \dots, b_1}\rbrack >1.$ \endproclaim The matrix $$ \left( \matrix 0 & 1\\ 1 & 0 \endmatrix \right) \P \left( \matrix 0 & 1\\ 1 & 0 \endmatrix \right) $$ achieves the above two conditions in the remark. \proclaim{Theorem 8.4}Let $\phi$ be a toral automorphism whose defining matrix is either $\P$ or $-\P$ where $$\P = \left( \matrix p & q\\ r & s \endmatrix \right)$$ is a hyperbolic matrix in $GL(2,{\Bbb Z}),$ with non-negative entries. Then there exists a Markov generator ${\Cal R}^*$ for $\phi,$ the members of which are of parallelograms. The associated Markov shift is given by a directed graph also specified by $\P:$ {\it i.e.}, the edge graph with connections given by $\P$ consists of two vertices labelled I and II with $p$ directed edges from I to itself, $q$ from I to II, $r$ from II to I, and $s$ from II to itself. \endproclaim \midinsert %\vspace{2.0in} \centerline{\epsfbox{fig8v.eps}} \botcaption{Figure 8.V} Edge graph defined by $\P$ \endcaption \endinsert \demo{Proof} We shall assume that the expanding eigen-line of $\P$ as given by Theorem 8.2 passes under the point $(1,1);$ if not,conjugate $\P$ by the matrix $$ \E = \left( \matrix 0 & 1\\ 1 & 0 \endmatrix \right), $$ which reflects the first quadrant about the line $y=x.$ Before proceeding in earnest, we need some notation. Dropping the bars, we now let $\v_\lambda,$ $\v_\mu$ be the expanding and contracting eigen-vectors of $\P$ and $\ell_\lambda,$ $\ell_\mu$ the corresponding eigenlines through the origin. We denote lines parallel to these through a point $\p$ by assigning $\p$ as a superscript. For example, $\ell^{(0,1)}_\lambda$ denotes the line through $(0,1)$ parallel to $\ell_\lambda ,$ etc. We define the following points as depicted in Figure 8.VI: $$ \aligned \o &\equiv (0,0)\\ \o^\prime &\equiv (1,0)\\ \o^{\prime\prime} &\equiv (1,1)\\ \o^{\prime\prime\prime} &\equiv (0,1)\\ \a &\equiv \ell_\mu \cap \ell_\lambda\\ \a^\prime &\equiv \ell_\mu^{(1,0)} \cap \ell_\lambda^{(1,0)}\\ \a^{\prime\prime} &\equiv \ell_\mu^{(1,1)} \cap \ell_\lambda^{(1,1)}\\ \a^{\prime\prime\prime}&\equiv \ell_\mu^{(0,1)}\cap\ell_\lambda^{(0,1)}\\ \b &\equiv \ell_\mu \cap \ell_\lambda^{(-1,0)} \\ \b^\prime &\equiv \ell\mu^{(1,0)} \cap \ell_\lambda = b + (1,0)\\ \b^{\prime\prime} &\equiv \ell_\mu^{(1,1)} \cap \ell_\lambda^{(0,1)} = \b + (1,1) \endaligned \tag 8.5 $$ $$ \aligned \c &\equiv \ell_\mu \cap \ell_\lambda^{(0,1)}\\ \c^{\prime} &\equiv \ell_\mu^{(1,0)} \cap \ell_\lambda^{(1,1)}\\ \overline{\c} &\equiv \ell_\mu^{(0,-1)} \cap \ell_\lambda \\ \overline{\d} &\equiv \ell_\mu \cap \ell_\lambda^{(-1,1)}\\ \d^\prime &\equiv \ell_\mu^{(1,0)}\cap \ell_\lambda^{(0,1)} = \overline{\d} + (1,0)\\ \d^* &\equiv \d^\prime -(0,1). \endaligned $$ \midinsert %\vspace{2in} \centerline{\epsfbox{fig8vi.eps}} \botcaption{Figure 8.VI} A remarkable fundamental region \endcaption \endinsert We have drawn Figure 8.VI as if the first statement in the remark following Theorem 8.2 holds. This places the point $\c^\prime$ in the unit square. Since we are not using this condition, $\c^\prime$ could appear anywhere to the left of the line $x=1$ in the strip between the lines $y = 0$ and $ y=1.$ Let $R_I$ be the interior of parallelogram $\a \c \d^\prime \b^{\prime}$ and $R_{II}$ the interior of parallelogram $\c^{\prime} \d^\prime \b^{\prime\prime} \a^{\prime\prime}.$ The closed set $\overline{R_I}\cup \overline{R_{II}},$ as we shall show, is a fundamental region, which we shall call the {\it principal Markov } one. As drawn in Figure 8.VI, this set is equivalent modulo ${\Bbb Z^2}$ to the unit square by sliding $\bigtriangleup \a \a^{\prime\prime\prime} \c$ one unit to the right and $\bigtriangleup \d^\prime \b^{\prime\prime} \a^{\prime\prime}$ one unit down. But in general we need a slightly more elaborate proof. First, no two points in the interior of $\overline{R_I}\cup \overline{R_{II}}$ are equivalent because $R_I\cup R_{II}$ is disjoint from its four neighboring unit translates which totally bound it. Second, the set of all ${\Bbb Z}^2-$translates of $\overline{R_I}\cup \overline{R_{II}}$ covers the plane because all integral horizontal translates of the union of this set with its unit downward vertical translate covers the infinite strip between the lines $y=0$ and $y=1$ and all integral vertical translates of the strip covers the plane. Thus we can view the torus to be the set $X =\overline{R_I} \cup \overline{R_{II}}$ with points on the boundary identified by lattice translations. The proof of the theorem involves four cases: two subcases arise for each matrix $\pm \P$ depending whether $\mu$ is positive or negative. These amount to the four possible combinations, $$(\lambda, \mu) = (\pm |\lambda|, \pm |\mu|),$$ of signs for the eigenvalues of the matrix representing $\phi.$ The simplest case is when both $\lambda$ and $\mu$ are positive. Things are more difficult when either is negative, especially $\mu.$ So that the proof appears less tedious, we divide that for each case into five steps. \medpagebreak \underbar{Case I:} $ \lambda >0 , \mu > 0.$ \proclaim{Step 1}The family ${\Cal R} = \{ R_I , R_{II} \}$ is a Markov partition. \endproclaim Our aim is to show that ${\Cal R}$ satisfies the hypothesis of Theorem 7.12. By virtue of their construction as parallelograms the members $ R_I , R_{II} $ of ${\Cal R}$ are connected. These open parallelograms are obviously abstract rectangles, each being homeomorphic to the Cartesian product of two of open intervals. The two in question are a pair intersecting sides of a parallelogram minus endpoints. Horizontals and verticals of $R_i, i = I,II,$ are given by $$v_i(\p) \equiv \ell^\p_\mu \cap R_i,$$ $$h_i(\p) \equiv \ell^\p_\lambda \cap R_i.$$ Since $\P$ defines a linear transformation of the plane, the image of a line parallel to an eigen-line is another line parallel to the same eigen-line: so alignment of verticals and horizontals is maintained by $\phi$ and $\phi^{-1}:$ namely, $$\alignat 2 &\p \in R_i \cap \phi^{-1} R_j &&\Rightarrow R_j \cap \phi v_i(\p) \subset v_j(\phi p ) ; \tag 1\\ &\p \in R_i \cap \phi R_j &&\Rightarrow R_j \cap \phi^{-1} h_i(\p) \subset h_j(\phi^{-1} p) \tag 2 \endalignat$$ for $i, j= I, II. $ Next we verify that the boundaries of these of members satisfy property {\it M} of Definition 7.10 which entails five items. The first of these concerns dividing $\partial R_I$ and $\partial R_{II}$ into vertical and horizontal pieces. As shown in Figure 8.VI we have $$\partial R_I = \partial_V R_I \cup \partial_H R_I ,$$ $$\partial R_{II} = \partial_V R_{II} \cup \partial_H R_{II} ,$$ where $$\align \partial_V R_I &\equiv \a\c \cup \b^{\prime}\d^\prime,\\ \partial_H R_I &\equiv \a\b^{\prime} \cup \c\d^\prime,\\ \partial_V R_{II} &\equiv \c^{\prime} \d^\prime \cup \a^{\prime\prime}\b^{\prime\prime},\\ \partial_H R_{II} &\equiv \c^{\prime}\a^{\prime\prime} \cup \d^\prime\b^{\prime\prime}, \endalign $$ each being the union of two line segments. Utilizing the boundary identifications, we have that $\partial {\Cal R}$ consists of two transverse line segments intersecting at the origin: namely, $$\aligned \partial_H{\Cal R} &= \overline{\c}\b^{\prime}\subset \ell^a_\lambda = \ell_\lambda,\\ \partial_V{\Cal R} &= \a\overline{\d} \subset \ell_\mu . \endaligned \tag 8.6 $$ It is clear from Figure 8.VI that (2) and (3) of 7.10 are satisfied: namely, $$\overline{v_i(\p)} \cap \partial R_i \subset \partial_H R_i,$$ $$\overline{h_i(\p)} \cap \partial R_i \subset \partial_V R_i,$$ From (8.6) and the property that the restrictions of $\P$ and $\P^{-1}$ respectively to the lines $\ell_\lambda$ and $\ell_\mu$ are contractions we get $$\aligned \overline{\c}\b^\prime&\subset (\overline{\c}\b^\prime)P\\ (\a\overline{\d})P &\subset \a\overline{\d} . \endaligned \tag 8.7 $$ We can restate (8.7) as items (4) and (5) of 7.10: namely, $$\align \phi \partial_V{\Cal R} &\subset \partial {\Cal R}_V \subset \partial{\Cal R},\\ \phi^{-1} \partial_H {\Cal R} &\subset \partial_H {\Cal R} \subset \partial {\Cal R}. \endalign$$ Thus we have established that ${\Cal R}$ satisfies the hypothesis of theorem 7.12: so it is Markov partition. \remark{Remark}At this point it may be instructive to remark on our definition of topological partition. This example illustrates the advantage of using open sets over their closures as members of such a partition. For one thing, $R_I \ne \overline{R_I}^o$ and $R_{II} \ne \overline{R_{II}}^o.$ For another, while $R_I$ and $R_{II}$ are abstract rectangles, their closures are not. For instance, $R_I$ is homeomorphic to a Cartesian product: namely, the product of the line segment $\a\b^{\prime}$ minus the end-points with the segment $ac$ minus the end-points. However, $\overline{R_I}$ is not homeomorphic to the Cartesian product of $\a\b^{\prime}$ with $\a\c,$ since part of the segment $\a\b^{\prime}$ is in the boundary and part isn't. Furthermore, $\partial_V {\Cal R}$ and $\partial_H {\Cal R}$ are connected line segments which get mapped into themselves under $\phi$ and $\phi^{-1}$ respectively. This would not be the case if ${\Cal R} = \{ \overline{R_I} , \overline{R_{II}} \}.$ If one's definition of topological partition involves closures of open sets as members rather than open sets, then one is forced into somewhat greater contortions in order to achieve the same results. \endremark The Markov partition ${\Cal R}$ is not necessarily a generator. The trouble is that, while the members of ${\Cal R}$ are connected, those of $ {\Cal R}^{(2)} = {\Cal R} \vee \phi^{-1} {\Cal R}$ may not be in which case nonempty sets of the form $\bigcap_{n = 0}^\infty \overline{\bigcap_{-n}^{n} \phi^{-k} R_{s_k}}$ may consist of more than one point. To overcome this let us examine the sets $ R_i \cap \phi^{-1} R_j \in {\Cal R} \vee \phi^{-1} {\Cal R}.$ As we shall see each consists of a union of disjoint open parallelograms, the number of which is given by the matrix $P.$ A remedy is immediately suggested. \proclaim{Step 2}The family ${\Cal R}^* = \{ R^*_k : 1 \le k \le N^* \} $ consisting of all connected components of the sets $ R_i \cap \phi^{-1} R_j \in {\Cal R} \vee \phi^{-1} {\Cal R}$ is Markov partition. \endproclaim Once again we must show that the members of ${\Cal R}^*$ satisfy the five items of Definition 7.10. In the universal cover the image $(R_i)\P$ is an open parallelogram that has been stretched by a factor of $\lambda$ in the $v_\lambda$-direction and shrunk by a factor $\mu$ in the $v_\mu$-direction. This parallelogram passes through various Markov fundamental regions; and in each one it when it intersects a parallelogram equivalent to $R_j,$ the intersection is a parallelogram. No two of these intersections share an equivalent point: for otherwise a violation of (2.1.1(3)) with respect to the fundamental region $ (\overline{R_I} \cup \overline{R_{II}})\P$ would be committed. While the set $\phi h_i(\p) \cap R_j$ may consist of several horizontals, the set $\phi h_i(\p) \cap R^*_k$ is either empty or a single one. Furthermore, if $\phi h_i(\p) \cap R^*_k \ne \emptyset$ for one horizontal $h_i(\p)$ of $R_i,$ then $\phi h_i(\p^\prime) \cap R^*_k \ne \emptyset$ for any other horizontal $ h_i(\p^\prime)$ in $R_i.$ Back on the torus the various non-equivalent parallelograms represent disjoint connected sets which we have labelled $R^*_k , 1 \le k \le N^*.$ Being parallelograms, these sets are abstract rectangles. Alignment of verticals and horizontals for these members of ${\Cal R}^*$ is maintained by $\phi$ and $\phi^{-1}$ for the same reason it is for members of ${\Cal R}.$ Regarding boundaries we have that $$\aligned &\partial_H {\Cal R}^{(2)} = \partial_H{\Cal R}^* = (\c^{\prime\prime}\b^{\prime})\P, \\ &\partial_V {\Cal R}^{(2)} = \partial_V{\Cal R}^* = \a\d . \endaligned \tag 8.8 $$ Thus, just as for ${\Cal R}$, we have $$\align \phi \partial_V{\Cal R}^* &= (\a\d)P \subset ad = \partial {\Cal R}^*_V \subset \partial{\Cal R}^*,\\ \phi^{-1}\partial_H {\Cal R}^* &= \c^{\prime\prime}\b^{\prime} \subset (\c^{\prime\prime}\b^{\prime})\P = \partial_H {\Cal R}^* \subset \partial {\Cal R}^*. \endalign$$ The partition ${\Cal R}^*$ satisfies the hypothesis of Theorem 7.12: so it is Markov. By reasoning as before, a parallelogram of the form $(R^*_k)\P$ passes through various fundamental regions; and in each one it when it intersects a parallelogram equivalent to $R^*_l,$ the intersection is a parallelogram, no two of which intersections share an equivalent point. Hence, a nonempty set of the form $\phi R^*_i \cap R^*_j$ is a single connected parallelogram. If $R^*_k$ is one of the parallelograms in $\phi R_i \cap R_j,$ then the length of its $v_\lambda$-dimension is the same as that of $R_j$ while the length of its $\v_\mu$-dimemsion is $|\mu|$ times that of $R_i.$ Similarly, a non-empty set of the form $\phi R^*_i \cap R^*_j$ is a single connected open parallelogram, the length of its $\v_\lambda$-dimension being the same as that of $R^*_j$ and the length of its $\v_\mu$-dimension $\mu$ times that of $R^*_i.$ \midinsert %\vspace{2in} \centerline{\epsfbox{fig8vii.eps}} \botcaption{Figure 8.VII} A nonempty parallelogram of the form $\bigcap_{-n}^{n} \phi^{-k} R^*_{s_k}$ \endcaption \endinsert \vskip.2truein Likewise, a non-empty set of the form $\bigcap_{-n}^{n} \phi^{-k} R^*_{s_k}$ is a single connected open parallelogram, the length of its $\v_\lambda$-dimension is $|\mu|^n$ times as that of $R^*_{s_{-n}}$ and the length of its $\v_\mu$-dimension $|\mu|^n$ times that of $R^*_{s_n}.$ From this we have $$ d \left( \bigvee_{-n}^{n} \phi^k {\Cal R}^* \right) = d ({\Cal R})/|\mu|^{n+1} \rightarrow 0 , \text{as } n \rightarrow \infty.$$ In other words, ${\Cal R}^*$ is a generator. \proclaim{Step 4}Let $\# (\phi R_i \cap R_j)$ denote the number of disjoint parallelograms in the intersection $\phi R_i \cap R_j.$ $$\aligned \#(\phi R_i\cap R_I) &\equiv \text{ number of lines } x = 0, x= 1,\dots, \text{ traversed by }(R_i)P;\\ \#(\phi R_i\cap R_{II}) &\equiv \text{ number of lines } y = 1, y = 2,\dots, \text{ traversed by }(R_i)P,\endaligned \tag 8.9 $$ which leads to $$ \alignedat 2 \#(\phi R_I \cap R_I) &= \text{$x$-coordinate of } (0,1)\P &&= p;\\ \# (\phi R_{II} \cap R_I) &= \text{$x$-coordinate of }(1,1)\P - (1,0)\P &&= q;\\ \#(\phi R_I \cap R_{II}) &= \text{$y$-coordinate of } (0,1)\P &&= r ;\\ \# (\phi R_{II} \cap R_{II}) &=\text{$y$-coordinate of } (1,1)\P - (1,0)\P &&= s. \endalignedat \tag 8.10$$ \endproclaim \midinsert %\vspace{2in} \centerline{\epsfbox{fig8viii.eps}} \botcaption{Figure 8.VIII} How $(R_I)\P$ and $(R_{II})\P$ intersect various fundamental regions \endcaption \endinsert \vskip.2truein To establish Step 4 it is important to understand how $(R_I)P$ and $(R_{II}P$ intersect various Markov fundamental regions particularly how they begin and end. We must show that Figure 8.VIII truly represents the situation: namely the segment $(b^\prime d^\prime)\P $ lies within the segment $\tilde a \tilde b.$ First, if a parallelogram $(R_i)\P$ intersects a lattice translate of $R_j$ then it stripes all the way across. As it does do, it passes strictly through the lattice translate without ever straddling any part of a horizontal boundary: for otherwise there would be a violation of the property that $(\overline{R_I} \cup \overline{R_{II}})\P$ is a fundamental region because $\partial_H({\Cal R}\P) \supset \partial_H {\Cal R}.$ Since $\P$ is a contraction on the line $\ell_\mu,$ we have $|(\a\b)\P| < |\a\b|;$ and since the point $\a = (0,0)$ is fixed, the point $(\b)\P$ lies inside the segment $\a\b.$ It then follows that the point $(\b^\prime)\P = (\b)\P+(p,q)$ lies inside a lattice translate of $\a\b$--that is, it lies on the line $\ell^{(p,q)}_\mu$ strictly between $\tilde{\a} \equiv (p,q)= (\a^\prime)\P$ and $\tilde{\b} \equiv (p,q)+\b.$ The same is true for $(\d^\prime)\P:$ for otherwise $(R_I)\P$ would straddle part of its own boundary on the line $\ell^{(p-1,q)}.$ Thus $$ (\a\c)\P \subset (\a\d)\P \subset \a\b .$$ and $$ (\b^\prime\d^\prime)\P \subset \tilde{\a} \tilde{\b} .$$ So the parallelogram $(R_I)\P$ begins (as shown in the leftmost figure of Figure 8.VIII) with its left vertical boundary contained in the segment $\a\b$ on the line $\ell_\mu$ and ends (as shown in the middle figure of Figure 8.VIII) with its right vertical boundary contained in the segment $\tilde{\a}\tilde{\b}$ on the line $\ell_\mu^{(p,q)}.$ We see that the $(R_I)\P$ begins by striping across $R_I.$ Its lower horizontal boundary lies on the line $\ell_\lambda$ and covers the lower horizontal boundary of $R_I.$ Not shown in the figure is manner by which $(R_I)\P$ stripes across the top of fundamental region consisting of $R_I+(r,s-1)$ and $R_{II}+(r,s-1)$ with its upper horizontal boundary contained in the line $\ell^{(\a^{\prime\prime\prime})\P}_\lambda = \ell^{(r,s)}_\lambda.$ The parallelogram $(R_I)\P$ ends by striping through $R_{II}+(p-1,q-1).$ The other parallelogram $(R_{II})\P$ begins where $(R_I)\P$ leaves off. Its left vertical boundary is contained in $\tilde{\a}\tilde{\b},$ and its right one in $\tilde{\tilde{\a}}\tilde{\tilde{\b}}$ where $\tilde{\tilde{\a}} \equiv (p+r,q+s) $ and $\tilde{\tilde{\b}} \equiv \b + (p,q)$ as shown in the middle figure of Figure 8.VIII. The first set that $(R_{II})\P$ stripes through is $R_I+(p,q)$ and the last $R_{II}+(p+r-1,q+s-1).$ It stripes through $R_I+(p,q)$ on top of $R_I \cap (R_I)\P + (p,q)$ and ends at the bottom of a $R_{II}+(p+r-1,q+s-1)$ as shown in Figure 8.VIII. As drawn in Figure 8.VI, the line segment $\a\a^{\prime\prime\prime}$ lies totally in $\overline{R_I}$ connecting its bottom horizontal boundary with its top: so $(R_i)\P$ has the property that it stripes across $R_I+(m,n)$ if and only if it passes through the interior of the line segment $\a \a^{\prime\prime\prime} + (m,n).$ But one must bear in mind that the picture does not represent all cases as $\c^\prime$ may not be located in the principal unit square so that the line segment $\a\a^{\prime\prime\prime}$ may not lie totally in $\overline{R_I}.$ Nevertheless, because of the way $(R_I)\P$ begins and ends it obeys this property when $(m,n) = (0,0)$ and $(m,n) = (p-1,q).$ Consequently, it also obeys this property for at all intermediary lattice points. By {\it intermediary } we mean at $(m,n)$ where $0 \le m \le p-1 $ and $0 \le n \le q.$ Similarly for $(R_{II})\P$ it satisfies the property for $(m,n) = (p,q),$ $(m,n) = (p+r-1,q+s-1),$ and thus for all intermediary $(m,n).$ The number of times $(R_i)P$ passes through a lattice translate $\a \a^{\prime\prime\prime}$ equals the number different lines $x = \text{integer}$ crossed by $(R_i)P,$ which equals $p$ for $(R_I)\P$ and $r$ for $(R_{II})\P.$ Similarly, a parallelogram $(R_i)\P$ intersects a lattice translate of $R_{II}$ if and only if $(R_i)\P$ crosses the same a lattice translate of $\a^{\prime\prime\prime} \a^{\prime\prime};$ and the number of times this happens equals the number lines $y = \text{integer}$ crossed by $(R_i)\P,$ which equals $q$ for $(R_I)\P$ and $s$ for $(R_{II})\P.$ \remark{Remark} A consequence of the fact that right contracting boundary of $(R_I)\P$ is contained in a lattice translate of $\a\b$ is that $\phi R_I \cap R_{II} \ne \emptyset$ which means $q>0.$ But this we aready know from the property that $P$ is hyperbolic. Similarly, $r>0.$ However, either $p$ or $s$ could be 0, but not both. \endremark \proclaim{Step 5}The transition matrix associated with mapping of the Markov generator ${\Cal R}^*$ by $\phi$ coincides with matrix which specifies the automorphism--namely, $\P$-- the edge graph of which is illustrated in Figure 8.V. \endproclaim From what we have established there are $N^* = p+q+r+s$ parallelograms $R^*_i$ in ${\Cal R}^*.$ We separate the subscripts into four sets: $$ \align \{ 1, &\dots, p \} \tag 1\\ \{p+1, &\dots, p+q \} \tag 2\\ \{p+q+1, &\dots, p+q+r \} \tag 3\\ \{p+q+r+1, &\dots, p+q+r+s\}.\tag 4 \endalign $$ We label the members of ${\Cal R}^*$ accordingly: $$ \align R^*_1 \cup \dots \cup R^*_p &= R_I \cap \phi R_I, \\ R^*_{p+1} \cup \dots \cup R^*_{p+q} &= R_{II} \cap \phi R_I,\\ R^*_{p+q+1} \cup \dots \cup R^*_{p+q+r} &= R_I \cap \phi R_{II},\\ R^*_{p+q+r+1} \cup \dots \cup R^*_{p+q+r+s} &= R_{II} \cap \phi R_{II}. \endalign $$ As we have said before: if $\phi h_i(\p) \cap R^*_k \ne \emptyset$ for one horizontal $h_i(\p)$ of $R_i,$ then $\phi h_i(\q) \cap R^*_k \ne \emptyset$ for any other horizontal $h_i(\q)$ of $R_i.$ Therefore, the image of each parallelogram $R^*_k$ contained in an $R_i$ intersects the same elements of ${\Cal R}^*.$ From this we get that $\phi R^*_k \cap R^*_l \ne \emptyset$, equivalently $ R^*_k \cap \phi^{-1}R^*_l \ne \emptyset,$ whenever either $$k \in (1)\cup (3) \text{ and } l \in (1)\cup (2),$$ or $$k \in (2)\cup (4) \text{ and } l \in (3)\cup (4).$$ \medpagebreak \underbar{Case II:} $ \lambda >0 , \mu < 0.$ Except for the lattice points of the unit square labelled by $\o$'s we redefine the other ones in Figure VI by translating them by $\rho \v_\mu$ with $\rho,$ chosen so that $$({\bar \d })\P= \a.$$ For example, $\a_{\text{new}} = \a_{\text{old}} + \rho \v_\mu.$ Whereas before the point $\a$ was the fixed point $\o$, now it isn't. Figures 8.IX(A) and 8.IX(B) depict new principal Markov fundamental regions in which the old one of Figure VI has been translated by $\rho \v_\mu.$ The difference in the two figures is the location of $\o$ with respect to $\b.$ In a moment we shall argue that Figure 8.IX(B) cannot occur. \midinsert %\vspace{2in} \centerline{\epsfbox{fig8ixa.eps}} \botcaption{Figure 8.IX(a)} New principal Markov fundamental region, a translation of the previous with $\o$ between $\a$ and $\b.$ \endcaption \endinsert \vskip.2truein \midinsert %\vspace{2in} \centerline{\epsfbox{fig8ixb.eps}} \botcaption{Figure 8.IX(b)} New principal Markov fundamental region, a translation of the previous with $\o$ above $\b.$ \endcaption \endinsert \vskip.2truein \proclaim{Step 1}The new partition $\R = \{ R_I , R_{II} \}$ is Markov. \endproclaim The proof of this is the same as in Step 1 of Case I except the verification of $$\align \phi \partial_V{\Cal R} &\subset \partial {\Cal R}_V \subset \partial{\Cal R},\\ \phi^{-1} \partial_H {\Cal R} &\subset \partial_H {\Cal R} \subset \partial {\Cal R} \endalign$$ is more involved and is as follows. For this new partition, (8.6) remains valid: namely, $$\partial_H{\Cal R} = \overline{\c}\b^\prime \subset \ell^a_\lambda,$$ $$ \partial_V{\Cal R} = \a\overline{\d} \subset \ell_\mu .$$ Before there was a common fixed point on $\partial_H {\Cal R}$ and $\partial_V {\Cal R}: $ namely, $\text{origin} = \partial_H {\Cal R} \cap \partial_V {\Cal R}, $ but now the intersection $\partial_H {\Cal R} \cap \partial_V {\Cal R} $ is no longer a fixed point. The line segment $\a\overline{\d}$ still contains the origin as a fixed point. The line segment $\overline{\c}\b$ also contains a fixed point, but this is not so obvious. This will be a consequence of the following version of (8.7): $$\aligned (\overline{\c}\b^\prime)\P &\supset \text{lattice translate of } \overline{\c}\b^\prime\\ (\a\overline{\d})\P &\subset \a\overline{\d} ; \endaligned \tag 8.11 $$ Verification of the first relation is more difficult than before. That the second relation holds is immediate because the translation was chosen to make it so. The first relation rests on the property of the partition that $\a,\b,\c, \d$ are the only points on the contracting boundary which have equivalent ones on the expanding. There are no others! \midinsert %\vspace{2in} \centerline{\epsfbox{fig8x.eps}} \botcaption{Figure 8.X} Image of expanding boundary of new principal Markov fundamental region. \endcaption \endinsert \vskip.2truein Recall $\d^* = \d^\prime -(0,1).$ Now because $(\bar \d)\P = \a,$ the point $\hat{\a} \equiv (\d^*)\P$ is a lattice translate of $\a$ and the line $\ell^\a_\lambda$ is mapped to the line $\ell^{\hat{\a}}_\lambda$ by $\P.$ See Figure 8.X. Let $\hat{\c},$ $\hat{\b},$ and $\hat{\d}$ be the points on the line $\ell_\lambda^{\hat{\a}}$ that are lattice translates of the points $\bar{\c},$ $\b^\prime,$ and $\d^*.$ We must show that $(\bar{\c}\b^\prime)\P$ contains $\hat{\c} \hat{\b}.$ Because the point $(\d^*)\P$ lies on the line $\ell_\lambda ^{\hat{\a}},$ so do the points $(\bar{\c})\P$ and $(\b^\prime)\P.$ Since $(\b)\P$ and $(\c)\P$ are contained in the segment $\a\overline{\d}$ and the pair of points $(\b^\prime)\P$ and $(\overline{\c})\P$ are lattice translates of neither $\a,$ $\b,$ $\c,$ nor $\overline{d},$ this pair lies outside the segment $\hat{\b} \hat{\c}.$ Since $(\d^*)\P$ lies inside, the segment, $(\bar{\c}\b^\prime)\P$ overlaps $\hat{\c}\hat{\b}.$ Now we are are in a position to prove that Figure8.IX(B) cannot occur. Let ${\tilde \a}= (p,q)+ \rho \v_\mu.$ Since $({\bar \d })\P= \a,$ we have that ${\tilde \a}= \d^\prime \P.$ Let $\tilde \b$ be the point equivalent to $\b^\prime $ on the line $\ell_\mu^{(p,q)},$ upon which $\tilde \a$ lies; and let $\tilde \c$ be the lattice translate of $\bar c$ on the line $ \ell_\lambda ^{(p,q)+ \rho v_\mu}.$ The segment $\tilde \c \tilde \b$ is a lattice translate of the horizontal boundary of $\overline{R_I} \cup \overline{R_{II}}.$ If $\b$ were below $\o$ on the line $\ell_\mu^{(0.0)},$ then by virtue of the fact that $\mu$ is negative the point $\b^\prime \P$ would lie above $(p,q)$ on this line, and hence above $\tilde \b.$ Since $\d^\prime \P = {\tilde \a}$ lies below $\tilde \b,$ the parallelogram $R_I\P$ would straddle the part of its own horizontal boundary: namely the segment $\tilde \c \tilde \b.$ This would contradict the fact that $R_I\P$ is a subset of a fundamental region. \proclaim{Step 2}The family ${\Cal R}^* = \{ R^*_k : 1 \le k \le N^* \} $ consisting of all connected components of the sets $ R_i \cap \phi^{-1} R_j \in {\Cal R} \vee \phi^{-1} {\Cal R}$ is Markov partition. \endproclaim Proof is the same as Step 2 of Case I. \proclaim{Step 3}The Markov partition ${\Cal R}^* $ is a generator. \endproclaim Proof, same as Case I, Step 3. \proclaim{Step 4}Let $\# (\phi R_i \cap R_j)$ denote the number of disjoint parallelograms in the intersection $\phi R_i \cap R_j.$ $$\align \#(\phi R_i\cap R_I) &\equiv \text{ number of lines } x = 0, x= 1,\dots, \text{ traversed by }(R_i)P;\\ \#(\phi R_i\cap R_{II}) &\equiv \text{ number of lines } y = 1, y = 2,\dots, \text{ traversed by }(R_i)P,\endalign $$ which leads to $$ \alignat 2 \#(\phi R_I \cap R_I) &= \text{$x$-coordinate of } (0,1)\P &&= p;\\ \# (\phi R_{II} \cap R_I) &= \text{$x$-coordinate of }(1,1)\P - (1,0)\P &&= q;\\ \#(\phi R_I \cap R_{II}) &= \text{$y$-coordinate of } (0,1)\P &&= r ;\\ \# (\phi R_{II} \cap R_{II}) &=\text{$y$-coordinate of } (1,1)\P - (1,0)\P &&= s. \endalignat $$ \endproclaim \midinsert %vspace{2in} \centerline{\epsfbox{fig8xi.eps}} \botcaption{Figure 8.XI} How the new $(R_I)\P$ and $(R_{II})\P$ intersect various fundamental regions \endcaption \endinsert \vskip.2truein Argument similar to Case I, Step 4 but based on Figure 8.XI. There is a slight difference here. The vertical line segment $\a \a^{\prime\prime\prime}$ is offset from the line $x=0,$ and $\a^{\prime\prime\prime} \a^{\prime \prime}$ does not lie on $y=1.$ If $\rho v_\mu =(\xi ,\eta)$, then $$\align \#(\phi R_i\cap R_I) &\equiv \text{ number of lines } x-\xi= 0, x-\xi= 1,\dots, \text{ traversed by }(R_i)P;\\ \#(\phi R_i\cap R_{II}) &\equiv \text{ number of lines } y-\eta = 1, y-\eta= 2,\dots, \text{ traversed by }(R_i)P,\endalign $$ To get the desired result we observe that the parallelgram $(R_i)P$ traverses the line $x-\xi= m$ if and only if it traverses the line $x=m.$ Similarly the parallelogram traverses $y-\eta = m$ if and only if it traverses $y=m.$ \proclaim{Step 5}The transition matrix associated with mapping of the Markov generator ${\Cal R}^*$ by $\phi$ coincides with matrix which specifies the automorphism--namely, $\P$-- the edge graph of which is illustrated in Figure 8.V. \endproclaim Argument same as Case I Step 5. \medpagebreak \underbar{Case III:} $ \lambda < 0 , \mu > 0.$ The sets $R_i$ are the same as for Case I. \proclaim{Step 1}The new partition $\R = \{ R_I , R_{II} \}$ is Markov. \endproclaim This depends on establishing (8.6): namely $$\align \overline{\c}\b^\prime&\subset (\overline{\c}\b^\prime)P\\ (\a\overline{\d})P &\subset \a\overline{\d} . \endalign $$ The argument for the first relation is similar to that of Case II, Step 1. The argument for the second is the same as (8.7) of Case I. \proclaim{Step 2}The family ${\Cal R}^* = \{ R^*_k : 1 \le k \le N^* \} $ consisting of all connected components of the sets $ R_i \cap \phi^{-1} R_j \in {\Cal R} \vee \phi^{-1} {\Cal R}$ is Markov partition. \endproclaim Proof is the same as Step 2 of Case I. \proclaim{Step 3}The Markov partition ${\Cal R}^* $ is a generator. \endproclaim Proof, same as Case I, Step 3. \midinsert \vspace{2in} \centerline{\epsfbox{fig8xii.eps}} \botcaption{Figure 8.XII} How $(R_I)\P$ and $(R_{II})\P$ intersect various fundamental regions for Case III. \endcaption \endinsert \vskip.2truein \proclaim{Step 4}Let $\# (\phi R_i \cap R_j)$ denote the number of disjoint parallelograms in the intersection $\phi R_i \cap R_j.$ $$\align \#(\phi R_i\cap R_I) &\equiv \text{ number of lines } x = 0, x= -1,\dots, \text{ traversed by }(R_i)P;\\ \#(\phi R_i\cap R_{II}) &\equiv \text{ number of lines } y = -1, y = -2,\dots, \text{ traversed by }(R_i)P,\endalign $$ which leads to $$ \alignat 2 \#(\phi R_I \cap R_I) &= \text{$x$-coordinate of } (0,1)\P &&= -p;\\ \# (\phi R_{II} \cap R_I) &= \text{$x$-coordinate of }(1,1)\P - (1,0)\P &&= -q;\\ \#(\phi R_I \cap R_{II}) &= \text{$y$-coordinate of } (0,1)\P &&= -r ;\\ \# (\phi R_{II} \cap R_{II}) &=\text{$y$-coordinate of } (1,1)\P - (1,0)\P &&= -s. \endalignat $$ \endproclaim Argument the same as Case I, step 4 but based on Figure 8.XII. \proclaim{Step 5}The transition matrix associated with mapping of the Markov generator ${\Cal R}^*$ by $\phi$ coincides with matrix which specifies the automorphism--namely, $\P$-- the edge graph of which is illustrated in Figure 8.V. \endproclaim Argument same as Case I Step 5. \medpagebreak \underbar{Case IV:} $ \lambda < 0 , \mu < 0.$ The sets $R_i$ are the same as in Case II-- {\it i.e.}, translations of the ones of Case I. \proclaim{Step 1}The new partition $\R = \{ R_I , R_{II} \}$ is Markov. \endproclaim The argument is the same as in Case II, Step1 \proclaim{Step 2}The family ${\Cal R}^* = \{ R^*_k : 1 \le k \le N^* \} $ consisting of all connected components of the sets $ R_i \cap \phi^{-1} R_j \in {\Cal R} \vee \phi^{-1} {\Cal R}$ is Markov partition. \endproclaim Proof same as Case I, Step 2. \proclaim{Step 3}The Markov partition ${\Cal R}^* $ is a generator. \endproclaim Proof, same as Case I, Step 3. \midinsert \vspace{2in} \centerline{\epsfbox{fig8xiii.eps}} \botcaption{Figure 8.XIII} How $(R_I)\P$ and $(R_{II})\P$ intersect various fundamental regions Case IV \endcaption \endinsert \vskip.2truein \proclaim{Step 4}Let $\# (\phi R_i \cap R_j)$ denote the number of disjoint parallelograms in the intersection $\phi R_i \cap R_j.$ $$\align \#(\phi R_i\cap R_I) &\equiv \text{ number of lines } x = 0, x= -1,\dots, \text{ traversed by }(R_i)P;\\ \#(\phi R_i\cap R_{II}) &\equiv \text{ number of lines } y = -1, y =-2,\dots, \text{ traversed by }(R_i)P,\endalign $$ which leads to $$ \alignat 2 \#(\phi R_I \cap R_I) &= \text{$x$-coordinate of } (0,1)\P &&=-p;\\ \# (\phi R_{II} \cap R_I) &= \text{$x$-coordinate of }(1,1)\P - (1,0)\P &&= -q;\\ \#(\phi R_I \cap R_{II}) &= \text{$y$-coordinate of } (0,1)\P &&= -r ;\\ \# (\phi R_{II} \cap R_{II}) &=\text{$y$-coordinate of } (1,1)\P - (1,0)\P &&= -s. \endalignat $$ \endproclaim Argument the same as Case II, Step 4 but based on Figure 8.XIII. \proclaim{Step 5}The transition matrix associated with mapping of the Markov generator ${\Cal R}^*$ by $\phi$ coincides with matrix which specifies the automorphism--namely, $\P$-- the edge graph of which is illustrated in Figure 8.V. \endproclaim Argument same as Case I Step 5. \qed \enddemo \subhead Exercises \endsubhead \roster \item"{8.1}" Let $(X, \phi)$ be the dynamical system ${\Cal R} = \{ R_i \ : i = 1, 2, 3 \}$ the Markov partition of Example 3.3. Show the partition ${\Cal S} = \{ S_i \ : i = 0, 1 \}$, where $S_0 = R_1 \cup R_2$ and $S_1 = R_3,$ is Markov. Hint: ${\Cal S}^{(2)}= {\Cal R}.$ Observe that associated directed graph $G$ is vertex labelled graph of Figure 2.II. \item"{8.2}" What is the maximum number of pre-images of $\pi$ in the last example? In Theorem 8.4? \endroster \subhead 9. Epilogue \endsubhead The main theorem of Section 6 and its converse exhibit a duality between factor maps and Markov partitions. We are thus presented with a type of \lq\lq chicken verses egg" question: which are more fundamental for getting concrete symbolic representations for concrete dynamical systems, Markov partitions or factor maps? In Example 3.2, we have with equal ease defined a factor map arithmetically producing from it a Markov partition and constructed a Markov partition thereby obtaining a factor map. However,in Section 8, we only constructed a Markov partition for an arbitrary hyperbolic automorphism of the two-dimensional torus. In trying to repeat the success of dimension two by drawing Markov partitions for hyperbolic toral automorphisms in dimension three, one is doomed to failure as Bowen proves in \cite{Bo2}. He shows that no point on the contracting boundary of a member of a Markov partition can there exist a tangent plane. The boundary is a forced to be a fractal. Even if such a figure could be constructed, rendering is certainly difficult, let alone incorporating it in a tiling of three space in a manner suitable for viewing. And then what about four dimensions and higher?. Therefore, in any dimension other than two an arithmetic method seems the only hope. Kenyon, Vershik \cite{KV}, and Praggastis \cite{P} attack the problem in this manner and obtain factor maps arithmetically for hyperbolic toral automorphisms. Ultimately the answer to our chicken-egg question will probably turn out to be that neither takes precedence over the other. Bowen's proof of existence of Markov partitions and hence finite factor maps for general hyperbolic axiom A diffeomorphisms supports this point of view \cite{Bo1}. In this work Bowen uses an argument employing a combination of both methods. and bootstraps his way to the desired result. It starts with a cover whose members have small diameter with respect to the expansive constant. A topological Markov shift is constructed by using the labels of the members as symbols and defining transitions according to the rule that the $j$-th symbol follows the $i$-th if the image of the $i$-th member of the cover intersects the $j$-th. Using stable and unstable manifolds one is able to define a factor map from the symbolic shift to the phase space. This symbolic extension is much too big. The cardinality of a pre-images under this map can be non-denumerable. However, the images of cylinder sets form a second cover whose members are abstract rectangles obeying a Markovian property. This cover though may fail to form a topological partition for two reasons: some members may have no interior; and pairs of them may overlap in more than just boundary points. This cover is pared down by eliminating those sets with no interior. The overlap problem is solved by using some geometry of abstract rectangles: namely two abstract rectangles overlapping in an open set can be partitioned into nonoverlapping abstract rectangles. The last step in getting a topological partition is to partition the members of this last cover abstract rectangles, no pair of which overlaps in an open set. Through all of this Markov property is still maintained by the members of this final partition. That this is a generator is gotten by the same argument as our Propostion 5.8. Returning to the line of investigation of Kenyon, Vershik, and Praggastis, there remain things to be understood, such as the connectivity of cylinder set images under arithmetically defined factor maps. Furthermore, the general case of Markov partitions for hyperbolic automorphims of n-dimensional tori has not yet been treated. \refindentwd=1.2cm \Refs \comment \ref \key \by \pages \paper \yr1970 \vol \jour \endref \endcomment \ref \key ATW \by Roy Adler, Charles Tresser, Patrick A. Worfolk \pages \paper Topological conjugacy of linear endomorphisms of the 2-torus \yr (to appear) \vol \jour Trans. Amer. Math. Soc. \endref \ref \key AW \by Roy L. Adler and Benjamin Weiss \pages \paper Similarity of automorphisms of the torus \yr1970 \vol 98 \jour Memoirs American Math. Soc. \endref \ref \key Be \by K. Berg \paper On the conjugacy problem for K-systems \bookinfo Ph.D. Thesis \yr1967 \publ University of Minnesota \endref \ref \key Bo1 \by R. Bowen \book Equilibrium States and the Ergodic Theory of Anosov Diffeomorphisms, {\rm Lecture Notes in Mathematics, Vol. 470} \publ Springer-Verlag \publaddr Berlin, Heidelberg, New York \yr1975 \endref \ref \key Bo2 \by R. Bowen \paper Markov partitions are not smooth \pages 130-132 \yr1970 \vol 71 \jour Proc. Amer. Math. Soc. \endref \ref \key KV \by R. Kenyon and A. Vershik \paper Arithmetic construction of sofic partitions of hyperbolic toral automorphisms \bookinfo Prepublication ou Rapport de Recherce n.178 \year1995 \publ Ecole Normale Superieure de Lyon \endref \ref \key LM \by D. Lind and B Marcus \book An Introduction to Symbolic Dynamics and Coding \publ Cambridge University Press \publaddr Cambridge, New York, Melbourne \yr1995 \endref \ref \key P1 \by B Praggastis \paper Markov partitions for hyperbolic toral automorphisms \bookinfo Ph.D. Thesis \publ University of Washington \yr1992 \endref \comment \ref \key P2 \by B Praggastis \paper Numeration systems and Markov partitions from self-similar tilings \bookinfo Ph.D. preprint \endref \endcomment \ref \key W \by R. F. Williams \pages 329-334 \paper The "DA" maps of Smale and structural stability \vol 14 \yr1970 \jour Proc. Symp. in Pure Math. \publ AMS \endref \endRefs \enddocument