From cube-lovers-errors@mc.lcs.mit.edu Mon Aug 25 11:47:21 1997
Return-Path:
Received: from sun30.aic.nrl.navy.mil by mc.lcs.mit.edu (8.8.1/mc) with SMTP
id LAA18038; Mon, 25 Aug 1997 11:47:21 -0400 (EDT)
Precedence: bulk
Errors-To: cube-lovers-errors@mc.lcs.mit.edu
Mail-from: From jbryan@pstcc.cc.tn.us Wed Aug 20 12:41:14 1997
Date: Wed, 20 Aug 1997 12:37:38 -0400 (EDT)
From: Jerry Bryan
Subject: Open and Closed Subgroups of G
To: Cube-Lovers
Message-Id:
I am going to use the terms open and closed with a certain trepidation.
These terms may already have a conventional meaning in group theory of
which I am not aware. If so, my apologies in advance. Anyway,...
The Hofstadter articles about the cube in Scientific American many years
ago made one point very strongly. Namely, that in solving the cube by
hand you often temporarily have to give up hard won progress. For
example, suppose you solve the cube bottom layer first, middle layer (the
middle between the top and bottom) second, and the top layer last. (This
isn't the way I do it, and I doubt that anybody does it in quite this way,
but it makes for a good example.)
Using this method, it is almost certain that you will have to disturb the
bottom layer to solve the middle layer, and it is almost certain that you
will have disturb the bottom and middle layers to solve the top layer.
(It's an interesting exercise to characterize those few positions where
you wouldn't have to disturb previously solved layers to complete your
task.)
The set of positions where the bottom layer is fixed constitute a group,
as do those positions where the two bottom layers are fixed. Hence, the
series of plateaus involved in this particular solution define a sequence
of nested subgroups.
The Thistlethwaite algorithm reverses the roles of the solution algorithm
and the sequence of nested subgroups. Instead of a solution algorithm
defining a sequence of nested subgroups, a sequence of nested subgroups
defines a solution algorithm. In some ways, I think this is a distinction
without a difference; it is more like two sides of the same coin.
However, I think there is one really fundamental difference with the
Thistlethwaite algorithm. Namely, you never have to give up any of your
"hard won progress". That is, after you make it to a particular subgroup
in the nested sequence, no subsequent move takes you out of that subgroup.
So let's define any subgroup of G having this property as closed, and any
subgroup which is not closed as open. To be a little more specific, a
closed subgroup is a subgroup such that for every position in the
subgroup, there is a maneuver back to Start which never leaves the
subgroup.
I am a quarter-turner, but I think that perhaps closed subgroups are an
argument which has not yet been specifically articulated for counting
half-turns as one move. That is, many of the subgroups which are used in
Thistlethwaite and Thistlethwaite-like algorithms forbid quarter-turns
along one or more axes at some point in the process. Restricting
quarter-turns assists your sequence of nested subgroups all to be closed
subgroups. It seems to me that such an approach leads very naturally to
counting half-turns as one move.
Finally, when I first read about Thistlethwaite's algorithm, I naively
assumed that the algorithm's maneuvers from the next to last subgroup in
the sequence to the last subgroup in the sequence (namely to Start itself)
were minimal in G. This is clearly not true in general. The first example
I remember where this began becoming clear to me was the __ group. We
could solve a cube as G -> ____ -> I, although the jump from G to ____
is quite a big jump. But a minimal maneuver in ____ is certainly not
necessarily minimal in G.
Let's call a subgroup H of G a closed minimal subgroup if every minimal
maneuver in H is also minimal in G. ____ is closed, but it is not closed
minimal. I have tried to think about which subgroups of G are clearly
closed minimal. I can't think of many. In fact the only examples I can
think of are subgroups generated as __~~, where s is a syllable or
syllables along the same axis. So , , , , and
and their conjugates are closed minimal subgroups. (Well, I and G are
closed minimal, but it hardly seems fair to count them.)
This whole area was discussed rather thoroughly in the recent spate of
messages about Korf's paper and Kociemba's algorithm, but without using
the terms closed or closed minimal. I do not believe any of the subgroups
which were discussed were claimed to be closed minimal, although I think
essentially all of them were closed. The most interesting subgroup which
was discussed was Mike Reid's co-called T, which is the intersection of
with its conjugates. I wonder if Mike's T subgroup is
closed minimal?
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
Robert G. Bryan (Jerry Bryan) jbryan@pstcc.cc.tn.us
Pellissippi State (423) 539-7198
10915 Hardin Valley Road (423) 694-6435 (fax)
P.O. Box 22990
Knoxville, TN 37933-0990
[Moderator's note: This message has been delayed by a clerical error
on my part.--Dan]
~~