Numeration systems and Markov partitions from self similar tilings

Using self similar tilings we represent the elements of RI as digit expansions with digits in RI being operated on by powers of an expansive linear map. We construct Markov partitions for hyperbolic toral automorphisms by considering a special class of self similar tilings modulo the integer lattice. We use the digit expansions inherited from these tilings to give a symbolic representation for the toral automorphisms. FRactals and fractal tilings have captured the imaginations of a wide spectrum of disciplines. Computer generated images of fractal sets are displayed in public science centers, museums, and on the covers of scientific journals. Fractal tilings which have interesting properties are finding applications in many areas of mathematics. For example, number theorists have linked fractal tilings of JR2 with numeration systems for JR2 in complex bases [16], [8]. We will see that fractal self similar tilings of R' provide natural building blocks for numeration systems of IR'. These numeration systems generalize the 1-dimensional cases in [14],[10],[11] as well as the 2-dimensional cases mentioned above. Our motivation for studying fractal tilings comes from ergodic theory. In [2] Adler and Weiss show that topological entropy is a complete invariant for metric equivalence of continuous ergodic automorphisms of the two-dimensional torus. Their method of proof is to construct a partition of the 2-torus which satisfies certain properties. The partition is called a Markov partition. By assigning each element of the partition a symbol, it is possible to assign each point in the 2-torus a bi-infinite sequence of symbols which corresponds to the orbit of the point. The objective is to represent the continuous dynamical system as a symbolic one in such a way that periodicity and transitivity is preserved in the representation. In [4] Bowen shows that every Anosov diffeomorphism has a Markov partition. In particular every hyperbolic toral automorphism has a Markov partition. His construction uses a recursive definition which deforms rectangles in the stable and unstable directions. While existence is shown, the proof does not indicate an efficient way to actually construct the partitions. In [5] Bowen shows that in the case of the 3-torus the boundary sets of the Markov partition have fractional Hausdorff dimension. In [3] Bedford constructs examples of Markov partitions for the 3-torus and describes the sets as crinkly tin cans. In [6] Cawley generalizes Bowen's results to higher dimensional tori. Since Markov partitions have properties which resemble those of self similar tilings and the boundary sets of these partitions have fractional dimension, it is Received by the editors October 2, 1996. 1991 Mathematics Subject Classification. Primary 58F03, 34C35, 54H20. ( 1999 Arnerican Mathematical Society 3315 This content downloaded from 157.55.39.170 on Tue, 20 Sep 2016 05:07:32 UTC All use subject to http://about.jstor.org/terms 3316 BRENDA PRAGGAS'TIS natural to suggest that an explicit finite construction of Markov partitions for hyperbolic toral automorphisms may be given using fractal self similar tilings. Moreover, there is a natural way to represent points in a tiled space using a symbolic system. The representations correspond to digit expansions. The set of sequences of digits used in these expansions will in turn generate a symbolic dynamical system which is metrically similar to the continuous system defined by the corresponding toral automorphism. 1. SUBDIVIDING AND SELF SIMILAR TILINGS In this first section we review the definition and properties of self similar tilings. Much of this information may be found in [17] and [10]. We then indicate how a self similar tiling of Rn provides a numeration system for Rt. Let X be a subset of RT which is the closure of its interior. Definition. A collection T of compact subsets of X is a tiling if it satisfies the following properties. (1) The union of the sets in T is equal to X. (2) Each set in T is the closure of its interior. (3) Each compact set in X ilntersects a finite number of sets in T. (In this case we say that T is locally finite.) (4) The interiors of the sets in T are mutually disjoint. The sets in T are called tiles. Suppose G is a subgroup of RW. A tiling T of X is G -finite if there exists a finite partition {Ij}GJ of T such that if T E Tj, then TS C {T+g: 9 EG}. The collection {T}jlj is a tile type partition for T. Suppose T is a G-finite tiling of X with a tile type partition {T}jgJ. If T', T2 E Tj for some j E J, then we will say that T1 and T2 are of the same type. This implies that there exists g E G such that T' + g = T2. We say that T2 is a G-translate of T'. This does not mean that if T', T2 E T and g E G such that T1 + g = T2, then T1 and T2 are of the same type. We will see that there will often exist tile type partitions which contain elements Tij and T1j2 such that every tile in Tj, is a G-translate of every tile in 2h. It follows that there are arbitrarily many different ways to define a tile type partition for a G-finite tiling. For now, let {Tj }jGJ define a tile type partition for T. Let 93 be the set of all finite unions of tiles in T. Let 93 be the set of all bounded subsets of X. Note that q3 C 93. Definition. Let Pl; p2 E q3, then there is a finite collection of tiles {Tk}kCK such that Pl = UkeK Tk. The sets P' and p2 have the same pattern if there exists g E G such that Pl + g = UkEK Tk + g = p2 and for each k E K, Tk + g is a tile in T of the same type as Tk. In particular tiles of the same type have the same pattern. If U E X, then there is a finite union of tiles P E q3 such that U C P. If g E G, then U and U + g have the same pattern if for some P E q3 such that U C P we have that P + g E v and P + g and P have the same pattern. If V is a subset of X and U E 93, then V contains the pattern of U if for some g E G, U + g C V and U + g has the same pattern as U. Let 0 be an expansive linear map on RI such that OX = X. To be expansive means that the eigenvalues for q all have modulus greater than 1. We adapt a This content downloaded from 157.55.39.170 on Tue, 20 Sep 2016 05:07:32 UTC All use subject to http://about.jstor.org/terms NUMERATION SYSTEMS AND MARKOVKOV PARTITIONS 3317 norm for R' which reflects the expansiveness of q as in [12]. More specifically, let {A j}j=j be the eigenvalues of q ordered so that 1 0 we have that the set {P E q4: diameter(P) 0 there exists R = R(r) > 0 such that every open ball of radius R contained in X contains the pattern of Br(x) n x for all x e X. Let G be a subgroup of R' such that bG = G. Definition. A G-finite tiling T of X with tile type partition {fT}.jEJ is subdividing with expansion map 0, if for each T E i, XT is a finite union of tiles and if T and T' are tiles of the same type, then XT and XT' have the same pattern. For each T E Ti we may think of the pattern of XT as defining a subdivision rule for Tj. A quasi-periodic subdividing tiling of T of X with expansion map 0 is called a self similar tiling. Example 1. Let 0 be the expansive map on R given by multiplication by 2 Note that A is a zero of x2 x 1. Let X+ = [0,oo). We construct a Z[A finite subdividing tiling T of X+ with expansion map q. Let TA = [0, 1] and TB = [0, A 1]We will partition T into two sets TA and TB. The tiles in TA will be Z[A]-translates of TA and the tiles in TB will be Z[A]-translates of TB. We define T by inductively defining TA and TB. Let TA E TA. If x E Z[A] and TA + X E TA, then o(TA+x) = [O,A]+Ax = ([O,1]+?x)U([1,A]+Ax) = (TA+Ax)U(TB+1+Ax). Let TA + AX E TA and let TB + 1 + Ax E TB. If y E Z[A] and TB + Y E TB, then q(TB+y) = [0,A2-A]+ Ay = [0,1]+Ay = TA+AY. This content downloaded from 157.55.39.170 on Tue, 20 Sep 2016 05:07:32 UTC All use subject to http://about.jstor.org/terms 3318 BRENDA PRAGGASTIS Let TA + Ay E TA. The tiling T is a Z[A ]-finite subdividing tiling of X+ with expansion map 0 and tile type partition {TA, JB}. We can represent the subdivision rules for T in terms of a substitution map. Let A represent a tile in WA and B represent a tile in TB. Define a substitution map 0 on the words in {A, B} by letting 0(A) = AB and letting 0(B) = A. We define 0 on each finite or infinite string of symbols in {A, B} by applying it to each symbol in the string. We see that T is represented by the fixed word w = ABAABABAABAAB....