Message #588

From: David Vanderschel <DvdS@Austin.RR.com>
Subject: Re: [MC4D] Something interesting and strange about permutations
Date: Fri, 26 Sep 2008 19:23:13 -0500

On Friday, September 26, "Melinda Green" <melinda@superliminal.com> wrote:
>… From my perspective Lucas is making a suggestion
>which is entirely reasonable (I.E. not wrong) but
>which Roice does not find satisfying. It doesn’t work
>very well for me either but it is not wrong. Roice
>on the other hand is suggesting a definition based on
>rotations– …

My perspective on that dialogue is a bit different.
I could not really discern any specific suggestion in
what Lucas wrote. What Roice wrote struck me as a
polite attempt to expose the logical flaws in what
Lucas had written. I thought Roice’s observations
were very perceptive. Roice mentioned the reflection
alternative as a point of interest, but I did not
perceive that he was suggesting it in an advocacy
mode.

>one that I preferred too, at least maybe until
>now. My shift in thinking didn’t come from the
>realization that MC2D didn’t seem to fit perfectly
>into this definition. It would be nice if it did fit
>but I was perfectly happy for it to be an exception,
>mostly useful for illustrating state graph properties
>for these puzzles. By the way, I added a nice image
>of the MC2D state graph to the applet page along with
>some descriptive text. See
>http://superliminal.com/cube/mc2d.html.

I have more to say in this regard, but I will wait and
make those comments in the earlier thread. (I got
behind on everything by trying to watch too much
Olympics coverage. Not caught up yet. :( )

>The thing that really struck me was Roice’s
>observation that rotations can always be described
>with pairs of reflections. This started me thinking
>that perhaps the "best" analogy might only involve
>reflection moves. Looked at this way, perhaps the
>original Rubik’s cube is the oddity which needed to
>use planar rotations to satisfy the practical demands
>of 3D objects in the physical world. It certainly
>makes for a fun and satisfying puzzle but perhaps we
>shouldn’t be more focused on the way that the plastic
>puzzle operates than the mathematical group that it
>operates upon.

If you admit reflections in addition to non-reflecting
reorientations, then you are introducing a lot more
possible permutations of the stickers. But the group
of the original non-reflecting puzzle remains as a
subgroup of the larger group that includes
reflections.

David Smith, you might want to consider extending your
permutation counting exercise to include also puzzles
with mirroring allowed. I am actually curious about
how many-fold is the increase even for the 3x3
3-puzzle. (For myself, the mirroring issue seems more
interesting than the super-supercube considerations.)

>So now we have the basis for defining a new analogy that can reproduce
>our puzzles in N dimensions:

> "A valid move is any combination of reflections of a hyperface
>that leaves its orientation unchanged."

Since all non-reflecting reorientations can be
achieved by reflecting pairs, this simply amounts to
adding reflection to what we already had. I.e., we
are just talking about the binary choice of adding
reflections - or not.

>MC2D moves only do interesting things with odd
>numbers of reflections,

? I do not understand the above statement. Why is a
4-cycle (Rotate corner positions.) not interesting?
[(1,2)(3,4)] * [(2,4)] = [(4,3,2,1)]

>and the Rubik’s cube is only physically implementable
>for even numbers. Looked at this way, perhaps the
>"best" version of MC3D would allow both odd and even
>numbers of reflections per move but with the option
>to restrict the available moves to even numbers of
>reflections in order to satisfy people with a
>nostalgia for physical reality. ;-) Looking at
>David’s implementation, I now see that this is
>exactly what he did although it is the default mode
>and that each reflecting click must be preceded by
>ctrl-q. David: I would love if you would add a new
>toggle so that plain clicks always perform reflection
>moves and ctrl-q clicks perform rotations.

I am pleased that you can imagine using the feature so
much that you regard the ctrl-q clicks as burdensome.
I don’t anticipate doing any maintenance on the
program in the next few months; but I will consider it
when I do. Personally, I regarded the feature as sort
of a ‘neat’ add-on, not to be used all that much.
Thus I introduced it in a manner which did not impact
the normal non-reflecting mode of operation. The
toggle you suggest would still achieve this. When I
have played with it myself, I used the reflecting
twists rather sparingly, so the prefix was no burden.

IMO, the interest of discovering how to generate any
rotation with two reflections does not last long. But
if what the user wants is a rotation, it does not make
a lot of sense to me to force the user to achieve it
as two reflections.

In working with a 4-puzzle simulator of my own, I
found that I wanted to specify twists incrementally.
(E.g., swap these two axes; then flip that one.) I
came to the realization that things would actually be
easier to think about if I temporarily allowed
reflected states in a slice as long as the user got
the slice back to unmirrored before twisting any other
slice.

