> < ^ Date: Thu, 08 Aug 2002 10:16:52 -0700
< ^ From: Bill Thurston <wpt@math.ucdavis.edu >
> ^ Subject: large permutation groups

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
that are manageable with large permutation groups.
BTW, the context is in a joint project I've been working on
with Nathan Dunfield: starting with the fundamental group G of a surface,
we've been trying to understand subgroups H of finite index.
The automorphism group Aut(G) [= mapping class group of the surface]
acts on the set of subgroups with a given
index; we'd like to understand these actions. Even for the simplest
interesting case, namely subgroups of index 5 with "Galois group" = A(5),
there are two orbits under the the automorphism group, of size
1440 (group A(1440), as deduced from cycle structures)
and 576 (not primitive: it breaks into 6 A(96) blocks, for which
IsNaturalAlternatingGroup reports true after a couple hours).

Bill Thurston

> < [top]