Address @hungaborhorvath's pull requests

[markuspf]

@hungaborhorvath has submitted a number of pull requests, most of which have been commented on by multiple people. Since the issues are somehow connected, we should decide on what to do with the pull requests. The numbers are listed below for convenience.

• Some small enhancements on Sylow and Hall subgroup computations #535
• Enhance MaximalNormalSubgroups for finite solvable groups #552
• Add NormalHallSubgroups #561
• Add ComplementClassesRepresentatives for all groups #563
• Add FrattiniSubgroup for nilpotent groups #583
• Add MinimalNormalSubgroups and Socle for all nilpotent groups #606

[hulpke]

#535, #561 are fine

#552, #583, #606 circumvent the method selection to force a test for nilpotence first. I'm uncomfortable with such installations, unless a clear benefit and lack of cost in inapplicable cases can be demonstrated,
The actual method code is fine.
My inclination would be to accept these pull requests, followed by a change of these installations (i.e. the methods installed for IsNilpotentGroup).

#563 is a hopeless method (which the included tests actually don't test) and which I'm inclined to reject: If both N and G?n are not solvable, it is unlikely that a subgroup lattice computation ever will terminate.

[markuspf]

Thank you for the feedback, @hulpke.

I merged #535 and #561 and we will see whether the more extensive tests run on jenkins turn up any problems. I'll have a closer look at the others soon (unless someone else beats me to it or objects loudly)

[stevelinton]

I think #549 is not the PR you mean.

[markuspf]

@stevelinton indeed. I just removed it.

[stevelinton]

Regarding #552, #583 and #606, I share @hulpke's concern about circumventing method selection in this way.

I think the test is in the wrong place. If you have two methods for solving a problem, where the first requires some Properties of the arguments and the second is slower (or even is just a No Method Found) it may well be sensible to try and explicitly check some of the Properties before calling the slower method. Specifically when that check will never fail when the slower method succeeds, and when the check is likely to be quicker than the slower method.

However I think the place to put that check is in the slower method (or as a fallback method if there is no slower method). In particular if the slower method is changed in any way, the conditions for doing the check need to be re-evaluated.

[markuspf]

I will try to merge #552, #583 and #606 with the proposed change that the methods are only installed for IsNilpotentGroup not for IsGroup.

[markuspf]

Mhm actually the MaximalNormalSubgroups code in #552 could be broken up futher into IsAbelian and IsSolvableGroup?

[markuspf]

I just merged #552, but split up the installed method for maximal subgroups into a case for abelian groups and a case for solvable groups.

[hungaborhorvath]

Thank you very much for checking these PRs.

@markuspf If you break up the code to be installed for only groups having the property, you do not need the artificial rank increase, anymore. Namely, RankFilter( IsGroup and IsAbelian ) - RankFilter( IsGroup ) should just be replaced by 0. Or should I put in a pull request about this after all these are merged?

[markuspf]

@hungaborhorvath I will just remove the rank increase manually. Thanks for pointing that out.

[olexandr-konovalov]

We have two new diffs now:

