A Hyperbolic Plane Coloring and the Simple Group of Order 168

symbol interpreted in much the same way as in complex analysis). In Solution 3 we will derive the same coloring from a highlighting H: E > Z7. Solution 2. To begin, we define a homomorphism +: r PSL2(Z7) Y + ) [o 1] +(/3) 11 °]> +(7)= [1 O]¢ (These matrices satisfy the same identities as a, ,l3 and , so we can be assured that such a homomorphism exists.) Recall that the matrices [a d] E PSL2(Z7) act on the set Z7 u {oo} by linear fractional transformations: a b ax + b c d (x)cx+d (mod7). Throughout this paper we will identify the matrices with the linear fractional transformations, for simplicity. Now we can describe our labeling L: V Z7 u {oo}. Given A E V, let B be any adajent vertex and let C be the unique adjacent vertex such that A ABC is in the tesselation and is positively oriented. Then there exists a unique isometry X E r such that X(P) = A, X(Q) = B, and x(R) = C. Then define L(A)-[+( X)](°°)* A much simpler way to compute the labeling L is to apply the following recursive procedure. Begin by labeling the central vertex P "oo" (i.e. setting L(P) = oo) and labeling the seven adjacent vertices "0" through "6," beginning with Q and proceeding counterclockwise. Extend to a labeling L(x) of all the vertices in the (2, 3, 7) tesselation by applying the following rule: Rule 1. If the vertices of A ABC are already labeled, with L(A) = a, L(B) = b, L(C(= c, where a, b, c are distinct elements of Z7 U {°°} and if A ABC is an adjacent trzangle, set L(D) = d, where d is the unaque number an Z7 U {°°} such that (a,b,c,d) = -l(mod7). Y T / J tX r s s nere ta, D, C. av aenotes tne cross ratlo. The uniqueness of d is a standard fact about cross ratios, but there is another reason that L may not be well-defined. Since each vertex belongs to seven different triangles, and each of these is adjacent to three different triangles, Rule 1 could give us many conflicting instructions about how to label a given vertex. The easiest way to show that it does not, in fact, lead to "conflicting instructions," is to verify that our first, non-recursive procedure does give a labeling that satisfies Rule 1. Lemma 1. L is a well-defined labeling on V and satisfies Rule 1. Proof: We need to show that L does not depend on the choice of the adjacent vertex B. Suppose we had chosen C (the next vertex, proceeding counterclockwise). thereby using the adjacent triangle A ACD instead of A ABC. Then the isometry mapping A PQR i\ ACD is X = X°t , so L( A) = [ +( X )] (°°) = [ +( X°t )] (°°) = [ +( X)] [ +( °t )] (°°) = [ +( X)] (°°), which agrees with the previous definition. Proceeding by induction counterclockwise about the vertex A, we conclude that L(A) is independent of the choice of the adJacent vertex B. 708 HYPERBOLIC PLANE COLORING AND SIMPLE GROUP OF ORDER 168 [October This content downloaded from 157.55.39.246 on Tue, 27 Sep 2016 05:30:31 UTC All use subject to http://about.jstor.org/terms To prove Rule 1 holds, we suppose that A ABC and A ABD are adjacent triangles in the tesselation. Without loss of generality, suppose that A ABC is located clockwise from tL ABD in the cycle of seven triangles with vertex A. Let X: A PQR A ACB, then x,(3-1: A PQR A CBA, x,l3: A PQR A BAC, and X(x-1,X3: A DAB. Hence L(C) = [ +( X)] [+( 13 1)](oo) = [+( X)](°), L(B) = [+(X)][+(/3)]( ) [+(X)]( ) L(D) = [4)( X)] [+(0t 1)] [(*( /3)] [+( /3)](oo)-[+( x)](2). Since +( X) is a linear fractional transformation, it preserves cross ratios. Thus (L(A) L(B), L(C), L(D)) = (oo, 1,0,2) --l(mod7). O Now we explain how to proceed from the vertex labeling L to a face coloring. Our coloring will be based on the fact that for any four distinct elements al, . . ., a4 E Z7 U {°°}, the set of all values of the cross-ratio (a1T(l)S aqr(2)X aX(3) a Zr(4)) as 7r ranges over all permutations is either {2, 4, 6} or {3, 5}. In the latter case, the subgroup of permutations which fix the cross-ratio has index 2 and hence must be the alternating group A4. Thus, in particular, if (a,b,c,d)-S (mod7) then (c, a, b, d) = (b, c, a, d) -S (mod 7) as well, while, for example, (b, a, c, d) -3 (mod 7) We will define a triple (a, b, c) to be positively oriented if and only if there is a positively oriented triangle A ABC with labels L(A) = a, L(B) = b, and L(C) = c. Obviously this will hold if and only if there exists f E PSL2(Z7) such that f(a) = oo, f(b) = O, and f(c) = 1. A linear fractional transformation which accomplishes this is d-b (b-d)c (:r = d-c (c-d)b This transformation can be represented by a matrix of determinant 1 if and only if det g is a quadratic residue. (If det g A2, then (1/A)g is a matrix of determinant 1 which represents the same transformation.) Thus we may define a positivelyoriented triple in a purely number-theoretic fashion: if a, b, c + oo, then (a, b, c) is positively oriented if and only if det g = (a b)(b c)(c a) is a quadratic residue (mod 7). Similarly, one can check that (a, b, oo) is positively oriented if and only if (b a) is a quadratic residue (mod 7). Here is our rule for coloring the faces of the (2, 3, 7) tesselation. Rule 2. Define Cf A ABC) = n if and only if {L(A), L(B), L(C)} c Sn or {L(A), L(B), L(C)} c Sns where Sn = {n, n + 1, n + 3, oo}. (As usual, all the additions are modulo 7. Sn denotes the complement of Sn in Z7 U {°°}.) An alternate definition for the sets SnS and the reason for choosing these particular sets, is given in the next lemma. Lemma 2. Let W be the following collection of subsets of Z7 U {°°}: W = {{a, b, c, d}|(a, b, c, d) = 3 iff( a, b, c) is positively oriented) . Then W = {SnS SnClO < n < 6}, and W is a (3, 4, 8) Steiner system. 1995] HYPERBOLIC PLANE COLORING AND SIMPLE GROUP OF ORDER 168 709 This content downloaded from 157.55.39.246 on Tue, 27 Sep 2016 05:30:31 UTC All use subject to http://about.jstor.org/terms (For the definition of a Steiner system, see, for example, [4].) Proof: It is easily checked that the sets {0, 1, 3, oo} and {2, 4, 5, 6} are in 9, and it follows for the remaining S,7SSS since they are obtained from these two by a translation (mod 7). Next we note that for each of the (8) = 56 triples {a, bSc} c Z7 U {C°} there is a unique d which satisfies the condition in the definition of W. This shows that W is a Steiner system. Since each set {a, b, c, d} E W can be generated from four different triples, there are 14 elements in i?. Thus the 14 sets of the form Sn and Sn must be all the elements of W. The fact that W is a Steiner system is required for the coloring C defined in rule 2 even to make sense: we need to know that for each set of three vertex labels, there is only one and only one color that can be assigned to that set. Now we confirm that this coloring solves the problem stated at the beginning. Theorem 3. C defines a coloring of F such that no two triang,Zes of the same color share a uertex. Proof: Suppose C(t ABC) = C(t ADE). Then {L(A), L(B), L(C)} and {L(A), L(D), L(E)} are either both in Sn or both in Sn, since they are not disjoint. This means that the sets have at least two elements in common. Since all the vertices adjacent to A have distinct labelings (a simple consequence of the construction in Lemma 1), this means that the original triangles also have two points in common. Suppose? without loss of generalitr, C = D. If B = E also, we are done. Otherwise, let a = L(A), b = L(B), c = L(C) e = L(E). By Rule 1, (a, c, b, e) = -1. But from Lemma 2 and the fact that {a, c, b, e} = Sn or Sn it follows that (a, c, b, e) = 3 or 5. By contradiction, we conclude that A ABC = A ADE. Solution 3. We can describe the coloring of Figure 1 in yet another way, using a highlighting of edges instead of a labeling of vertices. Proceeding counterclockwise, highlight the seven central edges of the tesselation in colors 0, 1? . . ., 6. Extend this to a highlighting of E by the following rules: Rule 1. The three edges of any triangle must be highlighted in colors that correspond to three collinear paints in the projectiue plane illustrated in Figure 3. (Thus, for example, if two edges of a tnangle are highlighted 0 and 1, then the third edge must be highlighted 3.) Rule 2. The seven edges incident at sny vertex A must be highlighted in colors +(°) +(1)? . . . S +(6) proceeding counterclocXise around A, where + is an automorphism of the projective plane. For example, as Figure 4 illustrates, if three consecutive edges are highlighted 0, 6 5 (proceedings counterclockwise about a point A), then the remaining edges must be highlighted 2, 1, 3, 4, in that order. Finally, note that the lines in our projective plane have been labeled in such a way that {a, b, c} are collinear {a, b, c, m} Sn, 710 HYPERBOLIC PLANE COLORING AND SIMPLE GROUP OF ORDER 168 [October This content downloaded from 157.55.39.246 on Tue, 27 Sep 2016 05:30:31 UTC All use subject to http://about.jstor.org/terms