SYMBOLIC DYNAMICS AND MARKOV PARTITIONS

Roy L. Adler Mathematical Sciences Department IBM, Thomas J. Watson Research Center Yorktown Heights, NY 10598

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.

1. Introduction.

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 [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 [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:

(1) symbolic representations of dynamical systems by means of Markov partitions;

(2) coding between symbolic systems having equal entropy. 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.

Typeset by AMS-TEX

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.

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 “proper sets with disjoint interiors”, a 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.

2. Abstract and Concrete Dynamical Systems.

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 abstract dynamical system is a pair (X, ϕ) where X is a compact metric space with metric, say, d(· , ·) and ϕ is a continuous mapping of a X into itself. We shall refer to X as the phase space of the dynamical system. The orbit of a point p ∈ X is defined to be the sequence (ϕ^{n}p)_{n=0,1,2,...}. We shall consider systems where ϕ is onto. Also we shall be mainly, though not exclusively, interested in invertible maps– i.e. where ϕ is a homeomorphism–in which case the orbit of a point p ∈ X is defined to be the bilaterally infinite sequence (ϕ^{n}p)_{n∈ℤ}. 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 2.1. Two systems (X, ϕ), (Y, ψ) are said to be topologically conjugate, (X, ϕ) ≃ (Y, ψ), if there is a homeomorphism θ of X onto Y which commutes with ϕ and ψ: i.e., ϕθ = θψ.

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.

2.1 Multiplication maps. Let (X, f) be the system whose phase space is the complex numbers of modulus one– i.e. elements of the unit circle–acted upon by the mapping f : z → z^{n} for some integer n > 1.

For our purposes it is more convenient to consider a topologically and algebraically equivalent formulation. Let X = ℝ/ℤ where ℝ is the real line and ℤ the subgroup of integers. Recall that elements in X are cosets modulo ℤ. The coset of x ∈ ℝ modulo ℤ, which we denote by {x}, is the set {x + z|z ∈ ℤ} of lattice translates of x. Invoking some standard terminology, the real line ℝ can be referred to as the universal cover of the the circle X. In view of the fact that ℤ acts as a group of transformations on the universal cover ℝ, a coset is also called a ℤ−orbit. Two points x, x′ in the same coset or ℤ−orbit are said to be equivalent mod ℤ. The metric is given by defining the 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′ ∈ {x} and y′ ∈ {y}, then {x′ + y′} = {x + y}. Thus addition of cosets given by {x} + {y} ≡ {x + y} is well defined and so is the multiplication-by-n map f : {x} ↦ {x} + ⋯ + {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, …, n.

The closed unit interval [0, 1] is a set referred to as a fundamental region for the action of ℤ on ℝ.

Definition 2.1.1. A fundamental region is defined as a closed set such that

(1) it is the closure of its interior;

(2) 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 ℤ tile ℝ); (3) no point in the interior is in the same ℤ-orbit as another one in the closed

region (this restriction does not apply to two boundary points– e.g. the points 0 and 1 are in the same one).

Fundamental regions are not unique: for example, the interval [1, 2] is also a fundamental region for the action of ℤ on ℝ, 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) = 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.

2.3 Toral Automorphisms. Consider the two dimensional torus ℝ^{2}/ℤ^{2} and a continuous group automorphism ϕ. Here the universal cover of the 2-torus is ℝ^{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 ℤ^{2} of points with integer coordinates on the universal cover ℝ^{2}. The definitions of cosets, lattice translates, orbits, addition, and the metric are quite similar.

A continuous automorphism ϕ is specified by a a 2 × 2 matrix A : with integer entries and determinant ±1. Let

A = ( \begin{matrix}a & b \\ c & d \end{matrix} ) .

The matrix A determines an invertible linear transformation on ℝ^{2}. We represent the points in the plane by row vectors and the action of the linear transformation by right^{1} matrix multiplication. The map ϕ is then defined as follows: the image of the coset containing (x, y) is the one containing (ax + cy, bx + dy). This map is well-defined– i.e., the image does not depend on the choice of coset representative (x, y)– because A is invertible and maps ℤ^{2} onto itself.

Some things to note. The map ϕ is a homeomorphism. The coset {0} = ℤ^{2} is a fixed point of ϕ. 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

1Right multiplication on row vectors turns out to be a little more convenient than left multiplication on column vectors.

(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 ϕ 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}, … which implies that the orbit of (x, y) is finite.

The plane ℝ^{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 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 ϕ takes the form

ϕ(x, y) = ({ax + cy}, {bx + dy}).

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.

2.4 Symbolic Shifts^{2}. Let A, called an alphabet, denote an ordered set of N symbols, often taken to be {0, 1, …, N − 1}. The domain of this system is the space

(2.4.1)  Σ_{N} = A^{ℤ} = {s = (s_{n})_{n∈ℤ}|s_{n} ∈ A}

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.

The shift transformation σ is defined by shifting each bi-infinite sequence one step to the left. This is expressed by

(σ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

2For comprehensive treatment of this area we refer the reader to the book by Lind and Marcus [LM].

Figure 2.I. Full 2-shift

Σ_{N} one of the important compact ones–namely, the Cantor discontinuum– and the shift a homeomorphism. The symbolic system (Σ_{N}, σ) is called the full N-shift.

Restricting the shift transformation of a full shift Σ_{N} to a closed shift-invariant subspace Σ, we get very general kind of dynamical system (Σ, σ) called a subshift. Given a symbolic sequence s = (s_{n})_{n∈ℤ} and integers m < n, we shall use the notation s_{[m,n]} to stand for the m−n+1-tuple (s_{m}, s_{m+1}, …, s_{n}). Given a symbolic phase space Σ, we call a k-tuple an allowable k-block if it equals s_{[m,m+k−1]} for some s ∈ Σ.

Returning to the realm of the more specific from our momentary excursion into the less knowable, we define shift of finite type, also called topological Markov shift , as the subshift of a full shift restricted to the set Σ_{G} of bi-infinite paths in a finite directed graph G derived from a complete one by possibly removing some edges.

Usually we denote the space Σ_{G} by Σ_{A} where A is a matix of non-negative integers a_{ij} denoting the number of edges leading from the i-th node to the j-th. The term “Markov” is derived from the resemblance to Markov chains for which the a_{ij} are probabilities instead of integers. One thing to note is that the ij entry of A^{n} is the number of paths of length n beginning at i−th node and ending at the j−th. Often however A is an N × N matrix of zeroes and ones specifying a directed graph of N nodes (edges) according to the following: the i-th node (edge) is connected to the j-th, i ⟶ j, if and only if a_{ij} = 1. Whether dealing with nodes or edges, we call A a transition matrix and restate for zero-one matrices the above definition by

(2.4.2)  Σ_{G} = Σ_{A} ≡ {s = (…, s_{n}, …)|a_{s_{n},s_{n+1}} = 1, s_{n} ∈ A, n ∈ ℤ}.

Remark.. Let (Σ_{G}, σ) be a topological shift given by a node-labelled directed graph G. Nodes from which there is no return are called transient, the rest recurrent. A node is transient if and only if either it has no predecessor nodes or all its predecessors are transient. This statement is not as circular as it seems: for the set of predecessors of any set of transient nodes, if non-empty, is a strictly smaller set of transient nodes. The only symbols which appear in bi-infinite sequences of Σ_{G} are labels of recurrent nodes.

Figure 2.II. Fibonacci shift

Figure 2.II describes the Fibonacci or golden ratio shift, so-called because the number of admissible n-blocks (paths of length n) are the Fibonacci numbers– namely, there are two 1-blocks, three 2-blocks, five 3-blocks, ….

Here the space Σ_{A} is given by the matrix

A = ( \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} ) .

If we label the first node by 0 and and the second by 1, then only sequences of 0’s and 1’s with 1’s separated by 0’s are admissible. While other shifts of finite type can be specified by graphs with either nodes or edges labelled, there is no edge labelled graph for the Fibonacci shift.

Given a node labelled graph G, we define the edge graph G^{(2)} by labelling the edges. For labels we can use the allowable 2-blocks. In general we define the higher edge graphs G^{(n)} as follows. The alphabet consists of all allowable blocks [a_{1}, …, a_{n}] gotten from paths of length n on G. The transitions are defined by

[a_{1}, …, a_{n}] ⟶ [b_{1}, …, b_{n}]

if and only if b_{1} = a_{2}, …, b_{n−1} = a_{n}.

There is a one-side version of the full N-shift: namely,

(2.4.3)  Σ_{N}^{+} = {s = (s_{0}, s_{1}, …)|s_{n} ∈ A, n = 0, 1, 2, … }.

On this space the shift transformation σ is similarly defined: namely, (σs)_{n} = s_{n+1} but only for non-negative n. It acts by shifting sequences one step to the left and dropping the first symbol. The metric on this phase space is defined the same as before but absolute value signs are not needed. We also have one-side versions of shifts of finite type. In one-side symbolic systems, the shift transformation, like a multiplication map, is continuous but not invertible.

Exercises.

3.1 Prove that the canonical map ψ : G^{(n)} ⟶ G defined by ψ[s_{1}, …, s_{n}] = s_{1} gives topological conjugacy of (Σ_{G^{(n)}}, σ) and (Σ_{G}, σ).

3 Symbolic Representations.

Shifts of finite type contain a great deal of complexity, yet are the best understood dynamical systems. Such symbolic dynamical systems can be used to analyze general discrete time ones. For example, a good symbolic representation will show how to identify periodic orbits, almost periodic ones, dense ones, etc..

Representing a general dynamical system by a symbolic one involves a fundamental complication. We have two desires: we would like a continuous one-to-one correspondence between orbits ϕ^{n}x of the first and orbits σ^{n}s of the second; and we want the shift system to be one of finite type. Unfortunately these two desires are in conflict: constraints placed by topology must be observed. On one hand a continuous one-to-one correspondence makes X homeomorphic to a shift system. On the other hand a shift system is totally disconnected while X is often a smooth manifold. Thus for the most part we must abandon the quest of finding a topological conjugacy between a given dynamical system and a shift of finite type. However, we shall see that by sacrificing one-to-one correspondence we can still salvage a satisfactory symbolization of orbits. We are reminded of arithmetic in which we represent real numbers symbolically by decimal expansions, unique for the most part, but must allow two expansions for certain rationals. To do otherwise would just make the instructions for arithmetical operations unnecessarily complicated. The most natural way to associate a symbolic sequence with a point in a dynamical system is to track its history as illustrated in Figure 3.I through a family of sets indexed by an alphabet of symbols.

Figure 3.I. Partitioning a dynamical system

This is easy, but what is more difficult is to get a family for which each history represents just one point. It is no achievement to specify a family for which each history might represent more than one point. However, we must live with the inevitability that each point might have more than one associated histories. Having found a family of sets, the orbits through which determine a unique point, we want still more: namely, we would like the totality of sequences which arise to comprise a subshift of finite type. In order to do this, we must find a family with special properties. We shall look at some examples for guidance as to what these properties ought to be, and families of sets possessing them will be called Markov partitions.

The first example is the trivial case of a dynamical system which is identical with its symbolic representation: namely, a topological Markov shift.

3.1 Cylinder Set Partition for Symbolic Sequences. Let (Σ_{A}, σ) be a topological Markov shift, vertex labelled by an alphabet A. We form the partition C = {C_{a} : a ∈ A} of elementary cylinder sets determined by fixing the 0-th coordinate: i.e., C_{a} = {s ∈ Σ_{A} : s_{0} = a}. Tracking the history of an orbit of a element s ∈ Σ_{A} through this partition means getting a sequence (s_{n})_{n∈ℤ} such that σ^{n}s ∈ C_{s_{n}}. But this sequence is s itself. Let us point out the salient features of this partition.

First^{3},

⋂_{n=0}^{∞} ⋂_{−n}^{n} ϕ^{−k}C_{s_{k}} = {s}

Second, if s ∈ C_{a} ∩ σ^{−1}C_{b} ≠ ∅ then s ∈ C_{a} and σs ∈ C_{b} : i.e., s_{0} = a, s_{1} = b. In terms of the graph, this means there is an edge from a to b. An absolutely obvious property of directed graphs is the following. If there is an edge from a to b, and an edge from b to c, then there is a path from a to c via b. This property can be reformulated as follows. If C_{a} ∩ σ^{−1}C_{b} ≠ ∅ and C_{b} ∩ σ^{−1}C_{c} ≠ ∅ then C_{a} ∩ σ^{−1}C_{b} ∩ σ^{−2}C_{c} ≠ ∅. This property has a length n version for arbitrary n: namely, n abutting edges form a path of length n + 1 and this can be reformulated to read that n pair-wise non-empty intersections lead to an (n + 1)−fold nonempty intersection. We shall call such a countable set of conditions for n = 2, 3, ... the Markov property: it turns out to be a key requirement in getting the desired symbolic representation from a partition.

Finally, there is another important feature of the partition C = {C_{a} : a ∈ A} : namely, the sets of this partition have a product structure respected by the shift which is described as follows. Let s ∈ C_{a} – in other words, s_{0} = a – and define two sets

v_{a}(s) ≡ ⋂_{0}^{∞} σ^{−k}C_{s_{k}}

which we shall call the vertical through s and

h_{a}(s) ≡ ⋂_{−∞}^{0} σ^{−k}C_{s_{k}}

which we shall call the horizontal. A sequence s ∈ C_{a} is the sole member of the intersection of its vertical and horizontal– i.e. {s} = v_{a}(s) ∩ h_{a}(s). Furthermore, for s, t ∈ C_{a} there is a unique sequence in the intersection of the horizontal through s and the vertical through t : namely, {(… s_{−2}, s_{−1}, s_{0} = t_{0}, t_{1}, t_{2}, …)} = v_{a}(s) ∩ h_{a}(t). We define a map of C_{a} × C_{a} onto C_{a} by (s, t) ↦ h_{a}(s) ∩ v_{a}(t), or rather the sole element of this intersection. It is easily verified that this map is continuous and its restriction to h_{a}(s)×v_{a}(t) for any s, t ∈ C_{a} is a homeomorphism of h_{a}(s)×v_{a}(t) onto C_{a}. Finally σ respects this product structure in the sense that if s ∈ C_{a}∩σ^{−1}C_{b} then:

σv_{a}(s) ⊂ v_{b}(σs),
σh_{a}(s) ⊃ h_{b}(σs).

This last property is closely connected with the Markov one.

The next example is based on the binary expansions of real numbers, and illustrates what one should expect of a good symbolic a representation of a dynamical system.

3From now on we shall commit a convenient semantic error of confusing a set consisting of a single point with the point itself and so dispense with the surrounding braces

3.2 Symbolic Representation for Multiplication by Two. Let (X, f) be the multiplication system where and f : x → {2x}. Recall that the domain Σ_{2}^{+} of the one-sided full 2-shift dynamical system (Σ_{[2]}^{+}, σ^{+}) is the set of one-sided infinite walks on the edge-labelled graph in Figure 2.I. We can equate a sequence s = (s_{n})_{n∈ℤ} with the binary expansion .s_{1}s_{2}s_{3} …. Consider the map π from Σ_{[2]}^{+} to X defined by π(s_{1} , s_{2} , …) = {s_{1}/2 + s_{2}/4 + … }. It is readily verified that

(i) fπ = πσ^{+}, (ii) π is continuous, (iii) π is onto, (iv) there is a bound on the number of pre-images (in this case two),

and

(v) there is a unique pre-image of ”most” numbers (here those with binary

expansions not ending in an infinite run of all zeros or all ones). The map π is not a homeomorphism, but we do have a satisfactory representation of the dynamical system by a one-sided 2-shift in the sense that: orbits are preserved; every point has at least one symbolic representative; there is a finite upper limit to the number of representatives of any point; and every symbolic sequence represents some point. This is a example of what is known as a factor map which we shall formalize in §4.

Figure 3.II. Graph of multiplication by 2 (mod 1)

As we have led to reader to expect, there is an alternate definition of π in terms of a partition. Consider R = {R_{0} = (0, 1/2), R_{1} = (1/2, 1)}. The elements of this family are disjoint open intervals whose closure cover the unit interval. The map π which associates sequences with points has an alternate expression in terms of this family: namely,

π(s_{1}, s_{2}, …) = ⋂_{n=0}^{∞} \overline{R_{s_{1}} ∩ f^{−1}(R_{s_{2}}) ∩ ⋯ ∩ f^{−n}(R_{s_{n+1}})}.

Remark. The reader might wonder about defining π by the simpler expression

π(s_{1}, s_{2}, …) = ⋂_{n=0}^{∞} \overline{f^{−n}(R_{s_{n+1}})}.

There are cases where this would suffice, but a difficulty can arise and does here. In X the point 0 which is identified with 1 is a fixed point of f which implies that 0 ∈ f^{−n}\overline{R_{i}} for i = 0, 1 and n ≥ 0. Thus, except for the all 0 or all 1 sequence, π(s_{1}, s_{2}, …) is a set which does not consist of a singleton: it contains two real numbers, one of which is the fixed point 0; and this renders π ill-defined. The most we can say in general is that

⋂_{n=0}^{∞} \overline{R_{s_{1}} ∩ f^{−1}(R_{s_{2}}) ∩ ⋯ ∩ f^{−n}(R_{s_{n+1}})} ⊊ ⋂_{n=0}^{∞} \overline{f^{−n}(R_{s_{n+1}})}

However, for the so-called expansive dynamical systems, when the size of partition elements is uniformly small enough, equality holds in which case π would be welldefined (see Proposition 5.8).

Next we consider hyperbolic automorphisms of the 2-torus. This was the first smooth class of invertible dynamical systems found to have Markov partitions. This discovery was made by K Berg [B] in 1966 in his doctoral research. A short time later R. Adler and B Weiss [AW] constructed some special Markov partitions in order to prove that two such systems are conjugate in the measure theoretic sense if they have the same entropy. For these systems topological conjugacy implies measure conjugacy, but not conversely. We shall give a formal development the general two-dimensional case in a later chapter. Before making that plunge, we shall wet our toes with an informal discussion of one specific illustrative case. A rigorous proof of what we are about to describe will be achieved by Theorem 7.13.

3.3 Partition for a Toral Automorphism. Take the matrix

A = ( \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} )

which we have met before in quite a different context. Let X be the two-torus and ϕ be given by A : that is,

ϕ(x, y) = ({x + y}, x).

Figure 3.III. The torus and eigen-directions of A

The matrix A has two eigenvalues: λ = (1+\sqrt{5} )/2 and μ = (1−\sqrt{5} )/2. Observe that λ > 1 and −1 < μ < 0. Associated with these eigenvalues are the eigenvectors v_{λ} pointing into the first quadrant and v_{μ} 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 v_{μ}-component by |μ| and expand its v_{λ}-component by λ. Note μ is negative, which causes a direction reversal besides a contraction in the v_{μ}-component. We refer to the direction of v_{λ} as the expanding direction and that of v_{μ} as the 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 ℤ^{2} of one of the three missing triangles inside.

Figure 3.IV. Another fundamental region of 2-torus

We call this fundamental region the principal one, and draw within it the collection of open rectangles 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 Markov. We label significant points using the same letters for those which are equivalent.

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).

Along with the image we have included an outline of the original partition. Notice that ϕR_{3} is actually the same as R_{2}. Also notice how the other ϕ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: ϕR_{i} ∩ R_{j} ≠ ∅ according to whether j follows i in the edge graph in Figure 3.VII.

The boundary of the sets in R, ∂R_{i} = \overline{R_{i}} − R_{i}, consists of various line segments in the v_{λ} and v_{μ} directions. The union of those of the R_{i}’s in the v_{λ}-direction is called the expanding boundary of the partition and those in the v_{μ}-direction, the contracting boundary. By lattice translations of the various bounding segments, we

Figure 3.V. Partition of 2-torus

can reassemble their union into two intersecting line segments through the origin, ob̄ and ad̄, 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 ad̄ contains its image under A; whereas ob̄ is contained in its image, or equivalently ob̄ contains its inverse image. Because A preserves eigen-directions and keeps the origin fixed, it is easy to see that ob̄ gets stretch over itself; but because there is a reflection involved it is not enough to know that the length of ad̄ is contracted by A. We must show that

Figure 3.VI. Its image

Figure 3.VII. Edge graph for ϕ acting on R

the points a and d̄ on the line segment ad̄ have their images within that segment. These points are the projections to l_{μ} in the v_{λ}-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 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 ϕ do not have any new boundary segments in the v_{μ}-direction that aren’t already contained in ad̄, while under negative iterates of ϕ there are no new ones in the v_{λ}-direction not already in ob̄. From this we obtain that for n ∈ ℕ a set ϕ^{n}R_{i} ∩ R_{j}, if nonempty, is a union of rectangles stretching in the expanding direction all the way across R_{j}. Similarly, a non-empty R_{i} ∩ ϕ^{−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 ⋂_{k=−n}^{0} ϕ^{−k}R_{s_{k}} ≠ ∅, then this intersection is a single rectangle stretching all the way across R_{s_{0}} in the expanding direction. Similarly, if ⋂_{k=0}^{n} ϕ^{−k}R_{s_{k}} ≠ ∅, then this set is a single rectangle stretching all the way across R_{s_{0}} in the contracting direction.

Figure 3.VIII. Intersections

Combining these two results we have that a non-empty closed set of the form \overline{⋂_{k=−n}^{n} ϕ^{−k}R_{s_{k}}} is a closed rectangle. The diameter of these sets is uniformly bounded by constant × |μ|^{n}. Thus as n → ∞, 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∈ℤ}. If fact, all points of the torus can be so represented.

If ⋂_{k=−n}^{n} ϕ^{−k}R_{s_{k}} ≠ ∅, then it is clear that R_{s_{i}} ∩ϕ^{−1}R_{s_{i+1}} ≠ ∅ for −n ≤ i ≤ 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}} ∩ϕ^{−1}R_{s_{i+1}} ≠ ∅ 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∈ℤ} are elements is a topological Markov shift.

