Message #1848

From: David Vanderschel <DvdS@Austin.RR.com>
Subject: Re: [MC4D] State graph of MC2D
Date: Fri, 05 Aug 2011 17:14:26 -0500

Melinda wrote:
> On 8/4/2011 3:02 PM, David Vanderschel wrote:
>> Melinda wrote:
>>> You looked at my diagram and thought that what I was
>>> attempting had something to do with cycles and conjugates
>>> but was just doing it wrong.

>> Melinda, you are making assumptions about what I was
>> thinking that are not only false, but are contrary to what I
>> actually wrote. I hope that, after reading this, you will
>> apologize for the above inappropriate accusation. I hope
>> you will read this post carefully, because it appears that
>> you have failed to do so with my previous posts.

> I most deeply apologize. I should definitely said "I’m
> guessing that you looked at my diagram…" That seems like
> a small qualification, but it is not at all. You are right
> to call me on it and I appreciate the risk you took in
> doing that. My pennance will be to try to read this
> message all the more carefully as you suggest.

I am relieved. I did not want to turn this into a fight,
but I did not want to ignore it either. I accept the apology.

>> It was Andrew Gould who straightened this out, providing
>> a way to specify the equivalence relation that gives rise
>> to your partition. It is mathematically sound and
>> elegantly simple. And, as it turns out, conjugating is
>> the way it’s done.

> I don’t know if it is correct to say it is THE way it’s
> done. It certainly is A way, and possibly even the BEST
> way. This point was one of the things that I was trying to
> get across. I’m sure that from your point of view it is
> definitely the right way. I’m just pointing out that there
> are other ways of looking at it. That was why I harped on
> the question of purpose or utility.

Actually, I believe that conjugation is quite validly
another way of describing my present interpretation of how
Nan was trying to describe your partitioning ‘algorithm’. I
can rephrase what he was saying as "Two permutations are
related if there is a way to pick up the whole puzzle and
put it back down turned and/or flipped in such a way that
the permutations can be seen to be the same." That does not
require worrying about colors. All you need to see is that,
relative to positions in fixed space (independent of the
orientation of the puzzle), the actual permutation movements
of the cubies are the same. (If they do match up, then
there would be an appropriate recoloring. It is just that
you don’t actually have to think about that aspect of it.)
But note that, again relative to fixed space positions,
picking up the puzzle and putting it back down does achieve
a particular permutation of the cubies. That permutation is
one which arises from a symmetry. If it does make the
permutations match up, then they are conjugates of each
other by that symmetry.

To look at it the other way around: Consider a particular
twist sequence relative to fixed space positions. Do it
with the initialized puzzle in standard orientation, and you
get permutation #1. Now initialize the puzzle, reorient it,
do the same sequence, and put the puzzle back in standard
orientation to get permutation #2. As a permuter, the
put-back is the inverse of the reorient. So permutation
#2 is a conjugate of #1 by the permutation (in fixed space)
that the reorientation induces.

My point is that conjugation is _not_ an orthogonal issue when
we are talking about making things match up by reorienting
the whole puzzle in space. In fact, I immediately moved
from Nan’s description, in rotation terms only, to talking
about conjugating with a rotation, as I perceive the
concepts as being equivalent - as they are in fact.

>> Now there is one rather odd thing you stated in your last
>> post that is indeed profoundly wrong:
>>
>> "With my diagram it is trivial to see that God’s number
>> must be 3 …"
>>
>> What I see is that it takes 4 twists to get from node 2 to
>> node 0.
>
> Do’h!
> It’s true and clear when you allow middle slices, but clearly I
> disproved myself about as completely as possible. Thanks
> for the correction.

I would argue that it still takes 4 twists even if you allow
center slice twists. If you take the 2->4->3->0 path, the
puzzle winds up upside down or mirror imaged, something that
should not be able to happen in 2-space. If you take the
2->1->0 path, the puzzle winds up rotated by 180 degrees.
You can’t fix either situation in 2 twists.

I never paid much attention to the center slice twists
precisely because they reorient the whole puzzle by a
reflection. If you fix that by picking up the puzzle and
putting it back down in standard orientation, then you see
that what you have accomplished is actually 2 2-cycle type
twists. So if you count a center slice twist as 2 twists
and don’t worry about disoriented puzzles, it still takes 4
twists to get from 2 to 0. I think it is entirely appropriate
that the implementation of MC2D does not permit
center slice twists.

