wrong `Size` for a `RecognizeGroup` result

[ThomasBreuer]

With the following input, I get a too large Size for a RecognizeGroup result in almost half of the attempts.

G:= AtlasSubgroup( "B", 2 );;  # the group 2^(1+22).Co2
Ggens:= GeneratorsOfGroup( G );;

F:= GF(2);;
M:= GModuleByMats( Ggens, F );;
facts:= MTX.CompositionFactors( M );;
Length( facts );  # 27
S:= First( facts, x -> x.dimension = 22 );;
C:= GroupWithGenerators( S.generators );;  # isom. with Co2
nice:= NiceMonomorphism( C );;
permgens:= List( S.generators, x -> ImagesRepresentative( nice, x ) );;
memgens:= GeneratorsWithMemory( permgens );;
find:= AtlasProgram( "Co2", "find" );;
res:= ResultOfBBoxProgram( find.program, GroupWithGenerators( memgens ) );;
slps:= List( res, SLPOfElm );;
stdmats:= List( slps, x -> ResultOfStraightLineProgram( x, Ggens ) );;

mx:= List( Maxes( CharacterTable( "Co2") ), CharacterTable );;
pos:= PositionsProperty( mx, x -> Size( x ) mod 23 = 0 );  # [ 9 ]
mx{ pos };  # [ CharacterTable( "M23" ) ]
restprg:= AtlasProgram( "Co2", "maxes", pos[1], 1 );;  # std. gens. of M23
stdrestmats:= ResultOfStraightLineProgram( restprg.program, stdmats );;
U:= GroupWithGenerators( stdrestmats );;  # 2^(1+22).M23 (or a subgroup)

M2:= GModuleByMats( stdrestmats, F );;
bases:= MTX.BasesCompositionSeries( M2 );;
Length( bases[7] );  # 198

ind:= MTX.InducedActionSubmodule( M2, bases[7] );;
U:= GroupWithGenerators( ind.generators );;

LoadPackage( "recog" );
Size( RecognizeMatrixGroup( U ) ) = 2^23 * Size( MathieuGroup( 23 ) );  # true
# So the 198x198 matrices really generate 2^(1+22).M23

mats:= ind.generators;;
mx:= AtlasProgram( "M23", "maxes", 7 );  # 23:11 in M23
res:= ResultOfStraightLineProgram( mx.program, ind.generators );;

sizes:= [];
for i in [ 1 .. 150 ] do
  Add( sizes, Size( RecognizeGroup( GroupWithGenerators( res ) ) ) );
od;
Collected( sizes );  # in my experiments, about half of the orders are correct
2^23 * 23 * 11;

The wrong results are usually twice the group order, and rarely I get four times the group order.

[fingolfin]

Thanks @ThomasBreuer. I took your example and adjusted it so that the matrices for U are directly input. That makes it possible to run everything in under a second instead of 3.5 minutes or so.

In there, one can set the variable seed to init the RNGs; values 1-4 lead to incorrect behavior, 5 and 6 produce "good" results.

So that makes it very convenient to play with it for further debugging.

bugU.g.gz

[ThomasBreuer]

Update:
The situation is even worse.

• Construct an element x with memory in the group generated by stdrestmats such that x has order 46.
  Then evaluating the SLP of x in ind.generators yields an element of order 23.
  This means that already the answer Size( RecognizeMatrixGroup( U ) ) is not correct.
• When I try Size( RecognizeGroup( GroupWithGenerators( ind.generators ) ) ) multiple times then I get always 85571854663680, which is the order of 2^(1+22).M23.
• When I try Size( RecognizeMatrixGroup( Group( stdrestmats ) ) ) then I get eventually (after 15 minutes) 10953197396951040, which is 2^23 * 1305722880. If we believe that the group is a subgroup of 2^(1+22).Co2 then the returned group order corresponds to a subgroup of index 32400, but this cannot happen.

[fingolfin]

With the original U, the problem seems to be the kernel, which is too large.... and it is really confusing:

gap> ri:= RecognizeGroup( GroupWithGenerators( res ) );; Size(ri);
F dim= 198 field=2  0
4244635648
gap> kri:=KernelRecogNode(ImageRecogNode(ri));
<recognition node LowerLeftPGroup Size=16777216 Dim=198 Field=2>

So this indicates a factor of $2^{24}$, i.e., the result is twice as big as it should be.

Let's just look at the kernel then:

gap> K:=Group(GeneratorsOfGroup(Grp(kri))); Size(RecognizeGroup(K));
<matrix group with 24 generators>
F dim= 198 field=2  0
4194304
gap> StringPP(last);
"2^22"

So a fresh recognition run now considers this group to have order $2^{22}$, i.e., a factor four less than before, and actually half of what it should be!

So, yeah, something is wrong in the LowerLeftPGroup code.

[fingolfin]

The kernel generators are computed by FindKernelLowerLeftPGroup, it produced 24 generators which are supposed to form a pcgs. The code then accordingly does:

  SetSize(ri,p^Length(ri!.gensNvectors));

so it computes the size based on the number of generators, i.e., $2^{24}$.

But the two final generators are equal to the identity! Hence this is actually a group of order $2^{22}$.