Errors (or crash)

[fingolfin]

Consider this code:

gens:=[ [ [ 0*Z(3), Z(3^2)^2 ], [ Z(3^2)^2, Z(3^2) ] ], [ [ 0*Z(3), Z(3^2) ], [ Z(3^2)^3, Z(3^2)^5 ] ],
  [ [ Z(3^2)^2, Z(3^2)^6 ], [ Z(3^2)^3, Z(3)^0 ] ], [ [ Z(3^2)^3, Z(3^2)^5 ], [ Z(3^2)^3, 0*Z(3) ] ],
  [ [ Z(3^2)^3, Z(3^2)^2 ], [ Z(3^2), Z(3^2)^2 ] ], [ [ Z(3^2)^7, Z(3^2)^3 ], [ Z(3^2)^6, Z(3)^0 ] ],
  [ [ Z(3^2)^7, Z(3^2)^3 ], [ Z(3^2), Z(3^2) ] ], [ [ Z(3^2)^6, Z(3^2)^6 ], [ Z(3), Z(3^2) ] ],
  [ [ Z(3^2)^7, Z(3) ], [ Z(3), 0*Z(3) ] ], [ [ Z(3), Z(3^2)^2 ], [ 0*Z(3), Z(3) ] ],
  [ [ Z(3^2)^7, Z(3^2)^5 ], [ Z(3^2)^2, Z(3^2)^3 ] ], [ [ Z(3^2)^2, Z(3^2) ], [ Z(3^2)^3, Z(3^2)^6 ] ],
  [ [ Z(3^2)^2, Z(3^2) ], [ Z(3^2)^7, 0*Z(3) ] ], [ [ Z(3), Z(3^2)^5 ], [ 0*Z(3), Z(3)^0 ] ],
  [ [ Z(3^2), Z(3^2)^5 ], [ Z(3^2)^5, Z(3^2)^6 ] ], [ [ Z(3^2)^2, Z(3)^0 ], [ Z(3^2)^6, Z(3^2) ] ],
  [ [ Z(3^2)^3, Z(3^2) ], [ Z(3^2), Z(3) ] ], [ [ Z(3^2)^3, 0*Z(3) ], [ Z(3^2)^3, Z(3^2) ] ],
  [ [ Z(3^2)^2, 0*Z(3) ], [ Z(3^2)^3, Z(3^2)^6 ] ], [ [ Z(3^2)^3, Z(3^2)^5 ], [ Z(3^2)^6, Z(3^2)^2 ] ],
  [ [ Z(3^2)^5, Z(3^2)^5 ], [ Z(3^2)^3, 0*Z(3) ] ], [ [ Z(3^2)^2, Z(3^2)^5 ], [ Z(3^2)^7, 0*Z(3) ] ],
  [ [ Z(3^2)^5, Z(3)^0 ], [ 0*Z(3), Z(3^2)^3 ] ], [ [ Z(3^2)^5, Z(3^2)^6 ], [ Z(3^2)^5, Z(3^2) ] ],
  [ [ Z(3^2)^7, Z(3)^0 ], [ Z(3^2), Z(3^2)^3 ] ], [ [ Z(3^2)^5, Z(3^2)^7 ], [ Z(3^2)^7, Z(3)^0 ] ],
  [ [ Z(3^2)^6, 0*Z(3) ], [ Z(3^2)^3, Z(3^2)^2 ] ], [ [ Z(3^2)^6, 0*Z(3) ], [ Z(3^2)^7, Z(3^2)^2 ] ],
  [ [ Z(3^2)^6, Z(3) ], [ Z(3^2)^3, Z(3^2)^3 ] ], [ [ Z(3)^0, Z(3)^0 ], [ Z(3^2)^6, Z(3^2)^5 ] ],
  [ [ Z(3^2)^7, Z(3^2)^7 ], [ Z(3), Z(3^2)^6 ] ], [ [ Z(3^2)^6, Z(3^2)^6 ], [ Z(3^2)^5, Z(3)^0 ] ],
  [ [ Z(3^2)^7, Z(3^2) ], [ Z(3^2)^2, Z(3^2)^7 ] ], [ [ Z(3^2)^7, Z(3^2)^6 ], [ Z(3)^0, Z(3^2)^6 ] ],
  [ [ Z(3^2)^2, Z(3^2) ], [ Z(3^2)^5, Z(3^2) ] ], [ [ Z(3^2)^7, Z(3^2)^6 ], [ Z(3^2)^6, 0*Z(3) ] ] ];

gm := GroupWithMemory(gens);

Reset(GlobalRandomSource, 30);;
Reset(GlobalMersenneTwister, 30);;
S := StabilizerChain(gm,rec( Projective := false,
        Cand := rec( points := One(gens[1]), ops := [OnLines,OnLines] ) ) );

Running it results in an error or even crash (depending on the orb version).

