> < ^ From:

< ^ Subject:

Javaid Aslam wrote:

It seems most of the group theoretic algorithms are based

on right coset decomposition of a the given group.I wonder if somebody knows good references for the

algorithms (e.g enumeration etc) based on the LEFT coset

decomposition using left traversals.I am considering only the permutation groups, ie. subsets

of a symmetric group.

I am not completely sure what you are asking for here, but here are a few

comments.

In one sense, this is a fairly trivial matter, because if you have a set of

right cosets {g_1,...,g_n} of a subgroup H in G, then you can get a set of

left cosets very easily by simply inverting them all -

{g_1^-1,...,g_n^-1} is a left transversal.

However, there are two different algorithms for finding transversals in

permutation groups, one of which naturally leads to a right transversal, and

the other to a left transversal. I do not know off hand which of these is

already implemented in GAP. There is a good case for having them both

available.

Suppose H is a subgroup of G.

We suppose that a base and strong-generating set for G is already known.

1. To find right coset reps, let 1 be the first base point for G, and first

(recursively) find right coset representatives {v_1,...,v_r} of the

stabilizer H_1 of H in G_1. The case in which G_1 is trivial is easy.

Let {g_1,...,g_m} be a right transversal of G_1 in G. (This will be

effectively known already as part of the base/strong-generating data

structure for G.) Then a right transversal for H in G can be chosen as

a subset of the elements

{ v_i g_j : 1<=i<=r, 1<=j<=m }.

So the method is to run through the elements of this subset, keeping

those which are in a coset that has not been seen before. It is quite

quick to test whether an element is in a new coset, and since the index

of H in G is known, we can stop as soon as we have found the correct

number of coset representatives.

2. To find left left coset reps, again let 1 be the first base point,

and let {x_1,...,x_r} be representatives of the orbits of H that are

contained in 1^G. Then we can assume that each of our left coset reps

maps 1 to one of the points x_1,...,x_r, so let

g_1,...,g_r in G satisfy 1^(g_i) = x_i for 1<=i<=r.

Those representatives mapping 1 to x_i have the form g_i v_j for elements

v_j in the stabiliser G_(x_i). In fact, we can find the v_j by applying the

method recursively to the the subgroup H_(x_i) of G_(x_i). To do this,

we need to change the first base point of H and G from 1 to x_i, so this

method involves doing a lot of base changes.

I did some timings on these methods some years ago, and my impression

was that Method 1. is slightly faster in general. However, Method 1.

has the disadvantage that the coset representatives have to be stored

as you go along, because at least the elements {v_1,...,v_r} are needed

during the next phase.

Method 2. has no storage overheads, and so it is useful in applications

where the index is very large (perhaps several million), and you wish

to consider elements in the transversal one-by-one, but you do not

need to store them.

Derek Holt.

> < [top]