Socle takes a long time to calculate for nilpotent (even for abelian) groups

[hungaborhorvath]

Socle of a p-group is just the Omega of the Center, which can be computed almost instantly. Socle, however, computes for a very long time for such groups:

gap> A := CyclicGroup(4);
pc group of size 4 with 2 generators>
gap> B := DirectProduct(A, A, A, A);
pc group of size 256 with 8 generators>
gap> C := DirectProduct(B, B, B, B);
pc group of size 4294967296 with 32 generators>
gap> Omega(Center(C),2); time;
pc group with 16 generators>
44
gap> Socle(C); time;
pc group with 16 generators>
160240

The following code may improve Socle computations significantly.

InstallMethod(Socle, " for p-groups", [ IsGroup and IsPGroup],
function(G)
local p;
p := PrimePGroup(G);
return Omega(Center(G), p);
end);

It is not too hard to implement this to nilpotent groups, and maybe in the general case an IsNilpotentGroup check could be forced (or IsAbelian).

Further, existing Socle (or knowing that the group is nilpotent) could be used for determining MinimalNormalSubgroups, considering that for nilpotent groups the minimal normal subgroups are exactly all subgroups of the socle.

[hulpke]

When Sole was implemented this was mainly of interest for primitive permutation groups. The current implementation for PCGroups is most likely an afterthought.

[hungaborhorvath]

Do you mean it should not be enhanced?

Preliminary testing (few examples) shows that the following code works rather quick for nilpotent groups:

InstallMethod(Socle, "for nilpotent groups",
              [ IsGroup and IsNilpotentGroup ], 7,
  function(G)
    local p, H, prodH;

    prodH := TrivialSubgroup(G);
    for H in SylowSystem(G) do
      p := PrimePGroup(H);
      prodH := ClosureSubgroupNC(prodH, Omega(Center(H), p));
    od;
    return prodH;
  end);

For example, after loading the above code I have this:

gap> A := DihedralGroup(16);;
gap> B := SmallGroup(27, 3);;
gap> C := SmallGroup(125, 4);;
gap> D := DirectProduct(A, B, C);;
gap> F := DirectProduct(D, D, D, D);;
gap> G := DirectProduct(F, F, F, F);;
gap> Socle(G); time; 
<pc group with 48 generators>
256

The rank 7 is arbitrary, giving it only rank 6 calls the solvable socle method instead of this.

If anybody tells me which file should this go in, I would be happy to put in a pull request. However, I would rather not mess with files I have otherwise no idea about, and I am not even sure if this should go to the main gap or into a package (e.g. CRISP?)...

Maybe it probably would be better if someone else did this (who knows the other Socle algorithms), and they could then include a forced IsNilpotentGroup check into the main algorithm...

[hulpke]

No -- my remark was just as an explanation of why the current functionality is as-is. Probably grppcattr would be a place for a pcgs based method.

[hungaborhorvath]

Of course an IsFinite check has to be done, and then the rank is not needed.

I played a bit with this code, and it turns out that GAP is not able to figure out by itself that all subgroups are central. Therefore an

SetIsAbelian(prodH, true);

should be set before the

od;

I wonder if it is possible to let GAP know that these subgroups are also central (and therefore normal) in G.

[fingolfin]

@hungaborhorvath You could potentially use SetIsNormalInParent to tell GAp that these groups are normal in their parent -- but watch out, and make sure to verify that the parent of the group really is G.

[hungaborhorvath]

@fingolfin Ok, thanks. That is probably a good idea.

And what happens if these groups have no parent? Would it make sense to define their parent as G, and then SetIsNormalInParent to true? I think I yesterday had an example where none of these groups had any parent.

[fingolfin]

You could in principle call SetParent(subgroup, G) to set the parent. In the case of things like the socle, I see no reason why you shouldn't do that.

BTW, are you going to prepare a pull request with your new method? Then I'd be happy to comment on it. Otherwise, please let me know, then I'll submit one with the code.

[hungaborhorvath]

Sure, I would be happy to put in a pull request. Should it go into grppcattr.gi then, or into another file?

(As a side note, is it ok if I remove all trailing whitespaces in a commit, or that should not happen?)

[fingolfin]

There seems nothing specific about pc groups in your code, so I'd probably rather put it into grp.gi.

A commit should always focus on one thing. If you add a new function somewhere, you should not change whitespace somewhere else.

[hungaborhorvath]

Ok, I put in a pull request #402 for finite nilpotent groups.

I wonder if an IsNilpotent check should be forced for the other Socle methods and then possibly redispatch to this method? For groups that are not yet known to be nilpotent (but are, see e.g. #398 ) this probably would be faster than anything else.

[fingolfin]

Well, for those groups it will be faster. The question is: Could there be groups where checking for being nilpotent overall takes more time than just computing the socle? Even if there is no such case right now: Could one pop up in the future?

Right now, I am inclined to say: "No, this is unlikely, so go ahead and add that redispatch". (But note that questions and concerns like this make the whole redispatch business somewhat fragile...)

[hungaborhorvath]

Ok, I could write such a redispatch right after the code in grp.gi. However, other package authors in their own library files should still adapt for it (e.g. CRISP for SolvableSocle).

[hungaborhorvath]

This is done in #402