C3v Three Face Group

Symmetry is an invariance. It is an operation which may be applied to a system which does not change the system. A mathematical group is invariant under the operation of element multiplication.

g * G = G

Multiply all elements of a group by any element of the group and you get the group back. Mathematical groups are in this sense self symmetric.

Mathematical groups may be partitioned into conjugacy classes. Pick a group element g and conjugate it with every element of the group to generate a conjugacy class: the set of elements which are conjugates of g. Pick and element not in the first conjugacy class and generate its conjugacy class. Continue until all group elements are placed in one class or another. Conjugacy classes are invariant wrt conjugation.

g' CLASS g = CLASS

Conjugate each member of a class with any group element and you get the class back. The conjugacy classes of a group point up a type of symmetrical structure of a group.

Around here people are interested in finding the shortest sequence of turns which will give a particular cube state and which cube states require the maximum number of turns. God's algorithm calculations if you will although the term might seem a bit presumptuous. In this context the symmetries of the Cayley graph for the group become of interest and gets one into a more everyday concept of symmetry--the symmetries of physical objects.

Staying with the three face group, the symmetries of a triangular pyramid are of interest. These symmetries are the geometric transforms which will map the points on the surface of a triangular pyramid back on itself. Rotate any point on the surface by 120° about an axis emerging from the apex and one arrives at another point on the pyramid. Likewise for a 240° rotation. The pyramid thus has two three-fold rotation symmetries. The pyramid also has three planes of symmetry which slice it in half. For any point on the pyramid, at the same distance on the other side of the plane is another point on the pyramid. Together with the identity transform these elements of symmetry form a mathematical group known as the C_3v symmetry point group in the terminology of Schoenflies.

These symmetries are significant for the three face group since the facelets of the three face group are arrayed in space in a manner which shares this symmetry. Rotate a facelet 120° about the three fold axis and one arrives at the location of another facelet. This produces a mapping of the facelets onto each other.

C3 := (1, 4, 17)(2, 3, 18)(5, 12, 19)(6, 11, 20)(7, 22, 10)(8, 21, 9);

The above permutation describes how the edge facelets are rearranged by a 120° rotation. Facelet no. 4 moves to the facelet no. 1 location and so forth. One may produce a group of facelet permutations in this manner which manifest the C_3v symmetry group in terms of the facelet representation of the three face group.

