Home »

Symmetry Reduction of Coset Spaces

Submitted by B MacKenzie on Fri, 02/22/2013 - 22:44.

Having repeatedly shot myself in the foot by mishandling the symmetry reduction of coset spaces, I finally sat down, laid out the math and put together a set of notes on the matter. These notes follow.

Coset Spaces

Solving Rubik's cube either manually or by computer usually involves dealing with coset spaces. A group may be partitioned into cosets of a subgroup of the group:

     g * SUB          where g is an element of the parent group and 
	              SUB is a subgroup of the parent group

Corners first solvers take a scrambled cube to the subgroup of the cube group with solved corner cubies. This subgroup is comprised of all the even parity edge arrangements composed with the identity corner arrangement. A coset of this subgroup is characterized by a particular arrangement of the corner cubies. All members of the coset have the same corner cubie arrangement. Obviously, a turn sequence which will take one coset member to a member of the parent subgroup will take any coset member to a member of the subgroup. One could use this coset space as the basis for an IDA solver pruning table. The table would list the depth of each coset of the solved corners group—that is, the minimum number of turns needed to take a member of the coset to a member of the subgroup.

The effectiveness of such a pruning table increases with the depth of the coset space. The deeper the average depth of the cosets the more effective is the pruning of the search tree. This equates to larger coset spaces based on smaller subgroups. In order fit larger pruning tables into physical memory one eventually must resort to symmetry reduction of the coset space.

For the purposes of this discussion two parent subgroups are considered. The first is the subgroup of the Rubik's cube group with solved edge cubies. This coset space consists of 12! * 211 = 980,995,276,800 cosets, one for each arrangement of the edge cubies. The second is the subgroup of the Rubik's cube group with the Up layer solved. This coset space consists of (24 * 21 * 18 * 15) * (24 * 22 * 20 * 18) = 25,866,086,400 cosets, one for each arrangement of the Up face cubies. Either of these coset spaces is too large to map into the physical memory of a personal computer and is a candidate for symmetry reduction.

Symmetry reduction

The elements of a symmetry equivalence class, m' g m (where m ranges over the cubic symmetry group and g is an element of the Rubik's cube group), are all at the same depth in the Cayley graph. Find the depth of one and one has found the depth of them all. The conjugates of the elements of a coset are given by:

	m' * g * SUB * m

A coset space may be reduced by symmetry only for those symmetry elements for which m' * SUB * m = SUB

	m' * g * SUB * m =

	m' * g * (m * SUB * m') * m =

	m' * g * m * SUB

The symmetry conjugates of the coset, g * SUB, are contained in the coset, m' * g * m * SUB only if SUB is invariant under conjugation by m.

The fixed edge cubie subgroup described above shows full cubic symmetry and the coset space may be reduced about 48 fold. The fixed Up cubie subgroup on the other hand only shows C4v symmetry. All other symmetries swap Up layer cubies with lower layer cubies and are not useable. Thus this coset space may only be reduced about eight fold.

Anti-symmetry reduction

Find the depth of a group element and you have also found the depth its inverse. The inverse of a left coset, g * SUB, is the right coset, SUB * g'. The second coset is composed of the inverses of the elements of the first coset. A coset space may be reduced with anti-symmetry only if the subgroup is a normal subgroup, i.e. 

	g * SUB = SUB * g

The subgroup of the cube group with all edge cubies solved is a normal subgroup. One may reduce this coset space using anti-symmetry. On the other hand, the subgroup of the cube group with the Up layer solved is not an normal subgroup and anti-symmetry reduction is not valid for this coset space.

To elaborate:

The subgroup of the cube group with solved edge cubies consists of all even parity corner positions composed with the identity edge position. Since a conjugate of an even parity corner position is always an even parity corner position: 

	g' SUB g = SUB

and thus:

	g * SUB =

	g * g' * SUB * g =

	SUB * g

For a cube group element g, the left coset is: 

	g * SUB = <  g * s0 , g * s1 , g * s2 … >

For the inverse of g: 

	g' * SUB = 

	SUB * g' = < s0' * g' , s1' * g' , s2' * g' … >      (SUB, being a group, includes the inverses)

Each element of a coset may thus be mapped to its inverse in the antisymmetric coset. So if one solves the coset containing g one knows the results one would obtain for the coset with edge position g'.

On the other hand, the fixed Up cubie subgroup is not a normal subgroup. Since g in general swaps Up layer cubies with lower layer cubies, a conjugate of a lower layer permutation is not always a lower layer permutation. 

	g' SUB g ≠ SUB

In general the inverses of g * SUB are not contained in the coset g' * SUB and this coset space may not be reduced by antisymmetry.

In Summary

Mapping each coset to a byte in memory, the cosets of the fixed edge cubie subgroup may be reduced by the full 96 M+ symmetries to about 10GB, while the cosets of the fixed Up layer subgroup may be reduced by the eight C4v symmetries to about 3.2 GB.

» login or register to post comments | previous forum topic | next forum topic

Comment viewing options

Select your preferred way to display the comments and click 'Save settings' to activate your changes.

My Interest in This Thread

Submitted by Jerry Bryan on Sat, 03/09/2013 - 10:09.
As you all can probably tell, I'm extremely interested in this thread. The reason is that I've struggled with the same issues for years and only in the last year or two have I come up with what I consider adequate solutions. I've been meaning to write up some of my results, and Bruce has beaten me to it. But that's probably a good thing because he writes about ten times more eloquently than I do and about ten times more succinctly than I do. But let me go ahead and put some of my ideas out there anyway.

I tend to think very literally in terms of the real cube, so the way I have been thinking about Bruce's cosets is in terms of graying out some of the cubies. That is, take some of the color tabs and color them gray instead of red or green or blue or whatever. Even though it is the color tabs that are being grayed out, the color tabs have to be grayed out by cubie. Either all of the color tabs associated with a particular cubie are grayed out or none of the color tabs associated with a particular cubie are grayed out.

As I think about this model, I only gray out corner cubies and edge cubies, never face center cubies. I leave them there as a frame of reference. In all truth, a computational or mathematical model of the cube does not need to include the face center cubies at all. Simply leaving the face center cubies out of a model does not turn the model into a model of a void cube, where a void cube is what we call a real, physical cube which contains no face center cubies. Modelling a void cube properly is much trickier than just leaving the face centers out of the model.

For Bruce's example of the fixed Up group I would gray out the Down layer except for its face center, and I would gray out the middle layer that's between the Up layer and the Down layer except for the face centers that are in that middle layer. The resulting cube when scrambled corresponds to positions in a search space, and each such position may be identified with one of the cosets of the fixed Up group. The cosets are not a group, and hence my model with grayed out cubies is not a group. I can produce a graph for the search space, but the graph is strictly speaking not a Cayley graph since the search space is not a group.

You might think of a cube with grayed out cubies being modeled something like the following. Number the 54 color tabs from 1 to 54. Then for those color tabs you wish to consider grayed out, number them all as 99. As moves are performed on this model, the 99's get moved around just like all the other numbers but when comparisons are made between different positions any 99 is equal to any other 99. Needless to say, my actual computer model is nowhere near this crude and I'm sure that nobody else's is either, but it's still a useful way to think about the problem.

My experience has been that as long as symmetry and anti-symmetry are not taken into account, a model with grayed out cubies is trivial to understand and easy to implement. But in my experience it is also the case that as soon as I try to incorporate symmetry and anti-symmetry into a model where some of the cubies are grayed out I run into all kinds of complications that I don't run into when there aren't any cubies grayed out. I'm going to put a discussion of those complications and my solutions into subsequent messages so that no one particular message gets too long. For now I will just say that my results track very closely with what Bruce has already written up so well.

Jerry
» login or register to post comments

The group S4 is the group of

Submitted by Jerry Bryan on Sat, 03/09/2013 - 11:39.
The group S4 is the group of all permutations on the set {1,2,3,4}. It will be conventient for the moment to consider S4 to be the set of permutations on the "alphabet" {A,B,C,D} and to consider the permutations to be "words" from this "alphabet". For example, the permutation ABCD may be considered to be the identity of this group and the permutation DACB may be considered to be the permutation that maps A to D, B to A, C to C, and D to B.

Within this framework, we can write a partial permutation by replacing one or more or the letters with a question mark. For example, the partial permutation AB?? may be considered to the the permutation that maps A to A and B to B while leaving the mappings for C and D unspecified. In addition, AB?? may be considered to be a coset. In particular, AB?? may be considered to be the coset {ABCD, ABDC}. This coset happens to be a group, so we may consider AB?? to be the subgroup of S4 that fixes A and B. Similarly, the partial permutation ??BA may be identified with the coset {CDBA, DCBA}. The analogy with Rubik's cube is that a Rubik's cube position with grayed out cubies can in the exact same way be identified with a coset.

If we start with the permutation ABCD and swap the A and C, we end up with CBAD. If we start with the permutation ABCD and swap the first letter with the third letter, we end up with CBAD. There is no difference in the two ways of swapping because we started with ABCD which is the identity permutation.

If we start with the permutation DABC and swap the A and C, we end up with DCBA. If we start with the permutation DABC and swap the first letter with the third letter, we end up with BADC. There is a difference between the two ways of swapping because we did not start with the identity permutation.

In his earliest writings, Singmaster pointed out that permutations on the Rubik's cube could be considered to be taking place on the cubies or on what he called cubicles - the slots where the cubies reside. In Singmaster standard notation, the quarter turn U on the edges may be written in cycle notation as Ue=(uf,ul,ub,ur). Singmaster said that uf, ul, etc. could be taken to be the uf cubie, the ul cubie, etc. or that they could be taken to be the uf cubicle, the ul cubicle, etc. He said that it didn't really matter which way you did it as long as you picked one way and stuck with it.

