REGULAR POLYHEDRA AND SIMPLE GROUPS The lecture had two basic topics: regular polyhedra and harmonic graphs. (The simple groups in the title were there for roughly the same reason as the costumes in a music video: to enhance the musical experience.) In the lecture I probably explained the connection between the actual topics and simple groups only in the vaguest terms, and I won't repeat any of it here. I'll put the two problems on top of this message, and follow them with a little bit of background from the lecture. ******************************************** PROBLEM 1. Give an example of an INFINITE harmonic graph (same axioms, but with an infinite set of vertices). Better yet (extra credit?) give a complete list of all infinite harmonic graphs. ******************************************** ******************************************** PROBLEM 2. Given a cube C centered at the origin in three dimensions, explain how to find a regular octahedron O (figure whose eight sides are equilateral triangles) which has exactly the same rotational symmetries as C. To make the problem more concrete (and to make it easier for the poor graders to tell whether your description makes sense): if the cube has vertices with coordinates (plus or minus 1, plus or minus 1, plus or minus 1) then write down the coordinates of the vertices of the octahedron you describe. ******************************************** BACKGROUND ON HARMONIC GRAPHS A "harmonic graph" is a graph (set of vertices together with set of edges, which are unordered pairs of distinct vertices. Difference from Spielman's lecture: the same edge is allowed to appear several times. Infinite graphs are allowed.) together with a positive integer "weight" attached to each vertex, and a distinguished "base" vertex. To be a harmonic graph, these are required to satisfy 1) The graph is connected: starting from any vertex, you can get to any other vertex by a chain of edges. 2) The base vertex has weight 1. 3) The weight of each vertex is equal to one half the sum of the weights of adjacent vertices. (If two vertices are joined by several edges, then the weights appear several times in the sum.) ------------------------------------ The most degenerate example of a harmonic graph has two vertices (the base and one other, each of weight 1) joined to each other by two edges. Other examples are... - type A_n (a loop of n+1 vertices, each of weight 1, n at least 1) 1 1 \ / - type D_n 2 - 2 - 2 - 2....2 (n+1 vertices, n at least 4; base / \ vertex in the upper left) 1 1 1 | 2 | - type E_6 1 - 2 - 3 - 2 - 1 (7 vertices, base on the top) 2 | - type E_7 1 - 2 - 3 - 4 - 3 - 2 - 1 (8 vertices, base on left) 3 | - type E_8 1 - 2 - 3 - 4 - 5 - 6 - 4 - 2 (9 vertices, base on left) ----------------------------------------- That's all the finite examples there are. To see that, think about how you might construct all possible harmonic graphs by starting at the base vertex and working out. The base has to have neighbors whose weights add up to two. There are three possibilities: (A) one neighbor of weight 2, (B) two neighbors of weight 1, or (C) one double neighbor of weight 1. Then look at a neighbor, and see what the possibilities for _its_ neighbors are. You already know one of them: the base, with weight 1. In case (C), there's no room for more neighbors; so you're in type A_1. In case (B), each neighbor must have one additional neighbor, of weight 1. Continuing with case (B) leads to type A_n. In case A, the weight of your second vertex is 2, so the weights of its neighbors must add up to 4. 1 is accounted for by the base vertex, so the new neighbors of the second vertex must have weights adding up to 3. There are three possibilities: three new vertices of weight 1 (leading to D_4), one new vertex of weight 2 and one of weight 1 (leading to other D_n), or one new vertex of weight 3 (leading to type E). Et cetera. ******************************************** BACKGROUND ON REGULAR POLYHEDRA Suppose P is a shape in two- or three-dimensional space. The "rotational symmetry group of P" means the collection of all rotations of space that preserve the shape P. Suppose for example that P is a regular pentagon centered at the origin in the plane. Then the rotational symmetry group consists of all (five) rotations of the plane through multiples of 72 degrees. The answer doesn't depend on how big the pentagon is, or how it's oriented in the plane; it only depends on the number of sides, and the fact that it's regular. In three-dimensional space, things are more complicated: two completely different regular polyhedra can have exactly the same rotational symmetry group. Here's a way to think about finding the rotational symmetries of a polyhedron P. I'll assume the center of mass of the polyhedron is at the origin. The polyhedron is made up of various faces, edges, and vertices. Think of a face as NOT including its edges, and think of an edge as NOT including the vertices at its ends. Then every point of the polyhedron is on exactly one face, or exactly one edge, or exactly one vertex (_exclusive_ or). A non-trivial rotation of space is always a clockwise rotation through a certain number of degrees around a certain axis; think of the axis as a line through the origin. The angle of rotation can be anything between 0 and 360 degrees; 0 and 360 are not allowed for non-trivial rotations. Suppose that the non-trivial rotation through THETA degrees around the axis R is a symmetry of our polyhedron P. The line R has to cut through the polyhedron in two points; we'll concentrate on one of them, and call it A. There are three cases: 1) A is a vertex V 2) A is on an edge E 3) A is on a face F Let's look at case 2) for definiteness; 1) is easier, and 3) is not much harder. Since the rotation around R by THETA degrees preserves P, and fixes the point A, it follows that the rotation of E is an edge of P containing A; so rotation of E = E The only way that can happen is if THETA = 180 degrees, and A is the midpoint of E. Arguing like this leads to ----------------------------------------------------------------------- PROPOSTION. Suppose P is a regular polyhedron, with faces which are regular n-gons, and m edges meeting at each vertex. The rotational symmetries of P are 1) the trivial rotation 2) rotation by (360 p)/m degrees around the line through each vertex, for 1 < p < m 3) rotation by 180 degree around the line through the midpoint of each edge 4) rotation by (360 q)/n degrees around the line through the midpoint of each face, for 1 < q < m. In this list, every non-trivial rotation has been counted twice. ----------------------------------------------------------------------- EXAMPLE: P = tetrahedron. The tetrahedron has 4 vertices, with 3 edges meeting at each vertex. There are 6 edges. The four faces are equilateral triangles, or "3-gons." Here is the list of symmetries 1) trivial rotation 2) rotation by 120 and 240 degrees around each vertex: total of 8 rotations. 3) rotation by 180 degrees around the midpoint of each edge: 6 rotations. 4) rotations by 120 and 240 degrees around the midpoint of each face: 8 rotations. Total number of rotational symmetries: 1 + (1/2)(8 + 6 + 8) = 12.