Message #2122

From: Melinda Green <melinda@superliminal.com>
Subject: Re: [MC4D] Calculating the number of permutation of 2by2by2by2by2 (2^5)
Date: Mon, 07 May 2012 19:31:08 -0700

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

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

>> Please help me to understand the part that is "not
>> quite". Here is what I am hearing: The main thing that makes
>> it tricky to be exact seems to involve mirror symmetry. In
>> particular, we would need to account for some relatively
>> rare cases of states that happen to have mirror symmetry,
>> and that counting those special cases appears to be very
>> difficult.
> That is my understanding; but I must confess that I have not
> myself fully absorbed all the gory details of the "real
> size" article. There may be other relevant symmetries
> besides mirroring.

Fair enough. I’m just glad to know that we are talking about the same thing.

>> If it can’t be done then it can’t be done. If that is the
>> case, then what is our best estimate of the truly unique
>> positions when accounting for color and mirror symmetries,
>> and in particular, what is the term that we need to divide
>> by and how is it derived?
> I say don’t try. Stay with the distinct arrangement counts
> we have. They are meaningful. Since you have an interest
> in the equivalence classes of these arrangements under
> conjugation by a symmetry, you might want to add the comment
> that the number of such equivalence classes will be less by
> a factor close to n!*2^n. Regarding the nature of the
> issue, you could just link to the "real size" article,
> saying that the analogous problem exists for any dimension.

That is a great suggestion, David. Thanks.
No problem is too large or complex that it can’t be foisted off onto
someone else! :-)

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?

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

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
<http://en.wikipedia.org/wiki/N-dimensional_sequential_move_puzzle#3x3_2D_square>.
Looking at my state graph on the MC2D page
<http://superliminal.com/cube/mc2d.html> there are clearly only 8 that
make any real sense to me.

-Melinda