Once again sets R_{i} have an obvious product structure. For p ∈ 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 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 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 ∈ R_{i} ∩ ϕ^{−1}R_{j} the following holds:

ϕv_{i}(p) ⊂ v_{j}(ϕp),
ϕh_{i}(p) ⊃ h_{j}(ϕp).

We shall incorporate we have just described in a comprehensive theory.

4. More on Abstract Dynamical Systems.

Definition 4.1. A dynamical system (X, ϕ) is said to be irreducible if for every pair of open sets U, V there exists n ≥ 0 such that ϕ^{n}U ∩ V ≠ ∅.

Another concept we need is the following

Definition 4.2. A point p is said to be bilaterally transitive if the forward orbit {ϕ^{n}p| n ≥ 0} and the backward orbit {ϕ^{n}p| n < 0} are both dense in X.

Remark.. A symbolic sequence in a topological Markov shift is bilaterally transitive if every admissible block appears in both directions and infinitely often.

We use the notation BLT (A) to denote the subset of bilaterally transitive points in A ⊆ 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.

Baire Category Theorem 4.3. Let {U_{n}} be a countable collection of open dense subsets of X. Then ⋂ U_{n} is nonempty. In fact ⋂ U_{n} is dense in X. Equivalently, a compact metric space in not the union of a countable collection of nowhere dense sets.

Proof. Choose inductively balls B_{n} such that B_{n} ⊂ \overline{B_{n}} ⊂ U_{n}, and \overline{B_{n}} ⊂ 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}∩U_{n} is a non-empty open set. The sequence (\overline{B_{n}})_{n∈ℕ} has the finite intersection property: so by compactness ⋂ \overline{B_{n}} is nonempty. But ⋂ \overline{B_{n}} ⊂ ⋂ B_{n} ⊂ ⋂ U_{n}. Thus the intersection ⋂ U_{n} is not empty. It is also dense which is a consequence of replacing U_{n} in the above argument by U_{n} ∩ B and X by \overline{B} where B is any ball. □

Proposition 4.4. If (X, ϕ) is irreducible, then the set of bilaterally transitive points is dense in X.

Proof. Let {U_{n}} be a countable basis for X. Since X is irreducible, ⋃_{k≥0} ϕ^{k}U_{n}, as well as ⋃_{k<0} ϕ^{k}U_{n}, is dense in X for each n. The set BLT (X) of bilaterally transitive points can be expressed as

BLT (X) = ⋂_{n}( ⋃_{k≥0} ϕ^{k}U_{n} ∩ ⋃_{k<0} ϕ^{k}U_{n}).

We apply the Baire Category Theorem to get BLT (X) ≠ ∅. But BLT (X) contains the whole orbit of any of its points and the orbit of any of its points is dense in X. □

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 4.5. A homeomorphism ϕ is said to be expansive if there exists a real number c > 0 such that if d(ϕ^{n}p, ϕ^{n}q) < c for all n ∈ ℤ then p = q.

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 4.6. For two general dynamical systems (X, ϕ) and (Y, ψ) we call the second a factor of the first and the first and extension of the second, if there exists a map π of X into Y, which we call a factor map, such that

(i) ψπ = πϕ, (ii) π is continuous, (iii) π is onto.

Furthermore, we say π is a finite factor map or that it is bounded-to-one if

(iv) there is a bound on the number of pre-images; and essentially^{4} one-to-one if

(v) every doubly transitive point has a unique pre-image.

Figure 4.I. Commutative diagram illustrating a factor map

We remark that a topological conjugacy^{5} 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.

Proposition 4.7. Let π be a factor map of (X, ϕ) and (Y, ψ) : i.e. π satisfies properties (i), (ii), and (iii) of Definition 4.6. If (X, ϕ) is irreducible, then so is (Y, ψ); and Y = \overline{BLT (Y)}.

Proof. Let U, V be non-empty open subsets of Y. By properties (i) and (iii) of factor maps, π^{−1}U, π^{−1}V are also non-empty and open. Since (X, ϕ) is irreducible,there exists n > 0 such that ϕ^{n}(π^{−1}U) ∩ π^{−1}V ≠ ∅. By 4.6(i),

∅ ≠ π[ϕ^{n}(π^{−1}U) ∩ π^{−1}V] = π[π^{−1}(ϕ^{n}U ∩ V)] = ψ^{n}U ∩ V.

4This term is used because in irreducible systems the non-doubly transitive points are negligible in both the sense of category and measure.

5Ther 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 homomorphism for factor map and isomorphism for topological conjugacy. These are the terms which denote the property of preserving structure.

Thus (Y, ψ) is irreducible and from Proposition 4.4 follows that Y = \overline{BLT (Y)}. □

Proposition 4.8. Let (X, ϕ) be irreducible and π an essentially one-to-one factor map of (X, ϕ) onto (Y, ψ): i.e. π satisfies (i),(ii),(iii), and (v) of Definition 4.6. Then π maps BLT (U) homeomorphically onto BLT (π(U)) for any open subset U of X.

