Reproducible errors on small solvable groups

[hulpke]

This rather naive loop:

 for p in [2,3,5,7] do for d in [3..10] do for q in [2,3,5,7] do
 g:=SylowSubgroup(GL(d,p),q); RecognizeGroup(g);od;od;od;

quickly runs into errors. The first is a CopySubMatrix with a matrix in a too-generic representation (I will add a fallback method), but there are more which might have to do with objects getting corrupted (I get entries over a non-prime field).

[ssiccha]

I re-ran it with the current master branch and now it throws almost no errors for d in [3..5]. Leaving out p=2, there are two errors due to recog related to passing invalid elements to FFE operations. One seldomly also occurrs for d <=5:

Error, FFE operations: <divisor> must not be zero in
  x := x[pos][pos] ^ -1 * x; at /home/sergio/source/pkg/recog//gap/projective.gi:168 called from 
h!.fun( h!.data, o ) at /home/sergio/source/pkg/orb//gap/homwdata.gi:36 called from
ImageElm( Homom( ri ), g ) at /home/sergio/source/pkg/recogbase//gap/recognition.gi:697 called from
slpforelement( ri )( ri, x ) at /home/sergio/source/pkg/recogbase//gap/recognition.gi:684 called from
SLPforElement( riker, n ) at /home/sergio/source/pkg/recogbase//gap/recognition.gi:713 called from
slpforelement( ri )( ri, x ) at /home/sergio/source/pkg/recogbase//gap/recognition.gi:684 called from
...  at *stdin*:42

Only for d > 5 I also get

Error, LogFFE: <z> must be a nonzero finite field element in
 return data.c ^ (LogFFE( DeterminantMat( m ), data.z ) mod data.gcd)
 ; at /home/sergio/source/pkg/recog//gap/projective.gi:137 called from 
...

For p=2 and d > 5 I get an error due to orb:

