Message #2128

From: David Vanderschel <DvdS@Austin.RR.com>
Subject: Re: [MC4D] Calculating the number of permutation of 2by2by2by2by2 (2^5)
Date: Wed, 09 May 2012 23:11:14 -0500

Melinda wrote:
>On 5/7/2012 6:34 PM, David Vanderschel wrote:
>>Melinda wrote:
>>>It sounds like we are getting closer to closure.

>>>>Does this mean that you now understand why you must
>>>>maintain the pairs of opposing colors when reassigning
>>>>sticker colors? With all my effort at trying to explain
>>>>it for you, I was hoping for an "I see now!" I was also
>>>>hoping that you would realize that it is easier to talk
>>>>about conjugation by a symmetry than to get involved in
>>>>talking about remapping sticker colors, which are
>>>>actually somewhat tangential to the real problem.

>I’m not sure that I feel much closer to that "ah ha" moment
>but I do feel as if we are converging on a story that will
>feel right for all of us.

Unfortunately, I can tell from your later questions that you
have yet to get it.

>If conjugation is the operation that allows us to compose
>all the symmetries into one state space, then it does feel
>like a useful way to describe what we are doing.

I don’t think there is any "if" to it. However, I am not
sure that I can interpret your "compose all the symmetries
into one state space" meaningfully. In particular, we are
not composing symmetries. Without reducing to the
equivalence classes of states related by conjugation by a
symmetry, we have a perfectly meaningful state space; and I
don’t really understand why you are fighting it. Why do you
suppose Dan Hoey titled his article "The _real_ size of cube
space"? It is because the approach of regarding states as
distinct just by sticker color arrangement was already well
established even back in ‘94. He was "injecting the
complication" of grouping those states which were related by
conjugation by a symmetry, and he realized that that was not
the accepted approach. His observation became relevant to
those who were actually trying to analyze relationships
between _particular_ states for the conventional 3D puzzle
because the reduction actually brought the problem into a
range that was computationally feasible. When we are just
interested in counting distinct states, that is not our
issue. You get just as good a sense of how many states
there are without the much more complex additional reduction
by a factor somewhat less than n!*2^n.

I think the important thing about the distinction is that,
when we reduce to equivalence classes of the (first pass)
distinct states with the conjugation approach, we are
focusing more on the nature of the _process_ (aka permutation)
which gives rise to a state rather than to the state itself.
The result of that process depends on the initial
orientation of the pile.

>>> The main MC4D page claims to give the exact counts for
>>> the 3D and 4D puzzles. Is that not true? If not, then I
>>> need to change it.

>>>>It is true. Also the counts that David Smith came up
>>>>with for 5D are intended to be exact. (I am not ruling
>>>>out the possibility of an error.) As I said, the
>>>>problem that Eric and David were solving is much more
>>>>straightforward and admits a precise answer. The
>>>>problem only arises when you start trying to get the
>>>>number of equivalence classes of the distinct states
>>>>they counted that are related through conjugation by a
>>>>symmetry, which is the complication that it would seem
>>>>you were trying to inject. That would result in a
>>>>reduction of Eric’s and David’s numbers by a factor
>>>>close to (but less than) n!*2^n. But it is not
>>>>practical to do that in an exact sense.

>I am not trying to inject a complication, rather I am trying
>to account for what appears to be an error in our claim. I
>certainly don’t want to count two states as unique when they
>share all the same properties other than handedness. I
>understand that attempting to account for this one rare
>symmetry won’t change the state count by much and that maybe
>it is currently impractical to attempt to do that.

Melinda, it is not an error! The configurations are truly
different in the sense that no amount of reorientation will
cause a matchup of sticker colors all around. There is no
unavoidable reason to want to regard the assignment of
sticker colors as being mutable.

>This may be covered in previous messages, but would you
>please explain how you derive the n!*2^n and why it is not
>(n-1)! as I had thought?

Melinda, I am losing patience on this one. Brandon tried to
explain it in his recent post. Nan mentioned it in that old
one I cited. It comes down to the fact that many of the
remappings of sticker colors you are proposing are just not
physical - the puzzles can’t do that! In particular, the
two sticker colors that are on the same axis in initial
state must always be on the same axis no matter how you
otherwise remap the stickers. Thus what is really possible
for remapping colors comes down to a permutation of the axes
and possible swapping of the two colors on an axis. E.g.,
on a standard Rubik’s cube, yellow/white and blue/green are
so paired. Thus you could not swap yellow with blue unless
you also swapped white and green. You could also swap just
blue and green. The n in the formulae Roice and I were
tossing about is the dimension of the puzzle. So, with
that understanding, I thought you were saying (2n-1)!, where
2n is the number of sticker colors. (Not sure why you took
out one factor of 2n. I guess you were thinking of one
color as being a reference with respect to which the others
were being permuted.)

