New York Journal of Mathematics

New York J. Math. 6 (2000) 237–283.

Divisible Tilings in the Hyperbolic Plane

S. Allen Broughton, Dawn M. Haney, Lori T. McKeough, and Brandy Smith Mayfield

Abstract. We consider triangle-quadrilateral pairs in the hyperbolic plane which “kaleidoscopically” tile the plane simultaneously. In this case the tiling by quadrilaterals is called a divisible tiling. All possible such divisible tilings are classified. There are a finite number of 1, 2, and 3 parameter families as well as a finite number of exceptional cases.

Contents

1. Introduction 238 2. Tilings and Tiling Groups 240

2.1. Tiling Groups 241 2.2. Divisible Tilings 243

3. Overview of Quadrilateral Search 246 3.1. Free Vertices 246 3.2. Constrained Vertices 248 3.3. The Two Search Methods 250

4. Direct Construction Method (K ≤ 12) 251 4.1. Polygon Construction and Elimination—No Interior Hubs 253 4.2. Computer Algorithm and Extension to Interior Hubs. 256

5. Boundary Construction Method (K > 12) 257 5.1. Geometric Quadrilateral Test 259 5.2. Boundary Word Test 259 5.3. Example: Failure of (2, 3, 7) to Tile (7, 7, 7, 7) 262 5.4. Example: Successful Tiling of (5, 5, 5, 5) by (2, 4, 5) 262

6. Catalogue of Divisible Tilings 265 Appendix A. Triangles with area ≤ \frac{π}{4} 282 References 283

237^{ISSN 1076-9803/00}

Received October 11, 1999.

Mathematics Subject Classification. 05B45, 29H10, 20H15, 51F15, 52C20, 51M10.

Key words and phrases. tiling, Fuchsian groups, reflection groups, crystallographic groups, hyperbolic plane.

The last three authors were supported by NSF grant DMS-9619714.

238 S. A. Broughton, D. Haney, L. McKeough, and B. Mayfield

1. Introduction

Let Δ be a polygon in one of the three two-dimensional geometries: the sphere 𝕊^{2}, the Euclidean plane 𝔼 or the hyperbolic plane ℍ. Suppose also that each interior angle of the polygon at vertex P_{i} has measure \frac{π}{s_{i}} where s_{i} is an integer. The polygon generates a tiling of the plane by repeated reflections in the sides of the polygon. Examples are the icosahedral tiling of the sphere by 36^{∘}-60^{∘}- 90^{∘} triangles in Figure 1.1, and the partially shown tilings of the Euclidean plane by 45^{∘}-45^{∘}-90^{∘} triangles in Figure 1.2 and the hyperbolic plane by 36^{∘}-36^{∘}-90^{∘} triangles in Figure 1.3. These tilings are called geodesic, kaleidoscopic tilings since the tiling may be generated by reflections in a single tile. We explain the term geodesic soon. A denizen of the two dimensional geometry could view the tiling by constructing a polygon of mirrors meeting at the appropriate angles – assuming that light travels in straight lines in the geometry! In the Euclidean case the mirrored polygons can actually be physically constructed and the tiling viewed for the three Euclidean kaleidoscopic triangles (30^{∘}-60^{∘}-90^{∘}, 45^{∘}-45^{∘}-90^{∘}, 60^{∘}-60^{∘}-60^{∘}) and the one 1-parameter family of kaleidoscopic rectangles.

The plane may be kaleidoscopically tiled in several different ways as Figure 1.2 shows. One way is by triangles. A second way is by squares consisting of four triangles meeting at the center of the square. Yet a third way is the tiling by squares formed from two triangles meeting along a hypotenuse. The tilings by squares are both refined or subdivided by the tiling of triangles, i.e., each square is a union of either four non-overlapping triangles or two non-overlapping triangles in the two cases. We say that the tiling by squares is divisible or that the tiling by squares is subdivided by the tiling by triangles. If Δ ⊂ Ω are such a triangle and square respectively we call (Δ, Ω) a divisible tiling pair.

There are no divisible quadrilateral tilings of the sphere. There are infinitely many different divisible quadrilateral tilings of the Euclidean plane but they are all found in the 45^{∘}-45^{∘}-90^{∘} tiling in Figure 1.2. In this paper we turn our attention to the much richer case of divisible quadrilateral tilings of the hyperbolic plane. The reader is invited to find the tiling by quadrilaterals hidden in Figure 1.3 without “cheating” by looking at the “answers” in the tables in Section 6. Each quadrilateral has 12 triangles.

The main result of the paper, Theorem 6.2, is a complete catalogue of all divisible quadrilateral tilings of the plane which may be subdivided by a triangle tiling. For completeness we also include the less complex cases of triangle tilings which subdivide triangle tilings (Theorem 6.1) and quadrilateral tilings which subdivide quadrilateral tilings (Theorem 6.3). The classification of tilings of quadrilaterals by triangles is broken up into two categories, constrained and free. The main difference between the two is that the free tilings occur in infinite families with simple parametrizations by integers, but there are only a finite number of constrained divisible tilings. The complete lists of the four types of divisible tiling pairs described above are given in Tables 6.1–6.4 in Section 6. More importantly, pictures of all the various tiling pairs are given in Tables 6.5–6.8 of the same section.

To put our results in a broader context we sketch an application of the results to a problem in the classification of Fuchsian groups, which in turn is relevant to the singularity structure of moduli spaces of Riemann surfaces for certain genera. Let Λ_{1} and Λ_{2} be two Fuchsian groups such that Λ_{1} has signature (0; l, m, n) and Λ_{2} has signature (0; s, t, u, v), and let ℍ be the disc model of the hyperbolic plane. Thus the projections ℍ → ℍ/Λ_{1} and ℍ → ℍ/Λ_{2} are branched covers of the sphere branched over 3 points of orders l, m, n and 4 points of orders s, t, u, v respectively. One may ask under what conditions does Λ_{2} ⊆ Λ_{1}. The tiling polygons Δ and Ω generate groups Λ_{1}^{∗} and Λ_{2}^{∗} such that the conformal subgroups Λ_{1} ⊂ Λ_{1}^{∗} and Λ_{2} ⊂ Λ_{2}^{∗}, of index 2, are of the type specified in the classification problem. The two groups constructed are real, i.e., the tiling polygons may be translated such that Λ_{1} and Λ_{2} are real, i.e., both groups are invariant under conjugation. In turn this implies that the points Λ_{1} and Λ_{2} correspond to singular points on the moduli space of Riemann surfaces with real defining equations for certain genera. The details of this will be discussed in a subsequent paper [4] which examines divisible tilings on surfaces. The problem of determining pairs Λ_{2} ⊆ Λ_{1} with an equal number of branch points was solved in [10]. The corresponding tiling problem is tilings of triangles by triangles and quadrilaterals by quadrilaterals. The solution of this problem follows easily from [10], though the classification has not been published, to our knowledge. We include both of these results for completeness.

The remainder of this paper is structured as follows. In Section 2 we introduce the necessary background on planar tilings, divisible tilings and the tiling groups. In Sections 3, 4 and 5 we introduce and discuss the two computer algorithms for determining the divisible tilings and illustrate them with some sample calculations. Finally all results, including figures are listed in tables in Section 6. Throughout the discussion, the reader is encouraged to look at these figures to gain a clearer idea of the definitions and the discussion.

We will use the disc model for the hyperbolic plane ℍ, in which the points are in the interior of the unit disc, the lines are the unit disc portions of circles and lines perpendicular to the boundary of the unit disc, and reflections are inversions in the circles defining the lines. We will denote the hyperbolic distance between two points z_{1} and z_{2} by ρ(z_{1}, z_{2}). All properties we use about hyperbolic geometry, in particular the area formula for polygons, may be found in the text by Beardon [1]. Acknowledgments. The initial part of this research work was conducted during the NSF-REU program at Rose-Hulman Institute of Technology in the summer of 1997 (Haney and McKeough [8]) and continued in 1998 (Smith [12]) under the direction of Allen Broughton. The 1997 project worked out the classification under a restrictive hypothesis called the corner condition and yielded 13 of the constrained cases. A subdivided quadrilateral satisfies the corner condition if each corner of the quadrilateral contains a single triangle. For example cases C1 and C2 in Table 6.7 satisfy this property though cases C5 and C9 do not. Many of the symmetry properties of the tilings were examined, and therefore the symmetry groups of the tiling pairs are included in the tables in Section 6. The 1997 group also undertook some of the preliminary work in determining divisible tilings on surfaces, the results of which will appear in a forthcoming publication [4]. The 1998 project took a different approach that yielded many of the free cases with a small number of triangles. The present work combines and extends both approaches to yield a complete classification of planar hyperbolic divisible tilings by quadrilaterals.

We thank the numerous participants of the 1997 and 1998 programs for the useful conversations and encouragement. All numerical calculations were performed using Maple [13]. The figures were produced with Maple and Matlab [14]. All Maple and Matlab scripts used, as well as images, are available at the tilings website [15].

Figure 1.1. Icosahedral (2, 3, 5) tiling of 𝕊^{2}

Figure 1.2. (2, 4, 4) tiling of 𝔼  Figure 1.3. (3, 3, 4) tiling of ℍ

2. Tilings and Tiling Groups

A tiling of the spherical, Euclidean or hyperbolic plane is a collection T of polygons, called tiles, that completely cover the plane without overlaps or gaps. The sides or edges of the tiles are called the edges of the tiling and the vertices of the tiles are called the vertices of the tiling. Let E and V denote the collection of edges and vertices of the tiling.

Definition 2.1. A tiling T of a plane is said to be a kaleidoscopic tiling if the following condition is met:

1. For each edge e ∈ E of the tiling the reflection r_{e} in the edge e is an isometry of the plane that maps tiles to tiles. In particular it interchanges the two tiles whose common edge is e.

A tiling T is called a geodesic, kaleidoscopic tiling if in addition we have the following condition.

2. The fixed line or mirror {x ∈ S : r_{e}(x) = x} of each reflection r_{e}, is the union of edges of the tiling. Such a line is called a line of the tiling.

The tiling of the Euclidean plane by hexagons or the dodecahedral tiling of the sphere by pentagons are examples of kaleidoscopic tilings which are not geodesic. For the remainder of the paper, unless specified otherwise, all tilings we discuss will satisfy Definition 2.1. The following proposition allows us to easily identify which polygons give rise to the desired tilings. It is easily proven using the Poincaré Polygon Theorem [1, p. 249].

Proposition 2.2. Let Δ = P_{1}P_{2} ⋯ P_{n} be a n-gon. Then Δ generates a kaleidoscopic tiling of the plane by repeated reflection in its sides only if the interior angles at the vertices of the polygon have measure \frac{2π}{n_{i}} where n_{i} is an integer. If in addition each n_{i} is even, say n_{i} = 2m_{i}, so \frac{2π}{n_{i}} = \frac{π}{m_{i}} then Δ generates a geodesic, kaleidoscopic tiling.

We shall call a polygon kaleidoscopic if it generates a kaleidoscopic tiling. Throughout the paper we shall only consider kaleidoscopic tilings that generate geodesic tilings, i.e., the angles have the form \frac{π}{m_{i}} .

Notation 2.3. A polygon P_{1}P_{2} ⋯ P_{n} such that the interior angle at P_{i} has radian measure \frac{π}{m_{i}} is called an (m_{1}, m_{2}, …, m_{n})-polygon. Note that 2m_{i} tiles meet at the vertex P_{i}. Hence we easily identify the tiles of the icosahedral tiling in Figure 1.1 as (2, 3, 5)-triangles.

2.1. Tiling Groups. The reflections in the edges of a tiling generate a group of isometries of the tiling, called the tiling group. We describe this group in some detail now for the case of a triangle. The generalization to the group of a general polygon easily follows from the triangle discussion. It is easy to show that every tile in the plane is the image, by some element of the tiling group, of a single tile, called the master tile, pictured in Figure 2.1. The sides of the master tile, Δ_{0}, are labeled p, q, and r, and we denote the vertices opposite these sides by P, Q, and R, respectively. We also denote by p, q, and r the reflection in corresponding side. We assume that Δ_{0} is an (l, m, n)-triangle so that the angles at R, P, and Q have size \frac{π}{l} radians, \frac{π}{m} radians, and \frac{π}{n} radians, respectively, where l, m, and n are integers ≥ 2 (see Figure 2.1). At each of the vertices of the triangle, the product of the two reflections in the sides of the triangle meeting at the vertex is a rotation fixing the vertex. The angle of rotation is twice the angle at this vertex. For example the product p · q, a reflection first through q then through p, is a counter-clockwise rotation through \frac{2π}{l} radians. We will refer to this rotation as a = pq and use it to label the vertex in Figure 2.1. Rotations around each of the other corners can be defined in the same way, so that b = qr and c = rp are counter-clockwise rotations through \frac{2π}{m} radians and \frac{2π}{n} radians, respectively.

Figure 2.1. The master tile and generators of T and T^{∗}

From the geometry of the master tile, we can derive relations among these group elements. It is clear that since p, q, and r are reflections, the order of each of these elements is 2:

p^{2} = q^{2} = r^{2} = 1. (1)

From the observations about rotations above, it is also clear that the orders are given by

o(a) = l, o(b) = m, o(c) = n, (2)

and

abc = pqqrrp = 1. (3)

The reflections generate a group T^{∗} = ⟨p, q, r⟩ , and the rotations generate a subgroup T = ⟨a, b, c⟩ which includes only the orientation-preserving isometries in T^{∗}. The subgroup T is of index 2 in T^{∗} and hence is also normal in T^{∗}. Here are some well-known basic facts about T^{∗} and T.

