Quelle chap11.html Sprache: HTML

products/sources/formale Sprachen/GAP/pkg/orb/doc/chap11.html

<?xml version="1.0" encoding="UTF-8"?>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>GAP (orb) - Chapter 11: Examples</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap11" onload="jscontent()">

<div class="chlinktop">Goto Chapter: <a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chap8.html">8</a> <a href="chap9.html">9</a> <a href="chap10.html">10</a> <a href="chap11.html">11</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>

<div class="chlinkprevnexttop"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap10.html">[Previous Chapter]</a> <a href="chapBib.html">[Next Chapter]</a> </div>

<a href="chap11_mj.html">[MathJax on]</a>
<a id="X7A489A5D79DA9E5C" name="X7A489A5D79DA9E5C"></a>
<div class="ChapSects"><a href="chap11.html#X7A489A5D79DA9E5C">11 Examples</a>
<div class="ContSect"> <a href="chap11.html#X7D5456AC85A830A4">11.1 The Mathieu group M_{11} acting in
 dimension 24</a>

</div>
<div class="ContSect"> <a href="chap11.html#X790F22B67C56A49F">11.2 The Fischer group Fi_{23} acting in
 dimension 1494
 </a>

</div>
<div class="ContSect"> <a href="chap11.html#X7D7BDBF87E7C45ED">11.3 The Conway group Co_1 acting in
 dimension 24
 </a>

</div>
<div class="ContSect"> <a href="chap11.html#X781209EE7C9D3E0E">11.4 The Baby Monster B acting on its 2A involutions</a>

</div>
</div>

<h3>11 Examples</h3>

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 <a href="chapBib.html#biBMNW">[MNW07]</a>.

In Section <a href="chap11.html#X7D5456AC85A830A4">11.1</a> 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 <a href="chap11.html#X790F22B67C56A49F">11.2</a> 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 <a href="chap11.html#X7D7BDBF87E7C45ED">11.3</a> 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 <a href="chapBib.html#biBLongOrbits">[Mal06]</a>.

In Section <a href="chap11.html#X781209EE7C9D3E0E">11.4</a> 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 ≈ 1.2⋅ 10^13, and its action on the cosets of a maximal subgroup isomorphic to Fi_23, having degree ≈ 1.0⋅ 10^15; for details see <a href="chapBib.html#biBMueBMCo2">[M\t08]</a> and <a href="chapBib.html#biBMNW">[MNW07]</a>, respectively.

Note that for all this to work you have to acquire and install the packages IO, cvec, and atlasrep, and for Section <a href="chap11.html#X781209EE7C9D3E0E">11.4</a> you additionally need the packages chop and genss.

<a id="X7D5456AC85A830A4" name="X7D5456AC85A830A4"></a>

<h4>11.1 The Mathieu group M_{11} acting in
 dimension 24</h4>

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 <code class="file">examples/m11PF3d24</code> subdirectory of the orb package. Then you simply run the example in the following way:

<div class="example"><pre>
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
...
</pre></div>

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 <code class="file">M11OrbitOnPF3d24.g</code>:

<div class="example"><pre>
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");
</pre></div>

We are using two helper subgroups U_1 < U_2 < M_11, where U_2≅ A_6.2 is the largest maximal subgroup of M_11, having order 720, and U_2≅ 5:4 is a maximal subgroup of U_2 of order 20, see <a href="chapBib.html#biBCCN85">[CCN+85]</a> 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 <code class="file">m11slps.g</code> and <code class="file">m11basech.cmat</code>, respectively. (In Section <a href="chap11.html#X781209EE7C9D3E0E">11.4</a> 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 <code class="file">OrbitBySuborbitBootstrapForLines</code> invokes the precomputation, and in particular says that we want to use projective action.

<a id="X790F22B67C56A49F" name="X790F22B67C56A49F"></a>

<h4>11.2 The Fischer group Fi_{23} acting in
 dimension 1494
 </h4>

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≅ 3_+^{1+8}.2_-^{1+6}.3_+^{1+2}.2S_4, which has order 3265173504≈ 3.2⋅ 10^9 and index [Fi_{23}: H]=1252451200 ≈ 1.3 ⋅ 10^9, see <a href="chapBib.html#biBCCN85">[CCN+85]</a> or the CTblLib package. All the files for this example are located in the <code class="file">examples/fi23m7</code> subdirectory of the orb package. You simply run the example in the following way:

<div class="example"><pre>
gap> ReadPackage("orb","examples/fi23m7/GOrbitByKOrbitsPrepare.g");
...
gap> ReadPackage("orb","examples/fi23m7/GOrbitByKOrbitsSearch35.g");
...
</pre></div>

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 <code class="file">GOrbitByKOrbitsPrepare.g</code>, we prepare the necessary input data, by using similar techniques as described at length in Section <a href="chap11.html#X781209EE7C9D3E0E">11.4</a>. (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 <code class="file">GOrbitByKOrbitsSearch35.g</code>, is the actual enumeration of H-orbits:

<div class="example"><pre>
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));
</pre></div>

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 <a href="chapBib.html#biBFi23mod2">[HNN06]</a>.

