Computing a (faithful) permutation representation of Lyons' sporadic simple group

The “Prob­lem”

While vising my colleagues Rebecca Waldecker and Imke Toborg in Halle to work on partition backtrack code (with Chris Jefferson of course!), I had the pleasure to meet Richard Lyons, the discoverer of the Lyons’ sporadic simple group.

I tried finding out what a small(est) degree permutation representation of this group would be, to run our backtracking code on it. This was just supposed to be some fun, since it seemed to fit the occasion (and maybe one should test larger degree permutations in GAP every so often, too!). So I looked at the web atlas, and to my surprise there were no generators of such a permutation representation there.

A quick look into the literature (ok, I’ll admit, wikipedia), revealed that there are faithful permutation representations of Lyons group on 8,835,156, on 9,606,125, and on 19,212,250 points. I started wondering how hard it would be to compute such a representation with GAP.

After a few emails (thanks Rob Wilson, and Thomas Breuer!), it turns out that it is not really difficult, once one knows what one is doing (and to be honest, I should have known better, but there we go).

The GAP ses­sion

Here’s the code, I started GAP with `-o 12g` to make sure there is enough memory available in the workspace.

gap> Load­Pack­age(“at­las­rep”);; Load­Pack­age(“orb”);;

Lets find out what atlasrep knows about Lyons group

gap> Dis­play­At­las­In­fo(“Ly”);
Rep­re­sen­ta­tions for G = Ly:    (all re­fer to std. gen­er­a­tors 1)—————————1: G <= GL(651,3)
2: G <= GL(2480,4)
3: G <= GL(111,5)
4: G <= GL(517,5)
5: G <= GL(2480a,5)
6: G <= GL(2480b,5)

Pro­grams for G = Ly:    (all re­fer to std. gen­er­a­tors 1)——————–class repres.
repr. cyc. subg.
std. gen. check­er
std. gen. find­er
max­es (all 9):
  1:  G2(5)
  2:  3.McL.2
  3:  5^3.L3(5)
  4:  2.A11
  5:  5^(1+4):4S6
  6:  3^5:(2xM11)
  7:  3^(2+4):2A5.D8
  8:  67:22
  9:  37:18

So there are 6 different matrix representations of Lyons group available. I’d like to use the one of dimension 111 over the field with 5 elements, for various reasons: its smallish, and I have a paper The Minimal 5-Representation of Lyons’ Sporadic Group - Meyer, Neutsch, Parker - 1985 - Mathematische Annalen 272 to hold on to.

gap> gens := At­las­Gen­er­a­tors(“Ly”, 3);j
rec( dim := 111,
  gen­er­a­tors := [ < im­mu­ta­ble com­pressed ma­trix 111x111 over GF(5) >,
      < im­mu­ta­ble com­pressed ma­trix 111x111 over GF(5) > ],
  group­name := “Ly”, id := “”,
  iden­ti­fi­er := [ “Ly”, [ “LyG1-f5r111B0.m1”, “LyG1-f5r111B0.m2” ], 1,
      5 ], rep­name := “LyG1-f5r111B0”, rep­nr := 3, ring := GF(5),
  size := 51765179004000000, stan­dard­iza­tion := 1, type := “matff” )

The maximal subgroup G_2(5) fixes a unique 7-dimensional subspace of GF(5)^{111}, I’ll try getting my hands on it using the MeatAxe. Unfortunately AtlasSubgroup did not want to cooperate, so I used the SLP provided in the Atlas.

gap> G25gens := func­tion(in­put)
> lo­cal work, out­put;
> work := [];;
> out­put := [];;
> work[1] := in­put[1];;
> work[2] := in­put[2];;
> work[3] := work[1] * work[2];;
> work[4] := work[3] * work[2];;
> work[5] := work[3] * work[4];;
> work[9] := work[5] * work[2];;
> work[6] := work[3] * work[5];;
> work[7] := work[6] * work[3];;
> work[8] := work[7] * work[7];;
> work[2] := work[7] * work[8];;
> work[3] := work[9]^7;;
> work[4] := work[3]^-1;;
> work[5] := work[3] * work[1];;
> work[1] := work[5] * work[4];;
> work[8] := work[6]^25;;
> work[7] := work[8]^-1;;
> work[3] := work[7] * work[2];;
> work[2] := work[3] * work[8];;
> out­put[1] := work[1];;
> out­put[2] := work[2];;
> re­turn out­put;
> end;
gap> v := MTX.Bases­Min­i­mal­Sub­mod­ules(GMod­ule­By­Mats(G25gens(gens.gen­er­a­tors), GF(5)))[1];
gap> o := Orb(gens.gen­er­a­tors, v, On­Sub­spaces­By­Canon­i­cal­Ba­sis,
> rec(tree­hash­size := 20000000, storenum­bers := true));;
gap> t := Nanosec­onds­Since­Epoch();; Enu­mer­ate(o); t2 := Nanosec­onds­Since­Epoch() - t;
3509899291325
gap> ly­gens := Ac­tionOn­Or­bit(o, gens.gen­er­a­tors);;

Now I have some generators of a permutation group, and I shall just test whether it has the correct size at this point:

gap> G := Group(ly­gens);
<per­mu­ta­tion group with 2 gen­er­a­tors>
gap> Load­Pack­age(“genss”);
gap> S := Sta­bi­liz­er­Chain(G);
<stabchain size=51765179004000000 or­blen=8835156 lay­er=1 Schreier­Depth=13>
 <stabchain size=5859000000 or­blen=5812500 lay­er=2 Schreier­Depth=16>
  <stabchain size=1008 or­blen=1008 lay­er=3 Schreier­Depth=7>
gap>

Re­sults

I ran this on my fairly low-spec laptop: Intel(R) Core(TM) i5-3320M CPU @ 2.60GHz, 2 cores/4 threads, 12GB memory. Since this takes an hour or so to complete, there is a point in storing the result on disk, and here (in GAP’s IO pickle format).

For people who don’t trust me, but are too lazy to compute them, Thomas Breuer’s page on the verification of ordinary character tables in the ATLAS has the generators as well: g1 g2.

Of course, now to do something useful with this representation, I will use it to stress-test ferret.

I should have known even better than just turning to google to find these representations: the demo code for HPC-GAP actually contains most of the above example in its full glory, courtesy of Max Neunhöffer.

Next, I will learn how Lyons group was constructed, and I’ll try the larger degree representations. Then Thompson’s group. I hear Magma can do it, so GAP should do it too.