[r-t] Fwd: Group theory question

[Martin Bright]

I've had an answer to Richard's question about cosets from somebody
who ought to know the answer if anybody does.  I haven't had a chance
to read it in detail yet.  The book he refers to is in the library
here, so I could have a look if needed.

Martin


---------- Forwarded message ----------
From: Derek Holt <D.F.Holt at warwick.ac.uk>
Date: 7 December 2011 11:39
Subject: Re: Group theory question
To: Martin Bright <martin at boojum.org.uk>
Cc: D.F.Holt at warwick.ac.uk


Dear Martin,

Sorry for the delay in replying - the final few weeks of term have been
unusually busy.

Rather than attempt to explain algorithms in detail in an e-mail, I will
refer you initially to Section 4.6.7, p126 of "Handbook of Computational
Group Theory" by Holt, Eick and O'Brien, CRC 2005. Although I hate to
encourage illegal downloads, if you find yourself completely unable to
locate a copy of this, then you could try
http://www.4shared.com/document/LtxPTggL/Handbook_of_Computational_Grou.html
which is a pirated edition. Some of the formulae have got a bit garbled, but
it is generally legible. Obviously I would be happy to try and answer any
questions you have after trying to read this!

There are two methods. They are both described for finding transversals
of H in G with H < G <= S_n, so you would apply them with G = S_n, which
would simplify them a little.

I think that for the problem of finding an index number of a coset, you would
want to define and ortder the coset representatives yourself rather than
assume that they were already given. If they were already given, you
would just have to reorder them to fit in with the algorithms.

The first method is most useful when the index |G:H| is too large to store
all of the coset reps explicitly, which I imagine would be frequently the
case with G = S_n for even moderately large n. It finds a canonical
representative of the left coset gH of g. I can describe that quite easily
for G = S_n. (BTW permutations in the book and also in Magma are multiplied
left to right.)

Find the smallest number k_1 in the orbit 1^{gH)} of 1^g under H, and find h_1
in H such that 1^{gh_1} = k_1.
Now compute the stabilizer H_{k_1} of k_1 in H.
Find the smallest number k_2 in the orbit 1^{g h_1 H_{k_1}} in the orbit of
1^{g h_1} under H_{k_1}, and find h)2 in H_{k_1} such that 1^{gh_1h_2} = k_2.
Compute the stabiliser H_{k_1k_2} of k_2 in  H_{k_1}.

Carry on like this to find the canonical representative gh_1h_2 ... h_n
of g in gS_n. This is the element g' of the coset for which the image vector
[1^g', 2^g', ..., n^g'] is lexicographically least.

I have not thought about this, but my guess is that you could use the orbit
structure of H to compute the integer corresponding to the coset, assuming
cosets are ordered by lexicographical order of representatives.

The second method is probably faster if you have space to store the full
transversal explicitly. It really does enable you to identify the numebr of the
coset of g quickly, and it is used in Magma (for example) for the CosetImage
function that computes the permutation action by right multiplication on the
cosets of a subgroup. I won't try and explain that here, but refer you
to the book.

Hope this is helpful!
Derek.



On Tue, Nov 22, 2011 at 01:34:15PM +0200, Martin Bright wrote:
> Dear Derek,
>
> Hello from Beirut.  I've got a friend who has a question in
> computational group theory, which you may be able to answer off the
> top of your head.
>
> Given a permutation group G < S_n, what is the fastest algorithm for
> testing which coset of G a given element of S_n lies in?  More
> formally, suppose that you have already labelled all the cosets with
> integers 1, ..., [S_n:G], he's after an algorithm which, given an
> element of S_n, returns the integer corresponding to the coset in
> which it lies.  Any amount of precomputation is allowed.
>
> Thanks for any help you can give!  I hope the new algebra regime in
> Warwick is off to a good start.
>
> Martin