> < ^ From:

< ^ Subject:

Dear Bill Thurston:

Once you have proved that your group is primitive, it should be easy to

verify

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

will

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,

then

(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]