# Two Face Group

Has the Rubik cube subgroup generated by the turns of two orthogonal faces been exhaustively expanded? My computer runs out of physical memory and bogs down after 18 q turns:

```Shell         Classes        Elements

0             1              1
1             1              4
2             3              10
3             6              24
4             15             58
5             35             140
6             85             338
7             204            816
8             493            1970
9             1189           4756
10            2863           11448
11            6862           27448
12            16324          65260
13            38550          154192
14            90192          360692
15            206898         827540
16            462893         1851345
17            992268         3968840
18            1973209        7891990

Totals        3792091        15166872

```

I calculate the order of the group as:

( 5! x 35 ) x 7! / 2 = 73,483,200

Extrapolating the above data using an exponential factor of 2 exceeds this order by 21 q turns, so the curve must max out and begin to descend by 21 q turns. Experimentally, using a forward/backward envelope search strategy I've solved hundreds of thousands of random group elements and have not found any requiring more than 24 q turns. I suspect that 26 q turns should be sufficient to solve any element but would like to be sure.

## Comment viewing options

### number for each class matches

In cube-mail-13 Jerry wrote about W-conjugate classes. Your numbers for classes matched his up to shell (level) 18.

Mark

### Symmetry

Had a look at cube-mail-13. Interesting to see symmetry discussed in a different context. As a chemist all my formal exposure to group theory was in connection with point group symmetry. W group? Heck, that's C2v. Same symmetry as a water molecule.

### < U, R > God's Algorithm

Yes, it's been calculated by Jerry Bryan and others.

Posted on Sept 1, 1994 on the original cube-lovers list. You can click on the leminscate on the right and see this result and others but not everything is in there yet. 25 q moves for the antipodal positions. It might be easier to use the html 'pre' tag then you can just use white space in a table (I see a lot of blank lines on my browser for your entry). You got the same answer as the rest of us: 73,483,200 elements in this group.

Mark

### I also posted <U,R> in

I also posted <U,R> in the face turn metric to Cube Lovers in 1994. The diameter in the face turn metric is 20f.

Back then, I solved the problem by writing the positions to an external file and sorting the file to identify duplicate positions. I wouldn't do it that way today. Instead, I would create a table with 73,483,200 elements to store the distance for each position.

Modern computers can easily accommodate such a table. Doing it in the most straightforward way, you would have one byte per position to store the length. With only slightly more work, you could store the information about each position in only two bits by storing the length mod 3. That would get the size of the table down to 18370800 bytes. If you add symmetry to the mix, you could cut the size of the table by another factor of about 4, and if you add antisymmetry to the mix you could cut the size of the table by another factor of about 2.

### Representing a group element as an integer

In the context of my program, a group state is encoded using one byte per cubelet with I don’t know how much overhead as each state is wrapped as an objective C class. Not the most memory efficient way of doing it certainly.

How would one encode a group element as a single integer? Something like N modulo 120 for the corner position permutation, ( N / 120 ) modulo 3 for corner #1 twist , etc?

### You don't actually code each

You don't actually code each group element as a single integer, exactly. Rather, you create a bijection between the group elements and the numbers from 1 to n (or sometimes from 0 to n-1), where n is the order of the group. The way I would create a bijection for S3 (for example) would be
```0: (0 1 2)
1: (0 2 1)
2: (1 0 2)
3: (1 2 0)
4: (2 0 1)
5: (2 1 0)
```
Here, I have shown the bijection in tabular form. An actual bijection in a program for a much larger group than S3 would involve some multiplying and dividing and some mixed base arithmetic.

I think most people use the Sims algorithm instead, which creates a similar (but not identical) bijection. However, the bijection induced by the Sims algorithm does not place the permuations in lexicographic order, and I prefer lexicographic order.