Proof. From the properties of π, if the forward orbit of x hits every nonempty open subset of X, then the forward orbit of π(x) hits every nonempty open subset of Y. Thus πBLT (U) ⊂ BLT (π(U)).

We have that π is a continuous one-to-one map of BLT (U) into BLT (π(U)). We prove next that its inverse is continuous also. The proof is a standard compactness argument which goes as follows. Suppose y_{n} → y, where y_{n}, y ∈ BLT (π(U)). We shall prove that π^{−1}y_{n} → π^{−1}y. By compactness the sequence (π^{−1}y_{n})_{n∈ℕ} has limit points in X. Let x be any one of these limit points. By continuity πx = y. But the pre-image of y is unique: so the sequence (π^{−1}y_{n})_{n∈ℕ}, having only one limit point, has a limit which is π^{−1}y.

Now let x ∈ π^{−1}BLT (π(U)) ⊂ U and let V be any non-empty open subset of X. Choose v ∈ BLT (V). Then by what we have already shown π(v) ∈ BLT (π(V)). Then there exists a sequence of positive integers k_{n} such that ψ^{k_{n}}π(x) → π(v). Thus

ϕ^{k_{n}}(x) = π^{−1}ψ^{k_{n}}π(x) → π^{−1}π(v) = v.

Thus x ∈ BLT (U). We have therefore established π^{−1}BLT (π(U)) ⊂ BLT (U) : in other words, BLT (π(U)) ⊂ πBLT (U). □

Proposition 4.9. Under the hypothesis of Proposition 4.8, if U is an open subset of X, then BLT (πU) = BLT [πU]^{o} and π\overline{U} = \overline{[πU]^{o}}.

Proof. Let y ∈ BLT (πU). Then the unique pre-image of y lies in BLT (U), and πy is not therefore in the closed set π(X − U). Hence, πy ∈ Y − π(X − U) ⊂ [πU]^{o}. Therefore, BLT (πU) = BLT [πU]^{o}.

From the continuity properties of π, Proposition 4.8, and what was just proven, we get the following string of equalities: π(\overline{U}) = π(\overline{BLT (U)}) = \overline{BLT (πU)} = \overline{BLT [πU]^{o}} = □

Exercises.

4.1 We call a directed graph G 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 (Σ_{G}, σ) is irreducible. Conversely, show that if the dynamical system (Σ_{G}, σ) is irreducible then there is an irreducible sub-graph G′ such that Σ_{G} = Σ_{G′}.

4.2 Given any topological Markov shift system (Σ_{G}) there exists irreducible sub-graphs G_{1}, …, G_{M} such that

Σ_{G} = Σ_{G_{1}} ∪ ⋯ ∪ Σ_{G_{M}} (disjoint).

5. Topological Partitions.

Definition 5.1. We call a finite family of sets R = {R_{0}, R_{1}, …, R_{N−1}} a topological partition for a compact metric space X if:

(1) Each R_{i} is open^{6}

(2) R_{i} ∩ R_{i} = ∅, i ≠ j

(3) X = \overline{R_{0}} ∪ \overline{R_{1}} ∪ ⋯ ∪ \overline{R_{N−1}}.;

Remark. For open sets U, V, \overline{U} ∩ V ≠ ∅ ⇒ U ∩ V ≠ ∅. So for members of a topological partition we get the following string of implications: R_{i} ∩ R_{j} = ∅ ⇒ \overline{R_{i}} ∩ R_{j} = ∅ ⇒ \overline{R_{i}}^{o} ∩ R_{j} = ∅ ⇒ \overline{R_{i}}^{o} ∩ \overline{R_{j}} = ∅ ⇒ \overline{R_{i}}^{o} ∩ \overline{R_{j}}^{o} = ∅. Thus \overline{R_{i}}^{o} ∩ \overline{R_{j}}^{o} = ∅ for i ≠ j.

Definition 5.2. Given two topological partitions R = {R_{0}, R_{1}, …, R_{N−1}} and S = {S_{0}, S_{1}, …, S_{M−1}} we define their common topological refinement R ∨ S as

R ∨ S = {R_{i} ∩ S_{j} : R_{i} ∈ R, S_{j} ∈ S}.

Proposition 5.3. The common topological refinement of two topological partitions is a topological partition.

Proof. Let R and S be the two partitions in question. First of all, it is clear that the elements of R ∨ S are disjoint. We show that the closure of elements of R ∨ S cover X. Let p ∈ X. We have that p ∈ \overline{R_{i}} for some i. Thus there exists a sequence of points p_{n} ∈ R_{i} such that d(p_{n}, p) < 1/n. Since S is a topological partition, for each n there exists S_{j_{n}} ∈ S such that p_{n} ∈ \overline{S_{j_{n}}}. Since 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} ∈ R_{i} ∩ \overline{S_{j}} we can choose a sequence of points q_{m,n} ∈ R_{i} ∩ S_{j} such that d(q_{m,n}, p_{n}) < 1/m. Thus d(q_{n,n}, p) < 2/n whence q_{n,n} → p as n → ∞. Therefore p ∈ \overline{R_{i} ∩ S_{j}}.

□

Proposition 5.4. For dynamical system (X, ϕ) with topological partition R of X, the set ϕ^{n}R defined by ϕ^{n}R = {ϕ^{n}R_{1}, …, ϕ^{n}R_{N−1}} is again a topological partition.

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. □

From Proposition 5.3 and 5.4 we have that for m ≤ n, ⋁_{m}^{n} ϕ^{k}R = ϕ^{m}R ∨ ϕ^{m−1}R ∨ ⋯ ∨ ϕ^{n}R is again a topological partition. We shall use the notation

R^{(n)} ≡ ⋁_{k=0}^{n−1} ϕ^{−k}R.

6Previous 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.

Thus R^{(2)} = R∨ϕ^{−1}R = {R_{i}∩ϕ^{−1}R_{j} : R_{i}, R_{j} ∈ R}. Observe that (R^{(2)})^{(2)} = R^{(3)}, or more generally (R^{(n)})^{(m)} = R^{(n+m−1)}.

The collection ⋃ ϕ^{n}R : n ∈ ℤ 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.

Proposition 5.5. Let R be a topological partition for dynamical system (X, ϕ). For every p ∈ X there exists a sequence (R_{s_{k}})_{k∈ℤ} of sets in R such that p ∈ ⋂_{n=0}^{∞} \overline{⋂_{−n}^{n} ϕ^{−k}R_{s_{k}}}.

Proof. Since ⋁_{m}^{n} ϕ^{k}R, m ≤ n, is a topological partition, there is a set in it whose closure contains p, say \overline{⋂_{m}^{n} ϕ^{−k}R_{s_{k}}}. We next show that in the refinement ⋁_{m−1}^{n+1} ϕ^{k}R the elements of the form ⋂_{m−1}^{n+1} ϕ^{−k}R_{t_{k}} where t_{k} = s_{k} for m ≤ k ≤ n comprise a subfamily which is a topological partition of \overline{⋂_{m}^{n} ϕ^{−k}R_{s_{k}}}. Because ⋁_{m−1}^{n+1} ϕ^{k}R satisfies 5.1(1) and (2), so does any subfamily. Condition 5.1(3) is a consequence of

⋃_{\begin{matrix}0≤t_{m−1}≤N−1 \\ 0≤t_{n+1}≤N−1 \\ t_{k}=s_{k}, m≤k≤n \end{matrix}} ⋂_{m−1}^{n+1} ϕ^{−k}R_{t_{k}} = ⋂_{m}^{n} ϕ^{−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}}, …, R_{s_{n}} such that p ∈ \overline{⋂_{−n}^{n} ϕ^{−k}R_{s_{k}}}, we can find sets R_{s_{−n−1}} and R_{s_{n+1}} such that p ∈

\overline{⋂_{−n−1}^{n+1} ϕ^{−k}R_{s_{k}}}. Hence there exists a sequence (R_{s_{k}})_{k∈ℤ} of sets in R such that p ∈ ⋂_{n=0}^{∞} \overline{⋂_{−n}^{n} ϕ^{−k}R_{s_{k}}}. □

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}}, …, R_{s_{n}} can be extended to a bi-infinite sequence (R_{s_{n}})_{n∈ℤ} such that if p ∈ \overline{⋂_{m}^{n} ϕ^{−k}R_{s_{k}}}, m ≤ n, then p ∈ ⋂_{n=0}^{∞} \overline{⋂_{−n}^{n} ϕ^{−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}}, … to a bi-infinite one.

Definition 5.6. We define the diameter d(R) of a partition R by

d(R) = max_{R_{i}∈R} d(R_{i})

where d(R_{i}) ≡ sup_{x,y∈R_{i}} d(x, y).

Definition 5.7. We call a topological partition a generator for a dynamical system (X, ϕ) if lim_{n→∞} d (⋁_{−n}^{n} ϕ^{k}R) = 0.

If R is a generator then clearly lim_{n→∞} d (⋂_{−n}^{n} ϕ^{−k}R_{s_{k}}) = 0 for any sequence of symbols (s_{i})_{i∈ℤ} ∈ {0, …, N − 1}^{ℤ}. The converse is also true (see exercise 5.1). In addition d (⋂_{n=0}^{∞} \overline{⋂_{−n}^{n} ϕ^{−k}R_{s_{k}}}) = 0. Hence in Proposition 5.5, if R is a generator

