FittingSubgroup or FrattiniSubgroup do not have HasIsNilpotentGroup

[hungaborhorvath]

I just came across the following:

gap> G := FittingSubgroup(DihedralGroup(12));;
gap> HasIsNilpotentGroup(G);
false

As the Fitting subgroup is, by definition, nilpotent, the method should set the IsNilpotentGroup property to true. TraceMethods says that lib/grp.gi:966 is used, and indeed, IsNilpotentGroup is not set.

The same happens with the FrattiniSubgroup (called from lib/grppcatr.gi:136):

gap> G := FrattiniSubgroup(SmallGroup(192, 30));;
gap> HasIsNilpotentGroup(G);
false

I wonder, in general what kind of properties/attributes should be set by methods?
For example, is it possible to let GAP know that Sylow subgroups of FrattiniSubgroup(G) are normal in G? Or, is it possible to let GAP know that Socle of a nilpotent group is always central?

[stevelinton]

The headline problem can, and probably should, be fixed by adding a SetIsNilpotentGroup( ,true) call to the method for FittingSubgroup.

I wonder though if there is any merit in introducing a more general mechanism? You could imagine, for instance a call to declare that when an object o has certain filters set, and a is some attribute then
a(o) should automatically have certain filters set, or even have something like immediate methods run on it.

Another approach would be to have a single filter

Is<Attr>Result

which is set in all objects (for which filters can be set, integers and fail and so on would have to be excluded) and then install implications or immediate methods from this. This doesn't allow you to access the type of the "source" object, but requires less new machinery.

[hungaborhorvath]

Actually, I was wondering what are the possible filters, properties, attributes that are more common to consider when one writes a new method computing something. More specifically, I was wondering if there is any kind of filter for a subgroup that is a subgroup of the center of another group (e.g. the socle of a nilpotent group). A method might find the socle in such a way that even the IsAbelian filter is not set, and then it needs to be set by hand. Similarly, if there were some properties about centralness (idk, like IsCentralInParent, if it exists at all), it should be set, as well.

I was wondering if there is a list of all existing properties somewhere?

[fingolfin]

@stevelinton This sounds related to what the "TODO lists" of the ToolsForHomalg project do. May want to talk to @mohamed-barakat @sebasguts about this (very interesting stuff).

@hungaborhorvath There is no way to automatically ensure that e.g. the object returned by Centre has the IsAbelian filter set.

As to listing all existing properties: Well, you could type "Is" in the GAP interpreter, then press the TAB key twice to get a rough idea ;-). Of course not all of the these are "properties", but then, you may actually want more than properties anyway.

[fingolfin]

While at it, I should also mention the operations UseFactorRelation, UseIsomorphismRelation, UseSubsetRelation, another (incomplete) attempt to solve one facet of the underlying bigger issue (namely that one should argue about the relations resp. maps between object, not the objects itself -- i.e. a more categorial point of view, as e.g. the Homalg project takes it).

Addressing this properly and in general would be very nice.

[fingolfin]

BTW, in the case discussed here, one of course also need to take extra care to not forget that there are also infinite groups, and for those, neither the Fitting nor the Frattini group need to be nilpotent.

[hungaborhorvath]

Hm, I did try the Is+TAB approach, and it is really hard to navigate there....

BTW, so how will the IsNilpotent property be remedied in practice? Will all corresponding library file maintainers add this to their files, or should someone do this for all library files and put in a pull request?

[fingolfin]

You can count the globals starting with Is:

gap> Number(NamesGVars(), x -> StartsWith(x, "Is"));
1511

Quite a lot. Of course not all are really for properties and other filters...

[olexandr-konovalov]

I think this produces a list of existing properties for objects in IsGroup. Here GAP started with -r -A:

