# [r-t] Coset labeling

Richard Smith richard at ex-parrot.com
Mon Nov 21 18:29:06 UTC 2011

```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
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

```