The bijection for S3 (or for any Sn) is "extremely symmetrical", or one might even say "completely symmetrical". Cube groups are not quite as symmetrical as Sn. As examples of this "lack of complete symmetry", bijections for cube groups must explicitly (or implicitly via the Sims algorithm) take into account such things as preservation of total twist, preservation of total flip, and preservation of parity between corners and edges.

But the bottom line with this idea is that you don't really store a bunch of positions in memory. In fact, your program typically never has more than one position stored in memory at a time. Instead, it stores the distance from Start associated with each position - often at one byte per position. And the table of lengths is indexed via the bijection between positions and the numbers from 1 to n (or from 0 to n-1).

Things get a little more complicated when symmetry and antisymmetry are added to the mix. I tend to operate with representative elements of M-conjugacy classes (which are equivalence classes). Doing it this way can make indexing rather awkward to deal with because representative elements are badly behaved. I think most people use symmetry coordinates rather than representative elements. Symmetry coordinates make indexing much easier to deal with than do representative elements.

### Group representations

Yes, a "bijection between the group elements and the numbers from 1 to n " is what I was talking about in my untutored way. One must have a scheme whereby one numbers the group elements leaving no gaps. Furthermore, one must have a scheme for converting that number back to a fuller representation of the group element. The particulars of that scheme are dependent on the group and how that group is represented.

I gather that the usual way group elements are represented is as a permutation of the facelets. When you start talking about these permutations in terms of abstract groups you've gone beyond my depth. I know little of these groups beyond symmetry point groups and that in terms of Schoenflies notation.

I represent the group differently. I represent each individual cubelet with a 3 x 3 transformation matrix describing how it has been moved from its home position. This has the advantage of tying in directly with the Open GL engine which makes extensive use of transformation matrixes for rendering 3D objects to the display. One further advantage is that the transformation matrixes may be further abstracted as elements of the cubic pure rotational group ( Schoenflies group O ; the C abstract group? -- the group generated by 900 rotations about the coordinate axes). So my representation of a Rubik group element essentially consists of a list of 20 integers between 0 and 23 representing the O group element for each cubelets rotational state. Multiplication of two group elements then consists of looking up 20 products in the O group multiplication table, one for each cubelet position.

So how would one derive an index from my representation? Extracting the corner and edge position permutations from my representation is straightforward. I presume there are schemes for indexing these groups. Corner and edge orientation are given by the rotational state. It could be done. It could be coded as a multidimensional array: distance[ edgePermIndex ][ cornerPermIndex ][ flip1][flip2]. . . [twist1][twist2] . . . Let the compiler take care of the arithmetic.

Not that I'm particularly interested in doing so. I wanted to know the diameter of UF group because I have a Rubik cube solution algorithm which ends with a brute force solution of that group. Twenty five q turns is no problem. Here's another question for you. What is the maximum depth one would need to search from an arbitrary member of the UFR group before finding a member of the UF group? So far I've found 14 q turns to be sufficient. 16 q turns is accessible, 17 might be a problem.

### Bijection

I don't know exactly how a bijection would work with your group representation, but it has to work about the same no matter which group model you use. I'll use the corners only group as an example. I'll use a cubicle based model rather than a cubie based model (it can be done equally well either way).

Consider the flu cubicle. It can contain a cubie in any one of 24 different ways. For example, it can include the flu cubie as flu, as luf, and as ufl (representing the three diffent twists). Similarly, the flu cubicle can contain the fur cubie as fur, as urf, or as rfu (again representing the three different twists).

The corners group has exactly 88179840 elements. Of those 88179840 elements, exactly 1/24, or 3674160 elements, correspond to each of the 24 possible contents of the flu cubicle. The fact that the numbers work out "exactly" in this manner is a consequence of several of the basic group theory theorems about the sizes of subgroups and cosets. So you will need to find a way to number the 24 different possibilities for the flu cubicle from 1 to 24 (or from 0 to 23), and to use those numbers to index yourself into the first 24th, the second 24th, ... through the twenty-fourth 24th of the 88179840 elements. It's a bijection, so you will need to be able to go both directions.

