Method selection for FrattiniSubgroup

[hungaborhorvath]

As far as I can see, there are 9 different methods handling FrattiniSubgroup computations:

handled by nice monomorphism, rank 370, grpnice.gi:529
method for trivial groups, rank 71, grp.gi:1024
for permgrp, rank 58, grpperm.gi:1598
pcgs computable groups using prefrattini and core, rank 52, grppcatr.gi:136
for pcp groups, rank 50, pkg/polycyclic-2.11/gap/pcpgrp/general.gi:142
for abelian groups, rank 43, grp.gi:1030
for nilpotent groups, rank 41, grp.gi:1048
Using radical, rank 35, maxsub.gi:335
generic method for groups, rank 35, grp.gi:1060

Some of these are superfluous, e.g. the "for permgrp" method checks if the groups is a p-group and then uses the same method that is used for nilpotent groups. If the group is not a p-group, then it exits by TryNextMethod. This circumvents method selection.

Further, the "generic method" has the same rank as the "radical" method (both filter for IsGroup), thus the generic method will never ever be called on any group. This could/should be cleaned up.

Second, I do not think that the pcgs or pcp methods should be before the abelian (or even the nilpotent) methods. Maybe abelian and nilpotent methods should receive a rank increase by an IsFinite rank?

For the pcp, pcgs, radical methods I cannot really decide what they do and how fast they compute the Frattini subgroup, but some of them fail to compute for particular groups, sometimes even if they are finite (!), e.g.