>I purposely call all of these operations "moves"
>instead of twists because thinking about twisting
>drags in all the problems with rotations that we’ve
>been struggling with. I kept saying that it was
>better to think about planes of rotation rather than
>axes of rotation, but that seems unnatural for a lot
>of people. If we base the discussions on reflections,
>then this suddenly becomes quite natural.

I am not sure what the "this" is in the preceding
statement. I agree that we should not be thinking
about "axis of rotation" in dimensions higher than 3,
as I think it is an erroneous concept. I would prefer
to continue to use "axis" to refer to a 1-dimensional
subspace. In the context of rotations in dimensions
higher than 3, the thing analogous to an axis which
one should be talking about is the "fixed space" of
the rotation. The dimension of that fixed space is 2
less than the dimension in which we are operating.
The plane of rotation and the fixed space are uniquely
related to one another by orthogonality; so, from a
mathematical point of view, there is really no
difference in which you want to talk about. There are
definitely circumstances when the fixed space view
offers more insight. There are also circumstances
when it is useful to be able to switch back and forth
between the two in contemplating the significance of a
reorientation.

>What do you people think? Is this a good basis for
>defining N-dimensional twisty puzzles?

IMO, no. As I indicated above, if what a user
imagines he wants is a non-reflecting reorientation,
there is no need to force that user into using
reflections to achieve it. That just makes the puzzle
more tedious without making it more interesting. (If
I had macros and no non-reflecting twists, the first
thing I would do would be to create macros for the
non-reflecting twists.) However, _adding_ the
possibility of reflections (as opposed to restricting
to reflections) remains interesting.

>If so, the only things that remain to figure out are
>the best user interface for computer implementations
>based on this model, and how best to animate the
>moves, if at all.

I don’t think there is any difficulty with respect to
animation. My implementation in 3-space was actually
trivial to achieve, as it used machinery which already
existed. You can think of it this way: Say it is an
n-dimensional puzzle. Embed the puzzle in a
(n+1)-dimension space by adding a new coordinate axis.
Now a reflection is a 180 degree rotation in a plane
that includes the new axis. The intersection of that
plane with the orginal subspace of the puzzle is the
(n-1)-dimensional hyperplane in n-space through which
the reflection occurs. What I implemented for
animating the reflection in 3-space is actually what
you would see in 3D (after the 4D scene is projected
down to 3D) while the rotation in 4-space is
proceeding. I don’t think that there is any
difficulty extending the approach to higher
dimensions. (In MC3D, you can use the feature to
control the animation with the mouse to examine more
closely what happens at the critical flattening point
of the animation process.)

For nD, the user interface that I would want would
include the possibility to flip (negate) any axis and
the possibility to swap any two axes - combinations of
which can be composed to specify a more complex
reorientation and/or reflection. As it happens, these
are also sufficient to achieve all possible
reorientations; but others can be imagined.

>I’m not signing up to implement anything anytime soon
>but I do enjoy the thought exercise. I did not have
>any sense for what would make for a good user
>interaction model but I think that David may have
>pointed us in the right direction. I do have some
>ideas for animations that might work. Let’s start
>with a single reflection move. These can be
>reflections about a point, line, or any space of
>dimension lower than the puzzle itself.

Not exactly. Any reflection will occur with respect
to an (n-1)-dimensional reflection hyperplane. In
that (n-1)-dimensional plane there can be embedded a
hyperplane of lower dimension which one may wish to be
included in the reflection plane. But a hyperplane of
dimension less than n-1 does not uniquely determine a
reflection. It does determine a family of possible
reflection planes which include it.

>The simplest animation would seem to be a linear
>interpolation of the beginning and ending vertex
>positions. That would leave a moment of degeneracy in
>the middle when the part being moved gets flattened
>into that point or line, etc. but that’s
>fine.

It’s more than fine: It’s reality! (Mathematically
speaking, of course.)

>Imagine that happening in MC2D. A 3x1 slice would
>collapse into a 0x1 line at the midpoint of the
>motion. It is interesting to notice that that is
>exactly what you would see in the current projection
>if the motion was implemented as a 3D twist coming
>out of the plane and then back as some people have
>mentioned. Maybe an equivalent reflection move on
>MC3D would involve an affine 4D rotation in order to
>flip over a 2x2x1 slice, leaving it turned
>inside-out? It’s an interesting thought.

Indeed. It is what I did and what I explained in
general n-dimensional terms above. I do not
understand the comment about "inside-out". A
reflection does not turn things inside out. E.g.,
look at your image in a mirror. If you try to flip a
slice of the 3-puzzle in 3D, you do wind up
(uselessly) with it being outside in; but it is not
reflected. (I wrote "outside in" because the most
dominant apparent effect is that the 3x3 array of
stickers that had been on the outside are now
invisibly facing inwards.)

