ONanScottType not working for some primitive groups of degree 3600

[ChristopherRussell]

I noticed that ONanScottType is not working with some primitive groups at degree 3600.

Observed behaviour

gap> for i in [1..33] do
> g:=PrimitiveGroup(3600,i);
> h:=Group(GeneratorsOfGroup(g));
> Print(ONanScottType(g) = ONanScottType(h),"\n");
> od;
false
false
false
false
false
true
false
false
false
false
false
false
false
true
false
true
false
false
false
false
false
true
false
false
false
false
false
false
true
true
true
true
true

Expected behaviour

PrimitiveGroup(d,i) and Group(GeneratorsOfGroup(PrimitiveGroup(d,i)))) should have the same O'Nan-Scott Type

[olexandr-konovalov]

Thank @ChristopherRussell - might this be related to #834? Especially since the manual has a note "for groups of degree up to 2499, O'Nan-Scott types 4a, 4b and 5 cannot occur" so I am curious whether this is now hardcoded somewhere in identification routines.

[olexandr-konovalov]

From an earlier email from @ChristopherRussell - these are groups for which the test fails:

1 - 648000 - 3b - 4c
2 - 1296000 - 3b - 4c
3 - 1296000 - 3b - 4c
4 - 1296000 - 3b - 4c
5 - 2592000 - 3b - 4c
7 - 51840000 - 4c - 4b
8 - 51840000 - 4c - 4a
9 - 51840000 - 4c - 4a
10 - 51840000 - 4c - 4b
11 - 51840000 - 4c - 4b
12 - 51840000 - 4c - 4b
13 - 103680000 - 4c - 4b
15 - 103680000 - 4c - 4b
17 - 103680000 - 4c - 4b
18 - 103680000 - 4c - 4b
19 - 103680000 - 4c - 4b
20 - 103680000 - 4c - 4b
21 - 103680000 - 4c - 4b
23 - 207360000 - 4c - 4b
24 - 207360000 - 4c - 4b
25 - 207360000 - 4c - 4b
26 - 207360000 - 4c - 4b
27 - 207360000 - 4c - 4b
28 - 207360000 - 4c - 4b

[hulpke]

@alex-konovalov No, this has nothing to do with groups not occurring in smaller degrees, but all with an errors in the library code (which did not get tested much for a lack of examples).

I however now get a discrepancy for no.6, and I wonder whether there is a miscommunication about how GAP labels the product action types:

The group has sole A_5^4 which has index 2, it has two normal subgroups of order 3600, so the sole is not simple. The group thus must be a product action of a diagonal group with a C2. This would be 4a in GAP's labelling, or HC in the named classes, unless I'm mistaken.

In GAP's labelling 4c is product action of almost simple with transitive (type PA). I think it actually cannot occur in degree 3600, because that is not a 4th power of a degree for A_5.

Am I confused here, or is this a misunderstanding with the data library?

[ChristopherRussell]

I however now get a discrepancy for no.6, and I wonder whether there is a miscommunication about how GAP labels the product action types:

The group has sole A_5^4 which has index 2, it has two normal subgroups of order 3600, so the sole is not simple. The group thus must be a product action of a diagonal group with a C2. This would be 4a in GAP's labelling, or HC in the named classes, unless I'm mistaken.

You are not mistaken about GAP's labeling.

When I made the database files I thought that no 6,16 were type 4a and no 14,22,29 were type 4b. However I have just noticed that in #818 I have uploaded a file that was not my final version of gap/prim/grps/gps35.g - as it seems to have no groups listed as 4a or 4b.

In GAP's labelling 4c is product action of almost simple with transitive (type PA). I think it actually cannot occur in degree 3600, because that is not a 4th power of a degree for A_5.

If this is true then I have made mistakes when creating the database file for degree 3600 by not properly dealing with types 4a & 4b. Then ONanScottType may be working correctly and this issue would be caused by the database file being incorrect.

[olexandr-konovalov]

@hulpke this still doesn't work, but now in a different way:

gap> for i in [1..33] do
> g:=PrimitiveGroup(3600,i);
> h:=Group(GeneratorsOfGroup(g));
> tg:=ONanScottType(g); th:=ONanScottType(h);
> Print(i, " : ", tg, " : ", th, " : " , tg = th, "\n" ); od;
1 : 3b : 4c : false
2 : 3b : 4c : false
3 : 3b : 4c : false
4 : 3b : 4c : false
5 : 3b : 4c : false
6 : 4c : 4a : false
7 : 4c : 4b : false
8 : 4c : 4a : false
9 : 4c : 4a : false
10 : 4c : 4b : false
11 : 4c : 4b : false
12 : 4c : 4b : false
13 : 4c : 4b : false
14 : 4c : 4b : false
15 : 4c : 4b : false
16 : 4c : 4a : false
17 : 4c : 4b : false
18 : 4c : 4b : false
19 : 4c : 4b : false
20 : 4c : 4b : false
21 : 4c : 4b : false
22 : 4c : 4b : false
23 : 4c : 4b : false
24 : 4c : 4b : false
25 : 4c : 4b : false
26 : 4c : 4b : false
27 : 4c : 4b : false
28 : 4c : 4b : false
29 : 4c : 4b : false
30 : 4c : 4c : true
31 : 4c : 4c : true
32 : 4c : 4c : true
33 : 4c : 4c : true

