Thanks for telling me about IsNaturalPermutationGroup. To try it out, I installed Gap4 and tested it on the examples I had already tried with Gap3. It did them, but no faster. The way I did it with Gap3 was to define the group g by giving it the explicit permutations of List([1..n]) that generate g and then by telling Gap to evaluate Size(g) to see whether I got n!. I decided to check the source code for IsNaturalPermutationGroup to see whether part of the algorithm involves first computing the size of the group and it appears that it does. Therefore, IsNaturalPermutationGroup can't improve on what I was already doing.
I realize that there might be some misunderstanding: any subgroup h of the permutation group on n objects is a permutation group and IsNaturalPermutationGroup is intended to detect whether h is isomorphic to a permutation group on possibly fewer than n objects. Therefore, it might well be, as Stefan said, that Gap was able to decide in 3 seconds that a group of permutations on millions of objects is a natural permutation group, but that natural permutation group might have been on a much smaller number of objects than n. How long would it have taken to realize that a group on millions of objects is the full symmetric group on all those millions of objects? Here is what I think might be more useful for my purposes: let x1,...xr be permutations on List([1..n]), let g be the group they generate. I want to be able to decide whether g is the full group of n! permutations on List([1..n]). First, one needs a routine that decides whether g acts transitively on List([1..n]) without actually computing the whole group or its order. If it doesn't act transitively, it isn't the full symmetric group. If it does act transitively, let h be the subgroup of g that fixes the last number n, viewed as a group of permutations on List([1..n-1]). Then one needs a routine that will take x1,...,xr and n and which will return an explicit set of generators of h, again without computing all of h or its order. Then by induction one tests whether g is n-point transitive. This procedure also makes it possible to examine the generators of h at any stage of the induction, which might also facilitate constructing proofs when computation fails. I don't know how efficiently one can compute the generators of h. Maybe it is harder than computing the order of g. Also, I haven't looked at the source code for Size(g). For all I know, it uses a variant of the method I just described. In that case, I just have to modify the code for Size(g) to make it print out information about h as it proceeds. Of course, if it turns out not to be the full symmetric group on List([1..n]), I'll want to know what it really is, but I'll cross that bridge when I come to it. At the moment, I'm convinced that the class of examples I'm looking at will always generate the full symmetric group on List([1..n]) and I just need a way to verify it in a number of cases. -- Ignorantly, Allan Adler <[EMAIL PROTECTED]> * Disclaimer: I am a guest and *not* a member of the MIT CSAIL. My actions and * comments do not reflect in any way on MIT. Also, I am nowhere near Boston. _______________________________________________ Forum mailing list [email protected] http://mail.gap-system.org/mailman/listinfo/forum
