Consistency check is needed

[olexandr-konovalov]

#30 emphasises that it would be useful to run some kind of consistency check for the database, to see if there are other groups for which the name may be not set up correctly.

[olexandr-konovalov]

Of course, one would have to implement some heuristics to compare the name and the structure description, to eliminate some obvious cases before checking the rest manually.

gap> checkname(1);
Checking 0 groups of degree 1
gap> checkname(2);
Checking 1 groups of degree 2
[ 2, 1 ] : S(2) is not C2
gap> checkname(3);
Checking 2 groups of degree 3
[ 3, 1 ] : A(3) is not C3
[ 3, 2 ] : S(3) is not S3
gap> checkname(4);
Checking 2 groups of degree 4
[ 4, 1 ] : A(4) is not A4
[ 4, 2 ] : S(4) is not S4
gap> checkname(5);
Checking 5 groups of degree 5
[ 5, 1 ] : C(5) is not C5
[ 5, 2 ] : D(2*5) is not D10
[ 5, 3 ] : AGL(1, 5) is not C5 : C4
[ 5, 4 ] : A(5) is not A5
[ 5, 5 ] : S(5) is not S5
gap> checkname(5);
Checking 5 groups of degree 5
[ 5, 1 ] : C(5) is not C5
[ 5, 2 ] : D(2*5) is not D10
[ 5, 3 ] : AGL(1, 5) is not C5 : C4
[ 5, 4 ] : A(5) is not A5
[ 5, 5 ] : S(5) is not S5
gap> checkname(6);
Checking 4 groups of degree 6
[ 6, 1 ] : PSL(2,5) is not A5
[ 6, 2 ] : PGL(2,5) is not S5
[ 6, 3 ] : A(6) is not A6
[ 6, 4 ] : S(6) is not S6
gap> checkname(7);
Checking 7 groups of degree 7
[ 7, 1 ] : C(7) is not C7
[ 7, 2 ] : D(2*7) is not D14
[ 7, 3 ] : 7:3 is not C7 : C3
[ 7, 4 ] : AGL(1, 7) is not C7 : C6
[ 7, 5 ] : L(3, 2) is not PSL(3,2)
[ 7, 6 ] : A(7) is not A7
[ 7, 7 ] : S(7) is not S7
gap> checkname(8);
Checking 7 groups of degree 8
[ 8, 1 ] : AGL(1, 8) is not (C2 x C2 x C2) : C7
[ 8, 2 ] : AGammaL(1, 8) is not (C2 x C2 x C2) : (C7 : C3)
[ 8, 3 ] : ASL(3, 2) is not (C2 x C2 x C2) : PSL(3,2)
[ 8, 4 ] : PSL(2, 7) is not PSL(3,2)
[ 8, 5 ] : PGL(2, 7) is not PSL(3,2) : C2
[ 8, 6 ] : A(8) is not A8
[ 8, 7 ] : S(8) is not S8
gap> checkname(9);
Checking 11 groups of degree 9
[ 9, 1 ] : 3^2:4 is not (C3 x C3) : C4
[ 9, 2 ] : 3^2:D(2*4) is not (S3 x S3) : C2
[ 9, 3 ] : 3^2:Q(8)=M(9) is not (C3 x C3) : Q8
[ 9, 4 ] : 3^2:8=AGL(1,9) is not (C3 x C3) : C8
[ 9, 5 ] : AGammaL(1, 9) is not (C3 x C3) : QD16
[ 9, 6 ] : 3^2:(2'A(4)) is not ((C3 x C3) : Q8) : C3
[ 9, 7 ] : AGL(2, 3) is not (((C3 x C3) : Q8) : C3) : C2
[ 9, 8 ] : PSL(2, 8) is not PSL(2,8)
[ 9, 9 ] : PGammaL(2, 8) is not PSL(2,8) : C3
[ 9, 10 ] : A(9) is not A9
[ 9, 11 ] : S(9) is not S9
gap> checkname(10);
Checking 9 groups of degree 10
[ 10, 1 ] : A(5) is not A5
[ 10, 2 ] : S(5) is not S5
[ 10, 3 ] : PSL(2, 9) is not A6
[ 10, 4 ] : PGL(2, 9) is not A6 : C2
[ 10, 5 ] : PSigmaL(2, 9) is not S6
[ 10, 6 ] : M(10) is not A6 . C2
[ 10, 7 ] : PGammaL(2, 9) is not (A6 : C2) : C2
[ 10, 8 ] : A(10) is not A10
[ 10, 9 ] : S(10) is not S10

[olexandr-konovalov]

Also, not each group has Name. Perhaps check only those which have a name?

[fingolfin]

I assume your function checkname compares the "name" (if any) of a group to its structure description?

Since most groups have multiple possible descriptions, that won't work.
Instead I'd try to implement a check by starting with the name, then applying
a few transformations to it, then using EvalString to evaluate the result
and finally comparing it to the input group (via Isomorphism, or if we are sure
we get the right permutation representation, then also via a conjugacy test).

Alternatively / in parallel, it might be worth looking at AtlasRep, as I think many of these names are based on the atlas?
Perhaps we should also have a function AtlasDescription or so, which works like StructureDescription but produces output more like what the atlas / primgrp use?

Anyway, for the "transform and evaluate approach", here are some rules that come to mind:

1. Split the name at = and then handle each resulting "part" separately
2. perform many substitutions (where the latter must be followed by a ( and not be preceded by another letter):

• A by AlternatingGroup
• S by SymmetricGroup
• C by CyclicGroup
• M by MathieuGroup
• Q into QuaternionGroup
• L, O+, O- should be the corresponding simple groups
• PSO+, PSO-, POmega+, POmega- etc.
• F (as in F(4,2)) for the finite group of Lie type with diagram F_4
• ...

3. possibly add helpers implementing ASL, AGL, PSigmaL, PGammaL, AGammaL, ... (possibly with a different name to avoid clashes? and the further corresponding substitutions in step 2)
4. convert G x H into DirectProduct(G, H)
5. transform NAME' into DerivedSubgroup(NAME)? But beware e.g. 2'A(4)
6. transform p alone and p^k into ElementaryAbelianGroup(p,k)? Might be better to handle it with the next step, though...
7. convert : into a suitable semidirect product (but that might actually be hard to check if there are multiple possible ones... but perhaps one can just enumerate them all?)
8. likewise for central products G.H; we may have to just construct all as for semidirects... or perhaps we can make some clever guesses based on atlas convention, dunno.

gap> AllPrimitiveGroups(NrMovedPoints,16);
[ 2^4:5, 2^4:D(2*5), AGL(1, 16), (A(4) x A(4)):2, (2^4:5).4, AGL(1, 16):2, 2^4.S(3) x S(3), 2^4.3^2:4,
  AGammaL(1, 16), (S(4) x S(4)):2, 2^4.PSL(4, 2), AGammaL(2, 4), ASL(2, 4):2, AGL(2, 4), ASL(2, 4), 2^4.S(6),
  2^4.A(6), 2^4:S(5), 2^4:A(5), 2^4.A(7), A(16), S(16) ]

[olexandr-konovalov]

Thanks @fingolfin! I started earlier today, and just pushed and submitted where I stopped in #34, without seeing this. It applied some heuristics, but more can be applied, or doing it the way you suggest. I will look at your ideas next.

I think a few open cases not covered by the check would be fine, but for now #34 still reports too many lines to be practically useful...

[olexandr-konovalov]

@fingolfin Good ideas, e.g. they would easily deal with cases like

gap> StructureDescription(PSL(2,9));
"A6"
gap> StructureDescription(PGL(2,9));
"A6 : C2"

[olexandr-konovalov]

Note: StructureDescription may also contain "=", e.g.

gap> G:=PrimitiveGroup(49,29);
7^2:((Q(8)'D(2*3)) x 3)
gap> StructureDescription(G);
"(C7 x C7) : (C3 x (C2 . S4 = SL(2,3) . C2))"

(Although it does not hurt, since we compare the structure description of a group from the library with the structure description of a group constructed by its name, so they should be equal anyway, whenever they have = or not).

[olexandr-konovalov]

@fingolfin pushed next version of #34 with some hybrid approach. Started to work there on parsing names with EvalString. Next, need helper function for group constructions.

I can't suppress error messages (when EvalString fails), but I can imagine creating a log file and grepping for error and warning markers, or writing a test report directly to a file.

gap> PrimGrpNamesCheck(1,8);
Error, Variable: 'AGL' must have a value              
Error, Could not evaluate string.

WARNING : [ 5, 3 ] : AGL(1, 5) is C5 : C4
Error, Variable: 'AGL' must have a value              
Error, Could not evaluate string.

WARNING : [ 7, 4 ] : AGL(1, 7) is C7 : C6
Error, Variable: 'AGL' must have a value              
Error, Could not evaluate string.

WARNING : [ 8, 1 ] : AGL(1, 8) is (C2 x C2 x C2) : C7
Error, Variable: 'AGammaL' must have a value
Error, Could not evaluate string.

WARNING : [ 8, 2 ] : AGammaL(1, 8) is (C2 x C2 x C2) : (C7 : C3)
Error, Variable: 'ASL' must have a value
Error, Could not evaluate string.

WARNING : [ 8, 3 ] : ASL(3, 2) is (C2 x C2 x C2) : PSL(3,2)
                                                      
gap> PrimGrpNamesCheckDegree(1600);
ERROR : [ 1600, 17 ] : PSU(4, 3) is PSU(3,4)
Syntax error: ; expected in stream:1
_EVALSTRINGTMP:=PSU(4, 3):2;
                         ^
ERROR : [ 1600, 18 ] : PSU(4, 3):2 is PSU(3,4) : C2
Syntax error: ; expected in stream:1
_EVALSTRINGTMP:=PSU(4, 3):4;
                         ^
ERROR : [ 1600, 19 ] : PSU(4, 3):4 is PSU(3,4) : C4
gap>

[olexandr-konovalov]

P.S. I was puzzled why [1600,18] worked. It happened that although there was an error in EvalString, it did return a group (which was certainly not the right group, so that was classified as an error):

gap> EvalString("PSU(4, 3):2");
Syntax error: ; expected in stream:1
_EVALSTRINGTMP:=PSU(4, 3):2;
 ^^^^^^^^^^^^^^^^^^^^^^^^^
<permutation group of size 3265920 with 2 generators>

[olexandr-konovalov]

FinInG package provides AGL (and others?):

gap> as := AffineSpace(1,5);
AG(1, 5)
gap> g:=AffineGroup(as);
AGL(1,5)
gap> StructureDescription(g);
"C5 : C4"

[olexandr-konovalov]

WARNING : [ 100, 5 ] : Alt(5) wreath Sym(2) is (A5 x A5) : C2

This should also be doable:

gap> WreathProduct(AlternatingGroup(5),SymmetricGroup(2));
Group([ (1,2,3,4,5), (3,4,5), (6,7,8,9,10), (8,9,10), (1,6)(2,7)(3,8)(4,9)(5,10) ])
gap> StructureDescription(last);
"(A5 x A5) : C2"

[fingolfin]

@alex-konovalov here are some helpers (somewhat crude but sufficient for the task at hand)

AGL := {d,q} -> SemidirectProduct(GL(d, GF(q)), GF(q)^d);
ASL := {d,q} -> SemidirectProduct(SL(d, GF(q)), GF(q)^d);

ASigmaL := function(d, q)
    local G, V;
    G := SigmaL(d, q);
    V := FieldOfMatrixGroup(G) ^ DimensionOfMatrixGroup(G);
    return SemidirectProduct(G, V);
end;

AGammaL := function(d, q)
    local G, V;
    G := GammaL(d, q);
    V := FieldOfMatrixGroup(G) ^ DimensionOfMatrixGroup(G);
    return SemidirectProduct(G, V);
end;

PSigmaL := function(d, q)
    local G, gens;
    G := SigmaL(d, q);
    gens := GeneratorsOfGroup(G);
    if not IsPrimeInt(q) then
        gens := gens{[1..Length(gens)-1]}; # HACK: last generator is Frobenius
    fi;
    return G / Center(Subgroup(G, gens));
end;

PGammaL := function(d, q)
    local G, gens;
    G := GammaL(d, q);
    gens := GeneratorsOfGroup(G);
    if not IsPrimeInt(q) then
        gens := gens{[1..Length(gens)-1]}; # HACK: last generator is Frobenius
    fi;
    return G / Center(Subgroup(G, gens));
end;

[olexandr-konovalov]

For the record: it takes 3 minutes to run

PrimGrpNames:=function()
local deg, i, g;
for deg in [1..4095] do
    for i in [1..NrPrimitiveGroups(deg)] do
        g := PrimitiveGroup(deg,i);
        if HasName(g) then
            Print( [deg, i ], " ", Name(g), "\n" );
        fi;
    od;
od;
end;

to print all names. 19795 primitive groups have names, out of 24558 contained in the library (that is, just above 80% have names).

[olexandr-konovalov]

Many thanks @fingolfin! I've added a commit on your behalf. Now, this case reported as an error:

gap> G:=PrimitiveGroup(10,7);
PGammaL(2, 9)
gap> StructureDescription(G);
"(A6 : C2) : C2"
gap> StructureDescription(PGammaL(2, 9));
"(A6 . C2) : C2"

However,

gap> IdGroup(G);
[ 1440, 5841 ]
gap> IdGroup(PGammaL(2, 9));
[ 1440, 5841 ]

So it's just StructureDescription works differently for the two groups (yes, I know, it's not promised that it returns the same string for isomorphic groups in different representation).

Perhaps for groups for which IdGroup works, I can add one more check.

[fingolfin]

I'd use IdGroup if available and otherwise fall back zo IsomorphismGroups