gap> F := FreeGroup("x", "y");; x := F.1;; y := F.2;;
gap> G := F/[x*y*x^(-1)*y^(-1), x^30, (x*y)^70];;
gap> TraceMethods(FrattiniSubgroup);
gap> FrattiniSubgroup(G);
#I  FrattiniSubgroup: Using radical at /home/ghorvath/work/gap/lib/maxsub.gi:
335
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 2nd choice method found for `FittingFreeLiftSetup' on 1 arguments at /home/ghorvath/work/gap/lib/methsel2.g:241 called from
FittingFreeLiftSetup( G 
 ) at /home/ghorvath/work/gap/lib/maxsub.gi:176 called from
MaximalSubgroupClassesSol( G 
 ) at /home/ghorvath/work/gap/lib/maxsub.gi:342 called from
<function "unknown">( <arguments> )
 called from read-eval loop at *stdin*:4
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
brk> 

I cannot decide if the "radical" method (or the "generic" method for that matter) can possibly be used for arbitrary groups (as they are called now), or only for finite (or only for finite with particular presentation). Nevertheless, if they error out on finite groups, then something should be done.

Another example (artificial as it may be) is

gap> k := 20;; 
gap> P := SylowSubgroup(SymmetricGroup(4*k), 2);; 
gap> A := Group((4*k+1, 4*k+2, 4*k+3));; 
gap> G := ClosureGroup(P, A);;
gap> TraceMethods(FrattiniSubgroup);
gap> FrattiniSubgroup(G); time; 
#I  FrattiniSubgroup: for permgrp at /home/ghorvath/work/gap/lib/grpperm.gi:
1598
#I Trying next: FrattiniSubgroup: Using radical at /home/ghorvath/work/gap/li\
b/maxsub.gi:335
#I  Setter(FrattiniSubgroup): system setter
<permutation group of size 295147905179352825856 with 68 generators>
86568

while

gap> k := 20;; 
gap> P := SylowSubgroup(SymmetricGroup(4*k), 2);; 
gap> A := Group((4*k+1, 4*k+2, 4*k+3));; 
gap> G := ClosureGroup(P, A);;
gap> TraceMethods(FrattiniSubgroup);
gap> IsSolvableGroup(G); time;
true
72
gap> FrattiniSubgroup(G); time; 
#I  FrattiniSubgroup: for permgrp at /home/ghorvath/work/gap/lib/grpperm.gi:
1598
#I Trying next: FrattiniSubgroup: pcgs computable groups using prefrattini an\
d core at /home/ghorvath/work/gap/lib/grppcatr.gi:136
#I  Setter(FrattiniSubgroup): system setter
<permutation group of size 295147905179352825856 with 68 generators>
1056

is much faster. I believe this would warrant a check for solvability (and possibly for finiteness) before applying the radical method.

BTW, for this group an IsNilpotent check takes 104 ms, and then the nilpotent method computes the Frattini subgroup in 336ms. About twice faster than the pcgs method. Thus maybe a nilpotency check is warranted, however that may not give that much of an increase over the pcgs method.

I am happy to submit a PR trying to clean this up a bit, but first I would like to have an idea about the general consensus on what people think should be done and how.

Similar issues could be had for NormalSubgroups, as well, and probably for a lot of other functions. (E.g. there CRISP circumvents the usual method selection in residual.gi:96 by checking for solvability and finiteness.)

[hulpke]

Some of these are superfluous, e.g. the "for permgrp" method checks if the groups is a p-group and then uses the same method that is used for nilpotent groups. If the group is not a p-group, then it exits by TryNextMethod. This circumvents method selection

No. This is exactly how method selection is intended to work.

Second, I do not think that the pcgs or pcp methods should be before the abelian (or even the nilpotent) methods. Maybe abelian and nilpotent methods should receive a rank increase by an IsFinite rank?

If you think it is worth doing so.

Further, the "generic method" has the same rank as the "radical" method (both filter for IsGroup), thus the generic method will never ever be called on any group. This could/should be cleaned up.

Yes, the method using the radical (which utilizes maximal subgroup functionality that was not available when the other method was installed) supersedes an older method fully. Again this is how method selection works -- a newer method overrides the older one. Once could remove the older one, but with very little gain.

I believe this would warrant a check for solvability (and possibly for finiteness) before applying the radical method.

This depends on what input you assume. A failing solvability test might be expensive for zero gain. Vice versa PcGroups immediately know that they are solvable, and thus anyhow go in the right route.

I cannot decide if the "radical" method (or the "generic" method for that matter) can possibly be used for arbitrary groups (as they are called now), or only for finite (or only for finite with particular presentation).
The radical method implicitly assumes (as much of GAPs library) some kind of finiteness.

Nevertheless, if they error out on finite groups, then something should be done.

What you're observing is a side-effect of using finitely presented groups. For a long time none of the standard functions were available for these groups, and the fact that now much of it works has long been underappreciated.
Yes, there currently is no method for FittingFreeLiftSetup for fp groups -- I'll try to add one in a quiet moment -- but the correct answer is probably that one should convert to another representation first.

[hungaborhorvath]

@hulpke Does the radical method and the generic method work for infinite groups, as well? If not, can we at least add an IsFinite filter, so that for arbitrary groups the redispatches will be called first?

[fingolfin]

Looking at this issue, I have a hard time filtering out what actionable items there are left, if any.

@hungaborhorvath suggested that abelian / solvable methods should come before pcp / pcgs methods. I disagree: pcgs / pcp implies that one can actually effectively compute in a group. Whereas a group may be abelian but almost untractable for computational purposes (e.g. it may have a complicated fp presentation, be infinite, etc.)

The problem with the radical method being ranked equally to the "generic" method is gone, the current ranking is this:

1. system getter, value: 2*SUM_FLAGS+37
2. handled by nice monomorphism: Subgroup, value: 372
3. for powerful p-groups, value: 140
4. method for trivial groups, value: 73
5. for permgrp, value: 58
6. pcgs computable groups using prefrattini and core, value: 52
7. for pcp groups, value: 50
8. Using radical, value: 45
9. for abelian groups, value: 43
10. for nilpotent groups, value: 41
11. generic method for groups, value: 35
12. default method requiring categories and checking properties, value: 0

This leaves the two concrete examples, were testing for solvability (or being abelian, nilpotent) may help tremendously.

Here it might help if something like the following was added to the generic method (alternatively, if suitable redispatch rules were used, perhaps):

    if not HasIsSolvableGroup(G) and IsSolvableGroup(G) then
       return FrattiniSubgroup(G);
    fi;

For the second problem: While it is true that a solvability check could hurt more than it helps, it is also true that the radical method computes the radical -- and at that point, can of course trivial decide if the groups is solvable. So inserting a similar check should be fine...

I'll prepare a pull request, then perhaps @hulpke can comment on it, and we can decide if it is worth it, or whether there are possibly case that might suffer from this "improvement".