Classical naming: failures to name a classical group as what it is

[fingolfin]

The test file tst/working/combined/ClassicalNaturalNaming.tst suggests that naming for certain classical groups is less reliable than in the general.

This may not be an actual "issue" but a normal artifact of these things being randomized; after all, in the "real world" application, we'll just retry the renaming eventually.

Still, I thought it would be good to settle this explicitly, hopefully with some feedback by @aniemeyer .

I've decided to turn this into an issue with concrete reproduces. To this end, I've been running this code for various parameters type, d, and q (requires PR #378, so make sure to git pull the latest master):

ReadPackage("recog", "tst/naming.g");
total:=0;;
for i in [1..100] do
  Reset(GlobalMersenneTwister,i);;
  Print("seed ",i,"\n");
  total := total + TestNaming(type,d,q);
od;
total;

or if you prefer a one-line for easier repetitions:

ReadPackage("recog", "tst/naming.g");;total:=0;;for i in [1..100] do Reset(GlobalMersenneTwister,i);; Print("seed ",i,"\n");total:=total+TestNaming(type,d,q);od;total;

Note that TestNaming invokes RecogniseClassical 20 times, so really we are testing it 20*100=2000 times.

Unitary groups

For $d=6$, $q=2$ we get 21 out of 2000 failures, but other parameters seem fine.

Symplectic groups

For $d=4$ all is good for $q=2,3,5,7,8,11$ (though for 8 it is rather slow). But not so for $q=4,9,13$ (with 2000 (!!!), 790 (!), 101 failures out of 2000). Yes, it always fails for Sp(4,4). It is always "has bad value for isSpContained; expected true, got unknown"

For $d=6$, $q=2$ we get 12 out of 2000 failures, but for larger $d$ and/or $q$ things seem to be fine.

Orthogonal groups in odd dimension

For $d=3$ and $q=2,3,4,5,8,13,16,17$ all is good (for 2000 tests). For $q=7$ we see a few failures (but merely 3 out of 2000 tests):

gap> Reset(GlobalMersenneTwister,8);; TestNaming("SO", 3, 7);
1: SO(3,7) has bad value for isOmegaContained; expected true, got unknown

But it fails a lot when $q$ is 9 or 11 or 19 (namely 26, 46 and 187 out of 20*100=2000 tests), for many random seeds, and for some then even multiple times, e.g.:

gap> Reset(GlobalMersenneTwister,10);; TestNaming("SO", 3, 9);
4: SO(3,9) has bad value for isOmegaContained; expected true, got unknown
11: SO(3,9) has bad value for isOmegaContained; expected true, got unknown

gap> Reset(GlobalMersenneTwister,2);; TestNaming("SO", 3, 11);
1: SO(3,11) has bad value for isOmegaContained; expected true, got unknown
2: SO(3,11) has bad value for isOmegaContained; expected true, got unknown

For $q=3$ we also get elevated failure rates when $d=5, 7, 9, 11, 13, ...$ (namely 11, 3, 3, 2, 9, ...) so maybe for this small field size we just have to live with that.

gap> Reset(GlobalMersenneTwister,16);; TestNaming("SO", 5, 3);
16: SO(5,3) has bad value for isOmegaContained; expected true, got unknown

gap> Reset(GlobalMersenneTwister,22);; TestNaming("SO", 7, 3);
11: SO(7,3) has bad value for isOmegaContained; expected true, got unknown

Orthogonal groups in even dimension

For these we need a slightly different test loop because the sign must be passed as an additional argument to TestNaming:

ReadPackage("recog", "tst/naming.g");
total:=0;;
for i in [1..100] do
  Reset(GlobalMersenneTwister,i);;
  Print("seed ",i,"\n");
  total := total + TestNaming(type,sign,d,q);
od;
total;

Orthogonal groups in even dimension, minus type

For $(d,q)=(6,2)$ we get 18 failures, for $(d,q)=(6,3)$ we get 59 failures. All other parameters seem fine.

Orthogonal groups in even dimension, plus type

Problematic parameters are $(4,8), (4,11), (4,13), (8,4), (8,7), (8,8)$ with, respectively, 2000, 2000, 2000, 117, 2, 14 failures.

For $(8,2)$ and $(8,3)$ the naming is fine but sloooow. And $(8,5)$ is UNBEARABLY slow because of Image(ProjectiveActionHomomorphismMatrixGroup(grp)) -- we talked about this before of course; I'll loook some more into it. (UPDATE: logged as #380 and addressed by PR #386, which also makes $(8,2)$ and $(8,3)$ faster)

For $(10,2)$, $(10,3)$, $(10,4)$, $(10,5)$ I see 24, 2, 2, 1 failures.

For $(12,2)$, $(12,3)$, $(12,4)$, $(12,5)$ I see 158, 124, 115, 99, failures.

For $(14,2)$, $(14,3)$, $(14,4)$, $(14,5)$ I see 56, 5, 5, 8, failures.

[fingolfin]

The cases SO(+1,4,q) for $q=8$ or $q\geq 11$ are handled by this piece of code:

    elif d = 4 and (q = 8 or q >= 11) then
        if recognise.needPlusMinus = false then
            recognise.needPlusMinus := true;
            return NotEnoughInformation;
        fi;
        if not IsSubset(recognise.plusminus,[[1,1],[1,-1],[-1,-1]]) then
            return TemporaryFailure;
        fi;

Looking at Magma, it does this instead:

    elif d eq 4 and (q eq 8 or q ge 11) then
        prop := [PropPlusPlus(grp), PropPlusMinus(grp), 
                 PropMinusMinus(grp)];
        return FindExample( grp, prop, N+10 );