Symmetry of Cayley Graphs of Subgroups of the Cube Group G

Normally, we think of Rubik's cube symmetry in terms of a particular position x.  The symmetry of x can be defined as Symm(x), where Symm(x) is the set all symmetries m in M such that x^m=x, and where M is the group of 48 symmetries of the cube.  By the closure property, Symm(x) is a subgroup of M, and there are 98 possible such subgroups.  I wish to expand this definition of symmetry to encompass an entire subgroup of the Cube group G.

The primary motivation for the expanded definition is to provide a standard mechanism to deal with the symmetry of subgroups of the Cube group G such as H=<U,R>.  I'm probably going to make things more complicated than they need to be.  However, I don't recall seeing a general discussion of group symmetries before, neither on Cube-Lovers nor on this forum.

It seems to me that the notation G=<generators> is really used in two different ways.  First of all, it defines a group.  Secondly, it defines a Cayley graph for the group.  There is not a one-to-one correspondence between groups and Cayley graphs.  For example, we might generate the standard cube group either as G₁=<Q> or as G₂=<Q,H>, where Q is the set of 12 quarter turns and H is the set of 6 half turns.  G₁ and G₂ are the same group, but they do not have the same Cayley graph.  We would say that as a Cayley graph G₁ reflects distances between positions in the quarter turn metric, and that as a Cayley graph G₂ reflects distances between positions in the face turn metric.

It seems to me that therefore symmetry is not really a group property.  Rather, it is a property of a particular Cayley graph for a group.  Indeed, my first proposed definition for "group symmetry" for subgroups of the Cube group G is as follows.  Let H=<generators>, where the generators are elements of the Cube group G.  Then, Symm(H) is the set of all m in M such that H^m is a distance preserving automorphism of H.  Distance is a property of a Cayley graph, not a property of a group.  To the extent that this definition is correct, symmetry must be a property of the Cayley graph for the group, not a property of the group itself.  Also, we note that just as with the symmetry of a particular position, the closure property assures that Symm(H) is a subgroup of M.

When a group is defined by a specific list of generators such as H=<U,R>, it is nearly always taken that the inverses of the generators are taken to be included in the list of generators whether they are listed explicitly or not.  For example, H=<U,R> is taken to mean the same thing as H=<U,R,U^-1,R^-1>.  The distinction is meaningless when <U,R> is taken to define the group.  However, when <U,R> is taken to define a Cayley graph for the group, the distinction might make a difference.

