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

## by Markus Pfeiffer

## The “Problem”

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 session

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

1 | gap> LoadPackage("atlasrep");; LoadPackage("orb");; |

Lets find out what atlasrep knows about Lyons group

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | gap> DisplayAtlasInfo("Ly"); Representations for G = Ly: (all refer to std. generators 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) Programs for G = Ly: (all refer to std. generators 1) -------------------- class repres. repr. cyc. subg. std. gen. checker std. gen. finder maxes (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.

1 2 3 4 5 6 7 8 | gap> gens := AtlasGenerators("Ly", 3);j rec( dim := 111, generators := [ < immutable compressed matrix 111x111 over GF(5) >, < immutable compressed matrix 111x111 over GF(5) > ], groupname := "Ly", id := "", identifier := [ "Ly", [ "LyG1-f5r111B0.m1", "LyG1-f5r111B0.m2" ], 1, 5 ], repname := "LyG1-f5r111B0", repnr := 3, ring := GF(5), size := 51765179004000000, standardization := 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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | gap> G25gens := function(input) > local work, output; > work := [];; > output := [];; > work[1] := input[1];; > work[2] := input[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];; > output[1] := work[1];; > output[2] := work[2];; > return output; > end; gap> v := MTX.BasesMinimalSubmodules(GModuleByMats(G25gens(gens.generators), GF(5)))[1]; gap> o := Orb(gens.generators, v, OnSubspacesByCanonicalBasis, > rec(treehashsize := 20000000, storenumbers := true));; gap> t := NanosecondsSinceEpoch();; Enumerate(o); t2 := NanosecondsSinceEpoch() - t; 3509899291325 gap> lygens := ActionOnOrbit(o, gens.generators);; |

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

1 2 3 4 5 6 7 8 | gap> G := Group(lygens); <permutation group with 2 generators> gap> LoadPackage("genss"); gap> S := StabilizerChain(G); <stabchain size=51765179004000000 orblen=8835156 layer=1 SchreierDepth=13> <stabchain size=5859000000 orblen=5812500 layer=2 SchreierDepth=16> <stabchain size=1008 orblen=1008 layer=3 SchreierDepth=7> gap> |

## Results

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.