Message #135

From: Nathanael Berglund <berglund@math.gatech.edu>
Subject: Re: [MC4D] "Physical models" of Rubik’s Cube (tesseract, hypercube, etc.)
Date: Tue, 19 Apr 2005 13:46:47 -0400

It’s fun to see some mathematics happening in this forum. Although
actually solving a Rubik’s Hypercube is certainly interesting, the mere
fact that we’re trying to generalize Rubik’s Cube into higher dimensions
suggests we have some interest in the mathematics of it.

I realize I should have been more explicit when I said "orthogonal
inertial rotations", since the rotations David gave are orthogonal in
the sense that their axes are orthogonal, and certainly they don’t
commute. Here’s what I mean by "orthogonal inertial rotations":
Let p1 and p2 be any two orthonormal vectors. Let P denote the
orthogonal projection onto the subspace spanned by p1 and p2 and Q
denote (I - P) (i.e. the projection onto the orthogonal complement of
this space). Let R denote any 2-dimensional rotation defined over (and
staying within) span{p1, p2}. Then R represents an inertial rotation on
the entire ambient space defined by PR + Q. Conversely, if one is given
a rotation K and there exist p1, p2, and R such that K = PR+Q (P and Q
as defined by p1,p2), then we call K an "inertial rotation". Let
"plane(K)" denote span{p1, p2}.
By "orthogonal inertial rotations" K1, K2, … , Kn I mean to say
inertial rotations for which plane(K1), plane(K2), … , plane(Kn) are
all mutually orthogonal as subspaces. Note that at least 4 dimensions
are required in order to have orthogonal inertial rotations. The fact
that these commute is not hard to see (simply construct an orthonormal
basis from the basis vectors for plane(K1), plane(K2), … , plane(Kn),
and whatever additional vectors are required, and express the inertial
rotations in this basis.) The fact that any rotation can be decomposed
into these "orthogonal inertial rotations" is based on the Shur
Decomposition. I have a proof of it in case anyone would like to see it.

The question that I have then becomes "What is the set of inertial
rotations I get when I decompose each of the 192 rotations of the
hypercube?", and more importantly "Are these inertial rotations a subset
of the original 192?" Allowing a rotation which doesn’t put the
hypercube back in it’s place would be bad. If the answer to the second
question is ‘yes’, then since any sequence of orthogonal inertial
rotations would be "conceptually independent" to the user there is no
need to have moves which perform two or more of them simultaneously.
This would be akin to having, for example, a single move that rotates
one side of a Rubik’s 4-Cube while simultaneously rotating the opposite
side (Since rotating both sides exactly the same way has a nice
interpretation as rotating a center slice, there is an argument for
keeping such a move around, but besides that case such a move would
serve only to add unnecessary complication.)
As an example consider the two rotations:
x <- -y
y <- x
z <- z
w <- w
and
x <- x
y <- y
z <- -w
w <- z
I would argue there is no need to have a move which performs these
rotations simultaneously.

– Nate

David Vanderschel wrote:

