April 7: A_4, S_4, A_5, and the other finite triangle groups via Cayley graphs The classification of subgroups of PSL_2(F) includes as special cases the three groups A_4, S_4, A_5. As noted already last time, these are the groups of rotations (= orientation-preserving isometries) of the regular solids in three dimensions: A_4 : tetrahedron (even permutations of the four vertices, or equivalently of the four faces which are in natural bijection with the vertices) S_4 : cube = hexahedron (any permutation of the four long diagonals); dually, octahedron (any permutation of the four pairs of opposite faces) A_5 : dodecahedron (any even permutation of the five inscribed cubes) dually, icosahedron (can you find a natural set of five objects?) Each is a subgroup of SO_3(R), which is contained in the group PSL_2(C) of automorphisms of the Riemann sphere (C is algebraically closed so every number is a square and PSL_2 = PGL_2); once we choose some explicit matrices with algebraic coefficients we can find these groups in PSL_2(F) for suitable finite F by reducing modulo a prime. But that requires algebraic number theory and it's not easy to make sure we have all the examples. Instead we'll use an approach which combines two familiar ideas but ones that get little actual use: Cayley graphs, which are usually introduced only as a visualization device; and generators and relations, which are usually very hard to apply in any nontrivial space. Specifically we'll show that each of A_4, S_4, A_5 is generated by elements b,c,d subject (only) to the relations b^2 = c^3 = d^n = bcd = 1 with n=3,4,5 respectively. Explicitly: A_4: n=3, b = (1 2) (3 4), c = (1 2 3), d = (2 3 4) [*any* double transposition and 3-cycle will do] S_4: n=4, b = (1 2), c = (2 3 4), bc = (1 2 3 4) A_5: n=5, b = (1 5) (2 3), c = (1 3 4), bc = (1 2 3 4 5) We can use bcd=1 to solve for any one of the generators, e.g. d=(bc)^{-1}, and get a presentation with only two generators -- the minimum for a non-cyclic group [though this is not so remarkable because lots of interesting groups can be generated by only two generators, including all simple groups]. For instance c and d can be taken to be rotations about a face and a vertex respectively of the regular solids with 4, 8, and 20 triangles (with the face containing the vertex). Thus the reason we stop at 5 is ultimately that 1/2 + 1/3 + 1/n must exceed 1 (which is also why one of the other exponents must be 2). The _Cayley graph_, call it C(G,S), of a group G with respect to a set S of generators is a directed graph with vertices G and edges of |S| kinds ("colors"), one for each element s of S: there's an s edge going from g to h iff h=sg. The graph is connected because S generates G. It is not necessarily connected as a directed graph (i.e. there may be g,h for which there's no *directed* path from g to h -- example: (G,S)=(Z,{1}) and hh iff there's an s^{-1} edge h-->g; there's usually no reason to let S include both s and its inverse, because once we have s we're already allowed to use s^{-1} to generate G -- unless s its own inverse. We assume that S does not contain both s and s^{-1} unless s = s^{-1}, that is, s^2 = 1. In that case there's an s edge from g to h iff there's one from h to g, so we simplify by combining them to a single _undirected_ edge. There are then no g,h for which both g-->h and h-->g are directed edges in C(G,S) (because if h=sg then g=s^{-1}h). Examples: i) nontrivial cyclic groups, (G,S) = (Z/nZ, {1}) or (Z, {1}). If n=2 we get a complete graph on two vertices; for n>2 it's a directed cycle of length n; for (Z,{1}), an infinite directed path. We may use redundant generators (except for s^{-1}), e.g. Z/6Z, {1,3}) or (Z/6Z, {1,2}). What happens for (Z/6Z, {2,3})? Note that this actually doesn't have any redundancy even though 1 generator suffices. ii) Dihedral groups. Example: S_3 with generators the 2-cycles (1 2) and (1 3) gives id -- (1 2) == (1 2 3) -- (2 3) == (1 3 2) -- (1 3) == id so we have our benzene ring again (and indeed S_3 is the group of automorphisms that take each "bond" to another bond of the same type). More generally the dihedral group of 2n elements has two generators g1, g2 satisfying g1^2 = g2^2 = (g1 g2)^n = 1 and then C(D_n, {g1,g2}) is a cycle of 2n edges of alternating types. Generators and relations: Here a group (usually finitely-generated, but not necessarily finite) is specified by generators g_1,...,g_n and relations that may be written either r_1,...,r_N [N needn't equal n] or r_j=1 or r'_j=r"_j, to the same effect (the last being equivalent to r'_j (r"_j)^{-1}). For example, Z is just , a cyclic group of order k is , a free group on n generators is , a free abelian group on the same generators is , and any finite abelian group can be obtained from that by adding some more relations -- in fact it's a standard theorem that we can choose the generators so that the extra relations are g_i^k_i with k_1 | k_2 | ... | k_n and the group determines the k_i except for prepending some 1's at the beginning. Such presentations are useful because to construct a map G --> H it is necessary and sufficient to find h_i in H satisfying the same relations. That is how we'll use it, at any rate. The problem is that for a large finite but non-abelian group it can be very hard to find such a presentation with few generators and relations. We can certainly do it with |G| generators and |G|^2 relations; and we can usually find very few generators g_1,...,g_n (n may be as small as 2) and some relations r_1,...,r_N; but how do we know it's enough that the map from the resulting group, call it Gamma, to G is an isomorphism? That's generally too hard; for general g_i and r_j it is known to be literally undecidable even whether Gamma is finite, or trivial! Happily in our setting we can use the lowly Cayley graph to answer the question. Remember we're looking at b^2 = c^3 = d^n = bcd = 1 consider first the simpler b^2 = c^2 = d^n = bcd = 1 that is, b^2 = c^2 = (bc)^n = 1 and use b and c as Cayley generators. Before imposing the condition (bc)^n=1 it's an infinite group, and the Cayley graph is just an infinite path of alternating b's and c's. That's the infinite dihedral group, a.k.a. the Ax+B group over Z -- since A must be invertible it's either 1 or -1, so we have the semidirect product, generated by x --> x+1 and x <--> -x, and we can take b: x <--> -x and c: x <--> 1-x. Then bc is x --> -(1-x) = x-1 which is of infinite order. Forcing it to have order n makes the Cayley graph close up after n+n steps and we get the dihedral group of order 2n. Now to be sure this case wasn't hard: any group element must be a finite word of alternating b's and c's, so (bc)^n=1 reduces to 2n possible words and since D_{2n} satisfies all those conditions we've found our group. But for b^2 = c^3 = (bc)^n = 1 it's tricker. We can use either c or d=bc as the second generator, and we'll go with d (which makes no difference for n=3 but gives rise to more familiar pictures for n=4 and n=5). Now we have n-gons of d's linked by b bonds subject to (bd)^3 = (bbc)^3 = c^3 = 1, so a graph with two bdbdbd hexagons and one n-gon of d's at each vertex -- and this exactly gives us the 12, 24, or 60 vertices of the truncated tetra-, octa-, and icosahedron! So: to find a copy of S_4 in H, just find non-identity b,c,d in H with b^2 = c^3 = d^4 = bcd = 1. This gives a map S_4 --> H. The kernel is normal, and the only nontrivial possibility is V, but then the image is S_3, making d^2 = 1. So if d^2 = 1 we get the 6-element dihedral group (as we already knew), and if d is actually of order 4 we have S_4. Likewise for A_4 and A_5, changing d^4=1 to d^3=1 or d^5=1 respectively (and without any annoying normal subgroup to worry about -- e.g. the kernel from A_4 couldn't be V because then the image would be Z/3 and b would be the identity). We'll use this to describe when these groups can be found in PSL_2(F_q). The outcome is: A_4: always unless q is an odd power of 2 S_4: iff q is odd and 24 | #PSL_2(F_q) and nicest of all: A_5: iff 60 | #PSL_2(F_q) we'll also give the explicit congruence criteria on q mod 8 or 5 that check those divisibility conditions.