I will make one more brief attempt at the end; but you
should really try to reread earlier postings in this thread
more carefully. It has been explained.

>>You have already worked out a simple example giving
>>representative members of the equivalence classes for the
>>case of the 2D puzzle with mirroring twists allowed. I
>>would hope you would remember the previous occasion on which
>>some folks on the list tried to explain the relationship of
>>your equivalence classes to conjugation by a symmetry:
>>http://games.groups.yahoo.com/group/4D_Cubing/message/1843
>>Perhaps that previous discussion will make better sense to
>>you now.

>A little bit. Nan’s link to
>http://kociemba.org/math/symmetries.htm on that message is
>definitely what I am talking about. I think that the fact
>that MC2D appears to require reflections to operate at all
>probably confused the issue more than clarifying, because
>the real issue applies to all of our puzzles, not just to
>that one.

I don’t think that allowing mirroring twists makes any
difference at all with respect to the problems of
enumerating the distinct states or the equivalence classes
of these distinct states under conjugation by a symmetry.

>I definitely do not get the bit about how using axes and
>color pairs is better than thinking about color
>equivalencies but it is good enough if the result is the
>same.

It is important, because, if you fail to maintain the opposing
color pairs, then you do _not_ get the same result.

More generally, I regard the whole issue of remapping
colors as a red herring. If you understand conjugation
by a symmetry, then the recoloring is just an obvious side
effect which is not worth getting worked up about. It is
true; but it is not what is important. The actual colors
themselves were always unimportant. What you should
actually regard as identifying a sticker ‘color’ is the
direction it faces in initial state - not some particular
hue that is being used to render it for visualization
purposes.

>I am still a little troubled by the "exact" values that you
>guys seem to prefer. MC2D is indeed a great example of the
>problem and I just can’t see how we can really say that
>there are 24 states in that puzzle that I think David S
>claimed in Wikipedia. Looking at my state graph on the MC2D
>page there are clearly only 8 that make any real sense to
>me.

It is really quite simple. The state of this particular
puzzle is characterized solely by the permutation of the 4
corner cubies, and any permutation of the 4 cubies is
possible. Thus there are 4! different arrangements. This
is a perfectly legitimate way to count distinct states. You
have observed that lots of them are not essentially
different. E.g., you would regard as being essentially the
same any two states for which just two adjacent corners have
been transposed without regard to which pair that is. That
is an additional complication by which you are grouping the
states into equivalence classes; and, yes, the relation is
conjugation by a symmetry.

The relevant conjugator for the example is rotation by a
multiple of 90 degrees in the plane of the puzzle. So start
with "swap the top 2". Then, if I rotate a quarter turn
clockwise, swap the top 2, and rotate back, I will have
achieved "swap the left 2". Those two _different_
permutations of the cubies are related by conjugation by a
90 degree rotation. It really is a different pair of cubies
that get swapped in the two cases. It is perfectly
legitimate to regard the two states as being different
without worrying about their relationship by conjugation.
Melinda, whether you wish to recognize it or not, you really
are trying to unnecessarily complicate the problem of
counting distinct puzzle states. And, as may be seen from
the "real size" article, the complication is by no means
trivial.

Let me go back once more to a more complex puzzle and some
non-trivial twist sequence. Do that sequence starting with
the pile in initial state and you get one particular
arrangement. Now get another identical puzzle in initial
state, but, without twisting any slices, first reorient the
whole pile so that it is no longer in initial state. Now
perform the same twist sequence again. You get a new
arrangement which is not the same as the arrangement on the
first puzzle. You cannot (in general) make them match up
sticker-for-sticker just by reorienting one. However, your
sticker color remapping approach will make them match up
with appropriate relative orientations. But there is no
mystery about the required sticker remapping!: It is
precisely that which was induced by the initial
reorientation of the second puzzle before performing the
twist sequence. So there is no need to talk about it.
Furthermore, it is clear that a reorientation of the pile
cannot change which pairs of sticker colors occur facing in
opposite directions on the same axis. Other than that
restriction, lots of sticker color mappings are possible via
the orientation step preceding the twist sequence. Indeed,
that number is n!*2^n.

Mirroring transforms for the conjugator are perfectly
legitimate even if they are not allowed for the puzzle,
because the conjugate will not induce any mirroring if none
of the twists do. (Indeed, you can actually practice
conjugation by a reflection on a 3D cube by watching what
you are doing in a mirror. Left/right and up/down do not
change, but front/back switches as well as the directional
sense of all twists (always looking towards the twisted
slice from its side of the cube).)

Regards,
David V.