[r-t] Coset labeling

[Simon Gay]

On 22/11/2011 22:12, Alexander Holroyd wrote:
> 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.
No, not a solution; just an attempt to put Richard's current approach
into some context.
>
> 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
>>
> _______________________________________________
> 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