Date: Fri, 13 Aug 93 18:26:09 -0400 (EDT)
From: Dan Hoey <hoey@aic.nrl.navy.mil >
~~~ Subject: Re: Squares group

Mark Longridge <mark.longridge@canrem.com> has some interesting things
to say about the antipodes of the group generated by half-turns:

If we define "symmetry level" as the number of distinct patterns
generated by rotating the cube through it's 24 different
orientations in space then most known antipodes are symmetry level
6. Thus the lower the number the higher the level of symmetry. The
least symmetric positions have level 24, and this is very common.

This approach is somewhat unfortunate in two ways. First, it would be
better to use the full 48-element symmetry group M of the cube,
because some patterns are not recognized as transformed images of each
other if you only use the 24-element group C of rotations. For
instance, the positions reached by processes F2R2T2 and F2T2R2 cannot
be related with C, so you would see four classes of positions at
distance three rather than three. But the antipodes you give are all
mirror-symmetric, so there is no new coalescence there.

Relating processes that are conjugates by a reflection is usually
somewhat tricky, since the moves of the process must be changed in
direction (replacing clockwise by counterclockwise) but in the squares
group this is a nonproblem.

The second deficiency of your approach is that you lose information by
specifying only the index of the symmetry subgroup (the ``number of
distinct patterns generated ...''). It makes sense to find out
exactly which subgroup of M is the symmetry group of your positions.
I've done that, below. Each of these symmetry groups comes in three
conjugates, so I've transformed some of the processes (marked x) so
they all use the same particular symmetry group(s). The group
elements are given as cycles of the cube faces, so (TD)(FRBL) means to
reflect T<->D and rotate F->R->B->L->F.

Cases with symmetry level 6:

These are cases where the symmetry group has order 8.

```p66x  Double 4 corner sw  L2 D2 R2 T2 L2 T2 F2 R2 (F2 B2 T2 F2) T2 L2 B2
p80   2 DOT, Invert T's   R2 B2 D2 R2 B2 L2 B2 L2 (T2 D2 F2 T2) F2 L2 T2
p99   2 DOT, 4 ARM        R2 B2 D2 L2 B2 L2 F2 L2 (T2 D2 F2 T2) F2 L2 T2
p100  2 Cross, 4 ARCH 1   R2 B2 T2 R2 F2 L2 F2 L2 (T2 D2 F2 T2) F2 L2 T2
```
```p66x, p80, p99, and p100 have symmetry group P=<(TD)(FRBL),(FB),(LR)>.
```
```p67x  Antipode 2          R2 D2 B2 T2 B2 T2 F2 L2 (F2 B2 T2 F2) L2 F2 D2
p130  2 Cross, 4 ARCH 2   L2 B2 D2 B2 L2 D2 F2 L2 (T2 D2 F2 L2) F2 L2 T2
```
```p67x and p130 have symmetry group Q=<(TD),(FRBL)>.
```
```p135x 2 X, 4 T            D2 B2 L2 F2 R2 F2 R2 D2 (R2 L2 F2 R2) D2 L2 F2
p137  2 X, 4 ARM          L2 F2 T2 B2 T2 F2 T2 L2 (T2 D2 F2 T2) L2 D2 F2
```
```p135x and p137 have symmetry group S=<(TD),(FB)(LR),(FR)(BL)>.
```

Cases with symmetry level 12:

These have 4-element symmetry groups.