<a id="X7D7BDBF87E7C45ED" name="X7D7BDBF87E7C45ED"></a>

<h4>11.3 The Conway group Co_1 acting in
 dimension 24
 </h4>

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 <code class="file">examples/co1F5d24</code> subdirectory of the orb package. Then you simply run the example in the following way:

<div class="example"><pre>
gap> ReadPackage("orb","examples/co1F5d24/Co1OrbitOnPF5d24.g");
...
gap> ReadPackage("orb","examples/co1F5d24/Co1OrbitOnPF5d24.findall.g");
...
</pre></div>

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 <a href="chap11.html#X7D5456AC85A830A4">11.1</a>, and can be directly read off from the code in the file <code class="file">Co1OrbitOnPF5d24.g</code>: We are using three helper subgroups U_1 < U_2 < U_3 < Co_1, where Co_1 has order 4157776806543360000≈ 4.2⋅ 10^18, see <a href="chapBib.html#biBCCN85">[CCN+85]</a> or the CTblLib package, and where U_3≅ 2_+^{1+8}.O_8(2) is the fifth maximal subgroup of Co_1, having order 89181388800≈ 8.9⋅ 10^10, while U_2≅ [2^8]: S_6(2) is a maximal subgroup of U_3 of order 371589120≈ 3.7⋅ 10^8, and U_1≅ 2^6: L_3(2) is a maximal subgroup of S_6(2) of order 10752≈ 1.1⋅ 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 <a href="chapBib.html#biBJansen">[Jan05]</a> 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 <code class="file">Co1OrbitOnPF5d24.findall.g</code>:

<div class="example"><pre>
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);
</pre></div>

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 <a href="chapBib.html#biBLongOrbits">[Mal06]</a>.

<a id="X781209EE7C9D3E0E" name="X781209EE7C9D3E0E"></a>

<h4>11.4 The Baby Monster B acting on its 2A involutions</h4>

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 <code class="file">examples/bmF2d4370</code> subdirectory of the orb package. You may simply run the example in the following way:

<div class="example"><pre>
gap> ReadPackage("orb","examples/bmF2d4370/BMOrbitOnF2d4370partI.g");
...
gap> ReadPackage("orb","examples/bmF2d4370/BMOrbitOnF2d4370partII.g");
...
</pre></div>

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.

<div class="example"><pre>
gap> LoadPackage("orb");
...
gap> LoadPackage("io");
...
gap> LoadPackage("cvec");
...
gap> LoadPackage("atlasrep");
...
gap> LoadPackage("chop");
...
gap> LoadPackage("genss");
...
</pre></div>

The one-point stabilisers associated to the smallest non-trivial orbit of B are its largest maximal subgroups E ≅ 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: E]=13571955000 ≈ 1.4 ⋅ 10^10, see <a href="chapBib.html#biBCCN85">[CCN+85]</a> 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 <a href="chapBib.html#biBJansen">[Jan05]</a> having dimension 4370, springs to mind. Explicit matrices in terms of standard generators in the sense of <a href="chapBib.html#biBWil96">[Wil96]</a> are available in <a href="chapBib.html#biBAGR">[Wil]</a>, 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.

<div class="example"><pre>
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)> ]
</pre></div>

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.