However, I do think that when we think of Rubik's cube and of what happens when we apply the U operation to a scrambled cube, we are nearly always thinking of a cubicle based model. Harkening back to my example of swapping the A with the C vs. swapping the first letter with the third letter, swapping the A with the C corresponds to a cubie based meaning for Singmaster's notation and swapping the first letter with the third letter corresponds to a cubicle based meaning for Singmaster's notation.

When Dan Hoey and Jim Saxbe first published their concept of how Rubik's cube symmetry needed to be calculated, they realized that they needed to apply symmetry to the cube twice - once in a cubie based fashion and once in a cubicle based fashion. They called their cubie based application of symmetry a recoloring. Their huge insight was in recognizing that as long as a symmetry is applied to the Start position that the symmetry can be applied in a cubicle based fashion and that the result would be the same as for the applying the symmetry in the cubie based fashion that they needed. So they were able to apply a symmetry to a scrambled cube in a cubicle based fashion (the xm part of an m-1xm calculation) and also they were able to apply a symmetry to the Start position in a cubicle based fashion to gain the effect of applying the symmetry in a cubie based fashion (the m-1 part of an m-1xm calculation).

My problem in dealing with all this when I had cubies grayed out has been that the the m-1 of the calculation didn't work with partial permutations and hence didn't work with cosets. The problem is not the inverse part of m-1. After all, m-1 is just another element of M. The problem is that some of the cubies grayed out m-1 is no longer being applied to the complete Start position and hence a cubicle based calculation is no longer the same as a cubie based calcuation. What happens is a cubicle based calculation for m-1 and what we need is a cubie based calculation.

I will continue this thought in my next message.

Jerry
» login or register to post comments

Conjugates of Partial Representations

Submitted by B MacKenzie on Sun, 03/10/2013 - 21:56.

In regards to forming conjugates of partial cube representations perhaps I can provide some insights. Here is my standard routine for forming the symmetry conjugate of a cube state:

-(void)getConjugateRep: (CM_SYMTAG *)conjugate
            ofStateRep: (const CM_SYMTAG *)state
              bySymTag: (CM_SYMTAG)symTag
{
    RM_Cubie    cubie, cubicle;
    CM_SYMTAG   inv, pdt;
	
    inv = [cubicGroup inverseOfTag: symTag];
	
    for( cubie = 0 ; cubie < 20 ; cubie++ )
    {
        cubicle = [self positionOfCubie: cubie inState: symTag ];
        pdt = [cubicGroup productOfOperatorTag: state[ cubicle ] stateTag: symTag];
		
        conjugate[cubie] = [cubicGroup productOfOperatorTag: inv stateTag: pdt ];
    }
}

I use a cubie based representation which lists a geometric transform for each cubie which encodes both the position and orientation of the cubie. I would like to draw your attention to the line highlighted in red. The state of cubie N in the conjugate depends on the state of cubie M (the cubie whose home position is cubicle M). Cubicle M is the cubicle cubie N is in in the conjugator symmetry. For a partial representation cubie M might not be part of the partial representation. The thrust of this is that although you are only interested in a subset of the cubies you can't let the remaining cubies go hang. In order for this routine to work for a coset space one must pass a valid member of the coset. It doesn't matter which member you pass. You can fill out the remainder of the representation in an arbitrary manner. If you do then you are assured by the math laid out in the parent of this thread that state returned by this method will be a member of the conjugate coset.

After sleeping on it I see that the above is wrong. The restrictions on the symmetry outlined in the parent of this thread are necessary precisely to assure that cubie M is part of the partial representation. So the above routine will work with a partial representation regardless of the values for the other cubie states.

» login or register to post comments

Thank you for your insightful

Submitted by Jerry Bryan on Mon, 03/11/2013 - 11:32.
Thank you for your insightful comment. I think the most salient part of your message is the following.

> In order for this routine to work for a coset space one must pass a
> valid member of the coset. It doesn't matter which member you pass.
> You can fill out the remainder of the representation in an arbitrary manner.

My problem with all of this is that I seem stubbornly to refuse to "fill out the remainder of the representation in an arbitrary manner". Instead, I cling to the very literal notion of grayed out cubies, where the grayed out cubies are the very part of the representation that needs to be filled out in an arbitrary manner. And by doing it this way, I shoot myself in the foot computationally. :)

Jerry
» login or register to post comments

I was wrong

Submitted by B MacKenzie on Mon, 03/11/2013 - 12:10.

See my addenda to last night's post. You should be able to form a coset conjugate by only looking at the cubies of interest. As long as one only uses allowed symmetries one could modify the above routine to only iterate through the cubies of interest rather than all twenty and it should still work. (the above routine as written can break if the out-set cubies have states outside of the range 0-23. So all that is needed is to zero out the out-set cubie values)

» login or register to post comments

Symmetry By Recoloring

Submitted by Jerry Bryan on Sun, 03/10/2013 - 13:08.

When we call a particular symmetry of the cube m, we most typically consider m to be a permutation by cubicle. If the same symmetry m is to be applied by cubie, we could call the symmetry m_by_recoloring. And to be very explicit about which m is which, there are 48 of them and we can number them, for example, as m1 through m48. Similarly, we can number the m_by_recoloring permutations as m_by_recoloring1 through m_by_recoloring48.

mk and m_by_recoloringk are not really different permutations in the sense that I have to have different permutation tables for them in my programs. They are the "same" permutations just applied in a slightly different way in computer code. Indeed, ( (mk)-1)(x)(mk) and ( (m_by_recoloringk)-1)(x)(mk) perform identically when x is a position that includes all the cubies. The difference only manifests itself when x is a position with some of the cubies grayed out. Hence, Hoey/Saxbe symmetry can be taken to be a special case of this "new" kind of symmetry.

The net result is that for cube positions with some of the cubies grayed out, I now calculate symmetry as (m_by_recoloring)-1(x)(m), where m and m_by_recoloring are always taken to be the same m.

It turns out that any permutation applied by cubie commutes with any permutation applied by cubicle. m_by_recoloring is simply m applied by cubie instead of being applied by cubicle. Hence, the following is the case: ( (m_by_recoloring)-1 (x) ) (m) = ( (x) (m_by_recoloring)-1) ) (m) = ( (x)(m) ) (m_by_recoloring)-1. Note the parentheses very carefully. They are (hopefully) arranged so that m and m_by_coloring-1 are never combined together directly. Rather, m_by_coloring-1 is always combined with a permutation by cubicle.

Finally, m_by_recoloring should really be called m_by_relabeling. I only called it recoloring because that's what Hoey and Saxbe called it. Consider a cube in the Start position with no cubies grayed out which is colored according to Cube Explorer standards - Up and Down are yellow and white, respectively; Front and Back are Red and Orange, respectively; and Left and Right are Blue and Green, respectively. Consider the reflection that swaps the Up and Down faces while leaving the other faces alone. The same reflection_by_recoloring swaps the yellow and white faces while leaving the other faces alone. But consider the Front/red face and number the red color tabs as follows. 

1 2 3
4 5 6
7 8 9
After swapping the Up/yellow face with the Down/white face, the red Front/red face will be numbered as follows 
7 8 9
4 5 6
1 2 3
All the Front color tabs will still be red, but they will be renumbered. The red color tab that originally was in the upper left hand corner of the red face will now be in the lower left hand corner of the red face, etc. And I prefer the term relabeling to renumbering because the symbols on the color tabs could be any symbols at all, not just numbers.

Jerry

» login or register to post comments

Anti-symmetry by Recoloring

Submitted by Jerry Bryan on Mon, 03/11/2013 - 12:37.
The final piece of the puzzle on using a cube with grayed out cubies to model cosets is anti-symmetry.

The way I handle symmetry reduction for a position x is to calculate m-1xm for each m in M. This will create a set xM of up to 48 conjugate positions. I place xM into lexicographic order, and take the first element in the lexicographic ordering as a symmetry representative for x. Let y be the symmetry representative of x.

The way I handle anti-symmetry reduction for a position x is to calculate the symmetry representative for x-1. Let z be the symmetry representative of x-1. If z=y, then x cannot be reduced by anti-symmetry. Otherwise I choose whichever of y and z comes first in lexicographical order as the combined symmetry/anti-symmetry representative for x.

Therefore, the problem of calculating anti-symmetry for a partial permutation reduces to the problem of calculating an inverse. For example, consider the subgroup H of the cube group G where H is the set of all positions where the uf cubie is fixed. H is a subgroup of index 24 in H, and hence there are 24 cosets. Each coset is characterized by the location of the uf cubie, where location includes both the cubicle in which the uf cubie is located and the flipped or non-flipped status of the uf cubie. My model for this coset space is to gray out all the corner cubies and to gray out all the edge cubies except the uf cubie.

To be precise about our cubie/cubicle notation, we will say that the uf cubie is in the uf cubicle if it is not flipped, and that the fu cubie (another name for the uf cubie) is in the uf cubicle if it is flipped. We will flip the cubie names, but not the cubicle names. For each cubicle name, we will have to pick one of the two possibilities and stick with it. For example, we will speak of the rf cubicle rather than of the fr cubicle.

We can consider the position where the uf cubie is in the uf cubicle to be the Start position for this coset space, and let's work in the quarter turn metric. After applying the move F to the Start position, the uf cubie will be in the rf cubicle. If we apply the move F-1 to the Start position, the uf cubie will be in the lf cubicle. So we can identify the position "uf cubie in the lf cubicle" as being the inverse of "uf cubie in the rf cubicle". The two inverse positions are produced by applying their respective maneuvers to the Start position, and their respective maneuvers are inverse maneuvers. All seems to be going well.

But this pretty picture quickly falls apart with the following example. Apply the maneuver FRR to the Start position where the uf cubie is in the uf cubicle. The FRR maneuver will result in the uf cubie being in the rb cubicle. The uf cubie will obviously be brought back to its home cubicle by the inverse maneuver R-1R-1F-1. But when the maneuver R-1R-1F-1 is applied to the Start position itself, crazy things happen and the result is the uf cubie being in the lf cubicle, a location not even close to being the inverse of the uf cubie being in the rb cubicle.

