`Error, LogFFE: <z> must be a nonzero finite field element` due to bug in `NotAbsolutelyIrred` recognition method resp. `RECOG.WriteOverBiggerFieldWithSmallerDegree`

[fingolfin]

Consider this input:

h := GL(3,5^2);;
b := Basis(VectorSpace(GF(5),Elements(GF(5^2))));;
gens := List(GeneratorsOfGroup(h),y->BlownUpMat(b,y));;
g := GroupWithGenerators(gens);;
mat:=Z(5)^0 * [
  [ 2, 3, 2, 1, 4, 0 ],
  [ 1, 1, 0, 1, 4, 0 ],
  [ 0, 0, 1, 3, 2, 3 ],
  [ 0, 1, 0, 2, 3, 1 ],
  [ 0, 1, 2, 0, 2, 2 ],
  [ 1, 4, 2, 1, 1, 0 ],
];;
Reset(GlobalRandomSource,10);; Reset(GlobalMersenneTwister,10);; ri:=RecognizeGroup(g); mat in ri;

It results in this error:

K dim=   6 field=5  0
<recognition node GoProjective Dim=6 Field=5
 F:<recognition node (projective) ProjDeterminant Dim=6 Field=5
    F:<recognition node Pcgs Size=2>
    K:<recognition node (projective) NotAbsolutelyIrred Dim=6 Field=5
       F:<recognition node (projective) ProjDeterminant Dim=3 Field=25
          F:<recognition node Pcgs Size=3>
          K:<recognition node (projective) ClassicalNatural Comment=SL(3,25)_StabilizerChain Size=50778000000 Dim=3 Field=25>>
       K:<recognition node (projective) BiggerScalarsOnly Dim=6 Field=5
          F:<recognition node (projective) StabilizerChainProj Size=3 Dim=2 Field=5>
          K:<trivial kernel>>>
 K:<recognition node DiagonalMatrices Dim=6 Field=5
    F:<recognition node Scalar Dim=1 Field=5>
    K:<trivial kernel>>
Error, LogFFE: <z> must be a nonzero finite field element
*[1] LogFFE( DeterminantMat( m ), data.z )
     in unknown function
   @ ~/Projekte/GAP/repos/pkg/gap-packages/recog/gap/projective.gi:154
 [2] h!.fun( h!.data, o )
     in ImageElm( h, o ) "for a mapping by function with data and an object"
   @ ~/Projekte/GAP/gap/pkg/orb/gap/homwdata.gi:36
 [3] ImageElm( Homom( ri ), g )
     in SLPforElementGeneric( ri, g )
   @ ~/Projekte/GAP/repos/pkg/gap-packages/recog/gap/base/recognition.gi:782
 [4] slpforelement( ri )( ri, x )
     in SLPforElement( ri, x )
   @ ~/Projekte/GAP/repos/pkg/gap-packages/recog/gap/base/recognition.gi:764
 [5] SLPforElement( rifac, gg )
     in SLPforElementGeneric( ri, g )
   @ ~/Projekte/GAP/repos/pkg/gap-packages/recog/gap/base/recognition.gi:786
...  at *stdin*:13
type 'quit;' to quit to outer loop
brk>

It's a real issue, in RECOG.WriteOverBiggerFieldWithSmallerDegree there is no verification check to ensure that the inputs are really what they are supposed to be. This is part of the NotAbsolutelyIrred recognition method.

This methods rewrites $(kd) \times (kd)$ matrices over GF(q) to $d \times d$ matrices over $GF(q^k)$. In the example at hand, $6\times 6$ matrices over GF(5) into $3\times3$ matrices over GF(25).

A simple fix would be to e.g. compute the rank of each $k \times k$ block: it must either be a zero block, or else have full rank. But this sounds expensive. Not sure if we have a much better option.

[fingolfin]

OK after discussing with @SoongNoonien I think what we can do is this: our code chooses a basis of length $k$ for the large field over the small field. And corresponding to that, we may obtain $k\times k$ matrices $M_1,\dots,M_k$ over the small field (I am not yet sure if the code actually computes these explicitly or not, but they are there implicitly at least).

The code in RECOG.WriteOverBiggerFieldWithSmallerDegree looks at each $k\times k$ block $B$ and from a single row or column in it, determines the coefficients $\lambda_1,\dots,\lambda_k$ such that $B = \sum \lambda_i M_i$.

The obvious correctness check is now to actually compute the right side of that equation and compare it against the block B.