and p ∈ ⋂_{n=0}^{∞} \overline{⋂_{−n}^{n} ϕ^{−k}R_{s_{k}}}, then p = ⋂_{n=0}^{∞} \overline{⋂_{−n}^{n} ϕ^{−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.

Proposition 5.8.. Let (X, ϕ) be expansive and R be a topological partition such that d(R) < c where c is the expansive constant. Then R is a generator;

Proof. The set ⋂_{−∞}^{∞} ϕ^{−k}\overline{R_{s_{k}}} contains at most one point and thus has zero diameter: for if there exists p, q ∈ ⋂_{−∞}^{∞} ϕ^{−k}\overline{R_{s_{k}}}, then d(ϕ^{n}p, ϕ^{n}q) < c for n ∈ ℤ implying p = q. Since ⋂_{−n}^{n} ϕ^{−k}R_{s_{k}} ⊂ ⋂_{−n}^{n} ϕ^{−k}\overline{R_{s_{k}}}, d (lim_{n→∞} ⋂_{−n}^{n} ϕ^{−k}R_{s_{k}}) = d (⋂_{−∞}^{∞} ϕ^{−k}\overline{R_{s_{k}}}) = 0. From Exercise 5.1 we get that R is a generator. □

Remarks. Generally we merely have the inclusion relation

(5.9)  ⋂_{n=0}^{∞} \overline{⋂_{−n}^{n} ϕ^{−k}R_{s_{k}}} ⊂ ⋂_{−∞}^{∞} ϕ^{−k}\overline{R_{s_{k}}}

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 ⋂_{n=0}^{∞} \overline{⋂_{−n}^{n} ϕ^{−k}R_{s_{k}}} ≠ ∅ then ⋂_{n=0}^{∞} \overline{⋂_{−n}^{n} ϕ^{−k}R_{s_{k}}} = ⋂_{−∞}^{∞} ϕ^{−k}\overline{R_{s_{k}}}.

From the inclusion relation (5.9) we see that if π(s) = p, then p ∈ \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 ∈ R_{i} or p ∈ \overline{R_{i}}^{o}, then s_{0} = i.. In addition, if there exists sequences s, t such that π(s) = π(t) = p and s_{0} = i ≠ j = t_{0}, then p ∈ \overline{R_{i}} ∩ \overline{R_{j}}, i ≠ j; and conversely. In which case p ∈ (\overline{R_{i}} − \overline{R_{i}}^{o}) ∩ (\overline{R_{j}} − \overline{R_{j}}^{o}) = ∂R_{i} ∩ ∂R_{j} : i.e. p belongs to the boundary of partition elements.

Let R = {R_{1}, …, R_{N}} be a generator for a dynamical system (X, ϕ) Let Σ be the subset of the full N-shift defined by

(5.10)  Σ ≡ \{s = (…, s_{n}, …) : ⋂_{n=0}^{∞} \overline{⋂_{−n}^{n} ϕ^{−k}R_{s_{k}}} ≠ ∅\}.

Because the topological partition R is a generator, the non-empty infinite intersection ⋂_{n=0}^{∞} \overline{⋂_{k=−n}^{n} ϕ^{−k}R_{s_{k}}} consists of a single point. Therefore, we can define a map π : Σ ⟶ X by

(5.11)  π(s) = ⋂_{n=0}^{∞} \overline{ϕ^{n}R_{s_{−n}} ∩ ϕ^{n−1}R_{s_{−n+1}} ∩ ⋯ ∩ ϕ^{−n}R_{s_{n}}}.

Figure 5.I. Commutative diagram for symbolic representation

Proposition 5.12.. Let the dynamical system (X, ϕ) have a topological partition R which is a generator. Then Σ as defined by (5.10) is a closed shift-invariant subset of Σ_{N} and the map π given by (5.11) is a factor map of the dynamical system (Σ, σ) onto (X, ϕ) − − i.e., π satisfies the following items of Definition 4.6:

(i) σπ = πϕ, (ii) π is continuous, (iii) π is onto.

Proof. To prove Σ is closed we must show that if s = (…, s_{k}, …) ∈ \overline{Σ} then

(5.13)  ⋂_{n=0}^{∞} \overline{⋂_{−n}^{n} ϕ^{−k}R_{s_{k}}} ≠ ∅,

which then implies that s ∈ Σ. For each n > 1 there is a sequence t = (…, t_{k}, …) ∈ Σ such that d(t, s) < 1/n. This means that t_{k} = s_{k}, −n ≤ k ≤ n so that

\overline{⋂_{−n}^{n} ϕ^{−k}R_{t_{k}}} = \overline{⋂_{−n}^{n} ϕ^{−k}R_{s_{k}}}.

Because t ∈ Σ, 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 Σ is σ−invariant we must show that if s ∈ Σ then σs ∈ Σ : in other words, for n ≥ 0, if ⋂_{−n}^{n} ϕ^{−k}R_{s_{k}} ≠ ∅ then ⋂_{−n}^{n} ϕ^{−k}R_{s_{k+1}} ≠ ∅. This follows from using the distributive property of ϕ^{−1} with respect to intersections and reindexing: i.e.

ϕ^{−1} (⋂_{−n}^{n} ϕ^{−k}R_{s_{k+1}}) = ⋂_{−n+1}^{n+1} ϕ^{−k}R_{s_{k}} ⊃ ⋂_{−n+1}^{n−1} ϕ^{−k}R_{s_{k}}.

We now turn our attention to the properties of π.

(i) π satisfies πσ = ϕπ. This follows from reindexing after applying the property that a homeomorphism commutes with the closure operation and preserves intersections: to wit,

ϕπ(s) = ϕ ⋂_{n=0}^{∞} \overline{⋂_{−n}^{n} ϕ^{−k}R_{s_{k}}}

= ⋂_{n=0}^{∞} \overline{⋂_{−n}^{n} ϕ^{−k+1}R_{s_{k}}}

= ⋂_{n=0}^{∞} \overline{⋂_{−n−1}^{n−1} ϕ^{−k}R_{s_{k+1}}}

= ⋂_{n=0}^{∞} \overline{⋂_{−n+1}^{n−1} ϕ^{−k}R_{s_{k+1}}} = π(σs).

(ii) π is continuous. From the generating property of R, given ϵ > 0 there is a positive integer n such that d(\overline{⋂_{−n}^{n} ϕ^{−k}R_{s_{k}}}) < ϵ. Thus, for s, t ∈ Σ_{G}, there is a δ > 0, namely δ = 1/(n + 1), such that if d(s, t) < δ then π(s), π(t) ∈ \overline{⋂_{−n}^{n} ϕ^{−k}R_{s_{k}}}.

(iii) π is onto. This follows immediately from Proposition 5.5.

□

Exercises.

5.1 Let R be a topological partition for a dynamical system (X, ϕ). Prove that if lim_{n→∞} d (⋂_{−n}^{n} ϕ^{−k}R_{s_{k}}) = 0 for any sequence of symbols (s_{i})_{i∈ℤ} ∈ {0, …, N − 1}^{ℤ} then lim_{n→∞} d (⋁_{−n}^{n} ϕ^{k}R) = 0.

6. Markov partitions and symbolic extensions.

Definition 6.1. We say that a topological partition R for a dynamical system (X, ϕ) satisfies the n-fold intersection property for a positive integer n ≥ 3, if R_{s_{k}} ∩ ϕ^{−1}R_{s_{k+1}} ≠ ∅, 1 ≤ k ≤ n − 1 ⇒ ⋂_{k=1}^{n} ϕ^{−k}R_{s_{k}} ≠ ∅. Furthermore, we call a topological partition Markov if it satisfies the n-fold intersection property for all n ≥ 3.

Remark.. In section 3.1 and before the term ”Markov” topological generator was defined, we considered the partition C = {C_{a} : a ∈ A} consisting of the elementary cylinder sets C_{a} = {s ∈ Σ_{G} : s_{0} = a} for a dynamical system (Σ_{G}, σ) where Σ_{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.

Proposition 6.2. If R is a Markov partition, then so is ⋁_{m}^{n} ϕ^{k}R for any m ≤ n.

Proof. We leave the proof as an exercise. □

If a topological partition 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.

Bootstrap Lemma 6.3. If R satisfies the 3-fold and R^{(2)} satisfies the n-fold intersection properties, n ≥ 3, then R satisfies the (n+1)-fold intersection property.

Proof. Suppose R_{i_{k}} ∩ ϕ^{−1}R_{i_{k+1}} ≠ ∅, 1 ≤ k ≤ n. Because R satisfies the 3-fold intersection property, we have

R_{i_{k}} ∩ ϕ^{−1}R_{i_{k+1}} ∩ ϕ^{−2}R_{i_{k+2}} ≠ ∅, 1 ≤ k ≤ n − 1.

In other words,

(R_{i_{k}} ∩ ϕ^{−1}R_{i_{k+1}}) ∩ ϕ^{−1}(R_{i_{k+1}} ∩ ϕ^{−1}R_{i_{k+2}}) ≠ ∅, 1 ≤ k ≤ n − 1.

Because R^{(2)} satisfies the n-fold intersection property, we obtain

⋂_{1}^{n+1} ϕ^{−k}R_{i_{k}} = ⋂_{1}^{n} ϕ^{−k}(R_{i_{k}} ∩ ϕ^{−1}R_{i_{k+1}}) ≠ ∅.

□

Suppose a dynamical system (X, ϕ) has a Markov generator R = {R_{0}, …, R_{N−1}}. We define an associated topological Markov shift given by the directed graph G whose vertices are labelled by A = {0, 1, …, N − 1} and in which the i-the vertex is connected to the j-th, i → j, iff R_{i} ∩ ϕ^{−1}R_{j} ≠ ∅. So by definition of the Markov shift associated with a transition matrix of a directed graph,

(6.4)  Σ_{G} = {s = (s_{n})_{n∈ℤ} : R_{s_{n−1}} ∩ ϕ^{−1}R_{s_{n}} ≠ ∅, s_{n} ∈ A, n ∈ ℤ}.

This set coincides with the subsystem defined by 5.10 which is easily seen as follows. On one hand, for s ∈ Σ_{G}, each of the closed sets

\{\overline{⋂_{k=−n}^{n} ϕ^{−k}R_{s_{k}}} | n = 1, 2 … \}

for any n ≥ 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 ⋂_{n=0}^{∞} \overline{⋂_{k=−n}^{n} ϕ^{−k}R_{s_{k}}} ≠ ∅. On the other hand, if ⋂_{n=0}^{∞} \overline{⋂_{k=−n}^{n} ϕ^{−k}R_{s_{k}}} ≠ ∅, then each finite intersection under the closure sign is non-empty which in turn implies that each pair of intersections R_{s_{k}} ∩ ϕ^{−1}R_{s_{k}} ≠ ∅, for arbitrary k ∈ ℤ.

Main Theorem.

Theorem 6.5. Suppose the dynamical system (X, ϕ) is expansive and has a Markov generator R = {R_{0}, …, R_{N−1}}. Then the map π, as defined by (5.11), is an essentially one-to-one finite factor map of the shift of finite type Σ_{G}, as defined by (6.1), onto X. Furthermore, If (X, ϕ) is irreducible, then so is (Σ_{G}, σ).

Proof. We must establish (i) - (v) in Definition 4.6. That π is a factor map– namely, it satisfies items (i), (ii), and (iii)–is the content of theorem 5.12.

In order to establish (iv)–namely, a bound on the number of pre-images under π–we introduce the following concept.

Definition 6.6. A map π from Σ_{G} to X said to have a diamond if there are two sequences s, t ∈ Σ_{G} for which π(s) = π(t) and for which there exist indices k < l < m such that s_{k} = t_{k}, s_{l} ≠ t_{l}, s_{m} = t_{m}.

Lemma 6.7. If the number of pre-images of a point is more than N^{2}, then π has a diamond.

Proof. We apply the familiar ”pigeon hole” argument. Let s^{(1)}, … s^{(N^{2}+1)} be N^{2}+1 different sequences which map to the same point. Since the sequences are distinct, there are a pair of indices k, m such that the allowable blocks s_{[k,m]}^{(1)}, … s_{[k,m]}^{(N^{2}+1)}

Figure 6.I. A diamond

are distinct. There are N^{2} distinct choices of pairs of symbols (s_{k}^{(i)}, s_{m}^{(i)}) : so by the ”pigeon hole principle” there must be two allowable blocks s_{[k,m]}^{(i)}, s_{[k,m]}^{(j)}, such

that (s_{k}^{(i)}, s_{m}^{(i)}) = (s_{k}^{(j)}, s_{m}^{(j)}). But, since the blocks are different, there is an index l such that s_{l}^{(i)} ≠ s_{l}^{(j)}. Thus the two sequences s^{(i)}, s^{(j)} map to the same point, agree at indices k, m, but differ at l which is between k, m, which means there is a diamond. □

Lemma 6.8. If there exists a bilaterally transitive point with two pre-images, then π has a diamond.

Proof. Let a BLT p have two pre-images. As we have indicated in the remark following 5.8, there are two sets R_{a}, R_{b} ∈ R, a ≠ b, such that p ∈ \overline{R_{a}} ∩ \overline{R_{b}}. For each n > 0, the family of sets

\{\overline{ϕ^{n}R_{s_{−n}} ∩ ⋯ ∩ R_{s_{0}} ∩ … ϕ^{−n}R_{s_{n}}} : s ∈ Σ_{G} where s_{0} = a\}

covers \overline{R_{a}}; and the family

\{\overline{ϕ^{n}R_{t_{−n}} ∩ ⋯ ∩ R_{t_{0}} ∩ … ϕ^{−n}R_{t_{n}}} : t ∈ Σ_{G} where t_{0} = b\}

covers \overline{R_{b}}. Thus, by compactness, there exists s, t ∈ Σ_{G} with s_{0} = a, t_{0} = b such that

p ∈ ⋂_{n=0}^{∞} \overline{⋂_{−n}^{n} ϕ^{−k}R_{s_{k}}}

and

p ∈ ⋂_{n=0}^{∞} \overline{⋂_{−n}^{n} ϕ^{−k}R_{t_{k}}}

Since p is bilaterally transitive and R_{0} is open, ϕ^{n}p ∈ R_{0} for some positive n and ϕ^{m}p ∈ R_{0} for some negative m. Thus by the remark following (5.8), s_{m} = t_{m} = 0, s_{0} = a ≠ b = t_{0}, s_{n} = t_{n} = 0, which is a diamond for π. □

Lemma 6.9. If d(R) < c/2, then π has no diamonds.

proof. Since πσ = ϕπ, we can asume without loss of generality that k = 1 in the definition of diamond. Assume that p = π(s) = π(t) where

s = (…, s_{−2}, a, b_{0}, b_{1}, …, b_{m−1}, d, s_{m+1}, …),
t = (…, t_{−2}, a, c_{0}, c_{1}, …, c_{m−1}, d, t_{m+1}, …).

We must show that b_{l} = c_{l} for 0 ≤ l ≤ m − 1. Because [a, b_{0}, b_{1}, …, b_{m−1}, d] is an allowable block in Σ_{G},

ϕR_{a} ∩ R_{b_{0}} ∩ ϕ^{−1}R_{b_{1}} ∩ ⋯ ∩ ϕ^{−m+1}R_{m−1} ∩ ϕ^{−m}R_{d} ≠ ∅.

Choose a point q in this open set. Because π is onto, there is a sequence

u = (…, u_{−2}, a, b_{0}, b_{1}, …, b_{m−1}, d, u_{m+1}, …) ∈ Σ_{G}

such that π(u) = q. Also since [a, c_{0}, c_{1}, …, c_{m−1}, d] is an allowable block and Σ_{G} is a shift of finite type, there is a sequence v ∈ Σ_{G} such that

v = (…, u_{−2}, a, c_{0}, c_{1}, …, c_{m−1}, d, u_{m+1}, …).

Thus

r ≡ π(v) ∈ \overline{ϕR_{a} ∩ R_{c_{0}} ∩ ϕ^{−1}R_{c_{1}} ∩ ⋯ ∩ ϕ^{−m+1}R_{m−1} ∩ ϕ^{−m}R_{d}}.

From d(R_{i}) < c/2 and ϕ^{l}(x) ∈ \overline{R_{b_{l}}} ∩ \overline{R_{c_{l}}} for 0 ≤ l ≤ m − 1, we conclude by the triangle inequality that d(ϕ^{l}q, ϕ^{l}r) < c. Furthermore, d(ϕ^{n}q, ϕ^{n}r) < c/2 for n < 0 and n > m−1. The expansive property then implies that q = r. Thus R_{b_{l}} ∩\overline{R_{c_{l}}} ≠ ∅ which implies that R_{b_{l}} ∩ R_{c_{l}} ≠ ∅. However, elements of R are pairwise disjoint: so b_{l} = c_{l}. □

(iv) There is a bound on the number of pre-images of π.

(v) A BLT point has a unique pre-image.

Because R is a generator, n can be chosen so that d (⋁_{−n}^{n} ϕ^{k}R) < c/2. By Proposition 6.2, ⋁_{−n}^{n} ϕ^{k}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 π^{(2n+1)} be the map of Σ_{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 π satisfies π = π^{(2n+1)}ψσ^{n} where ψ a conjugacy of Σ_{G} onto Σ_{G^{(2n+1)}}. Thus we have that under π 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 □

Converse to the Main Theorem. Recall that we introduced in 3.1 the partition C = {C_{i} : i = 0, …, N −1} consisting of the elementary cylinder sets C_{i} = {s ∈ Σ_{G} : s_{0} = i} for a dynamical system (Σ_{G}, σ) where Σ_{G} is a shift of finite type base on an alphabet A = {0, 1, …, N −1}. This partition is a topological Markov generator.

Theorem 6.10. Let (X, ϕ) be a dynamical system, (Σ_{G}, σ) an irreducible shift of finite type based on N symbols; and suppose there exists an essentially one-to-one factor map π from Σ_{G} to X. Then the partition R defined by R = {R_{i} = π(C_{i})^{o} : i = 0, …, N − 1} is a topological Markov generator.

Remark. Note we assume π 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: i.e., π 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).

Proof.

We must prove the following items

(1) Elements of R are disjoint:

(2) The closure of elements of R cover X.

(3) R is a generator.

(4) R satisfies the Markov property.

(1) Elements of R are disjoint: i.e., R_{i} ∩ R_{j} = ∅, i ≠ 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} ∩ R_{j} ≠ ∅ for i ≠ j. Then, by Proposition 4.7 BLT (R_{i} ∩ R_{j}) ≠ ∅. By Propositions 4.8 and 4.9, π^{−1} maps BLT (R_{i}) and BLT (R_{j}) homeomorphically onto BLT (C_{i}) and BLT (C_{j}) respectively. Therefore π^{−1} maps BLT (R_{i} ∩ R_{j}) = BLT (R_{i}) ∩ BLT (R_{j}) homeomorphically onto BLT (C_{i} ∩ C_{j}) = BLT (C_{i}) ∩ BLT (C_{j}), which implies that ∅ ≠ BLT (C_{i} ∩ C_{j}) ⊂ C_{i} ∩ C_{j}, a contradiction.

(2) X = ∪_{i=0}^{N−1}\overline{R_{i}}.

X = π(Σ_{G}) = π ∪_{i=0}^{N−1} C_{i} = ∪_{i=0}^{N−1}π(C_{i}) = ∪_{i=0}^{N−1}\overline{R_{i}}, the last inequality following from Proposition 4.9.

For the next two items we need a lemma.

Lemma 6.11. Under the hypothesis of 6.10, π(⋂_{m}^{n} σ^{−k}C_{s_{k}}) = \overline{⋂_{m}^{n} ϕ^{−k}R_{s_{k}}} for m < n.

Proof. Once again we use the bilaterally transitive points to deal with images of intersections. We have the following string of equalities.

π(⋂_{m}^{n} σ^{−k}C_{s_{k}}) = π (\overline{BLT (⋂_{m}^{n} σ^{−k}C_{s_{k}})}) = \overline{π(⋂_{m}^{n} BLT (σ^{−k}C_{s_{k}}))}

which by injectivity of π and shift-invariance of bilateral transitive points

= \overline{⋂_{m}^{n} π(BLT (σ^{−k}C_{s_{k}}))} = \overline{⋂_{m}^{n} πσ^{−k}BLT ((C_{s_{k}}))}

which by commutativity of π and Proposition4.8

= \overline{⋂_{m}^{n} ϕ^{−k}π(BLT (C_{s_{k}}))} = \overline{⋂_{m}^{n} ϕ^{−k}(BLT π(C_{s_{k}}))}

which by Proposition 4.9

= \overline{⋂_{m}^{n} ϕ^{−k}(BLT (R_{s_{k}}))} = \overline{BLT (⋂_{m}^{n} ϕ^{−k}(R_{s_{k}}))}

= \overline{⋂_{m}^{n} ϕ^{−k}(R_{s_{k}})}.

Q.E.D.

(3) R is a generator.

Because C is a generator, d (⋂_{−n}^{n} σ^{−k}C_{s_{k}}) → 0. By Lemma 6.11 , π(⋂_{−n}^{n} σ^{−k}C_{s_{k}}) = \overline{⋂_{−n}^{n} ϕ^{−k}R_{s_{k}}}. So, by continuity of π, we get

d (\overline{⋂_{−n}^{n} ϕ^{−k}R_{s_{k}}}) = d (⋂_{−n}^{n} ϕ^{−k}R_{s_{k}}) → 0.

(4) R satisfies the Markov property.

Suppose R_{s_{i}} ∩ ϕ^{−1}R_{s_{i+1}} ≠ ∅, 1 ≤ k ≤ n − 1. By Lemma 6.11 we have π[C_{s_{i}} ∩ σ^{−1}C_{s_{i+1}}] = \overline{R_{s_{i}} ∩ ϕ^{−1}R_{s_{i+1}}} ≠ ∅, 1 ≤ k ≤ n − 1. Thus C_{s_{i}} ∩ σ^{−1}C_{s_{i+1}} ≠ ∅, 1 ≤ k ≤ n − 1. Since C satisfies the Markov property, ⋂_{k=1}^{n} ϕ^{−k}C_{s_{k}} ≠ ∅ for all n > 1. So π(⋂_{k=1}^{n} ϕ^{−k}C_{s_{k}}) = \overline{⋂_{k=1}^{n} ϕ^{−k}R_{s_{k}}} ≠ ∅ for all n > 1. Therefore, ⋂_{k=1}^{n} ϕ^{−k}R_{s_{k}} ≠ ∅ for all n > 1. □

Corollary 6.12. If in addition to the hypotheses of Theorem 4.18 the dynamical system (X, ϕ) is expansive, then π is finite.

Proof. We derive 4.6(iv) from from the assumption that the domain of π is irreducible, π satisfies 4.6(i), (ii), (iii), and (v), and ϕ is expansive. This is an immediate consequence of Theorems 6.10 and 6.5. □

Exercises.

6.1 A topological partition R for a dynamical system (X, ϕ) is Markov if and only if

⋂_{k=0}^{n} ϕ^{−k}R_{s_{k}} ≠ ∅, ⋂_{k=−n}^{0} ϕ^{−k}R_{s_{k}} ≠ ∅ ⇒ ⋂_{k=−n}^{n} ϕ^{−k}R_{s_{k}} ≠ ∅,

for n ≥ 0.

6.2 Under the hypothesis of Theorem 6.5 show that if (X, ϕ) is irreducible, then

so is (Σ_{G}, σ). 6.3 Show that in Theorem 6.10, condition (v) cannot be replaced by condition

(iv). Hint consider the following example. Let

A = ( \begin{matrix}1 & 1 & 0 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{matrix} ) ,

Figure 6.II. π indicated by edge-labels

and π : X_{A} → X_{2} be defined by

π[1, 1] = π[2, 3] = π[3, 2] = 1
π[1, 2] = π[2, 1] = π[3, 1] = 0.

Show disjointness is violated in the image partition of the elementary cylinder sets.

6.3 Let π be a factor map from a topological Markov shift (Σ_{A}, σ) to an expansive dynamical system (X, ϕ) with expansive constant c and let the partition R defined by R = {R_{i} = π(C_{i})^{o} : i = 0, …, N − 1} satisfy d(R) < c/2. Show if π has a diamond, then there exists a point p ∈ X with a continuum of pre-images.

7. Product Structure.

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 7.1. A partition of a set R is defined to be a family H = {h(p) : p ∈ R} of subsets of R such that for p, q ∈ R

(1) p ∈ h(p)

(2) h(p) ∩ h(q) ≠ ∅ ⇒ h(p) = h(q).

Definition 7.2. We call two partitions

H = {h(p) : p ∈ R},
V = {v(p) : p ∈ R}

of R transverse if, h(p) ∩ v(q) ≠ ∅ for every p, q ∈ R.

A set R with two transverse partitions H, 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 H as horizontals and those of V as verticals. When we are dealing with elements R_{i} of a topological partition R = {R_{i} : i = 1, …, N}, each of having a pair of transverse partitions H_{i}, V_{i}, we refer to h_{i}(p), as the horizontal through p in R_{i} and to v_{i}(p) as the 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 stable set for what we call a vertical and unstable set for a horizontal.

Definition 7.3. Suppose a dynamical system (X, ϕ) has a topological partition R = {R_{i}}, each member of which has a pair of transverse partitions. We say alignment of verticals and horizontals are respectively maintained by by ϕ and ϕ^{−1} if for all i, j

(1) p ∈ R_{i} ∩ ϕ^{−1}R_{j} ⇒ R_{j} ∩ ϕv_{i}(p) ⊂ v_{j}(ϕp);

(2) p ∈ R_{i} ∩ ϕR_{j} ⇒ R_{j} ∩ ϕ^{−1}h_{i}(p) ⊂ h_{j}(ϕ^{−1}p).

We actually require something stronger.

Definition 7.4. In a dynamical system (X, ϕ) we say a topological partition R = {R_{i}} has property M if each set R_{i} has a pair of transverse partitions such that alignments of horizontals and verticals are maintained by ϕ 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 R. In other words 7.3 (1) and (2) are replaced by:

(1) p ∈ R_{i} ∩ ϕ^{−1}R_{j} ⇒ ϕv_{i}(p) ⊂ v_{j}(ϕp),

(2) p ∈ R_{i} ∩ ϕR_{j} ⇒ ϕ^{−1}h_{i}(p) ⊂ h_{j}(ϕ^{−1}p).

We remark that with respect to horizontals 7.6(2) can be expressed alternatively as follows:

p ∈ R_{i} ∩ ϕ^{−1}R_{j} ⇒ ϕh_{i}(p) ⊃ h_{j}(ϕp).

Proposition 7.5. If R has property M, then so does R^{(2)}.

Proof. Let R_{i} ∩ ϕ^{−1}R_{j} ≠ ∅ be a member of 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} ∩ ϕ^{−1}R_{j} : namely,

(1) H(R_{i} ∩ ϕ^{−1}R_{j}) = {h_{ij}(p) = h_{i}(p) ∩ ϕ^{−1}R_{j} : p ∈ R_{i} ∩ ϕ^{−1}R_{j}},

(2) V(R_{i} ∩ ϕ^{−1}R_{j}) = {v_{ij}(p) = v_{i}(p) : p ∈ R_{i} ∩ ϕ^{−1}R_{j}}.

Figure 7.I. Property M Figure 7.II. Violations

Figure 7.III. Property M on R^{(2)}

First to verify that this pair of partitions is transverse, we observe that if p, q ∈ R_{i} ∩ ϕ^{−1}R_{j} then by 7.4(1)

v_{i}(q) ⊂ ϕ^{−1}v_{j}(ϕq) ⊂ ϕ^{−1}R_{j}.

From definition (1) we have

h_{ij}(p) ∩ v_{ij}(q) = h_{i}(p) ∩ ϕ^{−1}R_{j} ∩ v_{i}(q) = h_{i}(p) ∩ v_{i}(q) ≠ ∅.

Second, we show that ϕ and its inverse map verticals and horizontals so as to satisfy property M. Let p ∈ R_{i} ∩ ϕ^{−1}R_{j} ∩ ϕ^{−1}(R_{j} ∩ ϕ^{−1}R_{k}). On one hand, it is immediate from definition that

ϕv_{ij}(p) = ϕv_{i}(p) ⊂ v_{j}(ϕp) = v_{ij}(ϕp).

On the other,

ϕh_{ij}(q) = ϕ(h_{i}(q) ∩ ϕ^{−1}R_{j}) ⊃ h_{j}(ϕq) ⊃ h_{j}(ϕq) ∩ ϕ^{−1}R_{k} = h_{jk}(ϕq).

□

Corollary 7.6. If R has property M then so does R^{(n)} for n = 1, 2, ….

Proof. Repeated use Proposition 7.5 using the identity (R^{(n)})^{(2)} = R^{(n+1)}. □

Proposition 7.7. For a dynamical system (X, ϕ) if a topological partition R has property M, then R satisfies the 3-fold intersection property.

Figure 7.IV. 3-fold Intersection Property

Proof. Let p ∈ ϕR_{i} ∩ R_{j} ≠ ∅ and q ∈ R_{j} ∩ ϕ^{−1}R_{k} ≠ ∅. Then by transversality v_{j}(q) ∩ h_{j}(p) ≠ ∅. Futhermore, v_{j}(q) ∩ h_{j}(p) ⊂ R_{j} and v_{j}(q) ∩ h_{j}(p) ⊂ ϕ^{−1}v_{k}(ϕq) ∩ ϕh_{i}(ϕ^{−1}p) ⊂ ϕ^{−1}R_{k} ∩ ϕR_{i} : So ϕR_{i} ∩ R_{j} ∩ ϕ^{−1}R_{k} ≠ ∅. Thus we have

R_{i} ∩ ϕ^{−1}R_{j} ≠ ∅, R_{j} ∩ ϕ^{−1}R_{k} ≠ ∅ ⇒ R_{i} ∩ ϕ^{−1}R_{j} ∩ ϕ^{−2}R_{k}.

□

Corollary 7.8. Given a dynamical system (X, ϕ), if a topological partition R has property M, then R^{(n)} is satisfies the 3-fold intersection property for n = 1, 2, ….

Proof. Follows from Corollary 7.6 and Proposition 7.7. □

Theorem 7.9. Given a dynamical system (X, ϕ), if a topological partition R has property M, then R is Markov.

Proof. Follows from Corollaries 7.6, 7.8, and the Bootstrap Lemma 6.3. For instance, R^{(n−1)} and R^{(n)} satisfies the 3-fold intersection property. so R^{(n−1)} satisfies the 4-fold one. Working our way back, we get R^{(n−2)} satisfies the 5-fold one, etc. Finally, we get that R satisfies the (n+2)−fold intersection property; but this is true for any n. □

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 R is given by ∂R_{i} ≡ \overline{R_{i}} − R_{i}. We denote the union of all boundaries of elements of R by ∂R ≡ ⋃_{i} ∂R_{i}. Suppose the boundary ∂R_{i} of each element of R is the union of two subsets: one, ∂_{V} R_{i} which we shall call the vertical boundary of R_{i}, the other, ∂_{H}R_{i}, the horizontal boundary of R_{i}. We denote the union of all vertical boundaries of elements of R by ∂_{V} R ≡ ⋃_{i} ∂_{V} R_{i}, and the union of all horizontal ones by ∂_{H}R ≡ ⋃_{i} ∂_{H}R_{i}.

Definition 7.10. We say that a topological partition R has boundaries satisfying property M if the following hold for each i :

(1) ∂R_{i} = ∂_{V} R_{i} ∪ ∂_{H}R_{i},

(2) \overline{v_{i}(p)} ∩ ∂R_{i} ⊂ ∂_{H}R_{i},

(3) \overline{h_{i}(p)} ∩ ∂R_{i} ⊂ ∂_{V} R_{i},

(4) ϕ∂_{V} R ⊂ ∂R,

(5) ϕ^{−1}∂_{H}R ⊂ ∂R.

We introduce the additional topological structure needed for the next theorem.

Definiton 7.11. We call a metric space R an abstract rectangle if it is homeomorphic to the Cartesian product two metric spaces– i.e. there exist two metric spaces H, V and a homeomorphism Φ of the Cartesian product H × V onto R.

Sets with a pair of transverse partitions usually arise in this way. Let Φ(p^{1}, p^{2}) = p, where p ∈ R and (p^{1}, p^{2}) ∈ H × V. Define the following horizontal and vertical sets of R :

h(p) ≡ Φ{(x, p^{2}) : x ∈ H},

Figure 7.V. Abstract rectangle

v(p) ≡ Φ{(p^{1}, y) : y ∈ V }.

Naturally the two partitions

H = {h(p) : p ∈ R},
V = {v(p) : p ∈ R}

of R are transverse since

v(p) ∩ h(q) = {Φ(p^{1}, q^{2})} ≠ ∅.

In addition, for each pair of points p, q ∈ R the map (p, q) ↦ v(p) ∩ h(q) is continuous, onto, and maps h(p) × 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.

Theorem 7.12. In a dynamical system (X, ϕ), if each element of a topological partition R is a connected abstract rectangle, the alignments of which are maintained by ϕ and its inverse respectively, and if R has boundaries with property M, then R itself has property M– i.e. R is a Markov partition.

Proof.

We give the proof only for verticals which consists in proving

p ∈ R_{i} ∩ ϕ^{−1}R_{j} ⇒ ϕv_{i}(p) ⊂ 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 ϕv_{i}(p) ⊈ R_{j}. The other one contradicts the connectivity of ϕv_{i}(p), which is a consequence of the the following.

Since R_{i} homeomorphic to h_{i}(p) × v_{i}(p), the vertical v_{i}(p) is connected: for otherwise R_{i} would not be. Therefore, the homeomorphic image ϕv_{i}(p) is connected as well. Thus, if ϕv_{i}(p) ⊈ R_{j}, then we would have that ϕv_{i}(p) ∩ ∂R_{j} ≠ ∅. Hence there would exist a point q ∈ ϕv_{i}(p) ∩ ∂R_{j} which is also in \overline{ϕv_{i}(p) ∩ R_{j}} : for if not,

Figure 7.VI. Impossible boundary picture

then there would be an open set U ⊃ ϕv_{i}(p) ∩ ∂R_{j} such that U ∩ ϕv_{i}(p) ∩ R_{j} = ∅, and the open sets R_{j} and U ∪ (X − \overline{R_{j}}) would disconnect ϕv_{i}(p).

By preservation of alignments, we have ϕv_{i}(p) ∩ R_{j} ⊂ v_{j}(ϕp) so that q ∈ \overline{v_{j}(ϕp)}. Thus q ∈ ∂_{H}R from which follows by property M for boundaries that ϕ^{−1}(q) ∈ ∂R. However, ϕ^{−1}(q) ∈ v_{i}(p) ⊂ R_{i}, which contradicts R_{i} ∩ ∂R_{i} = ∅.

□

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.

8. Markov Partitions for Automorphisms of the 2-torus.

Let X = ℝ^{n}/ℤ^{n} be the n-dimensional torus and A a n × n matrix with integer entries and determinant ±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 general linear group GL(n, ℤ). Both a matrix A and the automorphism ϕ it defines are called hyperbolic, if A has no eigenvalue of modulus one.

We shall devote the rest of this section to the two dimensional case; i.e. n = 2. Let

A = ( \begin{matrix}a & b \\ c & d \end{matrix} ) ∈ GL(2, ℤ).

Eigenvalues of A are are the solutions of the quadratic equation

x^{2} − (traceA)x + detA = 0.

Here hyperbolicity means that A has two distinct eigenvalues, say λ and μ which are irrational numbers. Since λμ = detA = ±1, we can assume that |λ| > 1 and |μ| < 1. An easy calculation shows that the row vectors

v_{λ} = (c, λ − a)
v_{μ} = (c, μ − a)

are eigenvectors associated with λ and with μ respectively. The action of A on a vector v is to contract its v_{μ}-component by μ and expand its v_{λ}-component by λ. Directions may or not be reversed depending on the signs of the eigenvalues. We refer to the direction of v_{λ} as the expanding direction and that of v_{μ} as the contracting one. Finally let ℓ_{λ} be a line through the origin in the expanding direction and ℓ_{μ} the one in the contracting direction. We call these lines, which are invariant under the action of A on the plane, the expanding and contracting eigen-line respectively. The slopes of these lines are m_{λ} = (λ − a)/c and m_{μ} = (μ − 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_{λ} and m_{μ} would be rational numbers and so would λ and μ.

Theorem 8.1. A hyperbolic toral automorphism is expansive.

Proof. Let ϕ be an automorphism and p, q ∈ X be any two different points of the two dimensional torus. Let c = |μ|/8. We shall show that there exists n ∈ ℤ such that d(ϕ^{n}p, ϕ^{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}, ϕ^{n}r) > c, for any r ≠ {0} in X.

Figure 8.I. A fundamental region and eigen-directions of A

We take the torus to be given by the fundamental region

X = {(x, y) : |x| ≤ 1/2, |y| ≤ 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 ≠ (0, 0). Let r_{λ} and r_{μ} be the v_{λ}−component and the v_{μ}−component of r respectively. Then from the triangle inequality

|λ^{n}r_{λ}| − |μ^{n}r_{μ}| ≤ ||ϕ^{n}r|| ≤ |λ^{n}r_{λ}| + |μ^{n}r_{μ}|.

One of the components r_{λ}, r_{μ} is not zero. We can assume that r_{λ} ≠ 0 : otherwise replace ϕ by ϕ^{−1} in the argument. We can also assume that |μ| < \frac{1}{2} : for, if not, replace ϕ by ϕ^{k} for large enough k. If ||r|| > \frac{|μ|}{4}, then ||ϕ^{n}r|| > c for n = 0. If ||r|| ≤ \frac{|μ|}{4}, choose n ≥ 1 such that

\frac{|μ|^{n+1}}{4} ≤ |r_{λ}| ≤ \frac{|μ|^{n}}{4} .

Then the following inequalities inequality show that ϕ^{n}r is in the fundamental region and that ||ϕ^{n}r|| > c.

|λ^{n}r_{λ}| + |μ^{n}r_{μ}| ≤ \frac{1}{4} + \frac{|μ|^{n+1}}{4} < \frac{1}{2},

\frac{|μ|}{8} ≤ \frac{|μ|}{4} − \frac{|μ|^{n+1}}{4} ≤ |λ^{n}r_{λ}| − |μ^{n}r_{μ}|.

□

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 ϕ be given by the matrix

A = ( \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} )

and the topological Markov shift (Σ_{G}, σ) by the edge-graph G of figure 3.VIII. Theorem 8.1 shows that ϕ 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.

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, ℤ) 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 [W] proved by entirely elementary methods of plane geometry.

Theorem 8.2. Let A ∈ GL(2, ℤ) be hyperbolic. Then there exists C, P ∈ GL(2, ℤ) such that CAC^{−1} = ϵP where ϵ = ±1, the choice of sign being the same as that of λ, and the entries of the matrix

P = ( \begin{matrix}p & q \\ r & s \end{matrix} )

are non-negative.

Proof.

Choose a pair of lattice points (α, β) , (γ, δ) such that

(i) The angle (α, β)(0, 0)(γ, δ) is acute and ℓ_{λ} lies in it but ℓ_{μ} does not.

(ii) The closed parallelogram with vertices the origin, the two lattice points,

and the lattice point (α + γ, β + δ) contains no other lattice point. 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 (α, β) and (γ, δ) so close to ℓ_{λ} 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 = ( \begin{matrix}γ & δ \\ α & β \end{matrix} ) .

Since

(0, 1)C = (α, β)
(1, 0)C = (γ, δ),

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.

The two lines \overline{ℓ}_{λ}, \overline{ℓ}_{μ} that are the images under C^{−1} of ℓ_{λ}, ℓ_{μ} are the expanding and contracting eigen-lines for each of the transformations ±CAC^{−1}. Choose P to be the one that preserves the orientation of \overline{ℓ}_{λ}, the choice of sign being that of λ. This means that the matrix P has |λ| as the expanding eigenvalue and either ±μ as the contracting. Furthermore, because C^{−1} maps the parallelogram onto the unit square and ℓ_{λ} passes through the parallelogram while ℓ_{μ} does not, the line \overline{ℓ}_{λ} passes through the first quadrant and the line \overline{ℓ}_{μ} 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 μ of P is positive or negative. In the second case (μ < 0), the linear map P reflects the first quadrant about the eigen-line \overline{ℓ}_{λ}, while in the first case (μ > 0) no reflection takes place. Let c denote the origin, a the lattice point (0, 1), and a′ its image under P.

Figure 8.II. Parallelogram and expanding direction

Let b be the projection of a on the line \overline{ℓ}_{λ} in the direction parallel to \overline{ℓ}_{μ} and b′ its image under P. The point b′ is also the projection of a′ on the line \overline{ℓ}_{λ}.

We deal first with the case without reflection. Let \overline{ℓ}′_{λ}, \overline{ℓ}′_{μ} be the lines through a parallel to \overline{ℓ}_{λ}, \overline{ℓ}_{μ} respectively. The notation |pq| stands for the length of the line segment with end-points p, q. On one hand, since |a′b′| = |μ|^{−1} ▪ |ab| < |ab|, the point a′ lies between the lines \overline{ℓ}′_{λ}, \overline{ℓ}_{λ}. On the other, since |cb′| = |λ| ▪ |cb| > |cb|, the point a′ lies to the left of \overline{ℓ}′_{μ}. The region bounded by these three lines, in which a′ thus lies, is contained in the first quadrant.

For the case with reflection, let c′ be the intersection of the line \overline{ℓ}_{λ} and the vertical through a′. Suppose that a′ belongs to the fourth quadrant but not the first. The point a′ being a lattice point implies that |a′c′| > 1. However, because triangle c′a′b′ is similar to cab, |a′c′| = |μ| ▪ |ac| < |ac| < 1, a contradiction.

□

Remark. By means of continued fractions we can somewhat augment the conclusion of Theorem 8.2: namely, we can conjugate so that the following two conditions to hold simultaneously.

(1) \overline{m}_{μ} < −1, Figure 8.III. Geometrical figure for proof without reflection

Figure 8.IV. Geometrical figure for proof with reflection

(2) 0 < \overline{m}_{λ} < 1,

where \overline{m}_{μ} is the slope of the contracting eigenline \overline{ℓ}_{μ} and \overline{m}_{λ} is the slope of the expanding one \overline{ℓ}_{λ} for P.

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 [a_{0}, a_{1}, …] = a_{0} + 1/(a_{1} + 1/ …) where a_{n} ∈ ℤ 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 [\overline{b_{1}, …, b_{m}}] > 1, where the overbar means infinite repetition of b_{1} through b_{m}. In [ATW] the following was proved.

Theorem 8.3. Let A ∈ GL(2, ℤ) be hyperbolic. The slope m_{λ}, being a quadratic surd, can be written m_{λ} = [a_{0}, a_{1}, …, a_{n}, \overline{b_{1}, …, b_{m}}], where m is as small as possible. If

C = ( \begin{matrix}0 & 1 \\ 1 & a_{0} \end{matrix} ) ( \begin{matrix}0 & 1 \\ 1 & a_{1} \end{matrix} ) … ( \begin{matrix}0 & 1 \\ 1 & a_{n} \end{matrix} ) ,

then CAC^{−1} = ϵP where

P = (( \begin{matrix}0 & 1 \\ 1 & b_{1} \end{matrix} ) … ( \begin{matrix}0 & 1 \\ 1 & b_{m} \end{matrix} ))^{N} ,

for some positive integer N and ϵ is the same as in Theorem 8.2. Furthermore, the slopes the eigen-lines of P satisfy \overline{m}_{λ} = [\overline{b_{1}, …, b_{m}}] > 1 and −1/\overline{m}_{μ} = [\overline{b_{m}, …, b_{1}}] > 1.

The matrix

( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) P ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} )