It turns out that what we need for inverses is simply to exchange the role of cubie and cubicle. So the inverse of the uf cubie being in the rb cubicle has to be the rb cubie being in the uf cubicle. Indeed, if we think of the Start position where the rb cubie is in the rb cubicle and apply the maneuver R-1R-1F-1, then we end up with the rb cubie in the uf cubicle, exactly what we need.

However, the problem with calculating inverses of partial permutations by inverting the roles of the cubies and cubicles is that doing so does not preserve the subgroup H and its associated collection of cosets. More informally, the cube will have been recolored in a way that cannot happen on a real cube that has some of its cubies grayed out. Instead of preserving H, we may be in a subgroup H2 and its associated collection of cosets where H2 is a conjugate of H.

After many years, I finally decided that the solution is actually very simple. Go ahead and reverse the roles of the cubies and cubicles, and then find an m in M such that (m-1)(H2)(m)=H. Since H and H2 are conjugate, there will always be such an m. Then, having gotten the position back into the realm of H and its cosets, reduce the position by symmetry as normal. Well, as I have described before, we can't really use m-1. With partial permutations and a coset model where cosets are defined with irrelevant cubies grayed out, we have to use m_by_recoloring-1 rather than m-1.

Jerry
» login or register to post comments

I am confused by your definit

Submitted by B MacKenzie on Wed, 03/13/2013 - 19:09.

I am confused by your definition of the inverse of a partial permutation. Would this definition of inversion allow one to use anti-symmetry to reduce the cosets of a non-normal subgroup? If not, what is its purpose?

When you say "However, the problem with calculating inverses of partial permutations by inverting the roles of the cubies and cubicles is that doing so does not preserve the subgroup H and its associated collection of cosets", this is true in general but it is not true for a normal subgroup. For the subgroup of the cube with solved edge cubies one can characterize the inverse of a coset simply by inverting the edge facelet permutation. Since edge facelets are confined to edge facelet slots there is no problem.

» login or register to post comments

I really want to give some

Submitted by Jerry Bryan on Wed, 03/13/2013 - 23:10.

I really want to give some more thought to my approach before trying to answer your question in detail. That's because I think I see a problem with my approach that I hadn't noticed before, but I still think some of my approach can be rescued. But in the meantime I have two comments and one question.

Comment #1: The best discussion of normal subgroups that I'm aware of in the context of Rubik's cube may be found at
http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/Martin_Schoenert__Re__Normal_Subgroups_of_G.html

Question: Could you clarify just a bit about what you take it to mean that a coset space can be reduced by anti-symmetry? In the case of a particular position x in the cube group G, to say that x can be reduced by anti-symmetry means to me that if y=x-1 then the sets xM and yM are disjoint (xM means the set of all m-1xm for all m in M).

If H is a subgroup of G defined in terms of fixing certain cubies and Hg for a fixed g in G is a coset, then I'm trying to use the same basic definitions for symmetry and anti-symmetry for cosets as for positions. For each coset Hg we take x to be a partial permutation taken from any element of Hg where x contains only those cubies fixed in H. For any fixed coset Hg, the partial permutation x will be the same for any permutation in Hg. Hence, we can identify the partial permutation x with the coset Hg.

Comment #2. Let's suppose that we let H be the trivial subgroup of the cube group G consisting only of the identity. Then, each coset contains only one element and every element of G may be identified with the coset that contains it. According to the way I think of being able to reduce permutations and cosets by anti-symmetry, some of the elements of G and hence some of the cosets of H can be reduced by anti-symmetry and some cannot even though H is normal. That is, if y=x-1 then xM and yM are the same set for some x in G and they are disjoint for other x in G. I'm taking x and y to be permutations that are elements of G, but as as indicated above each element of G can be identified with the coset that contains it for the trivial case where H contains only the identity.

Jerry

» login or register to post comments

I quickly read through Martin

Submitted by B MacKenzie on Thu, 03/14/2013 - 10:42.

I quickly read through Martin Schoenert's post. It contains a lot of group theory that I am not familiar with so I am going to have to spend some time studying it. The normal subgroups of the cube group G (fixed center model) which come to mind are:

1. G itself

2. The trivial subgroup.

3. Superflip

4. The subgroup with the edges in their starting positions regardless of their orientations.

5. The subgroup with the corners in their starting positions regardless of their orientations.

6. The subgroup with all cubies in their starting positions regardless of their orientations.

7. The fixed edges subgroup.

8. The fixed corners subgroup.

Schoenert comes up with five more. One is the commutator subgroup which I don't have a good feeling for. The others come by conjoining some of the above. I'll have to think about it.

A coset space is reducible by anti-symmetry if for all cosets the set of all inverses of the elements of the coset is also a coset. Now it may be that a particular coset is anti-symmetric and the set of the inverses is the same coset or a symmetry equivalent coset. In those cases there is no actual reduction. For the trivial subgroup its coset space is G which is reducible by anti-symmetry.

I wanted to get a feel for your partial permutation inversion method so I tried to apply it to a random coset of the fixed Up cubie subgroup:

Slots  UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR
g      -- -- -- BU -- -- -- UR UL -- UF -- --- --- --- BLU FUL --- UFR RBU
g'     BR DL LU FR -- -- -- -- -- -- -- -- DLB RDB FUL RFD --- --- --- ---

As may be seen the set of cubies specified in the inverse partial permutation are scattered about the cube. There is no M symmetry which maps these cubies onto the Up face cubies. They would all have to be Front face cubies or Down face cubies, etc for that to be the case. So it looks to me like there is a problem with what you are doing.

» login or register to post comments

> I wanted to get a feel fo

Submitted by Jerry Bryan on Thu, 03/14/2013 - 21:20.

> I wanted to get a feel for your partial permutation inversion method so I tried to apply it to a random coset of the fixed Up cubie subgroup: 

> Slots  UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR
> g      -- -- -- BU -- -- -- UR UL -- UF -- --- --- --- BLU FUL --- UFR RBU
> g'     BR DL LU FR -- -- -- -- -- -- -- -- DLB RDB FUL RFD --- --- --- ---

> As may be seen the set of cubies specified in the inverse partial
> permutation are scattered about the cube. There is no M symmetry
> which maps these cubies onto the Up face cubies. They would all
> have to be Front face cubies or Down face cubies, etc for that to
> be the case. So it looks to me like there is a problem with what
> you are doing.

You are correct. In my message entitled "Anti-symmetry by Recoloring" I stated that after taking the inverse of a partial permutation there will always be an m that under conjugation will return the inverse to the same set of cubies as were in the original subgroup. However, as your example so clearly shows, that is wrong. And as I think about it, I'm beginning to remember that I came to the same conclusion about a year ago. But I never wrote down my conclusion so I had to discover it again with your help.

Notwithstanding that regrettable error, there are examples that do work with my method despite the fact that the underlying subgroup is not normal. For example, consider the subgroup H that fixes the uf cubie. H is not normal. Nonetheless, there will always exist exactly two values of m in M that will return each coset inverse to the the same set of cubies that was used to define H.

Let me elaborate a bit. H is defined in this example as the set of all permutations that fix the uf cube. We may identify this condition with the partial permutation uf -> uf. The 24 cosets may be characterized by partial permutations of the form uf -> vw or uf -> wv where v is a primary color tab for the cubie and w is a secondary color tab for the cubie. Defining a primary and secondary color tab for each cubie is a way to define a frame of reference to be able to determine whether the cubie is flipped or not when it is not in its home cubicle.

Therefore, the 24 right cosets may be characterized by such partial permutations as uf -> uf, uf -> fu, uf -> ul, uf -> lu, etc. for all 24 possibilities. We may in turn identify these partial permutations with cube positions by identifying each partial permutation with the cube position that results from applying the partial permutation to the Start position where all the corner and edge cubies are grayed out except for the uf cubie. For example, we identify the partial permutation uf -> ul with the position where the uf cube is in the ul cubicle with the u color tab aligned with the U face, and we identify the partial permutation uf -> lu with the position where the uf cubie is in the ul cubicle with the u color tab aligned with the L face. This characterization of right cosets is completely compatible with a coset model where irrelevant cubies are grayed out. All that's really required to identify a coset is to identify the location (position and flip) of the uf cubie. So we can keep the other cubies and ignore them, or we can just gray them out.

With a right coset model where irrelevant cubies are grayed out, it's not even possible to define left cosets. For left cosets, we would need to characterize each coset as follows: uf -> uf, fu -> uf, ul -> uf, lu -> uf, etc. In other words, we would need to characterize each left coset by the contents of the uf cubicle. Any of the 24 cubie/flip combinations can be in the uf cubicle, so we cannot gray out any of the cubicles if we are going to define left cosets.

What happens with inverses of the cosets for the fixed uf cubie group is that taking an inverse maps a right coset to a left coset. For example, uf -> ul is mapped by the inverse operation to ul -> uf. The way we map permutations to cube positions, we may identify uf -> ul with "the uf cubie is in the ul cubicle" and we similarly interpret ul -> uf to mean "the ul cubie is in the uf cubicle". Informally speaking, the ul cubie is the "wrong color", but for this particular H we can always find two m values that will recolor ul back to being in H.

I haven't explained it very well, but it seems to me that it is correct that it's not possible to take inverses of cosets in the normal sense of "inverses" unless the subgroup is normal. But it also seems to me that it is possible to take "inverses" of some but not all cosets if the "inverse" operation is taken to be an inverse combined with a symmetry operation, and if there exists a symmetry operation which will restore the cubies as they are after the standard inverse operation back to the cubies that defined the subgroup.

Jerry

» login or register to post comments

Normal Subgroups of the Cube Group

Submitted by B MacKenzie on Thu, 03/14/2013 - 17:10.

