MinimalNormalSubgroups for nilpotent groups

[hungaborhorvath]

MinimalNormalSubgroups computes slower for nilpotent groups than if computed either from the Socle or from the Center:

gap> k := 100;; P := SylowSubgroup(SymmetricGroup(4*k), 2);; A := Group((4*k+1, 4*k+2, 4*k+3));; G := ClosureGroup(P, A);
<permutation group with 398 generators>
gap> IsNilpotentGroup(G);
true
gap> m1 := MinimalNormalSubgroups(Socle(G));; time;
24268
gap> k := 100;; P := SylowSubgroup(SymmetricGroup(4*k), 2);; A := Group((4*k+1, 4*k+2, 4*k+3));; G := ClosureGroup(P, A);
<permutation group with 398 generators>
gap> IsNilpotentGroup(G);
true
gap> m2 := MinimalNormalSubgroups(Center(G));; time;
23968
gap> k := 100;; P := SylowSubgroup(SymmetricGroup(4*k), 2);; A := Group((4*k+1, 4*k+2, 4*k+3));; G := ClosureGroup(P, A);
<permutation group with 398 generators>
gap> IsNilpotentGroup(G);
true
gap> m3 := MinimalNormalSubgroups(G);; time;
1936368

While the first two methods run in less than half minute, the third runs for more than half hour.
The first two methods are not entirely equivalent, either:

gap> G := CyclicGroup(Factorial(100));;
gap> Size(MinimalNormalSubgroups(G)); time;
25
11304
gap> G := CyclicGroup(Factorial(100));;
gap> Size(MinimalNormalSubgroups(Socle(G))); time;
25
9324

It seems that even for elementary abelian groups some enhancement can be obtained:

gap> G := ElementaryAbelianGroup(2^16);<pc group of size 65536 with 16 generators>
gap> min := [];; for g in G do if not g=One(G) then Add(min,Group(g)); fi; od; time;
1976
gap> MinimalNormalSubgroups(G);; time;7052
gap> Set(min)=Set(MinimalNormalSubgroups(G));
true

I probably will submit a pull request on this later on.

Note that minimal normal subgroups in an infinite abelian group are in the torsion part, and hence Socle and MinimalNormalSubgroups could be computed for infinite abelian (even for nilpotent, because minimal normal implies central) groups, as well. Would it make sense to implement such methods?

[bh11]

I presume you're using CRISP. All three calls spend most of the time computing a SmallGeneratingSet. The method used is

#I Method 4: ``SmallGeneratingSet: random and generators subset, randsims'', value: 58

in grpperm.gi. Seems it's not very fast for large degree perm groups.

Overriding this method by something simple like

gap> InstallMethod (SmallGeneratingSet, "use pcgs", [IsGroup and IsFinite and CanEasilyComputePcgs], 10, Pcgs);

speeds up things significantly, making all methods about equally fast.

Before CRISP 1.4, I used GeneratorsOfGroup instead of SmallGeneratingSet, not sure if this was an oversight or maybe on purpose to avoid situations like these.

[hungaborhorvath]

@bh11 Thank you, I tried your method. For the first group, there was a significant improvement, CRISP finished in 55 seconds. Still the Socle method is doubly fast.

For the second group I did not notice any difference, in fact, GAP did not even call SmallGeneratingSet for me.

For the third, I noticed an about 15% improvement, but still iterating through the elements is 3x faster.

[bh11]

Sorry, I was referring to the first group only. The other examples do not worry me a bit. For the large cyclic groups, computing its minimal normal subgroups only takes about twice as long as creating the group. As for the third example, a factor of three for a much more generic method compared to a trivial case is all you can expect.

But please feel free to add faster methods for the nilpotent case.

P.S. For the large cyclic group, most of the time is spent computing IndepdentGeneratorsOfAbelianGroup and PCores, so probably there's some room for improvement for "trivial" cases there, too.

[hungaborhorvath]

#606 should take care of most of these.

[fingolfin]

So #606 has been merged -- what is the status of this issue then?

[hungaborhorvath]

Ah, yes. There is still room for improvement for abelian groups, but that should be put into a separate issue. This can be closed.