[r-t] Coset labeling

Tue Nov 22 22:12:48 UTC 2011

Well, let's start with a very premissive version of the question.  We are 
given an explicit list of the elements of |G| (which of course we can get 
from its generators).  We are allowed to do an arbitrary amount of 
preprocessing, at the end of which we end up with some structure that uses 
O(|G|) memory.  Then using this, we want to implement a labelling function 
that takes time O(1) per call.  Simon correctly describes how do this in 
time O(c) per call, but that's not what's being asked for.  And certainly 
it can be done for certain special G.  But the question is whether it can 
be done for general G, which to me simply means that such functions exist 
for each G, with the constants in the O() notations being constants that 
do not depend on the G.

I would certainly think that the answer is no, but I don't have a proof.

So far as I can see, Simon's (d) does not answer this at all - such a 
function might not exist.

On Tue, 22 Nov 2011, Simon Gay wrote:

> 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
>
> _______________________________________________
> ringing-theory mailing list
> ringing-theory at bellringers.net
> http://bellringers.net/mailman/listinfo/ringing-theory_bellringers.net
>