```p108  2 DOT, 2 T, 2 ARM   L2 F2 T2 R2 B2 L2 F2 L2 (T2 D2 F2 T2) F2 L2 T2
p128x 2 H, 2 T, 2 CRN     L2 D2 R2 T2 L2 T2 F2 R2 (F2 B2 T2 F2) T2 L2 F2
p129x 2 H, 2 T, 2 ARCH    R2 T2 L2 T2 L2 T2 F2 R2 (F2 B2 T2 F2) T2 L2 F2
p131x 2 H, 2 ARM, 2 ARCH  L2 T2 R2 B2 D2 L2 B2 L2 (F2 B2 T2 F2) T2 L2 T2
p132  2 Cross,2 ARCH,2CRN L2 F2 D2 R2 F2 L2 B2 L2 (T2 D2 F2 T2) F2 L2 D2
p136x 2 H, 2 ARM, 2 CRN   R2 T2 L2 F2 D2 L2 F2 L2 (F2 D2 T2 F2) T2 L2 D2
```
```p108, p128x, p129x, p131x, p132, and p136x have symmetry group
HP=<(FB),(LR)>.
```
```p133x 2 Cross, 2 T, 2 ARM L2 T2 B2 T2 B2 T2 F2 L2 (F2 B2 T2 F2) L2 F2 D2
p134x 2 CRN, 2 X, 2 ARCH  L2 T2 B2 D2 F2 T2 F2 L2 (F2 B2 T2 F2) L2 F2 D2
```
```p133x and p134x have symmetry group HS=<(TD),(FB)(LR)>.
```

In case you have trouble forming the closure of these groups:

```P = {I, (FB)(LR), (TD)(FRBL),   (TD)(FLBR),
(FB),         (LR),
(TD)(FR)(BL), (TD)(FL)(BR)}

Q = {I, (FB)(LR), (TD),         (TD)(FB)(LR),
(TD)(FRBL),   (TD)(FLBR),
(FLBR),       (FRBL)}

S = {I, (FB)(LR), (TD),         (TD)(FB)(LR),
(TD)(FR)(BL), (TD)(FL)(BR),
(FR)(BL),     (FL)(BR)}
```
```HP = {I, (FB)(LR), (FB),         (LR)}

HS = {I, (FB)(LR), (TD),         (TD)(FB)(LR)}.
```

I should note that the subgroup names M, C, P, Q, S, HP, and HS are
part of a general classification of subgroups of M that I worked out
some time ago. I have a chart of them I can send; just ask by email.

A few observations...

- It is not possible to swap just 1 pair of edges and corners

Certainly, all the generators are even permutations on the edges and
on the corners.

- It is only possible to have 4, 6 or 8 corners out of place

That is a nice, concise way of putting it. To elaborate, if you
permute one of the corner orbits in a 3-cycle, the other will also be
permuted in a 3-cycle; otherwise, any pair of cycle structures of the
same parity is possible.

- In reaching an antipode one may start with any of the 6 turns
(since antipodes are global maxima, any turn will get you one move
closer)

Careful! This also relies on the fact you call a conjecture, below.
Otherwise you could have two neighboring global maxima, and their
inverses would be antipodes that do not have this property. For
instance, consider the corner group as generated by the 24 pairs of
neighboring squares (F2R2, etc). This is a 48-element group with
diameter 2, trivial enough to be analyzed by hand. Antipodes
(L2B2)(D2R2) and (D2R2)(T2F2) are neighbors, because
(L2B2)(D2R2)(F2T2)=(D2R2)(T2F2). So there is no length-2 process
equivalent to (F2T2)(R2D2) that starts with T2F2.

- If the corners are fixed, the position is NOT an antipode
- All known (probably all!) antipodes have symmetry level 6 or 12

I presume these comments are left over from before you found them all.

- Longest order appears to be 12

Appears? The orbits are all of size 4 (two orbits of corners, three
orbits of edges), so 12=LCM(2,3,4) is an easy upper bound. Finding
one is easy given the processes Singmaster lists.

- Although only conjectural, it is now believed that one turn of a
face MUST lead to a new state which is either 1 move closer or 1
move farther from START

Conjectural? It's immediate from the fact that each generator is an
odd permutation of the corner orbit {FTR,FDL,BTL,BDR}.

Question: Are there any irreducible square's group sequences that
are longer then 10 moves? Are these truly irreducible or only
irreducible under Dik Winter's Kociemba inspired program?

Well, that could be searched for; a matter of checking 600K positions
for each of the 15K or so pattern representatives. I hope I can find
the time to hack it up.

Dan Hoey
Hoey@AIC.NRL.Navy.Mil