[fingolfin]

It would be really good to resolve this for GAP 4.9.

[olexandr-konovalov]

Indeed. I've just tested with the master branch and the PrimGrp package, and the last reported discrepancies are still occurring there. Maybe @hulpke could help?

[olexandr-konovalov]

Another option could be to temporary disable ONanScottType for order 3600.

[ChristopherRussell]

I am happy to help make the fix since I created the database files. However my understanding of primitive groups is lacking. In particular, I don't understand the difference between the primitive groups of type 4a, 4b and 4c well enough to classify these groups by looking at them myself. When I last looked at this issue I felt unable to fix it myself due to this lack of understand. I do not recall anymore what exactly I felt needed to be done which I could not do, which is unfortunate.

To recap: the issue is that the groups in the database already know their ONanScottType because it has been pre-calculated and stored as part of the database. However for degree 3600 in the database these pre-calculated values are wrong.

Can we assume that the function ONanScottType gives the correct answer when we give it a group which was not from the database? If so, I can then change the pre-calculated ONanScottType of groups in the database of degree 3600 to be equal to what ONanScottType returns when we recreate these groups in GAP and ask for their ONanScottType. That would be a fix.

[ssiccha]

I just checked the first primitive group of degree 3600. The database is correct and the function is wrong. :(

The database says the first group is "3b" which is simple diagonal type. The function says its "4c", so a subgroup of a wreath product of an almost simple type primitive group, which is completely different. In diagonal type groups of types "3a" and "3b" the degree is a power of the order of the socle type group, in this case Alt_5. Also a point stabilizer then is a diagonal subgroup of the socle, isomorphic to the socle type group.

The following code shows that it's indeed of type "3b".

gap> groups := AllPrimitiveGroups( NrMovedPoints, [3600] ){[1..33]};;
gap> socles := List( groups, Socle );;
gap> DirectFactorsOfGroup(socles[1]);
[ <permutation group of size 60 with 2 generators>, <permutation group of size 60 with 2 generators>,
  <permutation group of size 60 with 2 generators> ]
gap> # Alternatively use `MinimalNormalSubgroups(socles[1]);` which takes a lot longer though
gap> Size(socles[1]);
216000
gap> 60^2; 60^3;
3600
216000
gap> DirectFactorsOfGroup(socles[1]);
[ <permutation group of size 60 with 2 generators>, <permutation group of size 60 with 2 generators>,
  <permutation group of size 60 with 2 generators> ]
gap> Stabilizer(socles[1],1);
<permutation group of size 60 with 2 generators>

[ssiccha]

So, the error is in this line. I'll try to figure out how to change it and whether the algorithm will be correct afterwards.

https://github.com/gap-system/gap/blob/952b2c908037afdab68aef62a67b9ad939b0901e/lib/grpperm.gi#L2078

[ChristopherRussell]

Okay, do let me know if I can help with changing anything in the database !

[hulpke]

@ssiccha I'm not sure why you access the group through a sublist, but I presume we are talking about TransitiveGroup(3600,1) ?

When I try this group, both stored library data and ONanScottType return 3b, as required:

 gap> g:=PrimitiveGroup(3600,1); 
<permutation group of size 648000 with 2 generators>
gap> ONanScottType(g);
"3b"
gap> g:=Group(GeneratorsOfGroup(g));
<permutation group with 2 generators>
gap> ONanScottType(g);
"3b"

Is there another hidden cause?

[markuspf]

curious, which version of GAP are you using, @hulpke? I get

gap> ONanScottType(Group(GeneratorsOfGroup(PrimitiveGroup(3600,1))));
"4c"

on today's master (commit 952b2c90), can any packages get involved in this?

[ssiccha]

@hulpke yes, that's the group. I was lazy. ^^

Weird. Git blame says the corresponding line in ONanScottType never changed.

Also, simple normal subgroups of the socle of a diagonal type group need not be transitive. Here the simple group is an Alt_5 acting on 3600 points. So unless your ONanScottType is different it shouldn't return "3b“.

[olexandr-konovalov]

@hulpke: I see the same as @markuspf with the freshly checked out master:

gap> ONanScottType(Group(GeneratorsOfGroup(PrimitiveGroup(3600,1))));
"4c"

in all three cases (no/default/all packages).

[hulpke]

Ah. In my version the line before the transitivity test is

cs:=CompositionSeries(s);
# if the group is diagonal, the diagonal together with a maximal socle
# normal subgroup generates the whole socle, so this normal subgroup
# acts transitively. For product type this is not the case.
t:=cs[2];
if IsTransitive(t,dom) then

That is t is a maximal normal subgroup of the socle (all factors but one) which of course with a diagonal will generate the socle, thus is transitive.

This got changed in my work branch

commit 6d995882b453e3f88e3ce605ad391ebdfa052334 Author: Alexander Hulpke hulpke@math.colostate.edu Date: Tue Jul 5 08:57:44 2016 -0600

FIX: ONanScottType misindexes composition series.
This fixes #852

Apparently it fell through the cracks when it came to staging pull requests.

[ssiccha]

I'm pretty sure the fix should be something along the lines of this:

    ...
    # now get one simple factor of the socle
    cs:=CompositionSeries(s);
    # if the group is diagonal, the diagonal together with a maximal socle
    # normal subgroup generates the whole socle, so this normal subgroup
    # acts transitively. For product type this is not the case.
    m:=cs[2];
    t:=cs[Length(cs)-1];
    if IsTransitive(m,dom) then
      # type 3
      if Length(cs)=3 and IsNormal(G,t) then
    # intransitive on 2 components:
    return "3a";
      else
    return "3b";
      fi;
    else
      # type 4
    ...

Basically if the socle is only the copy of 2 simple groups t and m are identical, which is why it worked for degree < 3600.

I'll wrap it up nicely tomorrow and try to write some tests. Also, I haven't understood the code for case "4b" yet.

[ssiccha]

Ah, you beat me to it. ^^

Also, I think we may need both a maximal and a minimal normal subgroup of the socle. If I run your version I still get a difference for e.g. PrimitiveGroup(3600,6).

gap> for i in [1..33] do
> g:=PrimitiveGroup(3600,i);
> h:=Group(GeneratorsOfGroup(g));
> tg:=ONanScottType(g); th:=ONanScottType(h);
> Print(i, " : ", tg, " : ", th, " : " , tg = th, "\n" ); od;
...
6 : 4c : 3b : false

I looked at no. 6 and I think it's "4a" or "4b" but definitely neither "3b" nor "4c". The detection of 3a/b vs 4a/b is wrong but we can do this via the degree.

[hulpke]

@ssiccha I have rewritten it again in https://github.com/gap-system/gap/pull/1937/commits/ae15e131cd2753f81f5334c334a74ed2b73561f6

to have it match better with the proof in Dixon/Mortimer, page 126. 3600/6 now gets 4a. (Not 4c as stored in the database... :-( )

I'll think once more whether this can be made more efficient.

Sorry for the trouble!.

[ChristopherRussell]

Once ONanScottType is working correctly, if you could post the GAP output of the following:

for i in [1..33] do
> g:=PrimitiveGroup(3600,i);
> h:=Group(GeneratorsOfGroup(g));
> tg:=ONanScottType(g); th:=ONanScottType(h);
> Print(i, " : ", tg, " : ", th, " : " , tg = th, "\n" );
> od;

then I can make the changes to the database.

[ssiccha]

@hulpke Ah, that looks very nice. I'll think about whether some of the computations can be left out and replaced by comparisons of the degrees and group sizes. :)

[ssiccha]

@hulpke The idea with a maximal normal subgroup m should work fine. The problem was that m is transitive both when the group is of type "3a/b" and also when it's of type "4a/b". In the product action case "4c" m can't be transitive so that's fine. We can distinguish cases "3" and "4" by the degree and the size / number of simple factors of the socle. Then we only need to compute the orbit of G on a minimal normal subgroup t of the socle to distinguish cases "b" and "c".

[ssiccha]

@ChristopherRussell

1 : 3b : 3b : true
2 : 3b : 3b : true
3 : 3b : 3b : true
4 : 3b : 3b : true
5 : 3b : 3b : true
6 : 4c : 4a : false
7 : 4c : 4b : false
8 : 4c : 4a : false
9 : 4c : 4a : false
10 : 4c : 4b : false
11 : 4c : 4b : false
12 : 4c : 4b : false
13 : 4c : 4b : false
14 : 4c : 4b : false
15 : 4c : 4b : false
16 : 4c : 4a : false
17 : 4c : 4b : false
18 : 4c : 4b : false
19 : 4c : 4b : false
20 : 4c : 4b : false
21 : 4c : 4b : false
22 : 4c : 4b : false
23 : 4c : 4b : false
24 : 4c : 4b : false
25 : 4c : 4b : false
26 : 4c : 4b : false
27 : 4c : 4b : false
28 : 4c : 4b : false
29 : 4c : 4b : false
30 : 4c : 4c : true
31 : 4c : 4c : true
32 : 4c : 4c : true
33 : 4c : 4c : true

See also here