achieves the above two conditions in the remark.

Theorem 8.4. Let ϕ be a toral automorphism whose defining matrix is either P or −P where

P = ( \begin{matrix}p & q \\ r & s \end{matrix} )

is a hyperbolic matrix in GL(2, ℤ), with non-negative entries. Then there exists a Markov generator R^{∗} for ϕ, the members of which are of parallelograms. The associated Markov shift is given by a directed graph also specified by P : 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.

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 = ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) ,

which reflects the first quadrant about the line y = x.

Figure 8.V. Edge graph defined by P

Before proceeding in earnest, we need some notation. Dropping the bars, we now let v_{λ}, v_{μ} be the expanding and contracting eigen-vectors of P and ℓ_{λ}, ℓ_{μ} the corresponding eigenlines through the origin. We denote lines parallel to these through a point p by assigning p as a superscript. For example, ℓ_{λ}^{(0,1)} denotes the line through (0, 1) parallel to ℓ_{λ}, etc.

We define the following points as depicted in Figure 8.VI:

(8.5)

o ≡ (0, 0)
o′ ≡ (1, 0)
o′′ ≡ (1, 1)
o′′′ ≡ (0, 1)
a ≡ ℓ_{μ} ∩ ℓ_{λ}
a′ ≡ ℓ_{μ}^{(1,0)} ∩ ℓ_{λ}^{(1,0)}
a′′ ≡ ℓ_{μ}^{(1,1)} ∩ ℓ_{λ}^{(1,1)}
a′′′ ≡ ℓ_{μ}^{(0,1)} ∩ ℓ_{λ}^{(0,1)}
b ≡ ℓ_{μ} ∩ ℓ_{λ}^{(−1,0)}
b′ ≡ ℓμ^{(1,0)} ∩ ℓ_{λ} = b + (1, 0)
b′′ ≡ ℓ_{μ}^{(1,1)} ∩ ℓ_{λ}^{(0,1)} = b + (1, 1)

