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