To actually run an orbit enumeration by suborbits, we have to collect some insight into the structure of the group under consideration and into its representation theory. In general, preparing the input data is more of an art than a science. The mathematical details are described in [MNW07].
In Section 11.1 we present a small example of the usage of the orbit-by-suborbit machinery. We use the sporadic simple Mathieu group \(M_{{11}}\) acting projectively on its irreducible module of dimension 24 over the field with 3 elements.
In Section 11.2 we present another example of the usage of the orbit-by-suborbit programs. In this example we determine 35 of the 36 double coset representatives of the sporadic simple Fischer group \(Fi_{{23}}\) with respect to its seventh maximal subgroup.
In Section 11.3 we present a bigger example of the usage of the orbit-by-suborbit machinery. In this example the orbit lengths of the sporadic simple Conway group \(Co_{{1}}\) acting in in its irreducible projective representation over the field with \(5\) elements in dimension \(24\) are determined, which were previously unknown. These orbit lengths were needed to rule out a case in [Mal06].
In Section 11.4 we present as an extended worked example how to enumerate the smallest non-trivial orbit of the sporadic simple Baby Monster group \(B\). We give a log of a GAP session with explanations in between, being intended to illustrate a few of the tools which are available in the orb package as well as in related packages. Actually, the orb package has also been applied to two much larger permutation actions of \(B\), namely its action on its 2B involutions, having degree \(\approx 1.2\cdot 10^{13}\), and its action on the cosets of a maximal subgroup isomorphic to \(Fi_{23}\), having degree \(\approx 1.0\cdot 10^{15}\); for details see [M\t08] and [MNW07], respectively.
Note that for all this to work you have to acquire and install the packages IO, cvec, and atlasrep, and for Section 11.4 you additionally need the packages chop and genss.
The example in this section is very small but our intention is that everything can still be analysed and looked at more or less by hand. We want to enumerate orbits of the Mathieu group \(M_{{11}}\) acting projectively on its irreducible module of dimension 24 over the field with 3 elements. All the files for this example are located in the examples/m11PF3d24 subdirectory of the orb package. Then you simply run the example in the following way:
gap> ReadPackage("orb","examples/m11PF3d24/M11OrbitOnPF3d24.g"); ... gap> o := OrbitBySuborbit(setup,v,3,3,2,100); ... #I OrbitBySuborbit found 100% of a U3-orbit of size 7 920 ...
Everything works instantly as it would have without the orbit-by-suborbits method. (Depending on whether the matrix and permutation generators for \(M_{{11}}\) are already stored locally, some time might be needed to fetch them.) The details of this computation can be directly read off from the code in the file M11OrbitOnPF3d24.g:
LoadPackage("orb");
LoadPackage("io");
LoadPackage("cvec");
LoadPackage("atlasrep");
SetInfoLevel(InfoOrb,2);
pgens := AtlasGenerators([ "M11", [ "M11G1-p11B0.m1", "M11G1-p11B0.m2" ], 1, 11 ]).generators;
gens := AtlasGenerators([ "M11", [ "M11G1-f3r24B0.m1", "M11G1-f3r24B0.m2" ], 1, 3 ]).generators;
cgens := List(gens,CMat);
basech := CVEC_ReadMatFromFile(Filename(DirectoriesPackageLibrary("orb",""),
"examples/m11PF3d24/m11basech.cmat"));
basechi := basech^-1;
cgens := List(cgens,x->basech*x*basechi);
ReadPackage("orb","examples/m11PF3d24/m11slps.g");
pgu2 := ResultOfStraightLineProgram(s2,pgens);
pgu1 := ResultOfStraightLineProgram(s1,pgu2);
cu2 := ResultOfStraightLineProgram(s2,cgens);
cu1 := ResultOfStraightLineProgram(s1,cu2);
setup := OrbitBySuborbitBootstrapForLines(
[cu1,cu2,cgens],[pgu1,pgu2,pgens],[20,720,7920],[5,11],rec());
setup!.stabchainrandom := 900;
v := ZeroMutable(cgens[1][1]);
Randomize(v);
ORB_NormalizeVector(v);
Print("Now do\n o := OrbitBySuborbit(setup,v,3,3,2,100);\n");
We are using two helper subgroups \(U_1 < U_2 < M_{11} \), where \(U_2\cong A_6.2\) is the largest maximal subgroup of \(M_{11}\), having order \(720\), and \(U_2\cong 5:4\) is a maximal subgroup of \(U_2\) of order \(20\), see [CCN+85] or the CTblLib package. The quotient spaces we use for the helper subgroups have dimensions \(5\) and \(11\) respectively. Straight line programs to compute generators of the helper subgroups in terms of the given generators of \(M_{11}\), and an appropriate basis exhibiting the quotients, have already been computed, and are stored in the files m11slps.g and m11basech.cmat, respectively. (In Section 11.4 we show in detail how such straight line programs and suitable bases can be found using the tools available in in the orb package.) The command OrbitBySuborbitBootstrapForLines invokes the precomputation, and in particular says that we want to use projective action.
The example in this section shows how to compute 35 of the 36 double coset representatives of the Fischer group \(Fi_{{23}}\) with respect to its seventh maximal subgroup \(H\cong 3_+^{{1+8}}.2_-^{{1+6}}.3_+^{{1+2}}.2S_4\), which has order \(3\,265\,173\,504\approx 3.2\cdot 10^9\) and index \([Fi_{{23}}\colon H]=1\,252\,451\,200 \approx 1.3 \cdot 10^9\), see [CCN+85] or the CTblLib package. All the files for this example are located in the examples/fi23m7 subdirectory of the orb package. You simply run the example in the following way:
gap> ReadPackage("orb","examples/fi23m7/GOrbitByKOrbitsPrepare.g"); ... gap> ReadPackage("orb","examples/fi23m7/GOrbitByKOrbitsSearch35.g"); ...
We will not go into the details of the computation here, but they can be read off directly from the code in the files in that directory. In the first part, run by the file GOrbitByKOrbitsPrepare.g, we prepare the necessary input data, by using similar techniques as described at length in Section 11.4. (Actually, this example has been dealt with before the advent of the packages chop and genss, hence we are using appropriate private code instead.) We are using two helper subgroups \(U_1 < U_2 < H < Fi_{{23}}\), being \(3\)-subgroups of \(H\) of order \(81\) and \(6561\), respectively. The 1494-dimensional irreducible representation of \(Fi_{{23}}\) over the field with 2 elements contains a vector that is fixed by \(H\), such that the action on its \(Fi_{{23}}\)-orbit is isomorphic to the action on the cosets of \(H\).
The second part, in the file GOrbitByKOrbitsSearch35.g, is the actual enumeration of \(H\)-orbits:
setup := OrbitBySuborbitBootstrapForVectors(
[cu1gens,cu2gens,cngens],[u1gensp,u2gensp,ngensp],
[81,6561,3265173504],[10,30],rec());
obsol := InitOrbitBySuborbitList(setup,40);
l := Orb(cggens,v,OnRight,rec(schreier := true));
Enumerate(l,100000);
OrbitsFromSeedsToOrbitList(obsol,l);
origseeds := List(obsol,OrigSeed);
positions := List(origseeds,x->Position(l,x));
words := List(positions,x->TraceSchreierTreeForward(l,x));
Note that this computation finds only 35 of the 36 double coset representatives. The last corresponds to a very short suborbit which is very difficult to find. Knowing the number of missing points, we guess the stabiliser in \(H\) of a missing representative, and find the latter amongst the fixed points of the stabiliser. We can then choose the one which lies in the \(G\)-orbit we have nearly enumerated above.
These double coset representatives were needed to determine the 2-modular character table of \(Fi_{{23}}\). Details of this can be found in [HNN06].
The example in this section shows how to compute all suborbit lengths of the Conway group \(Co_1\), in its irreducible projective action on a module of dimension 24 over the field with 5 elements. All the files for this example are located in the examples/co1F5d24 subdirectory of the orb package. Then you simply run the example in the following way:
gap> ReadPackage("orb","examples/co1F5d24/Co1OrbitOnPF5d24.g"); ... gap> ReadPackage("orb","examples/co1F5d24/Co1OrbitOnPF5d24.findall.g"); ...
We will not go into the details of the first part of the computation here, as they are very similar to those reproduced in Section 11.1, and can be directly read off from the code in the file Co1OrbitOnPF5d24.g: We are using three helper subgroups \(U_1 < U_2 < U_3 < Co_1\), where \(Co_1\) has order \(4\,157\,776\,806\,543\,360\,000\approx 4.2\cdot 10^{18}\), see [CCN+85] or the CTblLib package, and where \(U_3\cong 2_+^{{1+8}}.O_8(2)\) is the fifth maximal subgroup of \(Co_1 \), having order \(89\,181\,388\,800\approx 8.9\cdot 10^{10}\), while \(U_2\cong [2^8]\colon S_6(2)\) is a maximal subgroup of \(U_3\) of order \(371\,589\,120\approx 3.7\cdot 10^{8}\), and \(U_1\cong 2^6\colon L_3(2)\) is a maximal subgroup of \(S_6(2)\) of order \(10\,752\approx 1.1\cdot 10^{4}\). The projective action comes from the irreducible 24-dimensional linear representation of the Schur cover \(2.Co_1\) of \(Co_1\), which by [Jan05] is the smallest faithful representation of \(2.Co_1\) over the field GF(5), and the quotient spaces we use for the helper subgroups have dimensions \(8\), \(8\) and \(16\) respectively.
The details of the second part can be directly read off from the code in the file Co1OrbitOnPF5d24.findall.g:
oo := InitOrbitBySuborbitList(setup,80);
l := MakeRandomLines(v,1000);
OrbitsFromSeedsToOrbitList(oo,l);
intervecs := CVEC_ReadMatFromFile(Filename(DirectoriesPackageLibrary("orb",""),
"examples/co1F5d24/co1interestingvecs.cmat"));
OrbitsFromSeedsToOrbitList(oo,intervecs);
Length(oo!.obsos);
Sum(oo!.obsos,Size);
(5^24-1)/(5-1);
Note that this example needs about 2GB of main memory on a 32bit machine and probably nearly 4GB on a 64bit machine. However, the orbit lengths were previously unknown before they were computed with this program. The orbit lengths were needed to rule out a case in [Mal06].
The example in this section shows how to enumerate the smallest non-trivial orbit of the Baby Monster group \(B\). All the files for this example are located in the examples/bmF2d4370 subdirectory of the orb package. You may simply run the example in the following way:
gap> ReadPackage("orb","examples/bmF2d4370/BMOrbitOnF2d4370partI.g"); ... gap> ReadPackage("orb","examples/bmF2d4370/BMOrbitOnF2d4370partII.g"); ...
In the sequel we comment in detail on how the necessary input data actually is prepared. We begin by loading the packages we are going to use.
gap> LoadPackage("orb"); ... gap> LoadPackage("io"); ... gap> LoadPackage("cvec"); ... gap> LoadPackage("atlasrep"); ... gap> LoadPackage("chop"); ... gap> LoadPackage("genss"); ...
The one-point stabilisers associated to the smallest non-trivial orbit of \(B\) are its largest maximal subgroups \(E \cong 2.^2E_6(2).2\), which are the centralisers of its 2A involutions. Here \(E\) is a bicyclic extension of the twisted Lie type group \(^2E_6(2)\), and has index \([B\colon E]=13\,571\,955\,000 \approx 1.4 \cdot 10^{10}\), see [CCN+85] or the CTblLib package.
We first try to find a matrix representation of \(B\) such that the \(B\)-orbit we look for is realised as a set of vectors in the underlying vector space. The smallest faithful representation of \(B\) over the field GF(2), by [Jan05] having dimension 4370, springs to mind. Explicit matrices in terms of standard generators in the sense of [Wil96] are available in [Wil], and are accessibe through the atlasrep package. Moreover, we find generators of \(E\) by applying a straight line program, also available in the atlasrep package, expressing generators of \(E\) in terms of the generators of \(B\).
gap> gens := AtlasGenerators([ "B", [ "BG1-f2r4370B0.m1", "BG1-f2r4370B0.m2" ], 1, 2 ]).generators; [ <an immutable 4370x4370 matrix over GF2>, <an immutable 4370x4370 matrix over GF2> ] gap> bgens := List(gens,CMat); [ <cmat 4370x4370 over GF(2,1)>, <cmat 4370x4370 over GF(2,1)> ] gap> slpbtoe := AtlasStraightLineProgram([ "B", "BG1-max1W1", 1 ]).program;; gap> egens := ResultOfStraightLineProgram(slpbtoe,bgens); [ <cmat 4370x4370 over GF(2,1)>, <cmat 4370x4370 over GF(2,1)> ]
We look for a non-zero vector being fixed by both generators of \(E\). It turns out that the latter have a common fixed space of dimension 1. Then, since \(E\) is a maximal subgroup, the stabiliser in \(B\) of the non-zero vector \(v\) in that fixed space coincides with \(E\).
gap> x := egens[1]-egens[1]^0;; gap> nsx := NullspaceMat(x); <immutable cmat 2202x4370 over GF(2,1)> gap> y := nsx * (egens[2]-egens[2]^0);; gap> nsy := NullspaceMat(y); <immutable cmat 1x2202 over GF(2,1)> gap> v := nsy[1]*nsx; <immutable cvec over GF(2,1) of length 4370>
Storing eight elements of GF(2) into 1 byte, to store a vector of length 4370 needs 547 bytes plus some organisational overhead resulting in about 580 bytes, hence to store the full \(B\)-orbit of \(v\) we need \(580 \cdot [B\colon E] \approx 7.9 \cdot 10^{12}\) bytes. Hence we try to find helper subgroups suitable to achieve a saving factor of \(\approx 10^4\), i. e. allowing to store only one out of \(\approx 10^4\) vectors. To this end, we look for a pair \(U_1<U_2\) of helper subgroups such that \(|U_2| \approx 10^5\), where we take into account that typically the overall saving factor achieved is somewhat smaller than the order of the largest helper subgroup.
By [CCN+85], and a few computations with subgroup fusions using the CTblLib package, the derived subgroup \(E' \cong 2.{}^2E_6(2)\) of \(E\) turns out to possess maximal subgroups \(2 \times Fi_{{22}}\) and \(2.Fi_{{22}}\), where \(Fi_{{22}}\) denotes one of the sporadic simple Fischer groups, and where the former constitute a unique conjugacy class with associated normalizers in \(E\) of shape \(2 \times Fi_{{22}}.2\), while the latter consist of two conjugacy classes being self-normalising and interchanged by \(E\).
Now \(Fi_{{22}}\) has a unique conjugacy class of maximal subgroups \(M_{{12}}\), where the latter denotes one of the sporadic simple Mathieu groups; the subgroups \(M_{{12}}\) lift to a unique conjugacy class of subgroups \(M_{{12}}\) of \(2.Fi_{{22}}\), which turn out to constitute a conjugacy class of subgroups of \(E\) different from the subgroups \(M_{{12}}\) being contained in \(Fi_{{22}}\). Anyway, we have \(|M_{{12}}|=95\,040\), hence \(U_2=M_{{12}}\) seems to be a good candidate for the larger helper subgroup. In particular, there is a unique conjugacy class of maximal subgroups \(L_2(11)\) of \(M_{{12}}\), and since \(|L_2(11)|=660\) and \([M_{{12}}\colon L_2(11)]=144\) letting \(U_1=L_2(11)\) seems to be a good candidate for the smaller helper subgroup. Recall that \(U_1\) and \(U_2\) are useful helper subgroups only if we are able to find suitable quotient modules allowing for the envisaged saving factor.
To find \(U_1\) and \(U_2\), we first try to find a subgroup \(Fi_{{22}}\) or \(2.Fi_{{22}}\) of \(E\). We start a random search, aiming at finding standard generators of either \(Fi_{{22}}\) or \(2.Fi_{{22}}\), and we use GeneratorsWithMemory in order to be able to express the generators found as words in the generators of \(E\). To accelerate computations we first construct a small representation of \(E\); by [Jan05] the smallest faithful irreducible representation of \(Fi_{{22}}\) over GF(2) has dimension 78, hence we cannot do better for \(E\); note that the latter is a representation of \(\overline{E}:=E/Z(E) \cong {}^2E_6(2).2\).
gap> SetInfoLevel(InfoChop,2); gap> m := Module(egens); <module of dim. 4370 over GF(2)> gap> r := Chop(m); ... rec( ischoprecord := true, db := [ <abs. simple module of dim. 78 over GF(2)>, <trivial module of dim. 1 over GF(2)>, <abs. simple module of dim. 1702 over GF(2)>, <abs. simple module of dim. 572 over GF(2)> ], mult := [ 5, 4, 2, 1 ], acs := [ 1, 2, 3, 1, 4, 1, 1, 2, 2, 3, 1, 2 ], module := <reducible module of dim. 4370 over GF(2)> ) gap> i := Position(List(r.db,Dimension),78);; gap> egens78 := GeneratorsWithMemory(RepresentingMatrices(r.db[i])); [ <<immutable cmat 78x78 over GF(2,1)> with mem>, <<immutable cmat 78x78 over GF(2,1)> with mem> ]
By [Wil], standard generators \(a,b\) of \(Fi_{{22}}\) are given as follows: \(a\) is an element of the 2A conjugacy class of \(Fi_{{22}}\), and \(b\), \(ab\), and \((ab)^4bab(abb)^2\) have order 13, 11, and 12, respectively; standard generators of \(2.Fi_{{22}}\) are lifts of standard generators of \(Fi_{{22}}\) having the same order fingerprint. The 2A conjugacy class of \(Fi_{{22}}\) fuses into the 2A conjugacy class of \(\overline{E}\), where the latter is obtained as the 11-th power of the unique conjugacy class of elements of order 22, and \(\overline{E}\) has only one conjugacy class of elements of order 13.
gap> o := Orb(egens78,StripMemory(egens78[1])^0,OnRight,rec(schreier := true, > lookingfor := function(o,x) return Order(x)=22; end)); <open orbit, 1 points with Schreier tree looking for sth.> gap> Enumerate(o); <open orbit, 393 points with Schreier tree looking for sth.> gap> word := TraceSchreierTreeForward(o,PositionOfFound(o)); [ 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2 ] gap> g2a := Product(egens78{word})^11; <<immutable cmat 78x78 over GF(2,1)> with mem> gap> o := Orb(egens78,StripMemory(egens78[1])^0,OnRight,rec(schreier := true, > lookingfor := function(o,x) return Order(x)=13; end)); <open orbit, 1 points with Schreier tree looking for sth.> gap> Enumerate(o); <open orbit, 144 points with Schreier tree looking for sth.> gap> word := TraceSchreierTreeForward(o,PositionOfFound(o)); [ 1, 2, 1, 2, 1, 2, 1, 2, 2 ] gap> b := Product(egens78{word}); <<immutable cmat 78x78 over GF(2,1)> with mem>
We search through the \(\overline{E}\)-conjugates of g2a until we find a conjugate \(a\) together with \(b\) fulfilling the defining conditions of standard generators of \(Fi_{{22}}\), and moreover fulfilling the relations of the associated presentation of \(Fi_{{22}}\) available in [Wil].
To find conjugates, we use the product replacement algorithm to produce pseudo random elements of \(\overline{E}\). Assuming a genuine random search, the success probability of this approach is as follows: Letting \(\overline{E'}:=E'/Z(E') \cong {}^2E_6(2)\), out of the \(|\overline{E'}|/|C_{\overline{E'}}(g2a)|\) conjugates of g2a there are \(|C_{{ \overline{E'} }}(b)|/|C_{{ \overline{E'} }}(Fi_{{22}})| =|C_{{ \overline{E'} }}(b)|\) elements together with the fixed element \(b\) giving standard generators of \(Fi_{{22}}\). Since \(Fi_{{22}}\) has two conjugacy classes of elements of order 13, and there are three conjugacy classes of subgroups \(Fi_{{22}}\) of \(\overline{E'}\), the success probability is \(6 \cdot |C_{{ \overline{E'} }}(g2a)| \cdot |C_{{ \overline{E'} }}(b)|/|\overline{E'}| \approx 2 \cdot 10^{-5}\).
gap> pr := ProductReplacer(egens78,rec(maxdepth := 150)); <product replacer nrgens=2 slots=12 scramble=100 maxdepth=150 steps=0 (rattle)> gap> i := 0;; gap> repeat > i := i + 1; > x := Next(pr); > a := g2a^x; > until IsOne((a*b)^11) and IsOne(((a*b)^4*b*a*b*(a*b*b)^2)^12) and > IsOne((a*b^2)^21) and IsOne(Comm(a,b)^3) and > IsOne(Comm(a,b^2)^3) and IsOne(Comm(a,b^3)^3) and > IsOne(Comm(a,b^4)^2) and IsOne(Comm(a,b^5)^3) and > IsOne(Comm(a,b*a*b^2)^3) and IsOne(Comm(a,b^-1*a*b^-2)^2) and > IsOne(Comm(a,b*a*b^5)^2) and IsOne(Comm(a,b^2*a*b^5)^2); gap> i; 53271
Note that the initial state of the random number generator does influence this randomised result: it may very well be that you see some other value for \(i\).
Due to a presentation being available we have proved that the elements found generate a subgroup \(Fi_{{22}}\). If we had not had a presentation at hand, we might only have been able to find elements fulfilling the defining conditions of standard generators of \(Fi_{{22}}\), but still generating a subgroup of another isomorphism type. In that case, for further checks we can use the following tools: We try to find a short orbit of vectors, and using a randomized Schreier-Sims algorithm gives a lower bound for the order of the group seen. However, we can use the action on the orbit to get a homomorphism into a permutation group, allowing to prove that the group generated indeed has \(Fi_{{22}}\) as a quotient.
gap> S := StabilizerChain(Group(a,b),rec(TryShortOrbit := 30, > OrbitLengthLimit := 5000)); ... <stabchain size=64561751654400 orblen=3510 layer=1 SchreierDepth=8> <stabchain size=18393661440 orblen=2816 layer=2 SchreierDepth=7> <stabchain size=6531840 orblen=1680 layer=3 SchreierDepth=7> <stabchain size=3888 orblen=243 layer=4 SchreierDepth=5> <stabchain size=16 orblen=16 layer=5 SchreierDepth=2> gap> Size(S)=Size(CharacterTable("Fi22")); true gap> p := Group(ActionOnOrbit(S!.orb,[a,b]));; gap> DisplayCompositionSeries(p); G (2 gens, size 64561751654400) | Fi(22) 1 (0 gens, size 1)
We now return to our original representation.
gap> SetInfoLevel(InfoSLP,2); gap> slpetofi22 := SLPOfElms([a,b]); <straight line program> gap> Length(LinesOfStraightLineProgram(slpetofi22)); 278 gap> SlotUsagePattern(slpetofi22);; gap> fgens := ResultOfStraightLineProgram(slpetofi22,egens); ... [ <cmat 4370x4370 over GF(2,1)>, <cmat 4370x4370 over GF(2,1)> ] gap> a := fgens[1];; gap> b := fgens[2];; gap> IsOne(b^13); true gap> IsOne((a*b)^11); true gap> IsOne((a*b^2)^21); true
By construction the group generated by \(a,b\) is \(Fi_{{22}}\) or \(2 \times Fi_{{22}}\) or \(2.Fi_{{22}}\). Note that due to different seeds in the random number generator it is in fact possible at this stage that you have created a different group as displayed here! In our outcome, since \(a\) has even order, and both \(b\) and \(ab\) have odd order, we cannot possibly have \(2 \times Fi_{{22}}\); and by the presentation of \(2.Fi_{{22}}\) available in [Wil] the order of \(ab^2\) being 21 implies that we cannot possibly have \(2.Fi_{{22}}\) either. Hence we indeed have found standard generators of \(Fi_{{22}}\). If we had hit one of the cases \(2 \times Fi_{{22}}\) or \(2.Fi_{{22}}\), we could just continue the above search until we find a subgroup \(Fi_{{22}}\), or using the above order fingerprint we could easily modify the elements found to obtain standard generators of either \(Fi_{{22}}\) or \(2.Fi_{{22}}\).
Now, standard generators of \(U_2=M_{{12}}\) in terms of standard generators of \(Fi_{{22}}\), and generators of \(U_1=L_2(11)\) in terms of standard generators of \(M_{{12}}\) are accessible in the atlasrep package. Note that if we had found a subgroup \(2.Fi_{{22}}\) above, since \(M_{{12}}\) lifts to a subgroup \(2 \times M_{{12}}\) of \(2.Fi_{{22}}\), it would again be easy to find standard generators of \(M_{{12}}\) from the generators of \(M_{{12}}\) or \(2 \times M_{{12}}\) respectively provided by the atlasrep package. Anyway, the next task is to find good quotient modules such that the helper subgroups have longish orbits on vectors. To this end, we restrict to \(M_{{12}}\) and compute the radical series of the restricted module.
gap> slpfi22tom12 := AtlasStraightLineProgram([ "Fi22", "F22G1-max14W1", 1 ]).program;; gap> slpm12tol211 := AtlasStraightLineProgram([ "M12", "M12G1-max5W1", 1 ]).program;; gap> mgens := ResultOfStraightLineProgram(slpfi22tom12,fgens); [ <cmat 4370x4370 over GF(2,1)>, <cmat 4370x4370 over GF(2,1)> ] gap> lgens := ResultOfStraightLineProgram(slpm12tol211,mgens); [ <cmat 4370x4370 over GF(2,1)>, <cmat 4370x4370 over GF(2,1)> ] gap> m := Module(mgens);; gap> r := Chop(m);; ... gap> rad := RadicalSeries(m,r.db); ... rec( db := [ <abs. simple module of dim. 144 over GF(2)>, <abs. simple module of dim. 44 over GF(2)>, <simple module of dim. 32 over GF(2) splitting field degree 2>, <abs. simple module of dim. 10 over GF(2)>, <trivial module of dim. 1 over GF(2)> ], module := <reducible module of dim. 4370 over GF(2)>, basis := <immutable cmat 4370x4370 over GF(2,1)>, ibasis := <immutable cmat 4370x4370 over GF(2,1)>, cfposs := [ [ [ 1 .. 144 ], [ 145 .. 288 ], [ 289 .. 432 ], [ 433 .. 576 ], ... isotypes := [ [ 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5 ], ... isradicalrecord := true )
We observe that there are faithful irreducible quotients of dimensions 10, 32, 44, and 144. Since we look for a quotient module such that \(M_{{12}}\) has many regular orbits on vectors, we ignore the irreducible module of dimension 10. We consider the one of dimension 32.
gap> i := Position(List(rad.db,Dimension),32);; gap> mgens32 := RepresentingMatrices(rad.db[i]); [ <immutable cmat 32x32 over GF(2,1)>, <immutable cmat 32x32 over GF(2,1)> ] gap> OrbitStatisticOnVectorSpace(mgens32,95040,30); Found length 95040, have now 24 orbits, average length: 93060
This is excellent indeed. Hence we pick a summand of dimension 32 in the first radical layer, and apply the associated base change to all the generators.
gap> bgens := List(bgens,x->rad.basis*x*rad.ibasis);; gap> egens := List(egens,x->rad.basis*x*rad.ibasis);; gap> fgens := List(fgens,x->rad.basis*x*rad.ibasis);; gap> mgens := List(mgens,x->rad.basis*x*rad.ibasis);; gap> lgens := List(lgens,x->rad.basis*x*rad.ibasis);; gap> j := Position(rad.isotypes[1],i);; gap> l := rad.cfposs[1][j];; gap> Append(l,Difference([1..4370],l)); gap> bgens := List(bgens,x->ORB_PermuteBasisVectors(x,l));; gap> egens := List(egens,x->ORB_PermuteBasisVectors(x,l));; gap> fgens := List(fgens,x->ORB_PermuteBasisVectors(x,l));; gap> mgens := List(mgens,x->ORB_PermuteBasisVectors(x,l));; gap> lgens := List(lgens,x->ORB_PermuteBasisVectors(x,l));;
We consider the irreducible quotient module of \(M_{{12}}\) of dimension 32, whose restriction to \(L_2(11)\) turns out to be is semisimple. The irreducible quotients of dimension 10 are too small to have too many regular orbits, but the direct sum of two of them turns out to work fine.
gap> lgens32 := List(lgens,x->ExtractSubMatrix(x,[1..32],[1..32])); [ <cmat 32x32 over GF(2,1)>, <cmat 32x32 over GF(2,1)> ] gap> m := Module(lgens32);; gap> r := Chop(m); ... gap> soc := SocleSeries(m,r.db); ... rec( issoclerecord := true, db := [ <simple module of dim. 10 over GF(2) splitting field degree 2>, <trivial module of dim. 1 over GF(2)>, <abs. simple module of dim. 10 over GF(2)> ], module := <reducible module of dim. 32 over GF(2)>, basis := <cmat 32x32 over GF(2,1)>, ibasis := <cmat 32x32 over GF(2,1)>, cfposs := [ [ [ 1 .. 10 ], [ 11 ], [ 12 ], [ 13 .. 22 ], [ 23 .. 32 ] ] ], isotypes := [ [ 1, 2, 2, 3, 3 ] ] ) gap> i := Position(List(soc.db,x->[Dimension(x),DegreeOfSplittingField(x)]), > [10,1]);; gap> j := Position(soc.isotypes[1],i);; gap> l := Concatenation(soc.cfposs[1]{[j,j+1]});; gap> lgens32 := List(lgens32,x->soc.basis*x*soc.ibasis); [ <cmat 32x32 over GF(2,1)>, <cmat 32x32 over GF(2,1)> ] gap> lgens20 := List(lgens32,x->ExtractSubMatrix(x,l,l)); [ <cmat 20x20 over GF(2,1)>, <cmat 20x20 over GF(2,1)> ] gap> OrbitStatisticOnVectorSpace(lgens20,660,30); Found length 660, have now 4401 orbits, average length: 598
We apply the appropriate base change to all the generators.
gap> t := ORB_EmbedBaseChangeTopLeft(soc.basis,4370); <cmat 4370x4370 over GF(2,1)> gap> ti := ORB_EmbedBaseChangeTopLeft(soc.ibasis,4370); <cmat 4370x4370 over GF(2,1)> gap> bgens := List(bgens,x->t*x*ti);; gap> egens := List(egens,x->t*x*ti);; gap> fgens := List(fgens,x->t*x*ti);; gap> mgens := List(mgens,x->t*x*ti);; gap> lgens := List(lgens,x->t*x*ti);; gap> Append(l,Difference([1..4370],l)); gap> bgens := List(bgens,x->ORB_PermuteBasisVectors(x,l));; gap> egens := List(egens,x->ORB_PermuteBasisVectors(x,l));; gap> fgens := List(fgens,x->ORB_PermuteBasisVectors(x,l));; gap> mgens := List(mgens,x->ORB_PermuteBasisVectors(x,l));; gap> lgens := List(lgens,x->ORB_PermuteBasisVectors(x,l));;
Having reached the ultimate choice of basis, we recreate the fixed vector v.
gap> x := egens[1]-egens[1]^0;; gap> nsx := NullspaceMat(x);; gap> y := nsx * (egens[2]-egens[2]^0);; gap> nsy := NullspaceMat(y);; gap> v := nsy[1]*nsx;;
Finally we need small faithful permutation representations of the helper subgroups.
gap> mgens32 := List(mgens,x->ExtractSubMatrix(x,[1..32],[1..32])); [ <cmat 32x32 over GF(2,1)>, <cmat 32x32 over GF(2,1)> ] gap> S := StabilizerChain(Group(mgens32),rec(TryShortOrbit := 10)); ... <stabchain size=95040 orblen=3960 layer=1 SchreierDepth=7> <stabchain size=24 orblen=24 layer=2 SchreierDepth=4> gap> p := Group(ActionOnOrbit(S!.orb,mgens32)); <permutation group with 2 generators> gap> i := SmallerDegreePermutationRepresentation(p);; gap> pp := Group(List(GeneratorsOfGroup(p),x->ImageElm(i,x))); <permutation group with 2 generators> gap> m12 := MathieuGroup(12);; gap> i := IsomorphismGroups(pp,m12);; gap> mpermgens := List(GeneratorsOfGroup(pp),x->ImageElm(i,x)); [ (5,7)(6,11)(8,9)(10,12), (1,10,3)(2,11,12)(4,5,6)(7,9,8) ] gap> lpermgens := ResultOfStraightLineProgram(slpm12tol211,mpermgens); [ (1,8)(2,5)(3,9)(4,7)(6,11)(10,12), (1,8,3)(2,7,12)(4,6,9)(5,11,10) ]
We could just go on from here, however, sometimes it is useful to save all the created data to disk.
gap> f := IO_File("data.gp","w");; gap> IO_Pickle(f,"seed");; gap> IO_Pickle(f,v);; gap> IO_Pickle(f,"generators");; gap> IO_Pickle(f,bgens);; gap> IO_Pickle(f,egens);; gap> IO_Pickle(f,fgens);; gap> IO_Pickle(f,mgens);; gap> IO_Pickle(f,lgens);; gap> IO_Pickle(f,"permutations");; gap> IO_Pickle(f,mpermgens);; gap> IO_Pickle(f,lpermgens);; gap> IO_Close(f);;
This can be loaded again, in particular into a new GAP session, as follows.
gap> LoadPackage("orb");; ... gap> LoadPackage("cvec");; ... gap> f := IO_File("data.gp"); <file fd=4 rbufsize=65536 rpos=1 rdata=0> gap> IO_Unpickle(f); "seed" gap> v:=IO_Unpickle(f);; gap> IO_Unpickle(f); "generators" gap> bgens := IO_Unpickle(f);; gap> egens := IO_Unpickle(f);; gap> fgens := IO_Unpickle(f);; gap> mgens := IO_Unpickle(f);; gap> lgens := IO_Unpickle(f);; gap> IO_Unpickle(f); "permutations" gap> mpermgens := IO_Unpickle(f);; gap> lpermgens := IO_Unpickle(f);; gap> IO_Close(f);;
Now we are prepared to actually run the orbit enumeration. Note that for the following memory estimates we assume that we are running things on a 64bit machine. On a 32bit machine the overhead is smaller. We expect that all the vectors in the smaller quotient of dimension 20 will enumerated; needing 3 bytes per vector for the actual data which results in 40 bytes including overhead, this amounts to \(40 \cdot 2^{20} \approx 42\) MB of memory space. Since \(2^{32} \approx 4.3 \cdot 10^9\) is less than \([B\colon E]\), we also expect that the larger quotient of dimension 32 will be enumerated completely, by \(L_2(11)\)-orbits; needing 4 bytes per vector for the actual data resulting in 40 bytes including overhead, and assuming a saving factor as suggested by OrbitStatisticOnVectorSpace yields an estimated memory requirement of \(40 \cdot 2^{32} \cdot 1/598 \approx 287\) MB. For the large \(B\)-orbit, being enumerated by \(M_{{12}}\)-orbits, we similarly get an estimated memory requirement of \(584 \cdot [B\colon E] \cdot 1/93060 \approx 85\) MB.
gap> setup := OrbitBySuborbitBootstrapForVectors( > [lgens,mgens,bgens],[lpermgens,mpermgens,[(),()]], > [660,95040,4154781481226426191177580544000000],[20,32],rec()); #I Calculating stabilizer chain for whole group... #I Trying smaller degree permutation representation for U2... #I Trying smaller degree permutation representation for U1... #I Enumerating permutation base images of U_1... #I Looking for U1-coset-recognising U2-orbit in factor space... #I OrbitBySuborbit found 100% of a U2-orbit of size 95 040 #I Found 144 suborbits (need 144) <setup for an orbit-by-suborbit enumeration, k=2> gap> o := OrbitBySuborbitKnownSize(setup,v,3,3,2,51,13571955000); #I OrbitBySuborbit found 100% of a U2-orbit of size 1 #I OrbitBySuborbit found 100% of a U2-orbit of size 23 760 ... #I OrbitBySuborbit found 51% of a U3-orbit of size 13 571 955 000 <orbit-by-suborbit size=13571955000 stabsize=306129918735099415756800 ( 51%) saving factor=56404>
Indeed the saving factor actually achieved is smaller than the best possible estimate given above, but it still has the same order of magnitude.
generated by GAPDoc2HTML