> < ^ Date: Fri, 09 Aug 2002 12:30:18 +0200
> < ^ From: Dmitrii Pasechnik <d.pasechnik@twi.tudelft.nl >
> < ^ Subject: Re: large permutation groups

Dear GAP-Forum,

I would like to know if there is a developed system that, at least in
typical cases, will analyze large permutation groups that acting on sets with
perhaps several thousand elements. If the action is not
primitive, the functions IsPrimitive and Blocks seem to work
efficiently enough to cut the action into simpler pieces.
However, many other functions, such as IsNaturalAlternatingGroup,
seem to rely on constructing stabilizer chains, which seem
prohibitively time-consuming in cases such as this. I'm not
expert with this, so I'd like to avoid trying to reinvent the wheel.
I would suggest the GAP package GRAPE, that would allow
you to study graphs invariant under the natural action of your permutation
group. Usually it can tell you a lot about the group.
For instance, checking whether your group is doubly transitive.
It has a number of functions like ProbablyStabilizer that constructs
a subgroup of the point stabilizer without resorting to stabilizer chains.

It appears to me that by doing a manageable number of trials of
computing cycle lengths of random words, with very high probability
you quickly can know that the group is a natural symmetric or alternating
group (please correct me if I'm mistaken). Is there some simple
description, or better, a GAP implementation, of probabilistic methods
of this sort?
yes, such algorithms are known (the name escapes me right now, sorry).
Not sure about their GAP implementation though.

HTH,
Dmitrii.
http://www.thi.informatik.uni-frankfurt.de/~dima/


> < [top]