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.
__