Date: 22 Oct 1982 19:09-EDT
From: Dan Hoey at CMU-10A
Subject: The 2x2x2x2 magic tesseract
To: Cube-Lovers at MIT-MC

Allan Wechsler's message of 17 May 1982 contains some interesting
comments on the four-dimensional hyper-cube, or tesseract.  I will
expand on them, and offer a correction.

The tesseract has eight cubical sides, labeled Back, Front, Up,
Down, Left, Right, Out, and In.  Each side may be twisted in any of
the twenty-four ways that a cube may be rotated in three-space.
Since these twenty-four twists are generated by repeated
application of the six quarter-twists of the cube, I consider a
move to be a single quarter-twist of one of the cubical sides.

I have picked three of the quarter-twists of the Out side to be the
``clockwise'' twists, given as Of, Ou, and Or below.  Given the
constraint that clockwise twists must be conjugates of each other
with respect to the movement group of the tesseract in four-space,
the remaining clockwise quarter-twists are determined.  In the
following list, the upper-case letter denotes the side to be
twisted, and the quarter-twist is displayed as a permutation on the
(square) faces of that (cubical) side.

Of=(URDL)  Ou=(RFLB)  Or=(FUBD)     If=(RULD)  Iu=(FRBL)  Ir=(UFDB)
Ro=(UFDB)  Rf=(OUID)  Ru=(FOBI)     Lo=(FUBD)  Lf=(UODI)  Lu=(OFIB)
Ur=(OFIB)  Uo=(FRBL)  Uf=(ROLI)     Dr=(FOBI)  Do=(RFLB)  Df=(ORIL)
Fu=(ORIL)  Fr=(UODI)  Fo=(RULD)     Bu=(ROLI)  Br=(OUID)  Bo=(URDL)

These twists have the satisfying property that when two different
twists move an edge from position E1 to position E2, then one of
the twists is clockwise and the other counterclockwise.  For
instance, both the Dr and the Fr' twists move an edge from FID to
FOD.  Another property that mimics the three dimensional cube is
that clockwise twists on opposite sides are reversed:  The action
of Of on the O side is the inverse of the action of If on the I
side.

To see how the table above is constructed we must describe the
movement group of the tesseract (the group of whole-tesseract moves
in four-space).  I look at it as operating on quadruples VWXY of
mutually adjacent sides.  To see if VWXY->V'W'X'Y' is in the group,
replace all occurrences of B, D, L, and I with F, U, R, and O,
respectively.  The resulting permutation must have the same parity
as the number of replacements performed.  Thus FLOD->UROB is in the
group, because we perform three replacements to form FROU->UROF, an
odd permutation.

To tell whether a quarter-twist is clockwise or not, take the side
V to be twisted, two consecutive letters WX from the permutation,
and a fourth, orthogonal letter Y from {F, U, R, O}.  If VWXY->OURF
is in the movement group of the tesseract, then we have the
clockwise quarter-twist Vy, otherwise the counterclockwise
quarter-twist Vy'.  For instance, if we twist the U side as (LFRB),
then VWXY=ULFO->OURF is in the movement group (one replacement
creates the four-cycle URFO->OURF), so we have the clockwise twist
Uo.

Let us now examine the reachable configurations of the corners of
the tesseract.  Every quarter-twist moves eight corners in two
four-cycles, so only even permutations of the corners are
achievable.  The orientations of the corners are more complex.  If
we move corner VWXY to V'W'X'Y', then VWXY->V'W'X'Y' must be in the
movement group of the tesseract.  Thus only half of the twenty-four
permutations of {V', W', X', Y'} are achievable, because of the
permutation parity constraint.

To define the orientation of the corners, we label the sides of
each corner and each corner position with the letters VWXY, and
read the orientation of a cubie as the letters it has in the V, W,
X, and Y sides of its position.  It is important here to obey the
the permutation parity constraint when doing the labelling, so that
each cubie may be placed in the home (VWXY) orientation in any
position.  For instance, one possible labelling is as follows,
where each column refers to a corner:

V   F  F  F  F  F  F  F  F  B  B  B  B  B  B  B  B
W   U  U  U  U  D  D  D  D  U  U  U  U  D  D  D  D
X   R  O  L  I  O  L  I  R  O  L  I  R  R  O  L  I
Y   O  L  I  R  R  O  L  I  R  O  L  I  O  L  I  R

Thus if the FURO corner (column 1) is in the FLUO position (column
2), then its orientation is VXYW.  Any orientation that is an even
permutation of VWXY is possible.  The group of orientations, A4, is
the same as the movement group of the tetrahedron (with vertices
labeled VWXY) in three-space.

As I suggested in my message of 23 September 1982, this orientation
group is not Abelian, so the orientation of the last corner is not
completely determined by the orientations of the other fifteen.  To
see what is determined, let us look at the tetrahedron with
vertices at half of the corners of a three-dimensional cube, say
the FUR, FDL, BUL, and BDR corners.  As I reported on 15 June 1982,
the twelve movements of the tetrahedron consist of the identity,
three 180-degree rotations, and eight 120-degree rotations.  The
June message also mentions that if those corner cubies are moved as
a unit, preserving their positions and orientations relative to
each other, then the 180-degree rotations are achievable on the 3^3
(they are the corners of the Zig-Zag pattern) but the 120-degree
rotations violate the corner twist invariant.  Of course, four of
them perform a net clockwise twist, and four of them perform a net
counterclockwise twist.  Define the twist of a tetrahedron movement
to be the net clockwise twist it applies to the corners of the
cube.  Thus the twist of the movements of a tetrahedron VWXY is
given by the following table.

        Twist 0: VWXY, WVYX, XYVW, YXWV
        Twist 1: VXYW, WYXV, XVWY, YWVX
        Twist 2: VYWX, WXVY, XWYV, YVXW

By reasoning about the actions on corners of the cube, it is clear
that the twist of the product of two movements is the sum of their
twist, modulo three.  Thus the twist group is an Abelian quotient
of A4, isomorphic to the cyclic group on three elements.

Since the orientation group of the tesseract corners is also A4, we
may use the twist group to construct an orientation invariant of
the corners of the tesseract.  As described in the September
message, each qtw moves the corners in untwisted cycles, so the sum
of the twists of the orientations of the corners must be zero,
modulo 3.

I ran the Furst, Hopcroft, and Luks algorithm on the 2^4 tesseract
and found that this is the only invariant of corner orientation.
Therefore, the number of reachable positions of the tesseract is
(15! / 2) (12^15 / 3) ~ 3.358 x 10^18.  This is larger than Allan
Wechsler's upper bound because he thought there were only six
orientations of each corner.