Proposition 2.4. Let T^{∗} and T be derived from a tiling T as above. Then the following hold.

1. The groups T^{∗} and T have the following presentations

T^{∗} = ⟨p, q, r : p^{2} = q^{2} = r^{2} = (pq)^{l} = (qr)^{m} = (rp)^{n} = 1⟩ (4)

and

T = ⟨a, b, c : a^{l} = b^{m} = c^{n} = abc = 1⟩ . (5)

2. The full tiling group T^{∗} acts simply transitively on the tiles of T .

Proof. These facts are well-known, though we give a brief proof sketch for completeness. According to the Poincaré Polygon Theorem [1, p. 249], T^{∗} is a Fuchsian group, i.e., a discrete group of isometries, and a tile is a fundamental region for T^{∗}. Any group element fixing a tile must therefore fix all the interior points of the tile, and equals the identity. Thus, simple transitivity is proven. Now for the first part. First construct the dual graph by joining incentres of adjacent triangles by a segment meeting the common edge of the triangles at a right angle. It is easy to see that every word in T^{∗} corresponds to an edge path in the dual graph starting at the incentre of the master tile. Words which equal the identity correspond to closed paths. Now suppose we have a word corresponding to a closed path. We must show that we can reduce it to the identity by the relations above. Since ℍ is simply connected a closed edge path in the dual graph is homotopic to the identity. Using the homotopy a closed edgepath can be deformed to the identity in a series of moves of the following type: a) introduce or eliminate a path that crosses a tile edge and then goes back, b) replace a path which makes a partial clockwise turn around a vertex with the complimentary counter-clockwise turn around the same vertex. These two types of homotopies correspond to the relations p^{2} = q^{2} = r^{2} = 1 and (pq)^{l} = (qr)^{m} = (rp)^{n} = 1, respectively. This proves that T^{∗} has no other relations. A similar proof works for T. □

Because of the simple transitivity, given a master tile Δ_{0}, there is a unique isometry g ∈ T^{∗} such that Δ = gΔ_{0}. This then allows us to identify a vertex x as being a vertex of type P, Q, or R, depending on which vertex it is equivalent to in the master tile. The same applies to edges. Of course, in scalene triangles the vertex type and edge type are easily identified by angle measure and side length. However in the case of an isosceles triangle it is necessary to use the tiling group action to define types. Similar remarks apply to the quadrilateral with respect to the corresponding tiling groups of an (s, t, u, v)-quadrilateral, which we call Q^{∗} and Q :

Q^{∗} = ⟨ \begin{matrix}w, x, y, z : w^{2} = x^{2} = y^{2} = z^{2} = \\ (wx)^{s} = (xy)^{t} = (yz)^{u} = (zw)^{v} = 1 \end{matrix} ⟩ (6)

and

Q = ⟨d, e, f, g : d^{s} = e^{t} = f^{u} = g^{v} = defg = 1⟩ . (7)

2.2. Divisible Tilings.

Definition 2.5. A kaleidoscopic tiling is said to be divisible if it can be kaleidoscopically divided into a finer tiling. Thus we have two tiles Δ ⊂ Ω both of which generate a kaleidoscopic tiling of the plane. Each tile of the Ω-tiling is a union of polygons from the Δ-tiling. We say that the Δ-tiling subdivides the Ω-tiling. We call (Δ, Ω) a divisible tiling pair.

We have seen an example of a divisible hyperbolic quadrilateral tiling in Figure 1.3 and all examples of divisible tilings of the hyperbolic plane are given in the figures in Section 6. In each of the figures we only give one quadrilateral, though it may be easily extended to the plane through reflections in the sides of the quadrilateral. In fact the following is easily proven by using reflections in the sides of Ω.

Lemma 2.6. Suppose that Δ is a kaleidoscopic tile and that Ω ⊃ Δ is a larger polygon such that Ω is a union of the triangles of the tiling defined by Δ, and that the angles of Ω have measure \frac{π}{m_{i}} for various integers m_{i}. Then (Δ, Ω) is a kaleidoscopic tiling pair.

For the remainder of the paper we shall concentrate on the case where both Δ and Ω are triangles or quadrilaterals and the tilings are geodesic. In almost every case Δ will be a triangle and Ω will be a quadrilateral.

Remark 2.7. There are examples of kaleidoscopic tiling pairs where the tilings may not be geodesic. For example the Euclidean “honeycomb” tiling by hexagons may be subdivided into a tiling by equilateral triangles.

Remark 2.8. For an (l, m, n)-triangle Δ to tile an (s, t, u, v)-quadrilateral Ω each of s, t, u, and v must be a divisor of one of l, m, or n. For, some multiple of an angle of Δ must fit into each corner of the quadrilateral Ω.

The number of triangles. Let the (l, m, n)-triangle Δ and the (s, t, u, v)-quadrilateral Ω with Δ ⊂ Ω form a divisible tiling pair. The areas of the triangle, A_{t}, and quadrilateral, A_{q}, are given (see [1, 150] and [1, 153]) by:

A_{t} = π (1 − \frac{1}{l} − \frac{1}{m} − \frac{1}{n}) = πμ(l, m, n),
A_{q} = π (2 − \frac{1}{s} − \frac{1}{t} − \frac{1}{u} − \frac{1}{v} ) = πν(s, t, u, v),

for some positive rationals μ(l, m, n) and ν(s, t, u, v). Note that we must therefore have

\frac{1}{l} + \frac{1}{m} + \frac{1}{n} < 1 and \frac{1}{s} + \frac{1}{t} + \frac{1}{u} + \frac{1}{v} < 2.

A table of all values of possible (l, m, n) with μ(l, m, n) ≤ \frac{1}{4} is given in Appendix A. These are the only values we shall need for our study. Now Ω is a union of triangles congruent to Δ, let K denote the number of triangles. We have A_{q} = KA_{t} or,

2 − \frac{1}{s} − \frac{1}{t} − \frac{1}{u} − \frac{1}{v} = K (1 − \frac{1}{l} − \frac{1}{m} − \frac{1}{n}) , (8)

or alternatively:

K = \frac{2 − \frac{1}{s} − \frac{1}{t} − \frac{1}{u} − \frac{1}{v}}{1 − \frac{1}{l} − \frac{1}{m} − \frac{1}{n}} = \frac{ν(s, t, u, v)}{μ(l, m, n)}. (9)

It turns out that K has an upper bound of 60 for all triangles in the hyperbolic plane.

Proposition 2.9. Suppose the (l, m, n)-triangle Δ tiles the (s, t, u, v)-quadrilateral Ω. Then,

K = \frac{ν(s, t, u, v)}{μ(l, m, n)} = \frac{2 − \frac{1}{s} − \frac{1}{t} − \frac{1}{u} − \frac{1}{v}}{1 − \frac{1}{l} − \frac{1}{m} − \frac{1}{n}} ≤ 60.

Proof. Fix l, m and n. To maximize K we need to maximize the area of a quadrilateral. Thus each integer s, t, u, and v, should be made as large as possible. Since each of s, t, u, and v must divide one of l, m, or n, then the largest possible quadrilateral is a (b, b, b, b)-quadrilateral such that b is the largest integer selected from l, m, and n. Now the smallest possible value of μ(l, m, n) on the hyperbolic plane is \frac{1}{42} for a (2, 3, 7)-triangle, according to the table in Appendix A. Picking a (7, 7, 7, 7)-quadrilateral as suggested above, we get K = \frac{10}{7}/\frac{1}{42} = 60. For any other triangle we have μ(l, m, n) ≥ \frac{1}{24} with μ(l, m, n) = \frac{1}{24} realized for a (2, 3, 8) triangle. But now

K = \frac{2 − \frac{1}{s} − \frac{1}{t} − \frac{1}{u} − \frac{1}{v}}{1 − \frac{1}{l} − \frac{1}{m} − \frac{1}{n}} < \frac{2}{1/24} = 48.

□

Hubs. Let Ω be an arbitrary quadrilateral and let v be any vertex of the (l, m, n)- tiling contained in the interior or on the boundary of Ω. Assume for the moment that v is of type R. The collection of (l, m, n)-triangles with common vertex at v and contained in Ω will be called an R-hub. If the hub occurs at a corner in Ω then the number of triangles divides l. If the hub occurs on an edge, but not at a corner, then there are exactly l triangles in the hub and a hub occurring in the interior of the quadrilateral has 2l triangles. To distinguish the three types of hubs we call them corner hubs, edge hubs, and interior hubs, respectively. Since we are mainly concerned about edge hubs we just call them hubs, if it will not cause any confusion. An interior hub may be considered to be a union of two edge hubs, then it is called a double hub. The P -hubs and a Q-hubs are defined in the same fashion. When l, m and n are all distinct we refer to the R-hubs, P -hubs and Q-hubs as l-hubs, m-hubs and n-hubs respectively. The various types of hubs are illustrated in the figures in Table 3.1 in the next section.

The number of R-hubs (edge hubs and interior hubs, with interior hubs counted as two hubs) in a subdivided quadrilateral is the number h_{R}, given by:

h_{R} = \frac{K − c_{R}}{l} , (10)

where c_{R} is the number of triangles occurring in the corner R-hubs. We can clearly see that h_{R} must be an integer since the remaining edge hubs have l triangles, the interior hubs have 2l triangles, and every triangle belongs to a unique R-hub. The number c_{R} is usually easily determined from the numbers s, t, u, v. Similar formulas hold for P -hubs and Q-hubs:

h_{P} = \frac{K − c_{P}}{m} , h_{Q} = \frac{K − c_{Q}}{n} . (11)

3. Overview of Quadrilateral Search

We shall employ two different types of search algorithms depending on whether K is large or small. For low values of K we directly construct tilings of quadrilaterals without worrying what the angles are. For large values of K we will develop an algorithm that starts with a specific (l, m, n)-triangle Δ and determines all (s, t, u, v)-quadrilaterals Ω that the triangles can tile. To understand the rationale of splitting the search into two approaches, we need to define constrained and free vertices. We will also obtain constraints and bounds on l, m, n and K that are helpful in restricting the search. These bounds are important for otherwise the computer implementation of the search is impractical.

Definition 3.1. Let Δ ⊂ Ω generate a divisible tiling. Then the P -type vertices of the Δ-tiling are called Ω-constrained if at least one belongs to either an edge hub or an interior hub, i.e., h_{P} > 0. Otherwise the P -type vertices are called Ω-free. Similar definitions hold for Q-type and R-type vertices.

Remark 3.2. As the same triangle tiling can refine two different quadrilateral tilings freeness is relative to Ω, though we rarely mention Ω.

3.1. Free Vertices. The freeness of vertices is exemplified in the figures in Table 3.1. There we show the first four quadrilaterals of the infinite family of (2, 3, 5d) tilings of (d, 5d, d, 5d) quadrilaterals where d ≥ 2. All the quadrilaterals have the same divided structure. The free vertices may be “freely” dragged to the boundary of the hyperbolic plane through an infinite discrete set of positions. (In contrast, a constrained vertex cannot since it has a fixed measure.) The angles at the free vertices become smaller and smaller as we approach the boundary until we reach a (2, 3, ∞) tiling of an (∞, ∞, ∞, ∞)-quadrilateral. The free vertices are on the boundary and have measure 0 = \frac{π}{∞}. As we prove below, every divisible tiling with free vertices gives rise to such an infinite family of tilings.

Remark 3.3. Free vertices, or rather the lack of them play a special role in the interpretation and calculation of the “monodromy group” T^{∗}/core_{T^{∗}}(Q) of the tiling pair Δ ⊂ Ω. This group and its relation to tiling groups of surfaces with divisible tilings are discussed in greater detail in [8] and in the forthcoming paper [4].

The search algorithm for quadrilaterals with free vertices has to be handled differently from those with constrained vertices only, since there are infinitely many possibilities. Also, it turns out that the quadrilaterals with small numbers of triangles have free vertices and those with a large number of triangles have only constrained vertices, and for the midrange of values of K we have both types. We define special K to be the number such that for any tiling pair Δ ⊂ Ω with K > special K the divisible tiling has only constrained vertices. For values below or equal to special K we will use one algorithm and for those values above special K we will use another algorithm. The following proposition specifies special K.

Proposition 3.4. Let Δ ⊂ Ω be an arbitrary kaleidoscopic tiling pair consisting of an (l, m, n)-triangle Δ and an (s, t, u, v)-quadrilateral. Let

K = \frac{2 − \frac{1}{s} − \frac{1}{t} − \frac{1}{u} − \frac{1}{v}}{1 − \frac{1}{l} − \frac{1}{m} − \frac{1}{n}}

Table 3.1. A family of divisible quadrilaterals with free vertices

(2, 3, 10) tiling of (2, 10, 2, 10)  (2, 3, 15) tiling of (3, 15, 3, 150)

(2, 3, 20) tiling of (4, 20, 4, 20)  (2, 3, 25) tiling of (5, 25, 5, 25)

be the number of triangles covering Ω. Then if K > 12 then there are no Ω-free vertices in the Δ-tiling, i.e., special K equals 12. Furthermore if there are two types of free vertices then K ≤ 4 and if there are 3 types of free vertices then K = 2.

