Regression in the new MTC

[olexandr-konovalov]

I have discovered that Wedderga package tests became broken in the stable-4.10 and master branches (see gap-packages/wedderga#43). Using git bisect lead me to the conclusion that this was introduced in ce04724 which is a part of #2812 by @hulpke.

In GAP 4.9.3 we have:

gap> F:=FreeGroup("a","b","c");;
gap> AssignGeneratorVariables(F);
#I  Assigned the global variables [ a, b, c ]
gap> rels:=[ a^60, b^2*a^-30, c^2*a^-30, b^-1*a*b*a^-19, c^-1*a*c*a^-31, c^-1*b^-1*c*b*a^-45 ];
[ a^60, b^2*a^-30, c^2*a^-30, b^-1*a*b*a^-19, c^-1*a*c*a^-31, 
  c^-1*b^-1*c*b*a^-45 ]
gap> g:=F/rels;
<fp group on the generators [ a, b, c ]>
gap> IsomorphismSpecialPcGroup(g);
[ a, b, c ] -> [ f3^2*f4*f5*f6, f1*f2, f1 ]
gap> Size(g);
240

In stable-4.10 we have:

gap>  F:=FreeGroup("a","b","c");;
gap> AssignGeneratorVariables(F);
#I  Assigned the global variables [ a, b, c ]
gap>  rels:=[ a^60, b^2*a^-30, c^2*a^-30, b^-1*a*b*a^-19, c^-1*a*c*a^-31, c^-1*b^-1*c*b*a^-45 ];
[ a^60, b^2*a^-30, c^2*a^-30, b^-1*a*b*a^-19, c^-1*a*c*a^-31, c^-1*b^-1*c*b*a^-45 ]
gap> g:=F/rels;
<fp group on the generators [ a, b, c ]>
gap> IsomorphismSpecialPcGroup(g);
Error, the coset enumeration has defined more than 4096001 cosets
 at /Users/alexk/GITREPS/gap-stable-4.10/lib/sgpres.gi:2366 called from
NEWTC_Define( DATA, i, a ) at /Users/alexk/GITREPS/gap-stable-4.10/lib/sgpres.gi:3056 called from
NEWTC_DoCosetEnum( freegens, freerels, subgens, aug, trace 
 ) at /Users/alexk/GITREPS/gap-stable-4.10/lib/sgpres.gi:3200 called from
NEWTC_CosetEnumerator( FreeGeneratorsOfFpGroup( G ), RelatorsOfFpGroup( G ), GeneratorsOfGroup( H ), true, false 
 ) at /Users/alexk/GITREPS/gap-stable-4.10/lib/grpfp.gi:3849 called from
Size( C ) at /Users/alexk/GITREPS/gap-stable-4.10/lib/coll.gi:153 called from
<compiled statement>  called from
...  at *stdin*:10
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue

The full backtrace is

brk> Where(10);
NEWTC_Define( DATA, i, a ) at /Users/alexk/GITREPS/gap-stable-4.10/lib/sgpres.gi:3056 called from
NEWTC_DoCosetEnum( freegens, freerels, subgens, aug, trace 
 ) at /Users/alexk/GITREPS/gap-stable-4.10/lib/sgpres.gi:3200 called from
NEWTC_CosetEnumerator( FreeGeneratorsOfFpGroup( G ), RelatorsOfFpGroup( G ), GeneratorsOfGroup( H ), 
 true, false ) at /Users/alexk/GITREPS/gap-stable-4.10/lib/grpfp.gi:3849 called from
Size( C ) at /Users/alexk/GITREPS/gap-stable-4.10/lib/coll.gi:153 called from
<compiled statement>  called from
IsomorphismPcGroup( G ) at /Users/alexk/GITREPS/gap-stable-4.10/lib/pcgsspec.gi:756 called from
<function "unknown">( <arguments> )
 called from read-eval loop at *errin*:1
brk> 

[olexandr-konovalov]

I did git bisect for the second problem described in gap-packages/wedderga#43. It does not show up when GAP started with -A, at least one should start it with default packages. Second, it does not happen each time, so I've put a dozen of calls to WedderburnDecompositionInfo(GroupRing(Rationals,SmallGroup(240,89))); into a test file. Git bisect reported that the commit triggering this is 79b48fa from the same PR #2812 by @hulpke - could you please have a look? I so far did not manage to provide a simpler example which does not require Wedderga, but perhaps you can get some insight from the break loop?

[hulpke]

This is an interesting case, which shows again that FpGroups just can behave rather surprisingly. It is not a regression in code correctness or performance (and I've thus removed the regression label). In particular, it has to do only with the strategy of finding cyclic subgroups, not with performance or correctness of the MTC. The same coset enumeration issue turns up in the 25 years old enumerator inherited from GAP3.

What is happening is that the Size command tries to find a cyclic subgroup of smaller index, which it does in this case. However coset enumeration for this new subgroup turns out to be much harder in this example.

One can further refine the strategy (which I have done in #2895) to make this issue disappear.

Independently, is there a reason for making this an fp group example?

[olexandr-konovalov]

Thanks @hulpke - I will test #2895.

The free group example above occurred in this calculation in the code contributed to Wedderga by Allen Herman:

########> Diff in /circa/scratch/gap-jenkins/workspace/GAP-stable-test/GAPCOPT\
S/64build/GAPTARGET/packages/label/kovacs/GAP-stable-snapshot/pkg/wedderga-4.9\
.4/tst/wedderga07.tst:167
# Input is:
LocalIndicesOfCyclotomicAlgebra(W[27]);
# Expected output:
[ [ infinity, 2 ] ]

# But found:
Error, the coset enumeration has defined more than 4096001 cosets

########

I have managed to extract the group causing the problem from there to make the problem easily reproducible.