Error, no method found! For debugging hints type ?Recovery from NoMethodFound
The 1st argument is 'fail' which might point to an earlier problem
Error, no 1st choice method found for `mod' on 2 arguments at /home/sergio/source/gap_source/lib/methsel2.g:241 called from
NumberFFVector( v, 2 ) mod data[1] at /home/sergio/source/pkg/orb//gap/hash.gi:616 called from
ht!.hf( x, ht!.hfd ) at /home/sergio/source/pkg/orb//gap/hash.gi:312 called from
HTValue( orb!.ht, ob ) at /home/sergio/source/pkg/orb//gap/orbits.gi:446 called from
Position( o, p ) at /home/sergio/source/gap_source/pkg/genss-1.6.4/gap/genss.gi:1310 called from
SiftGroupElementSLP( ri!.stabilizerchain, x 
 ) at /home/sergio/source/pkg/recog//gap/projective.gi:104 called from
...  at *stdin*:41

which is calling ORB_HashFunctionForShortGF2Vectors with v := [ Z(2^2), Z(2^2) ] not being over GF(2). Can basically the same function be used for bigger fields, if we can guarantee that we will not suddenly change the field during the orbit computation?

[fingolfin]

The last issue, with Position( o, p ) failing for an orb orbit o is IMHO a design issue with the hash tables / dictionaries in orb, and the whole idea of automatically guessing a hash function via ChooseHashFunction: This fails to take into account that a single "sample" element for an orbit may be misleading. I.e. while the initial vector may be a GF(2) vector, the acting matrices might be over GF(4) and GF(8), and thus the orbit may contain vectors over GF(4), GF(8) and GF(64). And finally, the user may still try to look for a vector defined over, say GF(32), inside the orbit...

So I think we should extract a bug report for the orb package out of this, and fix it there. For now, I applied a quick fix to my local copy of orb. Now that error is gone, but now it seems to get stuck in an endless loop for p=2, d=6 and q=3.

Skipping over p=2, I could not reproduce any of the other two types of errors @ssiccha describes above. Can you?

[ssiccha]

@fingolfin Trying with the current master and the current version of recog I still can reproduce both errors via

gap> while true do                                                                                     
> for p in [3] do for d in [5..5] do for q in [2,3,5,7] do                                             
>  g:=SylowSubgroup(GL(d,p),q); RecognizeGroup(g);od;od;od;                                            
> od;

and

gap> while true do
> for p in [3] do for d in [6..6] do for q in [2,3,5,7] do
>  g:=SylowSubgroup(GL(d,p),q); RecognizeGroup(g);od;od;od;
> od;

E.g. I get

Error, FFE operations: <divisor> must not be zero in
  x := x[pos][pos] ^ -1 * x; at /home/sergio/projects/gap-pkg/recog//gap/projective.gi:168 called from 
RECOG.HomNormLastBlock( data, x 
 ) at /home/sergio/projects/gap-pkg/recog//gap/projective.gi:177 called from
func( C[i] ) at /home/sergio/projects/gap-master/lib/coll.gi:746 called from
List( GeneratorsOfGroup( G ), function ( x )
      return RECOG.HomNormLastBlock( data, x );
  end ) at /home/sergio/projects/gap-pkg/recog//gap/projective.gi:177 called from
CallFuncList( db[i].method, methargs 
 ) at /home/sergio/projects/gap-pkg/recog//gap/base/methsel.gi:107 called from
CallMethods( allmethods, 10, ri, H 
 ) at /home/sergio/projects/gap-pkg/recog//gap/base/recognition.gi:456 called from
...  at *stdin*:55
you can replace <divisor> via 'return <divisor>;'
brk> data;
rec( blocks := [ [ 1, 2 ], [ 3, 4 ] ] )
brk> x;
[ [ Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3) ], [ 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3) ], 
  [ 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0 ], [ 0*Z(3), 0*Z(3), Z(3), 0*Z(3) ] ]
brk> pos;
3
brk> g;
<matrix group of size 1024 with 4 generators>
brk> 

[fingolfin]

Aha, so in effect, you do this (and now I can reproduce it, too):

g:=SylowSubgroup(GL(5,3),2); while true do RecognizeGroup(g); od;

[ssiccha]

Yes, I could have been a bit clearer about that. ^^

[fingolfin]

I fixed the code dealing with block scalar matrices, which takes care of most of the errors, here, I think. The following problems remain:

First off, RecognizeGroup(SylowSubgroup(GL(6,2),3)); runs into an endless loop, and keeps adding and adding generators to the kernel. Narrowing this further down gets us to this test case:

gens:=Z(2)^0*[
[[0,0,1],[1,0,0],[0,1,0]],
[[0,0,1],[Z(2^2),0,0],[0,Z(2^2)^2,0]],
[[0,0,1],[Z(2^2)^2,0,0],[0,Z(2^2),0]],
[[0,0,Z(2^2)],[Z(2^2),0,0],[0,Z(2^2),0]],
[[0,0,Z(2^2)],[Z(2^2)^2,0,0],[0,1,0]],
[[0,0,Z(2^2)^2],[Z(2^2)^2,0,0],[0,Z(2^2)^2,0]],
[[0,1,0],[0,0,1],[1,0,0]]
];
g:=Group(gens);
r:=RecognizeGroup(g);

which results in

#I  Giving up desperately...

<failed recoginfo GoProjective Dim=3 Field=4
 F:<recoginfo (projective) C3C5 Dim=3 Field=4
    F:<recoginfo DiagonalMatrices Dim=1 Field=4>
    K:<recoginfo (projective) ReducibleIso Dim=3 Field=2
       F:<recoginfo (projective) BlockLowerTriangular Dim=3 Field=2
          F:<recoginfo (projective) BlockDiagonal Dim=3 Field=2
             F:<recoginfo (projective) BlocksModScalars Dim=3 Field=2
                F:<recoginfo (projective) NotAbsolutelyIrred Dim=2 Field=2
                   F:<recoginfo (projective) TrivialProjectiveGroup Size=1 Dim=1 Field=4>
                   K:<recoginfo (projective) BiggerScalarsOnly Dim=2 Field=2
                      F:<recoginfo (projective) StabilizerChain Size=3 Dim=2 Field=2>
                      K:<trivial kernel>>
                K:<trivial kernel>
             K:<trivial kernel>
          K:<trivial kernel>
       K:<trivial kernel>>
 K:has no kernel>

So this suggests the C3C5 code may have a problem.

The other problem is that in several of these examples, recognition goes through, but produces the wrong sizes -- in one case, the size is even too large!

[fingolfin]

One particulary "nice" minimal example which leads to bad recognition is this cyclic (!) matrix group:

g:=Group([ [ 0*Z(3), Z(3)^0 ], [ Z(3), 0*Z(3) ] ]);
# find issue
repeat r:=RecognizeGroup(g); until Size(r) <> Size(g);

The group has size 4, but is sometimes detected as size 2 (curiously, I found this example when looking into a case were the final size was too large, not too small).

Anyway, this also reminds me that ideally, we should add tests cases for these things. And perhaps not just test cases that involve calling the recognition code on some input code; rather, it would be good to develop a testing framework that allow us to test recognition methods in isolation (i.e. as unit tests, possibly with help of mock objects). The idea is that these tests should stress test individual methods, to see if they correctly reject input they cannot handle, and also deal correctly with input they should be able to deal with it.

[fingolfin]

I think this last example (2x2 over GF(3)) is closely related to issue #11.

[ssiccha]

If #280 gets merged, this should also fix some of the cases discussed here. A case in this issue which did not get fixed yet is this one: https://github.com/gap-packages/recog/issues/13#issuecomment-351240520.