Proof. The examples in Table 3.1 show that special K is 12 or greater. Now suppose that Δ ⊂ Ω is a tiling pair such that Q is a free vertex. We shall first construct an infinite family of divisible quadrilaterals all with the same structure. Assume that our tile Δ has sides p and q meeting at the origin at R in an angle \frac{π}{l}, so that q is a portion of the positive x-axis and p is a diameter in the first quadrant. The third side r of our triangle is a portion of a (euclidean) circle in the first quadrant meeting q at P in an angle \frac{π}{m}, meeting p at Q in an angle \frac{π}{n}, and meeting the boundary at right angles. (see the figures in Table 3.1). Now each triangle in the quadrilateral is of the form g_{i}Δ where g_{1}, …, g_{K} ∈ T^{∗}. For the quadrilaterals in the examples the 12 different g’s are 1, q, qr, qrp, qrpr, qrprq, pq, p, pr, prp, prpr, prprq. Move the side r so that its point of intersection moves along the x-axis, but the angle remains \frac{π}{m}. The moving line, denoted r_{N}, will intersect the diameter p in an angle \frac{π}{N} that varies continuously from π(1 − \frac{1}{l} − \frac{1}{m}) (when the point of intersection is at the origin) down to 0 (when the side r_{N} meets p on the boundary). Let Δ_{N} denote the triangle bounded by p, q, r_{N} and let p, q, r_{N} also denote the reflections in the sides of Δ_{N}. Now let g_{i}(N) be the isometry constructed from g_{i} by the replacements p → p, q → q, and r → r_{N}. Because Q is a free vertex then

⋃_{i=1}^{K} g_{i}(N)Δ_{N}

is a quadrilateral whose subdivided combinatorial structure is independent of N. The angles at Q-vertices have measure \frac{ρ_{i}π}{N} , where ρ_{1}, …, ρ_{k} are the numbers of triangles meeting at Q-vertices. In our example k = 4, ρ_{1} = ρ_{3} = 1, and ρ_{2} = ρ_{4} = 5. Let ρ be the least common multiple of the ρ_{i}’s. There are now an infinite number of integer values of N = ρd, d = d_{0}, d_{0} +1, … ∈ ℤ such that \frac{N}{ρ_{i}} = \frac{ρ}{ρ_{i}} d is an integer for all Q vertices, and such that the resulting (l, m, N)-triple corresponds to a hyperbolic triangle. The resulting quadrilaterals, of type (s_{N}, t_{N}, u_{N}, v_{N}), for appropriately selected integers, will then form our infinite family of kaleidoscopic quadrilaterals. If the other types of vertices are free then a multiparameter family may be created.

Finally let us get a bound on K. We know that

K = \frac{2 − \frac{1}{s_{N}} − \frac{1}{t_{N}} − \frac{1}{u_{N}} − \frac{1}{v_{N}}}{1 − \frac{1}{l} − \frac{1}{m} − \frac{1}{N}} ≤ \frac{2}{1 − \frac{1}{l} − \frac{1}{m} − \frac{1}{N}}

Now we may chose (l, m, N) of the form (l, m, ρd) so that

K ≤ lim_{d→∞} \frac{2}{1 − \frac{1}{l} − \frac{1}{m} − \frac{1}{ρd}} = \frac{2}{1 − \frac{1}{l} − \frac{1}{m}} .

The largest possible side for the right hand side is 12 when l = 2, m = 3. The next largest size is K = 8 for l = 2, m = 4. If there are two or three types of free vertices then a two or three parameter family limit calculation shows that K ≤ 4 and K ≤ 2, respectively. □

3.2. Constrained Vertices. We have established a limit on K when there are free vertices, we may establish a limit on l, m, n when there are only constrained vertices. We shall also show that l, m, and n must be chosen from the table in Appendix A.

Proposition 3.5. Let Δ ⊂ Ω be an arbitrary kaleidoscopic tiling pair consisting of an (l, m, n)-triangle Δ and an (s, t, u, v)-quadrilateral. Let

K = \frac{2 − \frac{1}{s} − \frac{1}{t} − \frac{1}{u} − \frac{1}{v}}{1 − \frac{1}{l} − \frac{1}{m} − \frac{1}{n}}

be the number of triangles covering Ω. Then if all the vertices of the Δ-tiling are constrained then

l, m, n ≤ K. (12)

Proof. If the R-vertices are constrained then there is at least one R-hub and hence at least l triangles. But then K ≥ l. The proofs of the other inequalities are identical. □

The above proposition implies that the universal bound of 60 is also a bound for l, m, n when we have constrained vertices. However we can do much better than this. Assume that l ≤ m ≤ n. Then, s, t, u, v ≤ n and

ν(s, t, u, v) = 2 − \frac{1}{s} − \frac{1}{t} − \frac{1}{u} − \frac{1}{v} ≤ 2 − \frac{1}{n} − \frac{1}{n} − \frac{1}{n} − \frac{1}{n} = ν(n, n, n, n).

It follows that

l, m, n ≤ K ≤ \frac{ν(n, n, n, n)}{μ(l, m, n)}. (13)

Thus, for instance, for a (2, 3, n) triangle we have

n ≤ \frac{2 − \frac{4}{n}}{\frac{1}{6} − \frac{1}{n}} = 12\frac{n − 2}{n − 6}.

Solving this inequality for integer solutions, we obtain 3 ≤ n ≤ 16. Since the triangle is hyperbolic then we further restrict 7 ≤ n ≤ 16. Analogously, for (2, 4, n) triangles we get 5 ≤ n ≤ 10, and for (3, 3, n) triangles we have 4 ≤ n ≤ 7.

Now let us obtain a lower bound for K when there are constrained vertices.

Proposition 3.6. Let Δ ⊂ Ω be a kaleidoscopic tiling pair with only constrained vertices. Then the number of triangles, K, is at least six.

Proof. Suppose that Ω has at least one interior hub. Then the proposition is satisfied unless the interior hub has four triangles. If there are only 4 triangles then the two other vertices are free. Suppose there are five triangles. Then, adjoining a single triangle to an interior hub of 4 will force us to have at least one edge hub with three triangles. In turn this will force an equivalent vertex to be a corner hub with exactly two angles of measure \frac{π}{3} , which is not allowed. In fact the hub of four must be completed to a quadrilateral tiled with six triangles as in case F12 in Table 6.6.

Thus we may assume that there are no interior hubs and that there is an edge hub for each different type of vertex, say a P -hub H_{P} , centered at V_{P}, a Q-hub H_{Q}, centered at V_{Q}, and an R-hub H_{R}, centered at V_{R}. The number of triangles in at least one of the hubs satisfies |H_{P} ∪ H_{Q} ∪ H_{R}| ≤ K. We shall estimate |H_{P} ∪ H_{Q} ∪ H_{R}| by inclusion-exclusion and arrive at a contradiction. We have:

|H_{P} ∪ H_{Q} ∪ H_{R}| = |H_{P} | + |H_{Q}| + |H_{R}|
− |H_{P} ∩ H_{Q}| − |H_{P} ∩ H_{R}| − |H_{Q} ∩ H_{R}|
+ |H_{P} ∩ H_{Q} ∩ H_{R}|
= l + m + n
− |H_{P} ∩ H_{Q}| − |H_{P} ∩ H_{R}| − |H_{Q} ∩ H_{R}|
+ |H_{P} ∩ H_{Q} ∩ H_{R}| .

Now |H_{P} ∩ H_{Q}| = 0 unless V_{P} and V_{Q} are vertices of the same triangle. Furthermore, |H_{P} ∩ H_{Q}| = 1 if the edge joining V_{P} and V_{Q} is part of an edge of Ω and |H_{P} ∩ H_{Q}| = 2 otherwise. Also |H_{P} ∩ H_{Q} ∩ H_{R}| = 1 if V_{P} , V_{Q}, and V_{R} are the vertices of the same triangle and it is zero otherwise. If |H_{P} ∩ H_{Q}| = |H_{P} ∩ H_{R}| = |H_{Q} ∩ H_{R}| = 2 then |H_{P} ∩ H_{Q} ∩ H_{R}| = 1 and |H_{P} ∪ H_{Q} ∪ H_{R}| = l + m + n − 5.

On the other hand if |H_{P} ∩ H_{Q} ∩ H_{R}| = 0 then one of |H_{P} ∩ H_{Q}| , |H_{P} ∩ H_{R}| , and |H_{Q} ∩ H_{R}| is zero so |H_{P} ∪ H_{Q} ∪ H_{R}| ≥ l + m + n − 4. Thus in all cases we have

l + m + n − 5 ≤ |H_{P} ∪ H_{Q} ∪ H_{R}| ≤ K ≤ 5, or
l + m + n ≤ 10.

Now as we go through hyperbolic (l, m, n)-triples in Appendix A we see that there is only one triple that satisfies this namely (3, 3, 4). The quadrilateral must contain one hub of order 4, but it is impossible to add a single triangle to make it into quadrilateral. We have eliminated all cases. □

The inequality (13) combined with K ≥ 6 shows that we get an area restriction μ < \frac{1}{3}. We now prove a stronger restriction μ ≤ \frac{1}{4}, which allows us to select all our μ-data from the table in Appendix A.

Proposition 3.7. If an (l, m, n)-triangle subdivides an (s, t, u, v)-quadrilateral, with only constrained vertices then μ(l, m, n) ≤ \frac{1}{4}.

Proof. Suppose that μ = μ(l, m, n) > \frac{1}{4}. Let ν = ν(s, t, u, v), we know that ν ≤ 2 and so thus

K = \frac{ν}{μ} < \frac{2}{1/4} = 8.

Since K must be an integer, and K ≥ 6 by our last proposition, then 6 ≤ K ≤ 7. Also, by Proposition 3.5, l, m, n ≤ K, so we may assume, without loss of generality, l ≤ m ≤ n ≤ 7. We consider four cases. Case 1. n = 7, K = 7. There exists exactly one 7-hub and no other triangles. However it is not possible to select the other angles to form a quadrilateral. Case 2. n = 6, K = 6, 7. There is exactly one 6-hub. At most one other triangle can be added and thus either 2 or possibly 3 triangles meet at the vertices. Since there is at least one hub of each type, then the only possible hyperbolic triangle is (3, 3, 6). However this satisfies μ ≤ \frac{1}{4}. Case 3. n = 5, K = 6, 7. Again there is exactly one 5-hub and one or two triangles must be added. Thus, except at the 5-hub, 2, 3 or 4 triangles meet at each vertex. The only hyperbolic possibilities are (2, 4, 5), (3, 3, 5), (3, 4, 5), and (4, 4, 5) triangles. The first satisfy two satisfy μ ≤ \frac{1}{4} and for the last two the upper bound \frac{ν(n,n,n,n)}{μ(l,m,n)} for K is smaller than 6. Case 4. n = 4, K = 6, 7. The only possible triangles are (3, 3, 4), (3, 4, 4), and (4, 4, 4) triangles, all of which satisfy the inequality.

Since there are no hyperbolic triangles with n ≤ 3, the proof is complete. □

Remark 3.8. After constructing the tables we may actually verify that μ(l, m, n) ≤ \frac{1}{6}.

3.3. The Two Search Methods. The existence of free vertices and families of divisible tilings forces us to split our search into two different approaches: the direct construction method (K ≤ 12) and the boundary construction method (K > 12). We describe the two approaches very briefly here and then devote one section each to the full description, implementation, and computational examples of both methods Direct construction method (K ≤ 12). Assume for the moment that there are no interior hubs. Then each edge of a triangle must either be a part of the side of the quadrilateral or reach from one side of the quadrilateral to another. Thus, as a “combinatorial” object the quadrilateral may be viewed as a circle with a set of non-intersecting chords or a better yet as a polygon with K + 2 vertices and with a collection of K − 1 diameters (see Figure 4.1 below). The diameters of the vertices can then be labeled as P, Q, R vertices via the tiling structure. In order to transform the polygon into a quadrilateral triangle K − 2 corners of the polygon must be flattened to straight angles, leaving four corners to form a quadrilateral. This imposes restrictions on l, m, and n, and allows us to compute s, t, u, and v or conclude that no tiling pair exists. The algorithm can be extended to the case where there are interior hubs. The algorithm depends only on the combinatorial structure of the polygon and not the actual angles so it can handle the case of free vertices. Unfortunately, the computational complexity of the computer search rises very quickly with K, and is not useful for large numbers of triangles. Boundary construction method (K > 12). If K > 12 then there is only a finite number of possibilities for (l, m, n) and hence a finite number of possibilities for (s, t, u, v), according to Remark 2.8. For each compatible pair of an (l, m, n) and (s, t, u, v) we try to construct an (s, t, u, v)-quadrilateral in the (l, m, n)-tiling by constructing the possible boundaries of a quadrilateral. The tile edges must occur in certain sequences in the tiling, thus the boundary can be constructed “combinatorially”. By making a geometric check we can tell whether the hypothesized boundary closes up, and hence forms a quadrilateral. Again there is only a finite number of cases to check.

4. Direct Construction Method (K ≤ 12)

We are first going to show that all divisible quadrilaterals may be constructed from a collection of Euclidean polygons, subdivided into K triangles and their combinatorial analogs. By using the dual graph we will show the existence of an algorithm that allows us to inductively construct all such polygons by attaching triangles, interior hubs and conglomerations of interior hubs to a polygon with a fewer number of triangles. Each such polygon may then be tested to see if it yields a quadrilateral.