The neat thing about these symmetry transforms is that the set of face turn generators, FT = ( R R' U U' F F' ), is invariant under conjugations by these symmetry elements.

s' FT s = FT

In consequence of this (and I won't go into the details): 1. the three face group as a whole is invariant wrt C_3v symmetry conjugations, 2. given a turn sequence giving a state one may by performing a symmetry transform on each turn of the sequence produce a turn sequence which will give a symmetry conjugate of that state and 3. if a state is at a particular depth in the Cayley graph all its symmetry conjugates will also be at that depth.

So this is what people around here mean when talking about symmetry equivalence classes. The symmetries are the group of geometric transforms inherent in the physical layout of the puzzle generators.

My vote for 27 as the diameter of the three face group is an educated guess based on the trends shown by the states at depth distribution. If anything I would be less surprised if it were 26 than if it were 28. Twenty-eight is a far stretch in my opinion.

I'm curious - what are the values for the length 18 antipodes for the 3-face edge group expressed in terms of Singmaster generators U,F and R?.
Do they span more than one conjugacy class?
I'm interested in the cycle structure of these nine group elements.

Without a lot of difficulty I was able to add a couple lines of code to the depth table initialization and pull out the configurations for the nine turn 18 edge positions:

State 1: one of 6 conjugates
FL BU RU RB FR DR DB DL DF UF LU BL UFR URB UBL ULF DRF DFL DLB DBR
( (1, 19)(2, 20)(3, 6)(4, 5)(7, 22)(8, 21)(9, 17)(10, 18) )
R2 F' U' R F U R' F' R' U' R' F' U' F' U' R2 F' U R U F' R

State 2: one of 3 conjugates
UF RF DF LF UB RB DB DL RU LU RD BL UFR URB UBL ULF DRF DFL DLB DBR
( (3, 18)(4, 17)(5, 9)(6, 10)(7, 20)(8, 19)(11, 22)(12, 21) )
R2 U F' R2 U F' R' U R' F' U R' F U' F' R' F' U R' F' R U

The nine states reduce to two under C_3v symmetry. The first line above gives the configuration in Singmaster facelet permutation notation. If you are not familiar with this notation, it encodes a facelet permutation in which facelets and facelet slots are numbered in the order:

UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR

So looking at entry 1 above, the Front-Left cubie is in the Up-Front slot with the Front facelet in the up position, the Up-Back cubie is in the Up-Right slot with the Back facelet in the Up position and so forth.

The second line gives the configuration in disjoint cycle notation suitable for GAP. The facelet/facelet slots are number in the same order as the Singmaster identity configuration: The Up facelet of the Up-Front cubie is numbered 1 and so forth. From the GAP representation one may see that both positions are double double-edge swaps, curiously enough. Hopefully, the above gives you the information you were curious about. The turn sequences are the solutions for the edge position composed with the identity corner position and are not optimal for the edge position.

A slight clarification. All 9 are actually conjugates in the group as one may readily verify using Gap. Although visually they split into two distinct types.

U := ( 2, 5, 7, 4)(10,34,26,18);
F := (18,21,23,20)( 7,28,42,13);
R := (26,29,31,28)( 5,36,45,21);

G := Group(U,F,R);

g := R^2*F-1*U-1*R*F*U*R-1*F-1*R-1*U-1*R-1*F-1*U-1*F-1*U-1*R^2*F-1*U*R*U*F-1*R;

h := R^2*U*F-1*R^2*U*F-1*R-1*U*R-1*F-1*U*R-1*F*U-1*F-1*R-1*F-1*U*R-1*F-1*R*U;

IsConjugate(G,g,h);

Conjugates within the group but not symmetry conjugates. They may be converted one to the other by conjugations with other group elements. Two elements are conjugate if there exists a group element g such that

g' A g = B

For symmetry conjugates the conjugators are symmetry transforms which need not be and in the present case are not members of the group. The three fold rotations (as manifest as a facelet permutation) violate twist parity and of course the mirror plane elements have mirror image corner cubies. So conjugate classes and symmetry conjugate classes are two different things.

Woops, reading over the above it struck me that we are discussing the edges only three face group. The above paragraph doesn't apply and the three fold rotations are group elements. The mirror plane elements violate flip parity and are not group elements.

I played around with this in GAP. Here's a GAP session which might point up the distinction:

U := (1, 3, 5, 7)(2, 4, 6, 8);

F := (1, 20, 9, 18)(2, 19, 10, 17);

R := (3, 17, 11, 21)(4, 18, 12, 22);

UFR := Group(U,F,R);

Size (UFR);
92897280

C3 := (1, 4, 17)(2, 3, 18)(5, 12, 19)(6, 11, 20)(7, 22, 10)(8, 21, 9);

Sigma_v := (1, 3)(2, 4)(5, 7)(6, 8) (9, 11)(10, 12)(17, 18)(19, 22)(20, 21);

C3v := Group(C3,Sigma_v);

Size( C3v );
6

Antipode_1 := (1, 19)(2, 20)(3, 6)(4, 5)(7, 22)(8, 21)(9, 17)(10, 18);

Antipode_2 := (3, 18)(4, 17)(5, 9)(6, 10)(7, 20)(8, 19)(11, 22)(12, 21);

IsConjugate(C3v, Antipode_1, Antipode_2);
false

IsConjugate(UFR, Antipode_1, Antipode_2);
true

Antipode_3 := C3^2 * Antipode_1 * C3;
(1,8)(2,7)(3,6)(4,5)(9,21)(10,22)(11,18)(12,17)

IsConjugate(C3v, Antipode_1, Antipode_3);
true

I have never heard of orientation parity violating symmetries before, but you are right. Excluding three edge cubies and one corner cubie makes things totally different.

For algorithmic purposes, one can divide the cubies in groups of four in a natural manner, and with those groups after each other one would get something like
UL UR DR DL | UF UB DB DF | BL FL FR BR | UBL UFR DFL DBR | DBL DFR UFL UBR
This is not a convenient notation for real life, but neither is Michael Reid's Singmaster notation. I would suggest something like
UBL UL UFL UF UFR UR UBR | BL FL FR BR | DBL DL DFL DF DFR DR DBR

Yet another issue is that with writing down the corner cubies, you suggest to have solved the edge subgroup as a subset of the whole group. But you solved the corner subgroup coset group instead.

With regard to "Singmaster facelet permutation notation," I had tended to assume the "UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR" ordering originated from Mike Reid and his optimal solver program. Or had it been used prior to that? I am wondering why you are attributing it to Singmaster.

Certainly Singmaster referred to cubies in this way, and also used such representations in a cycle-style notation. But I'm not aware if he had anything to do with this particular ordering for representing a cube state.

A cursory search of the cube lovers archives indicates that you are probably right. I found a post by Longridge dated Jan. 1995 where he proposed a configuration convention based on Singmaster's cycle notation which would suggest that no such convention was in place at that time.

A widely used convention for symbolizing a cube state would be desirable for the electronic cubing community. I find it very convenient in my own work. I used three separate programs to prepare the above post: the three face coset solver to output the states, a three face solver to reduce the list of states by symmetry and generate the turn sequences, and a utility for converting cube states into a cycle notation which may be understood by GAP. Since all three programs accept the same conventional cube state configuration strings it was no problem.

So, the Singmaster-Reid convention to coin a term. Singmaster for the basic symbols and Reid for the standard order of the facelets.

I picked up the system from Kociemba's optimal cube solver where he referred to it as Singmaster notation in his docs. If Mike Reid deserves the honor, then I guess I owe him an apology.

Your observation that the three face corners only group is isomorphic with the 2 x 2 x 2 cube lights up a light bulb. A couple of years ago I got in a discussion with Jerry Bryan about symmetry reduction and the 2 x 2 x 2 cube. Jerry pointed out that the group could be reduced using full cubic symmetry after I opined that C_3v symmetry was all that could be used. Jerry was right and I was wrong. This brings up the possibility of using full cubic symmetry in my coset solver. On reflection I think in order to do so the edges group must also be reducible by full cubic symmetry which I don't think is the case.

I chose to solve corner group cosets because the edge group is deeper than the corner group and thus gives more effective pruning in an IDA algorithm. To solve a coset I look ever deeper for solutions to the defining edge position and mark off the resulting corner positions until all corner positions are found. In solving an edge position the effective pruning depth is 13 or 14 turns. Done the other way, the effective pruning depth for a corner position is only 11 or 12 turns.

The regimen you put forward seems to require more computing resources than I have at my disposal. My solver can enumerate an average coset in about 8 minutes. Running both cores in parallel and with twelve fold symmetry reduction my humble IMac could completely enumerate the group in something like 60 years. My techniques are probably fairly rudimentary. With more sophisticated techniques the intrinsic speed could probably be improved by at least an order of magnitude. So, I think with a supercomputer cluster or such like the group could be enumerated in a reasonable time.

Well, I was thinking about God's number and concluded that enumerating the three face group would probably take far less time. But some results are more wanted than others.

Still, I wonder how fast the enumeration method will be. You need a binary table of about 1.8 TBytes. Indeed, there are 170.659.735.142.400 positions, and with 6 symmetries, inverse reduction and 8 bits per byte, we get 1.777.705.574.400 bytes with perfect reductions. But a quaternary table of about 3.6 TBytes might be more efficient (you can code two levels L and L+1, as well as < L and > L+1) and can also be used for FTM. Thus you need one or two harddisks of 2T.

Yet, still, you can hope that you may borrow a faster computer with many cores and harddisks. Before that time comes, you can reduce the amount of harddisk space, other resources and time by a factor 256, by ignoring edge flip. Then you still have cosets of 1.837.080 positions, which are coded binary (229.635 Bytes) or quaternary (459.270 Bytes). There are only far fewer cosets.

By the way, I am thinking of implementing the void cube for solving the anti-symmetric positions. The void cube is a factor 12 smaller than the regular cube, since you can permute the centers in 12 ways. Hence, you can find 12 anti-symmetries at a time, but only 5/12 of the symmetries are actually anti-symmetries that do not imply symmetries (since they have order 1 or 2), thus a factor 5 remains. The void corner cube is a factor 24 smaller, since you can also permute the centers by RL' (i.e. turning the RL slice down). And you can perfectly do symmetry reduction on the void cube. Since the void corner cube is the 2x2x2, the 2x2x2 can be symmetry-reduced with 48 symmetries as well. The magic number 1152 is the product of 48 symmetries m and 24 center permutations c, just as in the discussion you mention.

My suggestion was to remove edge flip explicitly from the group <U,F,R>, but you can remove it implicitly by enumerating
<U²,F,R> instead.

Mulling over your posts, I think I'm getting a handle on what your getting at. If I understand you, what you want to do is to a straightforward expansion of the group tree. To do this you need to map the three face group sequentially to memory. You mark the identity element as "active" and the rest as "unsolved". You iterate through the group and apply the face turns to the active elements. If a product state is marked as "unsolved" you mark it as "next". The state you just applied the turns to is marked as "solved". Continue iterating through the group until all states are marked as solved. With each pass through the group you keep a count of the active states to give the count of the states at each depth.

This scheme requires two bits per position, 0 = unsolved, 1 = active , 2 = next , 3 = solved. This comes to 42,664,933,785,600 bytes of memory which of course means you're going to have to use virtual memory on disk. With an indexing scheme which organizes the list by coset you can break up the problem by coset. Each coset has 1,837,080 elements and takes up 459,270 bytes of memory. The addition of a turn to a coset member will give a product in one of only six cosets characterized by adding a turn to the defining edge position. So what you do is pull 7 cosets into memory, process the parent coset and write the 7 cosets back out to disk. So you only use some 3 MB of physical memory per thread. That's pretty neat. It seems very doable to me given sufficient disk space.

To employ symmetry reduction one would have to map the symmetry equivalence classes sequentially to memory. Frankly, this is something I've never figured out how to do. I've seen reference on this forum to indexing schemes employing a "sym coordinate" which I believe will accomplish this. Let's assume that such an indexing is possible and you can reduce 12 fold by symmetry while still keeping the list organized by coset. This comes to 3.6 T of disk storage which I suppose is fairly accessible.

What you explain is what I mean. There are maybe a few remarks.

With inverse reduction reduction, you need 12 moves instead of 6. This is because you must also apply moves on the other side, i.e. if G is a generator of a position P, then you must compute the positions of GR, GR', GL, etc., but also the positions of RG, R'G, GL, etc.

For QTM, it is possible to do it binary. At first, you do not distinguish between solved on one hand and active or next on the other, getting you at ternary. Thus you mark solved as either active or next in an arbitrary manner. This has additional costs in time, though. Next, it is the parent coset that you update, by processing its 6 or 12 child cosets only for the move that connect them to the parent. This way, you increase the level of a coset for the whole coset at one time, instead of in 6 or 12 times. You keep track of the level of the coset, after which parity will distinguish between active and next. The arbitrary way in which solved will be marked is also by parity.

If you are interested, then I can explain you what you must do for anti-symmetry reduction. Or maybe, I just write a tutorial about the theory of Rubik's cube. It can all be explained very simple, without using groups and cosets.

With anti-symmetry reduction, it is not possible to decompose the corner coordinate into positions and orientations. This makes that you get very large tables if you code all 24 basic moves for the corner coordinate (6 face turns, 6 `other side' face turns, 6 symmetries and 6 anti-symmetries). For that purpose, I recommend to use what Herbert Kociemba calls a symrep coordinate for the corner coordinate. With a symrep coordinate, the move tables reduce in size by a factor 12 due to the 12 (anti-)symmetries. For the edges, a symrep coordinate is not necessary if you ignore the 256 edge flips, but I recommend to implement it as well, to prepare for edge flip when you can borrow a large computer. So you have two coordinates. For the corner coordinate, you need a table to compute a normal coordinate without parity from a symrep coordinate: the index of the 1,837,080 quaternary digits of the coset. Parity must be removed from the corners because the edge coordinate already codes this.

OK, when you state "you need a table to compute a normal coordinate without parity from a symrep coordinate" this gives me a hint of how one implements a sym coordinate.

To reduce a group by symmetry one partitions the group into equivalence classes and selects one element from each class to represent the class. So, choose an element and compute the symmetry conjugates both for it and its inverse. For the Rubik's cube group and with my representation this yields a list of 96 twenty byte strings (or fewer for symmetric elements). I sort the strings using a byte by byte comparison and the highest ranking element is chosen as the representative element. (Actually, in practice I do it a bit more efficiently than that, but the above is equivalent to what I do.)

In my three face coset solver I use symmetry reduction at the edges group level. I iterate through the 92,897,280 elements of the edges group. For each element I test whether it is the representative element of its equivalence class and only solve the coset if it is, multiplying the results by the size of the equivalence class.

I now gather that a "sym coordinate" is simply an arbitrary sequential numbering of the equivalence classes. One constructs a table listing the representative elements for each equivalence class and a table listing the index in the first table for the equivalence class of each member of the group. One may go on from there to construct move tables, depth tables and what have you in terms of the sym coordinate. Is this the basic strategy?

Assume a coordinate has c positions and that there is a group of s symmetries and r representants, i.e. the coordinate has r orbits under conjugation with the symmetry group, and with perfect symmetry reduction, we would have c = s * r.

A symrep coordinate is an array indexed by [0..c-1] whose elements are in [0..s-1] x [0..r-1] (x denotes cartesian product). Thus the array elements are structures of a symmetry index sym and a representant index rep, and that is where the name symrep comes from. If a coordinate index coord maps to (sym, rep), then the coordinate indexed by coord can be obtained by conjugating the representant indexed by rep with the symmetry indexed by sym.

It seems convenient to choose sym as small as possible. Next, suppose you have the edge positions as a coordinate. Then c = 12!, and a table of 60 moves (12 quarter face turns + 48 symmetries) for all values of coord takes more memory than your computer has. However, to apply a move on a symrep coordinate, it suffices to store the 60 moves for the r representants only, i.e. about c/47 representants. Some additional tables about symmetries and possible face turns are needed, but such tables are very small.

In addition to having a move table for each representant, it is also convenient to have a table with indices of subgroups of the symmetry group of s elements (symmetry subgroup table): the index of the largest symmetry subgroup V such that conjugation with elements of V does not change the coordinate of r.

If you use inverse reduction additionally, then the set [0..s-1] is doubled to [0..2s-1] to code inversion as well. Notice that inverting commutes with symmetry conjugation. In addition to having a move table and the above-mentioned table with subgroup indices, it is convenient to have another table with subgroup indices (anti-symmetry subgroup table): the index of the largest symmetry subgroup V such that conjugation elements of V does either not change the coordinate of r, or changes the coordinate of r into its inverse.

What was standing here was not entirely correct, so I removed it. I will put here something correct later if no reaction has appeared by then to make that impossible.

Ok, we start with a group, say the C_3v three face edge group. We map the elements of this group onto the integers using the indexing scheme of your choice to give indexes 0 to 9! * 256 -1. We'll call this the element index.

Partitioning the group by symmetry equivalence class we may construct a table:

classPartition[ classIndex ][ symIndex ] = elementIndex

where classIndex numbers the equivalence classes 0 to N-1 where N is the number of equivalence classes and symIndex numbers the symmetry elements 0 to N-1 where N is the number of symmetries. Each row of the table lists the elements of an equivalence class (with redundancies in the case of symmetrical classes). The first column of this table (assuming symIndex 0 is identity) would then list what I term the representative element of each equivalence class.

Am I right in assuming the the selection of which class element is to represent the class is an arbitrary one? Any scheme which would allow one to unambiguously select the representative element such as the one I outlined above is sufficient. One might choose to designate the representative element as the member with the lowest element index, say, and it would work just as well. The method chosen is a matter of convenience. Also, the assignment of the class indexes to the classes is an arbitrary one. One might number them sequentially as they are first encountered iterating through the element indexes for example and that would work as well as any other scheme.

Or actually repsym. Indeed the representant is arbitrary. About the symmetry, it would be nice to take the smallest one.

Instead of storing two subgroups of the symmetry group S for each representant, it seems better to store a subgroup of the Cartesian product of S and C_2, the cyclic group of order two (with elements 1,-1). (1,1) in S x C_2 means doing nothing and (1,-1) in S x C_2 means inversion. The subgroup of S x C_2 that you store is the stabilizer of r, i.e. the set of elements (s,i) such that s^(-1) r^(1-2i) s = r.

When you read from or write to the quaternary or binary table (actually, a binary table in memory always suffices, if you have another table on disk that you update each level, the binary table indicating positions reached thus far), you do not need to apply symmetry reduction on the corner coordinate. You just replace the corner coordinate c by s c^(1-2i) s^(-1), where (r, (s,i)) is repsym coordinate that indicates the edge position.

But for updating counters, you need to know not only the stabilizer of the representant r of the edge coordinate, but also the stabilizer of the corner coordinate c, i.e. the set of elements (s,i) such that s^(-1) c^(1-2i) s = c. Then you can take the intersection of both stabilizers, to obtain the stabilizer of the whole coordinate (r,c).
Write G_i for the stabilizer of i and V for the intersection of G_r and G_c. V is the stabilizer of (r,c).

Number of reduced positions to count (mod M + inv): #V / #G_r
Number of reduced* positions to count ((mod M + inv)*): 1
Number of positions to count: #G_0 / #G_r

Notice that #V / #G_r does not need to be integral, but you can multiply the first and last counter by G_0 = 12 (or G_0 = 96 with 6 faces) to obtain integral calculations. Other counters can be obtained from the first or last counter and the structure of V.

Say that you have a disk table with entries solved, active, unsolved. When you extend the table one level, you mark in the binary memory table all positions that are one move from those marked active on the disk in the first sweep. During the second sweep, you change active to solved and make the unsolved that are marked in the binary memory table active, processing the new active entries for counting.

With forward extension, you run through all positions marked active in the first sweep to obtain new positions (up to level 22). With backward extension, you run through all positions marked unsolved in the first sweep to obtain new positions (level 23 and up).

Thank you for your help (and I have benefited a lot from this discussion), but if you will forgive me, you jump around too much. It's like I had asked a question about laying the foundations for a house and you set off to explain how to tile the roof and oh, by the way you should install electric heat rather than gas.

What was hanging me up was that I had the misconception that there was some clever way to index a group such that the symmetry equivalence classes would fall out of the list naturally. This prevented me from seeing the expedient, obvious in retrospect, of simply numbering them in an arbitrary manner. That out of the way, I feel confident that I can proceed to construct a sym reduced move table and pruning table and implement a sym reduced IDA search algorithm. I'll deal with the details and contingencies when and if I encounter them.

I'm not going to invest half a kilobuck in a 4T disk drive just to attempt an enumeration of the three face group. I'll leave that up to you. Perhaps I'll revisit my coset solver to see if I can get the 10 fold increase in speed I alluded to earlier. Anyway, thanks again for your input.