>> One thing that is frustrating me about this diversion is
>> that I thought I had made a real contribution with the Cycle
>> Length Signature approach to a succinct but useful way to
>> classify the permutation state for any sort of cubie in any
>> generalization these puzzles. That approach is closely
>> related, as the CLS characterizes the conjugacy class of an
>> arrangement. The difference is that these conjugates are
>> not limited to conjugation by a symmetry. As it turns out,
>> that makes it much easier to identify the CLS class of an
>> arrangement; and it leads to a state graph with far fewer
>> nodes, which could be viewed as an advantage. Furthermore,
>> the insights from the CLS do have real practical
>> significance which can be readily applied when solving. I
>> thought folks would be excited about this.

> Yes, well I suggest that you not take a lack of discussion
> on your main point for a lack of interest. I know that
> there are a lot of very interested people reading this
> list who have no intention of ever posting. Maybe you can
> generate interest eventually, but you may need to continue
> to find ways of clarifying your thoughts even
> further. That along with some pretty diagrams may just do
> the trick! :-)

OK. Diagram (though not so pretty):

S11111
|
S1111 |
| |
S221 | S311
/ \ | / <br> S22 S31~ S111
\ | ~ /
\ | ~/
\ | S5 /~
\ |/ / ~
[ S3 ]—-S11
|
S

The nodes correspond to conjugacy classes as identified by
my CLSes. These are the transitions that can be achieved by
using solving moves that result in 3-cycles. It applies
when only 5 or fewer cubies (of any set that can occupy the
same positions) remain unplaced. It assumes that, when 1
cubie is moved to its home location, it arrives with correct
orientation; and, when 2 cubies are moved to their home
positions, at least 2 cubies wind up with correct
orientation. Any edge with a downward component corresponds
to a reduction of CLSC by 2 (excepting the bottom finishing
transition, for which the reduction is 4). I indicated the
S31->S11 transition in the strange manner with "~"s, as it
should be avoided. (That also addressed the problem that I
did not find a way to draw the graph without an
edge-crossing.)

The conjugacy classes are defined purely in terms of the
permutations of the cubies. They are independent of the
orientations, except that wrongly oriented cubies in their
home positions (i.e., stuck cubies) are counted as 1-cycles.

Though this graph could easily be extended to allow for more
than 5 unplaced cubies, I am not sure that has any practical
significance. The more cubies there are that are unplaced,
the harder it is to ‘see’ the CLS. However, the practical
significance really only comes into play in the end game.
The theory behind it assures that you are not wasting moves
prior to getting down to 5 unplaced as long as you are
always placing 2 cubies, placing 1 cubie and merging 2
cycles, or merging 3 cycles. (What I personally tend to do
in practice is that I try to deal with cubies stuck at home
first. If I merge such a stuck cubie into another cycle (of
length 2 or more), I can place one cubie. The setup is
easier if you only have to get the orientation right on 1
cubie; so the stuck cubies, as obnoxious as they may be, can
at least be exploited in this sense. In particular, from S221,
I always go to S22; and, from S311, to S31.)

One interesting point, which I failed to make earlier, is
that, when you are down to 4 unplaced cubies, you should not
even _look_ for a way to place 2. If the CLS is S22 or
S1111, it cannot be done. If the CLS is S31, it _should_
not be done. What is important is to see if any of the four
is stuck at home, in which case it must be moved.

Another interesting point is that, with 5 unplaced cubies,
you can finish in only 2 steps whenever there are no stuck
cubies. In a random permutation of n things, the expected
number of unmoved things is 1 and the probability that all
are moved is 1/n; so it is fairly common to wind up with a
5-cycle when 5 cubies are unplaced. In my experience with
the puzzles, it seems to be more common than one time out of
five. (If that’s true, I think there may be an explanation
of it in terms of the fact that an unmoved cubie may well be
oriented correctly, but I have not figured out how to make the
argument precise.) Except for S1111 (rare), when 4 cubies
are unplaced, you can always finish in 2 steps.

To make sure that the plain text graph looks right, I am
going to force Lucida Console again. I hope it does not
turn out as ugly as last time.

Regards,
David V.