I've been trying to puzzle out Schoenert's post about normal subgroups. Looking at his lattice:

                    G
                    | 2
                    G'
                   / \
                  /   \
                 /     \
                /       \
               /         \
              /           \
             /             \
            /               \
           /                 PE
          /                 / \
         /                 /   \
        /                 /     \
       PC                /       \
      / \               /         \
     /   \             /          GE'
    /     \           /           /
   X       \         /           /
  / \       \       /           /
GC'  \       \     /           /
  \   \       \   /           /
   \   \       \ /           / 12!/2
    \   \       P           /
8!/2 \   \     / \         /
      \   \   /   \       /
       \   \ /     \     /
        \   X       \   /
         \ / \       \ /
         VC   \       VE
           \   \     /
            \   \   / 2^10
         3^7 \   \ /
              \   Z
               \ / 2
               <1>

I think I can identify the nodes as follows:

  • G': The commutator subgroup. This subgroup is half the size of G and is the subgroup of cube states with even turn parity. That is, those cube states with even edge parity and even corner parity.

  • GE': The fixed corner cubie subgroup

  • GC': The fixed edge cubie subgroup

  • VE: The fixed corner subgroup with all edges in their starting positions regardless of orientation

  • VC: The fixed edges subgroup with all corners in their starting positions regardless of orientation.

  • Z: Superflip + identity.

  • <1>: The trivial subgroup.

  • P: The subgroup with all cubies in their starting positions regardless of orientation.

  • PC: The subgroup with the edge cubies in their starting positions regardless of orientation.

  • PE: The subgroup with the corner cubies in their starting positions regardless of orientation.

  • x The closure of the two fixed edge cubie subgroups with superflip.

I am by no means certain of these assignments so correct me if I am wrong. I have labeled some of the nodes Schoenert labels with x with P to denote the subgroup fixes position permutation only. A lot of Schoenert's arguments go over my head so I cannot evaluate them critically. If his arguments are sound, and I have no reason to believe they are not, then these are the sum of the normal subgroups of the cube group.

» login or register to post comments

> The elements of a symmetry

Submitted by Jerry Bryan on Fri, 03/08/2013 - 13:05.
> The elements of a symmetry equivalence class, m' g m (where m ranges
> over the cubic symmetry group and g is an element of the Rubik's cube
> group), are all at the same depth in the Cayley graph.

A very minor caveat is required for this statement to be true, although the caveat is readily satisfied for nearly all the problems we work on. Namely, it must be the case that if g is a generator for the group, then (m-1 g m) must also be a generator for the group. This condition of "closure of generators under symmetry" is certainly true for conventional problems in both the quarter turn metric and the face turn metric.

One case where certain care must be taken is a group generated, for example, as G=<U,R,U-1,R-1>. In this particular case, we cannot use the entire group M to determine the symmetries of the elements of G. Rather, we must restrict ourselves to the subgroup of elements in M that preserve the set of generators. If we restrict ourselves in this way, then we can still say that for this particular group G that there is "closure of generators under symmetry".

A more salient example is the stuck axle problem, where quarter turns and/or half turns are only allowed on 5 of the 6 faces of the cube. For an example with the quarter turn metric, we might generate a group as G=<F,U,R,D,L,F-1,U-1,R-1,D-1,L-1>. In this case, the group is the standard Rubik's cube group but the Cayley graph is not the standard Cayley graph for the quarter turn metric. The problem in this case is that the position that we normally denote by the maneuver B is more than one move from Start and therefore there are certain positions g and symmetries m such that (m-1 g m) is not at the same level of the Cayley graph as is the position g itself. The solution as before is to use the subgroup of M that preserves the generators as the symmetries for the stuck axle problem rather than using the entirety of M as the symmetries for the stuck axle problem.

But to repeat, these caveats don't apply most of the time, and they certainly don't apply to the problems Bruce is describing.

Jerry
» login or register to post comments

A correction to my caveat

Submitted by Jerry Bryan on Fri, 03/08/2013 - 23:35.
I need to post a minor correction to my caveat. I said the following.

> But to repeat, these caveats don't apply most of the time, and they
> certainly don't apply to the problems Bruce is describing.

In fact, my caveat does apply to one of Bruce's examples. In particular, it applies to the example of the "fixed Up cubie" subgroup. However, Bruce's original message already includes the appropriate "caveat", although using a slightly different language than I used. The two relevant portions of Bruce's message that include the appropriate caveat are as follows:

> A coset space may be reduced by symmetry only for those symmetry
> elements for which m' * SUB * m = SUB

and

> The fixed Up cubie subgroup ... only shows C4v
> symmetry. All other symmetries swap Up layer cubies with lower
> layer cubies and are not useable. Thus this coset space may only be
> reduced about eight fold.

So the "fixed Up cubie" subgroup does need my caveat, and Bruce did include the caveat in his message. His description is absolutely correct that when dealing with symmetry of the "fixed Up cubie" subgroup and its associated cosets one must only use the elements of M that are in C4v.

Jerry
» login or register to post comments

Schoenflies symbols and the C4v subgroups of M

Submitted by Jerry Bryan on Fri, 03/08/2013 - 23:52.
Most everybody uses Schoenflies symbols to refer to the subgroups of M. I totally understand why, because Schoenflies symbols are so widely used and are such a standard. But I'm always a little frustrated with them because with respect to the group of symmetries M and Rubik's Cube, most Schoenflies symbols actually refer to a set of conjugate subgroups of M rather than referring to a particular subgroup of M.

The C4v symbol is a good example. C4v symmetries are associated with a face-to-face axis - Front/Back, Up/Down, or Left/Right and hence the C4v symbol is associated with three different subgroups of M. Which is my point. To which of the three axes (and hence to which of the three subgroups) are we applying the name C4v?

I would be happier if the three subgroups were named something like C4v-FB, C4v-UD, and C4v-LR. In this context, Bruce's "fixed Up cubie" subgroup has C4v-UD symmetry. But I gather that physics, chemistry, etc. do not go beyond the C4v symbol when considering the geometric symmetry associated with molecules or crystals or whatever.

Jerry
» login or register to post comments

Cubic Group Subgroups

Submitted by B MacKenzie on Sat, 03/09/2013 - 01:21.

You are right about the ambiguity involved in specifying the subgroups of the cubic symmetry group with Schoenflies symbols. One must winnow out which particular subgroup is referred to from the context. Consider the <U , F , B> group and the <U , F> group. Both groups show C2v symmetry but the two cubic group subgroups are not even symmetry equivalent within the cubic group. One uses a C2 = C24 as the principal axis and the other uses a dihedral C2 as the principal axis. Still I think the symmetry elements involved are apparent from the context, but perhaps that is because I'm very familiar with the Schoenflies naming system.

» login or register to post comments

Symm and SymmClass

Submitted by Jerry Bryan on Sat, 03/09/2013 - 08:16.
Yes, you are totally correct that the symmetry elements are usually totally apparent from context. For example, I had no trouble at all determining from context that your C4v subgroup is actually what I called the C4v-UD subgroup in my follow-up message to indicate that your C4v is aligned with the U-D axis.

I don't have the same familiarity with the Schoenflies as symbols as most of the rest of you all probably do, and I'm truly not trying to be argumentative here. I realize that I'm surely the one who is out of step with the rest of the world with respect to Schoenfiles symbols. :)

It's just that I've spent more than twenty-five years where my programs calculate what I call Symm(x) where Symm(x) is the subgroup of symmetries associated with the permutation x. And to say Symm(x)=C4v in my programs would be totally ambiguous. Using Schoenflies symbols, I would have to say something like Symm(x)=C4v-UD or Symm(x)=C4v-FB etc. I then summarize results into what I call SymmClass, where if Symm(x)=C4v-FB then it really would be the case that SymmClass(x)=C4v. So using the terminology of Schoenflies symbols I would say C4v={C4v-UD,C4v-FB,C4v-LR). My SymmClass and Symm tables obviously contain 33 elements and 98 elements, respectively.

As an example of a case where it's very important to have Symm(x) rather than SymmClass(x), it's sometimes useful to calculate the symmetry for the corners separately from the symmetry for the edges. If we write x as (xc,xe), then it's perfectly meaningful to calculate Symm(xc) and Symm(xe) separately. And it can be extremely useful to do so, for example if using the fixed corners group or the fixed edges group to define cosets. And having done so, it then is the case that Symm(x)=Symm(xc) ∩ Symm(xe). On the other hand, if we consider x and m-1xm, then it's often not the case that Symm(x)=Symm(m-1xm) but it's always the case that SymmClass(x)=SymmClass(m-1xm).

Jerry
» login or register to post comments

Your post got me to fooling a

Submitted by B MacKenzie on Sun, 07/21/2013 - 19:32.

Your post got me to fooling around with the subgroups of the cubic, or Oh, point group. I wrote some code to generate the subgroups and sorted them by equivalence class. I indeed found 98 distinct subgroups. And conjugation affords 33 classes of symmetry equivalent groups:

The Oh Group has 98 subgroups in 33 classes.

Class 1 C1
1 equivalent groups of order 1
(
     x, y, z  E  
)

Class 2 Ci
1 equivalent groups of order 2
(
     x, y, z  E  
    -x,-y,-z  i  
)

Class 3 S4
3 equivalent groups of order 4
(
     x, y, z  E  
    -x, y,-z  C2y 
     z,-y,-x  S4y 
    -z,-y, x  S34y
)
(
     x, y, z  E  
     x,-y,-z  C2x 
    -x,-z, y  S4x 
    -x, z,-y  S34x
)
(
     x, y, z  E  
    -x,-y, z  C2z 
    -y, x,-z  S4z 
     y,-x,-z  S34z
)

Class 4 C2
3 equivalent groups of order 2
(
     x, y, z  E  
    -x,-y, z  C2z 
)
(
     x, y, z  E  
    -x, y,-z  C2y 
)
(
     x, y, z  E  
     x,-y,-z  C2x 
)