An associated divided polygon is constructed as follows. See Figures 4.1 and 4.3 below for examples without interior hubs. In Figure 4.2 an associated polygon with interior hubs has been drawn along with its dual graph discussed below. Let P_{1}, …, P_{n} be the vertices of the triangular tiling of Ω as we move clockwise around Ω. Construct a convex Euclidean n-gon whose vertices are labeled P_{1}, …, P_{n}. Add in all diagonals P_{i}P_{j} that correspond to edges of the tiling contained in Ω. Next we add points into the interior of the polygon corresponding to vertices of the tiling in the interior of Ω. We denote these vertices by Q_{1}, …, Q_{s} (see Figure 4.2 below). We further add in all the segments Q_{i}P_{j} and Q_{i}Q_{j} corresponding to edges of tiling interior to Ω. A combinatorial representation of the associated divided polygon or combinatorial divided polygon may then defined as the quintuple ({P_{i}}, {P_{i}P_{j}}, {Q_{i}}, {Q_{i}P_{j}}, {Q_{i}Q_{j}}) = (V_{∂}, E_{∂}, V_{i}, E_{i∂}, E_{i}) where each component is taken over the appropriate index set. Note that the set E_{∂} = {P_{i}P_{j}}, the set of all edges connecting boundary points, contains all the segments P_{i}P_{i+1}, 1 ≤ i ≤ n−1,

Figure 4.1. Polygon without interior hubs

and P_{n}P_{1}. The combinatorial representation is what we use for computer representation and calculation, the Euclidean polygon realization serves for visualization. Note that the same set of associated polygons also arises from a pentagon, hexagon etc., tiled by a triangle. The two critical features we need for the associated polygon are:

• it is a convex n-gon that is subdivided into triangles, and

• an even number of triangles meet at each interior vertex.

In order to prove that we may inductively construct all the associated polygons we work with a modification of the dual graph of an associated polygon. This is constructed as follows. Place a node in the interior of each of the triangles. Connect the nodes of neighbouring triangles by an arc crossing the common boundary. The constructed graph has cycles if and only if there are interior hubs. See Figure 4.2 for a combined picture of an associated polygon and its dual graph. The graph has the following properties, though we don’t use them all.

• It is planar.

• Each node is connected to at most three other nodes.

• The arcs of the graph may be coloured according to which type of edge they cross.

• The minimal cycles have an even number of nodes.

• The region enclosed by a minimal cycle contains no other point of the graph. We construct the modified dual graph as follows. For each interior hub, fill in the

portion of the dual graph bounded by the corresponding cycle. We could achieve this by blackening in the two quadrilaterals in the dual graph in Figure 4.2. The resulting object consists of nodes, arcs, isolated hubs and conglomerated hubs. An

Figure 4.2. Polygon and dual graph

isolated hub is one which is connected to another node or hubs by an arc only as in Figure 4.2. A conglomerated hub is one or more hubs joined together, as in cases F30, F31, and F33 in Table 6.6. There are some restrictions on the hubs and conglomerated hubs. The modified dual graph has a tree-like structure and therefore can be constructed by adding one component at a time. This leads to the following proposition which is the basis of our combinatorial search.

Proposition 4.1. Let Λ be the associated subdivided polygon constructed from a tiled quadrilateral. Then there is a sequence of associated subdivided polygons Λ_{0}, Λ_{1}, …, Λ_{s} = Λ such that Λ_{0} is empty and each Λ_{i+1} is obtained from Λ_{i} by adjoining a triangle, hub or conglomerated hub along a single edge.

Proof. If we replace each hub and conglomerated hub by a node then we obtain a tree. This follows from the fact that the modified dual graph is simply connected because it a deformation retract of a quadrilateral. Trees may be constructed by starting at any single node and then connecting additional nodes, one at a time, by exactly one arc each. This method of tree construction directly translates into the statement about adjoining the components of the associated polygons. □

4.1. Polygon Construction and Elimination—No Interior Hubs. Let us first concentrate on those associated polygons with no interior hubs, as the development is simpler. The case for polygons with interior points requires a few modifications which are described below. Let P_{K} be the set of polygons subdivided into K triangles without any interior vertices. The dual graph of any one of these polygons is a tree with K nodes and K − 1 arcs. Now 3K sides are contributed by the triangles, 2(K − 1) of which are absorbed as interior edges corresponding to the K − 1 arcs. Thus there are K + 2 triangle sides on the boundary and that many

Figure 4.3. Associated polygons for K = 4

vertices as well. In this case we are going to geometrically represent the associated polygon by a regular polygon for the following reasons. The first is that the number of such polygons is well known to be a Catalan number (see [7, p. 457])

|P_{K}| = c(K) = \frac{\binom{2K}{K}}{K + 1},

and hence we will call the associated divided polygons Catalan polygons. This will help us in making sure that enumeration is complete. The second is that we may use the dihedral symmetries of regular polygons to reduce the computational complexity. Clearly, dihedrally equivalent associated polygons will lead to the same

divisible quadrilateral, if any. Since |P_{12}| = \frac{\binom{24}{12}}{13} = 208 012, some reduction in complexity is desirable. The following proposition demonstrates that the complexity is reduced for low values of K.

Proposition 4.2. Let P_{K} denote the set of subdivisions of regular (K+2)-polygons into K triangles. Let OP_{K} denote the set of dihedral equivalence classes of the subdivided regular polygons. Let c(K) = |P_{K}| as above, oc(K) = |OP_{K}|. Then oc(K) is given by:

oc(K) = \frac{c(K) + (K + 2)c(\frac{K−1}{2})}{2(K + 2)}, K = 3, 5 mod 6,

oc(K) = \frac{c(K) + \frac{2(K+2)}{3}c(\frac{K−1}{3}) + (K + 2)c(\frac{K−1}{2})}{2(K + 2)}, K = 1 mod 6

oc(K) = \frac{c(K) + (K + 2)c(\frac{K}{2} ) + \frac{(K+2)}{2} ∑_{s=0}^{K/2−1} c(s)c(\frac{K}{2} − 1)}{2(K + 2)}, K = 0, 2 mod 6

and

oc(K) = \frac{c(K) + \frac{2(K+2)c( \frac{K−1}{3} )}{3} + (K + 2)c(\frac{K}{2} ) + \frac{(K+2)}{2} ∑_{s=0}^{K/2−1} c(s)c(\frac{K}{2} − 1)}{2(K + 2)},

for K = 4 mod 6. The growth is still exponential but at least is manageable for K ≤ 12, since oc(12) = 7528, and oc(K) ∽ c(K)/(2K + 4). The formulas are given in [5] and further references are listed in sequence M2375 of the Sloan integer sequence reference [11].

The adjoining process leads to a combinatorial divided polygon ({P_{i}}, {P_{i}P_{j}}, ϕ, ϕ, ϕ). The next step is to determine which (l, m, n) lead to divisible hyperbolic quadrilaterals. To do this we need to determine the type of the vertices on the boundary. Suppose that P_{i}P_{j}, P_{j}P_{k}, and P_{k}P_{i}, are the three edges of an arbitrarily chosen triangle Δ = ΔP_{i}P_{j}P_{k}, contained in Ω. Declare the types of P_{i}, P_{j}, and P_{k} to be P, Q,and R, respectively. The reflection of Δ in at least one of its sides must lie in Ω. Suppose for the sake of argument that this side is P_{i}P_{j}. Then there must be a P_{k′} such that P_{j}P_{k′} and P_{k′}P_{i} belong to the edge set of our combinatorial polygon. Now P_{k′} is the reflected image of P_{k} and so they must have the same type, namely R. Since the P_{k′} is found by examining only the combinatorial data ({P_{i}}, {P_{i}P_{j}}) we say that P_{k′} is the combinatorial reflection of P_{k}. Combinatorial reflection may be continued until every vertex is assigned a unique type.

Once the vertices have been assigned a type then the vertices of type R, P and Q may be assigned an angle of \frac{π}{l} , \frac{π}{m}, \frac{π}{n}. Let m_{i} be the integer so chosen for P_{i}. Next we assign to each vertex P_{i} the number s_{i} of triangles that meet at the vertex. This can be determined combinatorially by noting that there must be s_{i} + 1 edges of the form P_{i}P_{j} in the edge set E_{∂}. The angle measure at vertex P_{i} is \frac{s_{i}}{m_{i}} π. Finally we must select four vertices in V_{∂} to serve as the corners of the quadrilateral, or actually K − 2 corners to flatten into a straight angle. At this stage many of the configurations are eliminated.

Let us illustrate the process by discussing the case K = 4. Though |P_{4}| = 14 there are only 3 dihedrally inequivalent associated polygons. See Figure 4.3. The list of vertices, in counter-clockwise order, starting at the “3 o’clock vertex”, the vertex types, and the angle measures divided by π, are as given in the following table

Vertex Case 1 Case 2 Case 3
P_{1}  P, \frac{1}{m} P, \frac{1}{m} P, \frac{1}{m}
P_{2}  Q, \frac{4}{n}  Q, \frac{3}{n}  Q, \frac{3}{n}
P_{3}  P, \frac{1}{m} R, \frac{2}{l}  R, \frac{1}{l}
P_{4}  R, \frac{2}{l}  Q, \frac{1}{n}  P, \frac{3}{m}
P_{5}  P, \frac{2}{m} P, \frac{3}{m} Q, \frac{1}{n}
P_{6}  R, \frac{2}{l}  R, \frac{2}{l}  R, \frac{3}{l}

Now from the six vertices we must select two to flatten out to a straight angle, the remaining vertices are corners of the quadrilateral. To be a straight angle we must have \frac{s_{i}}{m_{i}} π = π or s_{i} = m_{i}. This automatically forces corners with a single triangle to be a quadrilateral corner, as is geometrically obvious. In Case 1 we can either choose {P_{4}, P_{6}} or {P_{2}, P_{5}} to flatten. For, P_{1} and P_{3} cannot be chosen and if we choose one of P_{4} or P_{6} we are forced to also choose the other since the angle measure for both is \frac{2}{l}π. If we choose \{P_{4}, P_{6}\} then l = 2, and both \frac{4}{n} and \frac{2}{m} are reciprocals of integers. It follows that (l, m, n) must have the form (2, 2d, 4e) and (s, t, u, v) must have the form (2d, e, 2d, d). The values of d and e are d ≥ 2, e ≥ 1 except that d = 2, e = 1 is disallowed since Δ would then be Euclidean. If we choose {P_{2}, P_{5}} , then n = 4, m = 2, and (l, m, n) must have the form (2d, 2, 4) and (s, t, u, v) must have the form (2, 2, d, d), with d ≥ 3. The complete analysis of K = 4 without interior hubs is given in the table below.

Case flattened corners (l, m, n) (s, t, u, v)  restrictions
1  P_{4}, P_{6}  (2, 2d, 4e) (2d, e, 2d, d) d ≥ 2, e ≥ 1, (d, e) ≠ (2, 1)
1  P_{2}, P_{5}  (2d, 2, 4) (2, 2, d, d) d ≥ 3
2  P_{3}, P_{6}  (2, 3d, 3e) (3d, e, 3e, d) d, e ≥ 2
2  P_{2}, P_{5}  (2d, 3, 3) (3, d, 3, d) d ≥ 2
3  P_{2}, P_{4}  (3d, 3, 3) (3, 3d, 3, d) d ≥ 2

For larger values of K the “wheat to chaff ratio” decreases drastically so we need to identify some methods of quickly rejecting combinatorial polygons. Let R_{1}, …, R_{L} be the vertices of type R and let λ_{1}, …, λ_{L}, be the angle multiplicities at these points. Define P_{1}, …, P_{M}, μ_{1}, …, μ_{M}, and Q_{1}, …, Q_{N}, ν_{1}, …, ν_{N} be similarly defined. These quantities satisfy the following relations:

L + M + N = K + 2
λ_{1} + … + λ_{L} = K
μ_{1} + … + μ_{M} = K
ν_{1} + … + ν_{N} = K

Next let l_{λ} = lcm(λ_{1}, …, λ_{L}) and write λ_{i} = \frac{l_{λ}}{s_{i}} . There only two ways that we can assign an angle \frac{π}{l} to R-vertices so that λ_{i} \frac{π}{l} is an integer submultiple of π. Either we set the angle to be \frac{π}{l_{λ}} , in which case the angle of the hub at R_{i} is λ_{i} \frac{π}{l_{λ}} = \frac{π}{s_{i}} or we set it to \frac{π}{l_{λ}d}, d ≥ 2, and then the angle at hub at R_{i} is λ_{i} \frac{π}{l_{λ}d} = \frac{π}{s_{i}d}. In the first case we get an edge hub for each s_{i} = 1 otherwise we get a corner hub. In the second case every hub is a corner hub and we get a free vertex. Similar considerations apply to the vertices of type P and Q.

An example will help illustrate. Consider the associated polygon for K = 10 in Figure 4.1. Proceeding counter-clockwise around the polygon from the three o’clock position vertices may be labeled R, P, Q, P, R, Q, P, R, Q, R, P, Q with multiplicities 3, 3, 4, 1, 3, 1, 3, 3, 4, 1, 3, 1. The sequences of multiplicities are:

{λ_{i}} = {3, 3, 3, 1}, {μ_{i}} = {3, 1, 3, 3}, {ν_{i}} = {4, 1, 4, 1}.

Thus we can choose either 1 or 4 corner hubs of type R, 1 or 4 corner hubs of type P, and 2 or 4 corner hubs of type Q. Of the eight possible choices only one yields a quadrilateral, namely, l = 3, m = 3, and n = 4 yielding 1, 1, and 2 corner hubs of types R, P and Q respectively. Thus we get a (3, 3, 4) ⊂ (3, 4, 3, 4) tiling pair yielding case C7 in Table 6.7. Note, for instance, that this method also allows us to construct a (d, 3, 4d, d, 3, 4d) hexagon tiled by a (3, 3, 4d) triangle.