Having determined the contents of the flu cubicle (an arbitrary choice, but you do have to pick one), you pick a second cubicle, say the fur cubicle. There are now 21 possibilities for the contents of the fur cubicle. You need to find a way to number those possibilities from 1 to 21 (or from 0 to 20). Those 21 possibilities will divide the remaining 3674160 elements into exactly 21 equal parts. Use your number to determine if you are in the first 21st part, the second 21st part, etc. as before.

Continue with each cubicle, and be sure you have an algorithm to go in both directions so that you have a bijection. In one direction, you will be doing a lot of multiplying, and in the other directon you will be doing a lot of dividing. As you go through the cubicles, you will find that there are 18 choices for the third cubicle, 15 for the fourth, 12 for the fifth, 9 for the sixth, 6 for the seventh, and 1 for the eighth.

And in answer to one of your questions, yes it's fairly conventional to number the color tabs of the cube, say from 1 to 54. Then, as moves are performed (typically, but not always, the moves are quarter turns or half turns), and as symmetry operations are performed, you simply keep up with where all the numbers go. And typically, rather than keeping the numbers in some sort of two or three dimensional array, they are simply kept in one long singly dimensioned array.

I don't know how much group theory is taught to chemists and physicists when they are dealing with (for example) the symmetries of a water molecule. A group is quite abstract, and different groups can at least superficially look very different even though in reality they are very similar groups.

The basic concept is that you have a non-empty set and a binary operation on the set that combines two elements of the set to form a third element of the set. The binary operation is usually written in group theory as something like z=xy, where x and y are the elements that are being combined to form the element z.

This notation is exactly like the notation for multiplication in algebra and calculus, and it is usually called "multiplication". However, the abstract "multiplication" in group theory often has nothing to do with multiplication in the every day sense of the word. Sometimes, I just wish it was called "combining".

In the case of your water molecule, the point symmetry group consists of a set of point symmetries. The "combining" operation is really just "followed by". So the equation z=xy in this context would mean to apply the point symmetry x to the molecule, followed by applying the point symmetry y to the molecule. The result will be the same as applying the point symmetry z to the molecule.

### Re: Bijection

I just thought I would discuss my general approach to representing the 3x3x3 cube, and sub-problems of it.

There was some mention of numbering the facelets, and represent the cube as a permutation of the facelets. With GAP, that is how you generally define the cube. Basically, in GAP, you define a set of basic moves, such as U, F, etc., in terms of how those moves permute the facelets. Then, the function Group(U,F) will automatically generate the group with U and F as generators. The expression Size(Group(U,F)) will return the size of the group.

But when I use C++, I usually use a cubie-level model, where I use an array for each type of piece (corners and edges for 3x3x3), with each array element having a number that represents the cubie occupying a given cubicle, or (especially when I care about the location of a subset of the cubies) a number representing the cubicle and orientation of a given cubie. I generally use this cubie-level model to build a "coordinate model" where I have a few integers representing the information instead of arrays.

For example, for the full cube group, I would have an integer for corner permutation from 0 to 8!-1, another integer for edge permutation (0 to (12!/2)-1), another integer for corner orientation (0 to 2187-1), and another integer for edge orientation (0 to 2048-1). Theoretically, you could combine these numbers into single number in the range 0 to 43252003274489855999, mapping each value in the range to a unique element of the cube group. Note that the range of the edge permutation number is only half the size needed to represent every edge permutation. The parity of the corner permutation must be determined before you can map the edge permutation number to the correct permutation of the edge cubies.

For permutation, I use a routine essentially the same as the perm_n_pack routine in Mike Reid's optimal solver. This represents the permutation in a sort of mixed radix fashion, with the least significant "digit" having 2 possible values, the next "digit" having 3 possible values, and so on. This routine maps the numbers in ascending order to the lexicographic order Jerry Bryan described. Another routine, perm_n_unpack, does the reverse mapping. Note these routines are designed for arrays holding permutation information only, whereas I store both permutation and orientation information. So I may need to make use of temporary arrays where the orientation information is left out.

