[GAP Forum] size of permutation groups
Steve Linton
sal at cs.st-and.ac.uk
Thu Jan 25 14:29:29 GMT 2007
Dear Allan,
IsNaturalSymmetricGroup checks the given group acts as Sn on the set of
points it moves. All its work is basically done in
the function PermgpContainsAn, which is as follows:
gap> Print(PermgpContainsAn);
function ( g )
local dom, n, mine, root, d, k, b, m, l, lh;
dom := MovedPoints( g );
n := Length( dom );
if not IsTransitive( g, dom ) then
return false;
fi;
if DoSnAnGiantTest( g, dom, 1 ) = true then
return true;
fi;
if not IsPrimitive( g, dom ) then
return false;
fi;
if n > 10 then
mine := Minimum( List( Collected( Factors( n ) ), function ( i )
return i[2];
end ) );
for m in [ 1 .. mine ] do
root := RootInt( n, m );
if root ^ m = n then
if m > 1 then
d := PermNatAnTestDetect( g, root, m, 1 );
if d <> fail then
Info( InfoGroup, 3, "Detected ", root, ",", m, ",",
1, "\n" );
return d;
fi;
fi;
for l in [ 2 .. RootInt( 2 * root, 2 ) + 1 ] do
lh := Int( l / 2 ) + 1;
k := 2;
b := Binomial( l, k );
while b < root and k < lh do
k := k + 1;
b := Binomial( l, k );
od;
if b = root then
d := PermNatAnTestDetect( g, l, m, k );
if d <> fail then
Info( InfoGroup, 3, "Detected ", l, ",", m, ",",
k, "\n" );
return d;
fi;
fi;
od;
fi;
od;
fi;
if DoSnAnGiantTest( g, dom, 2 ) = true then
return true;
fi;
return Size( g ) >= Factorial( n ) / 2;
endg
First this checks transitivity, which is easily done in linear time from just
the generators of g. Next it calls DoSnAnGiantTest which is a randomized
algorithm that searches for certain configurations of elements which are
common in Sn or An and suffice to prove that any transitive group containing
them must be Sn or An in natural action. If that fails, it checks for
primitivity, which takes worst-case quadratic time. If the group is not
primitive it is not Sn or An. I'm not sure what the next group of tests are,
although they do appear to involve iterative computation of point stabilizers.
If the group passes these, the randomized algorithm is called again, to try
harder in case we were just unlucky and only as a very last resort is the size
computed.
On my laptop this took 12 seconds for two random permutations of a million
points.
Steve
On Thu, 25 Jan 2007 07:48:57 -0500
Allan Adler <ara at zurich.csail.mit.edu> wrote:
>
> 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 <ara at zurich.csail.mit.edu>
> * 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
> Forum at mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum
--
Steve Linton School of Computer Science &
Centre for Interdisciplinary Research in Computational Algebra
University of St Andrews Tel +44 (1334) 463269
http://www.cs.st-and.ac.uk/~sal Fax +44 (1334) 463278
More information about the Forum
mailing list