<div class="example"><pre>
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>
</pre></div>

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 ⋅ [B: E] ≈ 7.9 ⋅ 10^12 bytes. Hence we try to find helper subgroups suitable to achieve a saving factor of ≈ 10^4, i. e. allowing to store only one out of ≈ 10^4 vectors. To this end, we look for a pair U_1<U_2 of helper subgroups such that |U_2| ≈ 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 <a href="chapBib.html#biBCCN85">[CCN+85]</a>, and a few computations with subgroup fusions using the CTblLib package, the derived subgroup E' ≅ 2.^2E_6(2) of E turns out to possess maximal subgroups 2 × 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 × 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}|=95040, 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}: 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 <code class="code">GeneratorsWithMemory</code> 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 <a href="chapBib.html#biBJansen">[Jan05]</a> 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 overlineE:=E/Z(E) ≅ ^2E_6(2).2.

<div class="example"><pre>
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> ]
</pre></div>

By <a href="chapBib.html#biBAGR">[Wil]</a>, 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 overlineE, where the latter is obtained as the 11-th power of the unique conjugacy class of elements of order 22, and overlineE has only one conjugacy class of elements of order 13.

<div class="example"><pre>
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>
</pre></div>

We search through the overlineE-conjugates of <code class="code">g2a</code> 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 <a href="chapBib.html#biBAGR">[Wil]</a>.

To find conjugates, we use the product replacement algorithm to produce pseudo random elements of overlineE. Assuming a genuine random search, the success probability of this approach is as follows: Letting overlineE':=E'/Z(E') ≅ ^2E_6(2), out of the |overlineE'|/|C_overlineE'}(g2a)| conjugates of g2a there are |C_{ overlineE' }(b)|/|C_{ overlineE' }(Fi_{22})| =|C_{ overlineE' }(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 overlineE', the success probability is 6 ⋅ |C_{ overlineE' }(g2a)| ⋅ |C_{ overlineE' }(b)|/|overlineE'| ≈ 2 ⋅ 10^-5.

<div class="example"><pre>
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
</pre></div>

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.

<div class="example"><pre>
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)
</pre></div>

We now return to our original representation.

<div class="example"><pre>
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
</pre></div>

By construction the group generated by a,b is Fi_{22} or 2 × 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 × Fi_{22}; and by the presentation of 2.Fi_{22} available in <a href="chapBib.html#biBAGR">[Wil]</a> 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 × 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 × 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 × 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.

<div class="example"><pre>
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 )
</pre></div>

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.

<div class="example"><pre>
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
</pre></div>

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.

<div class="example"><pre>
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));; 
</pre></div>

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.

<div class="example"><pre>
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
</pre></div>

We apply the appropriate base change to all the generators.

<div class="example"><pre>
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));; 
</pre></div>

Having reached the ultimate choice of basis, we recreate the fixed vector <code class="code">v</code>.

<div class="example"><pre>
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;; 
</pre></div>

Finally we need small faithful permutation representations of the helper subgroups.

<div class="example"><pre>
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) ]
</pre></div>

We could just go on from here, however, sometimes it is useful to save all the created data to disk.

<div class="example"><pre>
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);; 
</pre></div>

This can be loaded again, in particular into a new GAP session, as follows.

<div class="example"><pre>
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);; 
</pre></div>

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 ⋅ 2^20 ≈ 42 MB of memory space. Since 2^32 ≈ 4.3 ⋅ 10^9 is less than [B: 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 <code class="code">OrbitStatisticOnVectorSpace</code> yields an estimated memory requirement of 40 ⋅ 2^32 ⋅ 1/598 ≈ 287 MB. For the large B-orbit, being enumerated by M_{12}-orbits, we similarly get an estimated memory requirement of 584 ⋅ [B: E] ⋅ 1/93060 ≈ 85 MB.

<div class="example"><pre>
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>
</pre></div>

Indeed the saving factor actually achieved is smaller than the best possible estimate given above, but it still has the same order of magnitude.

<div class="chlinkprevnextbot"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap10.html">[Previous Chapter]</a> <a href="chapBib.html">[Next Chapter]</a> </div>

<div class="chlinkbot">Goto Chapter: <a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chap8.html">8</a> <a href="chap9.html">9</a> <a href="chap10.html">10</a> <a href="chap11.html">11</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>

<hr />
generated by <a href="https://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a>
</body>
</html>

quality100%

¤ Dauer der Verarbeitung: 0.13 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.