4.2. Computer Algorithm and Extension to Interior Hubs. Two Maple worksheets catpolys.mws and hubpolys.mws [15] were used to implement the search for divisible quadrilaterals with K ≤ 12. Maple was used so that the graphical capabilities could be used to draw various polygons (such as the figures in this section) to check the logic of the program during development. The algorithm steps were the following.

1. Create a sequence of files F_{K} containing the representatives of each dihedral equivalence class of Catalan polygons with a given number of sides.

a) Start off with F_{1} consisting of a triangle. b) From F_{K} create the file G_{K+1}, consisting of all polygons that can be

created from polygons in F_{K} by adding a triangle to each side of a polygon from F_{K}. The polygons are created as an ordered list.

c) Create an empty file F_{K+1}. Place the first element of G_{K+1} in F_{K+1}. Create the dihedral orbit of first element of G_{K+1}, and then remove this list of polygons from G_{K+1}. Repeat the procedure until G_{K+1} is empty.

2. For each polygon in F_{K} do the following:

a) Compute the multiplicity of all vertices.

b) Label P_{1} and P_{2}, R and Q respectively. Find the unique point P = P_{k} which completes the triangle. Now repeatedly use combinatorial reflection to label vertices of the polygon with P, Q or R. This part can be written so that it is guaranteed to terminate.

c) Construct the {λ_{i}}, {μ_{j}}, {ν_{k}} and determine all possible assignments of l, m, and n that lead to 4 vertices which are corners. This part can be easily modified to find tilings of pentagons, hexagons, etc.

d) Collect the valid assignments into a file Q_{K}.

The algorithm for the case of interior hubs requires just a few modifications.

1. Construct by hand a list consisting of a triangle and all hubs and conglomerated hubs with twelve or less triangles.

2. Start off with F_{4} containing the hub of 4. Next create G_{5} by adding triangles to the element in F_{4} at all possible locations.

3. Find representatives of the dihedral orbits and place them in F_{5}.

4. Construct further G_{K} by attaching a triangle, hub or conglomerated hub to polygons in sets with smaller numbers of triangles, so that the total number of triangles is K. The first non-triangle addition will be a hub of 4 to another hub of 4. Create F_{K} to be a set of representatives of dihedral orbits.

5. Create a labeling scheme for all vertices including interior vertices.

6. Create all valid assignments of angles to boundary vertices.

7. Check for compatibility with interior vertices, since the angles here are predetermined.

5. Boundary Construction Method (K > 12)

The boundary construction method was used for all divisible tilings for which K > 12, since in this case we are guaranteed that the tiling has no free vertices and hence there are only a finitely many (l, m, n)-triangles to consider. After describing the methods in the next two subsections we will do some sample calculations to illustrate the ideas.

According to the discussion in the previous sections we shall do the following.

1. Enumerate all of the (l, m, n)-triangles for which l ≤ m ≤ n, μ(l, m, n) ≤ \frac{1}{4}, l, m, n ≤ 60, and n ≤ (2 − \frac{4}{n})/μ(l, m, n). The table of μ-values in Appendix A can be used here.

2. For each triangle in Step 1, enumerate all candidate quadruples (s, t, u, v) formed from l, m, n. The numbers s, t, u, v must be selected from the divisors of l, m, n which are greater than 1.

3. For each candidate pair of an (l, m, n) and an (s, t, u, v) select those which pass the K-test and the hub tests, i.e., the quotients calculated in (9), (10) and (11) must be integers. In addition we eliminate those cases in which K = \frac{ν(s,t,u,v)}{μ(l,m,n)} ≤ 12, since these have already been determined by the direct construction method.

4. For each candidate pair resulting from 3, enumerate all possible assignments of vertex types of the triangle to the quadrilateral. This allows us to take multiple corners into account.

5. For each candidate pair resulting from 4, perform the quadrilateral search

algorithm, as we describe next. Quadrilateral Search. Having found an (l, m, n) and an (s, t, u, v) such that all the restrictions in 1–4 hold, quadrilaterals tiled by the triangle are sought out using a Maple program tilequad.mws (see [15]). Two somewhat different programs were developed, though they differ only in how the quadrilateral test is implemented. The quadrilateral search program is given an (l, m, n)-triangle, and a quadruple (s, t, u, v) and tries to find to a corresponding quadrilateral along the lines of the triangle tiling.

Look at Figures 5.1–5.3 or the figures in the tables in Section 6 to help understand how the algorithm works. In addition to the information (l, m, n) and (s, t, u, v) we need an assignment of vertex types and hub multiplicities to the corners of the quadrilateral. We must consider all compatible type assignments. For example if (l, m, n) = (2, 4, 5) and (s, t, u, v) = (2, 4, 2, 4) then the possible vertex assignments are (R, P, R, P), (P, P, R, P), (R, P, P, P) and (P, P, P, P) with hub multiplicities (1, 1, 1, 1), (2, 1, 1, 1), (1, 1, 2, 1) and (2, 1, 2, 1), respectively. Special attention needs to be paid to isosceles triangles. For instance, in attempting to tile a (5, 5, 5, 5) with a (2, 5, 5), 16 = 2^{4} type assignments should be considered.

Suppose that the type assignment is (S_{1}, S_{2}, S_{3}, S_{4}), where S_{i} ∈ {P, Q, R}. The algorithm starts by picking the vertex A′ of type S_{1} on the master tile. Pick an edge of the angle at A′ and move out along the ray determined by this edge. We move along the ray and observe the triangles we meet on the same side of the ray as our original triangle. We stop at some (there are many choices) triangle whose second vertex encountered is of type S_{2}. Call this vertex B′, our first side will be A′B′ (see Figures 5.2 and 5.3). To get the second side we turn the corner through π − \frac{π}{t} radians toward the side of the original triangle and proceed along the next ray in the tiling and stop at a vertex of type S_{3}, say C′ to produce the second side B′C′. Because of the compatibility conditions, when we turn the corner we will move out along a line of the tiling. Turn again through π − \frac{π}{u} radians to produce a third side C′D′ and turn again to produce a fourth side D′E′. When we have finished, if A′ = E′ and angle D′A′B′ has measure \frac{π}{s} then we have a quadrilateral of the desired type. Note that there are only a finite number of possibilities for each side of the quadrilateral since the number of hubs on the edges is bounded by the hub numbers, as illustrated in the attempted (2, 3, 7) tiling of a (7, 7, 7, 7) quadrilateral later in this section. Now the program keeps track of the four “combinatorial” sides of the quadrilateral by writing down the sequence of vertex types that we pass through as we move along an edge of the proposed boundary of the quadrilateral. This follows from the following observation:

Remark 5.1. Let ℓ be a line of the tiling, and let …, S_{−1}, S_{0}, S_{1}, … be the biinfinite sequence of types of vertices lying on ℓ, in the order in which they occur. Then, the entire sequence is determined by the types of two adjacent vertices. For example, in a (2, 3, 7) triangle only one sequence occurs {…, R, P, Q, R, Q, P, … } . In a (2, 4, 5) triangle ΔRP Q, two different sequences occur {…, R, P, … } and {…, P, Q, R, Q, … } . For a (2, 4, 6) triangle three sequences occur {…, R, P, ….} , {…, R, Q, … } , and {…, P, Q, … }. In each of the sequences above, the entire sequence is the bi-infinite cyclic repetition of the basic pattern shown. The pattern types only depend on parity of the numbers l, m, and n.

Now that we have the four edges, how can we determine if it is a quadrilateral with the correct angles. There are two methods that were used, which are explained in the next two subsections.

Remark 5.2. Though one really only needs one type of test, two were developed for the following reasons. The first test is faster to calculate and less susceptible to round off error. The second test produces “boundary words” which can be used to determine a surface of minimum genus which supports both tilings. See [4].

5.1. Geometric Quadrilateral Test. The first method uses the construction of a quadrilateral given by the following proposition which is proved in [2].

Proposition 5.3. Let α, β, γ, δ be four angles satisfying 0 < α, β, γ, δ ≤ \frac{π}{2} and α + β + γ + δ < 2π. Then for every value of h satisfying

(14) h > \frac{cos α cos β + 1}{sin α sin β}

there is a quadrilateral ABCD, unique up to congruence, such that

m(∠DAB) = α, m(∠ABC) = β,
m(∠BCD) = γ, m(∠CDA) = δ,

and

AB = h.

The algorithm so far has given us a set of points A′, B′, C′, D′, E′, such that all the lengths are known from the lists of points on the edges. For, the lengths of the sides of the triangles are easily computed and the types of all edges comprising a side of a quadrilateral are known. Let h be the length of the side \overline{A′B′} and construct quadrilateral ABCD as in the proposition above with α = \frac{π}{s} , β = \frac{π}{t} , γ = \frac{π}{u}, δ = \frac{π}{v} . The algorithm constructs the points A, B, C, D in the unit disc and so the lengths \overline{BC}, \overline{CD}, and \overline{DA} may be numerically calculated. If any of the differences |\overline{BC} − \overline{B′C′}| , |\overline{CD} − \overline{C′D′}| , |\overline{DA} − \overline{D′E′}| exceed an appropriately chosen ϵ then the candidate quadrilateral does not close up. Because Maple is used we can specify that the calculations be carried out to a large number of decimal places to guarantee good accuracy in the calculation of the lengths, and therefore that a small value of ϵ may be chosen. If all the differences are less than the tolerance ϵ then the candidate tiling is directly constructed, using the Matlab drawing scripts.

5.2. Boundary Word Test. Our second method uses group theory. For each of the possible quadrilateral boundaries the program creates four edge words in p, q, and r by making reflections through the various hubs along an edge of the quadrilateral. The four edge words are concatenated to form a boundary word. The four edges close up to form a quadrilateral if and only if the boundary word reduces to the identity. The pattern of hubs along the boundary allow us to quickly write down the boundary word. The details of determining the boundary word and showing it is the identity is described in detail in some sample calculations in Subsection 5.4.

By attempting to draw a quadrilateral in the triangle tiling, as above, we have a word which we want to prove is the identity. There are two possible approaches. The first approach is see if the word can be reduced to the identity, using the relations that we have in the group T^{∗}. Though in any specific example it always seems possible to find a reduction to the identity (when it exists) the authors decided against attempting to develop a computer algorithm to decide whether a word was reducible to the identity because of apparent complexity of doing so suggested by [9, p. 672]. If the maximum length L of the boundary words to be reduced is known beforehand the Knuth-Bendix algorithm [6, p. 116] produces, for each (l, m, n), a finite list of substitution rules which, if applied recursively to a given word of length at most ≤ L, will reduce to the identity if and only if the word is the identity. The length of each edge word is (very crudely) bounded by the number of triangles in the quadrilateral and so L ≤ 4 × 60 = 240. Thus it is possible (and interesting), in principle, to devise a reduction algorithm, however more work is required than by using the second approach that we describe next.

The second approach converts a product of an even number of reflections into a matrix by means of a homomorphism q : T → P SL_{2}(ℂ), which we describe shortly. The matrix images are computed numerically using Maple, which introduces some error into our calculations due to rounding off the entries in the matrices. This can be remedied that noting that if the computations are carried out with great accuracy, say to 50 decimal places as done in the study [8] (see Remarks 5.5 and 5.6), then a product which is not computed to be within a prescribed distance of the identity will not equal the identity.

We now describe the map q and state a theorem that guarantees that our conclusions based on approximate calculations are justified. The reflections in the sides of an (l, m, n)-triangle are inversions in the circle defining the side (or reflection in a diameter). Every such reflection has the form T_{A} ∘ ε where

T_{A}(z) = \frac{az + b}{\overline{b}z + \overline{a}}, A = [ \begin{matrix}a & b \\ \overline{b} & \overline{a} \end{matrix} ] , a\overline{a} − b\overline{b} = 1,
ϵ(z) = \overline{z}.

The matrix is determined only up to a scalar multiple of ±1. If the inversion is in a circle centered at z_{0} and perpendicular to the unit disc then A has the form

A = \frac{i}{\sqrt{z_{0}\overline{z_{0}} − 1}} [ \begin{matrix}z_{0} & −1 \\ 1 & −\overline{z_{0}} \end{matrix} ] .

Otherwise, the line is a diameter meeting the positive x-axis at the angle θ and A has the form.

A = [ \begin{matrix}e^{iθ} & 0 \\ 0 & e^{−iθ} \end{matrix} ]

If two of the edges of the (l, m, n)-triangle are diameters through the origin, then the third side is easily determined using analytic geometry (see [2]). Also note that the origin is a vertex of the tiling. Let P, Q, R be the matrices such that the reflections p, q, r are associated to:

p ↔ T_{P} ∘ ε, q ↔ T_{Q} ∘ ε, r ↔ T_{R} ∘ ε.

Then the elements a = pq, b = qr, and c = rp are associated to:

a ↔ T_{P \overline{Q}}, b ↔ T_{Q\overline{R}}, and c ↔ T_{R\overline{P}} ,

since

ε ∘ T_{A} ∘ ε = T\overline{A}, and
T_{AB} = T_{A} ∘ T_{B},

where \overline{A} is obtained by conjugating the entries of A.

Now a word w in p, q, r in T^{∗} representing the identity must have an even number of factors since an odd word is orientation reversing. Thus w is a word in a = pq, b = qr, c = rp, a^{−1} = qp, b^{−1} = rq, and c^{−1} = pr, and the matrix corresponding to w is obtained by making substitutions based on:

(15)  a → P \overline{Q},
b → Q\overline{R},
c → R\overline{P} .