Class 5 C2
6 equivalent groups of order 2
(
     x, y, z  E  
    -x, z, y  C2yz 
)
(
     x, y, z  E  
     z,-y, x  C2xz 
)
(
     x, y, z  E  
     y, x,-z  C2xy 
)
(
     x, y, z  E  
    -y,-x,-z  C2xy' 
)
(
     x, y, z  E  
    -z,-y,-x  C2xz' 
)
(
     x, y, z  E  
    -x,-z,-y  C2yz' 
)

Class 6 C3
4 equivalent groups of order 3
(
     x, y, z  E  
    -z,-x, y  C3xy'z' 
    -y, z,-x  C23xy'z'
)
(
     x, y, z  E  
     z, x, y  C3xyz 
     y, z, x  C23xyz
)
(
     x, y, z  E  
    -z, x,-y  C3x'y'z 
     y,-z,-x  C23x'y'z
)
(
     x, y, z  E  
     z,-x,-y  C3x'yz' 
    -y,-z, x  C23x'yz'
)

Class 7 Cs
6 equivalent groups of order 2
(
     x, y, z  E  
     x, z, y  σd_yz 
)
(
     x, y, z  E  
     z, y, x  σd_xz 
)
(
     x, y, z  E  
     y, x, z  σd_xy 
)
(
     x, y, z  E  
    -y,-x, z  σd_xy' 
)
(
     x, y, z  E  
    -z, y,-x  σd_xz' 
)
(
     x, y, z  E  
     x,-z,-y  σd_yz' 
)

Class 8 Cs
3 equivalent groups of order 2
(
     x, y, z  E  
     x, y,-z  σh_z 
)
(
     x, y, z  E  
     x,-y, z  σh_y 
)
(
     x, y, z  E  
    -x, y, z  σh_x 
)

Class 9 C4
3 equivalent groups of order 4
(
     x, y, z  E  
    -x, y,-z  C2y 
     z, y,-x  C4y 
    -z, y, x  C34y
)
(
     x, y, z  E  
     x,-y,-z  C2x 
     x,-z, y  C4x 
     x, z,-y  C34x
)
(
     x, y, z  E  
    -x,-y, z  C2z 
    -y, x, z  C4z 
     y,-x, z  C34z
)

Class 10 S6
4 equivalent groups of order 6
(
     x, y, z  E  
    -z,-x, y  C3xy'z' 
    -y, z,-x  C23xy'z'
    -x,-y,-z  i  
     y,-z, x  S6xy'z' 
     z, x,-y  S56xy'z'
)
(
     x, y, z  E  
     z, x, y  C3xyz 
     y, z, x  C23xyz
    -x,-y,-z  i  
    -y,-z,-x  S6xyz 
    -z,-x,-y  S56xyz
)
(
     x, y, z  E  
    -z, x,-y  C3x'y'z 
     y,-z,-x  C23x'y'z
    -x,-y,-z  i  
    -y, z, x  S6x'y'z 
     z,-x, y  S56x'y'z
)
(
     x, y, z  E  
     z,-x,-y  C3x'yz' 
    -y,-z, x  C23x'yz'
    -x,-y,-z  i  
     y, z,-x  S6x'yz' 
    -z, x, y  S56x'yz'
)

Class 11 D4
3 equivalent groups of order 8
(
     x, y, z  E  
     x,-y,-z  C2x 
    -x, y,-z  C2y 
    -x,-y, z  C2z 
     z, y,-x  C4y 
    -z, y, x  C34y
     z,-y, x  C2xz 
    -z,-y,-x  C2xz' 
)
(
     x, y, z  E  
     x,-y,-z  C2x 
    -x, y,-z  C2y 
    -x,-y, z  C2z 
     x,-z, y  C4x 
     x, z,-y  C34x
    -x, z, y  C2yz 
    -x,-z,-y  C2yz' 
)
(
     x, y, z  E  
     x,-y,-z  C2x 
    -x, y,-z  C2y 
    -x,-y, z  C2z 
    -y, x, z  C4z 
     y,-x, z  C34z
     y, x,-z  C2xy 
    -y,-x,-z  C2xy' 
)

Class 12 D2
1 equivalent groups of order 4
(
     x, y, z  E  
     x,-y,-z  C2x 
    -x, y,-z  C2y 
    -x,-y, z  C2z 
)

Class 13 D2
3 equivalent groups of order 4
(
     x, y, z  E  
     x,-y,-z  C2x 
    -x, z, y  C2yz 
    -x,-z,-y  C2yz' 
)
(
     x, y, z  E  
    -x,-y, z  C2z 
     y, x,-z  C2xy 
    -y,-x,-z  C2xy' 
)
(
     x, y, z  E  
    -x, y,-z  C2y 
     z,-y, x  C2xz 
    -z,-y,-x  C2xz' 
)

Class 14 D3
4 equivalent groups of order 6
(
     x, y, z  E  
     z, x, y  C3xyz 
     y, z, x  C23xyz
    -y,-x,-z  C2xy' 
    -z,-y,-x  C2xz' 
    -x,-z,-y  C2yz' 
)
(
     x, y, z  E  
    -z,-x, y  C3xy'z' 
    -y, z,-x  C23xy'z'
     y, x,-z  C2xy 
     z,-y, x  C2xz 
    -x,-z,-y  C2yz' 
)
(
     x, y, z  E  
     z,-x,-y  C3x'yz' 
    -y,-z, x  C23x'yz'
     y, x,-z  C2xy 
    -z,-y,-x  C2xz' 
    -x, z, y  C2yz 
)
(
     x, y, z  E  
    -z, x,-y  C3x'y'z 
     y,-z,-x  C23x'y'z
    -y,-x,-z  C2xy' 
     z,-y, x  C2xz 
    -x, z, y  C2yz 
)

Class 15 C2v
3 equivalent groups of order 4
(
     x, y, z  E  
    -x, y,-z  C2y 
     z, y, x  σd_xz 
    -z, y,-x  σd_xz' 
)
(
     x, y, z  E  
     x,-y,-z  C2x 
     x, z, y  σd_yz 
     x,-z,-y  σd_yz' 
)
(
     x, y, z  E  
    -x,-y, z  C2z 
     y, x, z  σd_xy 
    -y,-x, z  σd_xy' 
)

Class 16 c2v
3 equivalent groups of order 4
(
     x, y, z  E  
    -x, y,-z  C2y 
    -x, y, z  σh_x 
     x, y,-z  σh_z 
)
(
     x, y, z  E  
     x,-y,-z  C2x 
     x,-y, z  σh_y 
     x, y,-z  σh_z 
)
(
     x, y, z  E  
    -x,-y, z  C2z 
    -x, y, z  σh_x 
     x,-y, z  σh_y 
)

Class 17 C2v
6 equivalent groups of order 4
(
     x, y, z  E  
     y, x,-z  C2xy 
     y, x, z  σd_xy 
     x, y,-z  σh_z 
)
(
     x, y, z  E  
    -y,-x,-z  C2xy' 
    -y,-x, z  σd_xy' 
     x, y,-z  σh_z 
)
(
     x, y, z  E  
    -z,-y,-x  C2xz' 
    -z, y,-x  σd_xz' 
     x,-y, z  σh_y 
)
(
     x, y, z  E  
    -x,-z,-y  C2yz' 
     x,-z,-y  σd_yz' 
    -x, y, z  σh_x 
)
(
     x, y, z  E  
    -x, z, y  C2yz 
     x, z, y  σd_yz 
    -x, y, z  σh_x 
)
(
     x, y, z  E  
     z,-y, x  C2xz 
     z, y, x  σd_xz 
     x,-y, z  σh_y 
)

Class 18 c2h
3 equivalent groups of order 4
(
     x, y, z  E  
    -x, y,-z  C2y 
    -x,-y,-z  i  
     x,-y, z  σh_y 
)
(
     x, y, z  E  
     x,-y,-z  C2x 
    -x,-y,-z  i  
    -x, y, z  σh_x 
)
(
     x, y, z  E  
    -x,-y, z  C2z 
    -x,-y,-z  i  
     x, y,-z  σh_z 
)

Class 19 C2h
6 equivalent groups of order 4
(
     x, y, z  E  
     y, x,-z  C2xy 
    -y,-x, z  σd_xy' 
    -x,-y,-z  i  
)
(
     x, y, z  E  
    -y,-x,-z  C2xy' 
     y, x, z  σd_xy 
    -x,-y,-z  i  
)
(
     x, y, z  E  
    -z,-y,-x  C2xz' 
     z, y, x  σd_xz 
    -x,-y,-z  i  
)
(
     x, y, z  E  
    -x,-z,-y  C2yz' 
     x, z, y  σd_yz 
    -x,-y,-z  i  
)
(
     x, y, z  E  
    -x, z, y  C2yz 
     x,-z,-y  σd_yz' 
    -x,-y,-z  i  
)
(
     x, y, z  E  
     z,-y, x  C2xz 
    -z, y,-x  σd_xz' 
    -x,-y,-z  i  
)

Class 20 D3d
4 equivalent groups of order 12
(
     x, y, z  E  
     z,-x,-y  C3x'yz' 
    -y,-z, x  C23x'yz'
     y, x,-z  C2xy 
    -z,-y,-x  C2xz' 
    -x, z, y  C2yz 
    -y,-x, z  σd_xy' 
     z, y, x  σd_xz 
     x,-z,-y  σd_yz' 
    -x,-y,-z  i  
     y, z,-x  S6x'yz' 
    -z, x, y  S56x'yz'
)
(
     x, y, z  E  
    -z, x,-y  C3x'y'z 
     y,-z,-x  C23x'y'z
    -y,-x,-z  C2xy' 
     z,-y, x  C2xz 
    -x, z, y  C2yz 
     y, x, z  σd_xy 
    -z, y,-x  σd_xz' 
     x,-z,-y  σd_yz' 
    -x,-y,-z  i  
    -y, z, x  S6x'y'z 
     z,-x, y  S56x'y'z
)
(
     x, y, z  E  
     z, x, y  C3xyz 
     y, z, x  C23xyz
    -y,-x,-z  C2xy' 
    -z,-y,-x  C2xz' 
    -x,-z,-y  C2yz' 
     y, x, z  σd_xy 
     z, y, x  σd_xz 
     x, z, y  σd_yz 
    -x,-y,-z  i  
    -y,-z,-x  S6xyz 
    -z,-x,-y  S56xyz
)
(
     x, y, z  E  
    -z,-x, y  C3xy'z' 
    -y, z,-x  C23xy'z'
     y, x,-z  C2xy 
     z,-y, x  C2xz 
    -x,-z,-y  C2yz' 
    -y,-x, z  σd_xy' 
    -z, y,-x  σd_xz' 
     x, z, y  σd_yz 
    -x,-y,-z  i  
     y,-z, x  S6xy'z' 
     z, x,-y  S56xy'z'
)