>And then what about those pairs of reflections that
>Roice says can produce rotations? How might we
>animate those? It seems like we would have the same
>two natural choices. We could perform a linear
>interpolation of the vertex positions, or maybe we
>could find pure rotation matrices that achieve the
>same results. Even if all rotations can be expressed
>as pairs of reflections, it might not follow that all
>pairs of reflections can be expressed as rotations,

But they can be. One thing that needs to be mentioned
is that the reflection planes cannot be chosen
arbitrarily. They must be such that the puzzle
transforms onto itself in the same space. Given that
restriction, it follows that the result of two
reflections must be a non-reflecting reorientation.
(What else could it be?)

>but if it is true then we will have found a way to
>redefine all of our puzzles, including the original
>Rubik’s cube. So now we have come full circle and it
>is time to ask what have we gained. First we might
>have gained a simpler way to way to define the
>puzzles we already know and with some new
>moves.

I don’t really see this. It seems to me that the
relevant observation is that all these puzzles can be
extended by adding the possibility of reflecting
‘twists’. (Indeed, the 2-puzzle does nothing at all
unless you admit reflections.)

Assuming that some sort of implementation has been
provided, it seems to me that it is up to the puzzler
whether he wants to deal with the potential
complications of introducing mirroring twists. Some
will find the extended puzzle to be interesting.

I have yet to decide whether the 3-puzzle with
reflections is easier or more difficult than without.
A number of the usual parity considerations go out the
window with reflections allowed. You can achieve
things like every cubie placed correctly except for a
single unoriented corner.

>Second, it might show us how to implement these
>puzzles in any number of dimensions.

I am not sure what is the issue here. In principle,
reorientations are not difficult to specify in any
dimension. (Any reorientation can be seen as a
permutation of the axes and negation of a subset of
them. There is no mirroring if and only if the
even/odd parity of the permutation is equal to that of
the number of axes flipped.)

>And finally, it might give us back all our familiar
>puzzles (Rubik’s cube, MC4D, Hyperminx, etc.) as
>special cases in which moves consist of pairs of
>reflections.

I.e., the groups of the non-reflecting puzzles remain
as subgroups of the puzzles extended to include
mirroring.

>Oh, and it gives us an MC2D that is *not* a special
>case! And I swear that was not my intention! :-)

Since reflecting twists can be added to extend a
puzzle of any dimension, it can be argued that MC2D
was never a special case in the first place. It is
just that the order-3 n-puzzle for n=2 is especially
dull if the mirroring extension is not invoked.

The 2-puzzle is interesting in that it would appear to
be possible to physically implement a device that
actually permits the reflecting twists by doing
rotations in 3-space. (In this case, I normally refer
to them as "flips" rather than "twists".) I said
"possible". However, I have not devined a mechanism
that would achieve it. (Each corner must be attached
to at least one of the edge pieces adjacent to it.
The trick is to make it release from one of those
edges when you start flipping the other edge. It
would take a little slop I think.)

On Friday, September 26, "Jenelle Levenstein" <jenelle.levenstein@gmail.com> wrote:
>If you implement moves as reflections then each move
>will turn some of the pieces on the cube inside
>out.

Not true. E.g., for the 3-puzzle, the corner cubies
can exist in two states - mirrored or not -
independent of their current locations. But they are
still right side out. The edge cubies are not chiral
so they cannot be in reflected states.

>Do you think that if you implemented the 3^3 cube
>with your new definition of moves it would be easier
>or more difficult to solve?

The implementation already exists. You can try it
yourself. At first, having the possibility of
mirrored corners will be perceived as a substantial
complication. However, there are some transformations
that are easier to achieve with reflections possible,
so I am not sure it would be perceived as more
difficult in the long run. (Though preservation of
some the previous parities disappears, a new parity on
the number of mirrored corners arises. That number
must always be even.)

When I have worked the puzzle after a scramble with
mirroring allowed, my first project was to get all the
corners to an unmirrored state. Then I proceeded
normally without doing reflections. There are
probably better ways.

>Although it may be possible to do all the rotations
>on a 3D cube using reflections it would take a long
>time for anyone to get used to

Not really difficult to learn. Just tedious to
execute if you have to do it every time what you want
is a simple turn.

>and the possibility of being able to put a piece in
>position inside out will make solving more
>complicated.

As I pointed out above, there is the complication of
mirrored corners - but not "inside out" anything.

>However it sound like a very interesting puzzle.

And you can experience it now!:
http://david-v.home.texas.net/MC3D/

Regards,
David V.