Quellcodebibliothek Statistik Leitseite products/Sources/formale Sprachen/GAP/pkg/recog/doc/   (Algebra von RWTH Aachen Version 4.15.1©)  Datei vom 22.0.2025 mit Größe 64 kB image not shown  

Quelle  chap6_mj.html   Sprache: HTML

 
 products/Sources/formale Sprachen/GAP/pkg/recog/doc/chap6_mj.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>
<script type="text/javascript"
  src="https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<title>GAP (recog) - Chapter 6: Methods for recognition</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="chap6"  onload="jscontent()">


<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0_mj.html">Top</a>  <a href="chap1_mj.html">1</a>  <a href="chap2_mj.html">2</a>  <a href="chap3_mj.html">3</a>  <a href="chap4_mj.html">4</a>  <a href="chap5_mj.html">5</a>  <a href="chap6_mj.html">6</a>  <a href="chap7_mj.html">7</a>  <a href="chap8_mj.html">8</a>  <a href="chap9_mj.html">9</a>  <a href="chapBib_mj.html">Bib</a>  <a href="chapInd_mj.html">Ind</a>  </div>

<div class="chlinkprevnexttop"> <a href="chap0_mj.html">[Top of Book]</a>   <a href="chap0_mj.html#contents">[Contents]</a>    <a href="chap5_mj.html">[Previous Chapter]</a>    <a href="chap7_mj.html">[Next Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap6.html">[MathJax off]</a></p>
<p><a id="X78C5295B86AD0C66" name="X78C5295B86AD0C66"></a></p>
<div class="ChapSects"><a href="chap6_mj.html#X78C5295B86AD0C66">6 <span class="Heading">Methods for recognition</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6_mj.html#X79A20FD17F834C70">6.1 <span class="Heading">Methods for generic groups</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X78797CF584658CEC">6.1-1 <span class="Heading"><code class="code">FewGensAbelian</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X7E5E93027A194885">6.1-2 <span class="Heading"><code class="code">KnownNilpotent</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X878C1CED8191506C">6.1-3 <span class="Heading"><code class="code">SnAnUnknownDegree</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X8489BECB78664847">6.1-4 <span class="Heading"><code class="code">TrivialGroup</code></span></a>
</span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6_mj.html#X829A2F96860513F2">6.2 <span class="Heading">Methods for permutation groups</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X80320AF97EF01284">6.2-1 <span class="Heading"><code class="code">BalTreeForBlocks</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X7F46D8727850585D">6.2-2 <span class="Heading"><code class="code">Giant</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X8757E1C37F03A49D">6.2-3 <span class="Heading"><code class="code">Imprimitive</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X836212B6818B60FE">6.2-4 <span class="Heading"><code class="code">LargeBasePrimitive</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X804A913E84B77F97">6.2-5 <span class="Heading"><code class="code">MovesOnlySmallPoints</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X83C651E58239EEAF">6.2-6 <span class="Heading"><code class="code">NonTransitive</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X84C3750C7A4EEC34">6.2-7 <span class="Heading"><code class="code">Pcgs</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X82B9AF9F7A904FE5">6.2-8 <span class="Heading"><code class="code">PcgsForBlocks</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X834E9DFF7DC949DE">6.2-9 <span class="Heading"><code class="code">StabChain</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X7DC0B08B7C73A4F9">6.2-10 <span class="Heading"><code class="code">StabilizerChainPerm</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X8236A4817FA037E2">6.2-11 <span class="Heading"><code class="code">ThrowAwayFixedPoints</code></span></a>
</span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6_mj.html#X829BA50B82FEC109">6.3 <span class="Heading">Methods for matrix groups</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X857BF1317CAAF260">6.3-1 <span class="Heading"><code class="code">BlockDiagonal</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X81F74235823352B5">6.3-2 <span class="Heading"><code class="code">BlockLowerTriangular</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X8795A42285A332BB">6.3-3 <span class="Heading"><code class="code">BlockScalar</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X7A9F8CA181F6412D">6.3-4 <span class="Heading"><code class="code">DiagonalMatrices</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X7A1D99F67E62B1D7">6.3-5 <span class="Heading"><code class="code">GoProjective</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X7B2C182B7898BC45">6.3-6 <span class="Heading"><code class="code">KnownStabilizerChain</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X84E09FCF8527D74A">6.3-7 <span class="Heading"><code class="code">LowerLeftPGroup</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X8007B3DC787D192C">6.3-8 <span class="Heading"><code class="code">NaturalSL</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X811FC944788D9839">6.3-9 <span class="Heading"><code class="code">ReducibleIso</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X8635737086D48AE5">6.3-10 <span class="Heading"><code class="code">Scalar</code></span></a>
</span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6_mj.html#X867550F684F795AE">6.4 <span class="Heading">Methods for projective groups</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X87A53FB6813E2E3C">6.4-1 <span class="Heading"><code class="code">AltSymBBByDegree</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X7F58277E780EEA2E">6.4-2 <span class="Heading"><code class="code">BiggerScalarsOnly</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X863E0A1D7D7FEE04">6.4-3 <span class="Heading"><code class="code">BlockScalarProj</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X84FE699F85371643">6.4-4 <span class="Heading"><code class="code">Blocks</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X84865B2E87FB00CE">6.4-5 <span class="Heading"><code class="code">BlocksBackToMats</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X8605DA5E85DFACDC">6.4-6 <span class="Heading"><code class="code">BlocksModScalars</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X799F4A7A8239D70F">6.4-7 <span class="Heading"><code class="code">C3C5</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X7E484B8F83849B49">6.4-8 <span class="Heading"><code class="code">C6</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X7CE5D3D5876DE816">6.4-9 <span class="Heading"><code class="code">ClassicalNatural</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X7EC8D0FD7DC6B213">6.4-10 <span class="Heading"><code class="code">ComputeSimpleSocle</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X81E155F98671824A">6.4-11 <span class="Heading"><code class="code">D247</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X878ADA8A7CCE93E0">6.4-12 <span class="Heading"><code class="code">DoBaseChangeForBlocks</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X7ED3241F84A98292">6.4-13 <span class="Heading"><code class="code">FindElmOfEvenNormal</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X7845D88F845EC143">6.4-14 <span class="Heading"><code class="code">KroneckerKernel</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X8634C79E7DB22934">6.4-15 <span class="Heading"><code class="code">KroneckerProduct</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X865D3A1B7B6BB49B">6.4-16 <span class="Heading"><code class="code">LieTypeNonConstr</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X810B7F36818D626B">6.4-17 <span class="Heading"><code class="code">LowIndex</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X82B704EF80AE2FBB">6.4-18 <span class="Heading"><code class="code">NameSporadic</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X83E6AD6583DB7080">6.4-19 <span class="Heading"><code class="code">NotAbsolutelyIrred</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X850864887D7F193E">6.4-20 <span class="Heading"><code class="code">ProjDeterminant</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X83288F2279C27632">6.4-21 <span class="Heading"><code class="code">PrototypeForC2C4</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X7B2111968598599F">6.4-22 <span class="Heading"><code class="code">SporadicsByOrders</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X7A46A44F867CFB21">6.4-23 <span class="Heading"><code class="code">StabilizerChainProj</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X7FE1FA217A08DCE5">6.4-24 <span class="Heading"><code class="code">Subfield</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X7DE8D77D7D1E19E3">6.4-25 <span class="Heading"><code class="code">TensorDecomposable</code></span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X7A82C26E78FEF78F">6.4-26 <span class="Heading"><code class="code">ThreeLargeElOrders</code></span></a>
</span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6_mj.html#X7D4A5A9A8266A292">6.5 <span class="Heading">Unused methods</span></a>
</span>
</div>
</div>

<h3>6 <span class="Heading">Methods for recognition</span></h3>

<p><a id="X79A20FD17F834C70" name="X79A20FD17F834C70"></a></p>

<h4>6.1 <span class="Heading">Methods for generic groups</span></h4>

<p>The following methods can be equally applied to permutation, matrix and projective groups. We do not refer to them as black-box groups here, as they are allowed to contain code that only works for inputs of the listed types.</p>

<p><a id="X78797CF584658CEC" name="X78797CF584658CEC"></a></p>

<h5>6.1-1 <span class="Heading"><code class="code">FewGensAbelian</code></span></h5>

<p>This method is used for recognizing permutation groups.</p>

<p>If there are not too may generators (right now that means at most 200), check whether they commute; if yes, dispatch to <a href="chap6_mj.html#X7E5E93027A194885"><span class="RefLink"><span class="Heading"><code class="code">KnownNilpotent</code></span></span></a>, otherwise return <code class="keyw">NeverApplicable</code>.</p>

<p><a id="X7E5E93027A194885" name="X7E5E93027A194885"></a></p>

<h5>6.1-2 <span class="Heading"><code class="code">KnownNilpotent</code></span></h5>

<p>This method is unused!</p>

<p>Hint to this method if you know G to be nilpotent or call it directly if you find out so. Note that it will return NeverApplicable if G is a p-group for some prime p. Make sure that the !.projective component is set correctly such that we can set the right Order method.</p>

<p><a id="X878C1CED8191506C" name="X878C1CED8191506C"></a></p>

<h5>6.1-3 <span class="Heading"><code class="code">SnAnUnknownDegree</code></span></h5>

<p>This method is unused!</p>

<p>This method tries to determine whether the input group given by <var class="Arg">ri</var> is isomorphic to a symmetric group Sn or alternating group An with <span class="SimpleMath">\(11 \leq n\)</span>. It is an implementation of <a href="chapBib_mj.html#biBJLNP13">[JLNP13]</a>.</p>

<p>If <var class="Arg">Grp(ri)</var> is a permutation group, we assume that it is primitive and not a giant (a giant is Sn or An in natural action).</p>

<p><a id="X8489BECB78664847" name="X8489BECB78664847"></a></p>

<h5>6.1-4 <span class="Heading"><code class="code">TrivialGroup</code></span></h5>

<p>This method is used for recognizing permutation, matrix, and projective groups.</p>

<p>This method is successful if and only if all generators of a group <var class="Arg">G</var> are equal to the identity. Otherwise, it returns <code class="keyw">NeverApplicable</code> indicating that it will never succeed. This method is only installed to handle the trivial case such that we do not have to take this case into account in the other methods.</p>

<p><a id="X829A2F96860513F2" name="X829A2F96860513F2"></a></p>

<h4>6.2 <span class="Heading">Methods for permutation groups</span></h4>

<p>The following table gives an overview over the installed methods and their rank (higher rank means higher priority, the method is tried earlier, see Chapter <a href="chap4_mj.html#X8058CC8187162644"><span class="RefLink">4</span></a>).</p>

<div class="pcenter"><table class="GAPDocTable">
<caption class="GAPDocTable"><b>Table: </b>Permutation group find homomorphism methods</caption>
<tr>
<td class="tdleft">1250</td>
<td class="tdleft"><code class="code">FewGensAbelian</code></td>
<td class="tdleft">if very few generators, check IsAbelian and if yes, do KnownNilpotent</td>
<td class="tdleft"><a href="chap6_mj.html#X78797CF584658CEC"><span class="RefLink">6.1-1</span></a></td>
</tr>
<tr>
<td class="tdleft">1050</td>
<td class="tdleft"><code class="code">FewGensAbelian</code></td>
<td class="tdleft">if very few generators, check IsAbelian and if yes, do KnownNilpotent</td>
<td class="tdleft"><a href="chap6_mj.html#X78797CF584658CEC"><span class="RefLink">6.1-1</span></a></td>
</tr>
<tr>
<td class="tdleft">300</td>
<td class="tdleft"><code class="code">TrivialGroup</code></td>
<td class="tdleft">go through generators and compare to the identity</td>
<td class="tdleft"><a href="chap6_mj.html#X8489BECB78664847"><span class="RefLink">6.1-4</span></a></td>
</tr>
<tr>
<td class="tdleft">100</td>
<td class="tdleft"><code class="code">ThrowAwayFixedPoints</code></td>
<td class="tdleft">try to find a huge amount of (possible internal) fixed points</td>
<td class="tdleft"><a href="chap6_mj.html#X8236A4817FA037E2"><span class="RefLink">6.2-11</span></a></td>
</tr>
<tr>
<td class="tdleft">99</td>
<td class="tdleft"><code class="code">FewGensAbelian</code></td>
<td class="tdleft">if very few generators, check IsAbelian and if yes, do KnownNilpotent</td>
<td class="tdleft"><a href="chap6_mj.html#X78797CF584658CEC"><span class="RefLink">6.1-1</span></a></td>
</tr>
<tr>
<td class="tdleft">97</td>
<td class="tdleft"><code class="code">Pcgs</code></td>
<td class="tdleft">use a Pcgs to calculate a stabilizer chain</td>
<td class="tdleft"><a href="chap6_mj.html#X84C3750C7A4EEC34"><span class="RefLink">6.2-7</span></a></td>
</tr>
<tr>
<td class="tdleft">95</td>
<td class="tdleft"><code class="code">MovesOnlySmallPoints</code></td>
<td class="tdleft">calculate a stabilizer chain if only small points are moved</td>
<td class="tdleft"><a href="chap6_mj.html#X804A913E84B77F97"><span class="RefLink">6.2-5</span></a></td>
</tr>
<tr>
<td class="tdleft">90</td>
<td class="tdleft"><code class="code">NonTransitive</code></td>
<td class="tdleft">try to find non-transitivity and restrict to orbit</td>
<td class="tdleft"><a href="chap6_mj.html#X83C651E58239EEAF"><span class="RefLink">6.2-6</span></a></td>
</tr>
<tr>
<td class="tdleft">80</td>
<td class="tdleft"><code class="code">Giant</code></td>
<td class="tdleft">tries to find Sn and An in their natural actions</td>
<td class="tdleft"><a href="chap6_mj.html#X7F46D8727850585D"><span class="RefLink">6.2-2</span></a></td>
</tr>
<tr>
<td class="tdleft">70</td>
<td class="tdleft"><code class="code">Imprimitive</code></td>
<td class="tdleft">for a imprimitive permutation group, restricts to block system</td>
<td class="tdleft"><a href="chap6_mj.html#X8757E1C37F03A49D"><span class="RefLink">6.2-3</span></a></td>
</tr>
<tr>
<td class="tdleft">60</td>
<td class="tdleft"><code class="code">LargeBasePrimitive</code></td>
<td class="tdleft">recognises large-base primitive permutation groups</td>
<td class="tdleft"><a href="chap6_mj.html#X836212B6818B60FE"><span class="RefLink">6.2-4</span></a></td>
</tr>
<tr>
<td class="tdleft">55</td>
<td class="tdleft"><code class="code">StabilizerChainPerm</code></td>
<td class="tdleft">for a permutation group using a stabilizer chain via the <span class="URL"><a href="https://gap-packages.github.io/genss/">genss package</a></span></td>
<td class="tdleft"><a href="chap6_mj.html#X7DC0B08B7C73A4F9"><span class="RefLink">6.2-10</span></a></td>
</tr>
<tr>
<td class="tdleft">50</td>
<td class="tdleft"><code class="code">StabChain</code></td>
<td class="tdleft">for a permutation group using a stabilizer chain</td>
<td class="tdleft"><a href="chap6_mj.html#X834E9DFF7DC949DE"><span class="RefLink">6.2-9</span></a></td>
</tr>
</table><br />
</div>

<p><a id="X80320AF97EF01284" name="X80320AF97EF01284"></a></p>

<h5>6.2-1 <span class="Heading"><code class="code">BalTreeForBlocks</code></span></h5>

<p>This method is unused!</p>

<p>This method creates a balanced composition tree for the kernel of an imprimitive group. This is guaranteed as the method is just called from <code class="code">FindHomMethodsPerm.</code><a href="chap6_mj.html#X8757E1C37F03A49D"><span class="RefLink"><span class="Heading"><code class="code">Imprimitive</code></span></span></a> and itself. The homomorphism for the split in the composition tree used is induced by the action of <var class="Arg">G</var> on half of its blocks.</p>

<p><a id="X7F46D8727850585D" name="X7F46D8727850585D"></a></p>

<h5>6.2-2 <span class="Heading"><code class="code">Giant</code></span></h5>

<p>This method is used for recognizing permutation groups.</p>

<p>The method tries to determine whether the input group <var class="Arg">G</var> is a giant (that is, <span class="SimpleMath">\(A_n\)</span> or <span class="SimpleMath">\(S_n\)</span> in its natural action on <span class="SimpleMath">\(n\)</span> points). The output is either a data structure <span class="SimpleMath">\(D\)</span> containing nice generators for <var class="Arg">G</var> and a procedure to write an SLP for arbitrary elements of <var class="Arg">G</var> from the nice generators; or <code class="keyw">NeverApplicable</code> if <var class="Arg">G</var> is not transitive; or <code class="keyw">fail</code>, in the case that no evidence was found that <var class="Arg">G</var> is a giant, or evidence was found, but the construction of <span class="SimpleMath">\(D\)</span> was unsuccessful. If the method constructs <span class="SimpleMath">\(D\)</span> then the calling node becomes a leaf.</p>

<p><a id="X8757E1C37F03A49D" name="X8757E1C37F03A49D"></a></p>

<h5>6.2-3 <span class="Heading"><code class="code">Imprimitive</code></span></h5>

<p>This method is used for recognizing permutation groups.</p>

<p>If the input group is not known to be transitive then this method returns <code class="keyw">NotEnoughInformation</code>. If the input group is known to be transitive and primitive then the method returns <code class="keyw">NeverApplicable</code>; otherwise, the method tries to compute a nontrivial block system. If successful then a homomorphism to the action on the blocks is defined; otherwise, the method returns <code class="keyw">NeverApplicable</code>.</p>

<p>If the method is successful then it also gives a hint for the children of the node by determining whether the kernel of the action on the block system is solvable. If the answer is yes then the default value 20 for the number of random generators in the kernel construction is increased by the number of blocks.</p>

<p><a id="X836212B6818B60FE" name="X836212B6818B60FE"></a></p>

<h5>6.2-4 <span class="Heading"><code class="code">LargeBasePrimitive</code></span></h5>

<p>This method is used for recognizing permutation groups.</p>

<p>This method tries to determine whether the input group <var class="Arg">G</var> is a fixed-point-free large-base primitive group that neither is a symmetric nor an alternating group in its natural action. This method is an implementation of <a href="chapBib_mj.html#biBLNPS06">[LNPS06]</a>.</p>

<p>A primitive group <span class="SimpleMath">\(H\)</span> acting on <span class="SimpleMath">\(N\)</span> points is called <em>large</em> if there exist <span class="SimpleMath">\(n\)</span>, <span class="SimpleMath">\(k\)</span>, and <span class="SimpleMath">\(r\)</span> with <span class="SimpleMath">\(N = \{n \choose k\}^r\)</span>, and up to a permutational isomorphism <span class="SimpleMath">\(H\)</span> is a subgroup of the product action wreath product <span class="SimpleMath">\(S_n \wr S_r\)</span>, and an overgroup of <span class="SimpleMath">\((A_n) ^ r\)</span> where <span class="SimpleMath">\(S_n\)</span> and <span class="SimpleMath">\(A_n\)</span> act on the <span class="SimpleMath">\(k\)</span>-subsets of <span class="SimpleMath">\(\{1, ..., n\}\)</span>. This algorithm recognises fixed-point-free large primitive groups with <span class="SimpleMath">\(r \cdot k > 1\)</span> and <span class="SimpleMath">\(2 \cdot r \cdot k^2 \le n\)</span>.</p>

<p>A large primitive group <span class="SimpleMath">\(H\)</span> of the above type which does have fixed points is handled as follows: if the group <span class="SimpleMath">\(H\)</span> does not know yet that it is primitive, then <code class="func">ThrowAwayFixedPoints</code> (<a href="chap6_mj.html#X8236A4817FA037E2"><span class="RefLink">6.2-11</span></a>) returns <code class="keyw">NotEnoughInformation</code>. After the first call to <code class="code">LargeBasePrimitive</code>, the group <span class="SimpleMath">\(H\)</span> knows that it is primitive, but since it has fixed points <code class="code">LargeBasePrimitive</code> returns <code class="keyw">NeverApplicable</code>. Since <code class="func">ThrowAwayFixedPoints</code> (<a href="chap6_mj.html#X8236A4817FA037E2"><span class="RefLink">6.2-11</span></a>) previously returned <code class="keyw">NotEnoughInformation</code>, it will be called again. Then it will use the new information about <span class="SimpleMath">\(H\)</span> being primitive, and is guaranteed to prune away the fixed points and set up a reduction homomorphism. <code class="code">LargeBasePrimitive</code> is then applicable to the image of that homomorphism.</p>

<p>If <var class="Arg">G</var> is imprimitive then the output is <code class="keyw">NeverApplicable</code>. If <var class="Arg">G</var> is primitive then the output is either a homomorphism into the natural imprimitive action of <var class="Arg">G</var> on <span class="SimpleMath">\(nr\)</span> points with <span class="SimpleMath">\(r\)</span> blocks of size <span class="SimpleMath">\(n\)</span>, or <code class="keyw">TemporaryFailure</code>, or <code class="keyw">NeverApplicable</code> if no parameters <span class="SimpleMath">\(n\)</span>, <span class="SimpleMath">\(k\)</span>, and <span class="SimpleMath">\(r\)</span> as above exist.</p>

<p><a id="X804A913E84B77F97" name="X804A913E84B77F97"></a></p>

<h5>6.2-5 <span class="Heading"><code class="code">MovesOnlySmallPoints</code></span></h5>

<p>This method is used for recognizing permutation groups.</p>

<p>If a permutation group moves only small points (currently, this means that its largest moved point is at most 10), then this method computes a stabilizer chain for the group via <a href="chap6_mj.html#X834E9DFF7DC949DE"><span class="RefLink"><span class="Heading"><code class="code">StabChain</code></span></span></a>. This is because the most convenient way of solving constructive membership in such a group is via a stabilizer chain. In this case, the calling node becomes a leaf node of the composition tree.</p>

<p>If the input group moves a large point (currently, this means a point larger than 10), then this method returns <code class="keyw">NeverApplicable</code>.</p>

<p><a id="X83C651E58239EEAF" name="X83C651E58239EEAF"></a></p>

<h5>6.2-6 <span class="Heading"><code class="code">NonTransitive</code></span></h5>

<p>This method is used for recognizing permutation groups.</p>

<p>If a permutation group <var class="Arg">G</var> acts nontransitively then this method computes a homomorphism to the action of <var class="Arg">G</var> on the orbit of the largest moved point. If <var class="Arg">G</var> is transitive then the method returns <code class="keyw">NeverApplicable</code>.</p>

<p><a id="X84C3750C7A4EEC34" name="X84C3750C7A4EEC34"></a></p>

<h5>6.2-7 <span class="Heading"><code class="code">Pcgs</code></span></h5>

<p>This method is used for recognizing permutation groups.</p>

<p>This is the <strong class="pkg">GAP</strong> library function to compute a stabiliser chain for a solvable permutation group. If the method is successful then the calling node becomes a leaf node in the recursive scheme. If the input group is not solvable then the method returns <code class="keyw">NeverApplicable</code>.</p>

<p><a id="X82B9AF9F7A904FE5" name="X82B9AF9F7A904FE5"></a></p>

<h5>6.2-8 <span class="Heading"><code class="code">PcgsForBlocks</code></span></h5>

<p>This method is unused!</p>

<p>This method is called after a hint is set in <code class="code">FindHomMethodsPerm.</code><a href="chap6_mj.html#X8757E1C37F03A49D"><span class="RefLink"><span class="Heading"><code class="code">Imprimitive</code></span></span></a>. Therefore, the group <var class="Arg">G</var> preserves a non-trivial block system. This method checks whether or not the restriction of <var class="Arg">G</var> on one block is solvable. If so, then <code class="code">FindHomMethodsPerm.</code><a href="chap6_mj.html#X84C3750C7A4EEC34"><span class="RefLink"><span class="Heading"><code class="code">Pcgs</code></span></span></a> is called, and otherwise <code class="keyw">NeverApplicable</code> is returned.</p>

<p><a id="X834E9DFF7DC949DE" name="X834E9DFF7DC949DE"></a></p>

<h5>6.2-9 <span class="Heading"><code class="code">StabChain</code></span></h5>

<p>This method is used for recognizing permutation groups.</p>

<p>This is the randomized <strong class="pkg">GAP</strong> library function for computing a stabiliser chain. The method selection process ensures that this function is called only with small-base inputs, where the method works efficiently.</p>

<p><a id="X7DC0B08B7C73A4F9" name="X7DC0B08B7C73A4F9"></a></p>

<h5>6.2-10 <span class="Heading"><code class="code">StabilizerChainPerm</code></span></h5>

<p>This method is used for recognizing permutation groups.</p>

<p>TODO</p>

<p><a id="X8236A4817FA037E2" name="X8236A4817FA037E2"></a></p>

<h5>6.2-11 <span class="Heading"><code class="code">ThrowAwayFixedPoints</code></span></h5>

<p>This method is used for recognizing permutation groups.</p>

<p>This method defines a homomorphism of a permutation group <var class="Arg">G</var> to the action on the moved points of <var class="Arg">G</var> if <var class="Arg">G</var> has any fixed points, and is either known to be primitive or the ratio of fixed points to moved points exceeds a certain threshold. If <var class="Arg">G</var> has fixed points but is not primitive, then it returns <code class="keyw">NotEnoughInformation</code> so that it may be called again at a later time. In all other cases, it returns <code class="keyw">NeverApplicable</code>.</p>

<p>In the current setup, the homomorphism is defined if the number <span class="SimpleMath">\(n\)</span> of moved points is at most <span class="SimpleMath">\(1/3\)</span> of the largest moved point of <var class="Arg">G</var>, or <span class="SimpleMath">\(n\)</span> is at most half of the number of points on which <var class="Arg">G</var> is stored internally by <strong class="pkg">GAP</strong>.</p>

<p>The fact that this method returns <code class="keyw">NotEnoughInformation</code> if <var class="Arg">G</var> has fixed points but does not know whether it is primitive, is important for the efficient handling of large-base primitive groups by <code class="func">LargeBasePrimitive</code> (<a href="chap6_mj.html#X836212B6818B60FE"><span class="RefLink">6.2-4</span></a>).</p>

<p><a id="X829BA50B82FEC109" name="X829BA50B82FEC109"></a></p>

<h4>6.3 <span class="Heading">Methods for matrix groups</span></h4>

<p>The following table gives an overview over the installed methods and their rank (higher rank means higher priority, the method is tried earlier, see Chapter <a href="chap4_mj.html#X8058CC8187162644"><span class="RefLink">4</span></a>). Note that there are not that many methods for matrix groups since the system can switch to projective groups by dividing out the subgroup of scalar matrices. The bulk of the recognition methods are then installed es methods for projective groups.</p>

<div class="pcenter"><table class="GAPDocTable">
<caption class="GAPDocTable"><b>Table: </b>Matrix group find homomorphism methods</caption>
<tr>
<td class="tdleft">3100</td>
<td class="tdleft"><code class="code">TrivialGroup</code></td>
<td class="tdleft">go through generators and compare to the identity</td>
<td class="tdleft"><a href="chap6_mj.html#X8489BECB78664847"><span class="RefLink">6.1-4</span></a></td>
</tr>
<tr>
<td class="tdleft">1175</td>
<td class="tdleft"><code class="code">KnownStabilizerChain</code></td>
<td class="tdleft">use an already known stabilizer chain for this group</td>
<td class="tdleft"><a href="chap6_mj.html#X7B2C182B7898BC45"><span class="RefLink">6.3-6</span></a></td>
</tr>
<tr>
<td class="tdleft">1100</td>
<td class="tdleft"><code class="code">DiagonalMatrices</code></td>
<td class="tdleft">check whether all generators are diagonal matrices</td>
<td class="tdleft"><a href="chap6_mj.html#X7A9F8CA181F6412D"><span class="RefLink">6.3-4</span></a></td>
</tr>
<tr>
<td class="tdleft">1000</td>
<td class="tdleft"><code class="code">ReducibleIso</code></td>
<td class="tdleft">use the MeatAxe to find invariant subspaces</td>
<td class="tdleft"><a href="chap6_mj.html#X811FC944788D9839"><span class="RefLink">6.3-9</span></a></td>
</tr>
<tr>
<td class="tdleft">900</td>
<td class="tdleft"><code class="code">GoProjective</code></td>
<td class="tdleft">divide out scalars and recognise projectively</td>
<td class="tdleft"><a href="chap6_mj.html#X7A1D99F67E62B1D7"><span class="RefLink">6.3-5</span></a></td>
</tr>
</table><br />
</div>

<p><a id="X857BF1317CAAF260" name="X857BF1317CAAF260"></a></p>

<h5>6.3-1 <span class="Heading"><code class="code">BlockDiagonal</code></span></h5>

<p>This method is unused!</p>

<p>This method is only called when a hint was passed down from the method <a href="chap6_mj.html#X81F74235823352B5"><span class="RefLink"><span class="Heading"><code class="code">BlockLowerTriangular</code></span></span></a>. In that case, it knows that the group is in block diagonal form. The method is used both in the matrix- and the projective case.</p>

<p>The method immediately delegates to projective methods handling all the diagonal blocks projectively. This is done by giving a hint to the image to use the method <a href="chap6_mj.html#X8605DA5E85DFACDC"><span class="RefLink"><span class="Heading"><code class="code">BlocksModScalars</code></span></span></a>. The method for the kernel then has to deal with only scalar blocks, either projectively or with scalars, which is again done by giving a hint to either use <a href="chap6_mj.html#X8795A42285A332BB"><span class="RefLink"><span class="Heading"><code class="code">BlockScalar</code></span></span></a> or <a href="chap6_mj.html#X863E0A1D7D7FEE04"><span class="RefLink"><span class="Heading"><code class="code">BlockScalarProj</code></span></span></a> respectively.</p>

<p>Note that this method is implemented in a way such that it can also be used as a method for a projective group <var class="Arg">G</var>. In that case the recognition node has the <code class="code">!.projective</code> component bound to <code class="keyw">true</code> and this information is passed down to image and kernel.</p>

<p><a id="X81F74235823352B5" name="X81F74235823352B5"></a></p>

<h5>6.3-2 <span class="Heading"><code class="code">BlockLowerTriangular</code></span></h5>

<p>This method is unused!</p>

<p>This method is only called when a hint was passed down from the method <a href="chap6_mj.html#X811FC944788D9839"><span class="RefLink"><span class="Heading"><code class="code">ReducibleIso</code></span></span></a>. In that case, it knows that a base change to block lower triangular form has been performed. The method can then immediately find a homomorphism by mapping to the diagonal blocks. It sets up this homomorphism and gives hints to image and kernel. For the image, the method <a href="chap6_mj.html#X857BF1317CAAF260"><span class="RefLink"><span class="Heading"><code class="code">BlockDiagonal</code></span></span></a> is used and for the kernel, the method <a href="chap6_mj.html#X84E09FCF8527D74A"><span class="RefLink"><span class="Heading"><code class="code">LowerLeftPGroup</code></span></span></a> is used.</p>

<p>Note that this method is implemented in a way such that it can also be used as a method for a projective group <var class="Arg">G</var>. In that case the recognition node has the <code class="code">!.projective</code> component bound to <code class="keyw">true</code> and this information is passed down to image and kernel.</p>

<p><a id="X8795A42285A332BB" name="X8795A42285A332BB"></a></p>

<h5>6.3-3 <span class="Heading"><code class="code">BlockScalar</code></span></h5>

<p>This method is unused!</p>

<p>This method is only called by a hint. Alongside with the hint it gets a block decomposition respected by the matrix group <var class="Arg">G</var> to be recognised and the promise that all diagonal blocks of all group elements will only be scalar matrices. This method recursively builds a balanced tree and does scalar recognition in each leaf.</p>

<p><a id="X7A9F8CA181F6412D" name="X7A9F8CA181F6412D"></a></p>

<h5>6.3-4 <span class="Heading"><code class="code">DiagonalMatrices</code></span></h5>

<p>This method is used for recognizing matrix groups.</p>

<p>This method is successful if and only if all generators of a matrix group <var class="Arg">G</var> are diagonal matrices. Otherwise, it returns <code class="keyw">NeverApplicable</code>.</p>

<p><a id="X7A1D99F67E62B1D7" name="X7A1D99F67E62B1D7"></a></p>

<h5>6.3-5 <span class="Heading"><code class="code">GoProjective</code></span></h5>

<p>This method is used for recognizing matrix groups.</p>

<p>This method defines a homomorphism from a matrix group <var class="Arg">G</var> into the projective group <var class="Arg">G</var> modulo scalar matrices. In fact, since projective groups in <strong class="pkg">GAP</strong> are represented as matrix groups, the homomorphism is the identity mapping and the only difference is that in the image the projective group methods can be applied. The bulk of the work in matrix recognition is done in the projective group setting.</p>

<p><a id="X7B2C182B7898BC45" name="X7B2C182B7898BC45"></a></p>

<h5>6.3-6 <span class="Heading"><code class="code">KnownStabilizerChain</code></span></h5>

<p>This method is used for recognizing matrix groups.</p>

<p>If a stabilizer chain is already known, then the kernel node is given knowledge about this known stabilizer chain, and the image node is told to use homomorphism methods from the database for permutation groups. If a stabilizer chain of a parent node is already known this is used for the computation of a stabilizer chain of this node. This stabilizer chain is then used in the same way as above.</p>

<p><a id="X84E09FCF8527D74A" name="X84E09FCF8527D74A"></a></p>

<h5>6.3-7 <span class="Heading"><code class="code">LowerLeftPGroup</code></span></h5>

<p>This method is unused!</p>

<p>This method is only called by a hint from <a href="chap6_mj.html#X81F74235823352B5"><span class="RefLink"><span class="Heading"><code class="code">BlockLowerTriangular</code></span></span></a> as the kernel of the homomorphism mapping to the diagonal blocks. The method uses the fact that this kernel is a <span class="SimpleMath">\(p\)</span>-group where <span class="SimpleMath">\(p\)</span> is the characteristic of the underlying field. It exploits this fact and uses this special structure to find nice generators and a method to express group elements in terms of these.</p>

<p><a id="X8007B3DC787D192C" name="X8007B3DC787D192C"></a></p>

<h5>6.3-8 <span class="Heading"><code class="code">NaturalSL</code></span></h5>

<p>This method is unused!</p>

<p>TODO</p>

<p><a id="X811FC944788D9839" name="X811FC944788D9839"></a></p>

<h5>6.3-9 <span class="Heading"><code class="code">ReducibleIso</code></span></h5>

<p>This method is used for recognizing matrix and projective groups.</p>

<p>This method determines whether a matrix group <var class="Arg">G</var> acts irreducibly. If yes, then it returns <code class="keyw">NeverApplicable</code>. If <var class="Arg">G</var> acts reducibly then a composition series of the underlying module is computed and a base change is performed to write <var class="Arg">G</var> in a block lower triangular form. Also, the method passes a hint to the image group that it is in block lower triangular form, so the image immediately can make recursive calls for the actions on the diagonal blocks, and then to the lower <span class="SimpleMath">\(p\)</span>-part. For the image the method <a href="chap6_mj.html#X81F74235823352B5"><span class="RefLink"><span class="Heading"><code class="code">BlockLowerTriangular</code></span></span></a> is used.</p>

<p>Note that this method is implemented in a way such that it can also be used as a method for a projective group <var class="Arg">G</var>. In that case the recognition node has the <code class="code">!.projective</code> component bound to <code class="keyw">true</code> and this information is passed down to image and kernel.</p>

<p><a id="X8635737086D48AE5" name="X8635737086D48AE5"></a></p>

<h5>6.3-10 <span class="Heading"><code class="code">Scalar</code></span></h5>

<p>This method is unused!</p>

<p>TODO</p>

<p><a id="X867550F684F795AE" name="X867550F684F795AE"></a></p>

<h4>6.4 <span class="Heading">Methods for projective groups</span></h4>

<p>The following table gives an overview over the installed methods and their rank (higher rank means higher priority, the method is tried earlier, see Chapter <a href="chap4_mj.html#X8058CC8187162644"><span class="RefLink">4</span></a>). Note that the recognition for matrix group switches to projective recognition rather soon in the recognition process such that most recognition methods in fact are installed as methods for projective groups.</p>

<div class="pcenter"><table class="GAPDocTable">
<caption class="GAPDocTable"><b>Table: </b>Projective group find homomorphism methods</caption>
<tr>
<td class="tdleft">3000</td>
<td class="tdleft"><code class="code">TrivialGroup</code></td>
<td class="tdleft">go through generators and compare to the identity</td>
<td class="tdleft"><a href="chap6_mj.html#X8489BECB78664847"><span class="RefLink">6.1-4</span></a></td>
</tr>
<tr>
<td class="tdleft">1300</td>
<td class="tdleft"><code class="code">ProjDeterminant</code></td>
<td class="tdleft">find homomorphism to non-zero scalars mod d-th powers</td>
<td class="tdleft"><a href="chap6_mj.html#X850864887D7F193E"><span class="RefLink">6.4-20</span></a></td>
</tr>
<tr>
<td class="tdleft">1200</td>
<td class="tdleft"><code class="code">ReducibleIso</code></td>
<td class="tdleft">use the MeatAxe to find invariant subspaces</td>
<td class="tdleft"><a href="chap6_mj.html#X811FC944788D9839"><span class="RefLink">6.3-9</span></a></td>
</tr>
<tr>
<td class="tdleft">1100</td>
<td class="tdleft"><code class="code">NotAbsolutelyIrred</code></td>
<td class="tdleft">write over a bigger field with smaller degree</td>
<td class="tdleft"><a href="chap6_mj.html#X83E6AD6583DB7080"><span class="RefLink">6.4-19</span></a></td>
</tr>
<tr>
<td class="tdleft">1050</td>
<td class="tdleft"><code class="code">ClassicalNatural</code></td>
<td class="tdleft">check whether it is a classical group in its natural representation</td>
<td class="tdleft"><a href="chap6_mj.html#X7CE5D3D5876DE816"><span class="RefLink">6.4-9</span></a></td>
</tr>
<tr>
<td class="tdleft">1000</td>
<td class="tdleft"><code class="code">Subfield</code></td>
<td class="tdleft">write over a smaller field with same degree</td>
<td class="tdleft"><a href="chap6_mj.html#X7FE1FA217A08DCE5"><span class="RefLink">6.4-24</span></a></td>
</tr>
<tr>
<td class="tdleft">900</td>
<td class="tdleft"><code class="code">C3C5</code></td>
<td class="tdleft">compute a normal subgroup of derived and resolve C3 and C5</td>
<td class="tdleft"><a href="chap6_mj.html#X799F4A7A8239D70F"><span class="RefLink">6.4-7</span></a></td>
</tr>
<tr>
<td class="tdleft">850</td>
<td class="tdleft"><code class="code">C6</code></td>
<td class="tdleft">find either an (imprimitive) action or a symplectic one</td>
<td class="tdleft"><a href="chap6_mj.html#X7E484B8F83849B49"><span class="RefLink">6.4-8</span></a></td>
</tr>
<tr>
<td class="tdleft">840</td>
<td class="tdleft"><code class="code">D247</code></td>
<td class="tdleft">play games to find a normal subgroup</td>
<td class="tdleft"><a href="chap6_mj.html#X81E155F98671824A"><span class="RefLink">6.4-11</span></a></td>
</tr>
<tr>
<td class="tdleft">810</td>
<td class="tdleft"><code class="code">AltSymBBByDegree</code></td>
<td class="tdleft">try BB recognition for dim+1 and/or dim+2 if sensible</td>
<td class="tdleft"><a href="chap6_mj.html#X87A53FB6813E2E3C"><span class="RefLink">6.4-1</span></a></td>
</tr>
<tr>
<td class="tdleft">800</td>
<td class="tdleft"><code class="code">TensorDecomposable</code></td>
<td class="tdleft">find a tensor decomposition</td>
<td class="tdleft"><a href="chap6_mj.html#X7DE8D77D7D1E19E3"><span class="RefLink">6.4-25</span></a></td>
</tr>
<tr>
<td class="tdleft">700</td>
<td class="tdleft"><code class="code">FindElmOfEvenNormal</code></td>
<td class="tdleft">find D2, D4 or D7 by finding an element of an even normal subgroup</td>
<td class="tdleft"><a href="chap6_mj.html#X7ED3241F84A98292"><span class="RefLink">6.4-13</span></a></td>
</tr>
<tr>
<td class="tdleft">600</td>
<td class="tdleft"><code class="code">LowIndex</code></td>
<td class="tdleft">find an (imprimitive) action on subspaces</td>
<td class="tdleft"><a href="chap6_mj.html#X810B7F36818D626B"><span class="RefLink">6.4-17</span></a></td>
</tr>
<tr>
<td class="tdleft">580</td>
<td class="tdleft"><code class="code">NameSporadic</code></td>
<td class="tdleft">generate maximal orders</td>
<td class="tdleft"><a href="chap6_mj.html#X82B704EF80AE2FBB"><span class="RefLink">6.4-18</span></a></td>
</tr>
<tr>
<td class="tdleft">550</td>
<td class="tdleft"><code class="code">ComputeSimpleSocle</code></td>
<td class="tdleft">compute simple socle of almost simple group</td>
<td class="tdleft"><a href="chap6_mj.html#X7EC8D0FD7DC6B213"><span class="RefLink">6.4-10</span></a></td>
</tr>
<tr>
<td class="tdleft">500</td>
<td class="tdleft"><code class="code">ThreeLargeElOrders</code></td>
<td class="tdleft">recognise Lie type groups and get its characteristic</td>
<td class="tdleft"><a href="chap6_mj.html#X7A82C26E78FEF78F"><span class="RefLink">6.4-26</span></a></td>
</tr>
<tr>
<td class="tdleft">400</td>
<td class="tdleft"><code class="code">LieTypeNonConstr</code></td>
<td class="tdleft">do non-constructive recognition of Lie type groups</td>
<td class="tdleft"><a href="chap6_mj.html#X865D3A1B7B6BB49B"><span class="RefLink">6.4-16</span></a></td>
</tr>
<tr>
<td class="tdleft">100</td>
<td class="tdleft"><code class="code">StabilizerChainProj</code></td>
<td class="tdleft">last resort: compute a stabilizer chain (projectively)</td>
<td class="tdleft"><a href="chap6_mj.html#X7A46A44F867CFB21"><span class="RefLink">6.4-23</span></a></td>
</tr>
</table><br />
</div>

<p><a id="X87A53FB6813E2E3C" name="X87A53FB6813E2E3C"></a></p>

<h5>6.4-1 <span class="Heading"><code class="code">AltSymBBByDegree</code></span></h5>

<p>This method is used for recognizing projective groups.</p>

<p>This method is a black box constructive (?) recognition of alternating and symmetric groups.</p>

<p>This algorithm is probably based on the paper <a href="chapBib_mj.html#biBBLGN+05">[BLN+05]</a>.</p>

<p><a id="X7F58277E780EEA2E" name="X7F58277E780EEA2E"></a></p>

<h5>6.4-2 <span class="Heading"><code class="code">BiggerScalarsOnly</code></span></h5>

<p>This method is unused!</p>

<p>TODO</p>

<p><a id="X863E0A1D7D7FEE04" name="X863E0A1D7D7FEE04"></a></p>

<h5>6.4-3 <span class="Heading"><code class="code">BlockScalarProj</code></span></h5>

<p>This method is unused!</p>

<p>This method is only called by a hint. Alongside with the hint it gets a block decomposition respected by the matrix group <var class="Arg">G</var> to be recognised and the promise that all diagonal blocks of all group elements will only be scalar matrices. This method simply norms the last diagonal block in all generators by multiplying with a scalar and then delegates to <code class="code">BlockScalar</code> (see <a href="chap6_mj.html#X8795A42285A332BB"><span class="RefLink">6.3-3</span></a>) and matrix group mode to do the recognition.</p>

<p><a id="X84FE699F85371643" name="X84FE699F85371643"></a></p>

<h5>6.4-4 <span class="Heading"><code class="code">Blocks</code></span></h5>

<p>This method is unused!</p>

<p>TODO</p>

<p><a id="X84865B2E87FB00CE" name="X84865B2E87FB00CE"></a></p>

<h5>6.4-5 <span class="Heading"><code class="code">BlocksBackToMats</code></span></h5>

<p>This method is unused!</p>

<p>TODO</p>

<p><a id="X8605DA5E85DFACDC" name="X8605DA5E85DFACDC"></a></p>

<h5>6.4-6 <span class="Heading"><code class="code">BlocksModScalars</code></span></h5>

<p>This method is unused!</p>

<p>This method is only called when hinted from above. In this method it is understood that G should <em>neither</em> be recognised as a matrix group <em>nor</em> as a projective group. Rather, it treats all diagonal blocks modulo scalars which means that two matrices are considered to be equal, if they differ only by a scalar factor in <em>corresponding</em> diagonal blocks, and this scalar can be different for each diagonal block. This means that the kernel of the homomorphism mapping to a node which is recognised using this method will have only scalar matrices in all diagonal blocks.</p>

<p>This method does the balanced tree approach mapping to subsets of the diagonal blocks and finally using projective recognition to recognise single diagonal block groups.</p>

<p><a id="X799F4A7A8239D70F" name="X799F4A7A8239D70F"></a></p>

<h5>6.4-7 <span class="Heading"><code class="code">C3C5</code></span></h5>

<p>This method is used for recognizing projective groups.</p>

<p>TODO</p>

<p><a id="X7E484B8F83849B49" name="X7E484B8F83849B49"></a></p>

<h5>6.4-8 <span class="Heading"><code class="code">C6</code></span></h5>

<p>This method is used for recognizing projective groups.</p>

<p>This method is designed for the handling of the Aschbacher class C6 (normaliser of an extraspecial group). If the input <var class="Arg">G</var><span class="SimpleMath">\(\le PGL(d,q)\)</span> does not satisfy <span class="SimpleMath">\(d=r^n\)</span> and <span class="SimpleMath">\(r|q-1\)</span> for some prime <span class="SimpleMath">\(r\)</span> and integer <span class="SimpleMath">\(n\)</span> then the method returns <code class="keyw">NeverApplicable</code>. Otherwise, it returns either a homomorphism of <var class="Arg">G</var> into <span class="SimpleMath">\(Sp(2n,r)\)</span>, or a homomorphism into the C2 permutation action of <var class="Arg">G</var> on a decomposition of <span class="SimpleMath">\(GF(q)^d\)</span>, or <code class="keyw">fail</code>.</p>

<p><a id="X7CE5D3D5876DE816" name="X7CE5D3D5876DE816"></a></p>

<h5>6.4-9 <span class="Heading"><code class="code">ClassicalNatural</code></span></h5>

<p>This method is used for recognizing projective groups.</p>

<p>TODO</p>

<p><a id="X7EC8D0FD7DC6B213" name="X7EC8D0FD7DC6B213"></a></p>

<h5>6.4-10 <span class="Heading"><code class="code">ComputeSimpleSocle</code></span></h5>

<p>This method is used for recognizing projective groups.</p>

<p>This method randomly computes the non-abelian simple socle and stores it along with additional information if it is called for an almost simple group. Once the non-abelian simple socle is computed the function does not need to be called again for this node and therefore returns <code class="keyw">NeverApplicable</code>.</p>

<p><a id="X81E155F98671824A" name="X81E155F98671824A"></a></p>

<h5>6.4-11 <span class="Heading"><code class="code">D247</code></span></h5>

<p>This method is used for recognizing projective groups.</p>

<p>TODO</p>

<p><a id="X878ADA8A7CCE93E0" name="X878ADA8A7CCE93E0"></a></p>

<h5>6.4-12 <span class="Heading"><code class="code">DoBaseChangeForBlocks</code></span></h5>

<p>This method is unused!</p>

<p>TODO</p>

<p><a id="X7ED3241F84A98292" name="X7ED3241F84A98292"></a></p>

<h5>6.4-13 <span class="Heading"><code class="code">FindElmOfEvenNormal</code></span></h5>

<p>This method is used for recognizing projective groups.</p>

<p>TODO</p>

<p><a id="X7845D88F845EC143" name="X7845D88F845EC143"></a></p>

<h5>6.4-14 <span class="Heading"><code class="code">KroneckerKernel</code></span></h5>

<p>This method is unused!</p>

<p>TODO</p>

<p><a id="X8634C79E7DB22934" name="X8634C79E7DB22934"></a></p>

<h5>6.4-15 <span class="Heading"><code class="code">KroneckerProduct</code></span></h5>

<p>This method is unused!</p>

<p>TODO</p>

<p><a id="X865D3A1B7B6BB49B" name="X865D3A1B7B6BB49B"></a></p>

<h5>6.4-16 <span class="Heading"><code class="code">LieTypeNonConstr</code></span></h5>

<p>This method is used for recognizing projective groups.</p>

<p>Recognise quasi-simple group of Lie type when characteristic is given. Based on <a href="chapBib_mj.html#biBBKPS02">[BKPS02]</a> and <a href="chapBib_mj.html#biBAB01">[AB01]</a>.</p>

<p><a id="X810B7F36818D626B" name="X810B7F36818D626B"></a></p>

<h5>6.4-17 <span class="Heading"><code class="code">LowIndex</code></span></h5>

<p>This method is used for recognizing projective groups.</p>

<p>This method is designed for the handling of the Aschbacher class C2 (stabiliser of a decomposition of the underlying vector space), but may succeed on other types of input as well. Given <var class="Arg">G</var> <span class="SimpleMath">\( \le PGL(d,q)\)</span>, the output is either the permutation action of <var class="Arg">G</var> on a short orbit of subspaces or <code class="keyw">fail</code>. In the current setup, <q>short orbit</q> is defined to have length at most <span class="SimpleMath">\(4d\)</span>.</p>

<p><a id="X82B704EF80AE2FBB" name="X82B704EF80AE2FBB"></a></p>

<h5>6.4-18 <span class="Heading"><code class="code">NameSporadic</code></span></h5>

<p>This method is used for recognizing projective groups.</p>

<p>This method returns a list of sporadic simple groups that the group underlying <var class="Arg">ri</var> could be. It does not recognise extensions of sporadic simple groups nor the Monster and the Baby Monster group. It is based on the Magma v2.24.10 function <code class="code">RecognizeSporadic</code>.</p>

<p><a id="X83E6AD6583DB7080" name="X83E6AD6583DB7080"></a></p>

<h5>6.4-19 <span class="Heading"><code class="code">NotAbsolutelyIrred</code></span></h5>

<p>This method is used for recognizing projective groups.</p>

<p>If an irreducible projective group <var class="Arg">G</var> acts absolutely irreducibly then this method returns <code class="keyw">NeverApplicable</code>. If <var class="Arg">G</var> is not absolutely irreducible then a homomorphism into a smaller dimensional representation over an extension field is defined. A hint is handed down to the image that no test for absolute irreducibility has to be done any more. Another hint is handed down to the kernel indicating that the only possible kernel elements can be elements in the centraliser of <var class="Arg">G</var> in <span class="SimpleMath">\(PGL(d,q)\)</span> that come from scalar matrices in the extension field.</p>

<p><a id="X850864887D7F193E" name="X850864887D7F193E"></a></p>

<h5>6.4-20 <span class="Heading"><code class="code">ProjDeterminant</code></span></h5>

<p>This method is used for recognizing projective groups.</p>

<p>The method defines a homomorphism from a projective group <var class="Arg">G</var><span class="SimpleMath">\( \le PGL(d,q)\)</span> to the cyclic group <span class="SimpleMath">\(GF(q)^*/D\)</span>, where <span class="SimpleMath">\(D\)</span> is the set of <span class="SimpleMath">\(d\)</span>th powers in <span class="SimpleMath">\(GF(q)^*\)</span>. The image of a group element <span class="SimpleMath">\(g \in \textit{G}\)</span> is the determinant of a matrix representative of <span class="SimpleMath">\(g\)</span>, modulo <span class="SimpleMath">\(D\)</span>.</p>

<p><a id="X83288F2279C27632" name="X83288F2279C27632"></a></p>

<h5>6.4-21 <span class="Heading"><code class="code">PrototypeForC2C4</code></span></h5>

<p>This method is unused!</p>

<p>TODO/FIXME: PrototypeForC2C4 is not used anywhere</p>

<p><a id="X7B2111968598599F" name="X7B2111968598599F"></a></p>

<h5>6.4-22 <span class="Heading"><code class="code">SporadicsByOrders</code></span></h5>

<p>This method is unused!</p>

<p>This method returns a list of sporadic simple groups that <var class="Arg">G</var> possibly could be. Therefore it checks whether <var class="Arg">G</var> has elements of orders that do not appear in sporadic groups and otherwise checks whether the most common ("killer") orders of the sporadic groups appear. Afterwards it creates hints that come out of a table for the sporadic simple groups.</p>

<p><a id="X7A46A44F867CFB21" name="X7A46A44F867CFB21"></a></p>

<h5>6.4-23 <span class="Heading"><code class="code">StabilizerChainProj</code></span></h5>

<p>This method is used for recognizing projective groups.</p>

<p>This method computes a stabiliser chain and a base and strong generating set using projective actions. This is a last resort method since for bigger examples no short orbits can be found in the natural action. The strong generators are the nice generator in this case and expressing group elements in terms of the nice generators ist just sifting along the stabiliser chain.</p>

<p><a id="X7FE1FA217A08DCE5" name="X7FE1FA217A08DCE5"></a></p>

<h5>6.4-24 <span class="Heading"><code class="code">Subfield</code></span></h5>

<p>This method is used for recognizing projective groups.</p>

<p>TODO</p>

<p><a id="X7DE8D77D7D1E19E3" name="X7DE8D77D7D1E19E3"></a></p>

<h5>6.4-25 <span class="Heading"><code class="code">TensorDecomposable</code></span></h5>

<p>This method is used for recognizing projective groups.</p>

<p>TODO/FIXME: it is unclear if the following description actually belongs to this method, so be cautious!</p>

<p>This method currently tries to find one tensor factor by powering up commutators of random elements to elements of prime order. This seems to work quite well provided that the two tensor factors are not <q>linked</q> too much such that there exist enough elements that act with different orders on both tensor factors.</p>

<p>This method and its description needs some improvement.</p>

<p><a id="X7A82C26E78FEF78F" name="X7A82C26E78FEF78F"></a></p>

<h5>6.4-26 <span class="Heading"><code class="code">ThreeLargeElOrders</code></span></h5>

<p>This method is used for recognizing projective groups.</p>

<p>In the case when the input group <var class="Arg">G</var><span class="SimpleMath">\( \le PGL(d,p^e)\)</span> is suspected to be simple but not alternating, this method takes the three largest element orders from a sample of pseudorandom elements of <var class="Arg">G</var>. From these element orders, it tries to determine whether <var class="Arg">G</var> is of Lie type and the characteristic of <var class="Arg">G</var> if it is of Lie type. In the case when <var class="Arg">G</var> is of Lie type of characteristic different from <span class="SimpleMath">\(p\)</span>, the method also provides a short list of the possible isomorphism types of <var class="Arg">G</var>.</p>

<p>This method assumes that its input is neither alternating nor sporadic and that <code class="func">ComputeSimpleSocle</code> (<a href="chap6_mj.html#X7EC8D0FD7DC6B213"><span class="RefLink">6.4-10</span></a>) has already been called.</p>

<p>This recognition method is based on the paper <a href="chapBib_mj.html#biBKS09">[KS09]</a>.</p>

<p><a id="X7D4A5A9A8266A292" name="X7D4A5A9A8266A292"></a></p>

<h4>6.5 <span class="Heading">Unused methods</span></h4>

<p>The following table gives an overview over the methods which are currently unused.</p>

<div class="pcenter"><table class="GAPDocTable">
<caption class="GAPDocTable"><b>Table: </b>Unused group find homomorphism methods</caption>
<tr>
<td class="tdleft"><code class="code">KnownNilpotent</code></td>
<td class="tdleft"><code class="code">FindHomMethodsGeneric</code></td>
<td class="tdleft"><a href="chap6_mj.html#X7E5E93027A194885"><span class="RefLink">6.1-2</span></a></td>
</tr>
<tr>
<td class="tdleft"><code class="code">SnAnUnknownDegree</code></td>
<td class="tdleft"><code class="code">FindHomMethodsGeneric</code></td>
<td class="tdleft"><a href="chap6_mj.html#X878C1CED8191506C"><span class="RefLink">6.1-3</span></a></td>
</tr>
<tr>
<td class="tdleft"><code class="code">PcgsForBlocks</code></td>
<td class="tdleft"><code class="code">FindHomMethodsPerm</code></td>
<td class="tdleft"><a href="chap6_mj.html#X82B9AF9F7A904FE5"><span class="RefLink">6.2-8</span></a></td>
</tr>
<tr>
<td class="tdleft"><code class="code">BalTreeForBlocks</code></td>
<td class="tdleft"><code class="code">FindHomMethodsPerm</code></td>
<td class="tdleft"><a href="chap6_mj.html#X80320AF97EF01284"><span class="RefLink">6.2-1</span></a></td>
</tr>
<tr>
<td class="tdleft"><code class="code">BlockScalar</code></td>
<td class="tdleft"><code class="code">FindHomMethodsMatrix</code></td>
<td class="tdleft"><a href="chap6_mj.html#X8795A42285A332BB"><span class="RefLink">6.3-3</span></a></td>
</tr>
<tr>
<td class="tdleft"><code class="code">NaturalSL</code></td>
<td class="tdleft"><code class="code">FindHomMethodsMatrix</code></td>
<td class="tdleft"><a href="chap6_mj.html#X8007B3DC787D192C"><span class="RefLink">6.3-8</span></a></td>
</tr>
<tr>
<td class="tdleft"><code class="code">Scalar</code></td>
<td class="tdleft"><code class="code">FindHomMethodsMatrix</code></td>
<td class="tdleft"><a href="chap6_mj.html#X8635737086D48AE5"><span class="RefLink">6.3-10</span></a></td>
</tr>
<tr>
<td class="tdleft"><code class="code">BlockLowerTriangular</code></td>
<td class="tdleft"><code class="code">FindHomMethodsMatrix</code></td>
<td class="tdleft"><a href="chap6_mj.html#X81F74235823352B5"><span class="RefLink">6.3-2</span></a></td>
</tr>
<tr>
<td class="tdleft"><code class="code">BlockDiagonal</code></td>
<td class="tdleft"><code class="code">FindHomMethodsMatrix</code></td>
<td class="tdleft"><a href="chap6_mj.html#X857BF1317CAAF260"><span class="RefLink">6.3-1</span></a></td>
</tr>
<tr>
<td class="tdleft"><code class="code">LowerLeftPGroup</code></td>
<td class="tdleft"><code class="code">FindHomMethodsMatrix</code></td>
<td class="tdleft"><a href="chap6_mj.html#X84E09FCF8527D74A"><span class="RefLink">6.3-7</span></a></td>
</tr>
<tr>
<td class="tdleft"><code class="code">DoBaseChangeForBlocks</code></td>
<td class="tdleft"><code class="code">FindHomMethodsProjective</code></td>
<td class="tdleft"><a href="chap6_mj.html#X878ADA8A7CCE93E0"><span class="RefLink">6.4-12</span></a></td>
</tr>
<tr>
<td class="tdleft"><code class="code">Blocks</code></td>
<td class="tdleft"><code class="code">FindHomMethodsProjective</code></td>
<td class="tdleft"><a href="chap6_mj.html#X84FE699F85371643"><span class="RefLink">6.4-4</span></a></td>
</tr>
<tr>
<td class="tdleft"><code class="code">BlocksModScalars</code></td>
<td class="tdleft"><code class="code">FindHomMethodsProjective</code></td>
<td class="tdleft"><a href="chap6_mj.html#X8605DA5E85DFACDC"><span class="RefLink">6.4-6</span></a></td>
</tr>
<tr>
<td class="tdleft"><code class="code">BlocksBackToMats</code></td>
<td class="tdleft"><code class="code">FindHomMethodsProjective</code></td>
<td class="tdleft"><a href="chap6_mj.html#X84865B2E87FB00CE"><span class="RefLink">6.4-5</span></a></td>
</tr>
<tr>
<td class="tdleft"><code class="code">KroneckerProduct</code></td>
<td class="tdleft"><code class="code">FindHomMethodsProjective</code></td>
<td class="tdleft"><a href="chap6_mj.html#X8634C79E7DB22934"><span class="RefLink">6.4-15</span></a></td>
</tr>
<tr>
<td class="tdleft"><code class="code">KroneckerKernel</code></td>
<td class="tdleft"><code class="code">FindHomMethodsProjective</code></td>
<td class="tdleft"><a href="chap6_mj.html#X7845D88F845EC143"><span class="RefLink">6.4-14</span></a></td>
</tr>
<tr>
<td class="tdleft"><code class="code">BiggerScalarsOnly</code></td>
<td class="tdleft"><code class="code">FindHomMethodsProjective</code></td>
<td class="tdleft"><a href="chap6_mj.html#X7F58277E780EEA2E"><span class="RefLink">6.4-2</span></a></td>
</tr>
<tr>
<td class="tdleft"><code class="code">PrototypeForC2C4</code></td>
<td class="tdleft"><code class="code">FindHomMethodsProjective</code></td>
<td class="tdleft"><a href="chap6_mj.html#X83288F2279C27632"><span class="RefLink">6.4-21</span></a></td>
</tr>
<tr>
<td class="tdleft"><code class="code">SporadicsByOrders</code></td>
<td class="tdleft"><code class="code">FindHomMethodsProjective</code></td>
<td class="tdleft"><a href="chap6_mj.html#X7B2111968598599F"><span class="RefLink">6.4-22</span></a></td>
</tr>
<tr>
<td class="tdleft"><code class="code">BlockScalarProj</code></td>
<td class="tdleft"><code class="code">FindHomMethodsProjective</code></td>
<td class="tdleft"><a href="chap6_mj.html#X863E0A1D7D7FEE04"><span class="RefLink">6.4-3</span></a></td>
</tr>
</table><br />
</div>


<div class="chlinkprevnextbot"> <a href="chap0_mj.html">[Top of Book]</a>   <a href="chap0_mj.html#contents">[Contents]</a>    <a href="chap5_mj.html">[Previous Chapter]</a>    <a href="chap7_mj.html">[Next Chapter]</a>   </div>


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

--> maximum size reached

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

100%


¤ Diese beiden folgenden Angebotsgruppen bietet das Unternehmen0.12Angebot  Wie Sie bei der Firma Beratungs- und Dienstleistungen beauftragen können  ¤

*Eine klare Vorstellung vom Zielzustand




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.