Ziele Untersuchung
mit Columbo Integrität von
Datenbanken Interaktion und
Portierbarkeit Ergonomie der
Schnittstellen

Angebot Produkte Projekt Beratung

Mittel Analytik Modellierung Sprachen Algebra Logik Hardware Denken Kreativität

Zusammenhänge Gesellschaft Wirtschaft Branche Firma


products/sources/formale Sprachen/GAP/pkg/ctbllib/doc2/ (Algebra von RWTH Aachen Version 4.15.1^©) Datei vom 25.4.2025 mit Größe 597 kB

</tr>
<tr>
<td class="tdright"> </td>
<td class="tdcenter">=</td>
<td class="tdleft">∑_M ∈ ��^'(H,s) 1_M^H(g) / 1_M^H(1)
</tr>
<tr>
<td class="tdright"> </td>
<td class="tdcenter">=</td>
<td class="tdleft">∑_M ∈ ��/~^'(H,s) 1_M^H(g) ⋅ 1_M^H(s) / 1_M^H(1)
</tr>
</table> 
</div>

(Note that no summand for M = S occurs, so each group in ��/~^'(H,s) is self-normalizing.) We abbreviate the right hand side by σ(H,g,s), and set σ^'( H, s ) = max{ σ(H,g,s); g ∈ H ∖ S, |g| = [H:S] }. Then we get P( g, s ) ≤ |T|^-1 ⋅ ∑_t ∈ T σ(H^t,g^t,s) and thus

P( G, s ) ≤ max{ P( S, s ), max{ σ^'( H, s ); S ≤ H ≤ G, [H:S] prime } } .

For convenience, we set P^'(G,s) = max{ P(g,s); g ∈ G ∖ S }.

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

<h5>11.2-2 Computational Criteria</h5>

The following criteria will be used when we have to show the existence or nonexistence of x_1, x_2, ..., x_k, and s ∈ G with the property ⟨ x_i, s ⟩ = G for 1 ≤ i ≤ k. Note that manipulating lists of integers (representing fixed or moved points) is much more efficient than testing whether certain permutations generate a given group.

Lemma:

Let G be a finite group, s ∈ G^×, and X = ⋃_M ∈ ��(G,s) G/M. For x_1, x_2, ..., x_k ∈ G, the conjugate s^' of s satisfies ⟨ x_i, s^' ⟩ = G for 1 ≤ i ≤ k if and only if Fix_X(s^') ∩ ⋃_i=1^k Fix_X(x_i) = ∅ holds.

Proof. If s^g ∈ U ≤ G for some g ∈ G then Fix_X(U) = ∅ if and only if U = G holds; note that Fix_X(G) = ∅, and Fix_X(U) = ∅ implies that U ⊈ h^-1 M h holds for all h ∈ G and M ∈ ��(G,s), thus U = G. Applied to U = ⟨ x_i, s^' ⟩, we get ⟨ x_i, s^' ⟩ = G if and only if Fix_X(s^') ∩ Fix_X(x_i) = Fix_X(U) = ∅.

Corollary 1:

If ��(G,s) = { M } in the situation of the above Lemma then there is a conjugate s^' of s that satisfies ⟨ x_i, s^' ⟩ = G for 1 ≤ i ≤ k if and only if ⋃_i=1^k Fix_X(x_i) ≠ X.

Corollary 2:

Let G be a finite simple group and let X be a G-set such that each g ∈ G fixes at least one point in X but that Fix_X(G) = ∅ holds. If x_1, x_2, ... x_k are elements in G such that ⋃_i=1^k Fix_X(x_i) = X holds then for each s ∈ G there is at least one i with ⟨ x_i, s ⟩ ≠ G.

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

<h4>11.3 GAP Functions for the Computations</h4>

After the introduction of general utilities in Section <a href="chap11.html#X806328747D1D4ECC">11.3-1</a>, we distinguish two different tasks. Section <a href="chap11.html#X7A221012861440E2">11.3-2</a> introduces functions that will be used in the following to compute σ(g,s) with character-theoretic methods. Functions for computing P(g,s) or an upper bound for this value will be introduced in Section <a href="chap11.html#X83DACCF07EF62FAE">11.3-3</a>.

The GAP functions shown in this section are collected in the file <code class="file">tst/probgen.g</code> that is distributed with the GAP Character Table Library, see <a href="http://www.math.rwth-aachen.de/~Thomas.Breuer/ctbllib">http://www.math.rwth-aachen.de/~Thomas.Breuer/ctbllib</a>.

The functions have been designed for the examples in the later sections, they could be generalized and optimized for other examples. It is not our aim to provide a package for this functionality.

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

<h5>11.3-1 General Utilities</h5>

Let <code class="code">list</code> be a dense list and <code class="code">prop</code> be a unary function that returns <code class="keyw">true</code> or <code class="keyw">false</code> when applied to the entries of <code class="code">list</code>. <code class="code">PositionsProperty</code> returns the set of positions in <code class="code">list</code> for which <code class="keyw">true</code> is returned.

<div class="example"><pre>
gap> if not IsBound( PositionsProperty ) then
> PositionsProperty:= function( list, prop )
> return Filtered( [ 1 .. Length( list ) ], i -> prop( list[i] ) );
> end;
> fi;
</pre></div>

The following two functions implement loops over ordered triples (and quadruples, respectively) in a Cartesian product. A prescribed function <code class="code">prop</code> is subsequently applied to the triples (quadruples), and if the result of this call is <code class="keyw">true</code> then this triple (quadruple) is returned immediately; if none of the calls to <code class="code">prop</code> yields <code class="keyw">true</code> then <code class="keyw">fail</code> is returned.

<div class="example"><pre>
gap> BindGlobal( "TripleWithProperty", function( threelists, prop )
> local i, j, k, test;
> 
> for i in threelists[1] do
> for j in threelists[2] do
> for k in threelists[3] do
> test:= [ i, j, k ];
> if prop( test ) then
> return test;
> fi;
> od;
> od;
> od;
> 
> return fail;
> end );
gap> BindGlobal( "QuadrupleWithProperty", function( fourlists, prop )
> local i, j, k, l, test;
> 
> for i in fourlists[1] do
> for j in fourlists[2] do
> for k in fourlists[3] do
> for l in fourlists[4] do
> test:= [ i, j, k, l ];
> if prop( test ) then
> return test;
> fi;
> od;
> od;
> od;
> od;
> 
> return fail;
> end );
</pre></div>

Of course one could do better by considering unordered n-tuples when several of the argument lists are equal, and in practice, backtrack searches would often allow one to prune parts of the search tree in early stages. However, the above loops are not time critical in the examples presented here, so the possible improvements are not worth the effort for our purposes.

The function <code class="code">PrintFormattedArray</code> prints the matrix <code class="code">array</code> in a columnwise formatted way. (The only diference to the GAP library function <code class="func">PrintArray</code> (<a href="../../../doc/ref/chap24.html#X7DEBC9967DFDFC18">Reference: PrintArray</a>) is that <code class="code">PrintFormattedArray</code> chooses each column width according to the entries only in this column not w.r.t. the whole matrix.)

<div class="example"><pre>
gap> BindGlobal( "PrintFormattedArray", function( array )
> local colwidths, n, row;
> array:= List( array, row -> List( row, String ) );
> colwidths:= List( TransposedMat( array ),
> col -> Maximum( List( col, Length ) ) );
> n:= Length( array[1] );
> for row in List( array, row -> List( [ 1 .. n ],
> i -> String( row[i], colwidths[i] ) ) ) do
> Print( " ", JoinStringsWithSeparator( row, " " ), "\n" );
> od;
> end );
</pre></div>

Finally, <code class="code">CleanWorkspace</code> is a utility for reducing the space needed. This is achieved by unbinding those user variables that are not write protected and are not mentioned in the list <code class="code">NeededVariables</code> of variable names that are bound now, and by flushing the caches of tables of marks and character tables.

<div class="example"><pre>
gap> BindGlobal( "NeededVariables", NamesUserGVars() );
gap> BindGlobal( "CleanWorkspace", function()
> local name, record;
> 
> for name in Difference( NamesUserGVars(), NeededVariables ) do
> if not IsReadOnlyGlobal( name ) then
> UnbindGlobal( name );
> fi;
> od;
> for record in [ LIBTOMKNOWN, LIBTABLE ] do
> for name in RecNames( record.LOADSTATUS ) do
> Unbind( record.LOADSTATUS.( name ) );
> Unbind( record.( name ) );
> od;
> od;
> end );
</pre></div>

--> --------------------

--> maximum size reached

--> --------------------

quality97%

¤ Dauer der Verarbeitung: 0.35 Sekunden (vorverarbeitet) ¤

SSL chap11.html Sprache: HTML

products/sources/formale Sprachen/GAP/pkg/ctbllib/doc2/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 (CTblLibXpls) - Chapter 11: GAP Computations Concerning Probabilistic Generation of Finite
Simple Groups</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="X7BE9906583D0FCEC" name="X7BE9906583D0FCEC"></a>
<div class="ChapSects"><a href="chap11.html#X7BE9906583D0FCEC">11 GAP Computations Concerning Probabilistic Generation of Finite
Simple Groups</a>
<div class="ContSect"> <a href="chap11.html#X8389AD927B74BA4A">11.1 Overview</a>

</div>
<div class="ContSect"> <a href="chap11.html#X7B4649CF7B7CFAA1">11.2 Prerequisites</a>

<div class="ContSSBlock">
 <a href="chap11.html#X7B6AEBDF7B857E2E">11.2-1 Theoretical Background</a>

 <a href="chap11.html#X79D7312484E78274">11.2-2 Computational Criteria</a>

</div></div>
<div class="ContSect"> <a href="chap11.html#X7B56BE5384BAD54E">11.3 GAP Functions for the Computations</a>

<div class="ContSSBlock">
 <a href="chap11.html#X806328747D1D4ECC">11.3-1 General Utilities</a>

 <a href="chap11.html#X7A221012861440E2">11.3-2 Character-Theoretic Computations</a>

 <a href="chap11.html#X83DACCF07EF62FAE">11.3-3 Computations with Groups</a>

</div></div>
<div class="ContSect"> <a href="chap11.html#X7A221012861440E2">11.4 Character-Theoretic Computations</a>

<div class="ContSSBlock">
 <a href="chap11.html#X86CE51E180A3D4ED">11.4-1 Sporadic Simple Groups</a>

 <a href="chap11.html#X821778BC7D665AB4">11.4-2 No longer necessary computations for the Baby Monster and the Monster</a>

 <a href="chap11.html#X84E9D10F80A74A53">11.4-3 Automorphism Groups of Sporadic Simple Groups</a>

 <a href="chap11.html#X80DA58F187CDCF5F">11.4-4 Other Simple Groups – Easy Cases</a>

 <a href="chap11.html#X7B1E26D586337487">11.4-5 Automorphism Groups of other Simple Groups – Easy Cases</a>

 <a href="chap11.html#X78B856907ED13545">11.4-6 O_8^-(3)</a>

 <a href="chap11.html#X84AB334886DCA746">11.4-7 O_10^+(2)</a>

 <a href="chap11.html#X84E3E4837BB93977">11.4-8 O_10^-(2)</a>

 <a href="chap11.html#X8307367E7C7C3BCE">11.4-9 O_12^+(2)</a>

 <a href="chap11.html#X834FE1B58119A5FF">11.4-10 O_12^-(2)</a>

 <a href="chap11.html#X7C5980A385C088FA">11.4-11 S_6(4)</a>

 <a href="chap11.html#X829EDF7F7C0BCB8E">11.4-12 ∗ S_6(5)</a>

 <a href="chap11.html#X85162B297E4B67EB">11.4-13 S_8(3)</a>

 <a href="chap11.html#X8495C2BF7B6EFFEF">11.4-14 U_4(4)</a>

 <a href="chap11.html#X7A3BB5AA83A2BDF3">11.4-15 U_6(2)</a>

</div></div>
<div class="ContSect"> <a href="chap11.html#X8237B8617D6F6027">11.5 Computations using Groups</a>

<div class="ContSSBlock">
 <a href="chap11.html#X815320787B601000">11.5-1 A_2m+1, 2 ≤ m ≤ 11</a>

 <a href="chap11.html#X7B5321337B28100B">11.5-2 A_5</a>

 <a href="chap11.html#X82C3B4287B0C7BEE">11.5-3 A_6</a>

 <a href="chap11.html#X85B3C7217B105D4D">11.5-4 A_7</a>

 <a href="chap11.html#X84EA645A82E2BAFB">11.5-5 L_d(q)</a>

 <a href="chap11.html#X855460BE787188B9">11.5-6 ∗ L_d(q) with prime d</a>

 <a href="chap11.html#X7EA88CEF81962F3F">11.5-7 Automorphic Extensions of L_d(q)</a>

 <a href="chap11.html#X7C8806DB8588BB51">11.5-8 L_3(2)</a>

 <a href="chap11.html#X7B7061917ED3714D">11.5-9 M_11</a>

 <a href="chap11.html#X82E0F48A7FF82BB3">11.5-10 M_12</a>

 <a href="chap11.html#X7FF2E8F27FBEB65C">11.5-11 O_7(3)</a>

 <a href="chap11.html#X7F80F2527C424AA4">11.5-12 O_8^+(2)</a>

 <a href="chap11.html#X78F0815B86253A1F">11.5-13 O_8^+(3)</a>

 <a href="chap11.html#X85BACC4A83F73392">11.5-14 O^+_8(4)</a>

 <a href="chap11.html#X86EC26F78609618E">11.5-15 ∗ O_9(3)</a>

 <a href="chap11.html#X8393978A8773997E">11.5-16 O_10^-(3)</a>

 <a href="chap11.html#X7BBBEEEF834F1002">11.5-17 O_14^-(2)</a>

 <a href="chap11.html#X8477457780B69BC7">11.5-18 O_12^+(3)</a>

 <a href="chap11.html#X854D85F287767342">11.5-19 ∗ S_4(8)</a>

 <a href="chap11.html#X82CFBAF07D3487A0">11.5-20 S_6(2)</a>

 <a href="chap11.html#X826658207D9D6570">11.5-21 S_8(2)</a>

 <a href="chap11.html#X82A6496887F80843">11.5-22 ∗ S_10(2)</a>

 <a href="chap11.html#X7A03F8EC839AF0B5">11.5-23 U_4(2)</a>

 <a href="chap11.html#X7D738BE5804CF22E">11.5-24 U_4(3)</a>

 <a href="chap11.html#X7D4BC6A38074BF68">11.5-25 U_6(3)</a>

 <a href="chap11.html#X7A92577A830B5F23">11.5-26 U_8(2)</a>

</div></div>
</div>

<h3>11 GAP Computations Concerning Probabilistic Generation of Finite
Simple Groups</h3>

Date: March 28th, 2012

This is a collection of examples showing how the GAP system <a href="chapBib.html#biBGAP">[GAP24]</a> can be used to compute information about the probabilistic generation of finite almost simple groups. It includes all examples that were needed for the computational results in <a href="chapBib.html#biBBGK">[BGK08]</a>.

The purpose of this writeup is twofold. On the one hand, the computations are documented this way. On the other hand, the GAP code shown for the examples can be used as test input for automatic checking of the data and the functions used.

A first version of this document, which was based on GAP 4.4.10, had been accessible in the web since April 2006 and is available in the arXiv (no. 0710.3267) since October 2007. The differences between that document and the current version are as follows.

<ul>
<li>The format of the GAP output was adjusted to the changed behaviour of GAP until version 4.10. This affects mainly the way how GAP records are printed.

</li>
<li>Several computations are now easier because more character tables of almost simple groups and maximal subgroups of such groups are available in the GAP Character Table Library. (The more involved computations from the original version have been kept in the file.)

</li>
<li>The computation of all conjugacy classes of a subgroup of PΩ^+(12,3) has been replaced by the computation of the conjugacy classes of elements of prime order in this subgroup.

</li>
<li>The irreducible element chosen in the simple group PΩ^-(10,3) has order 61 not 122.

</li>
</ul>
<a id="X8389AD927B74BA4A" name="X8389AD927B74BA4A"></a>

<h4>11.1 Overview</h4>

The main purpose of this note is to document the GAP computations that were carried out in order to obtain the computational results in <a href="chapBib.html#biBBGK">[BGK08]</a>. Table I lists the simple groups among these examples. The first column gives the group names, the second and third columns contain a plus sign + or a minus sign -, depending on whether the quantities σ(G,s) and P(G,s), respectively, are less than 1/3. The fourth column lists the orders of elements s which either prove the + signs or cover most of the cases for proving these signs. The fifth column lists the sections in this note where the example is treated. The rows of the table are ordered alphabetically w.r.t. the group names.

In order to keep this note self-contained, we first describe the theory needed, in Section <a href="chap11.html#X7B4649CF7B7CFAA1">11.2</a>. The translation of the relevant formulae into GAP functions can be found in Section <a href="chap11.html#X7B56BE5384BAD54E">11.3</a>. Then Section <a href="chap11.html#X7A221012861440E2">11.4</a> describes the computations that only require (ordinary) character tables in the GAP Character Table Library <a href="chapBib.html#biBCTblLib">[Bre25]</a>. Computations using also the groups are shown in Section <a href="chap11.html#X8237B8617D6F6027">11.5</a>. In each of the last two sections, the examples are ordered alphabetically w.r.t. the names of the simple groups.

<div class="pcenter"><table class="GAPDocTable">
<caption class="GAPDocTable">Table: Table I: Computations needed in <a href="chapBib.html#biBBGK">[BGK08]</a></caption>
<tr>
<td class="tdleft">G</td>
<td class="tdcenter">σ < frac13</td>
<td class="tdcenter">P < frac13</td>
<td class="tdright">|s|</td>
<td class="tdright">see</td>
</tr>
<tr>
<td class="tdleft">A_5</td>
<td class="tdcenter">-</td>
<td class="tdcenter">-</td>
<td class="tdright">5</td>
<td class="tdright"><a href="chap11.html#X7B5321337B28100B">11.5-2</a></td>
</tr>
<tr>
<td class="tdleft">A_6</td>
<td class="tdcenter">-</td>
<td class="tdcenter">-</td>
<td class="tdright">4</td>
<td class="tdright"><a href="chap11.html#X82C3B4287B0C7BEE">11.5-3</a></td>
</tr>
<tr>
<td class="tdleft">A_7</td>
<td class="tdcenter">-</td>
<td class="tdcenter">-</td>
<td class="tdright">7</td>
<td class="tdright"><a href="chap11.html#X85B3C7217B105D4D">11.5-4</a></td>
</tr>
<tr>
<td class="tdleft">A_8</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">15</td>
<td class="tdright"><a href="chap11.html#X80DA58F187CDCF5F">11.4-4</a>, <a href="chap11.html#X84EA645A82E2BAFB">11.5-5</a></td>
</tr>
<tr>
<td class="tdleft">A_9</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">9</td>
<td class="tdright"><a href="chap11.html#X80DA58F187CDCF5F">11.4-4</a>, <a href="chap11.html#X815320787B601000">11.5-1</a></td>
</tr>
<tr>
<td class="tdleft">A_11</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">11</td>
<td class="tdright"><a href="chap11.html#X80DA58F187CDCF5F">11.4-4</a>, <a href="chap11.html#X815320787B601000">11.5-1</a></td>
</tr>
<tr>
<td class="tdleft">A_13</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">13</td>
<td class="tdright"><a href="chap11.html#X80DA58F187CDCF5F">11.4-4</a>, <a href="chap11.html#X815320787B601000">11.5-1</a></td>
</tr>
<tr>
<td class="tdleft">A_15</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">15</td>
<td class="tdright"><a href="chap11.html#X815320787B601000">11.5-1</a></td>
</tr>
<tr>
<td class="tdleft">A_17</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">17</td>
<td class="tdright"><a href="chap11.html#X815320787B601000">11.5-1</a></td>
</tr>
<tr>
<td class="tdleft">A_19</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">19</td>
<td class="tdright"><a href="chap11.html#X815320787B601000">11.5-1</a></td>
</tr>
<tr>
<td class="tdleft">A_21</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">21</td>
<td class="tdright"><a href="chap11.html#X815320787B601000">11.5-1</a></td>
</tr>
<tr>
<td class="tdleft">A_23</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">23</td>
<td class="tdright"><a href="chap11.html#X815320787B601000">11.5-1</a></td>
</tr>
<tr>
<td class="tdleft">L_3(2)</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">7</td>
<td class="tdright"><a href="chap11.html#X80DA58F187CDCF5F">11.4-4</a>, <a href="chap11.html#X7B1E26D586337487">11.4-5</a>,</td>
</tr>
<tr>
<td class="tdleft"> </td>
<td class="tdcenter"> </td>
<td class="tdcenter"> </td>
<td class="tdright"> </td>
<td class="tdright"><a href="chap11.html#X84EA645A82E2BAFB">11.5-5</a>, <a href="chap11.html#X7C8806DB8588BB51">11.5-8</a></td>
</tr>
<tr>
<td class="tdleft">L_3(3)</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">13</td>
<td class="tdright"><a href="chap11.html#X80DA58F187CDCF5F">11.4-4</a>, <a href="chap11.html#X7B1E26D586337487">11.4-5</a>,</td>
</tr>
<tr>
<td class="tdleft"> </td>
<td class="tdcenter"> </td>
<td class="tdcenter"> </td>
<td class="tdright"> </td>
<td class="tdright"><a href="chap11.html#X84EA645A82E2BAFB">11.5-5</a></td>
</tr>
<tr>
<td class="tdleft">L_3(4)</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">7</td>
<td class="tdright"><a href="chap11.html#X80DA58F187CDCF5F">11.4-4</a>, <a href="chap11.html#X7B1E26D586337487">11.4-5</a></td>
</tr>
<tr>
<td class="tdleft">L_4(3)</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">20</td>
<td class="tdright"><a href="chap11.html#X80DA58F187CDCF5F">11.4-4</a>, <a href="chap11.html#X84EA645A82E2BAFB">11.5-5</a></td>
</tr>
<tr>
<td class="tdleft">L_4(4)</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">85</td>
<td class="tdright"><a href="chap11.html#X84EA645A82E2BAFB">11.5-5</a></td>
</tr>
<tr>
<td class="tdleft">L_6(2)</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">63</td>
<td class="tdright"><a href="chap11.html#X84EA645A82E2BAFB">11.5-5</a></td>
</tr>
<tr>
<td class="tdleft">L_6(3)</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">182</td>
<td class="tdright"><a href="chap11.html#X84EA645A82E2BAFB">11.5-5</a></td>
</tr>
<tr>
<td class="tdleft">L_6(4)</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">455</td>
<td class="tdright"><a href="chap11.html#X84EA645A82E2BAFB">11.5-5</a></td>
</tr>
<tr>
<td class="tdleft">L_6(5)</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">1953</td>
<td class="tdright"><a href="chap11.html#X84EA645A82E2BAFB">11.5-5</a></td>
</tr>
<tr>
<td class="tdleft">L_8(2)</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">255</td>
<td class="tdright"><a href="chap11.html#X84EA645A82E2BAFB">11.5-5</a></td>
</tr>
<tr>
<td class="tdleft">L_10(2)</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">1023</td>
<td class="tdright"><a href="chap11.html#X84EA645A82E2BAFB">11.5-5</a></td>
</tr>
<tr>
<td class="tdleft">M_11</td>
<td class="tdcenter">-</td>
<td class="tdcenter">-</td>
<td class="tdright">11</td>
<td class="tdright"><a href="chap11.html#X7B7061917ED3714D">11.5-9</a></td>
</tr>
<tr>
<td class="tdleft">M_12</td>
<td class="tdcenter">-</td>
<td class="tdcenter">+</td>
<td class="tdright">10</td>
<td class="tdright"><a href="chap11.html#X84E9D10F80A74A53">11.4-3</a>, <a href="chap11.html#X82E0F48A7FF82BB3">11.5-10</a></td>
</tr>
<tr>
<td class="tdleft">O^+_8(2)</td>
<td class="tdcenter">-</td>
<td class="tdcenter">-</td>
<td class="tdright">15</td>
<td class="tdright"><a href="chap11.html#X7F80F2527C424AA4">11.5-12</a></td>
</tr>
<tr>
<td class="tdleft">O^+_8(3)</td>
<td class="tdcenter">-</td>
<td class="tdcenter">-</td>
<td class="tdright">20</td>
<td class="tdright"><a href="chap11.html#X78F0815B86253A1F">11.5-13</a></td>
</tr>
<tr>
<td class="tdleft">O^+_8(4)</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">65</td>
<td class="tdright"><a href="chap11.html#X85BACC4A83F73392">11.5-14</a></td>
</tr>
<tr>
<td class="tdleft">O^+_10(2)</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">45</td>
<td class="tdright"><a href="chap11.html#X84AB334886DCA746">11.4-7</a></td>
</tr>
<tr>
<td class="tdleft">O^+_12(2)</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">85</td>
<td class="tdright"><a href="chap11.html#X8307367E7C7C3BCE">11.4-9</a></td>
</tr>
<tr>
<td class="tdleft">O^+_12(3)</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">205</td>
<td class="tdright"><a href="chap11.html#X8477457780B69BC7">11.5-18</a></td>
</tr>
<tr>
<td class="tdleft">O^-_8(2)</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">17</td>
<td class="tdright"><a href="chap11.html#X80DA58F187CDCF5F">11.4-4</a></td>
</tr>
<tr>
<td class="tdleft">O^-_8(3)</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">41</td>
<td class="tdright"><a href="chap11.html#X78B856907ED13545">11.4-6</a></td>
</tr>
<tr>
<td class="tdleft">O^-_10(2)</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">33</td>
<td class="tdright"><a href="chap11.html#X84E3E4837BB93977">11.4-8</a></td>
</tr>
<tr>
<td class="tdleft">O^-_10(3)</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">122</td>
<td class="tdright"><a href="chap11.html#X8393978A8773997E">11.5-16</a></td>
</tr>
<tr>
<td class="tdleft">O^-_12(2)</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">65</td>
<td class="tdright"><a href="chap11.html#X834FE1B58119A5FF">11.4-10</a></td>
</tr>
<tr>
<td class="tdleft">O^-_14(2)</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">129</td>
<td class="tdright"><a href="chap11.html#X7BBBEEEF834F1002">11.5-17</a></td>
</tr>
<tr>
<td class="tdleft">O_7(3)</td>
<td class="tdcenter">-</td>
<td class="tdcenter">-</td>
<td class="tdright">14</td>
<td class="tdright"><a href="chap11.html#X7FF2E8F27FBEB65C">11.5-11</a></td>
</tr>
<tr>
<td class="tdleft">S_4(4)</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">17</td>
<td class="tdright"><a href="chap11.html#X80DA58F187CDCF5F">11.4-4</a>, <a href="chap11.html#X7B1E26D586337487">11.4-5</a></td>
</tr>
<tr>
<td class="tdleft">S_6(2)</td>
<td class="tdcenter">-</td>
<td class="tdcenter">-</td>
<td class="tdright">9</td>
<td class="tdright"><a href="chap11.html#X82CFBAF07D3487A0">11.5-20</a></td>
</tr>
<tr>
<td class="tdleft">S_6(3)</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">14</td>
<td class="tdright"><a href="chap11.html#X80DA58F187CDCF5F">11.4-4</a>, <a href="chap11.html#X7B1E26D586337487">11.4-5</a></td>
</tr>
<tr>
<td class="tdleft">S_6(4)</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">65</td>
<td class="tdright"><a href="chap11.html#X7C5980A385C088FA">11.4-11</a></td>
</tr>
<tr>
<td class="tdleft">S_8(2)</td>
<td class="tdcenter">-</td>
<td class="tdcenter">-</td>
<td class="tdright">17</td>
<td class="tdright"><a href="chap11.html#X826658207D9D6570">11.5-21</a></td>
</tr>
<tr>
<td class="tdleft">S_8(3)</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">41</td>
<td class="tdright"><a href="chap11.html#X85162B297E4B67EB">11.4-13</a></td>
</tr>
<tr>
<td class="tdleft">U_3(3)</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">6</td>
<td class="tdright"><a href="chap11.html#X80DA58F187CDCF5F">11.4-4</a>, <a href="chap11.html#X7B1E26D586337487">11.4-5</a></td>
</tr>
<tr>
<td class="tdleft">U_3(5)</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">10</td>
<td class="tdright"><a href="chap11.html#X80DA58F187CDCF5F">11.4-4</a>, <a href="chap11.html#X7B1E26D586337487">11.4-5</a></td>
</tr>
<tr>
<td class="tdleft">U_4(2)</td>
<td class="tdcenter">-</td>
<td class="tdcenter">-</td>
<td class="tdright">9</td>
<td class="tdright"><a href="chap11.html#X7A03F8EC839AF0B5">11.5-23</a></td>
</tr>
<tr>
<td class="tdleft">U_4(3)</td>
<td class="tdcenter">-</td>
<td class="tdcenter">+</td>
<td class="tdright">7</td>
<td class="tdright"><a href="chap11.html#X7D738BE5804CF22E">11.5-24</a></td>
</tr>
<tr>
<td class="tdleft">U_4(4)</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">65</td>
<td class="tdright"><a href="chap11.html#X8495C2BF7B6EFFEF">11.4-14</a></td>
</tr>
<tr>
<td class="tdleft">U_5(2)</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">11</td>
<td class="tdright"><a href="chap11.html#X80DA58F187CDCF5F">11.4-4</a></td>
</tr>
<tr>
<td class="tdleft">U_6(2)</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">11</td>
<td class="tdright"><a href="chap11.html#X7A3BB5AA83A2BDF3">11.4-15</a></td>
</tr>
<tr>
<td class="tdleft">U_6(3)</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">122</td>
<td class="tdright"><a href="chap11.html#X7D4BC6A38074BF68">11.5-25</a></td>
</tr>
<tr>
<td class="tdleft">U_8(2)</td>
<td class="tdcenter">+</td>
<td class="tdcenter"> </td>
<td class="tdright">129</td>
<td class="tdright"><a href="chap11.html#X7A92577A830B5F23">11.5-26</a></td>
</tr>
</table> 
</div>

Contrary to <a href="chapBib.html#biBBGK">[BGK08]</a>, Atlas notation is used throughout this note, because the identifiers used for character tables in the GAP Character Table Library follow mainly the Atlas <a href="chapBib.html#biBCCN85">[CCN+85]</a>. For example, we write L_d(q) for PSL(d,q), S_d(q) for PSp(d,q), U_d(q) for PSU(d,q), and O^+_2d(q), O^-_2d(q), O_2d+1(q) for PΩ^+(2d,q), PΩ^-(2d,q), PΩ(2d+1,q), respectively.

Furthermore, in the case of classical groups, the character tables of the (almost) simple groups are considered not the tables of the matrix groups (which are in fact often not available in the GAP Character Table Library). Consequently, also element orders and the description of maximal subgroups refer to the (almost) simple groups not to the matrix groups.

This note contains also several examples that are not needed for the proofs in <a href="chapBib.html#biBBGK">[BGK08]</a>. Besides several small simple groups G whose character table is contained in the GAP Character Table Library and for which enough information is available for computing σ(G), in Section <a href="chap11.html#X80DA58F187CDCF5F">11.4-4</a>, a few such examples appear in individual sections. In the table of contents, the section headers of the latter kind of examples are marked with an asterisk (∗).

The examples use the GAP Character Table Library, the GAP Library of Tables of Marks, and the GAP interface <a href="chapBib.html#biBAtlasRep">[WPN+22]</a> to the Atlas of Group Representations <a href="chapBib.html#biBAGRv3">[WWT+]</a>, so we first load these three packages in the required versions. The GAP output was adjusted to the versions shown below; in older versions, features necessary for the computations may be missing, and it may happen that with newer versions, the behaviour is different.

<div class="example"><pre>
gap> CompareVersionNumbers( GAPInfo.Version, "4.5.0" );
true
gap> LoadPackage( "ctbllib", "1.2", false );
true
gap> LoadPackage( "tomlib", "1.2", false );
true
gap> LoadPackage( "atlasrep", "1.5", false );
true
</pre></div>

Some of the computations in Section <a href="chap11.html#X8237B8617D6F6027">11.5</a> require about 800 MB of space (on 32 bit machines). Therefore we check whether GAP was started with sufficient maximal memory; the command line option for this is <code class="code">-o 800m</code>.

<div class="example"><pre>
gap> max:= GAPInfo.CommandLineOptions.o;;
gap> if not ( ( IsSubset( max, "m" ) and
> Int( Filtered( max, IsDigitChar ) ) >= 800 ) or
> ( IsSubset( max, "g" ) and
> Int( Filtered( max, IsDigitChar ) ) >= 1 ) ) then
> Print( "the maximal allowed memory might be too small\n" );
> fi;
</pre></div>

Several computations involve calls to the GAP function <code class="func">Random</code> (<a href="../../../doc/ref/chap30.html#X7FF906E57D6936F8">Reference: Random</a>). In order to make the results of individual examples reproducible, independent of the rest of the computations, we reset the relevant random number generators whenever this is appropriate. For that, we store the initial states in the variable <code class="code">staterandom</code>, and provide a function for resetting the random number generators. (The <code class="func">Random</code> (<a href="../../../doc/ref/chap30.html#X7FF906E57D6936F8">Reference: Random</a>) calls in the GAP library use the two random number generators <code class="func">GlobalRandomSource</code> (<a href="../../../doc/ref/chap14.html#X7AC96008820FAF1F">Reference: GlobalRandomSource</a>) and <code class="func">GlobalMersenneTwister</code> (<a href="../../../doc/ref/chap14.html#X7AC96008820FAF1F">Reference: GlobalMersenneTwister</a>).)

<div class="example"><pre>
gap> staterandom:= [ State( GlobalRandomSource ),
> State( GlobalMersenneTwister ) ];;
gap> ResetGlobalRandomNumberGenerators:= function()
> Reset( GlobalRandomSource, staterandom[1] );
> Reset( GlobalMersenneTwister, staterandom[2] );
> end;;
</pre></div>

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

<h4>11.2 Prerequisites</h4>

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

<h5>11.2-1 Theoretical Background</h5>

Let G be a finite group, S the socle of G, and denote by G^× the set of nonidentity elements in G. For s, g ∈ G^×, let P( g, s ):= |{ h ∈ G; S ⊈ ⟨ s^h, g ⟩ }| / |G|, the proportion of elements in the class s^G which fail to generate at least S with g; we set P( G, s ):= max{ P( g, s ); g ∈ G^× }. We are interested in finding a class s^G of elements in S such that P( G, s ) < 1/3 holds.

First consider g ∈ S, and let ��(S,s) denote the set of those maximal subgroups of S that contain s. We have

|{ h ∈ S; S ⊈ ⟨ s^h, g ⟩ }| = |{ h ∈ S; ⟨ s, h g h^-1 ⟩ ≠ S }| ≤ ∑_M ∈ ��(S,s) |{ h ∈ S; h g h^-1 ∈ M }|

Since h g h^-1 ∈ M holds if and only if the coset M h is fixed by g under the permutation action of S on the right cosets of M in S, we get that |{ h ∈ S; h g h^-1 ∈ M }| = |C_S(g)| ⋅ |g^S ∩ M| = |M| ⋅ 1_M^S(g), where 1_M^S is the permutation character of this action, of degree |S|/|M|. Thus

|{ h ∈ S; ⟨ s, h g h^-1 ⟩ ≠ S }| / |S| ≤ ∑_M ∈ ��(S,s) 1_M^S(g) / 1_M^S(1) .

We abbreviate the right hand side of this inequality by σ( g, s ), set σ( S, s ):= max{ σ( g, s ); g ∈ S^× }, and choose a transversal T of S in G. Then P( g, s ) ≤ |T|^-1 ⋅ ∑_t ∈ T σ( g^t, s ) and thus P( G, s ) ≤ σ( S, s ) holds.

If S = G and if ��(G,s) consists of a single maximal subgroup M of G then equality holds, i.e., P( g, s ) = σ( g, s ) = 1_M^S(g) / 1_M^S(1).

The quantity 1_M^S(g) / 1_M^S(1) = |g^S ∩ M| / |g^S| is the proportion of fixed points of g in the permutation action of S on the right cosets of its subgroup M. This is called the fixed point ratio of g w. r. t. S/M, and is denoted as μ(g,S/M).

For a subgroup M of S, the number n of S-conjugates of M containing s is equal to |M^S| ⋅ |s^S ∩ M| / |s^S|. To see this, consider the set { (s^h, M^k); h, k ∈ S, s^h ∈ M^k }, the cardinality of which can be counted either as |M^S| ⋅ |s^S ∩ M| or as |s^S| ⋅ n. So we get n = |M| ⋅ 1_M^S(s) / |N_S(M)|.

If S is a finite nonabelian simple group then each maximal subgroup in S is self-normalizing, and we have n = 1_M^S(s) if M is maximal. So we can replace the summation over ��(S,s) by one over a set ��/~(S,s) of representatives of conjugacy classes of maximal subgroups of S, and get that

σ( g, s ) = ∑_M ∈ ��/~(S,s) frac1_M^S(s) ⋅ 1_M^S(g)1_M^S(1).

Furthermore, we have |��(S,s)| = ∑_M ∈ ��/~(S,s) 1_M^S(s).

In the following, we will often deal with the quantities σ(S):= min{ σ( S, s ); s ∈ S^× } and ��/~(S):= ⌈ 1 / σ(S) - 1 ⌉. These values can be computed easily from the primitive permutation characters of S.

Analogously, we set P(S):= min { P( S, s ); s ∈ S^× } and P(S):= ⌈ 1 / P(S) - 1 ⌉. Clearly we have P(S) ≤ σ(S) and P(S) ≥ ��/~(S).

One interpretation of P(S) is that if this value is at least k then it follows that for any g_1, g_2, ..., g_k ∈ S^×, there is some s ∈ S such that S = ⟨ g_i, s ⟩, for 1 ≤ i ≤ k. In this case, S is said to have spread at least k. (Note that the lower bound ��/~(S) for P(S) can be computed from the list of primitive permutation characters of S.)

Moreover, P(S) ≥ k implies that the element s can be chosen uniformly from a fixed conjugacy class of S. This is called uniform spread at least k in <a href="chapBib.html#biBBGK">[BGK08]</a>.

It is proved in <a href="chapBib.html#biBGK">[GK00]</a> that all finite simple groups have uniform spread at least 1, that is, for any element x ∈ S^×, there is an element y in a prescribed class of S such that G = ⟨ x, y ⟩ holds. In <a href="chapBib.html#biBBGK">[BGK08, Corollary 1.3]</a>, it is shown that all finite simple groups have uniform spread at least 2, and the finite simple groups with (uniform) spread exactly 2 are listed.

Concerning the spread, it should be mentioned that the methods used here and in <a href="chapBib.html#biBBGK">[BGK08]</a> are nonconstructive in the sense that they cannot be used for finding an element s that generates G together with each of the k prescribed elements g_1, g_2, ..., g_k.

Now consider g ∈ G ∖ S. Since P( g^k, s ) ≥ P( g, s ) for any positive integer k, we can assume that g has prime order p, say. We set H = ⟨ S, g ⟩ ≤ G, with [H:S] = p, choose a transversal T of H in G, let ��^'(H,s):= 𝕄(H,s) ∖ { S }, and let 𝕄/~^'(H,s) denote a set of representatives of H-conjugacy classes of these groups. As above,

<div class="pcenter"><table class="GAPDocTablenoborder">
<tr>
<td class="tdright">|{ h ∈ H; S ⊈ ⟨ s^h, g ⟩ }| / |H|</td>
<td class="tdcenter">=</td>
<td class="tdleft">|{ h ∈ H; ⟨ s^h, g ⟩ ≠ H }| / |H|</td>
</tr>
<tr>
<td class="tdright"> </td>
<td class="tdcenter">≤</td>
<td class="tdleft">∑_M ∈ ��^'(H,s) |{ h ∈ H; h g h^-1 ∈ M }| / |H|

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.