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 124 kB

SSL chap4.html Sprache: HTML

products/sources/formale Sprachen/GAP/pkg/ctbllib/doc2/chap4.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 4: GAP Computations Concerning Hamiltonian Cycles in the Generating Graphs of Finite 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="chap4" 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="chap3.html">[Previous Chapter]</a> <a href="chap5.html">[Next Chapter]</a> </div>

<a href="chap4_mj.html">[MathJax on]</a>
<a id="X7D5919C182B1A462" name="X7D5919C182B1A462"></a>
<div class="ChapSects"><a href="chap4.html#X7D5919C182B1A462">4 GAP Computations Concerning Hamiltonian Cycles in the Generating Graphs of Finite Groups</a>
<div class="ContSect"> <a href="chap4.html#X8389AD927B74BA4A">4.1 Overview</a>

</div>
<div class="ContSect"> <a href="chap4.html#X7B6AEBDF7B857E2E">4.2 Theoretical Background</a>

<div class="ContSSBlock">
 <a href="chap4.html#X7AD3962D7AE4ADFB">4.2-1 Character-Theoretic Lower Bounds for Vertex Degrees</a>

 <a href="chap4.html#X825776BA8687E475">4.2-2 Checking the Criteria</a>

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

<div class="ContSSBlock">
 <a href="chap4.html#X802B2ED2802334B0">4.3-1 Computing Vertex Degrees from the Group</a>

 <a href="chap4.html#X87FE2DDD7F086D2F">4.3-2 Computing Lower Bounds for Vertex Degrees</a>

 <a href="chap4.html#X8677A8B1788ACD2C">4.3-3 Evaluating the (Lower Bounds for the) Vertex Degrees</a>

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

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

 <a href="chap4.html#X867D338F7F453092">4.4-2 The Monster</a>

 <a href="chap4.html#X7DC6DFCC83502CC3">4.4-3 Nonsimple Automorphism Groups of Sporadic Simple Groups</a>

 <a href="chap4.html#X8130C9CB7A33140F">4.4-4 Alternating and Symmetric Groups A_n, S_n,
for 5 ≤ n ≤ 13</a>

</div></div>
<div class="ContSect"> <a href="chap4.html#X83DACCF07EF62FAE">4.5 Computations With Groups</a>

<div class="ContSSBlock">
 <a href="chap4.html#X7B9ADC91802EE09F">4.5-1 Nonabelian Simple Groups of Order up to 10^7</a>

 <a href="chap4.html#X8033892B7FD6E62B">4.5-2 Nonsimple Groups with Nonsolvable Socle of Order at most 10^6</a>

</div></div>
<div class="ContSect"> <a href="chap4.html#X84E62545802FAB30">4.6 The Groups PSL(2,q)</a>

</div>
</div>

<h3>4 GAP Computations Concerning Hamiltonian Cycles in the Generating Graphs of Finite Groups</h3>

Date: April 24th, 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 generating graphs of finite groups. It includes all examples that were needed for the computational results in <a href="chapBib.html#biBGMN">[BGL+10]</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.12, is available in the arXiv at <a href="http://arxiv.org/abs/0911.5589v1">http://arxiv.org/abs/0911.5589v1</a> since November 2009. The differences between this file and the current document are as follows.

<ul>
<li>The format of the GAP output was adjusted to the changed behaviour of GAP 4.5.

</li>
<li>The records returned by <code class="func">IsomorphismTypeInfoFiniteSimpleGroup</code> (<a href="../../../doc/ref/chap39.html#X7C6AA6897C4409AC">Reference: IsomorphismTypeInfoFiniteSimpleGroup</a>) contain a component <code class="code">"shortname"</code> since GAP 4.11.

</li>
<li>The lower bounds computed for the sporadic simple Monster group have been improved in three steps.

First, the existence of exactly one class of maximal subgroups of the type PSL(2, 41) (see <a href="chapBib.html#biBNW12">[NW13]</a>) and the nonexistence of maximal subgroups with socle PSL(2, 27) (see <a href="chapBib.html#biBWil10">[Wil10]</a>) have been incorporated.

Second, the classification of classes of maximal subgroups of the Monster has been completed in <a href="chapBib.html#biBDLP25">[DLP25]</a>. As a consequence, the nonexistence of maximal subgroups with socle Sz(8) and PSU(3, 8) and the existence of exactly one class of maximal subgroups with the isomorphism types PSL(2, 13).2 and PSU(3, 4).4 have been proved, and the proof of the nonexistence of the previously claimed subgroups of the type L_2(59) yields that the Monster has maximal subgroups of the type 59:29. Moreover, meanwhile also all class fusions of the maximal subgroups are known; previously, we got only candidates for some primitive permutation characters.