########> Diff in /home/hudson/workspace/GAP-dev-compilers/GAPCOPTS/64build/GA\
PREADLINE/noreadline/label/gcc49/GAP-git-snapshot/tst/testinstall/opers/Maxima\
lNormalSubgroups.tst:32
# Input is:
List(MaximalNormalSubgroups(D2), StructureDescription);
# Expected output:
[ "D180", "D180", "C180" ]
# But found:
[ "C180", "D180", "D180" ]
########
########> Diff in /home/hudson/workspace/GAP-dev-compilers/GAPCOPTS/64build/GA\
PREADLINE/noreadline/label/gcc49/GAP-git-snapshot/tst/testinstall/opers/Maxima\
lNormalSubgroups.tst:40
# Input is:
Length(MaximalNormalSubgroups(G));
# Expected output:
7
# But found:
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 3rd choice method found for `ConjugacyClasses' on 1 arguments
########

While the 1st one is just the ordering, the 2nd one is strange. How did we miss it with Travis CI?

[hungaborhorvath]

@alex-konovalov @markuspf A RedispatchOnCondition needs to be added for all of these new methods.

In the tests that I have added I assumed that MaximalNormalSubgroups will check if the group (even if infinite) is Abelian or Solvable. This did not happen now, and GAP did not find any methods.

This will be an issue in all other PRs, as well.

[markuspf]

I am not sure whether RedispatchOnCondition (which I hadn't heard of until an hour ago) would not also constitute trying to trick method selection?

My impression was that the methods were only supposed to be selected if the appropriate properties of the group were already known.

Maybe @hulpke and/or @stevelinton can comment on that.

[stevelinton]

Redispatch on Condition is more-or-less the official way to deal with these situations, along the lines I suggested above.

Critically it is basically guaranteed to be called last, so it can’t get in the way of any method that might actually work.

Steve

On 28 Mar 2016, at 20:25, Markus Pfeiffer notifications@github.com wrote:

I am not sure whether RedispatchOnCondition (which I hadn't heard of until an hour ago) would not also constitute trying to trick method selection?

My impression was that the methods were only supposed to be selected if the appropriate properties of the group were already known.

Maybe @hulpke and/or @stevelinton can comment on that.

—
You are receiving this because you were mentioned.
Reply to this email directly or view it on GitHub

[markuspf]

Mhm. So I added RedispatchOnCondition calls.

Now in the following situation:

k := 5;; 
P := SylowSubgroup(SymmetricGroup(4*k), 2);; 
A := Group((4*k+1, 4*k+2, 4*k+3));; 
G := ClosureGroup(P, A);;

GAP does not know that P is nilpotent, so it uses a generic method based on normal subgroups, and takes a long time (I lost patience and stopped the test). If I make GAP know that the group is nilpotent (or soluble, although that ends up in CRISP) ask IsNilpotentGroup, then of course GAP will select the method for nilpotent groups.

Maybe in this case the fix is to weigh whether in the lattice method testing for nilpotency and redispatching is the correct thing to do?

[hungaborhorvath]

@hulpke about #563 I am sorry, I do not understand why you write that the tests do not check this method? The group A_5 semidirect S_5 is explicitly added to check this. Did I mess it up?

To give some background for everybody: Currently there is no method for ComplementClassesRepresentatives if both N and G/N are non-solvable, and for such groups the only reason StructureDescription does not fail is that the code in #563 is already hardcoded in SemidirectFactorsOfGroup. Now, I would like to clean this mess up and I propose to do it the following way: Replace SemidirectFactorsOfGroup, because it does not exactly do what it claims to do (in the comments of the source file), and it does not do it efficiently, either. I would like to use ComplementClassesRepresentatives instead, because that is exactly about semidirect decomposition. But then StructureDescription will error out if G is a group for which there exists a nonsolvable normal subgroup where G/N is nonsolvable, as well. To remedy this, we have #563.

In #563 I added the method only for groups knowing their conjugacy classes as per @bh11 suggestion, until we do not have anything better. @hulpke mentioned during the discussion that he might write a proper code at some point. In the meantime, however, (if #563 is merged), for the problematic groups I can call ConjugacyClassesSubgroups in StructureDescription with a possible warning. Or, (if #563 is rejected) we could simply error out for these groups.

[markuspf]

So I merged most of the PRs, but I hacked around problems with method selection in the tests by adding explicit IsNilpotentGroup and IsAbelian calls. we'll have to find out what the appropriate way of going about these actually should be (I will have a look at the discussions in the other PRs because I have to admit I din't read them fully yet).

I can add more RedispatchOnCondition calls, but these only help if there is no method, not if there is a method in the way that takes long.

[hungaborhorvath]

Some of the current methods should only be called for finite groups, e.g. grp.gi:4456. That way redispatch would help for infinite groups, at least.

@markuspf You have missed some code from #552, grppcatr:481-483. This tests, if G/G' is infinite (for arbitrary group, not only for abelian or solvable), in which case it errors out by telling the user that there are infinitely many maximal normal subgroups. Currently you get a no method found error:

gap> G := AbelianGroup([0,2]);
<fp group on the generators [ f1, f2 ]>
gap> IsAbelian(G);
true
gap> MaximalNormalSubgroups(G);
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 2nd choice method found for `AbelianGroupCons' on 2 arguments at /home/ghorvath/work/gap/lib/methsel2.g:241 called from
AbelianGroupCons( arg[1], arg[2] 
 ) at /home/ghorvath/work/gap/grp/basic.gd:136 called from
AbelianGroup( IsPcGroup, AbelianInvariants( G ) 
 ) at /home/ghorvath/work/gap/lib/grppcatr.gi:491 called from