c ≡ ℓ_{μ} ∩ ℓ_{λ}^{(0,1)}
c′ ≡ ℓ_{μ}^{(1,0)} ∩ ℓ_{λ}^{(1,1)}
\overline{c} ≡ ℓ_{μ}^{(0,−1)} ∩ ℓ_{λ}
\overline{d} ≡ ℓ_{μ} ∩ ℓ_{λ}^{(−1,1)}
d′ ≡ ℓ_{μ}^{(1,0)} ∩ ℓ_{λ}^{(0,1)} = \overline{d} + (1, 0)
d^{∗} ≡ d′ − (0, 1).

Figure 8.VI. A remarkable fundamental region

We have drawn Figure 8.VI as if the first statement in the remark following Theorem 8.2 holds. This places the point c′ in the unit square. Since we are not using this condition, c′ 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 acd′b′ and R_{II} the interior of parallelogram c′d′b′′a′′.

The closed set \overline{R_{I}} ∪ \overline{R_{II}}, as we shall show, is a fundamental region, which we shall call the principal Markov one. As drawn in Figure 8.VI, this set is equivalent modulo ℤ^{2} to the unit square by sliding △aa′′′c one unit to the right and △d′b′′a′′ one unit down. But in general we need a slightly more elaborate proof.

First, no two points in the interior of \overline{R_{I}} ∪\overline{R_{II}} are equivalent because R_{I} ∪R_{II} is disjoint from its four neighboring unit translates which totally bound it. Second, the set of all ℤ^{2}−translates of \overline{R_{I}} ∪ \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}} ∪ \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 ±P depending whether μ is positive or negative. These amount to the four possible combinations,

