]]> 2001 American Mathematical Society Conformal Geometry and Dynamics of the American Mathematical Society Conform. Geom. Dyn. ecgd 05 08 20011218 September 20, 1999 July 2, 2001 December 18, 2001 153 153-196 44 S1088-4173-01-00055-8 10.1090/S1088-4173-01-00055-8 1088-4173 English 20F65 52C20 05B45 2000 http://www.ams.org/jourcgi/jour-getitem?pii=S1088-4173-01-00055-8 0. Introduction This paper is concerned with recursive subdivisions of planar complexes. As an introductory example, we present a finite subdivision rule in Figure fig:dodec . There are two kinds of edges and three kinds of tiles. A thin edge is subdivided into five subedges (three of these are thick and two are thin) and a thick edge is subdivided into three subedges (two of these are thick and one is thin). There are three kinds of tiles: a triangle with thin edges; a quadrilateral with a pair of opposite thin edges and a pair of opposite thick edges; and a pentagon with thick edges. Each tile is subdivided into subtiles of those three kinds, and these subdivisions restrict on the boundary arcs to the subdivisions defined for the edges. Because of this, one can recursively subdivide planar complexes made up of tiles of these three kinds. For example, Figure fig:dodecq shows the second and third subdivisions of the quadrilateral tile type. This figure was produced by Kenneth Stephenson's computer program CirclePack CP . figure ecgd55el-fig-1 The dodecahedral subdivision rule fig:dodec figure figure minipage 1pc minipage .45 scale .5 ecgd55el-fig-2a minipage minipage .45 scale .52 ecgd55el-fig-2b minipage minipage The second and third subdivisions of the quadrilateral fig:dodecq figure Our motivation for the above subdivision rule is illustrated in Figure fig:colordodec . This figure, which was drawn from an image produced by Jeffrey Weeks's computer program SnapPea , shows a right-angled dodecahedron D in the Klein model of hyperbolic 3-space. The geodesic planes through the twelve faces intersect the sphere at infinity in twelve thick (red) circles. The group G generated by the reflections in these twelve geodesic planes is a discrete subgroup of Isom ( 3) , and D is a fundamental domain for the action of G on 3 . The images of D under elements of G form a tiling T of 3 . Define combinatorial balls B(n) , n0 , recursively by B(0) D and B(n 1) star (B(n),T) for n0 . For each n , the geodesic planes through the faces of B(n) intersect the sphere at infinity in circles. The thin (blue) circles in Figure fig:colordodec are the circles at infinity corresponding to the faces of B(1) . For each n , let (n) be the tiling of the 2-sphere determined by the circles coming from faces of B(k) for kn . The tiles of (n) are triangles, quadrilaterals, and pentagons, and the tiles of (n 1) are obtained from the tiles of (n) by the above subdivision rule. figure t ecgd55el-fig-3 An -complex for the dodecahedral subdivision rule fig:colordodec figure Unlike substitution tilings, where the tiles are given as rigid geometric objects, here the complexes are essentially combinatorial. Although a finite subdivision rule is defined topologically for convenience, it can be thought of as a finite rule for subdividing planar combinatorial complexes. While the tiles do not come with prescribed shapes, since we are dealing with cell complexes the intersections of tiles is greatly restricted. A central problem is to understand when the subdivisions can be realized geometrically so that the tiles at all levels are uniformly round. Our motivation for studying these subdivision rules arises from the wish to answer the following question, which is closely related to Thurston's hyperbolization conjecture. Given a negatively curved group G whose space at infinity is the 2-sphere, does G act properly discontinuously, cocompactly, and isometrically on hyperbolic 3-space To see the connection to subdivision rules, let G be a negatively curved group whose space at infinity is the 2-sphere. Let be a locally finite Cayley graph for G , and let be a vertex of . Given a geodesic ray 0,) with (0) and a positive integer n , one can define a disk at infinity D(,n) (for example, see CS for a definition). For each positive integer n , the collection equation (n) D(,n) is a geodesic ray in with (0) equation is a finite cover of . The main theorem of the Cannon-Swenson paper CS , Theorem 2.3.1, states that G acts properly discontinuously, cocompactly, and isometrically on hyperbolic 3-space if and only if the sequence (n) n 1 of disk covers is conformal in the sense of CRMT . Furthermore, line 3.30 CS states that for every n 2 the elements of (n) can be obtained from the elements of (n-1) by a finite recursion. Finite subdivision rules model the recursive structures of sequences of disk covers arising from negatively curved groups. The above sequences of disk covers do not generally arise from finite subdivision rules mainly because pairs of distinct elements of a disk cover may have large intersection, whereas finite subdivision rules deal with tilings, in which distinct elements can only intersect in their boundaries. However, we feel that this passage to tilings is not an oversimplification. Thus we are interested here in subdivision rules for tilings of surfaces. Our starting point is a finite set of closed 2-cells, and a way of subdividing each element of into 2-cells which are in turn identified with elements of . Given a 2-dimensional CW complex X whose 2-cells are identified with elements of , we use the subdivision rule on to recursively define subdivisions n(X) for n . We then want to understand the asymptotics of the subdivisions n(X) . In particular, we want to be able to tell whether they are conformal in the sense of CRMT . In Section sec:defns we give the basic definitions of finite subdivision rules and recall the definition of conformality from CRMT . We then give some examples. In Section sec:meshto0 we give the correspondence between the combinatorial and geometric definitions of mesh approaching 0. We then prove the layer theorem, which gives a subadditivity formula for combinatorial moduli, in Section sec:layer . In Section sec:axiom0 , we prove Theorem thm:axiom0 . This theorem states that, for bounded valence finite subdivision rules whose meshes approach 0, the two axioms for conformality in CRMT can be reduced to a single axiom, Axiom 0, which is weaker than either of them. This is similar to the analogous result for negatively curved groups in Theorem 8.2 SUFFRICH , and most of the material developed in SUFFRICH for the proof of Theorem 8.2 is applicable in the present setting. In Section sec:123crit we use this reduction to prove the 1,2,3-tile criterion, Theorem thm:123 , which reduces the checking of conformality to showing that the moduli of a certain finite set of quadrilaterals are uniformly bounded from 0. This greatly simplifies the problem of proving conformality for a finite subdivision rule. Several theorems are proved in Section sec:symmetry that exploit symmetry to estimate combinatorial moduli. These are especially useful when combined with Theorem thm:123 . In particular, we prove the conformality of every bounded valence finite subdivision rule whose mesh approaches 0 with one tile type such that the subdivision of that tile type has dihedral symmetry. It is easy to construct infinitely many such finite subdivision rules. In Section sec:layerex we use layered subdivision rules to give examples of nonconformal finite subdivision rules that only satisfy part of the hypotheses of Theorem thm:123 . Finally, in Section sec:rotation we discuss finite subdivision rules that have rotational symmetry. We show how to construct infinitely many rotationally symmetric finite subdivision rules with one tile type which are conformal. Though we did not construct these examples from that point of view, they all give self-replicating tilings. We then show that in general rotational symmetry is not enough to imply conformality. We thank the referee for numerous valuable suggestions. We also thank Richard Kenyon for suggesting the present form of the definition of a finite subdivision rule. Primary definitions and examples sec:defns Finite subdivision rules We first recall two definitions about CW complexes. The star of a subset Y of a CW complex X is the CW complex star (Y,X) which is the union of all closed cells in X which meet Y . A CW complex Y is a subdivision of a CW complex X if Y X and each closed cell of Y is contained in a closed cell of X . The idea behind a finite subdivision rule is to give a finite combinatorial rule for recursively subdividing tilings. Since we are mainly interested in tilings up to cellular homeomorphisms, we think of them as being essentially combinatorial objects. At its simplest, we envision having finitely many colors, a tile p c of each color c , and a subdivision X c of each tile p c into colored tiles so that if t is a tile of X c with color c(t) , then there is a cellular homeomorphism of t to p c(t) . We want to use these subdivisions to recursively subdivide any colored 2-dimensional CW complex. A potential problem is incompatibility. If an edge e in a colored 2-dimensional CW complex Y is in the boundary of two colored tiles t 1 and t 2 , then it will have induced subdivisions from X c(t 1) and from X c(t 2) . If these subdivisions are not cellularly homeomorphic, then we will not be able to define a subdivision of Y which on each tile t is isomorphic to X c(t) . To get around this problem, we assume that we also have finitely many edge colors, an edge of each color, and a subdivision of that edge into colored edges. We then require that we have edge colorings for each tile p c and for its subdivision X c , and that the tile subdivisions coincide with the edge subdivisions on the boundary of each tile p c . Our introductory example of the dodecahedral subdivision rule has two edge colors and three tile colors. To make this precise, one could use cellular homeomorphisms from the open subtiles (and open subedges) to the original open colored tiles (and open colored edges). The compatibility requirements between the edge subdivisions and the tile subdivisions would then be requirements that certain diagrams of maps were commutative. While this is straightforward to define, the details are messy and one is burdened with having separate maps for all of the subtiles and subedges. To avoid this, we define a finite subdivision rule via a quotient CW complex that has one open 1-cell for each colored edge and one open 2-cell for each colored tile. Subdividing the quotient complex creates a subcomplex. The identification of the edges and tiles of this subcomplex with our original colored edges and tiles is made by a continuous cellular map from the subcomplex to the quotient complex which restricts to a homeomorphism on every open cell. We then dispense completely with the idea of edge and tile colors because the information they carry is determined by the map from a subtile (or a subedge) to an original tile (or an original edge). For the dodecahedral subdivision rule, the quotient complex will have a single vertex, two edges, and three tiles. The preceding discussion leads us to make the following definition. A finite subdivision rule consists of the following: enumerate (1) A finite 2-dimensional CW complex S , called the subdivision complex , with a fixed cell structure such that S is the union of its closed 2-cells. We assume that for each closed 2-cell of S there is a CW structure s on a closed 2-disk such that s has at least three vertices, the vertices and edges of s are contained in s , and the characteristic map ss S which maps onto restricts to a homeomorphism on each open cell. (2) A finite 2-dimensional CW complex (S ) which is a subdivision of S . (3) A continuous cellular map (S )S , called the subdivision map , whose restriction to every open cell is a homeomorphism. enumerate We say that is orientation preserving if there is an orientation on the union of the open 2-cells of S such that the restriction of to each open 2-cell of (S ) is orientation preserving. If is a closed 2-cell in S , then the CW complex s in condition 1 is called a tile type . The tile type s comes equipped with the characteristic map s . If is a closed 1-cell in S , then a closed 1-disk e equipped with a characteristic map ee S which maps onto is called an edge type . Suppose is a finite subdivision rule. An -complex consists of a 2-dimensional CW complex X which is the union of its closed 2-cells equipped with a continuous cellular map fXS whose restriction to each open cell is a homeomorphism. Note that the tile types and the closed tiles of S are -complexes. Suppose that is a finite subdivision rule and X is an -complex with associated map fXS . The CW structure on (S ) determines a subdivision (X) of X such that the induced map f(X)(S ) restricts to a homeomorphism on each open cell. Hence (X) is an -complex with map f(X)S . We can define n(X) , for n a nonnegative integer, recursively by 0(X) X (with map fXS ) and n(X) ( n-1 (X)) (with map nf n(X) S ) if n1 . Suppose that is a finite subdivision rule, and X and X' are -complexes with associated maps fXS and f'X'S . A cellular map hXX' is called an -map if f f'h . An -map that is a cellular homeomorphism is an -isomorphism . A cellular homeomorphism hXX' is a weak -isomorphism if, for every positive integer n , there exists a cellular homeomorphism from n(X) to n(X') which agrees with h on the vertices of X . Let and ' be finite subdivision rules with associated CW complexes S and S ' and maps (S )S and ' '(S ' )S ' . Then and ' are isomorphic if there is a cellular homeomorphism hS S ' such that ' h h . We call h an isomorphism from to ' . The last condition is fairly strong and implies that h is a change of coordinates'' between and ' . We define a weak isomorphism between two finite subdivision rules by relaxing this condition. Let and ' be finite subdivision rules with associated CW complexes S and S ' and maps (S )S and ' '(S ' )S ' . Then and ' are weakly isomorphic if there is a cellular homeomorphism hS S ' such that h is cellularly isotopic to a cellular homeomorphism gS S ' such that ' g h . We call h a weak isomorphism from to ' . We discuss the notion of weak isomorphism in this paragraph. We begin with a finite subdivision rule , and we make the following observation. If k 1S S is a cellular homeomorphism which is cellularly isotopic to the identity map, then there exists another cellular homeomorphism k 2S S cellularly isotopic to the identity map such that k 1 k 2 . (The map k 2 is even cellular on (S ) .) Now let and ' be weakly isomorphic finite subdivision rules with h and g as in the definition. We have that h ' g . It follows that g(S )'(S ' ) is a cellular homeomorphism. Furthermore h h -1 ' gh -1 , and k 1 gh -1 S ' S ' is a cellular homeomorphism which is cellularly isotopic to the identity map. Hence h 2 h -1 ' k 1 ' k 1 2 ' k 2k 1 2 ' k 3 , where k 3S ' S ' is a cellular homeomorphism which is cellularly isotopic to the identity map. Hence h 2 2 ' k 3h , and k 3hS S ' is a cellular homeomorphism which is cellularly isotopic to h . It follows that k 3h 2(S )(') 2(S ' ) is a cellular homeomorphism. By induction we see for every nonnegative integer n that n(S ) is cellularly homeomorphic to (') n(S ' ) by means of a map which is cellularly isotopic to h . For this reason it might be said that weakly isomorphic finite subdivision rules are combinatorially equivalent. Weak isomorphism is the natural equivalence relation on finite subdivision rules for dealing with combinatorial moduli. Suppose that and ' are isomorphic (respectively weakly isomorphic) finite subdivision rules, and that h is an isomorphism (respectively weak isomorphism) from to ' . Let X be an -complex, with associated map fXS . Let X' be the ' -complex with X' X and with associated map hfX'S ' . Then for every nonnegative integer n , n(X) and (') n(X') are identical (respectively cellularly homeomorphic) as CW complexes. Given a finite subdivision rule , let t 1,,t m be an enumeration of the open tiles of S . The tile recursion matrix is the mm matrix (a ij ) with entry a ij equal to the number of open tiles in (S )t j which map to t i under . Suppose is a finite subdivision rule and X is an -complex. Let i,j be nonnegative integers with i j , let u be a cell in i(X) , and let w be a cell in j(X) . Then u is a predecessor of w if w u . We say that a finite subdivision rule has bounded valence if for every finite -complex X there is an upper bound on the vertex valences of the subdivisions n(X) for every n . This condition will hold if it holds when X S or if it holds whenever X is a tile type. Given a finite subdivision rule , we say that its mesh approaches 0 if given an open cover of S there exists a positive integer n such that every tile in n(S ) is contained in one of the sets of the open cover of S . If the mesh of approaches 0 and if X is a finite -complex equipped with a metric whose topology coincides with the given topology on X , then it easily follows that given a positive real number there exists a positive integer n such that every tile in n(X) has diameter less than . Let be a bounded valence finite subdivision rule. We say that its mesh approaches 0 combinatorially if i) given a closed edge e in S , there exists a positive integer n such that e contains more than one edge in n(S ) and ii) given a tile type t of and disjoint edges e and f of t , there exists a positive integer n such that if e' and f' are edges of n(t) with e' e and f' f , then there does not exist a tile of n(t) containing both e' and f' . We will show in Section sec:meshto0 that a bounded valence finite subdivision rule has mesh approaching 0 combinatorially exactly if it is weakly isomorphic to a finite subdivision rule with meshapproaching 0. Conformality subsec:conf We review the definition of conformality from CRMT . Let X be a topological surface. A shingling of X is a locally finite cover of X by compact connected sets, which are called shingles . A weight function on a shingling is a nonzero function such that (s) 0 for all sS . A weight function can be thought of as an approximate metric on X ; it gives a way to assign lengths to curves in X and areas to subsets of X . If is a weight function on , then the length of a curve in X is L(,) ss0 (s) and the area of a subset Y of X is A(Y,) ssY0 (s) 2 . Let Y be either a ring or a quadrilateral. If Y is a quadrilateral, let two disjoint edges of Y be called the ends'' of Y . The height of Y is H(Y,) L(,) is a curve in Y joining the ends of Y and the circumference of Y is C(Y,) L(,) is a curve in Y separating the ends of Y . If is a curve in Y which joins the ends of Y , then the collection of shingles which intersect is called a fat flow . Similarly, if is a curve in Y which separates the ends of Y , then the collection of shingles which intersect is called a fat cut . The combinatorial moduli of Y are the fat flow modulus M(Y,) H(Y,) 2 A(Y,) and the fat cut modulus m(Y,) A(Y,) C(Y,) 2 . A weight function which attains the supremum in the definition of M(Y,) is called an optimal weight function if (s) 0 for every s with sY . Similarly we have optimal weight functions for m(Y,) . Optimal weight functions exist and are unique up to scaling. (See, for example, SR for a proof.) Suppose we are given a surface X , a subset A of X , and a neighborhood N of A in X . We say that a ring R surrounds A in N if RNA and one of the connected components of NR is an open disk D such that D is one of the ends of R and D contains A . When N X we simply say that R surrounds A . If xX , we say that R surrounds x in N if R surrounds x in N . Now suppose that n n 1 is a sequence of shinglings of a topological surface X . The sequence n n 1 has mesh locally approaching 0 if, given a compact subset W of X and a cover of W by open subsets of X , then there is a positive integer n such that if mn and s m with sW , then s is contained in one of the elements of . Suppose that n n 1 has mesh locally approaching 0 . Let Y be an open subsurface of X . Then for each ring or quadrilateral in Y one gets two sequences of combinatorial moduli. The sequence n n 1 is conformal ( K ) in Y if there is a real number K 1 satisfying the following conditions. description Axiom I For each ring R in Y , there exists r 0 such that m(R, n) , M(R, n) r,Kr for sufficiently large n . Axiom II Given xY , a neighborhood N of x , and an integer J , there is a ring R surrounding x in N such that m(R, n), M(R, n) J for sufficiently large n . description When X Y we say that n n 1 is conformal ( K ) or simply conformal. The combinatorial Riemann mapping theorem in CRMT states that, given a conformal sequence of shinglings of an open topological surface X , there is a quasiconformal structure on X such that the analytic moduli of rings in X are within a global multiplicative bound of the asymptotic combinatorial moduli. Suppose that n n 1 is a sequence of shinglings of a topological surface X with mesh locally approaching 0 , and let R be a ring or quadrilateral in X . Then R has nondegenerate asymptotic moduli if m(R, n)n M(R, n)n is contained in a compact subset of (0,) and has degenerate asymptotic moduli otherwise. In our setting, X will be an -complex and the sequence of shinglings will be the sequence of collections of closed tiles in successive subdivisions of X . Suppose is a finite subdivision rule and X is an -complex such that X is a surface. For each nonnegative integer n , denote by n(X) the shingling of X whose elements are the closed tiles of n(X) . The pair (X,) is conformal if the sequence of shinglings n(X) is conformal in int (X) . The finite subdivision rule is conformal if (X,) is conformal whenever X is a bounded valence -complex such that X is a surface. Suppose is a finite subdivision rule, X is an -complex contained in 2 , n is a nonnegative integer, and K is a positive real number. Following CRMT , n(X) is almost round (K) if for each tile t n(X) there are concentric circular disks C(t) and D(t) such that C(t)tD(t) , and radius (D(t)) K radius (C(t)) . The pair (X,) is almost round if there is a positive real number K such that n(X) is almost round (K) for each nonnnegative integer n . The finite subdivision rule is almost round if every tile type is -isomorphic to an -complex t 2 such that (t,) is almost round. Note that even if a finite subdivision rule is almost round, it does not follow that (X,) is almost round for every -complex X . (See Example ex:binsquare and Figure fig:funnysquare .) The relevance of almost roundness to conformality comes from Theorem 7.1 CRMT , which states that if X is a compact subset of and n is a sequence of shinglings of X such that the mesh of n goes to 0 and n is almost round (K) for some K , then n is conformal. We sometimes wish to apply 3, Theorem 7.1 to conclude that combinatorial moduli of quadrilaterals are bounded from 0. Because the definition of conformality deals with rings, not quadrilaterals, this does not quite follow, and so we include the following lemma. lemma lem:confquad Let X be an open topological surface. Let n be a sequence of shinglings of X with mesh locally approaching 0 which is conformal. Let Q be a quadrilateral in X . Then the moduli M(Q, n) are uniformly bounded from 0. lemma proof Let R be a ring in X which separates the ends of Q (see Figure fig:ringquad ). Let n be a nonnegative integer. Let be an optimal weight function on n for R . Then A(Q,) A(R,) and H(Q,) H(R,) . Hence equation M(Q, n) H(Q,) 2 A(Q,) H(R,) 2 A(R,) M(R, n). equation Because n is conformal, the moduli M(R, n) are uniformly bounded from 0, and so the moduli M(Q, n) are uniformly bounded from 0. figure ecgd55el-fig-4 A ring R separating the ends of Q fig:ringquad figure This proves Lemma lem:confquad . proof Examples sec:finsubex We now give some examples of finite subdivision rules. Since we only consider them one at a time, for convenience we will denote each example by . For each example, we give a figure which indicates how each tile type is subdivided. Edges which are distinct in S are distinguished by how they are drawn. In each example given in this section, we orient the edges of the tile types and of their subdivisions to show how edges are identified in S and to help indicate the subdivision map (S )S . However, once we verify that it is possible to orient the edges compatibly in such a figure, then the orientations only clutter the figure. Because of the symmetries in these examples, it is clear how to subdivide further without edge orientations. ex the barycentric subdivision rule ex:barycent The single tile type t is a 2-simplex, and its subdivision is shown in Figure fig:barycent . We see that the subdivision complex S is the quotient of a triangle in which the three edges are identified preserving the orientations shown in the left of Figure fig:barycent . If X is an -complex and n is a positive integer, then n(X) is the n th barycentric subdivision of X . Hence does not have bounded valence. It was shown in Section 6.3.1 SR that if X is an -complex whose underlying space is the Euclidean plane, then (X,) is not conformal. Hence is not conformal. ex figure ecgd55el-fig-5 The tile type t and its subdivision (t) for the barycentric subdivision rule fig:barycent figure ex the binary quadrilateral subdivision rule ex:binsquare In this example thesingle tile type is a Euclidean square, and the subdivision complex S is the torus obtained from the square by identifying opposite edges. The subdivision of the square is into four smaller squares as shown in Figure fig:square . This finite subdivision rule is almost round, and the dihedral symmetries of the square are weak -isomorphisms. Because of this, it follows from Theorem thm:dihconf that is conformal. ex figure ecgd55el-fig-6 The subdivision of the tile type for the binary quadrilateral subdivision rule fig:square figure An interesting example of an -complex for the binary quadrilateral subdivision rule is shown in the top left of Figure fig:funnysquare . The -complex X is a square divided into three tiles, with two of the tiles having a pair of adjacent edges in common. Figure fig:funnysquare shows the first three subdivisions of X . Even though the subdivision rule is conformal, the pair (X,) is not almost round. However, one could also consider a copy X' of this CW complex on the Riemann surface (with a singular point with cone angle and a boundary point with angle 2 ) made up out of three squares glued together as indicated. Then (X',) is almost round, and the Riemann map from this quadrilateral to a rectangle, followed by an affine map from the rectangle to the square, would show how to redefine the map XS so that (X,) is almost round. figure ecgd55el-fig-7 Subdivisions of an -complex for the binary quadrilateral subdivision rule fig:funnysquare figure ex the pentagonal subdivision rule ex:pentagon In this example, the single tile type p is a pentagon and there is a single edge type. The subdivision of the pentagon is into six smaller pentagons as shown in Figure fig:pentag . As with the previous example, the dihedral symmetries of the pentagon are weak -isomorphisms. Hence it follows from Theorem thm:dihconf that is conformal. ex figure ecgd55el-fig-8 The subdivision of the tile type for the pentagonal subdivision rule fig:pentag figure figure minipage 1pc minipage .45 scale .8 ecgd55el-fig-9a minipage minipage .45 scale .52 ecgd55el-fig-9b minipage minipage 2(p) and 3(p) fig:pentls figure When we first started studying this example before we had proved Theorem thm:dihconf , we were wondering if we could define so that the tiles of the subdivisions n(p) were almost round (K) for some constant K that did not depend on n . After learning of this example from us, Kenneth Stephenson realized that his circlepacking program, CirclePack CP , might be an efficient computational tool for figuring out how to do this. (See BS for details of this approach.) Figure fig:pentls shows circle packing figures for 2(p) and 3(p) , as computed from CirclePack. Note that although the cell complex for 3(p) is a combinatorial subdivision of the cell complex for 2(p) , it need not be a geometric subdivision of the cell complex for 2(p) , since they were drawn independently using the circle packing algorithm. What is most impressive to us about the figures is that for each tile t in 2(p) , the shape of t in 2(p) is very close to the shape of (t) in 3(p) . This persists with further subdivisions, and is a strong indicator of conformality, since it suggests the sequence of subdivisions will be almost round. This example has been extensively studied by Bowers and Stephenson in BS . In this paragraph we introduce a barycenter trick''. Suppose we are given the following information, which is essentially what is contained in Figure fig:dodec if we delete the edge orientations. We have finitely many edge types with distinct labels. For each edge type we have a subdivision whose edges are labeled by the edge type labels. We have finitely many tile types with distinct labels whose edges are labeled with edge type labels. For each tile type we have a subdivision whose edges and tiles are labeled in a way which is compatible with the labeling of the edge type subdivisions and with the labeling of the tile types. We furthermore assume that the labeled subdivision of every edge type is invariant under the operation of interchanging the vertices of the edge type; in other words, the labels of the subdivision of every edge type are palindromic. At this point we do not quite have a finite subdivision rule. The barycenter trick produces a finite subdivision rule. The barycenter trick proceeds as follows. We orient every edge type arbitrarily. We insert a barycenter in every edge of the subdivision of every edge type. The subdivision of every edge type now has an even number of edges. We delete the edges in the second half. We label the remaining edges with the labels of the original edges which contain them, and we orient the remaining edges toward the barycenters which they contain. We likewise insert a barycenter in every edge of every tile type and in every edge of the subdivision of every tile type, labeling the new edges as before and orienting them toward the barycenters which they contain. The result is a compatible orientation of all of the new edges, allowing us to define a finite subdivision rule. Although the barycenter trick changes every tile type and its subdivision, the change is to only add a barycenter to every edge. We close this section with a simple example to illustrate somewhat the constraints and the choices in constructing a finite subdivision rule. In Figure fig:tryfsr1 we show a subdivision of a triangle ABC into three subtriangles. We want to construct a finite subdivision rule so that ABC is the single tile type and (ABC) is the subdivision of ABC shown in Figure fig:tryfsr1 . We first consider the possible edge types. figure ecgd55el-fig-10 The subdivision of the tile type fig:tryfsr1 figure Since each of the edges BC and AC is subdivided into two edges and AB is not properly subdivided, AB cannot have the same edge type as BC or AC . We first investigate the possibilities for having exactly two edge types. First suppose that the directed edges BC and AC have the same type. Then their subdivisions must be the same, so the directed edges DC and EC must have the same type (see Figure fig:tryfsr2 ). But then the directed edges DC , EC , EA , DA , and BA all must have the same type. This is impossible, since it implies that EA and DB have different types. Now suppose that the the directed edges AC and CB have the same edge type. Then AE and CD have the same type, and EC and DB have the same type. One of the directed edges in the boundary of triangle EDC has the same type as AB . There are six choices, and it is easy to see that each is impossible. Hence we cannot have only two edge types. figure ecgd55el-fig-11 Checking one possible choice with two edge types fig:tryfsr2 figure figure scale .80 ecgd55el-fig-12 The six possibilities with three edge types fig:tryfsr3 figure figure h scale .95 ecgd55el-fig-13 2(ABC) for each of the six possibilities fig:tryfsr4 figure So the only possibility for having a finite subdivision rule with a single tile type which is subdivided as in Figure fig:tryfsr1 is for all three of the edges of ABC to have different types. There are six possibilities for the edge type of the directed edge AB in (ABC) , and each can be realized by a finite subdivision rule. The six possible subdivisions of the tile type are shown in Figure fig:tryfsr3 , and Figure fig:tryfsr4 shows 2(ABC) (without edge labels and orientations) for the six different choices. Three of the six finite subdivision rules do not have bounded valence, and two of the six do not have mesh approaching 0 combinatorially. Mesh approaching 0 sec:meshto0 In this section we prove that a bounded valence finite subdivision rule has mesh approaching 0 combinatorially exactly if it is weakly isomorphic to a finite subdivision rule whose mesh approaches 0. This is convenient because we usually want to apply the geometric definition of mesh approaching 0 and the combinatorial definition is easier to prove. We begin with two lemmas. lem thm:lemma1 Let be a bounded valence finite subdivision rule whose mesh approaches 0 combinatorially. Let t be a tile type of . enumerate (1) Let u and v be distinct vertices of t . Then there exists a positive integer n such that no tile of n(t) contains both u and v . (2) Let v be a vertex of t and let e be an edge of t not containing v . Then there exists a positive integer n such that no tile of n(t) contains both v and an edge contained in e . enumerate lem proof To prove statement (1) of Lemma thm:lemma1 , let u and v be disjoint vertices of t . Because has bounded valence, there exists a positive integer n such that the valences of u and v in n(t) are maximal with respect to all subdivisions of t . Because every edge type of eventually subdivides properly, we furthermore assume without loss of generality that every edge of n(t) which contains u is disjoint from every edge of n(t) which contains v . Let e be an edge of n(t) containing u , and let f be an edge of n(t) containing v . Suppose that there is a tile s of n(t) containing both e and f . Since the mesh of approaches 0 combinatorially, there exists a subdivision of s for which there does not exist a tile containing both an edge in e and an edge in f . It follows that n may be chosen so large that no tile of n(t) contains an edge containing u and an edge containing v . This proves statement (1). Statement (2) can be proved similarly and so the proof of Lemma thm:lemma1 is complete. proof lem lem:lemma2 Let be a bounded valence finite subdivision rule whose mesh approaches 0 combinatorially. Let X be an -complex which is homeomorphic to a closed disk. Let e 1,,e k and f 1,,f k be disjoint edges in the boundary of X such that if i,j 1,,k with i j , then e i and f i do not separate e j and f j in X . Let p 1,,p k be points in e 1,,e k , and let q 1,,q k be points in f 1,,f k . Then there exists a subdivision n(X) of X and arcs 1,, k in X such that if i 1,,k , then i joins p i and q i and every tile of n(X) which meets i is disjoint from j with j 1,,k and j i . lem proof The assumptions imply that X(e 1 f 1) has two connected components. Let a and b denote the closures of these connected components. Let a' be a connected union of edges in the interior of a and let b' be a connected union of edges in the interior of b such that a'b' contains e i and f i for i 2,,k . Using the fact that the mesh of approaches 0 combinatorially and Lemma thm:lemma1 , it is easy to see that there exists a positive integer n such that no tile of n(X) meets both a and b and no tile of n(X) meets both a'b' and e 1f 1 . Similarly, we may increase n so that star 2(a, n(X)) is disjoint from star 2(b, n(X)) and star 2(a'b', n(X)) is disjoint from star 2(e 1f 1, n(X)) . It follows that there exists an arc 1 in X which separates star 2(a, n(X)) and star 2(b, n(X)) . Hence 1 joins e 1 and f 1 and 1 is disjoint from star 2(ab, n(X)) . We now modify 1 within star (e 1f 1, n(X)) so that 1 joins p 1 and q 1 and 1 is disjoint from star 2(a'b', n(X)) . It easily follows that if a' , then there exists an -subcomplex Y of n(X) which contains a' , is homeomorphic to a closed disk, and is disjoint from star ( 1, n(X)) . Likewise if b' , then there exists an -subcomplex Z of n(X) which contains b' , is homeomorphic to a closed disk, and is disjoint from star ( 1, n(X)) . It easily follows that we may inductively construct arcs 1,, k which have the properties stated in Lemma lem:lemma2 . This proves Lemma lem:lemma2 . proof thm thm:theorem3 thm:meshto0 Let be a bounded valence finite subdivision rule. Then the mesh of approaches 0 combinatorially if and only if is weakly isomorphic to a finite subdivision rule whose mesh approaches 0. thm proof It is clear that if is weakly isomorphic to a finite subdivision rule whose mesh approaches 0, then the mesh of approaches 0 combinatorially. To prove the converse, let be a bounded valence finite subdivision rule whose mesh approaches 0 combinatorially. Let t be a tile type of with characteristic map ttS . We identify t with a convex polygon in 2 . We will prove for every nonnegative integer n that there exists a cellular subdivision n(t) of t such that n 1 (t) is a subdivision of n(t) , n(t) is cellularly homeomorphic to n(t) , the edges of n(t) are piecewise linear, and the diameters of the tiles of n(t) approach 0 as n goes to . We define 0(t) to have just one tile, t . We now suppose that n(t) is defined for some nonnegative integer n , and we inductively define n 1 (t) and probably even some finer subdivisions of n(t) . Let be a positive real number. Let L be a union of a finite family of parallel lines in 2 such that L contains no vertex of n(t) , every point of t is within 2 of L , and if s' is a tile of n(t) which meets L , then L s' is a disjoint union of line segments whose interiors are both nonempty and lie in the interior of s' . Let s' be a tile of n(t) which meets L . Then Ls' is a disjoint union of line segments L 1,,L k whose interiors are both nonempty and lie in the interior of s' . Using the fact that the edge types of eventually subdivide properly, we now construct finitely many more subdivisions n 1 (t),, n l (t) if necessary, which are cellularly homeomorphic to n 1 (t),, n l (t) and whose edges are piecewise linear such that L i has endpoints p' i and q' i in interiors of edges e' i and f' i of n l (t) for i 1,,k and e' 1,,e' k , f' 1,,f' k are disjoint. We fix a cellular homeomorphism f t,n n(t) n(t) with f t,n (v) v for each vertex v of t , which gives us a correspondence between the cells of n(t) and n(t) . Let s be the tile in n(t) corresponding to s' . Let e 1,,e k , f 1,,f k be the edges of l(s) corresponding to e' 1,,e' k , f' 1,,f' k , and let p 1,,p k , q 1,,q k be points in the interiors of e 1,,e k , f 1,,f k . We next apply Lemma lem:lemma2 to the -complex l(s) and the points p 1,,p k , q 1,,q k and edges e 1,,e k , f 1,,f k of l(s) . The result is a subdivision l m (s) of l(s) and arcs 1,, k in s such that if i 1,,k , then i joins p i and q i and every tile of l m (s) which meets i is disjoint from j with j 1,,k and j i . Maintaining the properties of the previous sentence, we modify i for i 1,,k so that the intersection of i with every tile of l m (s) is an arc such that only its endpoints lie in the boundary of that tile. We choose l and m so that the previous sentence holds for every tile s' of n(t) which meets L . It follows that it is possible to modify n 1 (t),, n l (t) in the interiors of the tiles of n(t) if necessary and it is possible to construct subdivisions n l 1 (t) , , n l m (t) which are cellularly homeomorphic to n l 1 (t),, n l m (t) such that the edges of n l m (t) are piecewise linear, and every tile of n l m (t) lies in the -neighborhood of one of the lines of L . We now choose a sequence of such unions L of families of lines with successively smaller values of approaching 0 so that our lines form rectangular grids with successively smaller meshes. It follows that for every tile type t of and every nonnegative integer n there exists a cellular subdivision n(t) and a cellular homeomorphism f t,n n(t) n(t) such that n 1 (t) is a subdivision of n(t) , f t,n (v) v for every vertex v of t , and the diameters of the tiles of n(t) approach 0 as n goes to . We now define the finite subdivision rule . Let t 1,,t p be the tile types of , with associated characteristic maps t 1 t 1 S , , t p t p S . The tile types of will be t 1,,t p . We will denote the characteristic maps for by t 1 't 1 S , , t p 't p S . We will define the restrictions of t 1 ',, t p ' to t 1,,t p as maps to the 1-skeleton of S , and we will define S to be the quotient space of the disjoint union of t 1,,t p by the equivalence relation induced by these maps. Hence the 1-skeleton of S will equal the 1-skeleton of S . In this paragraph we define the restrictions of t 1 ',, t p ' to t 1,,t p . We define t 1 ',, t p ' on the vertices of t 1,,t p by t i '(v) t i (v) if i 1,,p and v is a vertex of t i . We next define t 1 ',, t p ' on the edges of t 1,,t p . Let e be an edge in S , and let e 1 be an edge in a tile type t i with t i (e 1) e . We define t i ' on e 1 by t i ' e 1 t i e 1 . Now suppose that e 2e 1 is an edge in a tile type t j with t j (e 2) e . There is a homeomorphism e 2 e 1 e 2e 1 such that t j e 2 t i e 1 e 2 e 1 . Let xe 2 . Since the diameters of the tiles of n(t j) go to 0 as n , x n star (x, n(t j)) . For each n , the image of star (x, n(t j))e 2 under f t i,n -1 e 2 e 1 f t j,n is a star in n(t i)e 1 . That is, star (x, n(t j))e 2 corresponds to a star in n(t i)e 1 via the correspondences of n(t j)e 2 to n(t j)e 2 , n(t j)e 2 to n(t i)e 1 (which is by way of n(S )e ), and n(t i)e 1 to n(t i)e 1 . Since the diameters of the tiles of n(t i) go to 0 as n , the intersection of these stars is a point ye 1 . We define t j '(x) t i '(y) . We define the restrictions of t 1 ',, t p ' to t 1,, t p by repeating this construction. This completes the construction of S . For each tile type t of S , we have already defined a subdivision (t) of t . These subdivisions induce a subdivision (S ) of S . We now define (S )S . Let x(S ) . Let i 1,,p such that x t i '(t i) , let yt i with t i '(y) x , and let s 1 be the open cell of (t i) with ys 1 . Let s 2 f t i,1 (s 1) (t i) , let s 3 t i (s 2) (S ) , and let s 4 (s 3) S . Let j 1,,p with s 4 t j (t j) , let s 5 be an open cell in t j such that t j s 5 maps s 5 homeomorphically onto s 4 , and let s 6 f t j,1 -1 (s 5) . For each positive integer n , the image of star (y, n(t i))s 1 under f t j,n-1 -1 ( t j s 5 ) -1 t i f t i,n is the intersection of s 6 with a star in n-1 (t j) . As n , the intersections of these sets is a point y' s 6 . We define (x) t j '(y') . One can check that is well defined and that is a finite subdivision rule. To complete the proof, it remains to show that and are weakly isomorphic. To do this, it suffices to find cellularly isotopic cellular homeomorphisms h,gS S such that h g . It is a straightforward matter to see that S and S are cellularly homeomorphic. We take hS S to be such a cellular homeomorphism. Furthermore, we may and do assume that if s is an open cell of t i with i 1,,p , then h( t i '(s)) t i (s) . We next define g . Let s be an open cell in (S ) . Let i 1,, p such that s t i '(t i) , and let s 1 be the open cell in (t i) with s t i '(s 1) . Let s 2 f t i,1 (s 1) (t i) , and let s 3 t i (s 2)(S ) . Note that h( (s)) (s 3) . We define g on s by g s s 3 -1 (h ) s . One can check that g is well defined, g is a cellular homeomorphism, and g and h give a weak isomorphism between and . This proves Theorem thm:theorem3 . proof The layer theorem sec:layer In preparation for the proof of Theorem thm:axiom0 , we prove a subadditivity formula for combinatorial moduli called the layer theorem. A special case of this for combinatorial moduli of rings was given in Theorem 1.7 SUFFRICH . The proof given there generalizes to this more general layer theorem. Since the proof is short, we reproduce it here. thm layer theorem thm:layer Let X be a quadrilateral or ring. If X is a ring, then let X 1,,X n be rings contained in X which separate the ends of X . If X is a quadrilateral, then let X 1,,X n be quadrilaterals contained in X which separate the ends of X and whose left and right sides are contained in the left and right sides of X . Let be a finite shingling of X which contains disjoint subsets 1,, n such that i is a shingling of X i for i 1,,n . Then M(X,) i 1 nM(X i, i) . thm proof For each i 1,,n , let i be an optimal weight function for the fat flow modulus M(X i, i) . Define a weight function on by (s) 0 if s i for all i 1,,n and (s) H(X i, i) A(X i, i) i(s) if s i . Then equation H(X,) i 1 n H(X i, i) A(X i, i) H(X i, i) i 1 n M(X i, i). equation Similarly equation A(X,) i 1 n ( H(X i, i) A(X i, i) ) 2 A(X i, i) i 1 n M(X i, i). equation Thus equation M(X,) M(X,) H 2(X,) A(X,) i 1 nM(X i, i) i 1 nM(X i, i) . equation This proves Theorem thm:layer . proof cor cor:tolayer We return to the setting of Axiom I and Axiom II in Subsection subsec:conf . Let L be a positive real number. If the sequence of shinglings i i 1 has bounded valence, then Axiom II can be weakened to the following statement. Given a point x Y and a neighborhood N of x there is a ring R surrounding x in N such that m(R, i) L for sufficiently large i . cor rmk The main point is that here L is fixed but the integer J in Axiom II may be arbitrarily large. rmk proof We must verify Axiom II, which states that given a point x Y , a neighborhood N of x and an integer J , there is a ring R surrounding x in N such that for sufficiently large i the combinatorial moduli of R are all greater than J . According to Corollary 1.4 SUFFRICH we have m(R, i) M(R, i) for every ring R contained in X . So the inequality satisfied by the fat cut modulus m(R, i) in the statement of Corollary cor:tolayer is also satisfied by the fat flow modulus M(R, i) . To obtain Axiom II, apply this modification of the form of Axiom II in the corollary I times, where I J L , to successively smaller neighborhoods of x to obtain I disjoint rings with fat flow moduli greater than L surrounding x each of which is surrounded by the previous ring. Theorem thm:layer implies that every ring in N surrounding x and containing these I rings has fat flow modulus at least J relative to all shinglings i with i sufficiently large. The bounded valence theorem Theorem 1.6 SUFFRICH now yields a corresponding estimate for fat cut moduli. This proves Corollary cor:tolayer . proof Axiom 0 implies conformality sec:axiom0 Theorem thm:axiom0 shows that, for bounded valence finite subdivision rules, Axiom I and Axiom II are implied by the following axiom, which is implied by either of them. Theorem thm:axiom0 is similar to Theorem 8.2 SUFFRICH , and the proof relies heavily on SUFFRICH . (Historically, Theorem thm:axiom0 was proved first and the argument was then generalized to prove Theorem 8.2 SUFFRICH .) Suppose we are given a finite subdivision rule , an -complex X which is a surface, and an open subsurface Y of X . description Axiom 0 Given xY and a neighborhood N of x , there is a ring R surrounding x in N such that the moduli m(R, i(X)) are uniformly boundedfrom 0. description We use the following lemma in the proof of Theorem thm:axiom0 . lem lemma:foraxiom0 Let be a finite subdivision rule and let Z be an -complex which is a surface. Let Y be an -complex which is a connected surface, and let 1, 2YZ be -maps which are injective on int (Y) . If 1(t) 2(t) for some tile t of Y , then 1 2 . lem proof Let t be a tile of Y such that 1(t) 2(t) . It follows easily from the definition of -map that there exists at most one -map from one tile to another. Hence 1 t 2 t . It is likewise easy to see that 1 and 2 agree on every point of every tile in Y which has an edge in common with t . Lemma lemma:foraxiom0 now follows from the connectivity of Y . proof thm Axiom 0 implies conformality thm:axiom0 Let be a bounded valence finite subdivision rule whose mesh approaches 0. Let X be a bounded valence -complex which is a surface. Assume that the sequence i(X) satisfies Axiom 0 in the interior of X . Then the sequence i(X) is conformal in the interior of X . thm proof To begin the proof of Theorem thm:axiom0 we construct a finite set of -complexes, called neighborhood models, which model stars of tiles of the complexes i(X) . A neighborhood model is a finite -complex N with a distinguished tile t such that there exists a nonnegative integer i , a tile s in the interior of i(X) , and an -isomorphism N star (s, i(X)) i(X) such that (t) s . We construct neighborhood models so that for every nonnegative integer i and every tile s in the interior of i(X) we have an -map as in the previous sentence, but if N and N' are neighborhood models with corresponding distinguished tiles t and t' and -maps , ' with (t) '(t') , then N N' and hence t t' and so ' by Lemma lemma:foraxiom0 . So for every nonnegative integer i and every tile s in the interior of i(X) we have a unique neighborhood model N and a unique corresponding -map N star (s, i(X)) . Because and X have bounded valence, the set of neighborhood models is finite. In this paragraph we transfer the assumptions on X to neighborhood models. Let N be a neighborhood model with distinguished tile t . By definition there exists an injective -map from N to i(X) for some nonnegative integer i which takes t to the interior of X . Using the compactness of t , it follows that there exist finitely many rings R in N such that every point in t is surrounded by one of these rings and the moduli m(R, i(N)) are uniformly bounded from 0 for every such ring R . We fix these rings and call them the distinguished rings of N . In this paragraph we use Corollary cor:tolayer to prove that Axiom II holds for every point in the interior of X relative to the sequence i(X) . Let i be a nonnegative integer. For every tile t of i(X) which is contained in the interior of X there exists a unique corresponding neighborhood model N . We have constructed finitely many distinguished rings in N . By identifying star (t, i(X)) with N for every such tile t , we obtain a collection i of rings in X such that i) every point contained in a tile t of i(X) with t int (X) is surrounded by one of the rings in i and ii) there exists a positive real number L which is independent of i such that m(R, j(X)) L for every R i and every integer j i . Now let x int (X) , and let U be a neighborhood of x . Because the mesh of approaches 0, it is possible to choose i so large that x is contained in a tile t of i(X) such that star (t, i(X)) U . It follows that the hypotheses of Corollary cor:tolayer are satisfied. Thus Corollary cor:tolayer shows that Axiom II holds for every point in the interior of X relative to the sequence i(X) . Having verified Axiom II, we turn to Axiom I. We will use the sufficiently rich theorem Theorem 7.1 SUFFRICH to verify Axiom I. This leads us to buffered rings. As a first step toward constructing models for buffered rings, in this paragraph we construct models for outer boundary rings in the neighborhood models. For this we essentially repeat the choice of distinguished rings in the neighborhood models except that where before we chose finitely many rings R in the interior of a neighborhood model N so that the moduli m(R, i(N)) are uniformly bounded from 0, we now require that m(R, i(N)) 18e 2K(2) for every sufficiently large positive integer i , where K(2) is the constant occurring in the quadratic area estimate Theorem 4.2.1 CRMT . We call such rings outer boundary ring models . We assume that if N is a neighborhood model with distinguished tile t , then every outer boundary ring model of N surrounds at least one point of t . Let N be a neighborhood model with distinguished tile t . We have chosen finitely many outer boundary ring models in N such that every point of t is surrounded by at least one outer boundary ring model, and every outer boundary ring model surrounds at least one point of t . It easily follows that to every outer boundary ring model R in N we can associate an open disk contained in t that is surrounded by R such that the open disks associated to distinct outer boundary ring models are disjoint. This extends to the following property. Suppose that N and N' are neighborhood models, that R and R' are outer boundary ring models of N and N' , respectively, and that D and D' are the open disks associated to (N,R) and (N',R') , respectively. Suppose that i is a nonnegative integer and that N i(X) and 'N' i(X) are injective -maps. Then either N N' , R R' , and ' or (D) '(D') . In this paragraph we construct buffered ring models in the neighborhood models. Let N be a neighborhood model, and let R be an outer boundary ring model of N . Let D be the open disk associated to the pair (N , R) in the previous paragraph. Recall that R was chosen so that m(R, i(N)) 18e 2K(2) for every sufficiently large positive integer i . Using Axiom II we now choose a ring R' contained in D such that m(R', i(N)) 18e 2K(2) for every sufficiently large positive integer i . Let R'' be the ring in N which contains R and R' and whose boundary is contained in RR' . The bounded valence theorem, Theorem 6.2.4 SR or Theorem 1.6 SUFFRICH , and the bounds on moduli given by the separation theorem in Theorem 4.2 SUFFRICH imply that there exists a positive real number L such that M(R'', i(N)) L forevery sufficiently large positive integer i . It follows that the ring between R and R' isa buffered ring (L) , and we call this ring a buffered ring model . Because there are only finitely many pairs (N,R) , we may assume that L is independent of (N,R) . In this paragraph we complete the proof of Theorem thm:axiom0 . Let Y be an open subsurface of X whose closure is compact and is contained in the interior of X . We choose a metric on X whose topology coincides with the given topology on X . Let be a positive real number. Because the mesh of approaches 0, there exists a positive integer i such that the star of every tile of i(X) which meets Y is in the interior of X and has diameter less than . Fix such a positive integer i . Let s be a tile of i(X) which meets Y . Let N be the neighborhood model with distinguished tile t , and let N star (s, i(X)) i(X) be the -isomorphism such that (t) s . It is clear that the image under of every buffered ring model in N is a buffered ring (L) in X . It easily follows that the set of all such buffered rings in X as s varies over the tiles in i(X) which meet Y yield a buffered ring cover (L) of Y with spanning ring mesh at most having bounded valence with respect to a parameter which is independent of and Y . The sufficiently rich theorem Theorem 7.1 SUFFRICH now implies that the sequence i(X) is conformal (M) in Y , where M is a positive real number which is independent of Y . The sequence i(X) is therefore conformal in the interior of X . This proves Theorem thm:axiom0 . proof The 1,2,3-tile criterion sec:123crit We now use Theorem thm:axiom0 to prove Theorem thm:123 , which shows that to check whether or not a bounded valence finite subdivision rule is conformal it suffices to check that the moduli of a finite number of very special quadrilaterals are uniformly bounded from 0. We begin by defining these very special quadrilaterals, which we call test quadrilaterals. Let be a finite subdivision rule. A test quadrilateral for is an -complex Q which is a quadrilateral of one of the following three types (see Figure fig:testquad ). There are two Type II test quadrilaterals in Figure fig:testquad to indicate that the top and bottom may or may not belong to a single tile. Type I : The quadrilateral Q consists of one tile, and each of the ends of Q consists of one edge. Type II : The quadrilateral Q consists of two tiles whose intersection consists of one edge f , and each of the ends of Q consists of one edge which meets f . We call f the interior edge of Q . Type III : The quadrilateral Q consists of three tiles t 1 , t 2 , and t 3 , where t 2 is a triangle with edges f 1 , f 2 , and f 3 . The intersection of t 1 and t 2 is f 1 , and the intersection of t 2 and t 3 is f 3 . The intersection of t 1 and t 3 is a vertex v . The top of Q consists of an edge containing v , and the bottom of Q is f 2 . We call f 1 and f 3 the interior edges of Q . We say that satisfies the 1-tile criterion (resp. 2-tile criterion , resp. 3-tile criterion ) if the moduli M(Q, i(Q)) are uniformly bounded from 0 for every test quadrilateral of Type I (resp. Type II, resp. Type III) for . thm the 1,2,3-tile criterion thm:123 Let be a bounded valence finite subdivision rule whose mesh approaches 0. Suppose that the moduli M(Q, i(Q)) are uniformly bounded from 0 for every test quadrilateral Q for . Then is conformal. thm proof Let X be a bounded valence -complex which is a surface. According to Theorem thm:axiom0 , it suffices to prove the following. Given a point x in int (X) and a neighborhood N of x in X , there exists a ring R surrounding x in N such that the moduli m(R, i(X)) are uniformly bounded from 0. So let x be a point in int (X) , and let N be a neighborhood of x in X . Let R be a ring in N surrounding x . We prove that the moduli m(R, i(X)) are uniformly bounded from 0. figure ecgd55el-fig-14 The three types of test quadrilaterals fig:testquad figure In this paragraph we choose a sufficiently large positive integer i and construct a special -subcomplex S of i(X) . Let be a simple closed curve in the interior of R separating the ends of R . Because the mesh of approaches 0, star (, i(X)) is contained in R and the union of three tiles of i(X) does not separate the ends of R for every sufficiently large positive integer i . We suppose that i is this large and fix it for the rest of the proof of Theorem thm:123 . We modify slightly if necessary so that not only is star (, i(X)) contained in R but also contains no vertex of i(X) . Now the argument in the long paragraph between lines 7.13 and 7.14 of SUFFRICH shows that there exist distinct tiles s 1,,s n in i(X) which meet such that i) s ks k 1 contains an edge f k for every integer k taken modulo n , ii) s k contains a path k whose interior is contained in the interior of s k joining f k-1 and f k for every integer k taken modulo n , and iii) the cyclic concatenation of 1,, n is a closed curve separating the ends of R . Let S be the -subcomplex of i(X) which is the union of s 1,,s n (see Figure fig:complexs ). Note that S need not be a ring. We partition the edges of S into three disjoint sets as follows. We call f 1,,f n vertical edges of S . The union of the remaining edges of S decomposes into two connected components, which naturally correspond to the top and bottom of R . We call the edges in the connected component corresponding to the top of R top edges of S . We call the edges in the other connected component bottom edges of S . figure ecgd55el-fig-15 The -complex S fig:complexs figure In this paragraph we define the notion of test quadrilateral image in S . A test quadrilateral image in S is an ordered pair (Q,E) , where Q is an -subcomplex of S and E is a set of two distinct edges of Q satisfying the following condition. There exists a test quadrilateral Q' with set of ends E' and an -map Q'Q such that the restriction to the interior of Q' is a homeomorphism with (E') E and the image under of every interior edge of Q' is a vertical edge of S . Since the union of three tiles of i(X) does not separate the ends of R , every test quadrilateral image (Q,E) in S determines a corresponding test quadrilateral Q' and map Q'Q up to -isomorphism. Let j be a nonnegative integer, which we fix for the rest of the proof of Theorem thm:123 . In this paragraph we define a weight function j on i j (X) . Let (Q,E) be a test quadrilateral image in S , and choose a corresponding test quadrilateral Q' and -map Q'Q . The fat flow optimal weight function on j(Q') with area 1 induces a weight function on j(Q) . We extend this weight function on j(Q) to a weight function ,j on i j (X) by defining the weight of every tile in i j (X) which is not in j(Q) to be 0. Since there are only finitely many test quadrilateral images in S , there are only finitely many such weight functions ,j , and we define j to be the sum of the ,j 's. A simpler version of the argument used to construct shows that every fat flow of R for the complex i j (X) has a fat subflow with an underlying flow curve of the following form. The flow curve is the concatenation of finitely many subcurves, each of whose interior lies in the interior of a tile of i(X) and whose endpoints lie in the interiors of edges of that tile with the possible exception that the endpoints of might lie in interiors of tiles of i(X) . Furthermore, successive subcurves lie in different tiles of i(X) . To compute the fat height of R relative to any weight function on i j (X) , we need consider only such flow curves. For the rest of the proof of Theorem thm:123 we assume that is such a flow curve of R for i j (X) beginning at the bottom of R and ending at the top of R . Note that by the triangle inequality the area of R relative to j is bounded above by the square of the number of test quadrilateral images in S . This gives an upper bound on the area of R relative to j which is independent of j . Using Theorem 1.6 SUFFRICH , the bounded valence theorem, it easily follows that to prove Theorem thm:123 it suffices to prove that there exists a positive real number H which is independent of j and such that L j() H , where L j() is the j -length of . To prove that there is such an H , we introduce the notion of joining the ends of a test quadrilateral image. Suppose given a test quadrilateral image (Q,E) in S , corresponding test quadrilateral Q' , and -map Q'Q . If a curve in R contains the image under of a flow curve in Q' , then we say that joins the ends of a test quadrilateral image . Suppose that joins the ends of a test quadrilateral image (Q,E) with test quadrilateral Q' as above. Since L j() is at least the ,j -length of , this implies that L j() is at least the square root of the fat flow modulus of Q' relative to the complex j(Q') . By hypothesis there is a uniform lower bound on all such moduli. This proves that L j() is at least the square root of this uniform lower bound if joins the ends of a test quadrilateral image. Thus to prove Theorem thm:123 , it suffices to prove that joins the ends of a test quadrilateral image. In this paragraph we construct a graph G from S . We begin by choosing a barycenter for every tile and edge of S . Let t be a tile of S . The barycenter of t is a vertex of G . If t contains any bottom edges, then choose one. The barycenter of this bottom edge is a vertex of G . It and the barycenter of t are joined by an edge. Likewise if t contains any top edges, then choose one. The barycenter of this top edge is a vertex of G . It and the barycenter of t are joined by an edge. The set of barycenters gotten in this way as t varies over all the tiles in S is the set of vertices of G . In addition to the edges of G already defined, the barycenters of two distinct tiles of S are joined by an edge if and only if the tiles have a vertical edge in common. This defines the graph G (see Figure fig:graphg ). We define the valence of a tile of S to be the valence of its barycenter. Each tile of S has valence either 3or 4. figure ecgd55el-fig-16 The graph G fig:graphg figure In this paragraph we assign an edge path in G to . Since separates the ends of R , it follows that meets . It easily follows that meets a bottom edge of S and a top edge of S . Let x 1 be the last point in relative to the parametrization of which is in a bottom edge of S . We construct an edge path in G as follows. From x 1 the path enters a tile t 1 of S . The initial vertex of is the vertex of G which is a barycenter in the boundary of t 1 which is in a bottom edge of S . From this vertex goes to the barycenter of t 1 . Let x 2 be the first point in beyond x 1 which is in the boundary of t 1 . If x 2 is in a top edge of S , then goes from the barycenter of t 1 to the vertex of G which is a barycenter in the boundary of t 1 which is in a top edge of S . If x 2 is in a vertical edge of S , then from x 2 the curve enters a tile t 2 t 1 of S , and goes from the barycenter of t 1 to the barycenter of t 2 . In this way we define one edge at a time until reaching the terminal vertex of , which is the first such barycenter of a top edge of S . Since S is contained in the ring R , we may orient S . Let t be a tile of S such that passes through the barycenter of t . If t has valence 3, then as passes through the barycenter of t it either reverses direction or turns left or turns right. If t has valence 4, then as passes through the barycenter of t it either reverses direction or turns left or turns right or goes straight. Suppose that goes straight through the barycenter of a tile t with valence 4. Then some subcurve of lies in t and joins two edges e 1 and e 2 of t such that (t, e 1,e 2 ) is a test quadrilateral image. So joins the ends of a test quadrilateral image if goes straight through the barycenter of some tile with valence 4. Hence we may assume that does not go straight through the barycenter of a tile with valence 4. It is easy to see that cannot either always turn left or always turn right. Moreover, either there exists a tile barycenter at which turns, then reverses direction an even number of times (possibly 0 times) and then turns in the direction opposite to the first turn or there exists a tile barycenter at which turns, then reverses direction an odd number of times and then turns in the same direction as the first turn. Suppose that contains a sub-edge path which at first turns at the barycenter of some tile t 1 , then reverses direction an even number of times and then finally turns in the direction opposite to the first turn at the barycenter of the tile t 2 . Let f be the vertical edge in t 1t 2 . Corresponding to the sub-edge path of under consideration, there exists a subcurve of in t 1t 2 which joins an edge e 1f of t 1 and an edge e 2f of t 2 . If e 1 and f are disjoint, then joins the ends of the test quadrilateral image (t 1, e 1,f ) . Thus we may assume that e 1 meets f . We may likewise assume that e 2 meets f . It easily follows that joins the ends of the test quadrilateral image (t 1t 2, e 1,e 2 ) . Finally suppose that contains a sub-edge path which at first turns at the barycenter of some tile t 1 , then reverses direction an odd number of times between the barycenter of t 1 and the barycenter of the tile t 2 and then finally turns in the same direction as the first turn at the barycenter of t 1 . Let f be the vertical edge in t 1t 2 . Corresponding to the sub-edge path of under consideration, there exists a subcurve of in t 1t 2 which meets f and goes from an edge e 1 of t 1 to an edge e 2 of t 1 such that e 1f , e 2f and e 1e 2 . As in the previous paragraph, we may assume that, e 1 and e 2 meet f . If t 1 is not a triangle, then joins the ends of the test quadrilateral image (t 1t 2, e 1,e 2 ) . Hence we may assume that t 1 is a triangle with edges f , e 1 , and e 2 . figure ecgd55el-fig-17 Proving that joins the ends of a test quadrilateral image fig:gamma figure Either e 1 or e 2 is a vertical edge. Suppose that e 2 is a vertical edge (see Figure fig:gamma ). Then e 1 is a bottom edge of S . Suppose that t 3 is the tile in S other than t 1 which contains e 2 . Then contains a subcurve in t 1t 2t 3 which meets f and e 2 and joins e 1 and an edge e 3 of either t 2 or t 3 such that e 3f and e 3e 2 . Suppose that e 3t 2 . As before, we may assume that e 3 meets f . Let v be the vertex common to f and e 2 . If ve 3 , then joins the ends of the test quadrilateral image (t 1t 2, e 2,e 3 ) . If ve 3 , then joins the ends of the test quadrilateral image (t 1t 2t 3, e 1,e 3 ) . It is likewise true that joins the ends of a test quadrilateral image if e 3t 3 . Finally, with respect to this argument, the case in which e 1 is a vertical edge is identical to the case in which e 2 is a vertical edge. This completes the proof of Theorem thm:123 . proof Finite subdivision rules with symmetry sec:symmetry Given a finite subdivision rule and an -complex X which is a quadrilateral or a ring, it is generally difficult to determine the moduli m(X, n(X)) and M(X, n(X)) . If X is a quadrilateral and has enough symmetry, one can make qualitative statements about the moduli. This is most useful when combined with Theorem thm:123 , as we will see in Theorem thm:dihconf . thm thm:rotational Let be a finite subdivision rule, let X be an -complex, and let Q be a subset of X which is a quadrilateral. Suppose that fXX is a cellular homeomorphism such that f(Q) Q and f takes the top and the bottom of Q into disjoint sides of Q . Then M(Q,(X)) 1 . thm proof By Section 2.3 SR , there exists an optimal weight function for M(Q,(X)) , a positive integer k , and minimal fat flows 1,, k such that is the sum of the characteristic functions 1,, k and A(Q,) kH(Q,) . Hence M(Q,(X)) H(Q,) 2 A(Q,) H(Q,) k . Let f () be the weight function on (X) defined by f ()(t) (f -1 (t)) for every t (X) . Given a subset S of (X) , let f (S) f(s)sS . Then f () j 1 k f ( j) and A(Q,f ()) A(Q,) . Since each minimal fat flow for f () must intersect each cut f ( j) , 1jk , H(Q,f ()) k . However, H(Q,) 2 A(Q,) M(Q,(X)) M(Q,f ()) k 2 A(Q,) , so H(Q,) k . This implies that M(Q,(X)) 1 , proving the theorem. proof cor cor:rotational Let be a finite subdivision rule and let Q be a finite -complex which is a quadrilateral whose top and bottom are unions of edges. Suppose that fQQ is a weak -isomorphism such that f takes the top and the bottom of Q into disjoint sides of Q . Then M(Q, n(Q)) 1 for every integer n 0 . cor We next define the notion of a weak -folding. Let be a finite subdivision rule. Let X , Y , and Z be finite -complexes such that 1) X , Y , and Z are closed topological disks, 2) int (X) int (Y) , and 3) Z X Y (see Figure fig:folding ). Suppose that there exists a weak -isomorphism f from X to an -subcomplex of Y such that the restriction of f to X Y is the identity map. Then there exists a cellular map gZ Y such that g X f and g Y is the identity map on Y . We call g a weak -folding . We say that Z admits a weak - folding of X into Y . figure ecgd55el-fig-18 The complexes X , Y , and Z for a weak -folding fig:folding figure thm thm:dihedral Let be a finite subdivision rule. Let X, Y and Z be finite -complexes such that 1) X , Y and Z are closed topological disks, 2) int (X) int (Y) , and 3) Z X Y . Suppose that fZ Y is a weak -folding of X into Y . Suppose that Z is a quadrilateral whose top T and bottom B are unions of edges. Suppose that Y is a quadrilateral with top f(T) and bottom f(B) . Then equation M(Z, n(Z)) 12M(Y, n(Y)) equation for every nonnegative integer n . thm proof Let n be a nonnegative integer. Let be an optimal weight function on n(Y) for M(Y, n(Y)) . Then there exists a cellular map g n(Z) n(Y) such that g n(X) is a cellular homeomorphism from n(X) to a subcomplex of n(Y) which agrees with f on the vertices of X and g n(Y) is the identity map. Let g () be the weight function on n(Z) defined by g ()(t) (g(t)) for every t n(Z) . It is clear that A(Z,g ()) 2A(Y,) . It is also easy to see that H(Z,g ()) H(Y,) . Hence equation M(Z, n(Z)) H(Z,g ()) 2 A(Z,g ()) 12 H(Y,) 2 A(Y,) 12M(Y,) 12M(Y, n(Y)). equation This proves Theorem thm:dihedral . proof thm thm:dihconf Let be a bounded valence finite subdivision rule whose mesh approaches 0. Suppose that has a single tile type t with p edges. Let the dihedral group G of order 2p act cellularly on t in the usual way. Suppose for this action that every element of G is a weak -automorphism of t . Then is conformal. thm proof We show that satisfies the 1,2,3-tile criterion, Theorem thm:123 . Note that the 1-tile criterion is vacuous if p 3 , and the 3-tile criterion is vacuous if p 3 . Applying Corollary cor:rotational with Q in Corollary cor:rotational replaced by t and f in Corollary cor:rotational replaced by a rotation in G which takes every edge of t to an adjacent edge shows that satisfies the 1-tile criterion. Because G contains every reflection of t , every test quadrilateral Q for consisting of two tiles admits a weak -folding of one tile of Q into the other. Hence Theorem thm:dihedral shows that satisfies the 2-tile criterion unless t is a triangle. If t is a triangle, then there exists a weak -automorphism of Q which interchanges the tiles of Q and is the identity map on their intersection. Hence Corollary cor:rotational shows that satisfies the 2-tile criterion in this case. An argument involving Theorem thm:dihedral similar to the one just used to verify the 2-tile criterion shows that satisfies the 3-tile criterion. Thus the 1,2,3-tile criterion implies that is conformal. This proves Theorem thm:dihconf . proof As an immediate corollary of Theorem thm:dihconf we get that the binary quadrilateral subdivision rule (Example ex:binsquare ) and the pentagonal subdivision rule (Example ex:pentagon ) are conformal. But Theorem thm:dihconf is much stronger than this. Let t be a p -gon with p3 , and let t' be a nontrivial subdivision of t into p -gons such that the corners of t are not subdivided and the dihedral group of order 2p acts cellularly as symmetries of t' . Then the barycenter trick of Section sec:finsubex yields a conformal finite subdivision rule with single tile type a 2p -gon t'' (obtained from t by adding a barycenter to each edge) such that (t'') and the complex obtained from t' by adding a barycenter to each edge are identical subdivisions. Hence it is easy to construct conformal finite subdivision rules. Some simple examples are shown in Figure fig:sqconf . figure ecgd55el-fig-19 Constructing conformal finite subdivision rules fig:sqconf figure We prove one more symmetry theorem for use in Section sec:layerex . thm thm:reflectional Let be a finite subdivision rule with bounded valence, let Q be an -complex which is a quadrilateral whose top and bottom are unions of edges, and let fQQ be a weak -isomorphism such that f takes the top and the bottom of Q bijectively to disjoint sides of Q . Then there is a positive real number K such that for each integer n0 , 1M(Q, n(Q)) K . thm proof Let V be an upper bound on the valences of j(Q) , j0 . Fix an integer n0 . Let Q' be the quadrilateral whose underlying complex is Q but whose ends are the sides of Q . By Corollary cor:rotational , 1M(Q', n(Q)) . Since f interchanges the sides of Q and the ends of Q , m(Q, n(Q)) 1 M(Q', n(Q)) 1 . By the bounded valence theorem Theorem 6.2.4 SR , M(Q, n(Q)) 4V 2 m(Q, n(Q)) . Hence M(Q, n(Q)) 4V 2 , which proves the theorem. proof Layered subdivision rules sec:layerex As we mentioned previously, it is generally difficult to compute the moduli m(X, n(X)) and M(X, n(X)) for a quadrilateral or ring X which is an -complex with respect to a finite subdivision rule . A class of examples for which one can sometimes reasonably estimate moduli are those for which each n(X) can be naturally subdivided into layers, since one can then use Theorem thm:layer . We use the term layered subdivision rules as a general (and loose) description for this class. We give three examples. The first one shows that it does not suffice to check a single quadrilateral to show that a finite subdivision rule satisfies the 1-tile criterion. The second example, which is a modification of the first one, shows that this persists even if the tile recursion matrix is irreducible. The third example is of a finite subdivision rule that satisfies the 1-tile criterion but does not satisfy the 2-tile criterion. Furthermore, there exists a quadrilateral for the third example with nondegenerate asymptotic moduli such that if this quadrilateral is split into two quadrilaterals in any way by an arc joining its sides, then the moduli of the two quadrilaterals degenerate to 0. The diamond chains subdivision rule ex the diamond chains subdivision rule ex:dmhdbnd In this finite subdivision rule the subdivision complex S contains a single edge and two tiles. Tile type t is an equilateral triangle, and (t) is the obvious subdivision of t into four subtriangles that are congruent to t . Tile type q is a quadrilateral. Its subdivision is shown in Figure fig:dmhdbnd1 ; quadrilaterals in (q) are identified with the image of q in S so that horizontal edges go to horizontal edges. The subdivisions (q) , 2(q) , and 3(q) are shown in Figure fig:dmhdbnd2 . ex figure ecgd55el-fig-20 The subdivisions of the tile types for the diamond chains subdivision rule fig:dmhdbnd1 figure figure ecgd55el-fig-21 i(q) , i 1,2,3 fig:dmhdbnd2 figure We view q as a quadrilateral with top and bottom as indicated in Figure fig:dmhdbnd1 . We will use the layer theorem to show that q has degenerate asymptotic moduli. To use the layer theorem we first rotate q 90 to obtain a quadrilateral q' . Note that for each positive integer n , n(q') is naturally divided into 2 n vertical layers (strips). More importantly for us, it is also divided into horizontal layers, each horizontal layer consisting of a chain of quadrilaterals or a chain of diamonds. The chains of diamonds come in different sizes; we say that a chain of diamonds has size i if the maximum number of triangles in a vertical layer of the chain is 2 i-1 . Then n(q') has 2 n chains of quadrilaterals. For each i 1,...,n , n(q') has 2 n-i chains of diamonds of size i . Although the chains of diamonds are not actually quadrilaterals, the proof of the layer theorem goes through as before. Let n be a fixed positive integer, let i 1,,n , and let D i be a chain of diamonds of size i . Let i be the weight function on the set of tiles of D i defined such that the weight of a triangle is the reciprocal of the number of triangles in its vertical strip. The fat flow height is H(D i, i) 1 . For each odd integer k with 1k 2 i-1 , there are 2 n 1-i vertical strips in D i with k triangles. Hence equation A(D i, i) 2 n 1-i ( 1 13 15 1 2 i-1 ) 2 n-i (2 (2 i)), equation and so M(D i, i) 1 (2 n-i (2 (2 i))) . The fat flow modulus of a chain of quadrilaterals is 1 2 n , with the constant weight function which assigns 1 to each tile in the chain being an optimal weight function. By the layer theorem, equation M(q', n(q')) 2 n1 2 n i 1 n 2 n-i 2 n-i (2 (2 i)) 1 1 2 (2) i 1 n 1i. equation Since the harmonic series is divergent, q' and q have degenerate asymptotic moduli. While q has degenerate asymptotic moduli, the quadrilateral X made up of two triangles with an edge in common has nondegenerate asymptotic moduli by Theorem thm:reflectional , taking the map in Theorem thm:reflectional to be reflection in the common edge. Since the tile recursion matrix for is reducible (see Chapter XIII GANT for the definition), it is not so surprising that some quadrilaterals have degenerate asymptotic moduli and some have nondegenerate asymptotic moduli. The next example, which was inspired by this one, shows that this can occur even if the tile recursion matrix is irreducible. ex ex:hdbnd2 In this example the subdivision complex S has two edges and two tiles. The subdivisions of the tile types are shown in Figure fig:hdband2 . ex Let X be the quadrilateral with a single tile labeled 1 , oriented as in Figure fig:hdband2 . Given a positive integer n , define a weight function n on n(X) which assigns weight 1 to every tile labeled 1 which has no predecessor which is a tile labeled 2 , and assigns weight 0 to every other tile. The fat cut circumference is C(X, n) 3 n and the area is A(X, n) 6 n , so m(X, n(X)) m(X, n) A(X, n) C(X, n) 2 6 n 9 n , n m(X, n(X)) 0 , and X has degenerate asymptotic moduli. Since the tile labeled 2 has rotational symmetry, the quadrilateral Y with single tile this tile and orientation as in Figure fig:hdband2 has nondegenerate asymptotic moduli by Theorem thm:reflectional . The tile recursion matrix, with respect to the obvious ordering of the tiles, is ( array ll 6 4 4 0 array ) , which is irreducible. figure ecgd55el-fig-22 The subdivisions of the tile types for the finite subdivision rule of Example ex:hdbnd2 fig:hdband2 figure A layered subdivision rule that satisfies the 1-tile criterion but not the 2-tile criterion ex ex:lyr1n2 We start with two edge types and a single tile type, with the subdivision of the tile type shown in Figure fig:lyr1not2 . We then apply the barycenter trick of Section sec:finsubex to obtain a finite subdivision rule such that the subdivision complex S has two edges and a single tile q . ex figure ecgd55el-fig-23 The subdivision of the tile type for the finite subdivision rule of Example ex:lyr1n2 fig:lyr1not2 figure figure ecgd55el-fig-24 A quadrilateral X with degenerate asymptotic moduli fig:lyr1n2q figure Since the tile type q is the subdivision of a quadrilateral and reflection in one of the diagonals of the quadrilateral is a weak -isomorphism, q has nondegenerate asymptotic moduli by Theorem thm:reflectional and hence satisfies the 1-tile criterion of Section sec:123crit . To see that does not satisfy the 2-tile criterion of Section sec:123crit , let X be the quadrilateral shown in Figure fig:lyr1n2q a). Given a positive integer n , n(X) can be divided into 4 n vertical layers. Figure fig:lyr1n2q b) shows the case where n 1 . Let n be the weight function on n(X) which assigns weight 1 to each tile. Then C(X, n) 4 n and A(X, n) 213 n , so m(X, n(X)) m(X, n) A(X, n) C(X, n) 2 213 n 16 n and hence n m(X, n(X)) 0 . Now the bounded valence theorem, Theorem 6.2.4 SR or Theorem 1.6 SUFFRICH , implies that n M(X, n(X)) 0 . Thus does not satisfy the 2-tile criterion of Section sec:123crit . In particular, is not conformal. figure ecgd55el-fig-25 Y , (Y) , and W fig:lyr1n2sq figure Now consider the quadrilateral Y shown in Figure fig:lyr1n2sq . This quadrilateral occurs in (q) , and hence occurs whenever one considers subdivisions of an -complex. Since the reflection in one of the diagonals of Y is a weak -isomorphism, Y has nondegenerate asymptotic moduli by Theorem thm:reflectional . Let be a simple edge-path in some subdivision j(Y) , j 0 , that irreducibly joins the sides of Y and is disjoint from the ends of Y , and let W be the quadrilateral that is contained in Y , has bottom the bottom of Y , has top , and has sides contained in the sides of Y . We will show that i M(W, i(W)) 0 . It will then follow by symmetry that the same is true of the quadrilateral with bottom , with top the top of Y , and with sides contained in the sides of Y . This shows that a quadrilateral can have nondegenerate asymptotic moduli even if, whenever it is divided into horizontal layers, the layers have asymptotic moduli converging to 0. Although the layers in j(Y) each join one of the sides with one of the ends, one of the two layers of W that is adjacent to the diagonal joins the bottom of W to the top of W . Let i be a nonnegative integer. Then i(W) has at least 4 i layers that join the bottom of W to the top of W . Let be the weight function on i(W) that assigns weight 1 to each tile. Then A(W,) 213 i j and C(W,) 4 i , so m(W, i(W)) m(W,) A(W,) C(W,) 2 213 i j 16 i . This implies that i m(W, i(W)) 0 and hence, by the bounded valence theorem, Theorem 6.2.4 SR or Theorem 1.6 SUFFRICH , i M(W, i(W)) 0 . Finite subdivision rules with rotational symmetry sec:rotation A finite subdivision rule has rotational symmetry , or is rotationally symmetric , if for each tile type t there exists an orientation-preserving weak -automorphism of t which takes every edge of t to an adjacent edge. We look now at finite subdivision rules that have a single tile type and have rotational symmetry. We first consider a class of examples which gives rotationally symmetric self-replicating tilings. Finally, we give an example of a nonconformal finite subdivision rule with bounded valence which has a single tile type and is rotationally symmetric. A construction of rotationally symmetric self-replicating tilings We begin the section by giving a general construction of rotationally symmetric subdivision rules. The construction can be done starting from the tiling of the Euclidean plane by equilateral triangles, squares, or regular hexagons. By area considerations, it cannot be done using tilings of the hyperbolic plane. In these examples, we are starting with a finite subdivision rule and are constructing an almost round finite subdivision rule ' which is weakly isomorphic to it. It follows that is conformal. Furthermore, translates of the single tile type of ' give a self-replicating tiling of 2 with rotational symmetry. Self-replicating tilings have been studied extensively. In particular, Thurston Thurston and Kenyon Kenyon constructed them from generalizations of the usual base 10 decimal expansion of a number with respect to bases which are complex numbers, and Dekking Dekking constructed them from free group endomorphisms. Our approach starts instead with the combinatorics of the subdivision, and is similar in spirit to that of Giles Giles1,Giles2 . For convenience, we will start with the square tiling of the plane. Several examples of this construction can be found in Mandelbrot Fractals . To begin the construction, choose vertices v 1 , v 2 , v 3 , and v 4 in the square lattice that are vertices of a square. We assume that they are not the vertices of a square in the square tiling, since this case is trivial. Label them so that they occur in clockwise order as vertices of a square. Now choose an arc 1 from v 1 to v 2 which is an edge path in the square tiling. There are two requirements on 1 . Let 2 be the image of 1 under rotation of 2 about v 2 , let 3 be the image of 2 under rotation of 2 about v 3 , let 4 be the image of 3 under rotation of 2 about v 4 , and let be the closed curve in the plane whose image is 1 2 3 4 . The first requirement is that 1 be invariant under rotation of about the midpoint of the line segment v 1v 2 . The second condition is that be a simple closed curve. Another way to look at these conditions is to pass to a quotient space. Let u be the center of the square with vertices v 1 , v 2 , v 3 , and v 4 , and let w be the midpoint of v 1v 2 . Let S be the quotient of the triangle with vertices v 1 , v 2 , and u obtained by identifying uv 1 with uv 2 and identifying wv 1 with wv 2 . Then S is a sphere with branch points u' , v' , and w' (the images of u , v 1 , and w , respectively) of order 4 , 4 , and 2 . The 1-skeleton of the square tiling of the plane projects to a graph on S . S is a quotient of the plane, and under this quotient map a curve as described in the previous paragraph projects to an arc in the graph on S joining v' and w' . Arcs 1 from v 1 to v 2 which satisfy the two requirements of the previous paragraph correspond exactly in the quotient to arcs from v' to w' which lie in the graph coming from the 1-skeleton of the square tiling. Before continuing the construction, we give two examples. ex ex:frsq1 In this example, v 2-v 1 (2,2) . The curve is shown in Figure fig:frsq1g and the image of in S is shown in Figure fig:frsq1s . ex figure ecgd55el-fig-26 The curve for Example ex:frsq1 fig:frsq1g figure figure ecgd55el-fig-27 The image of in S for Example ex:frsq1 fig:frsq1s figure figure scale .8 ecgd55el-fig-28 The curve for Example ex:frsq9 fig:frsq9g figure ex ex:frsq9 In this example, v 2 - v 1 (9,0) . The curve is shown in Figure fig:frsq9g and the image of in S is shown in Figure fig:frsq9s . ex figure ecgd55el-fig-29 The image of in S for Example ex:frsq9 fig:frsq9s figure We return now to the general construction. Suppose that 1 is an arc satisfying our two requirements above, and that is the corresponding curve. Since v 1 , v 2 , v 3 , and v 4 are vertices of a square, there is an orientation-preserving similarity of the plane that takes v 1 , v 2 , v 3 , and v 4 to the vertices of the unit square D with v 1 going to (0,0) . Let 1 be the image of under this map, and let D 1 be the disk enclosed by 1 . We consider 1 as a function 1 0,1 2 with 1(0) (0,0) , parametrized with constant speed. The Euclidean plane can be tiled by translates of D 1 , and this tiling is combinatorially equivalent to the square tiling of the plane, so one can repeat the above construction beginning with the tiling by translates of D 1 . One can recursively continue this process to produce curves i (with i(0) (0,0) , parametrized with constant speed) and disks D i for each positive integer i . Figure fig:frsq1ap shows the disks D 1 , D 2 , and D 3 for Example ex:frsq1 , and Figure fig:frsq9t shows the disk D 2 for Example ex:frsq9 . figure ecgd55el-fig-30 The disks D 1 , D 2 , and D 3 for Example ex:frsq1 fig:frsq1ap figure figure scale .85 ecgd55el-fig-31 The disk D 2 for Example ex:frsq9 fig:frsq9t figure The i 's can be recursively generated by simple edge replacement rules. Figure fig:frsq1er shows the edge replacement rule for Example ex:frsq1 , and Figure fig:frsq9er shows the edge replacement rule for Example ex:frsq9 . figure ecgd55el-fig-32 The edge replacement rule for Example ex:frsq1 fig:frsq1er figure figure ecgd55el-fig-33 The edge replacement rule for Example ex:frsq9 fig:frsq9er figure Let 0 be the line segment from v 1 to v 2 . Choose orientation-preserving constant speed parametrizations f 0 0,1 0 and f 1 0,1 1 . Let K d(f 1(t),f 0(t))t 0,1 , and let d d(v 1,v 2) . Then for any positive integer j , d( j 1 (t) , j(t)) t 0,1 K d j 1 . Hence the i 's converge uniformly to a continuous curve 0,1 2 . Note that for any positive integer i and any t 0,1 , d((t), i(t)) d i(d-1) . We associate to a finite subdivision rule as follows. has a single tile type, which is a quadrilateral. If we view this tile type as the quadrilateral Q in 2 with boundary and with vertices v 1 , v 2 , v 3 , and v 4 , then the subdivision of this tile type is given by the subdivision of Q by squares in the intersection of Q with the square tiling of 2 . Orient the edges in Q and in the subdivision of Q so that each vertex in Q (resp. in the subdivision of Q ) is either an initial vertex or a terminal vertex of every edge in Q (resp. in the subdivision of Q ) that meets it. The subdivision complex S is obtained from Q by identifying the four edges by order-preserving isomorphisms. There is a single edge type e , and it is subdivided into length ( 1) edges. The subdivision map is defined so that it is order preserving and the edge of S can be ordered so that the maps QS and (Q)S are order preserving on the edges. Note that, by construction of , the subdivision of Q is invariant under a rotation by angle 2 . Figure fig:frsq1sr shows the subdivision of the tile type for Example ex:frsq1 , and Figure fig:frsq9sr shows the subdivision of the tile type for Example ex:frsq9 . figure ecgd55el-fig-34 The subdivision of the tile type for Example ex:frsq1 fig:frsq1sr figure figure scale .85 ecgd55el-fig-35 The subdivision of the tile type for Example ex:frsq9 fig:frsq9sr figure In the above construction of the D i 's, D 1 is the image of Q under a similarity of the plane. The intersection of Q with the square tiling of 2 maps under this similarity to give a tiling of D 1 by squares with side lengths 1 d . By repeating this under the recursive construction of the D i 's, each D i has a tiling by squares with side lengths 1 d i . Combinatorially, this tiling is i(Q) . We next show that is a simple closed curve. In order to do this, we first show that has mesh approaching 0 combinatorially. Since there is a single edge type and d(v 1,v 2) 1 , each edge type of is subdivided into more than one edge. Now suppose that one of the subtiles of Q has edges in disjoint edges of Q . Since this subtile is a quadrilateral, it must have an edge joining disjoint edges in Q , but then this edge disconnects Q , so Q cannot have a subtile with an edge in each of the other two edges of Q . This is impossible, since the subdivision of Q is rotationally symmetric. Thus the mesh of approaches 0 combinatorially. It follows from Theorem thm:theorem3 that is weakly isomorphic to a finite subdivision rule whose mesh approaches 0, and so we assume that the mesh of approaches 0. For convenience we assume that the tile type is the unit square D . Let X be the square tiling of 2 , viewed as an -complex. As noted above, D i has a natural tiling by squares with side lengths 1 d i , which gives D i the structure of a CW complex which is cellularly homeomorphic to i(D) . In particular, for every positive integer i there exists a cellular homeomorphism iD i i(D) which preserves clockwise orientation such that i(0,0) (0,0) . Let s,t 0,1) with s t . Then because the mesh of approaches 0, the sequences i( i(s)) and i( i(t)) converge to points u,vD . Moreover u v . For every positive integer i let d i(u,v) denote the skinny path pseudometric; d i(u,v) is the smallest nonnegative integer n such that there exist tiles t 0,,t n of i(X) such that ut 0 , vt n , and t j t j 1 for j 0,,n-1 . Then because the mesh of approaches 0, there exists a positive integer i such that d i(u,v) 1 2K d-1 . It follows that d( i(s), i(t)) 1 d i 2K d-1 2K d i(d-1) . Hence, d((s),(t)) d( i(s), i(t)) - d((s), i(s)) - d((t), i(t)) 0 , so (s) (t) . Thus is a simple closed curve, and hence ( 0,1 ) bounds a disk D . By construction, 2 is tiled by translates of D . Furthermore, D has a subtiling, by tiles that are equivalent to D under similarities, that is cellularly homeomorphic to (Q) . It is straightforward to define a finite subdivision rule ' which is weakly isomorphic to , has D as the single tile type, and has the property that for each closed tile t of '(D ) the map tS ' is the composition of D and a similarity from t onto D . Hence if we let X' be 2 viewed as an ' -complex using the tiling by translates of D , then (X',') is almost round. By Theorem 7.1 CRMT , (X',') and (X,) are conformal. Note that in the edge replacement rule for Example ex:frsq9 , each edge is replaced by a union of 41 edges, each of length one ninth the length of the original edge. It follows from this that the Hausdorff dimension of D is the similarity dimension, which is (41) (9) . Example ex:frsq9 is one of an infinite family of examples with the property that the Hausdorff dimensions of the boundaries of the disks D converge to 2 . To see this, suppose that v 2 - v 1 (4s 1,0) for some positive integer s . Then the graph on S which comes from the grid on 2 has 4s 2 2s 1 vertices. It is easy to see that the maximum number of edges that an edge can be subdivided into in the edge replacement rule is 2(4s 2 2s 1) - 1 8s 2 4s 1 , and that this number of edges can be achieved. (Example ex:frsq9 illustrates the case s 2 , and Figure fig:frsq13g shows the curve for an example achieving the maximum number when s 3 .) When this maximum number of edges is achieved, the Hausdorff dimension of D is (8s 2 4s 1) (4s 1) , which converges to 2 as s . This was also noted in caption to Plate 53 Fractals . figure scale .8 ecgd55el-fig-36 The curve for the case s 3 fig:frsq13g figure A rotationally symmetric finite subdivision rule which is not conformal Our final example is a rotationally symmetric finite subdivision rule with a single tile type which is not conformal. It is crucial for the construction that is not orientation preserving. However, by making a tile type for each orientation, the example could easily be modified to an orientation-preserving, rotationally symmetric finite subdivision rule with two tile types. ex ex:rotnc In this example there is a single edge type and a single tile type. The tile type t is a quadrilateral viewed as a subset of the Euclidean plane. The tile type t is subdivided into forty-five tiles, and the edge type is subdivided into twenty-three edges. Figure fig:rotncsr shows the subdivision of t . We apply the barycenter trick of Section sec:finsubex to obtain a finite subdivision rule . We choose orientations for the open tile in S and for the interior of t so that the restriction of t to int (t) is orientation preserving. A tile s in (t) is labeled with a plus sign in Figure fig:rotncsr if is orientation preserving on t( int (s)) and is labeled with a minus sign if is orientation reversing on t( int (s)) . If s is not labeled, then it does not matter for the construction whether is orientation preserving or orientation reversing on t( int (s)) . It is clear that can be defined so that this finite subdivision rule is rotationally symmetric. ex figure scale .90 ecgd55el-fig-37 The subdivision of the tile type t fig:rotncsr figure figure ecgd55el-fig-38 The quadrilateral Q fig:rotncq figure Since this finite subdivision rule is rotationally symmetric, it satisfies the 1 -tile criterion. We next show that does not satisfy the 2 -tile criterion, and hence is not conformal. Let Q be the quadrilateral shown in Figure fig:rotncq viewed as a subset of the Euclidean plane, given the structure of an -complex with associated map fQS so that (with suitable orientations on Q and on the open tile of S ) f preserves orientation on each of the open tiles of Q . We use the layer theorem to show that n M(Q, n(Q)) 0 . By the bounded valence theorem, Theorem 6.2.4 SR or Theorem 1.6 SUFFRICH , it suffices to prove that n m(Q, n(Q)) 0 . We first define blocks. Let k be a positive, even integer. A block of height k is a subcomplex B of n(Q) , for some positive integer n , which satisfies the following: B is cellularly homeomorphic to a tiling by unit squares of a rectangle of height k and width 3 (we will use this cellular homeomorphism in describing the other conditions on B ); in any row of B , all of the tiles have the same orientation; in any column of B , the orientations of the tiles alternate; and the ends of B are in distinct ends of n(Q) . figure scale .90 ecgd55el-fig-39 The quadrilateral (Q) fig:rotncrq figure figure scale .90 ecgd55el-fig-40 The subdivision of a block of height 2 fig:rblock figure Note that (Q) has two blocks of height 2 (see Figure fig:rotncrq ). If B is a block of height k , then (B) contains four blocks of height 2k . (See Figure fig:rblock for the subdivision of a block of height 2 .) It follows by induction that, if n is a positive integer, then n(Q) contains 24 n-1 blocks of height 2 n . Let n be a positive integer, and let n be the weight function on n(Q) for which each tile in a block has weight 1 and each tile which is not in a block has weight 0 . Since each block contains three vertical layers, C(Q, n) 324 n-1 . Then equation m(Q, n(Q)) m(Q, n) 64 n-1 2 n 364 2n-2 1 32 n-1 . equation Hence n m(Q, n(Q)) 0 , and is not conformal.