Unexpected slowness when computing NormalSubgroups(SymmetricGroup(n)) for some n

[markuspf]

@mtorpey and I just happened upon the following unexpected behaviour:

gap> for i in [1..1000] do S := SymmetricGroup(40); NormalSubgroups(S);  Print("hi\n"); od;

Now sometimes GAP computes the normal subgroups of Sym(40) quite quickly (1-2 seconds), sometimes it takes a minute or (on @mtorpey's computer) seems to get stuck (in partition backtrack).

Maybe @hulpke can shine some light on where randomisation (pointing fingers randomly at reasons why this should even happen) is involved in this computation.

Of course for symmetric and alternating groups we can just install methods that give us the normal subgroups (@mtorpey is working on this) in basically no time at all, but there might be an underlying issue that makes this computation sometimes slower than it needs to be, and I'd like to know what it is.

[markuspf]

Update: The code seems to never get stuck, it just has very large variations in runtime: from 1.2 seconds all the way to one hour and 20 minutes letting it run over night.

[hulpke]

What happens is that the code of a centralizer of a random element is computed. In permutation groups probably a subgroup centralizer could be faster.

In any case, this should be faster, better etc. with proper recognition.

If this is a shopwstopper, I'd be happy to look at the normal subgroups code to avoid this particular issue.

[hulpke]

Looking at the example, the problem seems to be in Core(G,C) when C is a transitive subgroup of G. If G is the full symmetric group there is no quick reduction, so this takes a bit of time. I have added a silly heuristic (prefer intransitive centralizers) that avoids this bad case.