The following theorem now guarantees when an element which is approximately equal to the identity is actually equal to the identity. We first define the L^{∞} norm on matrices:

∥A∥ = max_{k,l}(|A(k, l)|)

Proposition 5.4. Let T be the group of orientation-preserving isometries generated by an (l, m, n)-triangle Δ in the hyperbolic plane. Assume that a vertex of Δ is at the origin. Let A ∈ P SL_{2}(ℂ) be a matrix representing an element of g ∈ T, according to the substitution in (15). Then, there is an ϵ_{Δ}, depending on Δ and not on A, such that if min(∥A − I∥ , ∥A + I∥) ≤ ϵ_{Δ} then g is the identity in T.

The proposition gets used in the following way. Suppose that the matrix A in the proposition has been computed approximately as Â. Suppose further that ∥Â − I∥ ≤ \frac{ϵ_{Δ}}{2} by calculation and that ∥A − Â∥ ≤ \frac{ϵ_{Δ}}{2} by controlling the accuracy

of the computation. Then, ∥A − I∥ ≤ ∥A − Â∥ + ∥Â − I∥ ≤ ϵ_{Δ}. and so that g is the identity.

Proof. Let A = [ \begin{matrix}a & b \\ \overline{b} & \overline{a} \end{matrix} ] and let ζ = g · 0 = \frac{a0+b}{\overline{b}0+\overline{a}} = b/\overline{a}. Observe that ζ is one of

the vertices of the tiling. There is a small hyperbolic ball of radius h such that 0 is the only vertex contained in that ball and hence ρ(ζ, 0) > h unless ζ = 0. We may take h to be any number smaller than all the sidelengths of the master tile. Let ϵ_{Δ} = tanh(h/2) be the Euclidean radius of this ball. Thus |ζ| > ϵ_{Δ} unless ζ = 0. But since min(∥A − I∥ , ∥A + I∥) ≤ ϵ_{Δ}, then |b| ≤ ϵ_{Δ}. Also, as a\overline{a} − b\overline{b} = 1, then

|a| ≥ 1 and hence |ζ| = \frac{|b|}{|a|} ≤ ϵ_{Δ}. This forces ζ = 0 and so A = [ \begin{matrix}e^{iθ} & 0 \\ 0 & e^{−iθ} \end{matrix} ] .

But then min(∥A − I∥ , ∥A + I∥) = |e^{iθ} − 1| = \sqrt{2 − 2 cos(θ)}. The smallest value of this expression is\sqrt{2 − 2 cos(\frac{π}{b})} where b is the largest of l, m and n. Thus we need only to adjust ϵ_{Δ} to be smaller than this. □

Remark 5.5. For a given (l, m, n) the coefficients of P \overline{Q}, Q\overline{R}, and R\overline{P} all belong to finite extension of ℚ. Therefore it is possible to exactly calculate words in the matrices by symbolic means. However the “cure” of exact symbolic computation is worse than the “disease” of approximation.

Remark 5.6. The 50 decimal places used in [8] are probably overkill. However, the scripts can be run automatically, computing with a large number of decimal places without an onerous time penalty. It is not to hard to show that an error bound for q-image of a word of length L is (2M)^{L/2}ϵ where M is the maximum of the entries of the matrices in Remark 5.5, and ϵ is the maximum error of individual matrix entries. Thus the required number decimal places is linear in the word length.

5.3. Example: Failure of (2, 3, 7) to Tile (7, 7, 7, 7). The largest possible value of K occurs for the attempt to tile a (7, 7, 7, 7)-quadrilateral by a (2, 3, 7)- triangle. The candidate pair passes the K-test and the hub tests since K = 60, h_{2} = 30, h_{3} = 20, and h_{7} = 8. Each of the four edges of any quadrilateral must have two 7-hubs. For, an edge with only one 7-hub and terminating \frac{π}{7} angles must close up to a (7, 7, 7) triangle as in Figure 5.1 below. Similarly there cannot be zero 7-hubs, as Figure 5.1 also shows. Thus every edge must have exactly two 7-hubs, and hence there is a unique way to construct the quadrilateral. But Figure 5.2 shows how the attempt to construct such a quadrilateral clearly fails.

Fig. 5.1. (2, 3, 7) tiling of (7, 7, 7)  Fig. 5.2. A failed boundary search

5.4. Example: Successful Tiling of (5, 5, 5, 5) by (2, 4, 5). Now let us examine a quadrilateral which can be subdivided by triangles. Let us subdivide the (5, 5, 5, 5)-quadrilateral with the (2, 4, 5)-triangle. See Case C25 in Table 6.7 for a picture of the subdivided tiling. It is found that K = 24, h_{2} = 12, h_{4} = 6 and h_{5} = 4. By looking at the tiling in Section 6 it is clear the any proposed edge of a (5, 5, 5, 5)-quadrilateral without a 5-hub closes up to a triangle. Since h_{5} = 4 then there must be exactly one 5-hub on each side. This greatly restricts the boundary searches. Let us consider the lower boundary tiles on the lower edge of the quadrilateral as pictured in Figure 5.3.

The far left triangle as oriented is a (5, 4, 2)-triangle. Though the order of l, m and n is unimportant for first three steps of the search, the ordering is very important in the quadrilateral construction phase. Thus for this particular triangle we have:

(pq)^{5} = a^{5} = 1,
(qr)^{4} = b^{4} = 1,
(rp)^{2} = c^{2} = 1.

Now let us construct the edge word corresponding to this part of the boundary. We label the triangles Δ_{0}, Δ_{1}, …, Δ_{8} as we move from left to right. It is obvious that Δ_{1} = rΔ_{0} since we reflect over the r edge. The reflections in sides of Δ_{1} are rpr, rqr and r = rrr. In fact if Δ′ = gΔ_{0} for some g ∈ T^{∗} the reflections in the sides of Δ′ are gpg^{−1}, gqg^{−1} and grg^{−1}. From the picture we see that Δ_{2} is the rqr image of Δ_{1} and hence Δ_{2} = (rqr)rΔ_{0} = rqΔ_{0}. Continuing one more step, we see that the reflections in the sides of Δ_{2} are rqpqr, rqr = rqqqr and rqrqr. Now Δ_{3} is obtained by reflecting Δ_{2} over the common rqrqr edge. Thus Δ_{3} = rqrqrΔ_{2} = (rqrqr)rqΔ_{0} = rqrΔ_{0}. The pattern is now evident which we now state as a proposition. We omit the easy induction proof.

Figure 5.3. Boundary tiles of lower edge

Proposition 5.7. Let Δ_{0}, Δ_{1}, …, Δ_{s} be a sequence of tiles such that Δ_{i} and Δ_{i−1} meet in edge e_{i}. Let r_{i} the unique edge among {p, q, r} such that e_{i} matches r_{i} by the unique transformation in T^{∗} carrying Δ_{0} to Δ_{i}. Let r_{i} also denote the reflection in r_{i}. Then

Δ_{i} = r_{1} · r_{2} ⋯ r_{i}Δ_{0}, for i = 1, …, s.

Applying the proposition we get

Δ_{8} = rqpqprqrΔ_{0} = w_{1}Δ_{0}

Continuing on with the next edges we get:

Δ_{16} = w_{2}w_{1}Δ_{0},
Δ_{24} = w_{3}w_{2}w_{1}Δ_{0},
Δ_{32} = w_{4}w_{3}w_{2}w_{1}Δ_{0}.

where w_{1} = w_{2} = w_{3} = w_{4} = rqpqprqr. The fact that all the edge words w_{1}, w_{2}, w_{3}, and w_{4} are equal is a consequence of the four-fold rotational symmetry of the quadrilateral. Observe that the edgewords are completely determined by the initial orientation of Δ_{0} and the number and type of hubs we pass through along an edge. The process of finding the word can be sped up by observing that passing through a hub along the edge concatenates a well-defined subword to the edge word. Thus one multiplies together a sequence of “hub words”.

The boundary word we have is (rqpqprqr)^{4}. The candidate boundary closes up if and only if and only if Δ_{32} = Δ_{0}, i.e., if and only if (rqpqprqr)^{4}Δ_{0} = Δ_{0}. Since T^{∗} acts simply transitively on the triangles then the boundary closes up if and only if

(rqpqprqr)^{4} = 1.

But we have

(rqpqprqr)^{4} = rqpqprq(rr)qpqprq(rr)qpqprq(rr)qpqprqr
= rqpqpr(qq)pqpr(qq)pqpr(qq)pqprqr
= rqpq(prp)q(prp)q(prp)qprqr

Now prpr = 1 so prp = r and likewise qrqrqrq = r. Thus we further obtain

(rqpqprqr)^{4} = rqp(qrqrqrq)prqr
= rq(prpr)qr
= rqqr
= 1.

We have exactly computed the expected reduction. Alternatively, we could translate the boundary word into a word in a, b, c and compute the matrix image in P SL_{2}(ℂ). One simply takes the letters in boundary word two at a time with the replacements: p^{2} = q^{2} = r^{2} = 1, pq = a, qr = b, pr = c, qp = a^{−1}, rq = b^{−1}, and pr = c^{−1}. Our word and the replacement matrices are (to 5 decimal places):

(rqpqprqr)^{4} = (b^{−1}ac^{−1}b)^{4}.

a ⟶ A ≐ [ \begin{matrix}.80903 + .58778i & 0 \\ 0 & .80903 − .58778i \end{matrix} ]
b ⟶ B ≐ [ \begin{matrix}.70708 + .97325i & −.66876i \\ .66876i & .70708 − .97325i \end{matrix} ]
c ⟶ C ≐ [ \begin{matrix}−1.2030i & −.39308 + .54105i \\ −.39308 − .54105i & 1.2030i \end{matrix} ]

The test matrix is seen to be approximately a scalar matrix:

(B^{−1}AC^{−1}B)^{4} ≐ [ \begin{matrix}−.9999 & 0 \\ 0 & −.9999 \end{matrix} ] .

The matrix calculations are done to 5 decimal places here to ensure clarity. By computing to a greater number of digits enough accuracy can be achieved to conclude that the boundary word is the identity. The matrix method is preferable since the computer (i.e., programmer) need not get creative about how to reduce words.

6. Catalogue of Divisible Tilings

This section contains a complete catalogue of all (s, t, u, v)-quadrilaterals which can be subdivided by (l, m, n)-triangles. For completeness we have also included the small number of tilings of triangles by triangles and quadrilaterals by quadrilaterals. For each category there are two tables, a table of data and a table of figures.

Theorem 6.1. Let Δ and Ω denote a hyperbolic, kaleidoscopic (l_{1}, m_{1}, n_{1})-triangle and (l_{2}, m_{2}, n_{2})-triangle respectively. Then there is one 2-parameter family, and five 1-parameter families of divisible tiling pairs Δ ⊂ Ω in which there are free vertices. There are two exceptional tiling pairs Δ ⊂ Ω with constrained vertices only. These families and exceptional cases are listed in Table 6.1 and pictured in Table 6.5.

Theorem 6.2. Let Δ and Ω denote a hyperbolic, kaleidoscopic (l, m, n)-triangle and (s, t, u, v)-quadrilateral respectively. Then there is one 3-parameter family, five 2-parameter families, and 28 1-parameter families of divisible tiling pairs Δ ⊂ Ω in which there are free vertices. These families are listed in Table 6.2 and pictured in Table 6.6. In addition there are 27 divisible tiling pairs Δ ⊂ Ω with constrained vertices only. These are listed Table 6.3 and pictured in Table 6.7

Theorem 6.3. Let Δ and Ω denote a hyperbolic, kaleidoscopic (s_{1}, t_{1}, u_{1}, v_{1})-quad-rilateral and (s_{2}, t_{2}, u_{2}, v_{2})-quadrilateral respectively. Then there is one 2-parameter family, and one 1-parameter family of divisible tiling pairs Δ ⊂ Ω in which there are free vertices. There are no examples with constrained vertices only. The two families are listed in Table 6.4 and pictured in Table 6.8.

Some notes on the tables:

• Although it is usual to arrange for l ≤ m ≤ n the geometry of a triangle being included in a larger polygon may force a different ordering. For both the triangle and the quadrilateral the ordering is obtained by moving about the figure in a counter-clockwise sense. A different orientation is obtained from the reflected quadrilateral. These permutations of the ordering are in the tables of pictures only, where comparison of the picture and the ordering makes sense.

• The groups T^{∗} and Q^{∗} denote the groups generated by reflections in the sides of Δ and Ω respectively. Then Aut(Ω) which is equal to the group taking Ω to itself and Stab_{T^{∗}}(Ω) = T^{∗} ∩ Aut(Ω) are also given in the tables. The groups are computed by visual inspection of the pictures. These groups are useful in determining the structure of tiling groups of surfaces of minimal genus supporting both tilings. See [8] and the forthcoming paper [4] for more details.

266 S. A. Broughton, D. Haney, L. McKeough, and B. Mayfield

Table 6.1. Triangles subdivided by triangles

Case Δ  Ω  restrictions K Stab_{T^{∗}}(Δ) Aut(Ω)
TF1 (2, d, 2e) (d, d, e)  \frac{2}{d} + \frac{1}{e} < 1 2 ℤ_{2}  ℤ_{2}
TF2 (2, 3, 2d) (2, d, 2d) d ≥ 4  3 trivial  trivial
TF3 (2, 3, 3d) (3, d, 3d) d ≥ 4  4 trivial  trivial
TF4 (2, 4, 2d) (d, 2d, 2d) d ≥ 3  4 ℤ_{2}  ℤ_{2}
TF5 (2, 3, 2d) (d, d, d)  d ≥ 4  6 𝔻_{3}  𝔻_{3}
TF6 (2, 3, 4d) (d, 4d, 4d) d ≥ 2  6 ℤ_{2}  ℤ_{2}
TC1 (2, 3, 8) (4, 8, 8)  12 ℤ_{2}  ℤ_{2}
TC2 (2, 3, 7) (7, 7, 7)  21 ℤ_{3}  ℤ_{3}