(λ, μ) = (±|λ|, ±|μ|),

of signs for the eigenvalues of the matrix representing ϕ. The simplest case is when both λ and μ are positive. Things are more difficult when either is negative, especially μ. So that the proof appears less tedious, we divide that for each case into five steps.

\underline{Case I:} λ > 0, μ > 0.

Step 1. The family R = {R_{I}, R_{II}} is a Markov partition.

Our aim is to show that R satisfies the hypothesis of Theorem 7.12.

By virtue of their construction as parallelograms the members R_{I}, R_{II} of 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) ≡ ℓ_{μ}^{p} ∩ R_{i},
h_{i}(p) ≡ ℓ_{λ}^{p} ∩ 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 ϕ and ϕ^{−1} : namely,

(1)  p ∈ R_{i} ∩ ϕ^{−1}R_{j} ⇒ R_{j} ∩ ϕv_{i}(p) ⊂ v_{j}(ϕp);
(2)  p ∈ R_{i} ∩ ϕR_{j} ⇒ R_{j} ∩ ϕ^{−1}h_{i}(p) ⊂ h_{j}(ϕ^{−1}p)

for i, j = I, II.

Next we verify that the boundaries of these of members satisfy property M of Definition 7.10 which entails five items. The first of these concerns dividing ∂R_{I} and ∂R_{II} into vertical and horizontal pieces. As shown in Figure 8.VI we have

∂R_{I} = ∂_{V} R_{I} ∪ ∂_{H}R_{I},
∂R_{II} = ∂_{V} R_{II} ∪ ∂_{H}R_{II},

where

∂_{V} R_{I} ≡ ac ∪ b′d′,
∂_{H}R_{I} ≡ ab′ ∪ cd′,
∂_{V} R_{II} ≡ c′d′ ∪ a′′b′′,
∂_{H}R_{II} ≡ c′a′′ ∪ d′b′′,

each being the union of two line segments. Utilizing the boundary identifications, we have that ∂R consists of two transverse line segments intersecting at the origin: namely,

(8.6)  \begin{aligned}∂_{H}R & = \overline{c}b′ ⊂ ℓ_{λ}^{a} = ℓ_{λ}, \\ ∂_{V} R & = a\overline{d} ⊂ ℓ_{μ}. \end{aligned}

It is clear from Figure 8.VI that (2) and (3) of 7.10 are satisfied: namely,

\overline{v_{i}(p)} ∩ ∂R_{i} ⊂ ∂_{H}R_{i},
\overline{h_{i}(p)} ∩ ∂R_{i} ⊂ ∂_{V} R_{i},

From (8.6) and the property that the restrictions of P and P^{−1} respectively to the lines ℓ_{λ} and ℓ_{μ} are contractions we get

(8.7)

\overline{c}b′ ⊂ (\overline{c}b′)P
(a\overline{d})P ⊂ a\overline{d}.

We can restate (8.7) as items (4) and (5) of 7.10: namely,

ϕ∂_{V} R ⊂ ∂R_{V} ⊂ ∂R,
ϕ^{−1}∂_{H}R ⊂ ∂_{H}R ⊂ ∂R.

Thus we have established that R satisfies the hypothesis of theorem 7.12: so it is Markov partition.

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} ≠ \overline{R_{I}}^{o} and R_{II} ≠ \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 ab′ minus the end-points with the segment ac minus the end-points. However, \overline{R_{I}} is not homeomorphic to the Cartesian product of ab′ with ac, since part of the segment ab′ is in the boundary and part isn’t. Furthermore, ∂_{V} R and ∂_{H}R are connected line segments which get mapped into themselves under ϕ and ϕ^{−1} respectively. This would not be the case if 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.

The Markov partition R is not necessarily a generator. The trouble is that, while the members of R are connected, those of R^{(2)} = R ∨ ϕ^{−1}R may not be in which case nonempty sets of the form ⋂_{n=0}^{∞} \overline{⋂_{−n}^{n} ϕ^{−k}R_{s_{k}}} may consist of more than one point. To overcome this let us examine the sets R_{i} ∩ ϕ^{−1}R_{j} ∈ R ∨ ϕ^{−1}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.

Step 2. The family R^{∗} = {R_{k}^{∗} : 1 ≤ k ≤ N^{∗}} consisting of all connected components of the sets R_{i} ∩ ϕ^{−1}R_{j} ∈ R ∨ ϕ^{−1}R is Markov partition.

Once again we must show that the members of 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 λ in the v_{λ}-direction and shrunk by a factor μ in the v_{μ}-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}} ∪ \overline{R_{II}})P would be committed. While the set ϕh_{i}(p) ∩ R_{j} may consist of several horizontals, the set ϕh_{i}(p) ∩ R_{k}^{∗} is either empty or a single one. Furthermore, if ϕh_{i}(p) ∩ R_{k}^{∗} ≠ ∅ for one horizontal h_{i}(p) of R_{i}, then ϕh_{i}(p′) ∩ R_{k}^{∗} ≠ ∅ for any other horizontal h_{i}(p′) in R_{i}. Back on the torus the various non-equivalent parallelograms represent disjoint connected sets which we have labelled R_{k}^{∗}, 1 ≤ k ≤ N^{∗}. Being parallelograms, these sets are abstract rectangles.

Alignment of verticals and horizontals for these members of R^{∗} is maintained by ϕ and ϕ^{−1} for the same reason it is for members of R.

Regarding boundaries we have that

(8.8)  \begin{matrix}∂_{H}R^{(2)} = ∂_{H}R^{∗} = (c′′b′)P, \\ ∂_{V} R^{(2)} = ∂_{V} R^{∗} = ad. \end{matrix}

Thus, just as for R, we have

ϕ∂_{V} R^{∗} = (ad)P ⊂ ad = ∂R_{V}^{∗} ⊂ ∂R^{∗},
ϕ^{−1}∂_{H}R^{∗} = c′′b′ ⊂ (c′′b′)P = ∂_{H}R^{∗} ⊂ ∂R^{∗}.

The partition 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 ϕR_{i}^{∗} ∩ R_{j}^{∗} is a single connected parallelogram.

If R_{k}^{∗} is one of the parallelograms in ϕR_{i} ∩R_{j}, then the length of its v_{λ}-dimension is the same as that of R_{j} while the length of its v_{μ}-dimemsion is |μ| times that of R_{i}. Similarly, a non-empty set of the form ϕR_{i}^{∗} ∩ R_{j}^{∗} is a single connected open parallelogram, the length of its v_{λ}-dimension being the same as that of R_{j}^{∗} and the length of its v_{μ}-dimension μ times that of R_{i}^{∗}.

Likewise, a non-empty set of the form ⋂_{−n}^{n} ϕ^{−k}R_{s_{k}}^{∗} is a single connected open parallelogram, the length of its v_{λ}-dimension is |μ|^{n} times as that of R_{s_{−n}}^{∗} and the length of its v_{μ}-dimension |μ|^{n} times that of R_{s_{n}}^{∗}. From this we have

d (⋁_{−n}^{n} ϕ^{k}R^{∗}) = d(R)/|μ|^{n+1} → 0, as n → ∞.

Figure 8.VII. A nonempty parallelogram of the form ⋂_{−n}^{n} ϕ^{−k}R_{s_{k}}^{∗}

In other words, R^{∗} is a generator.

Step 4. Let #(ϕR_{i} ∩ R_{j}) denote the number of disjoint parallelograms in the intersection ϕR_{i} ∩ R_{j}.

(8.9)

#(ϕR_{i} ∩ R_{I}) ≡ number of lines x = 0, x = 1, …, traversed by (R_{i})P;
#(ϕR_{i} ∩ R_{II}) ≡ number of lines y = 1, y = 2, …, traversed by (R_{i})P,

which leads to

(8.10)

#(ϕR_{I} ∩ R_{I}) = x-coordinate of (0, 1)P  = p;
#(ϕR_{II} ∩ R_{I}) = x-coordinate of (1, 1)P − (1, 0)P = q;
#(ϕR_{I} ∩ R_{II}) = y-coordinate of (0, 1)P  = r;
#(ϕR_{II} ∩ R_{II}) = y-coordinate of (1, 1)P − (1, 0)P = s.

Figure 8.VIII. How (R_{I})P and (R_{II})P intersect various fundamental regions

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′d′)P lies within the segment ã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}} ∪ \overline{R_{II}})P is a fundamental region because ∂_{H}(RP) ⊃ ∂_{H}R.

Since P is a contraction on the line ℓ_{μ}, we have |(ab)P| < |ab|; and since the point a = (0, 0) is fixed, the point (b)P lies inside the segment ab. It then follows that the point (b′)P = (b)P+(p, q) lies inside a lattice translate of ab–that is, it lies on the line ℓ_{μ}^{(p,q)} strictly between ã ≡ (p, q) = (a′)P and b̃ ≡ (p, q) + b. The same is true for (d′)P : for otherwise (R_{I})P would straddle part of its own boundary on the line ℓ^{(p−1,q)}. Thus

(ac)P ⊂ (ad)P ⊂ ab.

and

