Incorrect SocleTypePrimitiveGroup for large degrees

[ssiccha]

The information in SocleTypePrimitiveGroup for primitive groups on large degrees are incorrect. This was reported via Mail by @aniemeyer. I've investigated a bit further.

gap> prims := AllPrimitiveGroups(NrMovedPoints,[4095]);;
gap> prims[5];
A(4095)
gap> prims[6];
S(4095)
gap> SocleTypePrimitiveGroup(prims[5]);
rec( parameter := 5, series := "A", width := 1 )
gap> SocleTypePrimitiveGroup(prims[6]);
rec( parameter := 6, series := "A", width := 1 )

Which means that the socles of the fifth and sixth groups are alternating groups on 5 and 6 points respectively.

I've had a look at the data files data/gps37.g, data/gps38.g, data/gps39.g and the socle type information on the natural alternating and symmetric groups seems to be wrong in all of them. The first line of data/gps37.g is

PRIMGRP[3723]:= 
[[1,Factorial(3723)/2,1,"2",[ [ 3722, 1 ] ],3721,"Alt(3723)",["A",1,1],"Alt"],
[2,Factorial(3723),0,"2",[ [ 3722, 1 ] ],3723,"Sym(3723)",["A",2,1],"Sym"]];

According to lib/primitiv.gi the eighth entries are the socle type information. In both cases they say that the alternating groups act on 1 or 2 points in their natural action.

Does someone know which functions were used to generate the database? Maybe @alex-konovalov, @hulpke or @aniemeyer ?

[fingolfin]

We encountered several other issues about consistency of the data here, and PR #34 adds consistency checks to help with finding more of them. I think it would make sense for that to check the validity of more precomputed attributes, among them SocleTypePrimitiveGroup: basically, we can do a check for if HasSocleTypePrimitiveGroup(g)... and then validate as much as possible

[fingolfin]

Also note that the SocleTypePrimitiveGroup attribute returned above is different from what a "raw" SocleTypePrimitiveGroup produces in that the latter also sets a name field in the record.

gap> SocleTypePrimitiveGroup(AlternatingGroup(4095));
rec( name := "A(4095)", parameter := 4095, series := "A", width := 1 )
gap> SocleTypePrimitiveGroup(SymmetricGroup(4095));
rec( name := "A(4095)", parameter := 4095, series := "A", width := 1 )

This might lead to some code breaking in case it relies on name being present. On the other hand, the documentation for SocleTypePrimitiveGroup does not seem to mention name, so I am not clear to what value it is set, and when.

[fingolfin]

There are many more similar issues, e.g.

gap> g:=PrimitiveGroup(4094,3);
A(4094)
gap> IsNaturalAlternatingGroup(g);
true
gap> SocleTypePrimitiveGroup(g);
rec( parameter := 3, series := "A", width := 1 )

and

gap> g:=PrimitiveGroup(4094,4);
S(4094)
gap> IsNaturalSymmetricGroup(g);
true
gap> SocleTypePrimitiveGroup(g);
rec( parameter := 4, series := "A", width := 1 )

I added some code which checks the SocleTypePrimitiveGroup and immediately found more divergences; note that the series can differ due to exceptional isomorphisms between the various Lie type series / small groups. But there seem to be more genuine bugs, e.g. this one:

PrimitiveGroup(4095,1) SocleTypePrimitiveGroup is rec(
  parameter := [ 7, 2 ],
  series := "C",
  width := 1 )
rec(
  name := "B(6,2) = O(13,2) ~ C(6,2) = S(12,2)",
  parameter := [ 6, 2 ],
  series := "B",
  width := 1 )

However, fully recomputing SocleTypePrimitiveGroup seems rather (too) slow to run it regularly. But perhaps it can be run at least once, to catch more such issues?

[fingolfin]

It seems that at least all the alternating and symmetric group entries for degrees 2500-4096 are wrong.

[hulpke]

The data for these groups comes from Colva, and I think she set up the initial part of the database. However (we probably store more data than Magma, and so some had to be recomputed) the error might come in through a conversion routine.

[fingolfin]

It would be good to resolve this, then make a new release of primgrp with all the corrections.

@hulpke I wonder what's better: looking at your conversion routine to see if we can spot a bug explaining the discrepancies, then resolve it, and re-run the conversion? Or should we directly edit the data here.

I also wondered if some of the name fixes we made need to be addressed in Magma as well. This made me use their online calculator on PrimitiveGroup(100,14) and it calls that group Alt(6)^2.(2 \times 4), while we call it Alt(6)^2.4 since 9b7b55b (before we had it as Alt(6)^2.2^2 which is also wrong).

But then I noticed that group we have has size 518400 (which is indeed equal to 360^2*4), while Magma says it has size 1036800. So at least one of the two programs is wrong... Whether by another conversion error, or because we imported the data from an older Magma version which has since been fixed, or some other reason... This seems to be another argument for trying to re-run the conversion tool against the latest Magma, and check for differences?

[olexandr-konovalov]

Perhaps @colva and @ChristopherRussell could have some suggestions?

[hulpke]

My involvement with the primitive groups library was mainly to fix bugs in degree <=255, but I don't recall doing the conversion for the larger degrees.
The socle type might have been added by us and is not in the Magma version.