Class 21 D2d
3 equivalent groups of order 8
(
     x, y, z  E  
    -x, y,-z  C2y 
     z,-y, x  C2xz 
    -z,-y,-x  C2xz' 
     z,-y,-x  S4y 
    -z,-y, x  S34y
    -x, y, z  σh_x 
     x, y,-z  σh_z 
)
(
     x, y, z  E  
     x,-y,-z  C2x 
    -x, z, y  C2yz 
    -x,-z,-y  C2yz' 
    -x,-z, y  S4x 
    -x, z,-y  S34x
     x,-y, z  σh_y 
     x, y,-z  σh_z 
)
(
     x, y, z  E  
    -x,-y, z  C2z 
     y, x,-z  C2xy 
    -y,-x,-z  C2xy' 
    -y, x,-z  S4z 
     y,-x,-z  S34z
    -x, y, z  σh_x 
     x,-y, z  σh_y 
)

Class 22 D2d
3 equivalent groups of order 8
(
     x, y, z  E  
     x,-y,-z  C2x 
    -x, y,-z  C2y 
    -x,-y, z  C2z 
     z, y, x  σd_xz 
    -z, y,-x  σd_xz' 
     z,-y,-x  S4y 
    -z,-y, x  S34y
)
(
     x, y, z  E  
     x,-y,-z  C2x 
    -x, y,-z  C2y 
    -x,-y, z  C2z 
     x, z, y  σd_yz 
     x,-z,-y  σd_yz' 
    -x,-z, y  S4x 
    -x, z,-y  S34x
)
(
     x, y, z  E  
     x,-y,-z  C2x 
    -x, y,-z  C2y 
    -x,-y, z  C2z 
     y, x, z  σd_xy 
    -y,-x, z  σd_xy' 
    -y, x,-z  S4z 
     y,-x,-z  S34z
)

Class 23 C3v
4 equivalent groups of order 6
(
     x, y, z  E  
    -z,-x, y  C3xy'z' 
    -y, z,-x  C23xy'z'
    -y,-x, z  σd_xy' 
    -z, y,-x  σd_xz' 
     x, z, y  σd_yz 
)
(
     x, y, z  E  
     z, x, y  C3xyz 
     y, z, x  C23xyz
     y, x, z  σd_xy 
     z, y, x  σd_xz 
     x, z, y  σd_yz 
)
(
     x, y, z  E  
    -z, x,-y  C3x'y'z 
     y,-z,-x  C23x'y'z
     y, x, z  σd_xy 
    -z, y,-x  σd_xz' 
     x,-z,-y  σd_yz' 
)
(
     x, y, z  E  
     z,-x,-y  C3x'yz' 
    -y,-z, x  C23x'yz'
    -y,-x, z  σd_xy' 
     z, y, x  σd_xz 
     x,-z,-y  σd_yz' 
)

Class 24 C4v
3 equivalent groups of order 8
(
     x, y, z  E  
    -x,-y, z  C2z 
    -y, x, z  C4z 
     y,-x, z  C34z
     y, x, z  σd_xy 
    -y,-x, z  σd_xy' 
    -x, y, z  σh_x 
     x,-y, z  σh_y 
)
(
     x, y, z  E  
    -x, y,-z  C2y 
     z, y,-x  C4y 
    -z, y, x  C34y
     z, y, x  σd_xz 
    -z, y,-x  σd_xz' 
    -x, y, z  σh_x 
     x, y,-z  σh_z 
)
(
     x, y, z  E  
     x,-y,-z  C2x 
     x,-z, y  C4x 
     x, z,-y  C34x
     x, z, y  σd_yz 
     x,-z,-y  σd_yz' 
     x,-y, z  σh_y 
     x, y,-z  σh_z 
)

Class 25 C4h
3 equivalent groups of order 8
(
     x, y, z  E  
    -x,-y, z  C2z 
    -y, x, z  C4z 
     y,-x, z  C34z
    -y, x,-z  S4z 
     y,-x,-z  S34z
    -x,-y,-z  i  
     x, y,-z  σh_z 
)
(
     x, y, z  E  
    -x, y,-z  C2y 
     z, y,-x  C4y 
    -z, y, x  C34y
     z,-y,-x  S4y 
    -z,-y, x  S34y
    -x,-y,-z  i  
     x,-y, z  σh_y 
)
(
     x, y, z  E  
     x,-y,-z  C2x 
     x,-z, y  C4x 
     x, z,-y  C34x
    -x,-z, y  S4x 
    -x, z,-y  S34x
    -x,-y,-z  i  
    -x, y, z  σh_x 
)

Class 26 D2h
1 equivalent groups of order 8
(
     x, y, z  E  
     x,-y,-z  C2x 
    -x, y,-z  C2y 
    -x,-y, z  C2z 
    -x,-y,-z  i  
    -x, y, z  σh_x 
     x,-y, z  σh_y 
     x, y,-z  σh_z 
)

Class 27 D2h
3 equivalent groups of order 8
(
     x, y, z  E  
    -x, y,-z  C2y 
     z,-y, x  C2xz 
    -z,-y,-x  C2xz' 
     z, y, x  σd_xz 
    -z, y,-x  σd_xz' 
    -x,-y,-z  i  
     x,-y, z  σh_y 
)
(
     x, y, z  E  
     x,-y,-z  C2x 
    -x, z, y  C2yz 
    -x,-z,-y  C2yz' 
     x, z, y  σd_yz 
     x,-z,-y  σd_yz' 
    -x,-y,-z  i  
    -x, y, z  σh_x 
)
(
     x, y, z  E  
    -x,-y, z  C2z 
     y, x,-z  C2xy 
    -y,-x,-z  C2xy' 
     y, x, z  σd_xy 
    -y,-x, z  σd_xy' 
    -x,-y,-z  i  
     x, y,-z  σh_z 
)

Class 28 D4h
3 equivalent groups of order 16
(
     x, y, z  E  
     x,-y,-z  C2x 
    -x, y,-z  C2y 
    -x,-y, z  C2z 
     x,-z, y  C4x 
     x, z,-y  C34x
    -x, z, y  C2yz 
    -x,-z,-y  C2yz' 
     x, z, y  σd_yz 
     x,-z,-y  σd_yz' 
    -x,-z, y  S4x 
    -x, z,-y  S34x
    -x,-y,-z  i  
    -x, y, z  σh_x 
     x,-y, z  σh_y 
     x, y,-z  σh_z 
)
(
     x, y, z  E  
     x,-y,-z  C2x 
    -x, y,-z  C2y 
    -x,-y, z  C2z 
    -y, x, z  C4z 
     y,-x, z  C34z
     y, x,-z  C2xy 
    -y,-x,-z  C2xy' 
     y, x, z  σd_xy 
    -y,-x, z  σd_xy' 
    -y, x,-z  S4z 
     y,-x,-z  S34z
    -x,-y,-z  i  
    -x, y, z  σh_x 
     x,-y, z  σh_y 
     x, y,-z  σh_z 
)
(
     x, y, z  E  
     x,-y,-z  C2x 
    -x, y,-z  C2y 
    -x,-y, z  C2z 
     z, y,-x  C4y 
    -z, y, x  C34y
     z,-y, x  C2xz 
    -z,-y,-x  C2xz' 
     z, y, x  σd_xz 
    -z, y,-x  σd_xz' 
     z,-y,-x  S4y 
    -z,-y, x  S34y
    -x,-y,-z  i  
    -x, y, z  σh_x 
     x,-y, z  σh_y 
     x, y,-z  σh_z 
)

Class 29 T
1 equivalent groups of order 12
(
     x, y, z  E  
     x,-y,-z  C2x 
    -x, y,-z  C2y 
    -x,-y, z  C2z 
    -z, x,-y  C3x'y'z 
     y,-z,-x  C23x'y'z
     z,-x,-y  C3x'yz' 
    -y,-z, x  C23x'yz'
    -z,-x, y  C3xy'z' 
    -y, z,-x  C23xy'z'
     z, x, y  C3xyz 
     y, z, x  C23xyz
)

Class 30 Th
1 equivalent groups of order 24
(
     x, y, z  E  
     x,-y,-z  C2x 
    -x, y,-z  C2y 
    -x,-y, z  C2z 
    -z, x,-y  C3x'y'z 
     y,-z,-x  C23x'y'z
     z,-x,-y  C3x'yz' 
    -y,-z, x  C23x'yz'
    -z,-x, y  C3xy'z' 
    -y, z,-x  C23xy'z'
     z, x, y  C3xyz 
     y, z, x  C23xyz
    -x,-y,-z  i  
    -x, y, z  σh_x 
     x,-y, z  σh_y 
     x, y,-z  σh_z 
    -y, z, x  S6x'y'z 
     z,-x, y  S56x'y'z
     y, z,-x  S6x'yz' 
    -z, x, y  S56x'yz'
     y,-z, x  S6xy'z' 
     z, x,-y  S56xy'z'
    -y,-z,-x  S6xyz 
    -z,-x,-y  S56xyz
)

