Assertion failure in IsomorphismFpGroupByGeneratorsNC from AllHomomorphismClasses

[improbable-nickkrempel]

Observed behaviour

On this input:

G := PerfectGroup(336, 1);
AllHomomorphismClasses(G, G);
CharacteristicSubgroups(G);
AllHomomorphismClasses(G, G);

The output is:

gap> G := PerfectGroup(336, 1);
L3(2) 2^1 = SL(2,7)
gap> AllHomomorphismClasses(G, G);
[ [ b*a*b^-1*(a*b)^2*a, a*b^-1*a*b*(a*b*a)^2 ] -> [ <identity ...>, <identity ...> ], [ b*a*b^-1*(a*b)^2*a, a*b^-1*a*b*(a*b*a)^2 ] -> 
    [ a^-1*b^-1*(b^-1*a^-1)^2*b^-1*a*b*(b*a)^2*b^2*a, a*b ], [ b*a*b^-1*(a*b)^2*a, a*b^-1*a*b*(a*b*a)^2 ] -> [ b^-1*a^-1*b^-2*a^-1*b^-1*a*(a*b^2*a*b)^2, a^2*b^2*a ] ]
gap> CharacteristicSubgroups(G);
[ Group([  ]), Group([ a^-2 ]), Group([ a, b ]) ]
gap> AllHomomorphismClasses(G, G);
Error, Assertion failure in
  Assert( 0, Length( GeneratorsOfPresentation( pres ) ) = Length( gens ) ); at /home/nickkrempel/Documents/gap-4.10.2/lib/ghomfp.gi:879 called from 
IsomorphismFpGroupByGeneratorsNC( G, gens, nam ) at /home/nickkrempel/Documents/gap-4.10.2/lib/gpfpiso.gi:36 called from
IsomorphismFpGroupByGenerators( Source( hom ), m[1] ) at /home/nickkrempel/Documents/gap-4.10.2/lib/ghomfp.gi:40 called from
IsSingleValued( imgs ) at /home/nickkrempel/Documents/gap-4.10.2/lib/morpheus.gi:1149 called from
MorClassLoop( G, bi, params, 9 ) at /home/nickkrempel/Documents/gap-4.10.2/lib/teaching.g:1010 called from
<function "AllHomomorphismClasses">( <arguments> )
 called from read-eval loop at *stdin*:4
you may 'return;'
brk> 

Expected behaviour

Expect the second call to AllHomomorphismClasses to succeed with the same result as the first call.

Copy and paste GAP banner (to tell us about your setup)

 ┌───────┐   GAP 4.10.2 of 19-Jun-2019
 │  GAP  │   https://www.gap-system.org
 └───────┘   Architecture: x86_64-pc-linux-gnu-default64-kv3
 Configuration:  gmp 6.1.2
 Loading the library and packages ...
 Packages:   AClib 1.3.1, Alnuth 3.1.1, AtlasRep 2.1.0, AutoDoc 2019.05.20, AutPGrp 1.10, Browse 1.8.8, Carat 2.2.3, CRISP 1.4.4, Cryst 4.1.19, CrystCat 1.1.9, 
             CTblLib 1.2.2, FactInt 1.6.2, FGA 1.4.0, Forms 1.2.5, GAPDoc 1.6.2, genss 1.6.5, IO 4.6.0, IRREDSOL 1.4, LAGUNA 3.9.3, orb 4.8.2, Polenta 1.3.8, 
             Polycyclic 2.14, PrimGrp 3.3.2, RadiRoot 2.8, recog 1.3.2, ResClasses 4.7.2, SmallGrp 1.3, Sophus 1.24, SpinSym 1.5.1, TomLib 1.2.8, TransGrp 2.0.4, 
             utils 0.63
 Try '??help' for help. See also '?copyright', '?cite' and '?authors'

[fingolfin]

I can also reproduce this in 4.11.1 and the master branch. I think @hulpke is the person to ask about this code :-).

[stertooy]

Just a remark, but AllHomomorphismClasses(G,H) isn't guaranteed to have the same output every time it's called (random elements of H may be used at some point). The error can be recreated by repeatedly calling AllHomomorphismClasses, so CharacteristicSubgroups most likely has nothing to do with this.

I've recently been using AllHomomorphismClasses a lot (hence my interest in this issue) and never encountered this problem, but then again I mostly plugged in groups created with SmallGroup.

I ran a few quick tests, and encountered the error when running the code below for n = 120, 168, 336, 360 and 504.

gap> G := PerfectGroup( n, 1 );; for i in [1..100] do AllHomomorphismClasses(G,G);; od;

However, when using SL(2,5), PSL(3,2), SL(2,7), AlternatingGroup(6) and PSL(2,8) as input instead of a group created with PerfectGroup, I couldn't recreate the error. Thus, I suspect that PerfectGroup is at least partly to blame.

As a final side note: when using PerfectGroup( 360, 1 ), I also occasionally encoutered the following error/warning instead:

Error, Trying to eliminate all auxillary generators might cause the
size of the presentation to explode. Proceed at risk! at /usr/lib/gap-4.11.1/lib/sgpres.gi:3583 called from
NEWTC_PresentationMTC( aug, 0, nam ) at /usr/lib/gap-4.11.1/lib/ghomfp.gi:872 called from
IsomorphismFpGroupByGeneratorsNC( G, gens, nam ) at /usr/lib/gap-4.11.1/lib/gpfpiso.gi:36 called from
IsomorphismFpGroupByGenerators( Source( hom ), m[1] ) at /usr/lib/gap-4.11.1/lib/ghomfp.gi:43 called from
IsSingleValued( imgs ) at /usr/lib/gap-4.11.1/lib/morpheus.gi:1223 called from
MorClassLoop( G, bi, params, 9 ) at /usr/lib/gap-4.11.1/lib/teaching.g:1013 called from
...  at *stdin*:77
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue

I'm not sure whether or not this is directly related to this issue, or if it should be raised as a separate one, but again this error never occurs when using AlternatingGroup(6) instead...

[hulpke]

The issue has nothing to do with AllHomomorphismClasses but with FpGroups. The problem disappears, when one uses

G := PerfectGroup(IsPermGroup,336, 1);

to create the group as permutation group.

What is happening is that a GHBI on a subgroup is generated. For that, GAP needs to rewrite the presentation in the chosen subgroup generators, which is done by a MTC.

The MTC introduces secondary generators, that need to be eliminated afterwards. This is done with Tietze transformations (at the cost of expanding the total length of the presentation -- thus the rare warning about total length), but apparently in rare cases they eliminate the relator needed to eliminate the generator.
I will submit a PR that fixes this.

(We could change the somewhat surprising behavior of the perfect groups library and not give an FpGroup, but a PermGroup as default.)