[hulpke]

As for the discrepancy in degree 100, this was not taken from Magma, but computed by Heiko Theissen, but the initial version of the library was not arrangement-stable (it computed subgroups in the socle factor) and thus we later decided to just put the groups in fixed order and at that time promised we would never rearrange. Magmas group 14 is our group 28, and our group 14 has been stable since at least GAP4.4 (which is as far as I can go back easily) and the name A6^2.4 is OK.

I'm not sure about where (and when) the arrangement in Magma stems from.

[ChristopherRussell]

I did the conversion for groups of order 2500-4095 sometime around February-April 2016 with the help of @colva, as part of my Masters dissertation. I don't know exactly what version of Magma I was using, I have never owned Magma but used it by accessing a machine called Neumann (neumann.mcs.st-and.ac.uk) owned by the maths department in St Andrews. Having not thought about primitive groups in a long time, I don't comprehend these issues at a glance. In case it is useful, the code I used to do the conversion is in the Appendix of my dissertation along with a description in Section 7. The code was mostly Colva's, which she used for order <2500 with a few additions by me to handle (maybe unsuccessfully??) the new cases that can occur between orders 2500-4095.

[fingolfin]

@hulpke my apologies, I misunderstood and thought you were involved (also because you did a lot of these conversions and wrote that converter tool). Thanks also for clarifying that the GAP and Magma numbers don't match. I guess it would be useful for someone to figure out the relevant permutations and offer them in primgrp but that's another issue

@ChristopherRussell thank you, that helps a lot

[colva]

Hi all I’ve been struggling to remember exactly the sequence of events here. Hannah Coutts made the groups as part of her PhD, but only got round to putting them into Magma. Chris then pulled them from Magma to GAP as part of his (excellent) masters project, and I suspect the socle types got added then, since Magma doesn’t store that data. The code Chris used for the socle types is on pp48-49 of his thesis. PRIMITIVE_INDICES_MAGMA should convert between the two numberings for degree up to 999. I would guess the numbering should be the same for degree greater than 1000. In particular, PrimitiveGroup(100, 14) in GAP is not the same group as in Magma. The names in Magma were mostly put in by Hannah and me, but only for degrees > 1000. Best wishes Colva

[ssiccha]

As @fingolfin already said, thanks @ChristopherRussell and @colva! That is tremendously helpful.

Now that we have the code to regenerate the primitive group data for degrees >= 2500 we should be able to find the bug responsible for the incorrect socle type data. If you are OK with that @ChristopherRussell, we should IMO also add the conversion code from your thesis to the primgrp package.

The obvious next question is: who is going to do that? :D Is there a canonical candidate for that, e.g. someone who is "responsible" for the primgrp package?

[fingolfin]

@ChristopherRussell thank you for uploading your thesis, and the tex code -- it's muuuuch easier to extract your code from that than from the final PDF :-).

@ssiccha well, the package meta data lists @hulpke and @alex-konovalov as maintainers, although I have no idea if they have any time for taking care of this.

We could also add "The GAP Team" as a maintainer (as we did for multiple other packages), and then find a volunteer. Or I should volunteer one of my employees grin, although they are already having their plates full with other stuff

[ChristopherRussell]

If you are OK with that @ChristopherRussell, we should IMO also add the conversion code from your thesis to the primgrp package.

I am happy for you to do this.

[fingolfin]

For reference, the groups were added to the GAP repository in this PR: gap-system/gap#818. The data for degree 4095 is in file prim/grps/gps39.g there (and in data/gps39.g in primgrp). Looking at its start, we see this:

PRIMGRP[3970]:= 
[[1,Factorial(3970)/2,1,"2",[ [ 3969, 1 ] ],3968,"Alt(3970)",["A",1,1],"Alt"],
[2,Factorial(3970),0,"2",[ [ 3969, 1 ] ],3970,"Sym(3970)",["A",2,1],"Sym"]];
PRIMGRP[3971]:= 
[[1,Factorial(3971)/2,1,"2",[ [ 3970, 1 ] ],3969,"Alt(3971)",["A",1,1],"Alt"],
[2,Factorial(3971),0,"2",[ [ 3970, 1 ] ],3971,"Sym(3971)",["A",2,1],"Sym"]];
PRIMGRP[3972]:= 
[[1,Factorial(3972)/2,1,"2",[ [ 3971, 1 ] ],3970,"Alt(3972)",["A",1,1],"Alt"],
[2,Factorial(3972),0,"2",[ [ 3971, 1 ] ],3972,"Sym(3972)",["A",2,1],"Sym"]];
...

The relevant bit is the eighth entry in each case, which is ["A",1,1] resp. ["A",2,1]. These entries are wrong, for they are used like this by primgrp:

  SetSocleTypePrimitiveGroup(g,rec(series:=l[8][1],
                                   parameter:=l[8][2],
				   width:=l[8][3]));

We can probably fix them with a even a simple search and replace, but actually perhaps we can do even better, and replace all of these "A_n/S_n in natural rep" entries by something generic which primgrp only expands on the fly as needed... After all, we know all this data.

Granted, this won't fix the other cases.