For example, the arcs of a graph (usually the arcs are called edges, not to be confused with the edges of a Rubik's cube) can be directed (going in only one direction) or can be undirected (bidirectional, going in both directions).  Different authors handle the details of this particular issue in different ways.  For example, some authors use the word "graph" itself without any qualifying adjectives to indicate a structure in which all the arcs go in both directions.  And other authors use the word "graph" itself without any qualifying adjectives in a more generic fashion, and always include qualifying adjectives to indicate whether the arcs are directional or not.  For the very small subgroup <U>, if all the arcs of the Cayley graph are considered to go in both directions, then U³=U^-1 and the length of U³ is 1.  But if for <U> the arcs of the Cayley graph only go in one direction and if the inverse U^-1 is not automatically included in the list of generators, then the length of U³ is 3.  Indeed, in this case the (directed) Cayley graph does not even define a metric because the distance from Start to U³ is not the same as the distance from U³ to Start.  I am going to try to avoid any possible confusion by listing all inverses in the list of generators.

By analogy to the full cube group, we might describe H₁=<U,R,U^-1,R^-1> as denoting the subgroup in the quarter turn metric.  We would similarly denote the same subgroup in the face turn metric as H₂=<U,R,U^-1,R^-1,U²,R²>.  But what about H₃=<U,R,U^-1,R^-1,U²>? Well, H₁ and H₂ are the same subgroup and have the same symmetry as each other, but they have a different metric.  H₃ is also the same subgroup, but it has both a different symmetry and a different metric than H₁ and H₂.

The last example suggests a second and more useful definition for subgroup symmetry.  Let H=<g₁,g₂,...g_n>, where the generators are elements of the Cube group G.  Then, Symm(H) is the set of all m in M such that (g_k)^m is also a generator.  In other words, Symm(H) is the set of all m for which H^m preserves the set of generators.

It seems fairly straightforward that the two definitions are equivalent.  It is clearly necessary that a distance preserving automorphism preserve the set of generators.  That's because g^m must be in H for all g in the set of generators (otherwise H^m does not define an automorphism), and the length of g^m must be 1 for all g in the set of generators (otherwise H^m is not distance preserving).  It is also sufficient that the set of generators be preserved.  Consider for example an element x of H, and consider what happens to x under H^m.  If the length of x is n, then we may write x as (g_{i_1})(g_{i_2})...((g_{i_n}).  We therefore can write x^m as (g_{i_1})^m(g_{i_2})^m...((g_{i_n})^m. Because g^m is a generator for all g in the set of generators, x^m is in H and the length of x^m is the same as the length of x.

The fact that symmetry of the Cayley graph of a subgroup of the Cube group G can be defined in terms of the generators can be used in a program as follows.  Let Symm(H)=K where K is a subgroup of M, choose an x in H, and consider Symm(x).  We may calculate Symm(x) either as the set of all m in M such that x^m=x or as the set of all m in K such that x^m=x.  We will get the same answer either way, but clearly dealing with the set of all m in K will generally be much faster than dealing with the set of all m in M.  In the case of symmetry representatives, we don't have any options.  We must define y=Rep(x) as something like the minimum of x^m for all m in K.  If we considered all m in M, we might end up with a symmetry representative that is in G but that is not in H.  Similarly, given a symmetry representative y, we might want to calculate the entire equivalence class of positions that are equivalent under symmetry.  The equivalence class would have to be calculated as x^K rather than x^M, otherwise the equivalence class might include elements in G that are not in H.

The fact that symmetry of the Cayley graph of a subgroup of the Cube group G can be defined in terms of the generators means that the set of distance preserving automorphisms for the subgroup can be thought of as permutations on the generators.  For example, the symmetries of <U,R,U^-1,R^-1> can permute the generators as follows:

1. U->U,  R->R,  U^-1->U^-1,  R^-1->R^-1
2. U->R,  R->U,  U^-1->R^-1,  R^-1->U^-1
3. U->U^-1,  R->R^-1,  U^-1->U,  R^-1->R
4. U->R^-1,  R->U^-1,  U^-1->R,  R^-1->U

It might be pointed out that the symmetry of the entire cube group is the same in both the quarter turn metric and the face turn metric.  Namely, Symm(<Q>)=Symm(<Q,H>)=M.  In the face turn metric, all the distance preserving automorphisms map quarter turns to quarter turns and half turns to half turns.  However, because the Stuck Axle problem has long been solved, it has long been known that the entire cube group can be generated with moves of only five faces.  For example, the entire cube group can be generated as G₃=<F,B,L,R,U,F^-1,B^-1,L^-1,R^-1,U^-1>. Symm(G₃) is not the same as Symm(<Q>) or Symm(<Q,H>).

Finally, I would consider this discussion of symmetry and generators to apply to what I might call "extended face turns" as generators.  The extended face turns would include the quarter turns Q, the half turns H, the slice quarter turns such as RL^-1, the antislice quarter turns such as RL, and the slice/antislice half turns such as R²L² (slice half turns and antislice half turns cannot be distinquished from each other).  However, I would not consider this discussion to apply to what I might call true slice turns where one of the middle layers of the 3x3x3 cube is literally moved.  We normally do not model slice turns by literally moving the middle layers because moving the middle layers moves the face centers.  Rather, we model slice turns by moving opposite faces at the same time.  I think that symmetry considerations get a little more complicated if the face centers are allowed to move.