On 05/09/95 at 12:11:02 hoey@AIC.NRL.Navy.Mil said:

No, the 4-spot pattern is also a local maximum at 12 qtw, although its
symmetry group is of order 16. Jim Saxe and I reported this on 22
March 1981, in "No short relations and a new local maximum".

Argh! After Dan and Mike pointed this out, I did remember having seen
it in the archives. Worse still, Dan pointed it out again on
3 August 1992. But since it has come up, let's take a brief look
at the 22 March 1981 note.

With five-qtw searches, it became possible to check another
conjecture, using an approach that Jim suggested. The four-spot
pattern

U U U
U U U
U U U

R R R  B B B  L L L  F F F
R L R  B F B  L R L  F B F
R R R  B B B  L L L  F F F

D D D
D D D
D D D

is solvable in twelve qtw, either by (FFBB)(UD')(LLRR)(UD') or by its
inverse, (DU')(LLRR)(DU')(FFBB). It is immediate that a twelve qtw
path from this pattern to START can begin with a twist of any face in
either direction. The program was used to verify that there are no ten
qtw paths. (It generated the set of positions attainable at most five
qtw from START and the set of positions obtainable from the four-spot
in at most five qtw, and verified that the intersection of the two sets
is empty.) Thus the four-spot is exactly twelve qtw from START and all
its neighbors are exactly eleven qtw from START, proving that the
four-spot is a local maximum.

Call the 4-spot s. Then, the twelve neighbors form two M-conjugacy
classes: N1={sL,sL',sF,sF',sR,sR',sB,sB'} and N2={sU,sU',sD,sD'}.
Also, we have s'=s. Dan and Jim's solution starts in N1 and ends with
a quarter-turn from N2, and since s'=s, we can say "or vice versa".
Hence, we can start a solution with any of the twelve quarter turns,
and therefore s is a local maximum.

There are other positions with the same symmetry characteristics as
the 4-spot. That is, there are other positions for which the
symmetry group contains sixteen elements. There are only three subgroups
of M containing sixteen elements, and the three subgroups are M conjugate.
The three M-conjugates of the 4-spot position correspond to the three
conjugate subgroups of M containing sixteen elements. But what of
other positions with the same symmetry group? For example, if the
edges of the 4-spot are all flipped, is the position a local maximum?
I don't know, but it is interesting to see how far we can get without
knowing a process.

Call the 4-spot with all edges flipped t. Then, we certainly have
t'=t. Is this true of all positions whose symmetry group contains
sixteen elements? Also, we certainly have the twelve neighbors
forming M-conjugacy classes similar to those for s, N1 with eight
elements and N2 with four. Is this true of all positions whose symmetry
group contains sixteen elements? Finally, a solution either starts in
N1 or starts in N2. If starting in N1 implies ending with a
quarter-turn from N2 or vice versa, then t is a local maximum.
Can we prove such a thing without actually finding a solution?

 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
Robert G. Bryan (Jerry Bryan)                        (304) 293-5192
Associate Director, WVNET                            (304) 293-5540 fax
837 Chestnut Ridge Road                              BRYAN@WVNVM
Morgantown, WV 26505                                 BRYAN@WVNVM.WVNET.EDU