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.