[r-t] Coset labeling

[Simon Gay]

If I understand correctly, the problem you are interested in is the
following.

Given a group G, which is a subgroup of S_n, there are of course n! /
|G| cosets. Let c be the number of cosets. Then you want:

1. A specific numbering of the cosets by numbers in the range 0 .. c-1.
I think this means explicitly knowing at least one element of each coset.

2. A function from S_n to {0 .. c-1}, mapping an element of S_n to the
number of the coset of G that it is in. This is what you call a coset
labelling function.

3. You want the function in (2) to be constant time.

4. You don't want a hash table of size n! or, ideally, even of size |G|.

5. You want a general way of doing this, which I interpret to mean that
you want to be able to construct the coset labelling function
algorithmically, given G.


If I am right about (5), then I think the key question is how is G
specified, in order to be the input to the algorithm?

You could think of various ways of specifying G:

a. As an explicit list of its elements.

b. As an implementation of its membership predicate.

c. By a set of generators (most likely, if you are thinking of
multi-part compositions).


If (a) then you already have essentially a table of size |G|, but you
still have to do some work to find an explicit representative of each
coset. (This can be considered set-up cost, so it's not too bad). But
then the obvious way to get a coset labelling function would be to test
for membership of each coset, so you get time c.

If (b) then again it would take some work to find the representatives of
the cosets, and it seems similar to (a).

If (c): I don't know anything about algorithms for working with group
presentations, but maybe there is something.


What I think you said you are doing now is effectively:

d. Specify G by providing an implementation of its coset labelling function.

Clearly (d) implies (b) but provides more information.


You might say this is cheating and just solving the problem by
redefining it, but you say that in practice you are able to do (d) for
the groups that you are interested in.

Thinking in Java-style object-oriented terms, I would say that you have
an interface for a subgroup, which requires the coset labelling function
to be implemented. Any particular subgroup you want can be defined by
implementing this interface. If there are families of subgroups for
which you can define the coset labelling function in certain ways, for
example cyclic groups or direct products of cyclic groups, then you have
various classes that implement the subgroup interface.

Simon







On 21/11/2011 18:29, Richard Smith wrote:
> 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
>
> _______________________________________________
> ringing-theory mailing list
> ringing-theory at bellringers.net
> http://bellringers.net/mailman/listinfo/ringing-theory_bellringers.net



The University of Glasgow, charity number SC004401