Divisible Tilings in the Hyperbolic Plane 267

Table 6.2. Quadrilaterals subdivided by triangles with free vertices

Case Δ  Ω  restrictions  K Stab_{T^{∗}}(Ω) Aut(Ω)
F1  (d, 2e, 2f) (d, e, d, f)  \frac{2}{d} + \frac{1}{e} + \frac{1}{f} < 2 2 ℤ_{2}  ℤ_{2}
F2  (2, 2d, 3e) (2, d, 2d, e)  d ≥ 2, e ≥ 2  3 trivial  trivial
F3  (3, 2d, 3e) (d, e, 2d, 2e)  \frac{1}{d} + \frac{1}{e} < \frac{4}{3}  3 ℤ_{2}  ℤ_{2},if d = e
F4  (2, 2d, 2e) (d, e, d, e)  d ≥ 2, e ≥ 2  4 ℤ_{2}×ℤ_{2}  𝔻_{4},if d = e
F5  (2, 2d, 4e) (d, 2d, e, 2d)  d ≥ 2, e ≥ 2  4 ℤ_{2}  ℤ_{2}
F6  (2, 3d, 3e) (d, 3d, e, 3e)  \frac{1}{d} + \frac{1}{e} < \frac{3}{2}  4 ℤ_{2},if d = e ℤ_{2},if d = e
F7  (2, 4, 2d) (2, 2, d, d))  d ≥ 3  4 ℤ_{2}  ℤ_{2}
F8  (3, 3, 2d) (3, d, 3, d)  d ≥ 2  4 ℤ_{2}  ℤ_{2}
F9  (3, 3, 3d) (3, d, 3, 3d)  d ≥ 2  4 trivial  ℤ_{2}
F10 (2, 4, 6d) (2, 4, 2d, 3d)  d ≥ 1  5 trivial  trivial
F11 (2, 5, 2d) (2, d, d, 2d)  d ≥ 2  5 trivial  trivial
F12 (2, 3, 3d) (2, d, 2, d)  d ≥ 2  6 ℤ_{2}  ℤ_{2}
F13 (2, 3, 4d) (2, 2d, 2, d)  d ≥ 2  6 ℤ_{2}  ℤ_{2}
F14 (2, 4, 3d) (4, 4, d, d)  d ≥ 2  6 ℤ_{2}  ℤ_{2}
F15 (2, 4, 6d) (2, 3d, 6d, 2d)  d ≥ 1  6 trivial  trivial
F16 (2, 5, 6d) (4, 2d, 3d, 6d)  d ≥ 1  6 trivial  trivial
F17 (2, 6, 2d) (d, d, 2d, 2d)  d ≥ 2  6 ℤ_{2}  ℤ_{2}
F18 (2, 3, 10d) (2, 5d, 3, 2d)  d ≥ 1  7 trivial  trivial
F19 (2, 3, 12d) (2, 3d, 3, 4d)  d ≥ 1  7 trivial  trivial
F20 (2, 3, 4d) (3, d, 3, d)  d ≥ 2  8 ℤ_{2}  ℤ_{2}
F21 (2, 3, 6d) (3, d, 3, 3d)  d ≥ 2  8 ℤ_{2}  ℤ_{2}
F22 (2, 4, 2d) (d, d, d, d)  d ≥ 3  8 𝔻_{4}  𝔻_{4}
F23 (2, 4, 3d) (d, 3d, d, 3d)  d ≥ 1  8 ℤ_{2}  ℤ_{2}
F24 (2, 4, 4d) (d, 4d, 2d, 4d) d ≥ 2  8 ℤ_{2}  ℤ_{2}
F25 (2, 3, 12d) (2, 4d, 6d, 3d)  d ≥ 1  9 trivial  trivial
F26 (2, 3, 15d) (2, 3d, 15d, 5d) d ≥ 1  9 trivial  trivial
F27 (2, 3, 6d) (2, d, 6d, 3d)  d ≥ 2  9 trivial  trivial
F28 (2, 3, 14d) (3, d, 14d, 7d)  d ≥ 1  10 trivial  trivial
F29 (2, 3, 20d) (3, 4d, 20d, 5d) d ≥ 1  10 trivial  trivial
F30 (2, 3, 30d) (3, 10d, 15d, 6d) d ≥ 1  10 trivial  trivial
F31 (2, 3, 4d) (d, 2d, d, 2d)  d ≥ 2  12 ℤ_{2}×ℤ_{2}  ℤ_{2}×ℤ_{2}
F32 (2, 3, 5d) (d, 5d, d, 5d)  d ≥ 2  12 ℤ_{2}  ℤ_{2}
F33 (2, 3, 6d) (d, 6d, 2d, 3d) d ≥ 2  12 trivial  trivial
F34 (2, 3, 8d) (d, 8d, 2d, 8d) d ≥ 1  12 ℤ_{2}  ℤ_{2}

268 S. A. Broughton, D. Haney, L. McKeough, and B. Mayfield

Table 6.3. Quadrilaterals subdivided by triangles without free vertices

Case Δ  Ω  K Stab_{T^{∗}}(Ω) Aut(Ω)
C1  (3, 4, 4) (4, 4, 4, 4)  6 ℤ_{2}  ℤ_{2}×ℤ_{2}
C2  (3, 3, 5) (3, 3, 5, 5)  7 trivial  ℤ_{2}
C3  (3, 4, 4) (2, 3, 3, 4)  7 trivial  trivial
C4  (2, 4, 5) (2, 2, 4, 4)  10 ℤ_{2}  ℤ_{2}
C5  (2, 4, 5) (2, 2, 4, 4)  10 ℤ_{2}  ℤ_{2}
C6  (2, 4, 5) (2, 4, 2, 4)  10 ℤ_{2}  ℤ_{2}
C7  (3, 3, 4) (3, 4, 3, 4)  10 trivial  ℤ_{2}
C8  (2, 4, 5) (2, 2, 4, 5)  11 trivial  trivial
C9  (2, 3, 8) (2, 2, 4, 4)  12 ℤ_{2}  ℤ_{2}
C10 (2, 4, 6) (3, 3, 6, 6)  12 ℤ_{2}  ℤ_{2}
C11 (2, 4, 6) (4, 4, 4, 4)  12 ℤ_{2}×ℤ_{2}  ℤ_{2}×ℤ_{2}
C12 (2, 5, 5) (5, 5, 5, 5)  12 ℤ_{2}  ℤ_{2}
C13 (3, 3, 4) (4, 4, 4, 4)  12 ℤ_{4}  ℤ_{4}
C14 (2, 3, 8) (2, 3, 3, 4)  12 trivial  trivial
C15 (2, 3, 10) (3, 3, 5, 5)  14 ℤ_{2}  ℤ_{2}
C16 (2, 3, 10) (2, 5, 5, 10) 15 trivial  trivial
C17 (2, 3, 9) (3, 3, 3, 9)  16 trivial  trivial
C18 (2, 4, 5) (2, 4, 5, 4)  16 trivial  trivial
C19 (2, 3, 12) (6, 6, 12, 12) 18 ℤ_{2}  ℤ_{2}
C20 (2, 3, 8) (3, 4, 3, 4)  20 ℤ_{2}  ℤ_{2}
C21 (2, 4, 5) (4, 4, 4, 4)  20 ℤ_{2}×ℤ_{2}  ℤ_{2}×ℤ_{2}
C22 (2, 4, 5) (4, 4, 5, 5)  22 ℤ_{2}  ℤ_{2}
C23 (2, 3, 8) (2, 8, 4, 8)  24 ℤ_{2}  ℤ_{2}
C24 (2, 3, 8) (4, 4, 4, 4)  24 𝔻_{4}  𝔻_{4}
C25 (2, 4, 5) (5, 5, 5, 5)  24 ℤ_{4}  ℤ_{4}
C26 (2, 3, 7) (2, 7, 2, 7)  30 ℤ_{2}  ℤ_{2}
C27 (2, 3, 7) (3, 7, 3, 7)  44 ℤ_{2}  ℤ_{2}

Table 6.4. Quadrilaterals subdivided by quadrilaterals

Case Δ  Ω  restrictions K Stab_{T^{∗}}(Δ) Aut(Ω)
QF1 (2, 2, d, e) (d, d, e, e) \frac{1}{d} + \frac{1}{e} < 1 2 ℤ_{2}  ℤ_{2}
QF2 (2, 2, 2, d) (d, d, d, d) d ≥ 3  4 ℤ_{2}×ℤ_{2}  𝔻_{4}

Table 6.5. Triangles subdivided by triangles

\begin{matrix}Case TF1: K = 2, \\ (d, 2, 2e) ⊂ (d, d, e) \end{matrix}  \begin{matrix}Case TF2: K = 3, \\ (2, 3, 2d) ⊂ (2, 2d, d) \end{matrix}

\begin{matrix}Case TF3: K = 4, \\ (3, 2, 3d) ⊂ (3, 3d, d) \end{matrix}  \begin{matrix}Case TF4: K = 4, \\ (2d, 4, 2) ⊂ (2d, 2d, d) \end{matrix}

\begin{matrix}Case TF5: K = 6, \\ (2d, 2, 3) ⊂ (d, d, d) \end{matrix}  \begin{matrix}Case TF6: K = 6, \\ (4d, 3, 2) ⊂ (4d, 4d, d) \end{matrix}

270 S. A. Broughton, D. Haney, L. McKeough, and B. Mayfield

Table 6.5, part 2

\begin{matrix}Case TC1: K = 12, \\ (8, 2, 3) ⊂ (8, 8, 4) \end{matrix}  \begin{matrix}Case TC2: K = 24 \\ (7, 3, 2) ⊂ (7, 7, 7) \end{matrix}

Table 6.6. Divisible quadrilaterals with free vertices

\begin{matrix}Case F1: K = 2, \\ (d, 2e, 2f) ⊂ (d, e, d, f) \end{matrix}  \begin{matrix}Case F2: K = 3, \\ (2, 2d, 3e) ⊂ (2, d, 2d, e) \end{matrix}

\begin{matrix}Case F3: K = 3, \\ (2d, 3, 2e) ⊂ (2d, 2e, d, e) \end{matrix}  \begin{matrix}Case F4: K = 4, \\ (2d, 2e, 2) ⊂ (d, e, d, e) \end{matrix}

\begin{matrix}Case F5: K = 4, \\ (2d, 2, 4e) ⊂ (2d, d, 2d, e) \end{matrix}  \begin{matrix}Case F6: K = 4, \\ (3d, 3e, 2) ⊂ (3d, e, 3e, d) \end{matrix}

\begin{matrix}Case F7: K = 4, \\ (2, 4, 2d) ⊂ (2, 2, d, d) \end{matrix}  \begin{matrix}Case F8: K = 4, \\ (3, 3, 2d) ⊂ (3, d, 3, d) \end{matrix}

\begin{matrix}Case F9: K = 4, \\ (3, 3, 3d) ⊂ (3, 3d, 3, d) \end{matrix}  \begin{matrix}Case F10: K = 5, \\ (2, 4, 6d) ⊂ (2, 4, 2d, 3d) \end{matrix}

\begin{matrix}Case F11: K = 5, \\ (2, 2d, 5) ⊂ (2, d, d, 2d) \end{matrix}  \begin{matrix}Case F12: K = 6, \\ (2, 3, 3d) ⊂ (2, d, 2, d) \end{matrix}

Table 6.6, part 3

\begin{matrix}Case F13: K = 6, \\ (2, 3, 4d) ⊂ (2, 2d, 2, d) \end{matrix}  \begin{matrix}Case F14: K = 6, \\ (4, 2, 3d) ⊂ (4, 4, d, d) \end{matrix}

\begin{matrix}Case F15: K = 6, \\ (6d, 2, 4) ⊂ (6d, 2d, 2, 3d) \end{matrix}  \begin{matrix}Case F16: K = 6, \\ (5, 6d, 2) ⊂ (5, 2d, 3d, 6d) \end{matrix}

\begin{matrix}Case F17: K = 6, \\ (2d, 6, 2) ⊂ (2d, 2d, d, d) \end{matrix}  \begin{matrix}Case F18: K = 7, \\ (2, 3, 10d) ⊂ (2, 5d, 3, 2d) \end{matrix}

\begin{matrix}Case F19: K = 7, \\ (2, 3, 12d) ⊂ (2, 3d, 3, 4d) \end{matrix}  \begin{matrix}Case F20: K = 8, \\ (3, 4d, 2) ⊂ (3, d, 3, d) \end{matrix}

\begin{matrix}Case F21: K = 8, \\ (3, 6d, 2) ⊂ (3, d, 3, 3d) \end{matrix}  \begin{matrix}Case F22: K = 8, \\ (2d, 2, 4) ⊂ (d, d, d, d) \end{matrix}

\begin{matrix}Case F23: K = 8, \\ (3d, 2, 4) ⊂ (3d, d, 3d, d) \end{matrix}  \begin{matrix}Case F24: K = 8, \\ (4d, 4, 2) ⊂ (4d, 2d, 4d, d) \end{matrix}