Class 31 Td
1 equivalent groups of order 24
(
     x, y, z  E  
     x,-y,-z  C2x 
    -x, y,-z  C2y 
    -x,-y, z  C2z 
    -z, x,-y  C3x'y'z 
     y,-z,-x  C23x'y'z
     z,-x,-y  C3x'yz' 
    -y,-z, x  C23x'yz'
    -z,-x, y  C3xy'z' 
    -y, z,-x  C23xy'z'
     z, x, y  C3xyz 
     y, z, x  C23xyz
     y, x, z  σd_xy 
    -y,-x, z  σd_xy' 
     z, y, x  σd_xz 
    -z, y,-x  σd_xz' 
     x, z, y  σd_yz 
     x,-z,-y  σd_yz' 
    -x,-z, y  S4x 
    -x, z,-y  S34x
     z,-y,-x  S4y 
    -z,-y, x  S34y
    -y, x,-z  S4z 
     y,-x,-z  S34z
)

Class 32 O
1 equivalent groups of order 24
(
     x, y, z  E  
     x,-y,-z  C2x 
    -x, y,-z  C2y 
    -x,-y, z  C2z 
    -z, x,-y  C3x'y'z 
     y,-z,-x  C23x'y'z
     z,-x,-y  C3x'yz' 
    -y,-z, x  C23x'yz'
    -z,-x, y  C3xy'z' 
    -y, z,-x  C23xy'z'
     z, x, y  C3xyz 
     y, z, x  C23xyz
     x,-z, y  C4x 
     x, z,-y  C34x
     z, y,-x  C4y 
    -z, y, x  C34y
    -y, x, z  C4z 
     y,-x, z  C34z
     y, x,-z  C2xy 
    -y,-x,-z  C2xy' 
     z,-y, x  C2xz 
    -z,-y,-x  C2xz' 
    -x, z, y  C2yz 
    -x,-z,-y  C2yz' 
)

Class 33 Oh
1 equivalent groups of order 48
(
     x, y, z  E  
     x,-y,-z  C2x 
    -x, y,-z  C2y 
    -x,-y, z  C2z 
    -z, x,-y  C3x'y'z 
     y,-z,-x  C23x'y'z
     z,-x,-y  C3x'yz' 
    -y,-z, x  C23x'yz'
    -z,-x, y  C3xy'z' 
    -y, z,-x  C23xy'z'
     z, x, y  C3xyz 
     y, z, x  C23xyz
     x,-z, y  C4x 
     x, z,-y  C34x
     z, y,-x  C4y 
    -z, y, x  C34y
    -y, x, z  C4z 
     y,-x, z  C34z
     y, x,-z  C2xy 
    -y,-x,-z  C2xy' 
     z,-y, x  C2xz 
    -z,-y,-x  C2xz' 
    -x, z, y  C2yz 
    -x,-z,-y  C2yz' 
     y, x, z  σd_xy 
    -y,-x, z  σd_xy' 
     z, y, x  σd_xz 
    -z, y,-x  σd_xz' 
     x, z, y  σd_yz 
     x,-z,-y  σd_yz' 
    -x,-z, y  S4x 
    -x, z,-y  S34x
     z,-y,-x  S4y 
    -z,-y, x  S34y
    -y, x,-z  S4z 
     y,-x,-z  S34z
    -x,-y,-z  i  
    -x, y, z  σh_x 
     x,-y, z  σh_y 
     x, y,-z  σh_z 
    -y, z, x  S6x'y'z 
     z,-x, y  S56x'y'z
     y, z,-x  S6x'yz' 
    -z, x, y  S56x'yz'
     y,-z, x  S6xy'z' 
     z, x,-y  S56xy'z'
    -y,-z,-x  S6xyz 
    -z,-x,-y  S56xyz
)

I assigned the Schoenflies symbols to the groups by hand and I hope they are all done correctly. The group elements are identified two ways, with a transformation of the x,y,z axes and with a Schoenflies symbol. For example, -z,-x, y C3xy'z' designates a three fold rotation about the ( 1,-1,-1) axis vector, i.e. the axis going through the RDB corner position. This places the neg. z axis in the x axis position, the neg. x axis in the y position and the y axis in the z position. For another, C2xy is a two fold rotation about the vector ( 1, 1, 0 ) or the axis going through the UR edge position.

For the symmetry planes the subscript gives the vector perpendicular to the plane. σh_x is the plane perpendicular to the x axis.

The h subscript designates a plane perpendicular to a principal axis while d designates a plane containing one C4 axis and bisecting the angle made by the other two C4 axes. These designations are appropriate for the Oh group but not necessarily for the subgroups. Often an Oh h (horz) plane will be a v (vert) plane for a particular subgroup and so forth.

Note that there are a number cases where two or more classes have members belonging to the same point group and thus have the same Schoenflies symbol. How one would go about devising a scheme for indexing a database such as your Symm tables that would allow you to access the appropriate one is of course implementation dependent. I don't see how a standard naming convention would be called for. Personally, if I need a particular symmetry I generate it on the fly. If I need say a D4h symmetry group to use with the < U , D , R2 , L2 , F2 , B2 > group: 
  symGroup = [cubicGroup subgroupFromGenerators:
                [NSSet setWithObjects:
                  [cubicGroup elementNamed: @" z, y,-x"], // C4y
                  [cubicGroup elementNamed: @"-x,-y, z"], // C2z
                  [cubicGroup elementNamed: @"-x,-y,-z"], // i
                  nil]];
» login or register to post comments

My model for the 98 symmetry

Submitted by Jerry Bryan on Mon, 07/22/2013 - 11:00.
My model for the 98 symmetry groups and 33 symmetry classes of M may be found at http://cubezzz.dyndns.org/drupal/?q=node/view/74 I have spot checked but not detail checked, and your model seems to be equivalent to mine. I assigned Schoenflies symbols to my model by using the Schoenflies symbols from Herbert Kociemba's Cube Explorer. I didn't try to figure them out myself.

My programs have never generated symmetries on the fly. I generated symmetry group tables and symmetry class tables by hand many years ago and have copied them from program to program ever since. After I created the tables, I did do a considerable amount of programmatic validation, doing things like writing a program to assure that symmetries assigned manually to each group did include closure within the group, etc.

Jerry
» login or register to post comments

Cubic Symmetry

Submitted by B MacKenzie on Mon, 07/22/2013 - 16:24.

Boy, hand coding the symmetry elements must have been an arduous task. In my class CubicSymmetryGroup I begin by forming all permutations of the x,y,z coordinate axes. This gives 3! * 23 = 48 mappings both parallel and anti–parallel. These permutations are represented as 3 x 3 matrixes. These matrixes are a representation of the Oh group under the operation of matrix multiplication. Moreover, the matrixes are the actions of the symmetry elements on a point, again through the operation of matrix multiplication. So if you define the positions of the cubies with x,y,z points centered on the origin one may derive symmetry permutations for the cubies by multiplying their positions by the symmetry matrixes and seeing to which cubicle each cubie is moved. So, as you may gather I tend to start small and build things up.

It should certainly be possible to assign Schoenflies symbols to the above groups programmatically. Back in school (some forty years distant now) when I was introduced to point group symmetry the Prof handed out a flow chart which went something like:

1. Does it have multiple high order rotation axes?
   1. Yes. It's a platonic solids group: T, O, I etc.
   2. No. Does it have any proper or improper rotation axes?
      1. Yes Is the highest order improper axis of higher order than any proper axis?
         1. Yes.  The group is Sn.
         2  No. Does it have C2 axes perpendicular to the highest order (principal) axis?
            1. Yes.  Does it have a plane of symmetry perpendicular to the principal axis?
               1. Yes.  The group is Dnh.
               2. NO. Does it have any vertical planes of symmetry?
                  1. Yes. The group is Dnv.
                  2. No. The group is Dn.
            2. No.  Does it have a horizontal plane of symmetry?
               1. Yes.  The group is Cnh
               2. No.  Does it have any vertical planes of symmetry?
                  1. Yes. the group is Cnv.
                  2. No. The group is Cn
      2. No. Does it have a plane of symmetry?
         1. Yes. The group is Cs.
         2. NO. Does it have inversion symmetry?
            1. Yes. The group is Ci
            2. No. The group is C1

Such a scheme wouldn't be that hard to code I think.

» login or register to post comments

Truly it was arduous. I ac

Submitted by Jerry Bryan on Tue, 07/23/2013 - 10:52.
Truly it was arduous.

I actually cheated in one respect. I got the tables for the 24 rotations exactly right, then I got one reflection exactly right. Having gotten one reflection exactly right, I wrote a little test program that just multiplied the one reflection by each of the 24 rotations to create all 24 of the reflections. The little test program wrote the 24 reflections to a file in a format acceptable as an initialization statement in C/C++, and I then copied the 24 reflections back into my source code.

I think most people writing Rubik's cube programs represent a position with four indexes - one index for the positions of the corner cubies, one index for the twists of the corner cubies, one index for the positions of the edge cubies, and one index for the flips of the edge cubies. Mathematically, this is a wreath product for the corners, a wreath product for the edges, and a direct product combining the corners with the edges. Essentially what you have is (S8 wr C3) × (S12 wr C2). The Cube group is a subgroup of this model group.

I've always done it a little differently. I model each individual color tab, 24 color tabs for the corners and 24 color tabs for the edges, with a direct product combining the corners with the edges. Mathematically, the model is S24 × S24 with the Cube group being a subgroup of this model group. I do save memory by storing only one color tab for each cubie, and in addition to saving memory the process of storing only one color tab for each cubie has the effect of encoding the twist state for the corners and the flip state for the edges. So I can treat my model as a wreath product model anytime it is computationally advantageous to do so.

Nevertheless, I think an actual wreath product model is much more efficient than my model in most respects. But I spend a lot of time thinking about producing permutations in lexicographic order, and I find it much easier to think about lexicographic order with the S24 × S24 model.

All of which is a long way of saying that I had to hand code the symmetries on a color tab by color tab basis. Having done so, I had to hand code the symmetry group and symmetry class tables. Truly arduous.