<function "unknown">( <arguments> )
 called from read-eval loop at *stdin*:6
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
brk> 

This particular problem could be handled by e.g. adding the missing code to the IsAbelian method, and further writing a method for all groups (which would presumably come after all the IsFinite methods), checking G/G' first, and exiting with TryNextMethod(); if G/G' is finite.

I have not checked all the changes in the PRs thoroughly, not even this, so there might be further problems. Is there any way I can check what exactly has been merged compared to what is on the PR links?

edit: confusing typos, sorry.

[markuspf]

I have merged exactly the PRs, and then edited accordingly, hence you can just look at the history of the files to see what was merged, and how I changed it.

I did intentionally remove the computation of AbelianInvariants, as per @fingolfin's comment that it might be too much of an assumption being able to compute them.

[hungaborhorvath]

@markuspf Ah, ok, now I understand. @fingolfin did not explicitly state, though, that it should be removed, and nobody ever replied to my reasoning on his comment.

[olexandr-konovalov]

@hungaborhorvath we have a problem :)

It is required that tests should run without packages (i.e. when GAP is started with -A option) as well. When one calls e.g. make testinstall it produces two log files in dev/log, one for the test without packages and one with all packages loaded.

Now this is what happens in testinstall:

1. IsPcpGroup is defined in polycyclic - I suggest to replace this by IsPermGroup. There is no necessity to introduce the dependency on polycyclic package in this test (but polycyclic may add such test to their test files):

########> Diff in /Volumes/hudson-fs/workspace/GAP-dev/GAPCOPTS/64build/GAPGMP\
/gmp/GAPTARGET/install/label/fruitloop/GAP-git-snapshot/tst/testinstall/opers/\
MinimalNormalSubgroups.tst:16
# Input is:
D := DihedralGroup(IsPcpGroup, 8);;
# Expected output:
# But found:
Error, Variable: 'IsPcpGroup' must have a value
########

2. Test runs too long (while with default packages it takes only 3 seconds!) and then runs out of memory:

########> Diff in /Volumes/hudson-fs/workspace/GAP-dev/GAPCOPTS/64build/GAPGMP\
/gmp/GAPTARGET/install/label/fruitloop/GAP-git-snapshot/tst/testinstall/opers/\
MinimalNormalSubgroups.tst:54
# Input is:
SortedList(List(MinimalNormalSubgroups(D), IdGroup));
# Expected output:
[ [ 2, 1 ], [ 2, 1 ], [ 2, 1 ], [ 2, 1 ], [ 2, 1 ], [ 2, 1 ], [ 2, 1 ], 
  [ 2, 1 ], [ 2, 1 ], [ 2, 1 ], [ 2, 1 ], [ 2, 1 ], [ 2, 1 ], [ 2, 1 ], 
  [ 2, 1 ], [ 2, 1 ], [ 2, 1 ], [ 2, 1 ], [ 2, 1 ], [ 2, 1 ], [ 2, 1 ], 
  [ 2, 1 ], [ 2, 1 ], [ 2, 1 ], [ 2, 1 ], [ 2, 1 ], [ 2, 1 ], [ 2, 1 ], 
  [ 2, 1 ], [ 2, 1 ], [ 2, 1 ], [ 3, 1 ], [ 3, 1 ], [ 3, 1 ], [ 3, 1 ], 
  [ 5, 1 ] ]
# But found:
Error, reached the pre-set memory limit
(change it with the -o command line option)
########

The group here is constructed as follows:

gap> A := DihedralGroup(16);;
gap> B := SmallGroup(27, 3);;
gap> C := SmallGroup(125, 4);;
gap> D := DirectProduct(A, B, C, SmallGroup(1536, 2));
<pc group of size 82944000 with 20 generators>

and apparently some package is required to handle this.

3. This also requires polycyclic:

########> Diff in /Volumes/hudson-fs/workspace/GAP-dev/GAPCOPTS/64build/GAPGMP\
/gmp/GAPTARGET/install/label/fruitloop/GAP-git-snapshot/tst/testinstall/opers/\
MinimalNormalSubgroups.tst:64
# Input is:
F := AbelianPcpGroup([0,0,0]);;
# Expected output:
# But found:
Error, Variable: 'AbelianPcpGroup' must have a value
########
########> Diff in /Volumes/hudson-fs/workspace/GAP-dev/GAPCOPTS/64build/GAPGMP\
/gmp/GAPTARGET/install/label/fruitloop/GAP-git-snapshot/tst/testinstall/opers/\
MinimalNormalSubgroups.tst:66
# Input is:
MinimalNormalSubgroups(G); 
# Expected output:
[ Pcp-group with orders [ 2 ], Pcp-group with orders [ 2 ], 
  Pcp-group with orders [ 2 ], Pcp-group with orders [ 3 ], 
  Pcp-group with orders [ 3 ], Pcp-group with orders [ 3 ], 
  Pcp-group with orders [ 3 ], Pcp-group with orders [ 5 ], 
  Pcp-group with orders [ 7 ] ]
# But found:
[ <group with 1 generators>, <group with 1 generators> ]
########
########> Diff in /Volumes/hudson-fs/workspace/GAP-dev/GAPCOPTS/64build/GAPGMP\
/gmp/GAPTARGET/install/label/fruitloop/GAP-git-snapshot/tst/testinstall/opers/\
MinimalNormalSubgroups.tst:79
# Input is:
MinimalNormalSubgroups(HeisenbergPcpGroup(3));
# Expected output:
[  ]
# But found:
Error, Variable: 'HeisenbergPcpGroup' must have a value
########

4. Without packages, for G := AbelianGroup([2, 3, 4, 5, 6, 7, 8, 9, 10]) this runs out of memory:

########> Diff in /Volumes/hudson-fs/workspace/GAP-dev/GAPCOPTS/64build/GAPGMP\
/gmp/GAPTARGET/install/label/fruitloop/GAP-git-snapshot/tst/testinstall/opers/\
MinimalNormalSubgroups.tst:118
# Input is:
Collected(List(Set(MinimalNormalSubgroups(G)), Size));
# Expected output:
[ [ 2, 31 ], [ 3, 13 ], [ 5, 6 ], [ 7, 1 ] ]
# But found:
Error, reached the pre-set memory limit
(change it with the -o command line option)
########

5. Not a real problem,may be fixed by sorting:

########> Diff in /Volumes/hudson-fs/workspace/GAP-dev/GAPCOPTS/64build/GAPGMP\
/gmp/GAPTARGET/install/label/fruitloop/GAP-git-snapshot/tst/testinstall/opers/\
MaximalNormalSubgroups.tst:32
# Input is:
List(MaximalNormalSubgroups(D2), StructureDescription);
# Expected output:
[ "D180", "D180", "C180" ]
# But found:
[ "C180", "D180", "D180" ]
########

6. No method found for G constructed with

F := FreeGroup("r", "s");; r := F.1;; s := F.2;;
G := F/[r^(-1)*s^(-1)*r*s, r^18, s^24];;