gap> isg := WITH_IMPS_FLAGS(FLAGS_FILTER(IsGroup));
<flag list>
gap> gatts := List(Filtered(ATTRIBUTES, a-> IS_SUBSET_FLAGS(isg,FLAGS_FILTER(a[2]))),a->a[1]);;
gap> Filtered(gatts, x ->x{[1,2]}="Is");
[ "IsImpossible", "IsEmpty", "IsTrivial", "IsNonTrivial", "IsFinite", "IsWholeFamily", 
  "IsDuplicateFree", "IsIntegralCyclotomic", "IsGeneratorsOfMagmaWithInverses", 
  "IsAssociative", "IsCommutative", "IsGeneratorsOfSemigroup", "IsZeroGroup", 
  "IsSimpleSemigroup", "IsZeroSimpleSemigroup", "IsReesCongruenceSemigroup", 
  "IsRegularSemigroup", "IsInverseSemigroup", "IsBand", "IsBrandtSemigroup", 
  "IsCliffordSemigroup", "IsCommutativeSemigroup", "IsCompletelyRegularSemigroup", 
  "IsCompletelySimpleSemigroup", "IsGroupAsSemigroup", "IsIdempotentGenerated", 
  "IsLeftZeroSemigroup", "IsMonogenicSemigroup", "IsMonoidAsSemigroup", 
  "IsOrthodoxSemigroup", "IsRectangularBand", "IsRightZeroSemigroup", "IsSemiband", 
  "IsSemilatticeAsSemigroup", "IsZeroSemigroup", "IsCyclic", "IsElementaryAbelian", 
  "IsFinitelyGeneratedGroup", "IsSubsetLocallyFiniteGroup", "IsPGroup", "IsNilpotentGroup", 
  "IsPerfectGroup", "IsSporadicSimpleGroup", "IsSimpleGroup", "IsAlmostSimpleGroup", 
  "IsSupersolvableGroup", "IsMonomialGroup", "IsSolvableGroup", "IsPolycyclicGroup", 
  "IsInfiniteAbelianizationGroup", "IsNormalInParent", 
  "IsomorphismTypeInfoFiniteSimpleGroup", "IsomorphismPcGroup", "IsomorphismSpecialPcGroup",
  "IsomorphismPermGroup", "IsomorphismFpGroup", "IsGeneratorsOfInverseSemigroup", 
  "IsNormalForm", "IsWeylGroup", "IsBuiltFromAdditiveMagmaWithInverses", "IsBuiltFromMagma",
  "IsBuiltFromMagmaWithOne", "IsBuiltFromMagmaWithInverses", "IsBuiltFromGroup", 
  "IsBuiltFromSemigroup", "IsBuiltFromMonoid", "IsomorphismRefinedPcGroup", 
  "IsAlternatingGroup", "IsSymmetricGroup", "IsDihedralGroup", "IsQuaternionGroup", 
  "IsQuasiDihedralGroup", "IsPSL", "IsCentralFactor", "IsFrattiniFree", 
  "IsHandledByNiceMonomorphism", "IsGroupOfAutomorphisms", 
  "IsGroupOfAutomorphismsFiniteGroup", "IsGeneralLinearGroup", "IsSpecialLinearGroup", 
  "IsomorphismFpSemigroup", "IsomorphismFpMonoid", "IsFullTransformationSemigroup", 
  "IsomorphismTransformationSemigroup", "IsomorphismTransformationMonoid", 
  "IsReesMatrixSemigroup", "IsReesZeroMatrixSemigroup", "IsomorphismReesMatrixSemigroup", 
  "IsomorphismPartialPermSemigroup", "IsomorphismPartialPermMonoid", "IsBergerCondition", 
  "IsSubnormallyMonomial", "IsMinimalNonmonomial" ]

[hungaborhorvath]

@alex-konovalov Hm, now I really start to wonder.... If one really meticulously wants to properly set these properties, then e.g. after figuring out that a group is abelian or nilpotent, then a lot of these properties should automatically set to false, e.g. IsSimpleGroup, IsSymmetricGroup, IsPSL, etc. (with a possible few exceptions). I am guessing that immediate methods could be written for such cases, but it would be tedious, never ending, and parts of it may already exist somewhere in the code.

Not to mention the situations, like when (anywhere, anytime) a nontrivial normal subgroup is computed, and then IsSimpleGroup should be set to false. But I guess nobody can expect the developers to keep track of all these properties....

[hulpke]

What would (apart from a stab-collecting urge) be the gain of having e.g. IsSimpleGroup be set automatically? There is no method selection on a filter being set to false.
Also even if they are set to true, there are in practice only a few property filters for which there are better methods. E.g. IsSolvableGroup often has better methods, but there are typically none implemented for IsNilpotentGroup. So setting such filters automatically would not yield any improvement.