Jerry
» login or register to post comments

Representations

Submitted by B MacKenzie on Tue, 07/23/2013 - 15:05.

You're a better man than I. I couldn't have done that. In the first cube simulation I wrote I hand coded the matrixes for the C4 rotations and felt hard pressed.

I'm not very clear on what you mean by "producing permutations in lexicographic order". I have taken it to mean you have a slick way of representing cube states which allows you to do breath first states at depth calculations very efficiently but I don't have a good idea of what exactly is involved.

My own representation of a cube state does not separate position from orientation. A q-turn applies a C4 rotation to the cubies on that face. In a scrambled cube the position and orientation of each cubie will be the product of a series of C4 rotations, i.e. an element of the O point group. So the state of the cube may be specified by assigning an O group element to each cubie. The composition of two cube states is straightforward so this is the basis of a robust representation of the Rubik's cube group.

There are situations where it is advantageous to split up position from orientation. Particularly, a move table for the combined representation might be too large and it becomes necessary to have a position perm move table and an orientation move table. Here I have encountered problems with applying symmetries to the orientation representation. Flip isn't a problem if the symmetrical definition of flip is used. In this definition flipped edge cubies require an odd number of q-turns to return to the identity state and un-flipped cubies require and even number of q-turns. When I tried to do the split with a corner cubie representation I couldn't get it to work right. The trouble is that the definition of twist introduces a preferred direction which makes symmetry operations on the twist representation more complicated. I have thought that there must be a way of specifying corner cubie orientation which doesn't rely on a reference direction but as yet I haven't come up with one.

» login or register to post comments

> I'm not very clear on what

Submitted by Jerry Bryan on Tue, 07/23/2013 - 20:34.
> I'm not very clear on what you mean by "producing permutations in lexicographic order".

Consider S3, the group of 6 permutations on the set {1,2,3}. These 6 permutations may be represented with a number of different notations as follows: 

Cycle Notation           Cycle Notation       Two Row     One Row
  without              explicitly listing     Notation   Notatioin
explicitly listing       the fixed points
 the fixed points

------------------------------------------------------------------

   ()                      (1)(2)(3)          (1 2 3)      (1 2 3)
                                              (1 2 3)

------------------------------------------------------------------

  (2,3)                      (1)(2,3)         (1 2 3)      (1 3 2)
                                              (1 3 2)

------------------------------------------------------------------

  (1,2)                      (1,2)(3)         (1 2 3)      (2 1 3)
                                              (2 1 3)

------------------------------------------------------------------

  (1,2,3)                    (1,2,3)          (1 2 3)      (2 3 1)
                                              (2 3 1)

------------------------------------------------------------------

  (1,3,2)                    (1,3,2)          (1 2 3)      (3 1 2)
                                              (3 1 2)
------------------------------------------------------------------

   (1,3)                     (1,3)(2)         (1 2 3)     (3 2 1)
                                              (3 2 1)

------------------------------------------------------------------
The one row notation is the notation I tend to see least often in the literature, but it's the notation that's usually most useful to me. The way I have written S3, if you read the one row notation column top to bottom, it's in lexicographic order. Think of the digits 1, 2, and 3 as "letters" from an "alphabet" with 1 coming before 2 which comes before 3. The six permutations are in "alphabetic" order. Indeed, I often think in terms of letters from the actual English alphabet. If I write S3 in terms of the alphabet {A,B,C} and in alphabetic order, I get the following which is exactly the same as the one row notation column above. 
  ABC
  ACB
  BAC
  BCA
  CAB
  CBA
The fundamental problem in enumerating cube space is duplicate positions, that is, positions that can be effected by more than one minimal maneuver. To detect and eliminate duplicate positions, the positions usually have to be stored. But if the duplicate positions can be generated in lexicographic order, they don't really have to be stored other then the current one and the previous one. Lexicographic order is the term usually applied to a more general alphabet of any set of symbols provided only that those symbols can be ordered as first symbol, second symbol, etc.

As an example of how lexicographic order avoids storing all the positions, suppose I have the following list of "words" from the alphabet {A,B,C}. 

ABC
ACB
BCA
BCA
CBA
There are five items in the list, but only four distinct items in the list because BCA is duplicate. I've written out the whole list, but in practice you only produce one list item at a time and don't store any of them except for the previous one. The program operation might be something like the following. Even though once again I'm displaying a list where you can see all the items at the same time, remember that my program only is processing and storing one previous and one current position at any one particular point in time. 
        previous        current

          (null)          ABC        count it
           ABC            ACB        count it
           ACB            BCA        count it
           BCA            BCA        don't count it
           BCA            CBA        count it
           CBA            (end)      don't count it (and stop)
Jerry
» login or register to post comments

So, can I take it to mean tha

Submitted by B MacKenzie on Wed, 07/24/2013 - 11:56.
So, can I take it to mean that in a systematic exploration of the Cayley graph by composing all combinations of 2 turns, then all combinations of 3 turns etc., you can tell by the lexigraphical order of a product whether you have produced a new node or reproduced a node at lesser depth?
» login or register to post comments

Basically, yes. The algori

Submitted by Jerry Bryan on Thu, 07/25/2013 - 21:54.
Basically, yes.

The algorithm does require a certain about of composing and storing of all permutations of 1 turn, 2 turns, 3 turns, etc. for a certain number of turns as a part of an initialization process. For example, suppose you have composed and stored all positions out to a distance of 6 turns from Start the old fashioned way.

Let Si be all the positions that are i turns from Start and let Tj be all the positions that are k turns from Start. Store all the positions in arrays called S0, S1, S2, S3, S4, S5, or S6 as appropriate, and make sure they are stored in lexicographic order within each Si. For positions of length 1 turn through 6 turns, store all the same positions a second time in arrays called T1, T2, T3, T4, T5, or T6 as appropriate. It turns out that the permutations within each Tj do not have to be stored in any particular order.

You might nor might not actually store each position twice as indicated because Si and Ti are the same set. But the algorithm requires certain data structures for S and certain data structures for T, and the data structures are not the same.

Now suppose that you calculate all products st in lexicographic order where s is S6 and t is in T1. All such products st will be of length 5 turns, 6 turns, or 7 turns. Because the products st are in lexicographic order and because the elements of S5 are in lexicographic order, it's easy to discard all products st that match an element of S5. Because the products st are in lexicographic order and because the elements of S6 are in lexicographic order, it's easy to discard all products st that match an element of S6. Having discarded all the products st that are of length 5 turns or 6 turns, all remaining products st will be of length 7 turns. Some of the products st may be duplicate, but because they are being produced in lexicographic order it's easy to eliminate the duplicates. All that remain are all the distinct permutations of length 7 turns. They don't have to be stored anywhere. They only have to be counted.

Next suppose that you calculate all products st in lexicographic order where s is S6 and t is in T1 and also where t is in T2. Such products will be of length 4 turns, 5 turns, 6 turns, 7 turns, or 8 turns. As before, discard all products st that match an element of S4, S5, or S6. The remaining products will all be of length 7 turns or 8 turns. In particular, some of the products where s is of length 6 turns and t is of length 2 turns may actually be of length 7 turns. If so, then there will be some other s* in S6 and some other t* in T1 such that (s*)(t*) matches st. (s*)(t*) and st will appear subsequent to each other in lexicographic order, and the process is arranged so that (s*)(t*) - the shorter of the two - will always appear before st. So it's easy to discard this particular st at the same time that duplicate positions are being eliminated. The surviving positions are all the positions that are 7 turns from Start and 8 turns from Start, respectively. Such positions only have to be counted and not stored.

If you were going to run the program for T1 and T2, then you wouldn't bother to run it just for T1. If you were going to run the program for T1, T2, and T3, then you wouldn't bother to run it just for T1 and T2. Etc. Normally, I would try to run it all the way out through T6 to count all positions out through 12 turns from Start as long as I thought the program wasn't going to run too long.

Some optimizations are possible in the quarter turn metric. For example, the product st where s is in S6 and t is in T1 may only be of length 5 turns or 7 turns in the quarter turn metric whereas the product may be length 5 turns or 6 turns or 7 turns in the face turn metric. But the algorithm as described will produce correct results in both metrics.

Jerry

» login or register to post comments

That's neat. You still need

Submitted by B MacKenzie on Fri, 07/26/2013 - 10:36.
That's neat. You still need to store previously solved states but only out to half of the target depth. So your technique effectively doubles the depth one can take a breath first evaluation before memory is exhausted.
» login or register to post comments

Correction

Submitted by B MacKenzie on Tue, 07/23/2013 - 08:33.

The above flow chart doesn't handle the Sn point groups properly. It should be emended as follows:

1. Does it have multiple high order rotation axes?
   1. Yes. It's a platonic solids group: T, O, I etc.
   2. No. Does it have any proper rotation axes?
      1. Yes. Are all rotation elements the consequence of an improper axis? i.e. S26 = C3
         1. Yes.  The group is Sn.
         2  No. Does it have C2 axes perpendicular to the highest order (principal) axis?
            1. Yes.  Does it have a plane of symmetry perpendicular to the principal axis?
               1. Yes.  The group is Dnh.
               2. NO. Does it have any vertical planes of symmetry?
                  1. Yes. The group is Dnv.
                  2. No. The group is Dn.
            2. No.  Does it have a horizontal plane of symmetry?
               1. Yes.  The group is Cnh
               2. No.  Does it have any vertical planes of symmetry?
                  1. Yes. the group is Cnv.
                  2. No. The group is Cn
      2. No. Does it have a plane of symmetry?
         1. Yes. The group is Cs.
         2. NO. Does it have inversion symmetry?
            1. Yes. The group is Ci
            2. No. The group is C1
» login or register to post comments

Good point, Jerry. Thanks fo

Submitted by B MacKenzie on Fri, 03/08/2013 - 15:45.
Good point, Jerry. Thanks for clarifying that issue.
» login or register to post comments