########> Diff in /Volumes/hudson-fs/workspace/GAP-dev/GAPCOPTS/64build/GAPGMP\
/gmp/GAPTARGET/install/label/fruitloop/GAP-git-snapshot/tst/testinstall/opers/\
MaximalNormalSubgroups.tst:40
# Input is:
Length(MaximalNormalSubgroups(G));
# Expected output:
7
# But found:
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 3rd choice method found for `ConjugacyClasses' on 1 arguments
########

7. Again dependency on polycyclic:

########> Diff in /Volumes/hudson-fs/workspace/GAP-dev/GAPCOPTS/64build/GAPGMP\
/gmp/GAPTARGET/install/label/fruitloop/GAP-git-snapshot/tst/testinstall/opers/\
Socle.tst:18
# Input is:
D := DihedralGroup(IsPcpGroup, 8);;
# Expected output:
# But found:
Error, Variable: 'IsPcpGroup' must have a value
########
########> Diff in /Volumes/hudson-fs/workspace/GAP-dev/GAPCOPTS/64build/GAPGMP\
/gmp/GAPTARGET/install/label/fruitloop/GAP-git-snapshot/tst/testinstall/opers/\
Socle.tst:77
# Input is:
F := AbelianPcpGroup([0,0,0]);;
# Expected output:
# But found:
Error, Variable: 'AbelianPcpGroup' must have a value
########
########> Diff in /Volumes/hudson-fs/workspace/GAP-dev/GAPCOPTS/64build/GAPGMP\
/gmp/GAPTARGET/install/label/fruitloop/GAP-git-snapshot/tst/testinstall/opers/\
Socle.tst:78
# Input is:
G := F / Subgroup(F, [(F.1*F.2)^180, (F.1*F.2^5)^168]);;
# Expected output:
# But found:
Error, the coset enumeration has defined more than 4096000 cosets
########
########> Diff in /Volumes/hudson-fs/workspace/GAP-dev/GAPCOPTS/64build/GAPGMP\
/gmp/GAPTARGET/install/label/fruitloop/GAP-git-snapshot/tst/testinstall/opers/\
Socle.tst:79
# Input is:
Socle(G);
# Expected output:
Pcp-group with orders [ 6, 210 ]
# But found:
Group([ (3,7)(5,9), (5,11)(7,9), (1,5,3)(7,11,9), (2,8,10)(4,6,12), (4,6)
(10,12) ])
########
########> Diff in /Volumes/hudson-fs/workspace/GAP-dev/GAPCOPTS/64build/GAPGMP\
/gmp/GAPTARGET/install/label/fruitloop/GAP-git-snapshot/tst/testinstall/opers/\
Socle.tst:87
# Input is:
G := HeisenbergPcpGroup(3);; IsNilpotentGroup(G);; Socle(G);
# Expected output:
Pcp-group with orders [  ]
# But found:
Error, Variable: 'HeisenbergPcpGroup' must have a value
Group(<6 generators>)
########

[olexandr-konovalov]

Also, there are now 2 diffs in manual examples with default packages. They are harmless, the groups are actually equal. I will update them when the code will be stable. Just to report them in case anyone notices.

########> Diff in [ "./../../lib/grp.gd", 3166, 3170 ]
# Input is:
s:=SubnormalSeries(g,Group((1,2)(3,4)));
# Expected output:
[ Group([ (1,2,3,4), (1,2) ]), Group([ (1,2)(3,4), (1,4)(2,3) ]),
 Group([ (1,2)(3,4) ]) ]
# But found:
[ Group([ (1,2,3,4), (1,2) ]), Group([ (1,2)(3,4), (1,3)(2,4) ]), 
 Group([ (1,2)(3,4) ]) ]
########
########> Diff in [ "./../../lib/grp.gd", 1715, 1718 ]
# Input is:
MaximalNormalSubgroups( g );
# Expected output:
[ Group([ (2,4,3), (1,4)(2,3), (1,3)(2,4) ]) ]
# But found:
[ Group([ (1,2,3), (2,3,4) ]) ]
########

[markuspf]

If I ever have this funny idea to just do minor edits and merge, please someone remind me of this issue.

[markuspf]

@hungaborhorvath I suggest you now look at the state of the code and submit new PRs for issues you find.

We will have to make some statements about testing functionality somewhere, for instance testing of code in the library relying on packages, which then fail because the test is run with the option -A.

[hungaborhorvath]

@markuspf I will look through all 5 PRs and their current states, look through the log, and try to fix the problems I find. It will take some time and I cannot begin until this weekend, maybe not until next weekend. :-(

[fingolfin]

@markuspf I was about to write my concerns about how these merges were perhaps a bit hasty (resp. how I think one should not do merge + edit, but rather request the PR submitter to apply those edits first before doing the merge...). But I see you already seem to have some concerns about it yourself, so I guess that settles it ... ;-).
Anyway, overall, I am glad that you and others work on getting @hungaborhorvath contributions merged. :-)

[markuspf]

Yes, apparently I had to learn this the hard way. I'll certainly not forget the experience though.

[hungaborhorvath]

@markuspf Do not beat yourself up on this, you did a pretty good job at rewriting the methods.

I have now checked the code and made some changes corresponding to the previous PRs, see #705 for maximal normal subgroups, #711 for minimal normal subgroups and socle, and see issue #710 for deciding what should be done about Frattini subgroup computation.

Further, the Sylow- and Hall subgroup PR had a bug, which is corrected in #708, and #706 tries to add abelian filters even if solvability is checked (for better method selection).

[markuspf]

I wasn't beating myself up (at least not over having done things wrong), just about the fact that in my desire to get this moved along I went ahead and merged your PRs creating a lot of work for myself in the process.
In future I will more likely ask the submitter to amend the PR, or, if I propose changes submit PRs onto their PRs.