Message #1837

From: schuma <mananself@gmail.com>
Subject: Re: State graph of MC2D
Date: Wed, 03 Aug 2011 08:55:21 -0000

Hi David,

I haven’t read your CLS stuff yet. But about Melinda’s classification of the 24 states, here is my understanding:

Her definition of equivalency is not the conjugate class. It’s about global rotation and re-coloring.

Definition: Starting from state A, if there exists a global rotation of 90*n degrees affecting all the corners and the centers, and then exists a recoloring (a permutation of the four colors), resulting in state B, then we say state A and state B are equivalent.

Melinda’s "states" or I called "types" are the equivalence classes under this equivalency relation.

Melinda, please correct me if my understanding is incorrect or my statement is unclear.

Your discussion about CLS looks interesting and I will read it when I wake up. :)

Nan

— In 4D_Cubing@yahoogroups.com, David Vanderschel <DvdS@…> wrote:
>
> I think maybe a little too much is being made of this state
> graph business for the 2D puzzle. I am going to start by
> being somewhat critical of what has been said so far. Then
> I am going to switch gears and discuss a different, but
> closely related, way of partitioning cubie arrangements -
> one which I have found to have very general applicability in
> solving any type of cubie in any of the generalizations of
> the puzzle.
>
>
> What we are dealing with in MC2D is S4, the symmetric group
> on 4 elements. See
> http://en.wikiversity.org/wiki/Symmetric_group_S4
>
> This is a rather well understood subject. It is all there
> really is to the 2D puzzle, since there is no issue of
> orientation for the cubies. (The orientation of a 2D cubie
> is determined by its position.)
>
> In the case of MC2D, we are given 4 2-cycles (the twists)
> with which to generate the group. (3 would have sufficed.)
>
> As I (fail to) recall, Melinda never made it very clear
> about what were her criteria for the particular partitioning
> of the 24 permutations she chose for her "states". I never
> understood what technical meaning she was ascribing to
> "complete" or why she used the definite article on "the
> complete graph". There are many ways to partition the 24
> elements of S4. Nan’s graphs certainly would seem to me to
> be closer to what I would call "complete" in this context.
>
> There are ways to be precise about such things: E.g., one
> could say, "Two permutations are related if they are
> conjugates of one another." This is an equivalence relation
> which partitions the permutations into the 5 equivalence
> classes. Melinda’s state 5 is an equivalence class by this
> relation. It consists of the 12 permutations that are
> 3-cycles.
>
> However, by the conjugacy relation, Melinda’s states 1 (2
> permutations) and 2 (1 permutation) should be merged. All 3
> consist of 2 2-cycles. These, along with the identity, form
> a subgroup of S4 isomorphic to the Klein Four Group. See
> http://en.wikipedia.org/wiki/Klein_four_group
> Kamack and Keane called such permuters "crosses", and I will
> stick with that.
>
> The crosses, the 3-cycles, and the identity (i.e., states 1,
> 2, 5, and 0) exhaust the 12 even permuters of S4.
>
> What about the odd ones? Again, by conjugacy, Melinda’s
> states 3 and 6 should be merged, as these are the 1-cycles,
> of which there are 6. What remain are 6 4-cycles. These
> are in Melinda’s states 4 and 7, and any pair of 4-cycles is
> related by conjugation.
>
> Thus the conjugacy relation partitions S4 into 5 equivalence
> classes which can be seen to correspond to the identity,
> crosses, 3-cycles, 1-cycles, and 4-cycles of sizes 1, 3, 8,
> 6, and 6 respectively.
>
> Melinda’s graph accurately depicts the fact that you cannot
> get from any member of either of the last two states to one
> of the first 3 with one twist. Similarly for 0 -> 2. But I
> cannot turn this observation into a clue for the
> partitioning. For example, there exist permutation pairs
> from states 3 and 5 which require 3 twists to get from one
> to the other. Therefore an edge between two states does not
> mean that any pair from the 2 states is related by a single
> twist.
>
> The best guess that I can come up with for Melinda’s
> partitioning relation is the following: Two permutations
> are related if they are conjugates and, if one moves a cubie
> to the diagonally opposite corner, then both must do so.
> That sounds fairly inelegant to me, and I am not sure what
> the justification for it would be. (I imagine that Melinda
> must have had something else in mind which happens to work
> out this way.) Furthermore, it singles out two pairs of the
> positions as being "diagonally opposite", a property of the
> puzzle, not S4. (Diagonally opposite can also be defined in
> terms of the 4 2-cycles we are given to generate the group:
> Two positions are diagonally opposite if the transposition
> for that pair is not one of the generators.)
>
> The pejorative word "bottleneck" has been used to describe
> Melinda’s node 5, which consists of the 8 3-cycles. I don’t
> understand the implications of this. After all, we are
> talking about 2/3 of the even permutations in S4. One of
> them is bound to be close (in the twisting sense) to any odd
> permutation. I don’t see anything particularly bad or good
> about this fact.
>
> From the practical point of view, there is no practical
> point of view! By this I mean that the state graph does not
> really give me any useful insight into solving the puzzle.
> It was trivial to start with. I did not need any help.
>
> There is a sense in which a lot of the above is addressed by
> the concept of "cycle structure". See
> http://en.wikipedia.org/wiki/Symmetric_group#Conjugacy_classes
>
>
>
> So let me switch gears into an area where some help would be
> beneficial. As it turns out, I had already discovered some
> significance of cycle structure even before I ran across a
> reference to it here:
> http://www.scribd.com/doc/55445481/37/De%EF%AC%81nition-of-a-group#page=88
> Proposition 3.31 there is easy to prove; but it is not the
> sort of thing that would have occurred to me, even though
> cycle structure was already something I was thinking about.
>
> I refer to cycle structure in terms of "Cycle Length
> Signature" or "CLS" for the current permutation of a set of
> cubies which can all occupy the same set of positions. I
> indicate a CLS by writing "S" (for signature) followed by
> digits, in non-increasing order, representing the lengths of
> all the cycles for all the unplaced cubies of the set. (In
> the rare case that such a cycle is of length greater than 9,
> you have to delimit it with a comma.) It includes 1-cycles
> for cubies which are in their home positions with incorrect
> orientation. I refer to such a cubie as being "stuck at
> home", as it needs to be removed from its home position
> before it can be placed with correct orientation. The fact
> that a CLS corresponds to a conjugacy class for the
> permutation group, though interesting from the academic
> point of view, is not what interests me from the practical
> point of view.
>
> A useful number can be derived from the CLS. I call it the
> Cycle Length Signature Count or CLSC. The CLSC is derived
> from the CLS by adding the lengths of the cycles and then
> adding the number of cycles. The significance of CLSC is as
> follows:
>
> Most of my solving is by means of moves (or twist
> sequences) which accomplish 3-cycles. If 3 cubies are
> already permuted in a 3-cycle relative to their home
> positions, then doing a move which accomplishes the
> reverse 3-cycle can place two of them with correct
> orientation. If the third one comes out with correct
> orientation, that is just a matter of luck. You cannot
> normally count on it unless the 3 cubies are the last
> unplaced cubies in the set.
>
> So, unless you get the good luck, we can see that the
> best a 3-cycle can do is to reduce the CLSC by 2: If
> the 3 cubies we permute are in a cycle of length greater
> than 2, then the unplaced cubies of the original cycle
> will be in a cycle of length 2 less than we started
> with, and the number of cycles in the CLS will remain
> the same. (The preceding assumes that the 2 cubies
> which are placed are placed with correct orientation,
> and this is possible in general.) If the 3 cubies we
> permute come from 2 different cycles and one of them is
> a cycle of length 2 or more, then we can only place one
> of them. However, the cycles are merged. So we reduce
> the sum of the cycle lengths by 1 and the number of
> cycles by 1. If the 3 cubies we permute come from 3
> different cycles, then we can place none of them, but
> the number of cycles is reduced by 2.
>
> Thus each move will typically decrease CLSC by 2.
>
> I first used this insight when solving a regular 3D puzzle.
> I don’t have to start doing 3-cycle type moves until I get
> down to the last 5 or fewer unplaced corners. The CLSes
> possible in that situation are as follows:
>
> S5, S221, S311, S11111,
> S22, S31, S1111,
> S3, S111,
> S11
>
> Those are in decreasing order of the number of unplaced
> cubies and increasing order of the number of cubies stuck at
> home. (You can do it for a number of unplaced cubies larger
> than 5, but this is enough to make the relevant points.)
>
> The transitions which can be achieved (not counting good
> luck) by doing a 3-cycle are as follows:
>
>
> CLS CLSC
>
> S11111 -> S311 10 -> 8
> S221 -> S22 or S31 8 -> 6
> S311 -> S111 or S31 8 -> 6
> S1111 -> S31 8 -> 6
> S5 -> S3 6 -> 4
> S22 -> S3 6 -> 4
> S31 -> S11 or S3 6 -> 4
> S111 -> S3 6 -> 4
> S11 -> S3 4 -> 4
> S3 -> S 4 -> 0
>
>
> The last one beats the "decrease CLSC by 2" behaviour
> because, assuming it places 2 with correct orientation, the
> last 3-cycle must place all 3 correctly, no luck required.
> We see that S11 should be avoided, since it cannot be
> reduced by a 3-cycle at all. (Now, though it works, I don’t
> actually do two 3-cycles to fix S11. However, the move that
> I use to fix the orientation on 2 corners is 14 twists,
> which is very close to the 16 twists required to do two
> 3-cycles, so it really is almost the same.)
>
> The important lesson that one can learn from the above is
> the following: When faced with S31 (which is pretty obvious
> once you get there), do not place 2 of the cubies in the
> 3-cycle (as tempting as that may be), as you are guaranteed
> to wind up in S11 in this case. (No good luck is possible
> in this situation.) It is far better to place just one
> cubie and move the one that’s stuck at home.
>
> The above logic is not just for corner cubies in a 3D
> puzzle. It applies to any type of cubie in any
> generalization of the puzzle. However, in higher dimensions
> there are cubie positions which have enough symmetries that
> it is possible to change the orientation of just one cubie
> without otherwise affecting the arrangement of the pile.
> E.g., corners in 4D. Thus S1 is possible in those cases.
>
> The number of 3-cycle solving moves required to finish is
> typically (CLSC-2)/2, unless you make the S31->S11 mistake.
> Aside from avoiding the mistake, the 3-cycle solving moves
> you choose don’t affect the number of moves required to
> finish. This last fact was somewhat surprising to me, as I
> had developed a lot ‘theories’ in my mind about which sizes
> of cycles should be tackled first. As it turns out, it
> makes no difference. Except for S31, if you can place 2,
> that’s good. If you can place 1 and merge 2 cycles, that is
> also good.
>
> We can see that the worst case for 5 unplaced cubies is
> S11111. Oddly, this is a state that some solving methods
> actually seek to achieve - at least S1111. As far as I am
> concerned, one should avoid having any cubies be stuck at
> home to whatever extent is possible.
>
> (There are cases where I can handle S22 in a more direct
> manner than 2 3-cycles. However, the improvement is not all
> that impressive.)
>
>
> I must admit that, until quite recently, I did not realize
> how closely related were my CLS approach and Melinda’s state
> graph. That’s because I did not realize that a signature
> corresponded to a conjugacy class, and I did not realize how
> close to conjugacy classes were Melinda’s states. However,
> there remains a big difference in that my approach treats
> cubies which are stuck at home, a situation that cannot even
> arise in the 2D case. Furthermore, my approach generalizes
> to all generalizations of the puzzle and to all cubie types
> in an obvious manner that can be applied with useful effect.
>
> Regards,
> David V.
>