[hungaborhorvath]

@hulpke Apart from the urge (which I guess is rather important), I can imagine that a later algorithm called by the user calls for IsSimpleGroup (e.g. for a similar situation: Socle currently calls for IsPrimitiveGroup and exits if its result is false), and this call might be costly (compared to being already set), because the algorithms for IsSimpleGroup will look at something else, not the fact that GAP has already computed a nontrivial normal subgroup. (This might be a wrong example, considering IsSimpleGroup is probably rather fast all the time).

Further, setting properties costs only 1 bit of memory, i.e. cheap. I can understand not setting attributes which may use up bigger chunks of memory.

About IsNilpotentGroup you are right. I found only 5 instances in the main library files where method selection checks whether this property is set. However, issue #385 is exactly about a situation, where current methods implemented for solvable groups is significantly slower than for nilpotent groups. Finally, considering that (statistically) most groups are p-groups, and therefore nilpotent, GAP probably should try to treat them a bit more favourably, if possible. (However, I would not argue that most interesting groups may not be nilpotent.)

[bh11]

@hungaborhorvath You'd have to check nontrivial proper for (some? every?) normal subgroup computed, keeping in mind that IsSimpleGroup also covers the abelian case. Probably depends a lot on a person's usage of GAP whether this makes sense. Besides, knowing that a group is not simple, not abelian, not nilpotent, … usually doesn't help during method selection.

Essentially, the same is true for enforced finiteness and nilpotency checks – depends very much on the usage scenario whether they will speed up or slow down things.

Btw., please keep in mind that methods that seem to be very efficient for small groups may be rather slow when groups get more complicated. The efficiency of "Center", in particular, depends a lot on the group and its representation. If I remember correctly, I decided against computing the socle from the centre of the Fitting subgroup in CRISP because of this problem. (Maybe I should add a method at least for the case when the Fitting subgroup knows its centre.)

[hungaborhorvath]

@bh11 This is interesting. Do you have some group examples where it takes a long time to compute the center of the Fitting subgroup? It would be worth looking at.

BTW, I am wondering how fast a FittingSubgroup computation is in general?

[hungaborhorvath]

I did some checking. The solvable Socle method is unfortunately not enforced, and therefore will only be used when the group knows that it is solvable. Otherwise it falls back rather quickly to some general method of computing all normal subgroups and takes a much longer time. I advise that an IsSolvable check should be enforced. RedispatchOnCondition does not work, because there is a generic (and rather slow) method, so it will never fall back.

gap> G := tpg[400]; 
Group([ (1,2)(3,4)(5,6)(7,8)(9,10)(11,12)(13,14)(15,16)(17,18)(19,20)(21,22)
(23,24)(25,26)(27,28)(29,30), (2,5)(7,10)(12,15)(17,20)(22,25)(27,30), (4,6)
(10,12)(16,18)(22,24)(28,30) ])
gap> TraceMethods(Socle); 
gap> Socle(G); time; 
#I  Socle: for permgrp at /home/ghorvath/work/gap/lib/grpperm.gi:1522
#I  trying next: Socle: from normal subgroups
#I  Setter(Socle): system setter
<permutation group with 10 generators>
2388
gap> HasNormalSubgroups(G);
true
gap> HasSize(G);
true

gap> G := tpg[400]; 
Group([ (1,2)(3,4)(5,6)(7,8)(9,10)(11,12)(13,14)(15,16)(17,18)(19,20)(21,22)
(23,24)(25,26)(27,28)(29,30), (2,5)(7,10)(12,15)(17,20)(22,25)(27,30), (4,6)
(10,12)(16,18)(22,24)(28,30) ])
gap> TraceMethods(Socle);
gap> IsSolvable(G); time; 
true
8
gap> Socle(G); time; 
#I  Socle: for permgrp at /home/ghorvath/work/gap/lib/grpperm.gi:1522
#I  trying next: Socle: for finite soluble group, via SolvableSocle
#I  Setter(Socle): system setter
<permutation group with 10 generators>
308

I also compared it with the method of computing the FittingSubgroup first, and then either the product of Omega(Center(H)) for H running in a SylowSystem, or simply computing the Center first and then computing the Omega group. They were comparable (226 and 228ms altogether), and about 20% faster than the SolvableSocle method. Of course, this difference is not that much.