Third, all character tables of maximal subgroups of the Monster group and their class fusions are available since version 1.3.10 of CTblLib, hence no special treatment for the Monster group is needed anymore in order to compute its primitive permutation characters. In particular, the data file <code class="file">data/prim_perm_M.json</code> of CTblLib is no longer needed. In earlier versions, that file had been used to collect information about primitive permutation characters for which the character table was not yet available.

See Section <a href="chap4.html#X867D338F7F453092">4.4-2</a> for comments on earlier versions, and for the bounds that had been computed from the partial information that was available at that time.

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

<h4>4.1 Overview</h4>

The 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#biBGMN">[BGL+10]</a>.

In order to keep this note self-contained, we first describe the theory needed, in Section <a href="chap4.html#X7B6AEBDF7B857E2E">4.2</a>. The translation of the relevant formulae into GAP functions can be found in Section <a href="chap4.html#X7B56BE5384BAD54E">4.3</a>. Then Section <a href="chap4.html#X7A221012861440E2">4.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="chap4.html#X83DACCF07EF62FAE">4.5</a>.

The examples use the GAP Character Table Library and the GAP Library of Tables of Marks, so we first load these packages in the required versions.

<div class="example"><pre>
gap> if not CompareVersionNumbers( GAPInfo.Version, "4.5" ) then
> Error( "need GAP in version at least 4.5" );
> fi;
gap> LoadPackage( "ctbllib", "1.2", false );
true
gap> LoadPackage( "tomlib", "1.1.1", false );
true
</pre></div>

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

<h4>4.2 Theoretical Background</h4>

Let G be a finite noncyclic group and denote by G^× the set of nonidentity elements in G. We define the generating graph Γ(G) as the undirected graph on the vertex set G^× by joining two elements x, y ∈ G^× by an edge if and only if ⟨ x, y ⟩ = G holds. For x ∈ G^×, the vertex degree d(Γ, x) is |{ y ∈ G^×; ⟨ x, y ⟩ = G }|. The closure cl(Γ) of the graph Γ with m vertices is defined as the graph with the same vertex set as Γ, where the vertices x, y are joined by an edge if they are joined by an edge in Γ or if d(Γ, x) + d(Γ, y) ≥ m. We denote iterated closures by cl^(i)(Γ) = cl(cl^(i-1)(Γ)), where cl^(0)(Γ) = Γ.

In the following, we will show that the generating graphs of the following groups contain a Hamiltonian cycle:

<ul>
<li>Nonabelian simple groups of orders at most 10^7,

</li>
<li>groups G containing a unique minimal normal subgroup N such that N has order at most 10^6, N is nonsolvable, and G/N is cyclic,

</li>
<li>sporadic simple groups and their automorphism groups.

</li>
</ul>
Clearly the condition that G/N is cyclic for all nontrivial normal subgroups N of G is necessary for Γ(G) being connected, and <a href="chapBib.html#biBGMN">[BGL+10, Conjecture 1.6]</a> states that this condition is also sufficient. By <a href="chapBib.html#biBGMN">[BGL+10, Proposition 1.1]</a>, this conjecture is true for all solvable groups, and the second entry in the above list implies that this conjecture holds for all nonsolvable groups of order up to 10^6.

The question whether a graph Γ contains a Hamiltonian cycle (i. e., a closed path in Γ that visits each vertex exactly once) can be answered using the following sufficient criteria (see <a href="chapBib.html#biBGMN">[BGL+10]</a>). Let d_1 ≤ d_2 ≤ ⋯ ≤ d_m be the vertex degrees in Γ.

<dl>
<dt>Pósa's criterion:
<dd>If d_k ≥ k+1 holds for 1 ≤ k < m/2 then Γ contains a Hamiltonian cycle.

</dd>
<dt>Chvátal's criterion:
<dd>If d_k ≥ k+1 or d_m-k ≥ m-k holds for 1 ≤ k < m/2 then Γ contains a Hamiltonian cycle.

</dd>
<dt>Closure criterion:</dt>
<dd>A graph contains a Hamiltonian cycle if and only if its closure contains a Hamiltonian cycle.

</dd>
</dl>
<a id="X7AD3962D7AE4ADFB" name="X7AD3962D7AE4ADFB"></a>

<h5>4.2-1 Character-Theoretic Lower Bounds for Vertex Degrees</h5>

Using character-theoretic methods similar to those used to obtain the results in <a href="chapBib.html#biBBGK">[BGK08]</a> (the computations for that paper are shown in <a href="chapBib.html#biBProbGenArxiv">[Breb]</a>), we can compute lower bounds for the vertex degrees in generating graphs, as follows.

