Size(g) gives wrong value for presentation aa,ababab,abbab'

[rokicki]

For the following input:

f := FreeGroup("a","b");;
g := f / [ f.1*f.1,f.1*f.2*f.1*f.2*f.1*f.2,f.1*f.2*f.2*f.1*f.2^-1 ];
Size(g);
IDGroup(g);

Observed behaviour

Gap prints:

gap> gap> <fp group on the generators [ a, b ]>
gap> 3
gap> Error, group is not solvable at /Users/rokicki/gapcompile3/gap-4.13.0/lib/grpfp.gi:4286 called from
IsomorphismPcGroup( G 
 ) at /Users/rokicki/gapcompile3/gap-4.13.0/pkg/smallgrp/gap/small.gi:319 called from
<function "IdGroup generic method for groups">( <arguments> )

Expected behaviour

This is the trivial group, so I expect it to print 1 for the size and "[1, 1]" for the group id.

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

 ┌───────┐   GAP 4.13.0 of 2024-03-15
 │  GAP  │   https://www.gap-system.org
 └───────┘   Architecture: aarch64-apple-darwin23-default64-kv9
 Configuration:  gmp 6.3.0, GASMAN
 Loading the library and packages ...
 Packages:   AClib 1.3.2, Alnuth 3.2.1, AtlasRep 2.1.8, AutPGrp 1.11, 
             CRISP 1.4.6, Cryst 4.1.27, CrystCat 1.1.10, CTblLib 1.3.9, 
             FactInt 1.6.3, FGA 1.5.0, GAPDoc 1.6.7, IRREDSOL 1.4.4, 
             LAGUNA 3.9.6, Polenta 1.3.10, Polycyclic 2.16, PrimGrp 3.4.4, 
             RadiRoot 2.9, ResClasses 4.7.3, SmallGrp 1.5.3, Sophus 1.27, 
             SpinSym 1.5.2, StandardFF 1.0, TomLib 1.2.11, TransGrp 3.6.5, 
             utils 0.85
 Try '??help' for help. See also '?copyright', '?cite' and '?authors'

I see the same behavior on MacOS (using ARM64) and Ubuntu (on x86-64).

[rokicki]

Just for completeness, Magma says this is the trivial group:

SetVerbose("InfGrp", 2);
G<x,y> := FPGroup<x,y|x^2, x*y*x*y*x*y, x*y*y*x*y^-1>;
G;
Order(G);

gives

Finitely presented group G on 2 generators
Relations
    x^2 = Id(G)
    (x * y)^3 = Id(G)
    x * y^2 * x * y^-1 = Id(G)
1

[Stefan-Kohl]

Listing the elements also gives the correct result:

gap> AsList(g);
[ <identity ...> ]
gap> Size(g);  # still wrong
3

[james-d-mitchell]

Just to say that I can reproduce this, also in the master branch. Didn't have time to investigate further.

[rokicki]

Here's another one that gets messed up:

Print("abb,acd,bdc,cc,dd");;
f := FreeGroup("a","b","c","d");;
g := f / [ f.1*f.2*f.2,f.1*f.3*f.4,f.2*f.4*f.3,f.3*f.3,f.4*f.4 ];
h := SimplifiedFpGroup(g);
Size(h);
IdGroup(h);
Size(g);
IdGroup(g);

which gives

gap> abb,acd,bdc,cc,dd
gap> gap> <fp group on the generators [ a, b, c, d ]>
gap> <fp group on the generators [ c ]>
gap> 2
gap> [ 2, 1 ]
gap> 4
gap> Error, group is not solvable at /Users/rokicki/gapcompile3/gap-4.13.0/lib/grpfp.gi:4286 called from
IsomorphismPcGroup( G 
 ) at /Users/rokicki/gapcompile3/gap-4.13.0/pkg/smallgrp/gap/small.gi:319 called from
<function "IdGroup generic method for groups">( <arguments> )

[fingolfin]

Thank you for taking the time to report this error! Also thanks to everyone for trying to reproduce it, which is indeed quite simple here. That this group indeed can't be cyclic of order 3 can also be verified using AbelianInvariants(g); and in fact also with pen and paper. So no need for further checks there.

A quick check reveals that this used to work right in GAP 4.9 and is broken since GAP 4.10. Equipped with this knowledge I used the dev/bisect.sh script (after fixing some recent regressions in it) to narrow this issue down to commit 98bd149 from 2018 by @hulpke (introduced via PR #2895) which fixed issue #2892.

For some background, back in GAP 4.9, the entire MTC (modified Todd-Coxeter) implementation in GAP was rewritten from scratch in an heroic effort by @hulpke as the old implementation had serious known issues and was very hard to understand and debug. The new implementation is closely based on the description in the "Handbook of Computational Group Theory" which can be used to help understand it. Still, such a major rewrite always comes with some fallout and in GAP 4.10 a lot of that was cleared up. Seems this particular fix introduced a new issue of its own, not found till today :-/

[fingolfin]

As a temporary workaround, you can apply this patch, which seems to resolve the issue:

diff --git a/lib/grpfp.gi b/lib/grpfp.gi
index b84ded14a..bdd1900ab 100644
--- a/lib/grpfp.gi
+++ b/lib/grpfp.gi
@@ -3858,9 +3858,9 @@ BindGlobal("FinIndexCyclicSubgroupGenerator",function(G,maxtable)
     if t<>fail then
       # do not try to redo the work if the index is comparatively small, as
       # it's not worth doing double work in this case.
-      if Length(t[2][1])<100 then
-        return [ElementOfFpGroup(FamilyObj(One(G)),t[1]),max];
-      fi;
+#       if Length(t[2][1])<100 then
+#         return [ElementOfFpGroup(FamilyObj(One(G)),t[1]),max];
+#       fi;
 
       perms:=List(t[2]{[1,3..Length(t[2])-1]},PermList);
       short:=FreeGeneratorsOfFpGroup(G);

I assume this optimization violates some implicit invariant of the code ("if X holds / is known than Y holds / is known") and needs some tweaking

[fingolfin]

OK, with the "shortcut" that code returns [ a, 4096000 ] but with my patch, it returns [ <identity ...>, 4096000 ]. That looks quite significant...

But I now have to attend a course, so I'll not debug this further for now. (Obviously a fix is already shown above, but we need to verify that the problem reported in #2892 stays fixed -- as far as I can tell, the example there never was turned into a test case, perhaps that could be done now. And finally I think that was also a bit of a performance improvement, so that should also be considered (but IMHO "correctness > speed")

[hulpke]

As a temporary workaround, you can apply this patch, which seems to resolve the issue:

This might hide the bug but does not fix it:

gap> u:=SubgroupNC(g,[g.1]);
gap> hom:=IsomorphismFpGroupByGenerators(u,[u.1]);
gap> RelatorsOfFpGroup(Range(hom));
[ F1^2 ]