From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Q about dodecahedra Date: 10 Jul 1998 21:56:06 GMT In article , Jan Kristian Haugland wrote: >Is this conjecture of mine a known theorem, or easy to >prove, or false? (It's not awfully interesting in itself, >but related to something else I've been thinking about ;-)) I don't know if it's been studied, I think it's false, and it's a lot more interesting than some of the junk we see here! > "It is impossible to glue together a finite number > of regular dodecahedra of the same size face-to-face, > edge-to-edge, in Euclidean 3D-space, in such a way that > each dodecahedron has exactly two neighbours." I wish I had twelve dodecahedra handy to test this, but can't you form them into a (almost planar) hexagon? When you stack three in a row, the top is simply a translation of the bottom by four times the vector from the center of the inscribed sphere to the center of the circle inscribed on the face through which you pass. You could of course stack another pair atop the first pair, or build out from any of the five faces adjacent to the top. Choosing the latter option translates by four times a _different_ vector, and again we have the option of building on any of the faces adjacent to the one we just used. Choosing one of the lower two options takes us, um, further *that* way, and, er, a little down *this* way, and uh, a little off the plane of the previous four cells. Now the point is that among the faces from which to build next is the bottom-most face, so we attach another pair of cells there, and proceed to return to the origin by attaching pairs of cells to the faces opposite from the previous choices. The net result is a translation by 4v1 + 4v2 + 4v3 + 4(-v1) + 4(-v2) + 4(-v3) = 0. Of course if your dodecahedra are just wireframes (so that they can intersect) you can use just 8 cells by travelling in just two directions instead of three. It seems to me the more interesting question is whether or not there are other chains besides simple translations and their negatives: A. One can show that the only chains which can be made by simple translations are those with "obvious" cancellation as above. (The six translations are linearly independent over Q.) B. One can also show that the set of motions forms something like a free group: if you never stack three in a row as I did above, you can't come home again. (This is nontrivial.) C. One can _probably_ show that none of the combination moves work either, unless there is an obvious reason for cancellation; I didn't work this out. This remaining possibility boils down to the question of closing the loop with several manoeuvres like this: (start cell)+(Some long chain of cells)+(stack) ( of ) (finish cell)+(Identical chain of cells)+(three) which accomplish a translation in the direction of the small stack of three at the end, which is different from any of the directions on the starting cell. (If you insist on using solid dodecahedra, you must replace that stack of three with half the hexagon I built). dave ============================================================================== Date: Sat, 11 Jul 1998 13:21:47 +0100 (BST) From: Jan Kristian Haugland To: Dave Rusin Subject: Re: Q about dodecahedra Newsgroups: sci.math On 10 Jul 1998, Dave Rusin wrote: > B. One can also show that the set of motions forms something like a free > group: if you never stack three in a row as I did above, you can't > come home again. (This is nontrivial.) Have you proved this? This is actually what I really had in mind: No "three in a row" and no "sharp turns". I had a response poiting out the solution with 8, involving 2 x 3-in-a-row, before. Thanks! ============================================================================== From: Dave Rusin Date: Sat, 11 Jul 1998 12:38:42 -0500 (CDT) To: haugland@maths.ox.ac.uk Subject: Re: Q about dodecahedra Yes, I believed I proved it. In fact I thought I was going to be able to prove no closed chain of any sort existed, until I got to a hole in the proof, which led to the example. I'm glad I found the example, actually, because it made for a much shorter post than I was developing! For your reading pleasure I am attaching that draft post; you'll see it gives the proof you wanted, then fizzles as it tries to prove impossible something which in fact _is_ possible! By the way, what's the project? dave [Draft post follows] ================================================================== This is a very intriguing question; the answer is "no". First let's clarify the problem. When you want to piece together the dodecahedra, do you view them as solid or as wire-frames? In the former case there are local and global restrictions not present in the latter: first, the two neighbors of a single dodecahedron cannot meet it at adjacent faces (the dihedral angle at a meeting is less than that of a dodecahedron); second, one would have to ensure that as the chain of dodecahedra winds through space, they would have to avoid enclosing points in the interior of some previous cells. As it turns out, there is not even a way to build a chain of the wire-frame models which loops back, as we shall see. Now let's suppose you had such an arrangement of dodecahedra. Pick one cell to be the first one, and pick one of its neighbors to be second. Following from neighbor to neighbor we eventually want to loop back to the first one. (There may be more cells in your configuration, that is, a set of disjoint chains in space meets your conditions. It's sufficient to show there is no single chain, of course.) Assign to each of the 12 faces of the first cell a distinct color. Then you may color the other dodecahedra in succession, viewing the face where two neighbors meet as a mirror. (When the last cell meets the first, this assignment of colors may be incompatible with the original; the coloration forced upon the first cell at the end simply permutes the faces. According to taste one may either name this permutation and show that it is irrelevant, or repeat the cycle through the chain to obtain a longer, self-intersecting, chain of colored dodecahedra in space which returns properly colored to the original cell; one need only observe that every permutation of 12 colors is of finite order!) Now we have a notation to describe the chain. One may store the structure simply by recording the colors of the faces across which we reflect to pass from each cell to its neighbor. If the colors of reflection are, in order, c_1, c_2, c_3, ..., then there is an affine motion A(i) such that the i-th cell is simply the image of the first one under A(i). In fact, A(i) is just the composite of A(i-1) with a certain reflection, but this is not the easiest description of A(i) since the plane of reflection is itself wandering through space. We thus prefer this easier description: Lemma: A(i) = R(c_1) o R(c_1) o ... o R(c_i) where R(c) is the reflection of R^3 across the face of color c in the original dodecahedron. This lemma isn't entirely trivial; in fact, you'll notice that the composites appear to be taken in the WRONG order! Still, it's true, and easily proven by induction: the case i=1 is a consequence of the definitions, and A(i) = Ref o A(i-1) where Ref is the reflection across the plane of the c_i - colored face in the (i-1)-st cell. By induction, this face is A(i-1)( F ) where F is the appropriately-colored face in the first cell. Now, reflections across planes P have the property that for any affine map A, Ref( A(P) ) = A Ref(P) A^(-1), so the reflection we apply to obtain the i-th cell is Ref = A(i-1) R(c_i) A(i-1)^(-1) = [R(c_1) o ... o R(c_[i-1])] o R(c_i) o A(i-1)^(-1) so that A(i) = Ref o A(i-1) has the desired form, QED. So now the question on the floor is, is there a sequence c_1, ..., c_n of the twelve sides of the original dodecahedron such that R(c_1) o ... o R(c_n) = I (or, according to taste, = some member of the symmetry group Dod of orthogonal motions preserving the original dodecahedron; |Dod| = 120 ). Of course we insist that each c_i be distinct from c_(i-1) (and if we want to avoid self-intersecting chains of dodecahedra, we do so locally precisely by prescribing for each c which of the other six color c' may follow.) One may phrase this in purely group-theoretic terms as follows. Notice that for each face c of the dodecahedron there is an element sigma of Dod which carries the Blue face (say) to the given one; then as in the proof of the lemma, R(c) = sigma o R(Blue) o sigma^(inverse). Writing simply R for this refection across the blue face, and collecting adjacent terms in Dod, we are asking whether there is a set of elements alpha_i in Dod for which the product alpha_1 R alpha_2 R ... alpha_n R = I is trivial; the condition that the succesive c_i be distinct is now the condition that each alpha_i be non-identity. Thus the original question involving (wireframe) dodecahedra is equivalent to the following question in group theory: Is the subgroup (of the group of affine motions of R^3) generated by Dod and R simply the _free_ product of Dod and ? Now this formulation shows that the original question is a "real" question, and not a "toy", but it doesn't immediately make the answer easy to obtain. Indeed, demonstrating freeness of a product is usually accomplished by finding an appropriate action on something geometrical, that is, one would usually work back to something like the dodecahedra to solve this problem in group theory! However, we can answer this particular question in the affirmative using a little arithmetic. The short answer is that the reason no such product of affine motions can ever be the identity map is that every application of R picks up some more 5's in denominators; it will take a little while to set this up properly. Begin by selecting a coordinate system through the original dodecahedron so that the coordinates of the centers of the faces are the cyclic permutations of v1 = [0, 1, alpha] ( alpha = (1+sqrt(5))/2 ) and the three vectors obtained from v1 by changing signs of coordinates. If u is the vector at the origin pointing to the center of the face with color c then R(c) is the map which sends any vector v to [ v - ( 2 / ) u ] + 2u I would like to represent this reflection by a matrix B(c) (or B(u) ). Since we have a coordinate system picked out, we may represent the affine maps with matrices: a function of the form v -> M.v + w for some fixed 3x3 matrix M and 3x1 vector w is represented by the 4x4 matrix [ M w ] [ 0 1 ]. For us, w = 2u and M is the rotation matrix, obtained by storing in its columns the actions of the rotation on the basis vectors. For example, for u = v1, M is the matrix [ 0 0 0 ] I - (2/(1+alpha^2)) [ 0 1 alpha ] [ 0 alpha alpha^2 ] and of course the other relfections are obtained by permuting rows and columns cyclically, and by changing the sign of alpha . (The 3x3 reflection matrices for v1 and -v1 are the same, naturally.) Form the 4x4 matrix B with this M in the upper left and 2 v1 in the last column (with [0 0 0 1] in the last row); this is the matrix representation for the reflection across the face pointed to by v1. This is B(v1), and the other eleven B(v_i) are obtained by appropriate permutations and sign changes. The key issue here is that all the entries in B(v) are integers in the ring S = Z[alpha], EXCEPT for the presence of the multiplier 2/(1+alpha^2) = (sqrt(5)-1) / sqrt(5). We need only show that these denominators accumulate rather than cancel. Assume first we have a string of reflections R(c_1) o R(c_2) o ... o R(c_n) in which no adjacent pair of reflections is across opposite sides of the dodecahedron. We will show that this composite cannot be the identity map, i.e. that the matrix equation B(c_1) * B(c_2) * ... * B(c_n) = I in GL_4(R) cannot hold. Suppose it did. Multiply the equation by (sqrt(5))^n to obtain an equation among matrices in M_4( S ): (sqrt(5)*B(c_1)) * (sqrt(5)*B(c_2)) * ... * (sqrt(5)*B(c_n)) = 5^(n/2)*I Now reduce modulo the ideal ( sqrt(5) ) in S; note that S/(sqrt(5)) is naturally isomorphic to Z/5Z. The matrix on the right is the zero matrix. On the left we now have a number of factors each obtained from the reduction of sqrt(5)*B(v1) (which I calculate to be [ 0 0 0 0 ] [ 0 1 3 1 ] [ 0 3 4 3 ] [ 0 0 0 0 ] mod 5) by performing simultaneous cyclic permutations and sign changes of the first three rows and columns. Well, can a product of these be zero? Consider the shortest string of such matrices whose product is zero. This requires that the kernel of the left-most factor B1 include a nonzero vector in the image of the product of the others. That image is a subspace of the image of the last factor B2 in the product, so certainly the image of B2 must include a nonzero vector in the kernel of B1. But the image of B2 is the set of multiples of one vector, which has precisely two nonzero coordinates (including the fourth). On the other hand, the kernel of B1 includes few vectors with a 0 as their fourth coordinate and precisely one other 0 as well; indeed the only such vectors are those in the image of B1. Considering all the permutations of coordinates, it's easy to check that this means B1 and B2 must actually be reflections across either the same face or across opposite faces. Both of these have been disallowed by our assumptions, and a contradiction follows. No such product of reflections can be the identity map. There remains the possibility that two consecutive reflections are across opposite faces. In this case, the composite of the two is simply a translation, so that the product of the matrices B(v)B(-v) is just [ I 4v] [ 0 I ] which is already integral over S; so for each such pair we reduce the number of powers of sqrt(5) by two in the argument above. We still have a sequence of matrices over Z/5Z whose product should be zero, but now we allow for some matrices obtained from the usual permutations of [ 1 0 0 0 ] [ 0 1 0 1 ] [ 0 0 1 3 ] [ 0 0 0 1 ] as well. HMM. Eventually want to reduce to the case when we are multiplying by sqrt(5)^0, so that we want some translations to sum to I (not 0 mod 5). Note: 6 translations are lin indep/Q; just embed in Z^6 using real and imaginary parts. ============================================================================== Date: Sat, 11 Jul 1998 22:24:09 +0100 (BST) From: Jan Kristian Haugland To: Dave Rusin Subject: Re: Q about dodecahedra On Sat, 11 Jul 1998, Dave Rusin wrote: Thanks for the proof! I haven't tried to really *read* it yet, but it's nice to know that there is an argument supporting the (restricted) conjecture. > By the way, what's the project? Oh, long story. A long time ago, I "discovered" that if you 5-colour the dodecahedra in the 120-cell, and pick out the ones with 2 of the colours, you get a nice cubic graph with 48 vertices and girth 8, by taking the dodecahedra to be "vertices" and common faces to be edges. In August/September last year, I started wondering if one could do something similar in 3D-space. So I guess I was looking at induced cubic subgraphs of lattices, and for a long time I was only concerned with Z^3. How large can the girth be? I soon found one with girth 10, and it seemed like it was hard to improve on this even with noninduced subgraphs. Eventually, I did however find a noninduced subgraph with girth 12. It's easy to give an upper bound of 16. For a long time, I struggled trying to tightening the gap. Along the way, I stumbled across a new induced subgraph of girth 10, which I thought was very "pretty". So I once again turned my attention to the induced ones, and found yet another one of girth 10. After a while I also managed to prove - to myself - that the three I'd found are indeed the only ones. But then I had to get down to writing up my thesis, which is not on graphs but number theory! I thought about trying to write up the proof of the result recently, but I couldn't reproduce it from my notes, so I think I'll leave it as a "result without proof"! Instead, I thought about induced subgraphs of the FCC-lattice instead recently, and found that I could give some that were isomorphic to some of my subgraphs of Z^3. Then I found that I could give an isomorphic copy of the "pretty" graph I mentioned also by using 12 uniformly distributed unit vectors as "edges", and thought "cool, I can represent it by gluing together dodecahedra, maybe I should try to find out if one can do that with any other graph" but then I realized that they don't meet edge-to-edge in this case. That's why I started this thread, to see if I could go about this. If the answer was negative (as it has now turned out), then I can be happy with the representation I had. Maybe this isn't leading anywhere, but I've had fun so far. I defined "representation graphs" for the subgraphs of Z^3; finite cubic graphs where the edges are coloured and oriented to indicate where the neighbours are in 3D space. Surprisingly, two of the three induced cubic subgraphs of Z^3 with girth 10 have very small repr. graphs (a tetrahedron and a square with two double edges), whereas the last one has a repr. graph with 20 vertices. So it's much more complex, and I would nominate it for the "most beautiful graph ever" ;-) I may also have other candidates in view of the dodecahedron-representation, and I just had another idea for producing graphs in 3D- space with large girth... AND I also have some thoughts/results about what happens in higher dimensions, and with higher valency of the graphs. Oh well.