Note that the least signifcant "digit" in this mixed radix number is either 0 or 1, and if you change the value of just that digit you swap two cubies (more precisely, the cubies in the last two cubicles, if using the cubicle-based representation). This means that the permutation parity changes between odd and even. Since (for the 3x3x3) the corner permutation parity and the edge permutation parity must be the same, the parity information for one of them is redundant. Thus, you can remove the least significant bit of one of the permutation values (such as I did for the edge permutation above). Reconstructing that bit is not so trivial. I generally create a lookup table (a large bit-vector) to generate it. Basically if you set the bit to 0, and the resulting permutation has the parity that matches the other parity, then you know that you have the correct permutation value. Otherwise, you need to set that bit to 1.

For cases when I care about the positions of a subset of the cubies, I created an extension of the perm_n_pack routine that works for m out of n cubies/items. When using a subset, the array elements (in the cubie level representation) represent cubies, and their values represent cube positions ("cubicles") where the cubies are located. Of course, I also created a routine for the reverse mapping.

Edge orientation and corner orientation can be thought of as represented by base 2 numbers for edges, and base 3 numbers for corners. For the full 3x3x3, you would only need 11 base 2 digits for edges, and 7 base 3 digits for corners. The digit values for the remaining edge and corner cubies can be reconstructed based on conserveration of flips/twists.

I usually use a sym-coordinate that takes the place of one or two of the coordinate values of the simple coordinate model discussed above. I generally now use antisymmetry, if applicable, in addition to the applicable cube symmetries for the problem being analyzed. The other coordinates are not affected. This means that there are some redundancies in this "coordinate space" in terms of the equivalence classes. When I determine a new position for the current distance (depth), I must either make sure I mark any other symmetrically equivalent positions, too; or I must make sure I always determine the representative, and only store distance values in the positions for the representative elements. Either way, the table is a little larger than it needs to be, but the amount of wasted space is generally fairly small.

For the <U, F> group, the edge orientation is irrelevant. All corner orientation configurations satisfying conservation of twists are possible, so that is straightforward. There are 7! permutations of the 7 movable edges, but only 6!/6 permutations of the 6 movable corners (and another factor of 2 reduction for matching parity with the edge parity). This makes creating a bijection a little more tricky. One possibility would be to just generate the set of all legal permutations of the corners, and build lookup tables that map between the 720 different values perm_n_pack can return (for n=6) to a number in the range of 0..119, and vice versa. Note that the even-parity and odd-parity cases should be mapped to the numbers in the 0..119 range in some reasonable way so that you can determine parity easily (such as by taking the value modulo 2, or by dividing by 60). The reverse mapping takes the parity and a number 0..59 and maps that back to a number in the range of 0..719 that perm_n_unpack can then use to generate the cubie-level permutation array.

### Chemists and Group Theory

Ok, I get the concept. If I needed to do it I think I could figure out a scheme.

Chemist’s are concerned with symmetry groups mainly in connection with quantum mechanics and molecular orbital theory. (As a synthetic organic chemist, I’m about as far away from the nuts and bolts of this as one can get as a chemist so I can’t speak too knowledgeably about it. Hopefully I can give you some idea about it without spouting total nonsense).

What chemists look at are the irreducible matrix representations for the symmetry group of a molecule. One representation may be based on how a point x,y,z is transformed by the group, another might be based on how the binary products xy , xz , yz are transformed by the group. Anyway, group theory provides a fundamental set of matrix representations, homomorphic with the point group, which are the essence of the shape of a molecule.

One can formulate quantum mechanical wave equations in matrix form. That matrix must be isomorphic with an irreducible representation of the symmetry group of the molecule it is describing or it’s no good. So group theory is very useful to quantum mechanicians in setting up their wave equations.