The difference becomes rather significant with the example explained in #385 There, the CRISP method did not finish in sensible time for me, but I may not have waited enough.
I am not sure, though, how often one considers such big direct products.

Anyway, I would suggest that the CRISP method get a bigger rank and should also enforce an IsSolvable check, otherwise it will not be called in a lot of situations where it really should.

Then we could compare which method is faster for which groups and figure out which one to use when.

[hulpke]

@hungaborhorvath The basic setup of the method selection is that only properties that are already known are considered, that is GAP does not try to test for useful properties. This was a deliberate design decision to not try to put in ``clever'' deductions (or go the route of Prolog and similar languages) which have the potential to become expensive.
Also in general a method that is called will perform the calculation and not bail out in the hope of better methods being available in more specialized situations.

If there is a calculation in which it would be worth to test for a property, the standard way of implementing it is:

Install a method that does not require the condition. Rank it higher than the next method (using `ApplicableMethod' will give you ranks and thus give you an idea how much higher it should be.

This method then tests the property and calls `TryNextMethod()' to exit if the property is not fulfilled.

That way there is no need to manically set properties (or rely on clever implications) to get the better methods to be selected.

In the end it is often the representation far more than mathematical properties that allow for better algorithms. E.g. the good methods for solvable groups don't just require solvability but in fact the ability to compute exponents with respect to a polycyclic generating set.

[hungaborhorvath]

@hulpke Thanks for the explanation. I still disagree about not setting properties if by some theorem they are known in certain situations, but I also understand that currently setting many (most?) of them do not seem to affect anything. I very much liked the idea of such properties being set, because in 80% of the time in algebra problems the solution presented itself to me after observing some particular thing (e.g. a property) being true or not, and I like that GAP has the same thinking.

Anyway, just to sum up: do I understand correctly that you suggest to write some simple code for the generic method (with high enough rank) which tests for solvability and/or nilpotency (whichever seems cheap enough compared to the possible gain) and then exit with TryNextMethod(); ? And maybe do this with checking first the presentation of the group and if such tests are feasible?

[hulpke]

@hungaborhorvath I'm not advocating to never set properties and if you want to do so in your code please do so. My concern is to go into existing code and add such assignments in bulk.

Yes, you would install a method that does not require (e.g.) IsNilpotentGroup, but possibly some other filters about representation or capabilities (IsFinite and CanEasilyTestMembership would be good candidates.)

[bh11]

@hungaborhorvath @hulpke Instead of installing an explicit method with fewer filter requirements, why not rank the RedispatchOnConditions code higher? This has the advantage that all other methods are reconsidered after (e.g.) nilpotency has been discovered, so one need not be so careful about ranking. Anyway, this is what CRISP does for NormalSubgroups, seems to work well.

[hulpke]

@bh11 RedispatchOnCondition was intended to provide fallback tests, avoiding `NoMethodFound' errors and therefore ranks the method by default to be at the very end of the method selection. Using it in the way you describe brings up a number of problems:

• You will need to rank the method by hand to lie after the "better" (to avoid infinite recursion) but before the "worse" method. These ranks can change, e.g. because of the introduction of new filters or because of changes in other methods
• With the change two methods are involved instead of one. This makes debugging the method selection harder.
• Such an installation focusses not on one better method but gives the impression that the other methods are all worse.

[bh11]

@hulpke 1) No, the redispatch will only have to be ranked above the method it tries to avoid. Infinite recursion can't happen, regardless of the rank it is given. It's easy to compute the required rank from existing filters which makes the code fairly independent of subsequent ranking changes. Otoh, if you install a method which checks a property, this method usually needs to be re-ranked manually because its formal requirements will place it very low on the method list.

2. How does that differ from a method exiting via "TryNextMethod"? Of course, the redispatch messages could be improved (e.g., by stating if a re-dispatch happens and what property was computed, and ideally by giving the file position where the re-dispatch was defined, instead of the file position of the generic re-dispatch function). Imo, having one re-dispatch checking for a property is better than a series of methods all checking that property individually.

3. Quite on the contrary – re-dispatching allows all methods to profit from the additional knowledge, not just one. Also, re-dispatching can happen a lot later, giving more lower ranked methods a chance to be selected.

[hungaborhorvath]

#400 takes care of this.