Membership test fails if element is not in group

[ssiccha]

An S_n acting on k-sets is recognised correctly:

SnOn2Sets := Action( SymmetricGroup(100), Combinations( [1..100], 2 ), OnSets );;
r := RecogniseGroup( SnOn2Sets );

But if I try to check membership of an element that is not in the group via

g := PseudoRandom( SymmetricGroup( 4950 ) );;
g in r;

I get the following error:

Error, List Element: <list>[1] must have an assigned value in
  h[i] := Intersection( List( gams, function ( t )
            return T[t];
        end ) )[1]; at /home/sergio/source/pkg/recog//gap/snksetswrsr.gi:448 called from 
RECOG.FindImageJellyfish( el, data.T, data.seen 
 ) at /home/sergio/source/pkg/recog//gap/snksetswrsr.gi:465 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( ri, el ) at /home/sergio/source/pkg/recogbase//gap/recognition.gi:862 called from
...  at line 5 of *stdin*
you can 'return;' after assigning a value

I think the problem is that FindImageJellyfish does not check for its 'applicability'. I will have a look into that.

[hulpke]

This is not just here, but in general -- the recognition trees do not test well for membership, if the element is outside the group.

[ssiccha]

I'll just make a small list here:

• S_n acting on k-sets:
  Action( SymmetricGroup(100), Combinations([1..100], 2), OnSets )
• SL: SL(4,5^2).
• C5: G := GL(4,5); G := Group( G.1, G.2, Z(5^2) * One(G) )
• C6 looks fine: RECOG.MakeC6Group(Sp(4,5),Sp(4,5),3)[1]
• ...

[fingolfin]

Yes, this is a general problem, but also one that can be fixed in a relatively uniform manner. I have a pretty good idea what needs to be changed where. Let's see.

[fingolfin]

BTW, you can also get it into a hissy fit if you look for a permutation in a matrix group, or vice versa.

[fingolfin]

I think I was wrong, and instead of a "uniform" solution, what we have to do is to add lots of input validations to homomorphism methods. This then serves triple purpose:

• it fixes use cases like the one described in this issue
• it can fixe incorrect recognition result, e.g. if internally to catch situations where we failed to correctly recognize something (e.g. a kernel is too small, but as we sift more elements into it, a homomorphism may fail to apply -- which we then must detect, and report to the higher level)
• it enhances our confidence that all computations are actually correct.

I added some more of these checks in my recent commits. This takes care of your examples, I think.

[ssiccha]

@fingolfin To expand on this: Every homomorphism phi : G -> H should provide a function which checks for an element x whether phi is applicable to x in the mathematical sense.

Not sure whether this works always: If G <= GF(d,q) there should be a group G <= GG <= GF(d,q) s.t. phi is applicable to all elements of GG. Think of G being reducible and GG the group of (wrt to the right basis) triangular block matrices.
This should be a somewhat uniform solution (for the cases where it works).

[fingolfin]

I am not sure what your example is meant to say, but I also don't see any serious issues here: One could indeed use two functions: one to perform general sanity checks, the other to compute the actual image under the morphism. The first function would e.g. filter out permutations or matrices over the wrong field; it might also filter out matrices which are unsuitable for other reasons (e.g. no diagonal, when the morphism expects diagonal matrices). Things that pass through still may be outside of the group we expect -- but the morphism should be applicable to them, and produce a valid result.

So to stay with the diagonal subgroup example: If we so far only recognized a proper subgroup of the full diagonal subgroup, then applying the morphism to a diagonal matrix outside that proper subgroup may "work", but we'll later (e.g. when computing preimages) notice that something is amiss, and increase the generator set. This is fine, and essentially what happens right now anyway.

The problems I fixed so far were really all of the kind were the matrix considered was not even diagonal; or it was diagonal, but over the wrong field; etc. -- i.e. all things which are cheap to check.

It remains to be determined if having this functionality split across two functions is useful -- so far, I added all those checks to the homomorphisms and/or to functions which select the homomorphisms. If we split those checks off into separate / additional functions, then there should be a reason for that. I can't think of any right now, can you? Anyway, if we later come up with one, we can still do this then.

[ssiccha]

I agree that this is something we can do down the road if we find it useful.

My feeling is, that there are three steps involved in applying a homomorphism.
First of all, there are the general sanity checks which could involve checking whether a vector is compressed or not. Then, there are checks which ensure that the output of the homomorphism will be correct. And then there is actually computing the homomorphism.

The second step in your example would be to check that the given matrix is diagonal and this is what ensures that applying the homomorphism will be correct. All other checks would fall under "implementation details".
I think putting the correctness-checks into a separate function would have the following benefits:

• making it clear which homomorphism can be applied under which circumstances, further enhancing the confidence that results are correct
• for some homomorphisms we would probably have to figure out what such a check would even look like
• the above points could be checked off very systematically
• people who add new methods should be forced to provide such a function.

In contrast, what's to say that some of the more complicated recognition methods don't rely implicitly on other methods having been executed first, i.e. on the current ranking of the methods? That problem is somehow related to applying homomorphisms since the groups in the tree can grow.

What do you think?

About the sanity checks: it may make sense to define a RecognitionTree type which represents the collection of recognition nodes of a group. Then this RecognitionTree could perform most of the sanity checks, in contrast to having to do them "all over the place".