Let R be a set of representatives of conjugacy classes of nonidentity elements in G, fix s ∈ G^×, let ��(G,s) denote the set of those maximal subgroups of G that contain s, let ��(G,s)/∼ denote a set of representatives in ��(G,s) w. r. t. conjugacy in G. For a subgroup M of G, the permutation character 1_M^G is defined by

1_M^G(g):= (|G| ⋅ |g^G ∩ M|) / (|M| ⋅ |g^G|),

where g^G = { g^x; x ∈ G }, with g^x = x^-1 g x, denotes the conjugacy class of g in G. So we have 1_M^G(1) = |G|/|M| and thus |g^G ∩ M| = |g^G| ⋅ 1_M^G(g) / 1_M^G(1).

Doubly counting the set { (s^x, M^y); x, y ∈ G, s^x ∈ M^y } yields |M^G| ⋅ |s^G ∩ M| = |s^G| ⋅ |{ M^x; x ∈ G, s ∈ M^x }| and thus |{ M^x; x ∈ G, s ∈ M^x }| = |M^G| ⋅ 1_M^G(s) / 1_M^G(1) ≤ 1_M^G(s). (If M is a maximal subgroup of G then either M is normal in G or self-normalizing, and in the latter case the inequality is in fact an equality.)

Let Π denote the multiset of primitive permutation characters of G, i. e., of the permutation characters 1_M^G where M ranges over representatives of the conjugacy classes of maximal subgroups of G.

Define

δ(s, g^G):= |g^G| ⋅ max{ 0, 1 - ∑_{π ∈ Π} π(g) ⋅ π(s) / π(1) }

and d(s, g^G):= |{ x ∈ g^G; ⟨ s, x ⟩ = G }|, the contribution of the class g^G to the vertex degree of s. Then we have d(Γ(G), s) = ∑_{x ∈ R} d(s, x^G) and

<div class="pcenter"><table> <tr> <td class="tdright">d(s, g^G)</td> <td class="tdcenter">=</td> <td class="tdleft">|g^G| - |⋃_{M ∈ M(G,s)} { x ∈ g^G; ⟨ x, s ⟩ ⊆ M }|</td> </tr> <td class="tdright"> </td> <td class="tdcenter">≥</td> <td class="tdleft">|g^G| ⋅ max{ 0, 1 - Σ_{M ∈ M(G,s)} 1_M^G(g) / 1_M^G(1) }</td> <tr> <td class="tdright"> </td> <td class="tdcenter">=</td> <td class="tdcenter">|g^G| ⋅ max{ 0, 1 - Σ_{M ∈ M(G,s)} 1_M^G(g) / 1_M^G(1) }</td> </tr> <tr> <td class="tdright"> </td> <td class="tdcenter">≥</td> <td class="tdcenter">|g^G| ⋅ max{ 0, 1 - Σ_{M ∈ M(G,s)/∼} 1_M^G(g) ⋅ 1_M^G(s) / 1_M^G(1) }</td> </tr> <tr> <td class="tdright"> </td> <td class="tdcenter">=</td> <td class="tdcenter">δ(s, g^G)</td> </tr> </table> </div>

So δ(s):= ∑_x ∈ R δ(s, x^G) is a lower bound for the vertex degree of s; this bound can be computed if Π is known.

For computing the vertex degrees of the iterated closures of Γ(G), we define d^(0)(s, g^G):= d(s, g^G) and

