> < ^ Date: Tue, 20 Aug 2002 12:04:48 -0400
> < ^ From: John Dixon <jdixon@math.carleton.ca >
< ^ Subject: re: large permutation groups

Dear Bill Thurston:
Once you have proved that your group is primitive, it should be easy to
that it is either the alternating or symmetric group by examining a few of its
elements. A theorem of Jordan says that a primitive subgroup of S_n contains
A_n if it contains an element which is a p-cycle for some prime p < n-2. I
prove in my paper (Math. Z. 110 (1969) 199-205) that "almost all" elements in
S_n have some power which is such a p-cycle. In other words, there is high
probability that for a random element x in S_n there is a prime p < n-2 such
that the cycle decomposition of x consists of a single p-cycle and other cycles
whose lengths are not divisible by p.
The function Random in GAP may need a stabilizer chain in which case you
not want to use it to find a random element of your group. However, a simple
search through some of the products obtained from your generators seems likely
to find a suitable element if one exists.
If it appears that your group is not the alternating or symmetric group,
(since it is primitive) it is known that its order is relatively small and
computing the stabilizer chain is probably quite feasible in that case (for
example, see Liebeck, Arch. Math. (Basel) 43 (1984) 11-15).
- John D. Dixon

Bill Thurston wrote:
> 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.
> 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? Or perhaps, I just need some advice about native GAP commands

> < [top]