\begin{matrix}Case F25: K = 9, \\ (2, 3, 12d) ⊂ (2, 4d, 6d, 3d) \end{matrix}  \begin{matrix}Case F26: K = 9, \\ (2, 3, 15d) ⊂ (2, 3d, 15d, 5d) \end{matrix}

\begin{matrix}Case F27: K = 9, \\ (2, 6d, 3) ⊂ (2, d, 6d, 3d) \end{matrix}  \begin{matrix}Case F28: K = 10, \\ (3, 14d, 2) ⊂ (3, 2d, 14d, 7d) \end{matrix}

\begin{matrix}Case F29: K = 10, \\ (3, 2, 20d) ⊂ (3, 4d, 20d, 5d) \end{matrix}  \begin{matrix}Case F30: K = 10, \\ (3, 2, 30d) ⊂ (3, 10d, 15d, 6d) \end{matrix}

\begin{matrix}Case F31: K = 12, \\ (4d, 2, 3) ⊂ (2d, d, 2d, d) \end{matrix}  \begin{matrix}Case F32: K = 12, \\ (5d, 3, 2) ⊂ (5d, d, 5d, d) \end{matrix}

\begin{matrix}Case F33: K = 12, \\ (6d, 3, 2) ⊂ (6d, 2d, 3d, d) \end{matrix}  \begin{matrix}Case F34: K = 12, \\ (8d, 3, 2) ⊂ (8d, 4d, 8d, d) \end{matrix}

Table 6.7. Divisible quadrilaterals with constrained vertices

\begin{matrix}Case C1: K = 6, \\ (4, 4, 3) ⊂ (4, 4, 4, 4) \end{matrix}  \begin{matrix}Case C2: K = 7, \\ (3, 5, 3) ⊂ (3, 3, 5, 5) \end{matrix}

\begin{matrix}Case C3: K = 7, \\ (4, 3, 3) ⊂ (2, 3, 3, 4) \end{matrix}  \begin{matrix}Case C4: K = 10, \\ (2, 4, 5) ⊂ (2, 2, 4, 4) \end{matrix}

\begin{matrix}Case C5: K = 10, \\ (4, 2, 5) ⊂ (2, 2, 4, 4) \end{matrix}  \begin{matrix}Case C6: K = 10, \\ (2, 5, 4) ⊂ (2, 4, 2, 4) \end{matrix}

\begin{matrix}Case C7: K = 10, \\ (3, 3, 4) ⊂ (3, 4, 3, 4) \end{matrix}  \begin{matrix}Case C8: K = 11, \\ (2, 4, 5) ⊂ (2, 2, 4, 5) \end{matrix}

\begin{matrix}Case C9: K = 12, \\ (2, 8, 3) ⊂ (2, 2, 4, 4) \end{matrix}  \begin{matrix}Case C10: K = 12, \\ (6, 4, 2) ⊂ (3, 3, 6, 6) \end{matrix}

\begin{matrix}Case C11: K = 12, \\ (4, 2, 6) ⊂ (4, 4, 4, 4) \end{matrix}  \begin{matrix}Case C12: K = 12, \\ (5, 2, 5) ⊂ (5, 5, 5, 5) \end{matrix}

\begin{matrix}Case C13: K = 12, \\ (4, 3, 3) ⊂ (4, 4, 4, 4) \end{matrix}  \begin{matrix}Case C14: K = 14, \\ (8, 3, 2) ⊂ (2, 3, 3, 4) \end{matrix}

\begin{matrix}Case C15: K = 14, \\ (3, 10, 2) ⊂ (3, 3, 5, 5) \end{matrix}  \begin{matrix}Case C16: K = 15, \\ (2, 3, 10) ⊂ (2, 5, 5, 10) \end{matrix}

\begin{matrix}Case C17: K = 16, \\ (9, 3, 2) ⊂ (3, 3, 3, 9) \end{matrix}  \begin{matrix}Case C18: K = 16, \\ (4, 2, 5) ⊂ (2, 4, 5, 4) \end{matrix}

\begin{matrix}Case C19: K = 18, \\ (12, 3, 2) ⊂ (6, 6, 12, 12) \end{matrix}  \begin{matrix}Case C20: K = 20, \\ (3, 2, 8) ⊂ (3, 4, 3, 4) \end{matrix}

\begin{matrix}Case C21: K = 20, \\ (4, 2, 5) ⊂ (4, 4, 4, 4) \end{matrix}  \begin{matrix}Case C22: K = 20, \\ (4, 2, 5) ⊂ (4, 4, 5, 5) \end{matrix}

\begin{matrix}Case C23: K = 24, \\ (8, 3, 2) ⊂ (2, 8, 4, 8) \end{matrix}  \begin{matrix}Case C24: K = 24, \\ (8, 3, 2) ⊂ (4, 4, 4, 4) \end{matrix}

\begin{matrix}Case C25: K = 24, \\ (5, 4, 2) ⊂ (5, 5, 5, 5) \end{matrix}  \begin{matrix}Case C26: K = 30, \\ (2, 3, 7) ⊂ (2, 7, 2, 7) \end{matrix}

\begin{matrix}Case C27: K = 44, \\ (3, 7, 2) ⊂ (3, 7, 3, 7) \end{matrix}

Table 6.8. Quadrilaterals subdivided by quadrilaterals

\begin{matrix}Case QF1: K = 2, \\ (d, e, 2, 2) ⊂ (d, e, e, d) \end{matrix}  \begin{matrix}Case QF2: K = 3, \\ (d, 2, 2, 2) ⊂ (d, d, d, d) \end{matrix}

282 S. A. Broughton, D. Haney, L. McKeough, and B. Mayfield

Appendix A. Triangles with area ≤ \frac{π}{4}

Angle Description  μ
(2, 3, 7)  \frac{1}{42}
(2, 3, 8)  \frac{1}{24}
(2, 4, 5)  \frac{1}{20}
(2, 3, 9)  \frac{1}{18}
(2, 3, d), d = 10, 11  \frac{d−6}{6d}
(2, 3, 12), (2, 4, 6), (3, 3, 4) \frac{1}{12}
(2, 3, d), d = 13, 14  \frac{d−6}{6d}
(2, 3, 15), (2, 5, 5)  \frac{1}{10}
(2, 3, 16)  \frac{5}{48}
(2, 4, 7)  \frac{3}{28}
(2, 3, 17)  \frac{11}{102}
(2, 3, d), 18 ≤ d ≤ 23  \frac{d−6}{6d}
(2, 3, 24), (2, 4, 8)  \frac{1}{8}
(2, 3, d), 25 ≤ d ≤ 29  \frac{d−6}{6d}
(2, 3, 30), (2, 5, 6), (3, 3, 5) \frac{2}{15}
(2, 3, d), 31 ≤ d ≤ 35  \frac{d−6}{6d}
(2, 3, 36), (2, 4, 9)  \frac{5}{36}
(2, 3, d), 37 ≤ d ≤ 59  \frac{d−6}{6d}
(2, 3, 60), (2, 4, 10)  \frac{3}{20}
(2, 3, d), 61 ≤ d ≤ 104  \frac{d−6}{6d}
(2, 3, 105), (2, 5, 7)  \frac{11}{70}
(2, 3, d), 106 ≤ d ≤ 131  \frac{d−6}{6d}
(2, 3, 132), (2, 4, 11)  \frac{7}{44}
(2, 3, d), d ≥ 133  \frac{d−6}{6d}
(2, 4, 12), (2, 6, 6),  \frac{1}{6}
(3, 3, 6), (3, 4, 4)  \frac{1}{6}
(2, 4, 13)  \frac{9}{52}
(2, 5, 8)  \frac{7}{40}
(2, 4, d), 14 ≤ d ≤ 16  \frac{d−4}{4d}
(2, 5, 9)  \frac{17}{90}
(2, 6, 7), (3, 3, 7)  \frac{4}{21}
(2, 4, d), 17 ≤ d ≤ 19  \frac{d−4}{4d}
(2, 4, 20), (2, 5, 10)  \frac{1}{5}
(2, 4, d), 21 ≤ d ≤ 23  \frac{d−4}{4d}

Angle Description  μ
(2, 4, 24), (2, 6, 8), (3, 3, 8)  \frac{5}{24}
(2, 5, 11)  \frac{23}{110}
(2, 4, d), 25 ≤ d ≤ 27  \frac{d−4}{4d}
(2, 4, 28), (2, 7, 7)  \frac{3}{14}
(2, 4, 29)  \frac{25}{116}
(2, 4, 30), (2, 5, 12), (3, 4, 5)  \frac{13}{60}
(2, 4, d), 31 ≤ d ≤ 35  \frac{d−4}{4d}
(2, 4, 36), (2, 6, 9), (3, 3, 9)  \frac{2}{9}
(2, 4, 37)  \frac{33}{148}
(2, 5, 13)  \frac{29}{130}
(2, 4, d), 38 ≤ d ≤ 46  \frac{d−4}{4d}
(2, 5, 14)  \frac{8}{35}
(2, 4, d), 47 ≤ d ≤ 55  \frac{d−4}{4d}
(2, 4, 56), (2, 7, 8)  \frac{13}{56}
(2, 4, d), 57 ≤ d ≤ 59  \frac{d−4}{4d}
(2, 4, 60), (2, 5, 15)  \frac{7}{30}
(2, 6, 10), (3, 3, 10)  \frac{7}{30}
(2, 4, d), 61 ≤ d ≤ 79  \frac{d−4}{4d}
(2, 4, 80), (2, 5, 16)  \frac{19}{80}
(2, 4, d), 81 ≤ d ≤ 113  \frac{d−4}{4d}
(2, 5, 17)  \frac{41}{170}
(2, 4, d), 114 ≤ d ≤ 131  \frac{d−4}{4d}
(2, 4, 132), (2, 6, 11), (3, 3, 11) \frac{8}{33}
(2, 4, d), 133 ≤ d ≤ 179  \frac{d−4}{4d}
(2, 4, 180), (2, 5, 18)  \frac{11}{45}
(2, 4, d), 181 ≤ d ≤ 251  \frac{d−4}{4d}
(2, 4, 252), (2, 7, 9)  \frac{31}{126}
(2, 4, d), 253 ≤ d ≤ 379  \frac{d−4}{4d}
(2, 4, 380), (2, 5, 19)  \frac{47}{190}
(2, 4, d), d ≥ 381  \frac{d−4}{4d}
(2, 5, 20), (2, 6, 12)  \frac{1}{4}
(2, 8, 8), (3, 3, 12)  \frac{1}{4}
(3, 4, 6), (4, 4, 4)  \frac{1}{4}

Divisible Tilings in the Hyperbolic Plane 283

References

[1] A. F. Beardon, The Geometry of Discrete Groups, Graduate Texts in Mathematics, no. 91, Springer-Verlag, New York, 1995, MR 97d:22011, Zbl 528.30001.

[2] S. A. Broughton, Constructing kaleidoscopic tiling polygons in the hyperbolic plane, Amer. Math. Monthly, to appear.

[3] S. A. Broughton, Kaleidoscopic tiling of surfaces, background notes for the Rose-Hulman REU Tilings Project, http://www.rose-hulman.edu/Class/ma/HTML/REU/Tilings/pubs.html#Kaleido.

[4] S .A. Broughton, D. Haney, L. McKeough, B. Smith, Divisible Tilings on Hyperbolic Surfaces, in preparation.

[5] J. Dochkowa, H. Harboth, I. Mengerson, Cut set Catalan numbers, Proceedings of the Twenty-ninth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1998), Congr. Numer. 130 (1998), 133–139, CMP 1 676 458.

[6] D. B. A. Epstein, J. W. Cannon, D. F. Holt, S. V. F. Levy, M. S. Paterson, and W. P. Thurston, Word Processing in Groups, Jones and Bartlett, Boston, 1992, MR 93i:20036, Zbl 764.20017.

[7] R. P. Grimaldi, Discrete and Combinatorial Mathematics (fourth ed.), Addison Wesley, Reading, 1999, Zbl 787.05001.

[8] D. Haney and L. McKeough Quadrilaterals Subdivided by Triangles in the Hyperbolic Plane, Rose-Hulman Math. Sci. Tech Rep. no. 98-04, 1998.

[9] A. Seress, An Introduction to computational group theory, Notices of the AMS, 44 no. 6, (June/July 1997), 671–679, MR 98e:20002, Zbl 929.20001.

[10] D. Singerman, Finitely maximal Fucshian groups, J. London Math. Soc. 6 (1972), 29–38, MR 48 #529, Zbl 251.20052.

[11] N. J. A. Sloane & S. Plouffe, The Encyclopedia of Integer Sequences, Acad. Press, San Diego, 1995, MR 96a:11001, Zbl 845.11001.

[12] B. M. Smith, Triangle tilings of quadrilaterals in the hyperbolic plane, (in preparation).

[13] MAPLE V, Waterloo Maple Inc., Waterloo, Canada.

[14] MATLAB, The Mathworks, Natick, Massachusetts.

[15] Rose-Hulman NSF-REU Tilings web site, http://www.rose-hulman.edu/Class/ma/HTML/REU/Tilings/tilings.html

Rose-Hulman Institute of Technology, Terre Haute IN, 47803 allen.broughton@rose-hulman.edu http://www.rose-hulman.edu/˜ brought/

University of Georgia, Athens, GA 30602

haneydaw@arches.uga.edu

St. Paul’s School, Concord NH

lmckeoug@sps.edu

3302 Cheyenne Court, Fairfield Twp, OH 45011

brandymayfield@hotmail.com

This paper is available via http://nyjm.albany.edu:8000/j/2000/6-12.html.