TODO: add more details from discussion at #15

[fingolfin]

The error is this:

gap> S := StabilizerChain(gm,rec( Projective := false,
>         Cand := rec( points := One(gens[1]), ops := [OnLines,OnLines] ) ) );
Error, hash function not applicable to key of type plain list of small finite field elements in
  HTValue( orb!.ht, ob ) at GAPROOT/pkg/orb/gap/orbits.gi:443 called from
Position( o, p ) at GAPROOT/pkg/genss/gap/genss.gi:803 called from
GENSS_RandomElementFromAbove( S, layer ) at GAPROOT/pkg/genss/gap/genss.gi:883 called from
GENSS_StabilizerChainInner( stabgens, false, layer + 1, cand, opt, S ) at GAPROOT/pkg/genss/gap/genss.gi:898 called from
GENSS_StabilizerChainInner( stabgens, false, layer + 1, cand, opt, S ) at GAPROOT/pkg/genss/gap/genss.gi:898 called from
GENSS_StabilizerChainInner( GeneratorsOfGroup( grp ), false, 1, cand, opt, false ) at GAPROOT/pkg/genss/gap/genss.gi:1139 called from
...  at *stdin*:25
type 'quit;' to quit to outer loop
brk> ob;
[ Z(3)^0, Z(3^2)^6 ]
brk> orb!.ht!.hfd;
[ 1009, 3 ]

What seems to happen is that ChooseHashFunction was used to select a hash function, and the initial input consisted of vectors over GF(3). But later on there are vectors which are not defined over GF(3), just over an extension field, and so the hash function fails.

IMHO this hints at a fundamental design deficiency with the hash tables implemented in orb, resp. how they are used here: It is not sufficient to just look at the seeds of an orbit, we also must consider the action on those vectors.

I've also seen other variants of this. And there are even worse things, like this:

InstallGlobalFunction( ORB_HashFunctionForGF2Vectors,
function(v,data)
  if not IsGF2VectorRep(v) then return 0; fi;
  return HashKeyBag(v,101,2*GAPInfo.BytesPerVariable,data[2]) mod data[1] + 1;
end );

That function should not be return 0 there, but rather fail, because a common cause for triggering this return is that somehow compressed and non-compressed vectors get mixed; but silently accepting the non-compressed vectors, we violate the crucial invariant "equal objects in the hash table must have equal hashes" which can lead to wrong results later on.

So absent a strong enough type system, a purely guess based heuristic for which hash functions to use won't work. There must be a way to provide further information.

A possible solution might be to audit all "recursive" calls to Orb (and Stab??) in genss, to make sure they pass an explicit hashfunc, probably copied from the higher up level. That won't address all instances of this problem but at least some.

[fingolfin]

Hmm, but the bug also goes away if I use Group instead of GroupWithMemory (I tried with 10000 different random seeds)

[fingolfin]

OK, major difference: with Group, all the group generators are stored as immutable compressed matrices. With GroupWithMemory the generators are memory objects wrapping mutable plain lists of lists.

As a result, the orbit of the former consists of compressed vectors (well, except for the first one, which is a concern of its own sigh) while for the latter the orbits consists of uncompressed vectors (i.e., plain lists of field elements).

I have a fix which changes GroupWithMemory to remove this discrepancy (which may be a good idea anyway), for the GAP side. But this just papers over the core issue:

because we end up using plain lists, they don't store the parent field; and thus in the recursion, the code initializing the orbit and hash tables initially only sees the subfield, not the full field, and thus things break down.

This can be fixed by ensuring that only proper "vector obj" are used for the orbit, but for various reasons I am not sure this is realistic (plus this code is also meant to be usable together with cvec and its compressed matrix type).

Another fix would be to explicitly transfer this kind of information "down the line" -- e.g. by explicitly applying the hash function chosen at the top level to the next level... I'll try and see if I can make that work.

BTW orb has special code to deal with the case of matrices acting on vectors, and it gets applied here, it just isn't enough... To quote it:

            # Handle the special case of matrices over a finite field
            # acting on vectors with OnRight or OnLines, because the
            # field of the vector could be smaller than the field of the
            # matrices:
            if not(IsBound(re.hf)) and not(IsBound(re.forflatplainlists)) and
               IsRowVector(x) and IsFFECollection(x) and
               ForAll(o.gens,IsFFECollColl) then
                f := FieldOfMatrixList(o.gens);
                if Size(DefaultField(x)) < Size(f) then
                    o.ht := HTCreate(x*PrimitiveRoot(f),re);
                else
                    o.ht := HTCreate(x,re);
                fi;
            else
                o.ht := HTCreate(x,re);
            fi;

[fingolfin]

I think I have tracked it down (or at least one major cause for it triggering this error in the ClassicalMaximal package test suite), see gap-system/gap#5907