From hoey@aic.nrl.navy.mil Thu Aug 20 13:51:38 1992
Received: from Sun0.AIC.NRL.Navy.Mil by life.ai.mit.edu (4.1/AI-4.10) id AA16858; Thu, 20 Aug 92 13:51:38 EDT
Received: from sun30.aic.nrl.navy.mil by Sun0.AIC.NRL.Navy.Mil (4.1/SMI-4.0)
id AA19935; Thu, 20 Aug 92 13:51:25 EDT
Return-Path:
Received: by sun30.aic.nrl.navy.mil; Thu, 20 Aug 92 13:51:25 EDT
Date: Thu, 20 Aug 92 13:51:25 EDT
From: hoey@aic.nrl.navy.mil
Message-Id: <9208201751.AA14111@sun30.aic.nrl.navy.mil>
To: Allan C Wechsler ,
wft@math.canterbury.ac.nz (Bill Taylor)
Cc: Cube-Lovers@ai.mit.edu
Subject: Re: subgroups
On 14 Jan 1992, Allan C. Wechsler posted
>Regarding the meta-approach of descending through a series of subgroups,
>how much leverage does properly selecting the chain give you? It seems
>like the jump from to is pretty large.
>There are probably other paths through the subgroup lattice.
>Does anyone have a table of subgroups?
As far as selecting the chain goes, I have been meaning to look into
that a bit. Of course, since Bill posted, the results of Hans
Kloosterman, Michael Reid, and Dik Winter have shown that you indeed
get a lot of leverage. I would like to get some idea of the possible
group towers, for a more general approach to selecting which towers
give you leverage. But what I haven't been able to figure out is how
to figure out which coset of G1 wrt G2 you're in. I've been able to
figure it out for specific groups, but if we wanted to do this for a
lot of chains, we would need to do coset identification given G1 and
G2 as a table of strong generators. We could in fact ensure that the
strong generators of G1 form a subset of those of G2. Is that a hard
thing to do?
More to the point, I've heard that the FHL algorithm should more
properly be called Sims's algorithm and that Furst, Hopcroft, and Luks
mostly analyzed the performance. I haven't read anything by Sims on
it, though. Is there a good reference that treats this sort of
algorithm in a more general setting? I have toyed with implementing
the Jerrum improvements to FHL, but it is a mighty complicated beast.
Also, a talk announced in the archives mentioned 1987 work by Akos
Seress that was supposed to be an improvement, but I don't know
whether it got published. Anyway, if not, do you know if there is a
good general way of finding out which coset a given position is in.
On 29 Jan 1992, wft@math.canterbury.ac.nz (Bill Taylor) posted
> There hasn't been any response to this, seemingly, which is a pity.
For some reason, I never saw Bill's message. I just noticed it when
comparing my files against the archives. [ Archives seekers note: the
archives have moved to FTP.LCS.MIT.EDU (18.26.0.36), still in
directory /pub/cube-lovers. ]
> In any event, I would like to know of any other well-known subgroups.
> There are the slice group; double-slice group; U group; square group;
> anti-slice group. How many others are there not mentioned here, that
> people know of ?
There were some tables in Singmaster with more examples, and there are
the stuck-faces groups that I wrote about on 21 July 1981. I seem to
recall there was some non-obvious equivalence between two groups,
perhaps the slice group and the antislice group. But a general list
of popular subgroups would be interesting. Of course a list of *all*
the subgroups would have, um, over three beelion of them. I suspect
it has more than 4.3x10^19. Does anyone know a good way of counting
how many subgroups there are? Or even a way of estimating the number?
By comparison, the symmetries of the cube form a 48-element group with
98 subgroups.
Dan Hoey
Hoey@AIC.NRL.Navy.Mil