d^(i+1)(s,g^G):= |g^G| if d^(i)(Г(G),s) + d^(i)(Г(G),g) ≥ |G|-1, and d^(i+1)(s,g^G):= d^(i)(s,g^G) otherwise. </Alt>  Then <M>d(&cl;^{(i)}(\Gamma(G)), s) = \sum_{{x \in R}} d^{(i)}(s, g^G)</M> holds. Analogously, we set <M>\delta^{(0)}(s, g^G):= \delta(s, g^G)</M>, <Alt Only="LaTeX"><![CDATA[ \[ \delta^{(i+1)}(s, g^G):= \left\{ \begin{array}{lcl} |g^G| & ;; & \delta^{(i)}(s) + \delta^{(i)}(g) \geq |G|-1 \\ \delta^{(i)}(s, g^G) & ; & \mbox{\rm otherwise} \end{array} \right. \]

δ^(i+1)(s, g^G):= |g^G| if δ^(i)(s) + δ^(i)(g) ≥ |G|-1, δ^(i+1)(s, g^G):= δ^(i)(s, g^G) otherwise, and δ^(i)(s):= ∑_{x ∈ R} δ^(i)(s, x^G), a lower bound for d(cl^(i)(Γ(G)), s) that can be computed if Π is known.

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

<h5>4.2-2 Checking the Criteria</h5>

Let us assume that we know lower bounds β(s) for the vertex degrees d(cl^(i)(Γ(G)), s), for some fixed i, and let us choose representatives s_1, s_2, ..., s_l of the nonidentity conjugacy classes of G such that β(s_1) ≤ β(s_2) ≤ ⋯ ≤ β(s_l) holds. Let c_k = |s_k^G| be the class lengths of these representatives.

Then the first c_1 vertex degrees, ordered by increasing size, are larger than or equal to β(s_1), the next c_2 vertex degrees are larger than or equal to β(s_2), and so on.

Then the set of indices in the k-th nonidentity class of G for which Pósa's criterion is not guaranteed by the given bounds is

{ x; c_1 + c_2 + ⋯ + c_k-1 < x ≤ c_1 + c_2 + ⋯ c_k, x < (|G| - 1) / 2, β(s_k) < x+1 }.

This is an interval { L_k, L_k + 1, ..., U_k } with

L_k = max{ 1 + c_1 + c_2 + ⋯ + c_k-1, β(s_k) }

and

U_k = min{ c_1 + c_2 + ⋯ + c_k, ⌊ |G|/2 ⌋ - 1 } .

(Note that the generating graph has m = |G|-1 vertices, and that x < m/2 is equivalent to x ≤ ⌊ |G|/2 ⌋ - 1.)

The generating graph Γ(G) satisfies Pósa's criterion if all these intervals are empty, i. e., if L_k > U_k holds for 1 ≤ k ≤ l.

The set of indices for which Chvátal's criterion is not guaranteed is the intersection of

{ m-k; 1 ≤ m-k < m/2, d_k < k }

with the set of indices for which Pósa's criterion is not guaranteed.

Analogously to the above considerations, the set of indices m-x in the former set for which Chvátal's criterion is not guaranteed by the given bounds and such that x is an index in the k-th nonidentity class of G is

{ m-x; c_1 + c_2 + ⋯ + c_k-1 < x ≤ c_1 + c_2 + ⋯ c_k, 1 ≤ m-x < (|G| - 1) / 2, β(s_k) < x }.

This is again an interval { L^'_k, L^'_k + 1, ..., U^'_k } with

L^'_k = max{ 1, m - ( c_1 + c_2 + ⋯ + c_k ) }

and

U^'_k = min{ m - ( c_1 + c_2 + ⋯ + c_k-1 ) - 1, ⌊ |G|/2 ⌋ - 1, m-1 - β(s_k) } .

The generating graph Γ(G) satisfies Chvátal's criterion if the union of the intervals { L^'_k, L^'_k + 1, ..., U^'_k }, for 1 ≤ k ≤ l is disjoint to the union of the intervals { L_k, L_k + 1, ..., U_k }, for 1 ≤ k ≤ l.

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

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

We describe two approaches to compute, for a given group G, vertex degrees for the generating graph of G or lower bounds for them, by calculating exact vertex degrees from G itself (see Section <a href="chap4.html#X802B2ED2802334B0">4.3-1</a>) or by deriving lower bounds for the vertex degrees using just character-theoretic information about G and its subgroups (see Section <a href="chap4.html#X87FE2DDD7F086D2F">4.3-2</a>). Finally, Section <a href="chap4.html#X8677A8B1788ACD2C">4.3-3</a> deals with deriving lower bounds of vertex degrees of iterated closures.

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

<h5>4.3-1 Computing Vertex Degrees from the Group</h5>

In this section, the task is to compute the vertex degrees d(s,g^G) using explicit computations with the group G.

The function <code class="code">IsGeneratorsOfTransPermGroup</code> checks whether the permutations in the list <code class="code">list</code> generate the permutation group <code class="code">G</code>, provided that <code class="code">G</code> is transitive on its moved points. (Note that testing the necessary condition that the elements in <code class="code">list</code> generate a transitive group is usually much faster than testing generation.) This function has been used already in <a href="chapBib.html#biBProbGenArxiv">[Breb]</a>.

<div class="example"><pre>
gap> IsGeneratorsOfTransPermGroup:= function( G, list )
> local S;
> 
> if not IsTransitive( G ) then
> Error( "<G> must be transitive on its moved points" );
> fi;
> S:= SubgroupNC( G, list );
> 
> return IsTransitive( S, MovedPoints( G ) )
> and Size( S ) = Size( G );
> end;;
</pre></div>

The function <code class="code">VertexDegreesGeneratingGraph</code> takes a transitive permutation group G (in order to be allowed to use <code class="code">IsGeneratorsOfTransPermGroup</code>), the list <code class="code">classes</code> of conjugacy classes of G (in order to prescribe an ordering of the classes), and a list <code class="code">normalsubgroups</code> of proper normal subgroups of G, and returns the matrix [ d(s, g^G) ]_s, g of vertex degrees, with rows and columns indexed by nonidentity class representatives ordered as in the list <code class="code">classes</code>. (The class containing the identity element may be contained in <code class="code">classes</code>.)

The following criteria are used in this function.

<ul>
<li>The function tests the (non)generation only for representatives of C_G(g)-C_G(s)-double cosets, where C_G(g):= { x ∈ G; g x = x g } denotes the centralizer of g in G. Note that for c_1 ∈ C_G(g), c_2 ∈ C_G(s), and a representative r ∈ G, we have ⟨ s, g^c_1 r c_2 ⟩ = ⟨ s, g^r ⟩^c_2. If ⟨ s, g^r ⟩ = G then the double coset D = C_G(g) r C_G(s) contributes |D|/|C_G(g)| to the vertex degree d(s, g^G), otherwise the contribution is zero.

</li>
<li>We have d(s, g^G) ⋅ |C_G(g)| = d(g, s^G) ⋅ |C_G(s)|. (To see this, either establish a bijection of the above double cosets, or doubly count the edges between elements of the conjugacy classes of s and g.)

</li>
<li>If ⟨ s_1 ⟩ = ⟨ s_2 ⟩ and ⟨ g_1 ⟩ = ⟨ g_2 ⟩ hold then we have d(s_1, g_1^G) = d(s_2, g_1^G) = d(s_1, g_2^G) = d(s_2, g_2^G), so only one of these values must be computed.

</li>
<li>If both s and g are contained in one of the normal subgroups given then d(s, g^G) is zero.

</li>
<li>If G is not a dihedral group and both s and g are involutions then d(s, g^G) is zero.

</li>
</ul>

<div class="example"><pre>
gap> BindGlobal( "VertexDegreesGeneratingGraph",
> function( G, classes, normalsubgroups )
> local nccl, matrix, cents, powers, normalsubgroupspos, i, j, g_i,
> nsg, g_j, gen, pair, d, pow;
> 
> if not IsTransitive( G ) then
> Error( "<G> must be transitive on its moved points" );
> fi;
> 
> classes:= Filtered( classes,
> C -> Order( Representative( C ) ) <> 1 );
> nccl:= Length( classes );
> matrix:= [];
> cents:= [];
> powers:= [];
> normalsubgroupspos:= [];
> for i in [ 1 .. nccl ] do
> matrix[i]:= [];
> if IsBound( powers[i] ) then
> # The i-th row equals the earlier row 'powers[i]'.
> for j in [ 1 .. i ] do
> matrix[i][j]:= matrix[ powers[i] ][j];
> matrix[j][i]:= matrix[j][ powers[i] ];
> od;
> else
> # We have to compute the values.
> g_i:= Representative( classes[i] );
> nsg:= Filtered( [ 1 .. Length( normalsubgroups ) ],
> i -> g_i in normalsubgroups[i] );
> normalsubgroupspos[i]:= nsg;
> cents[i]:= Centralizer( G, g_i );
> for j in [ 1 .. i ] do
> g_j:= Representative( classes[j] );
> if IsBound( powers[j] ) then
> matrix[i][j]:= matrix[i][ powers[j] ];
> matrix[j][i]:= matrix[ powers[j] ][i];
> elif not IsEmpty( Intersection( nsg, normalsubgroupspos[j] ) )
> or ( Order( g_i ) = 2 and Order( g_j ) = 2
> and not IsDihedralGroup( G ) ) then
> matrix[i][j]:= 0;
> matrix[j][i]:= 0;
> else
> # Compute $d(g_i, g_j^G)$.
> gen:= 0;
> for pair in DoubleCosetRepsAndSizes( G, cents[j],
> cents[i] ) do
> if IsGeneratorsOfTransPermGroup( G,
> [ g_i, g_j^pair[1] ] ) then
> gen:= gen + pair[2];
> fi;
> od;
> matrix[i][j]:= gen / Size( cents[j] );
> if i <> j then
> matrix[j][i]:= gen / Size( cents[i] );
> fi;
> fi;
> od;
> 
> # For later, provide information about algebraic conjugacy.
> for d in Difference( PrimeResidues( Order( g_i ) ), [ 1 ] ) do
> pow:= g_i^d;
> for j in [ i+1 .. nccl ] do
> if not IsBound( powers[j] ) and pow in classes[j] then
> powers[j]:= i;
> break;
> fi;
> od;
> od;
> fi;
> od;
> 
> return matrix;
> end );
</pre></div>

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

<h5>4.3-2 Computing Lower Bounds for Vertex Degrees</h5>

In this section, the task is to compute the lower bounds δ(s, g^G) for the vertex degrees d(s, g^G) using character-theoretic methods.

We provide GAP functions for computing the multiset Π of the primitive permutation characters of a given group G and for computing the lower bounds δ(s, g^G) from Π.

For many almost simple groups, the GAP libraries of character tables and of tables of marks contain information for quickly computing the primitive permutation characters of the group in question. Therefore, the function <code class="code">PrimitivePermutationCharacters</code> takes as its argument not the group G but its character table T, say. (This function is shown already in <a href="chapBib.html#biBProbGenArxiv">[Breb]</a>.)

If T is contained in the GAP Character Table Library (see <a href="chapBib.html#biBCTblLib">[Bre25]</a>) then the complete set of primitive permutation characters can be easily computed if the character tables of all maximal subgroups and their class fusions into T are known (in this case, we check whether the attribute <code class="func">Maxes</code> (<a href="../doc/chap3.html#X8150E63F7DBDF252">CTblLib: Maxes</a>) of T is bound) or if the table of marks of G and the class fusion from T into this table of marks are known (in this case, we check whether the attribute <code class="func">FusionToTom</code> (<a href="../doc/chap3.html#X7B1AAED68753B1BE">CTblLib: FusionToTom</a>) of T is bound). If the attribute <code class="func">UnderlyingGroup</code> (<a href="../../../doc/ref/chap70.html#X81E41D3880FA6C4C">Reference: UnderlyingGroup for tables of marks</a>) of T is bound then the group stored as the value of this attribute can be used to compute the primitive permutation characters. The latter happens if T was computed from the group G; for tables in the GAP Character Table Library, this is not the case by default.

The GAP function <code class="code">PrimitivePermutationCharacters</code> tries to compute the primitive permutation characters of a group using this information; it returns the required list of characters if this can be computed this way, otherwise <code class="keyw">fail</code> is returned. (For convenience, we use the GAP mechanism of attributes in order to store the permutation characters in the character table object once they have been computed.)

<div class="example"><pre>
gap> DeclareAttribute( "PrimitivePermutationCharacters",
> IsCharacterTable );
gap> InstallOtherMethod( PrimitivePermutationCharacters,
> [ IsCharacterTable ],
> function( tbl )
> local maxes, i, fus, poss, tom, G;
> 
> if HasMaxes( tbl ) then
> maxes:= List( Maxes( tbl ), CharacterTable );
> for i in [ 1 .. Length( maxes ) ] do
> fus:= GetFusionMap( maxes[i], tbl );
> if fus = fail then
> fus:= PossibleClassFusions( maxes[i], tbl );
> poss:= Set( fus,
> map -> InducedClassFunctionsByFusionMap(
> maxes[i], tbl,
> [ TrivialCharacter( maxes[i] ) ], map )[1] );
> if Length( poss ) = 1 then
> maxes[i]:= poss[1];
> else
> return fail;
> fi;
> else
> maxes[i]:= TrivialCharacter( maxes[i] )^tbl;
> fi;
> od;
> return maxes;
> elif HasFusionToTom( tbl ) then
> tom:= TableOfMarks( tbl );
> maxes:= MaximalSubgroupsTom( tom );
> return PermCharsTom( tbl, tom ){ maxes[1] };
> elif HasUnderlyingGroup( tbl ) then
> G:= UnderlyingGroup( tbl );
> return List( MaximalSubgroupClassReps( G ),
> M -> TrivialCharacter( M )^tbl );
> fi;
> 
> return fail;
> end );
</pre></div>

The next function computes the lower bounds δ(s, g^G) from the two lists <code class="code">classlengths</code> of conjugacy class lengths of the group G and <code class="code">prim</code> of all primitive permutation characters of G. (The first entry in <code class="code">classlengths</code> is assumed to represent the class containing the identity element of G.) The return value is the matrix that contains in row i and column j the value δ(s, g^G), where s and g are in the conjugacy classes represented by the (i+1)-st and (j+1)-st column of <code class="code">tbl</code>, respectively. So the row sums of this matrix are the values δ(s).

<div class="example"><pre>
gap> LowerBoundsVertexDegrees:= function( classlengths, prim )
> local sizes, nccl;
> 
> nccl:= Length( classlengths );
> return List( [ 2 .. nccl ],
> i -> List( [ 2 .. nccl ],
> j -> Maximum( 0, classlengths[j] - Sum( prim,
> pi -> classlengths[j] * pi[j] * pi[i]
> / pi[1] ) ) ) );
> end;;
</pre></div>

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

<h5>4.3-3 Evaluating the (Lower Bounds for the) Vertex Degrees</h5>

In this section, the task is to compute (lower bounds for) the vertex degrees of iterated closures of a generating graph from (lower bounds for) the vertex degrees of the graph itself, and then to check the criteria of Pósa and Chvátal.

The arguments of all functions defined in this section are the list <code class="code">classlengths</code> of conjugacy class lengths for the group G (including the class of the identity element, in the first position) and a matrix <code class="code">bounds</code> of the values d^(i)(s, g^G) or δ^(i)(s, g^G), with rows and columns indexed by nonidentity class representatives s and g, respectively. Such a matrix is returned by the functions <code class="code">VertexDegreesGeneratingGraph</code> or <code class="code">LowerBoundsVertexDegrees</code>, respectively.

The function <code class="code">LowerBoundsVertexDegreesOfClosure</code> returns the corresponding matrix of the values d^(i+1)(s, g^G) or δ^(i+1)(s, g^G), respectively.

<div class="example"><pre>
gap> LowerBoundsVertexDegreesOfClosure:= function( classlengths, bounds )
> local delta, newbounds, size, i, j;
> 
> delta:= List( bounds, Sum );
> newbounds:= List( bounds, ShallowCopy );
> size:= Sum( classlengths );
> for i in [ 1 .. Length( bounds ) ] do
> for j in [ 1 .. Length( bounds ) ] do
> if delta[i] + delta[j] >= size - 1 then
> newbounds[i][j]:= classlengths[ j+1 ];
> fi;
> od;
> od;
> 
> return newbounds;
> end;;
</pre></div>

Once the values d^(i)(s, g^G) or δ^(i)(s, g^G) are known, we can check whether Pósa's or Chvátal's criterion is satisfied for the graph cl^(i)(Γ(G)), using the function <code class="code">CheckCriteriaOfPosaAndChvatal</code> shown below. (Of course a negative result is meaningless in the case that only lower bounds for the vertex degrees are used.)

The idea is to compute the row sums of the given matrix, and to compute the intervals { L_k, L_k + 1, ..., U_k } and { L^'_k, L^'_k + 1, ..., U^'_k } that were introduced in Section 4.2-2.

The function <code class="code">CheckCriteriaOfPosaAndChvatal</code> returns, given the list of class lengths of G and the matrix of (bounds for the) vertex degrees, a record with the components <code class="code">badForPosa</code> (the list of those pairs [ L_k, U_k ] with the property L_k ≤ U_k), <code class="code">badForChvatal</code> (the list of pairs of lower and upper bounds of nonempty intervals where Chvátal's criterion may be violated), and data (the sorted list of triples [ δ(g_k), |g_k^G|, ι(k) ], where ι(k) is the row and column position of g_k in the matrix bounds). The ordering of class lengths must of course be compatible with the ordering of rows and columns of the matrix, and the identity element of G must belong to the first entry in the list of class lengths.

<div class="example"><pre>
gap> CheckCriteriaOfPosaAndChvatal:= function( classlengths, bounds )
> local size, degs, addinterval, badForPosa, badForChvatal1, pos,
> half, i, low1, upp2, upp1, low2, badForChvatal, interval1,
> interval2;
> 
> size:= Sum( classlengths );
> degs:= List( [ 2 .. Length( classlengths ) ],
> i -> [ Sum( bounds[ i-1 ] ), classlengths[i], i ] );
> Sort( degs );
> 
> addinterval:= function( intervals, low, upp )
> if low <= upp then
> Add( intervals, [ low, upp ] );
> fi;
> end;
> 
> badForPosa:= [];
> badForChvatal1:= [];
> pos:= 1;
> half:= Int( size / 2 ) - 1;
> for i in [ 1 .. Length( degs ) ] do
> # We have pos = c_1 + c_2 + \cdots + c_{i-1} + 1
> low1:= Maximum( pos, degs[i][1] ); # L_i
> upp2:= Minimum( half, size-1-pos, size-1-degs[i][1] ); # U'_i
> pos:= pos + degs[i][2];
> upp1:= Minimum( half, pos-1 ); # U_i
> low2:= Maximum( 1, size-pos ); # L'_i
> addinterval( badForPosa, low1, upp1 );
> addinterval( badForChvatal1, low2, upp2 );
> od;
> 
> # Intersect intervals.
> badForChvatal:= [];
> for interval1 in badForPosa do
> for interval2 in badForChvatal1 do
> addinterval( badForChvatal,
> Maximum( interval1[1], interval2[1] ),
> Minimum( interval1[2], interval2[2] ) );
> od;
> od;
> 
> return rec( badForPosa:= badForPosa,
> badForChvatal:= Set( badForChvatal ),
> data:= degs );
> end;;
</pre></div>

Finally, the function <code class="code">HamiltonianCycleInfo</code> assumes that the matrix <code class="code">bounds</code> contains lower bounds for the vertex degrees in the generating graph Γ, and returns a string that describes the minimal i with the property that the given bounds suffice to show that cl^(i)(Γ) satisfies Pósa's or Chvátal's criterion, if such a closure exists. If no closure has this property, the string <code class="code">"no decision"</code> is returned.

<div class="example"><pre>
gap> HamiltonianCycleInfo:= function( classlengths, bounds )
> local i, result, res, oldbounds;
> 
> i:= 0;
> result:= rec( Posa:= fail, Chvatal:= fail );
> repeat
> res:= CheckCriteriaOfPosaAndChvatal( classlengths, bounds );
> if result.Posa = fail and IsEmpty( res.badForPosa ) then
> result.Posa:= i;
> fi;
> if result.Chvatal = fail and IsEmpty( res.badForChvatal ) then
> result.Chvatal:= i;
> fi;
> i:= i+1;
> oldbounds:= bounds;
> bounds:= LowerBoundsVertexDegreesOfClosure( classlengths,
> bounds );
> until oldbounds = bounds;
> 
> if result.Posa <> fail then
> if result.Posa <> result.Chvatal then
> return Concatenation(
> "Chvatal for ", Ordinal( result.Chvatal ), " closure, ",
> "Posa for ", Ordinal( result.Posa ), " closure" );
> else
> return Concatenation( "Posa for ", Ordinal( result.Posa ),
> " closure" );
> fi;
> elif result.Chvatal <> fail then
> return Concatenation( "Chvatal for ", Ordinal( result.Chvatal ),
> " closure" );
> else
> return "no decision";
> fi;
> end;;
</pre></div>

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

<h4>4.4 Character-Theoretic Computations</h4>

In this section, we apply the functions introduced in Section <a href="chap4.html#X7B56BE5384BAD54E">4.3</a> to character tables of almost simple groups that are available in the GAP Character Table Library.

Our first examples are the sporadic simple groups, in Section <a href="chap4.html#X86CE51E180A3D4ED">4.4-1</a>, then their automorphism groups are considered in Section <a href="chap4.html#X7DC6DFCC83502CC3">4.4-3</a>. Small alternating and symmetric groups are treated in Section <a href="chap4.html#X8130C9CB7A33140F">4.4-4</a>.

For our convenience, we provide a small function that takes as its argument only the character table in question, and returns a string, either <code class="code">"no prim. perm. characters"</code> or the return value of <code class="code">HamiltonianCycleInfo</code> for the bounds computed from the primitive permutation characters.

<div class="example"><pre>
gap> HamiltonianCycleInfoFromCharacterTable:= function( tbl )
> local prim, classlengths, bounds;
> 
> prim:= PrimitivePermutationCharacters( tbl );
> if prim = fail then
> return "no prim. perm. characters";
> fi;
> classlengths:= SizesConjugacyClasses( tbl );
> bounds:= LowerBoundsVertexDegrees( classlengths, prim );
> return HamiltonianCycleInfo( classlengths, bounds );
> end;;
</pre></div>

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

<h5>4.4-1 Sporadic Simple Groups</h5>

Since version 1.3.10 of CTblLib, the GAP Character Table Library contains the tables of maximal subgroups of all sporadic simple groups.

So the function <code class="code">PrimitivePermutationCharacters</code> can be used to compute all their primitive permutation characters.

<div class="example"><pre>
gap> spornames:= AllCharacterTableNames( IsSporadicSimple, true,
> IsDuplicateTable, false );
[ "B", "Co1", "Co2", "Co3", "F3+", "Fi22", "Fi23", "HN", "HS", "He",
 "J1", "J2", "J3", "J4", "Ly", "M", "M11", "M12", "M22", "M23",
 "M24", "McL", "ON", "Ru", "Suz", "Th" ]
gap> for tbl in List( spornames, CharacterTable ) do
> info:= HamiltonianCycleInfoFromCharacterTable( tbl );
> if info <> "Posa for 0th closure" then
> Print( Identifier( tbl ), ": ", info, "\n" );
> fi;
> od;
</pre></div>

It turns out that the information available in the GAP Character Table Library is sufficient to prove that the generating graph contains a Hamiltonian cycle.

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

<h5>4.4-2 The Monster</h5>

In the original version of this file, a special treatment of the Monster group had been necessary because not all character tabes of its maximal subgroups were available, and also not all class fusions from some maximal subgroups were known whose character tables were available. This section shows the computations that were used at that time.

Meanwhile the maximal subgroups of the Monster are classified, see <a href="chapBib.html#biBDLP25">[DLP25]</a>, their character tables are available, and also all class fusions from the maximal subgroups are known. Thus we can easily compute the primitive permutation characters of the Monster group. The computations shown in this section are not needed to prove the claims from <a href="chapBib.html#biBGMN">[BGL+10]</a>, they are kept just for historical reasons. Thus this section is an example how the availability of the full list of primitive permutation characters of the Monster simplifies proofs.

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

--> maximum size reached

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

quality100%

¤ Dauer der Verarbeitung: 0.39 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.