(b′d′)P ⊂ ã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 ab on the line ℓ_{μ} and ends (as shown in the middle figure of Figure 8.VIII) with its right vertical boundary contained in the segment ãb̃ on the line ℓ_{μ}^{(p,q)}. We see that the (R_{I})P begins by striping across R_{I}. Its lower horizontal boundary lies on the line ℓ_{λ} 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 ℓ_{λ}^{(a′′′)P} = ℓ_{λ}^{(r,s)}. 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 ãb̃, and its right one in ˜ ã˜b̃ where ˜ ã ≡ (p + r, q + s) and ˜b̃ ≡ 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} ∩ (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 aa′′′ 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 aa′′′+(m, n). But one must bear in mind that the picture does not represent all cases as c′ may not be located in the principal unit square so that the line segment aa′′′ 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 intermediary we mean at (m, n) where 0 ≤ m ≤ p − 1 and 0 ≤ n ≤ 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 aa′′′ equals the number different lines x = 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′′′a′′; and the number of times this happens equals the number lines y = integer crossed by (R_{i})P, which equals q for (R_{I})P and s for (R_{II})P.

Remark. A consequence of the fact that right contracting boundary of (R_{I})P is contained in a lattice translate of ab is that ϕR_{I} ∩ R_{II} ≠ ∅ 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.

Step 5. The transition matrix associated with mapping of the Markov generator R^{∗} by ϕ coincides with matrix which specifies the automorphism–namely, P– the edge graph of which is illustrated in Figure 8.V.

From what we have established there are N^{∗} = p + q + r + s parallelograms R_{i}^{∗} in R^{∗}. We separate the subscripts into four sets:

(1)  {1, …, p}
(2)  {p + 1, …, p + q}
(3)  {p + q + 1, …, p + q + r}
(4)  {p + q + r + 1, …, p + q + r + s}.

We label the members of R^{∗} accordingly:

R_{1}^{∗} ∪ ⋯ ∪ R_{p}^{∗} = R_{I} ∩ ϕR_{I},
R_{p+1}^{∗} ∪ ⋯ ∪ R_{p+q}^{∗} = R_{II} ∩ ϕR_{I},
R_{p+q+1}^{∗} ∪ ⋯ ∪ R_{p+q+r}^{∗} = R_{I} ∩ ϕR_{II},
R_{p+q+r+1}^{∗} ∪ ⋯ ∪ R_{p+q+r+s}^{∗} = R_{II} ∩ ϕR_{II}.

As we have said before: if ϕh_{i}(p) ∩ R_{k}^{∗} ≠ ∅ for one horizontal h_{i}(p) of R_{i}, then ϕh_{i}(q) ∩ R_{k}^{∗} ≠ ∅ 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 R^{∗}. From this we get that ϕR_{k}^{∗} ∩ R_{l}^{∗} ≠ ∅, equivalently R_{k}^{∗} ∩ ϕ^{−1}R_{l}^{∗} ≠ ∅, whenever either

k ∈ (1) ∪ (3) and l ∈ (1) ∪ (2),

or

k ∈ (2) ∪ (4) and l ∈ (3) ∪ (4).

\underline{Case II:} λ > 0, μ < 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 ρv_{μ} with ρ, chosen so that

(d̄)P = a.

For example, a_{new} = a_{old} + ρv_{μ}. 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 Figure 8.IX(a). New principal Markov fundamental region, a translation of the previous with o between a and b.

regions in which the old one of Figure VI has been translated by ρv_{μ}. 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.

Step 1. The new partition R = {R_{I}, R_{II}} is Markov.

The proof of this is the same as in Step 1 of Case I except the verification of

ϕ∂_{V} R ⊂ ∂R_{V} ⊂ ∂R,
ϕ^{−1}∂_{H}R ⊂ ∂_{H}R ⊂ ∂R

is more involved and is as follows.

For this new partition, (8.6) remains valid: namely,

∂_{H}R = \overline{c}b′ ⊂ ℓ_{λ}^{a},
∂_{V} R = a\overline{d} ⊂ ℓ_{μ}.

Before there was a common fixed point on ∂_{H}R and ∂_{V} R : namely, origin = ∂_{H}R ∩ ∂_{V} R, but now the intersection ∂_{H}R ∩ ∂_{V} 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 Figure 8.IX(b). New principal Markov fundamental region, a translation of the previous with o above b.

contains a fixed point, but this is not so obvious. This will be a consequence of the following version of (8.7):

(8.11)

(\overline{c}b′)P ⊃ lattice translate of \overline{c}b′
(a\overline{d})P ⊂ a\overline{d};

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!

Recall d^{∗} = d′ − (0, 1). Now because (d̄)P = a, the point â ≡ (d^{∗})P is a lattice translate of a and the line ℓ_{λ}^{a} is mapped to the line ℓâ ; λ by P. See Figure 8.X. Let ĉ, b̂, and d̂ be the points on the line ℓâ ; λ that are lattice translates of the points c̄, b′, and d^{∗}. We must show that (c̄b′)P contains ĉb̂. Because the point (d^{∗})P lies on the line ℓâ ; λ, so do the points (c̄)P and (b′)P. Since (b)P and (c)P are contained in the segment a\overline{d} and the pair of points (b′)P and (\overline{c})P are lattice translates of neither a, b, c, nor \overline{d}, this pair lies outside the segment b̂ĉ. Since (d^{∗})P lies inside, the segment, (c̄b′)P overlaps ĉb̂.

Now we are are in a position to prove that Figure8.IX(B) cannot occur. Let ã = (p, q)+ρv_{μ}. Since (d̄)P = a, we have that ã = d′P. Let b̃ be the point equivalent Figure 8.X. Image of expanding boundary of new principal Markov fundamental region.

to b′ on the line ℓ_{μ}^{(p,q)}, upon which ã lies; and let c̃ be the lattice translate of c̄ on the line ℓ_{λ}^{(p,q)+ρv_{μ}}. The segment c̃b̃ is a lattice translate of the horizontal boundary of \overline{R_{I}} ∪ \overline{R_{II}}. If b were below o on the line ℓ_{μ}^{(0.0)}, then by virtue of the fact that μ is negative the point b′P would lie above (p, q) on this line, and hence above b̃. Since d′P = ã lies below b̃, the parallelogram R_{I}P would straddle the part of its own horizontal boundary: namely the segment c̃b̃. This would contradict the fact that R_{I}P is a subset of a fundamental region.

Step 2. The family R^{∗} = {R_{k}^{∗} : 1 ≤ k ≤ N^{∗}} consisting of all connected components of the sets R_{i} ∩ ϕ^{−1}R_{j} ∈ R ∨ ϕ^{−1}R is Markov partition.

Proof is the same as Step 2 of Case I.

Step 3. The Markov partition R^{∗} is a generator.

Proof, same as Case I, Step 3.

Step 4. Let #(ϕR_{i} ∩ R_{j}) denote the number of disjoint parallelograms in the intersection ϕR_{i} ∩ R_{j}.

#(ϕR_{i} ∩ R_{I}) ≡ number of lines x = 0, x = 1, …, traversed by (R_{i})P;
#(ϕR_{i} ∩ R_{II}) ≡ number of lines y = 1, y = 2, …, traversed by (R_{i})P,

which leads to

#(ϕR_{I} ∩ R_{I}) = x-coordinate of (0, 1)P  = p;
#(ϕR_{II} ∩ R_{I}) = x-coordinate of (1, 1)P − (1, 0)P = q;
#(ϕR_{I} ∩ R_{II}) = y-coordinate of (0, 1)P  = r;
#(ϕR_{II} ∩ R_{II}) = y-coordinate of (1, 1)P − (1, 0)P = s.

Argument similar to Case I, Step 4 but based on Figure 8.XI. There is a slight difference here. The vertical line segment aa′′′ is offset from the line x = 0, and Figure 8.XI. How the new (R_{I})P and (R_{II})P intersect various fundamental regions

a′′′a′′ does not lie on y = 1. If ρv_{μ} = (ξ, η), then

#(ϕR_{i} ∩ R_{I}) ≡ number of lines x − ξ = 0, x − ξ = 1, …, traversed by (R_{i})P;
#(ϕR_{i} ∩ R_{II}) ≡ number of lines y − η = 1, y − η = 2, …, traversed by (R_{i})P,

To get the desired result we observe that the parallelgram (R_{i})P traverses the line x − ξ = m if and only if it traverses the line x = m. Similarly the parallelogram traverses y − η = m if and only if it traverses y = m.

Step 5. The transition matrix associated with mapping of the Markov generator R^{∗} by ϕ coincides with matrix which specifies the automorphism–namely, P– the edge graph of which is illustrated in Figure 8.V.

Argument same as Case I Step 5.

\underline{Case III:} λ < 0, μ > 0. The sets R_{i} are the same as for Case I.

Step 1. The new partition R = {R_{I}, R_{II}} is Markov.

This depends on establishing (8.6): namely

\overline{c}b′ ⊂ (\overline{c}b′)P
(a\overline{d})P ⊂ a\overline{d}.

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.

Step 2. The family R^{∗} = {R_{k}^{∗} : 1 ≤ k ≤ N^{∗}} consisting of all connected components of the sets R_{i} ∩ ϕ^{−1}R_{j} ∈ R ∨ ϕ^{−1}R is Markov partition.

Proof is the same as Step 2 of Case I.

Figure 8.XII. How (R_{I})P and (R_{II})P intersect various fundamental regions for Case III.

Step 3. The Markov partition R^{∗} is a generator.

Proof, same as Case I, Step 3.

Step 4. Let #(ϕR_{i} ∩ R_{j}) denote the number of disjoint parallelograms in the intersection ϕR_{i} ∩ R_{j}.

#(ϕR_{i} ∩ R_{I}) ≡ number of lines x = 0, x = −1, …, traversed by (R_{i})P;
#(ϕR_{i} ∩ R_{II}) ≡ number of lines y = −1, y = −2, …, traversed by (R_{i})P,

which leads to

#(ϕR_{I} ∩ R_{I}) = x-coordinate of (0, 1)P  = −p;
#(ϕR_{II} ∩ R_{I}) = x-coordinate of (1, 1)P − (1, 0)P = −q;
#(ϕR_{I} ∩ R_{II}) = y-coordinate of (0, 1)P  = −r;
#(ϕR_{II} ∩ R_{II}) = y-coordinate of (1, 1)P − (1, 0)P = −s.

Argument the same as Case I, step 4 but based on Figure 8.XII.

56 SYMBOLIC DYNAMICS AND MARKOV PARTITIONS

Step 5. The transition matrix associated with mapping of the Markov generator R^{∗} by ϕ coincides with matrix which specifies the automorphism–namely, P– the edge graph of which is illustrated in Figure 8.V.

Argument same as Case I Step 5. \underline{Case IV:} λ < 0, μ < 0. The sets R_{i} are the same as in Case II– i.e., translations of the ones of Case I. Step 1. The new partition R = {R_{I}, R_{II}} is Markov. The argument is the same as in Case II, Step1 Step 2. The family R^{∗} = {R_{k}^{∗} : 1 ≤ k ≤ N^{∗}} consisting of all connected

components of the sets R_{i} ∩ ϕ^{−1}R_{j} ∈ R ∨ ϕ^{−1}R is Markov partition.

Proof same as Case I, Step 2. Step 3. The Markov partition R^{∗} is a generator. Proof, same as Case I, Step 3.

Figure 8.XIII. How (R_{I})P and (R_{II})P intersect various fundamental regions Case IV

Step 4. Let #(ϕR_{i} ∩ R_{j}) denote the number of disjoint parallelograms in the intersection ϕR_{i} ∩ R_{j}.

#(ϕR_{i} ∩ R_{I}) ≡ number of lines x = 0, x = −1, …, traversed by (R_{i})P;
#(ϕR_{i} ∩ R_{II}) ≡ number of lines y = −1, y = −2, …, traversed by (R_{i})P,

which leads to

#(ϕR_{I} ∩ R_{I}) = x-coordinate of (0, 1)P  = −p;
#(ϕR_{II} ∩ R_{I}) = x-coordinate of (1, 1)P − (1, 0)P = −q;
#(ϕR_{I} ∩ R_{II}) = y-coordinate of (0, 1)P  = −r;
#(ϕR_{II} ∩ R_{II}) = y-coordinate of (1, 1)P − (1, 0)P = −s.

Argument the same as Case II, Step 4 but based on Figure 8.XIII.

Step 5. The transition matrix associated with mapping of the Markov generator R^{∗} by ϕ coincides with matrix which specifies the automorphism–namely, P– the edge graph of which is illustrated in Figure 8.V.

Argument same as Case I Step 5.

□

Exercises.

8.1 Let (X, ϕ) be the dynamical system R = {R_{i} : i = 1, 2, 3} the Markov partition of Example 3.3. Show the partition S = {S_{i} : i = 0, 1}, where S_{0} = R_{1} ∪ R_{2} and S_{1} = R_{3}, is Markov. Hint: S^{(2)} = R. Observe that associated directed graph G is vertex labelled graph of Figure 2.II.

8.2 What is the maximum number of pre-images of π in the last example? In Theorem 8.4?

9. Epilogue. 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 “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 [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 [KV], and Praggastis [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 [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.

References

[ATW] Roy Adler, Charles Tresser, Patrick A. Worfolk, Topological conjugacy of linear endomorphisms of the 2-torus, Trans. Amer. Math. Soc. ((to appear)).

[AW] Roy L. Adler and Benjamin Weiss, Similarity of automorphisms of the torus, Memoirs American Math. Soc. 98 (1970).

[Be] K. Berg, On the conjugacy problem for K-systems (1967), University of Minnesota.

[Bo1] R. Bowen, Equilibrium States and the Ergodic Theory of Anosov Diffeomorphisms, Lecture Notes in Mathematics, Vol. 470, Springer-Verlag, Berlin, Heidelberg, New York, 1975.

[Bo2] R. Bowen, Markov partitions are not smooth, Proc. Amer. Math. Soc. 71 (1970), 130-132.

[KV] R. Kenyon and A. Vershik, Arithmetic construction of sofic partitions of hyperbolic toral automorphisms, Ecole Normale Superieure de Lyon.

[LM] D. Lind and B Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge University Press, Cambridge, New York, Melbourne, 1995.

[P1] B Praggastis, Markov partitions for hyperbolic toral automorphisms (1992), University of Washington.

[W] R. F. Williams, The ”DA” maps of Smale and structural stability, Proc. Symp. in Pure Math. 14 (1970), AMS, 329-334.