> On Wednesday, April 13, "Nathanael Berglund"
> <berglund@math.gatech.edu> wrote:
> >If you’ve never taken apart a Rubik’s Cube, I
> >recommend you find an old well worn one and try it.
>
> How to do it: Rotate a face, say the top one, 45
> degrees. You can then pry up the edge pieces of the
> top face, popping them out without damaging anything.
> (You can even do this on a new puzzle.)
>
> >It’s great fun! If you do so you will notice that
> >the pieces have some surfaces which fit together to
> >form a sphere (O.K., so it’s not exactly a sphere.
>
> I would say that the pieces have interior edges (one
> dimensional) which lie on (or near) the surface of a
> sphere. It is those edges behind which hook the
> ‘blocks’ extending inwards from the corner and edge
> pieces to hold them in. Only small portions of the
> sphere are realized, but that spherical shape is what
> permits the move flexibility.
>
> >The center piece consists of three mutually
> >perpendicular cylinders to which the six center
> >pieces attach. Seeing the cube taken apart, it
> >becomes quite clear why the center pieces don’t ever
> >change position. How these cylinders stay attached
> >is a black box to me, since I don’t think I can take
> >that part apart without breaking it (if anyone knows
> >how this actually works, I would be interested in
> >hearing about it).
>
> I recall seeing a cube with stickers removed, and
> there was a screw in the middle of each face piece.
> (But not all cubes are made the same way.)
>
> Inside each cylinder, there is a spring which pulls
> the face piece towards the center, with the cylinder
> stopping it at the right distance. During turning,
> the face piece just slides rotationally on the end of
> the cylinder. I think it would be difficult to make
> it work without the bit of slop that those springs
> allow for. I do not know which end of the spring has
> the pivot; but I see no difficulty accomplishing such
> a pivot, and I do not see why you would need more than
> one cylinder. Some cubes make creaking noises when
> you twist them because of the springs dragging inside.
>
> >As a mathematician, of course I want to find an
> >explicit formalization of this model.
>
> I infer that the point of Nate’s message is that he
> claims to have achieved this objective. However, I
> must say that I remain confused about just what has
> been achieved. As far as I can tell, Nate has come up
> with a way of mathematically defining some 3-space
> point sets whose shapes (for corners and edges)
> correspond well to the shapes actually invented by
> Rubik. Because they are based on the internal sphere,
> they permit the required motions. But I think I must
> still be missing something here, because I wind up
> saying to myself, "So what?" Clearly a real physical
> model can exist, because Rubik’s Cubes do work! The
> fact that the shapes of the pieces of a working
> physical realization can be captured via a
> mathematical point-set description does not surprise
> me.
>
> >With this physical model, we know a posteri that the
> >only possible moves are multiples of 90 degree
> >rotations about the coordinate axes, or some
> >combination of these.
>
> I am not so sure about the "a posteriori" aspect of
> this inference. It seems to me that it results more
> from conscious intent and design.
>
> >Of course a physical Rubik’s cube can be taken apart,
> >but the theoretical one just constructed cannot be
> >(or at least, that is my conjecture).
>
> If I read Nate’s models correctly, it appears that his
> model adequately reflects the blocks which extend
> inwards (beyond the extent of the corresponding
> cubical piece and into the interior ‘sphere’) from the
> edge and corner pieces and which hook behind the edges
> of adjacent pieces which lie on the sphere. I agree
> that it cannot be taken apart. This is because Nate’s
> ‘theoretical’ face spindles do not have springs in
> them.
>
> It appears that a mathematical model has been achieved
> which captures the property of this thing hanging
> together. But this does not bear on solving the
> puzzle. For my own purposes as a mathematician, it
> seems to me that the simpler model - expressed as a
> 3x3x3 pile of 1x1x1 cubies, along with a description
> of the motions permitted for certain subsets of those
> cubies (the 3x3x1 slices) - captures the nature of the
> puzzle better and is certainly easier to work with.
> As a mathematician, I am anxious to _avoid_ details
> related to the actual mechanics of a realization of
> the object.
>
> >We also know that these rotations form a group (I
> >claim this is obvious from the fact that these are
> >invertible functions applied from a set of states to
> >itself, one of which leaves the state unchanged).
>
> To me, it is obvious because it can be viewed as a set
> of permutations on the 54 stickers. (Actually 48,
> since the face cubies don’t move.) Permutation groups
> are pretty well understood.
>
> >HIGHER DIMENSIONAL "GEOMETRIC" GENERALIZATION:
>
> >One will notice that this ‘physical model’ allows all
> >of the moves one would expect for a Rubik’s
> >Hypercube. However, also observe that any of the
> >eight ‘cubical sides’ of this model can be subjected
> >to all of the usual moves allowed for a 3-d Rubik’s
> >Cube without causing any self-intersections either.
> >Thus the natural generalization of the physical model
> >leads to a quite different puzzle than the natural
> >algebraic generalization of Rubik’s Cube.
>
> The same conclusion could be drawn regarding the
> puzzle as a 3x3x3x3 pile of hypercubies. Given a
> 3x3x3x1 pile corresponding to a hyperface, you can
> ignore the dimension in which the pile is thin and
> think of it as a 3x3x3 pile as with Rubik’s Cube -
> ie., turning 3x3x1 subsets with respect to the rest of
> the pile. My point is that Nate’s "physical model" is
> not the only approach which could lead one to consider
> moves which permute only a subset of the pieces
> corresponding to a hyperface. Indeed, the same notion
> falls out in a more easily graspable manner with the
> pile of hypercubies approach.
>
> >My personal experience seem to be that the physical
> >generalization is somewhat easier to solve, due to
> >the increased number of allowable moves, combined
> >with the fact that once 2/3 of the Rubik’s Hypercube
> >is solved, the problem reduces to merely solving a
> >3-d Rubik’s Cube.
>
> Indeed, it is much easier. Ironically though, the
> corresponding group is much larger - which some
> might regard as corresponding to greater complexity.
>
> Actually, the group is not as much larger as you might
> think. It turns out that the smaller group already
> includes the move that turns a center 3x3x1x1 slice of
> a 3x3x3x1 pile. Such a move is not even difficult to
> discover. Turning an external 3x3x1x1 slice of a
> 3x3x3x1 pile is the type of permutation that Nate
> added.
>
> Nate, have you convinced yourself that your 4D model
> cannot fall apart? I have difficulty thinking about
> how the hooks work in the 4D case, and I cannot
> convince myself. I am not saying that it is not
> true - just that it is not obvious to me. I am
> particularly concerned about how the hook on a
> 2-sticker piece works.
>
> >I should mention that I have also thought of a 4-d
> >model that would allow only the moves usually allowed
> >in the Rubik’s 4-Cube, but it is much more
> >complicated geometrically. At this point I have not
> >put down specific numbers for it, but have managed to
> >convince myself of it’s existence.
>
> I would be very surprised if such a model exists. The
> reason is that a valid model must support turning a
> center 3x3x1x1 slice of a 3x3x3x1 pile. (Not in a
> single move - but without affecting anything else.
> Ie., the group admits this permutation.) So the
> constraint in the smaller group is that there is some
> sense in which opposite external slices of an affected
> 3x3x3x1 pile must maintain the same orientation
> relative to one another. Given that the center slice
> between them _can_ turn and that this is true for each
> of the three relevant axes, it strikes me that that
> constraint would be difficult to achieve in a
> ‘physical’ model - even granting the existence of 4D
> construction materials. If it turns out that it is
> possible, I will be very impressed.
>
> In response to Melinda, Nate wrote:
> >Indeed, from the point of view of algebra, both of
> >your models yield the same set of possible states. In
> >fact, I believe with my "physical model" all the
> >rotations in MagicCube4D are possible, and no
> >detaching of hyperfaces is necessary.
>
> That’s a good point. I think "detachment" is
> primarily just a way of speaking. Just looking at
> MC4D’s animated projection into 3D is helpful for me
> to convince myself that rotating a hyperface about
> axes that are not aligned with coordinate axes does
> not lead to pieces intersecting. (It takes some
> imagination.)
>
> >The elegance of MagicCube4D is that it contains a
> >direct move (i.e. geodesic, inertial rotation, or
> >2-dimensional rotation, whichever you like to call
> >it) to each of the 23 (24 if you count the null
> >rotation) rotations.
>
> It has struck me as extremely elegant that the 23
> reorientations of a cube can be obtained by 2D
> rotations about the axes which pass through corner,
> edge, and face positions. There are 4 such axes
> through corners admitting 2 new twist positions each.
> There are 6 such axes through edge-middles admitting 1
> new twist position each. There are 3 such axes
> through the face-centers, admitting 3 new positions
> each. 4x2+6x1+3x3 = 23. Clearly the reorientations
> are all different. (So that was actually a proof by
> enumeration, since we know that there cannot be more
> than 24, counting the identity transformation.) I
> doubt that this elegance is just a happy accident, but
> I have never come up with an intuitive argument about
> why it _should_ be possible to represent all the
> reorientations in this way. I wrote a program which,
> given a reorientation transformation represented as a
> 3x3 matrix, directly computes which single axis to
> twist about. It is not trivial.
>
> >Any more rotations than this would not gain the user
> >anything, and any less would make some moves
> >unnecessarily burdensome. For Rubik’s 5-cubes and
> >higher, non-inertial rotations become possible (since
> >the hyperfaces are now 4-cubes). However, one could
> >make an argument against allowing such rotations in a
> >UI, since as a consequence of the Shur Decomposition
> >Theorem any such rotation can be written as the
> >product of orthogonal 2-dimensional rotations, which
> >being orthogonal must commute,
>
> There is something here that I do not understand at
> all: Even 90 degree rotations of a 3-cube about two
> different coordinate axes (clearly orthogonal) do not
> commute.
>
> >and so conceptually these rotations would be
> >independent from each other.
>
> >This would bring down the 192 rotations possible for
> >a 4-cube shaped side to a smaller, perhaps more
> >reasonable number (I’m not quite sure what that
> >number is. If anyone has a way of calculating it, I
> >would be interested to know about it.)
>
> But Nate has already mentioned that, if 90 degree
> turns about any two axes are permitted, then those two
> moves generate the entire group of 192 such rotations
> of the 4-cube. Since I like 90 degree coordinate-
> axis-aligned twists, I don’t see much opportunity for
> a method of reducing this which would make sense.
> But, as long as the coordinate-axis-aligned twists are
> in the UI, then all 192 reorientations can still be
> generated. The impact is on twist-count. I think it
> is still cleaner to regard any such reorientation as
> being a single twist, no matter how one specifies it.
>
> (Where 192 comes from: A reorienting transformation
> must map each of the 4 axis-aligned unit vectors onto
> itself or another, and there are 24 ways to permute
> them. For each mapping of a basis vector onto a basis
> vector, there may be a sign change. There are 2^4
> ways of assigning signs. When you multiply it out,
> you get 384; but half of those are mirror-image
> transformations which are not permitted.)
>
> Regards,
> David V.
>
>
> ————————————————————————
> Yahoo! Groups Links
>
> * To visit your group on the web, go to:
> http://groups.yahoo.com/group/4D_Cubing/
>
> * To unsubscribe from this group, send an email to:
> 4D_Cubing-unsubscribe@yahoogroups.com
> <mailto:4D_Cubing-unsubscribe@yahoogroups.com?subject=Unsubscribe>
>
> * Your use of Yahoo! Groups is subject to the Yahoo! Terms of
> Service <http://docs.yahoo.com/info/terms/>.
>
>