That done, knowing which symmetry group representation is the basis for the quantum mechanical description for an electron’s energy level then tells one a lot about how it will behave. Put an iron ion in an octahedral complex and the orbitals will go up or down in energy in a predictable way based on symmetry arguments. This shows up in the electronic spectrum. One can look at how the spectral lines are split and say, “Hey, that’s an octahedral complex.”

That’s the kind of games chemists play with group theory. I was exposed to the definition of what constitutes a group. Representation of groups under the rules of matrix multiplication. Conjugate classes, etc. How to determine which point group describes the symmetry of a particular molecule. Then how to extract information from the group character table about the characteristics of the irreducible group representations.

### Petrus method

There is a speedsolving method called the Petrus method that is similar to the method B MacKenzie describes.

In that method, the solver builds a 2x2x2 block with 1 corner and 3 edges (in relation to the appropriate centers). I believe that puts the cube into the <U, F, R> subgroup (or an isomorphism of it). Then that 2x2x2 is extended to a 3x2x2 block, followed by orienting the remaining edges. I was thinking that would put the cube into the <U, R> or equivalent subgroup, but I think it is a group that is a factor of six larger. Then, it completes a 3x3x2 block (two layers), keeping the remaining edges oriented, of course. Then, the final layer is completed in two or three steps. In extending the 2x2x2 block to 3x2x2, only U-, F-, and R-layer moves are made, and extending the 3x2x2 (after orienting edges) to a 3x3x2 is done using only U- and R-layer moves. But the method may temporarily break up completed blocks at other times.

See http://lar5.com/cube/index.html for details of the method.

I haven't done a God's Algorithm calculation of the coset space for moving from <U, F, R> into <U, R> (or <U, F>). The cube subgroups page of Jaap's Puzzle Page web site ( http://www.geocities.com/jaapsch/puzzles/subgroup.htm) lists the sizes of these and related subgroups. <U, F, R> has 170,659,735,142,400 elements, or 2,322,432 times the size of <U, R>. It seems to me that finding am efficient representation for a coset space of two nested groups like these is not a trivial task. By that I mean being able to come up with a mapping (bijection) between the coset elements and a range of integers. I've had to do that kind of thing in my five-stage 4x4x4 analyses.

### cosets

What you describe is essentially the search strategy I've implemented. I progress through subgroups: Rubik group --> UFR group --> UF group --> solved. The first step, solving a 2x2x2 corner, requires at most 9 q turns. The last step, solving the UF group, takes at most 25 q turns. The maximum for the UFR to UF step is at least 14 q turns and is probably 15 or 16 q turns. Gives a quick solution averaging a shade under 38 q turns. By applying the algorithm to each of the 24 different orientations of the cube, both for the recto and for the inverse, the average comes down to 32 q turns.

I took a crack at characterizing the cosets. I figured, perhaps incorrectly, that one could really trim the search tree because I reasoned that expanding from one member of a coset yields the same cosets as expanding from another. I dropped it when I realized that in order to be useful in a forward/backward search scheme you'd need to be dealing with a normal subgroup which the UF group is not. (Looking at what I just wrote, it could probably be made to work by matching right cosets from the goal state to left cosets from the random state. No matter, I don't think I had a workable characterization of the cosets anyway).

### Formatting Tables

I've been composing my messages in a word processor and then saving in HTML. The editor I used generates a lot of header info to format tables which this editor chokes on. Here's what I get with a different word processor. This OK?

 Shell Classes Elements 0 1 1 1 1 4 2 3 10 3 6 24 4 15 58 5 35 140 6 85 338 7 204 816 8 493 1970 9 1189 4756 10 2863 11448 11 6862 27448 12 16324 65260 13 38550 154192 14 90192 360692 15 206898 827540 16 462893 1851345 17 992268 3968840 18 1973209 7891990 TOTALS 3792091 15166872

### Looks Good

That method works much better with drupal.