[r-t] Coset labeling

[Richard Smith]

Simon Gay wrote:

> Maybe this suggestion is too obvious, but if I remember my undergraduate 
> group theory correctly:
>
> The coset containing r is Gr. So r and s are in the same coset if and only if 
> their cosets are the same: Gr = Gs.
>
> Gr = Gs if and only if s * inverse(r) is in G.

That's certainly true, but it doesn't actually yield as big 
an improvement as it might sound.  However that's only 
obvious if you know more about the context in which I'm 
want to do this.

I'm searching for methods or compositions that are true to a 
particular part-head group.  That's what G is.  So I 
typically have a set, M, of rows already in the method (or 
leads heads/ends in the composition), and I want to test 
whether some new row, r, is in the same coset as a member of 
M.

In your scenario, I can iterate through each m in M, testing 
whether m.r^{-1} is in G.  As you say, I can make that 
latter test O(1) by using a hash table.  But I have to do 
this |M| times, so my algorithm ends up O(|M|).

However, if I have a labelling algorithm, instead of using 
M, the set of rows, I use L, the set of labels for each m in 
M:

   L = { label(m) : m in M }

All I now have to do is find label(r) and see whether that's 
in L, and by using a hash table for that, I can make that 
lookup O(1).  The complexity of the whole test is then 
simply the complexity of the labelling algorithm.  If that 
is O(|G|) then in the very common case that |G| < |M|, I'm 
winning.  As most of the time, |G|=1, I'm reluctant to take 
that performance hit.  Yes, I could use different algorithms 
in different cases, but that can rapidly lead to a 
maintenance nightmare and subtle bugs that only manifest in 
complex test cases.

I know that I can write O(1) coset labelling algorithms for 
many of the more common groups, including the case of a 
direct product of an arbitrary number of symmetrical groups 
(which crop up in differentials), and with a bit of thought, 
I think I can probably extend this to include arbitrary 
direct products of symmetrical, alternating, dihedral and 
cyclic groups (in their standard representations).  That 
would include virtually everything that normally turns up in 
ringing.  Until someone starts looking at Hudson's group, or 
some of the other interesting transitive groups.  As 
Hudson's group only has order 60, that particular case isn't 
too bad.  But what if someone wants to look at, say, one of 
the Matthieu groups?

Perhaps I'm being unreasonable in hoping I can do this in 
O(1) in the general case.  But nor am I convinced it's 
impossible.

RAS