|
|
|
|
Quelle chap3_mj.html
Sprache: HTML
|
|
| products/sources/formale Sprachen/GAP/pkg/recog/doc/chap3_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 3: Group 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="chap3" 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="chap2_mj.html">[Previous Chapter]</a> <a href="chap4_mj.html">[Next Chapter]</a> </div>
<p id="mathjaxlink" class="pcenter"><a href="chap3.html">[MathJax off]</a></p>
<p><a id="X7F73983582251807" name="X7F73983582251807"></a></p>
<div class="ChapSects"><a href="chap3_mj.html#X7F73983582251807">3 <span class="Heading">Group recognition</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3_mj.html#X81E31E377B16CF39">3.1 <span class="Heading">The recursive procedure</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X7BFEB34483548A89">3.1-1 RecogniseGeneric</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X84338F037B91CDD0">3.1-2 RecognisePermGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X788DCF6A7D9E80BD">3.1-3 RecogniseMatrixGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X841176DD7BA1CAA0">3.1-4 RecogniseProjectiveGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X853B4EE27AF57CD3">3.1-5 RecogniseGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X7AD4A7168016DF8F">3.1-6 TryFindHomMethod</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3_mj.html#X83A18ADB8207154F">3.2 <span class="Heading">Recognition nodes</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X7D2B419B83CD3BF8">3.2-1 RecogNodeFamily</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X801C44668004C0A0">3.2-2 IsRecogNode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X8408B8B286312375">3.2-3 RecogNode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X8469BB658377FD92">3.2-4 IsLeaf</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X7D6CEF0178ED73A7">3.2-5 IsReady</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X7972380780D99B04">3.2-6 Grp</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X8273C2FC79FB6543">3.2-7 Homom</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X864194958685AAD7">3.2-8 NiceGens</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X808A01AA869115EC">3.2-9 pregensfac</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X78DE5A1782456494">3.2-10 ImageRecogNode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X7DE53FAA782440B2">3.2-11 KernelRecogNode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X83BA3AE582319312">3.2-12 ParentRecogNode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X7ACD6B4C7982B1E3">3.2-13 fhmethsel</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X83167779869A3BF5">3.2-14 slpforelement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X83167779869A3BF5">3.2-15 SLPforElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X7FBE4706828964EB">3.2-16 StdPresentation</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X82F234BC853D1323">3.2-17 methodsforimage</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X7FEEE37F858F614B">3.2-18 validatehomominput</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X7FEEE37F858F614B">3.2-19 ValidateHomomInput</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X7EFA298E7E4760A0">3.2-20 calcnicegens</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X78B05A1E78564BBF">3.2-21 CalcNiceGensGeneric</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X80444E4E8501D0B0">3.2-22 CalcNiceGensHomNode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X7EFA298E7E4760A0">3.2-23 CalcNiceGens</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X80C2451F805CA06D">3.2-24 slptonice</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X7B7E9EAC7AACF8D8">3.2-25 gensN</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X81644C3A8064063F">3.2-26 findgensNmeth</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X7DC1D16F807D6895">3.2-27 FindKernelRandom</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X8244F0DE86C23ECA">3.2-28 FindKernelDoNothing</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X87E8AB1B78F60112">3.2-29 FindKernelFastNormalClosure</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X82154EA88011654F">3.2-30 gensNslp</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X86A101E17F87F01F">3.2-31 immediateverification</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X868D75F87B0F33C5">3.2-32 InitialDataForKernelRecogNode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X86F6DB9482B4D8AC">3.2-33 InitialDataForImageRecogNode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X814D78347858EC13">3.2-34 isone</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X7D0F06047B88E5CD">3.2-35 isequal</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X860CF50D80A4215A">3.2-36 OrderFunc</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X7EBE1C5D7C99FA2F">3.2-37 <span class="Heading">Other components of recognition nodes</span></a>
</span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3_mj.html#X8577717D85D631C2">3.3 <span class="Heading">Methods to find homomorphisms</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X7FCBB7C686D0B1DF">3.3-1 FindHomomorphism</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X7F299344834AAB6E">3.3-2 SLPforElementGeneric</a></span>
</div></div>
</div>
<h3>3 <span class="Heading">Group recognition</span></h3>
<p>This chapter describes a generic framework for group recognition. The basic problem is, we want to solve the constructive membership problem: given any <span class="SimpleMath">\(g \in G\)</span>, <span class="SimpleMath">\(G = \langle X \rangle\)</span>, write a straight line program (SLP) from <span class="SimpleMath">\(X\)</span> to <span class="SimpleMath">\(g\)</span>, for <span class="SimpleMath">\(g \notin G\)</span> (in the situation that <span class="SimpleMath">\(G\)</span> is naturally embedded into some bigger group), the algorithm should fail. This is usually done by constructing some nice generators (and then writing an SLP from the nice generators to <span class="SimpleMath">\(g\)</span> and concatenating with an SLP from <span class="SimpleMath">\(X\)</span> to the nice generators). Often, for efficiency reasons, we will just store the nice generators and then only be interested in the SLP from those to <span class="SimpleMath">\(g\)</span>. The framework presented here deals with exactly this process.</p>
<p>The generic framework was designed having three situations in mind: permutation groups, matrix groups and projective groups. Although the methods used are quite different for those cases, there is a common pattern in the procedure of recognition. Namely, first we have to find a homomorphism, solve the constructive membership problem recursively in image and kernel, then put it together. The recursion ends in groups where we can solve the constructive membership problem directly. The general framework reflects this idea and separates it from the rest of the recognition methods.</p>
<p>Solution of the constructive membership problem comes in two stages: first a <q>recognition phase</q> and then a <q>verification phase</q>. The recognition phase usually consists of randomised algorithms with certain error or failure probabilities. The result is some kind of <q>recognition information</q> that will describe the group already very well, but which is not yet proven to be correct. However, one can already write arbitrary elements in the group as product of the given generators. In the verification phase a presentation of the group is calculated, thereby proving that the group generated by the given generators is in fact isomorphic to the group described by the recognition information. In many cases the verification phase will be much more expensive than the recognition phase.</p>
<p>In the following sections, we describe the generic framework. We begin in Section <a href="chap3_mj.html#X81E31E377B16CF39"><span class="RefLink">3.1</span></a> with a technical description of the recursive procedure behind our main function <code class="func">RecogniseGroup</code> (<a href="chap3_mj.html#X853B4EE27AF57CD3"><span class="RefLink">3.1-5</span></a>). In Section <a href="chap3_mj.html#X83A18ADB8207154F"><span class="RefLink">3.2</span></a> we describe the return type of <code class="func">RecogniseGroup</code> (<a href="chap3_mj.html#X853B4EE27AF57CD3"><span class="RefLink">3.1-5</span></a>) which we call <q>recognition nodes</q>. The methods to find homomorphisms are described in Section <a href="chap3_mj.html#X8577717D85D631C2"><span class="RefLink">3.3</span></a>. Finally, we have three sections in which we collect conventions for the recognition of different types of groups.</p>
<p><a id="X81E31E377B16CF39" name="X81E31E377B16CF39"></a></p>
<h4>3.1 <span class="Heading">The recursive procedure</span></h4>
<p>At the heart of the recognition procedure is a function called <code class="func">RecogniseGeneric</code> (<a href="chap3_mj.html#X7BFEB34483548A89"><span class="RefLink">3.1-1</span></a>) which gets a <strong class="pkg">GAP</strong> group object and returns a so-called <q>recognition node</q> (see Subsection <a href="chap3_mj.html#X83A18ADB8207154F"><span class="RefLink">3.2</span></a> for details). Success or failure will be indicated by this record being in the filter <code class="func">IsReady</code> (<a href="chap3_mj.html#X7D6CEF0178ED73A7"><span class="RefLink">3.2-5</span></a>) or not.</p>
<p>To know how to find homomorphisms the function gets as another argument a database of methods (see Section <a href="chap3_mj.html#X8577717D85D631C2"><span class="RefLink">3.3</span></a> for a description of the setup for methods for finding homomorphisms and Section <a href="chap4_mj.html#X7F89FF55818F1139"><span class="RefLink">4.1</span></a> in Chapter <a href="chap4_mj.html#X8058CC8187162644"><span class="RefLink">4</span></a> for details about method databases). This database will be different according to the type of group in question.</p>
<p>To describe the algorithm executed by <code class="func">RecogniseGeneric</code> (<a href="chap3_mj.html#X7BFEB34483548A89"><span class="RefLink">3.1-1</span></a>) we first summarise it in steps:</p>
<ol>
<li><p>Create a new, empty recognition node.</p>
</li>
<li><p>Use the database of <code class="code">FindHomomorphism</code> methods and the method selection procedure described in Chapter <a href="chap4_mj.html#X8058CC8187162644"><span class="RefLink">4</span></a> to try to find a homomorphism onto a smaller group or an isomorphism onto another known group. Terminate with failure if this does not work.</p>
</li>
<li><p>If an isomorphism is found or a method somehow else recognises the group in question, such that we can write elements as straight line programs in the generators from now on, then make the recognition node a leaf of the recognition tree and return success.</p>
</li>
<li><p>Otherwise the function sets up all the data for the homomorphism and calls itself with the image of the homomorphism. Note that this might use another database of recognition methods because the homomorphism might change the representation of the group.</p>
</li>
<li><p>After successful recognition of the image group the procedure has to recognise the kernel of the homomorphism. The first step for this is to find generators. If they are not already known from the <code class="code">FindHomomorphism</code> method, they are created by producing random elements in the group, mapping them through the homomorphism, writing them as a straight line program in the images of the generators and applying this straight line program to the original generators. The quotient of the random element and the result of the straight line program lies in the kernel of the homomorphism. After creating 20 (FIXME: is 20 correct?) random generators of the kernel we assume for the moment that they generate the kernel.</p>
</li>
<li><p>The function <code class="func">RecogniseGeneric</code> (<a href="chap3_mj.html#X7BFEB34483548A89"><span class="RefLink">3.1-1</span></a>) can now call itself for the kernel. After successful recognition of the kernel all the data for the node is completed and success is returned.</p>
</li>
<li><p>The function <code class="func">RecogniseGeneric</code> (<a href="chap3_mj.html#X7BFEB34483548A89"><span class="RefLink">3.1-1</span></a>) now acquires preimages of the nice generators behind the homomorphism and appends the nice generators of the kernel. This list of generators is now the list of nice generators for the current node.</p>
</li>
</ol>
<p>Note that with the collected data one can write arbitrary elements of the group as a straight line program in the generators as follows:</p>
<ol>
<li><p>Map the element through the homomorphism.</p>
</li>
<li><p>Write the element in the image group as a product of the nice generators in the image group.</p>
</li>
<li><p>Apply the resulting straight line program to the preimages of those nice generators and calculate the quotient, which will now lie in the kernel.</p>
</li>
<li><p>Write the kernel element as a straight line program in the kernel generators.</p>
</li>
<li><p>Assemble both straight line programs to one bigger straight line program (which is now in terms of our own nice generators) and return it.</p>
</li>
</ol>
<p>If this procedure fails in the fourth step, this indicates that our random generators for the kernel did not yet generate the full kernel and makes further recognition steps necessary. This will not happen after a successful verification phase.</p>
<p>The latter procedure to write elements as straight line programs in the generators is implemented in the function <code class="func">SLPforElementGeneric</code> (<a href="chap3_mj.html#X7F299344834AAB6E"><span class="RefLink">3.3-2</span></a>) which will be called automatically if one calls the <code class="func">SLPforElement</code> (<a href="chap3_mj.html#X83167779869A3BF5"><span class="RefLink">3.2-15</span></a>) function of the resulting recognition node (see <code class="func">slpforelement</code> (<a href="chap3_mj.html#X83167779869A3BF5"><span class="RefLink">3.2-14</span></a>)).</p>
<p>It is now high time to give you the calling details of the main recursive recognition function:</p>
<p><a id="X7BFEB34483548A89" name="X7BFEB34483548A89"></a></p>
<h5>3.1-1 RecogniseGeneric</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RecogniseGeneric</code>( <var class="Arg">H</var>, <var class="Arg">methoddb</var>, <var class="Arg">depthString</var>, <var class="Arg">knowledge</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RecognizeGeneric</code>( <var class="Arg">H</var>, <var class="Arg">methoddb</var>, <var class="Arg">depthString</var>, <var class="Arg">knowledge</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: <code class="keyw">fail</code> for failure or a recognition node.</p>
<p><var class="Arg">H</var> must be a <strong class="pkg">GAP</strong> group object, <var class="Arg">methoddb</var> must be a method database in the sense of Section <a href="chap4_mj.html#X854385507D03A016"><span class="RefLink">4.2</span></a> containing <code class="code">FindHomomorphism</code> methods in the sense of Section <a href="chap3_mj.html#X8577717D85D631C2"><span class="RefLink">3.3</span></a>. <var class="Arg">depthString</var> is a string whose length measures the depth in the recognition tree. It will be increased by one character for each step we go into the tree, namely by <code class="code">F</code> for a image node, and <code class="code">K</code> for a kernel. The top level begins with an empty string. <var class="Arg">knowledge</var> is an optional record the components of which are copied into the new recognition node which is created for the group <var class="Arg">H</var>. Especially the component <code class="code">hints</code> can contain a list of additional find homomorphism methods (described by records as in Section <a href="chap4_mj.html#X854385507D03A016"><span class="RefLink">4.2</span></a>). The methods in <code class="code">hints</code> and in <var class="Arg">methoddb</var> are merged and sorted into rank-descending order. The result is passed to <code class="func">CallMethods</code> (<a href="chap4_mj.html#X7BC2692183B6C4E6"><span class="RefLink">4.3-1</span></a>). This feature is intended to give hints about prior knowledge about which find homomorphism method might succeed.</p>
<p>The function performs the algorithm described above and returns either <code class="keyw">fail</code> in case of failure or a recognition node in case of success. For the content and definition of recognition nodes see Section <a href="chap3_mj.html#X83A18ADB8207154F"><span class="RefLink">3.2</span></a>.</p>
<p>The user will usually not call this function directly, but will use the following convenience functions:</p>
<p><a id="X84338F037B91CDD0" name="X84338F037B91CDD0"></a></p>
<h5>3.1-2 RecognisePermGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RecognisePermGroup</code>( <var class="Arg">H</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RecognizePermGroup</code>( <var class="Arg">H</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: <code class="keyw">fail</code> for failure or a recognition node.</p>
<p><var class="Arg">H</var> must be a <strong class="pkg">GAP</strong> permutation group object. This function calls <code class="func">RecogniseGeneric</code> (<a href="chap3_mj.html#X7BFEB34483548A89"><span class="RefLink">3.1-1</span></a>) with the method database used for permutation groups, which is stored in the global variable <code class="func">FindHomDbPerm</code> (<a href="chap4_mj.html#X836B50947A46B1A5"><span class="RefLink">4.2-2</span></a>), and no prior knowledge.</p>
<p><a id="X788DCF6A7D9E80BD" name="X788DCF6A7D9E80BD"></a></p>
<h5>3.1-3 RecogniseMatrixGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RecogniseMatrixGroup</code>( <var class="Arg">H</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RecognizeMatrixGroup</code>( <var class="Arg">H</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: <code class="keyw">fail</code> for failure or a recognition node.</p>
<p><var class="Arg">H</var> must be a <strong class="pkg">GAP</strong> matrix group object over a finite field. This function calls <code class="func">RecogniseGeneric</code> (<a href="chap3_mj.html#X7BFEB34483548A89"><span class="RefLink">3.1-1</span></a>) with the method database used for matrix groups, which is stored in the global variable <code class="func">FindHomDbMatrix</code> (<a href="chap4_mj.html#X7CA5F5FA7E850885"><span class="RefLink">4.2-3</span></a>), and no prior knowledge.</p>
<p><a id="X841176DD7BA1CAA0" name="X841176DD7BA1CAA0"></a></p>
<h5>3.1-4 RecogniseProjectiveGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RecogniseProjectiveGroup</code>( <var class="Arg">H</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RecognizeProjectiveGroup</code>( <var class="Arg">H</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: <code class="keyw">fail</code> for failure or a recognition node.</p>
<p><var class="Arg">H</var> must be a <strong class="pkg">GAP</strong> matrix group object over a finite field. Since as of now no actual projective groups are implemented in the <strong class="pkg">GAP</strong> library we use matrix groups instead. The recognition will however view the group as the projective group, i.e. the matrix group modulo its scalar matrices. This function calls <code class="func">RecogniseGeneric</code> (<a href="chap3_mj.html#X7BFEB34483548A89"><span class="RefLink">3.1-1</span></a>) with the method database used for projective groups, which is stored in the global variable <code class="func">FindHomDbProjective</code> (<a href="chap4_mj.html#X7A4F8342854507E3"><span class="RefLink">4.2-4</span></a>), and no prior knowledge.</p>
<p><a id="X853B4EE27AF57CD3" name="X853B4EE27AF57CD3"></a></p>
<h5>3.1-5 RecogniseGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RecogniseGroup</code>( <var class="Arg">H</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RecognizeGroup</code>( <var class="Arg">H</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: <code class="keyw">fail</code> for failure or a recognition node.</p>
<p><var class="Arg">H</var> must be a <strong class="pkg">GAP</strong> group object. This function automatically dispatches to one of the two previous functions <code class="func">RecognisePermGroup</code> (<a href="chap3_mj.html#X84338F037B91CDD0"><span class="RefLink">3.1-2</span></a>), or <code class="func">RecogniseMatrixGroup</code> (<a href="chap3_mj.html#X788DCF6A7D9E80BD"><span class="RefLink">3.1-3</span></a>), according to the type of the group <var class="Arg">H</var>. Note that since currently there is no implementation of projective groups in the <strong class="pkg">GAP</strong> library, one cannot recognise a matrix group <var class="Arg">H</var> as a projective group using this function.</p>
<p><a id="X7AD4A7168016DF8F" name="X7AD4A7168016DF8F"></a></p>
<h5>3.1-6 TryFindHomMethod</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ TryFindHomMethod</code>( <var class="Arg">H</var>, <var class="Arg">method</var>, <var class="Arg">projective</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: <code class="keyw">fail</code> or <code class="keyw">false</code> or a recognition node.</p>
<p>Use this function to try to run a given find homomorphism method <var class="Arg">method</var> on a group <var class="Arg">H</var>. Indicate by the boolean <var class="Arg">projective</var> whether or not the method works in projective mode. For permutation groups, set this to <code class="keyw">false</code>. The result is either <code class="keyw">fail</code> or <code class="keyw">false</code> if the method fails or a recognition node <code class="code">ri</code>. If the method created a leaf then <code class="code">ri</code> will be a leaf, otherwise it will have the attribute <code class="func">Homom</code> (<a href="chap3_mj.html#X8273C2FC79FB6543"><span class="RefLink">3.2-7</span></a>) set, but no image or kernel have been created or recognised yet. You can use for example the methods in <code class="func">FindHomMethodsPerm</code> (<a href="chap4_mj.html#X7A94720080D344DA"><span class="RefLink">4.4-1</span></a>) or <code class="func">FindHomMethodsMatrix</code> (<a href="chap4_mj.html#X79B60CEF8292F142"><span class="RefLink">4.4-2</span></a>) or <code class="func">FindHomMethodsProjective</code> (<a href="chap4_mj.html#X7D796A2179E9026A"><span class="RefLink">4.4-3</span></a>) as the <var class="Arg">method</var> argument.</p>
<p>GAP homomorphisms are not required to give a sensible answer when given a value not in their source, and in practice often enter the break loop, or return an incorrect answer. This causes problems when checking if a value is not in the represented group. To avoid this problem, <code class="func">validatehomominput</code> (<a href="chap3_mj.html#X7FEEE37F858F614B"><span class="RefLink">3.2-18</span></a>) can be set to a function. This function is used to filter possible group elements, before they are passed to <code class="func">Homom</code> (<a href="chap3_mj.html#X8273C2FC79FB6543"><span class="RefLink">3.2-7</span></a>).</p>
<p><a id="X83A18ADB8207154F" name="X83A18ADB8207154F"></a></p>
<h4>3.2 <span class="Heading">Recognition nodes</span></h4>
<p>A recognition node is a <strong class="pkg">GAP</strong> component object. It is a member of the family</p>
<p><a id="X7D2B419B83CD3BF8" name="X7D2B419B83CD3BF8"></a></p>
<h5>3.2-1 RecogNodeFamily</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RecogNodeFamily</code></td><td class="tdright">( family )</td></tr></table></div>
<p>and is in the category</p>
<p><a id="X801C44668004C0A0" name="X801C44668004C0A0"></a></p>
<h5>3.2-2 IsRecogNode</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsRecogNode</code></td><td class="tdright">( category )</td></tr></table></div>
<p>and is <code class="func">IsAttributeStoringRep</code> (<a href="../../../doc/ref/chap13_mj.html#X7A951C33839AF2C1"><span class="RefLink">Reference: IsAttributeStoringRep</span></a>), such that we can define attributes for it, the values of which are stored once they are known. A recognition node always represents a whole binary tree of such records, see the attributes <code class="func">ImageRecogNode</code> (<a href="chap3_mj.html#X78DE5A1782456494"><span class="RefLink">3.2-10</span></a>) and <code class="func">KernelRecogNode</code> (<a href="chap3_mj.html#X7DE53FAA782440B2"><span class="RefLink">3.2-11</span></a>) below.</p>
<p>Recognition nodes can be created via:</p>
<p><a id="X8408B8B286312375" name="X8408B8B286312375"></a></p>
<h5>3.2-3 RecogNode</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RecogNode</code>( <var class="Arg">H</var>[, <var class="Arg">projective</var>][, <var class="Arg">r</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RecogNode</code>( <var class="Arg">r</var>, <var class="Arg">H</var>, <var class="Arg">projective</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: a recognition node.</p>
<p>Create an <code class="func">IsRecogNode</code> (<a href="chap3_mj.html#X801C44668004C0A0"><span class="RefLink">3.2-2</span></a>) object <code class="code">node</code> representing the group <var class="Arg">H</var>. The optional boolean <var class="Arg">projective</var> defaults to false and specifies, in the case that <var class="Arg">H</var> is a matrix group, whether <var class="Arg">H</var> is to be interpreted as a projective group. The optional record <var class="Arg">r</var> defaults to an empty record and is used to initialize the returned <code class="code">node</code>.</p>
<p>For backwards-compatibility, also the order of arguments <code class="code">r, H, projective</code> is accepted.</p>
<p>The following filters are defined for recognition nodes:</p>
<p><a id="X8469BB658377FD92" name="X8469BB658377FD92"></a></p>
<h5>3.2-4 IsLeaf</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsLeaf</code></td><td class="tdright">( flag )</td></tr></table></div>
<p>This flag indicates, whether or not a recognition node represents a leaf in the recognition tree. If it is not set, one finds at least one of the attributes <code class="func">ImageRecogNode</code> (<a href="chap3_mj.html#X78DE5A1782456494"><span class="RefLink">3.2-10</span></a>) and <code class="func">KernelRecogNode</code> (<a href="chap3_mj.html#X7DE53FAA782440B2"><span class="RefLink">3.2-11</span></a>) set for the corresponding node. This flag is normally reset and has to be set by a find homomorphism method to indicate a leaf.</p>
<p><a id="X7D6CEF0178ED73A7" name="X7D6CEF0178ED73A7"></a></p>
<h5>3.2-5 IsReady</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsReady</code></td><td class="tdright">( flag )</td></tr></table></div>
<p>This flag is set for a <code class="func">IsRecogNode</code> (<a href="chap3_mj.html#X801C44668004C0A0"><span class="RefLink">3.2-2</span></a>) object <code class="code">node</code> by <code class="func">RecogniseGeneric</code> (<a href="chap3_mj.html#X7BFEB34483548A89"><span class="RefLink">3.1-1</span></a>), if recognition of the <em>subtree</em> rooted in <code class="code">node</code> finished successfully. Recognition of a node is considered successful, if two conditions hold. First, the call of <code class="func">CallMethods</code> (<a href="chap4_mj.html#X7BC2692183B6C4E6"><span class="RefLink">4.3-1</span></a>) for this node reports <code class="keyw">Success</code>, that is a method from the respective method database (see Section <a href="chap4_mj.html#X854385507D03A016"><span class="RefLink">4.2</span></a>) was successful. Secondly, the construction of the kernel generators was successful.</p>
<p>Thus, if the <code class="func">IsReady</code> flag is set, this does not necessarily mean, that the result of the recognition procedure was verified and proven to be mathematically correct!</p>
<p>In particular, any computations using the datastructure set up by the recognition procedure, like <code class="func">Size</code> (<a href="chap5_mj.html#X858ADA3B7A684421"><span class="RefLink">5.1-3</span></a>) and membership testing via <code class="func">\in</code> (<a href="chap5_mj.html#X87BDB89B7AAFE8AD"><span class="RefLink">5.1-2</span></a>), will error if <code class="func">IsReady</code> is not set.</p>
<p>The following attributes are defined for recognition nodes:</p>
<p><a id="X7972380780D99B04" name="X7972380780D99B04"></a></p>
<h5>3.2-6 Grp</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Grp</code>( <var class="Arg">ri</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>The value of this attribute is the group that is to be recognised by this recognition node <var class="Arg">ri</var>. This attribute is always present during recognition and after completion. Note that the generators of the group object stored here always have a memory attached to them, such that elements that are generated from them remember, how they were acquired.</p>
<p><a id="X8273C2FC79FB6543" name="X8273C2FC79FB6543"></a></p>
<h5>3.2-7 Homom</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Homom</code>( <var class="Arg">ri</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>The value of this attribute is the homomorphism that was found from the group described by the recognition node <var class="Arg">ri</var> as a <strong class="pkg">GAP</strong> object. It is set by a find homomorphism method that succeeded to find a homomorphism (or isomorphism). It does not have to be set in leaf nodes of the recognition tree.</p>
<p><a id="X864194958685AAD7" name="X864194958685AAD7"></a></p>
<h5>3.2-8 NiceGens</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NiceGens</code>( <var class="Arg">ri</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>The value of this attribute must be set for all nodes and contains the nice generators. The <code class="func">SLPforElement</code> (<a href="chap3_mj.html#X83167779869A3BF5"><span class="RefLink">3.2-15</span></a>) function of the node will write its straight line program in terms of these nice generators. For leaf nodes, the find homomorphism method is responsible to set the value of <code class="func">NiceGens</code>. By default, the original generators of the group at this node are taken. For a homomorphism (or isomorphism), the <code class="func">NiceGens</code> will be the concatenation of preimages of the <code class="func">NiceGens</code> of the image group (see <code class="func">pregensfac</code> (<a href="chap3_mj.html#X808A01AA869115EC"><span class="RefLink">3.2-9</span></a>)) and the <code class="func">NiceGens</code> of the kernel. A find homomorphism method does not have to set <code class="func">NiceGens</code> if it finds a homomorphism. Note however, that such a find homomorphism method has to ensure somehow, that preimages of the <code class="func">NiceGens</code> of the image group can be acquired. See <code class="func">calcnicegens</code> (<a href="chap3_mj.html#X7EFA298E7E4760A0"><span class="RefLink">3.2-20</span></a>), <code class="func">CalcNiceGens</code> (<a href="chap3_mj.html#X7EFA298E7E4760A0"><span class="RefLink">3.2-23</span></a>) and <code class="func">slptonice</code> (<a href="chap3_mj.html#X80C2451F805CA06D"><span class="RefLink">3.2-24</span></a>) for instructions.</p>
<p><a id="X808A01AA869115EC" name="X808A01AA869115EC"></a></p>
<h5>3.2-9 pregensfac</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ pregensfac</code>( <var class="Arg">ri</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>The value of this attribute is only set for homomorphism nodes. In that case it contains preimages of the nice generators in the image group. This attribute is set automatically by the generic recursive recognition function using the mechanism described with the attribute <code class="func">calcnicegens</code> (<a href="chap3_mj.html#X7EFA298E7E4760A0"><span class="RefLink">3.2-20</span></a>) below. A find homomorphism does not have to touch this attribute.</p>
<p><a id="X78DE5A1782456494" name="X78DE5A1782456494"></a></p>
<h5>3.2-10 ImageRecogNode</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ImageRecogNode</code>( <var class="Arg">ri</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>The value of this attribute is the recognition node of the image of the homomorphism that was found from the group described by the recognition node <var class="Arg">ri</var>. It is set by the generic recursive procedure after a find homomorphism method has succeeded to find a homomorphism (or isomorphism). It does not have to be set in leaf nodes of the recognition tree. This attribute value provides the link to the <q>image</q> subtree of the recognition tree.</p>
<p><a id="X7DE53FAA782440B2" name="X7DE53FAA782440B2"></a></p>
<h5>3.2-11 KernelRecogNode</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ KernelRecogNode</code>( <var class="Arg">ri</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>The value of this attribute is the recognition node of the kernel of the homomorphism that was found from the group described by the recognition node <var class="Arg">ri</var>. It is set by the generic recursive procedure after a find homomorphism method has succeeded to find a homomorphism (or isomorphism). It does not have to be set in leaf nodes of the recognition tree or if the homomorphism is known to be an isomorphism. In the latter case the value of the attribute is set to <code class="keyw">fail</code>. This attribute value provides the link to the <q>kernel</q> subtree of the recognition tree.</p>
<p><a id="X83BA3AE582319312" name="X83BA3AE582319312"></a></p>
<h5>3.2-12 ParentRecogNode</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ParentRecogNode</code>( <var class="Arg">ri</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>The value of this attribute is the recognition node of the parent of this node in the recognition tree. The top node does not have this attribute set.</p>
<p><a id="X7ACD6B4C7982B1E3" name="X7ACD6B4C7982B1E3"></a></p>
<h5>3.2-13 fhmethsel</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ fhmethsel</code>( <var class="Arg">ri</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>The value of this attribute is the record returned by the method selection (see Section <a href="chap4_mj.html#X83FCCBCA78F608E1"><span class="RefLink">4.3</span></a>) after it ran to find a homomorphism (or isomorphism). It is there to be able to see which methods were tried until the recognition of the node was completed.</p>
<p><a id="X83167779869A3BF5" name="X83167779869A3BF5"></a></p>
<h5>3.2-14 slpforelement</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ slpforelement</code>( <var class="Arg">ri</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>After the recognition phase is completed for the node <var class="Arg">ri</var>, we are by definition able to write arbitrary elements in the group described by this node as a straight line program (SLP) in terms of the nice generators stored in <code class="func">NiceGens</code> (<a href="chap3_mj.html#X864194958685AAD7"><span class="RefLink">3.2-8</span></a>). This attribute value is a function taking the node <var class="Arg">ri</var> and a group element as its arguments and returning the above mentioned straight line program. For the case that a find homomorphism method succeeds in finding a homomorphism, the generic recursive function sets this attribute to the function <code class="func">SLPforElementGeneric</code> (<a href="chap3_mj.html#X7F299344834AAB6E"><span class="RefLink">3.3-2</span></a>) which does the job for the generic homomorphism situation. In all other cases the successful find homomorphism method has to set this attribute to a function doing the job. The find homomorphism method is free to store additional data in the recognition node or the group object such that the <code class="func">SLPforElement</code> (<a href="chap3_mj.html#X83167779869A3BF5"><span class="RefLink">3.2-15</span></a>) function can work.</p>
<p><a id="X83167779869A3BF5" name="X83167779869A3BF5"></a></p>
<h5>3.2-15 SLPforElement</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SLPforElement</code>( <var class="Arg">ri</var>, <var class="Arg">x</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a straight line program expressing <var class="Arg">x</var> in the nice generators.</p>
<p>This is a wrapper function which extracts the value of the attribute <code class="func">slpforelement</code> (<a href="chap3_mj.html#X83167779869A3BF5"><span class="RefLink">3.2-14</span></a>) and calls that function with the arguments <var class="Arg">ri</var> and <var class="Arg">x</var>.</p>
<p><a id="X7FBE4706828964EB" name="X7FBE4706828964EB"></a></p>
<h5>3.2-16 StdPresentation</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StdPresentation</code>( <var class="Arg">ri</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>After the verification phase, the presentation is stored here. Details have still to be decided upon.</p>
<p><a id="X82F234BC853D1323" name="X82F234BC853D1323"></a></p>
<h5>3.2-17 methodsforimage</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ methodsforimage</code>( <var class="Arg">ri</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>This attribute is initialised at the beginning of the recursive recognition function with the database of find homomorphism methods that was used to recognise the group corresponding to the recognition node <var class="Arg">ri</var>. If the found homomorphism changes the representation of the group (going for example from a matrix group to a permutation group), the find homomorphism method can report this by exchanging the database of find homomorphism methods to be used in the recognition of the image of the homomorphism by setting the value of this attribute to something different. It lies in the responsibility of the find homomorphism method to do so, if the representation changes through the homomorphism.</p>
<p><a id="X7FEEE37F858F614B" name="X7FEEE37F858F614B"></a></p>
<h5>3.2-18 validatehomominput</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ validatehomominput</code>( <var class="Arg">ri</var>, <var class="Arg">x</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>The value of this attribute, if there is any, must be a function with two arguments: a recognition record <var class="Arg">ri</var>, and an element <var class="Arg">x</var>. The function must return a boolean. If it returns <code class="keyw">false</code>, then this means that <var class="Arg">x</var> is not in the source of the homomorphism returned by <code class="func">Homom</code> (<a href="chap3_mj.html#X8273C2FC79FB6543"><span class="RefLink">3.2-7</span></a>). If <code class="keyw">true</code> is returned, then either <var class="Arg">x</var> is in the source of that homomorphism, or passing <var class="Arg">x</var> to the homomorphism returns <code class="keyw">fail</code>.</p>
<p>For example, if <var class="Arg">ri</var> represents a matrix group that preserves a subspace, then the source of <code class="func">Homom</code> (<a href="chap3_mj.html#X8273C2FC79FB6543"><span class="RefLink">3.2-7</span></a>) will be matrices which preserve that subspace, and passing matrices which do not preserve this subspace to <code class="func">Homom</code> (<a href="chap3_mj.html#X8273C2FC79FB6543"><span class="RefLink">3.2-7</span></a>) may produce incorrect answers. <code class="func">validatehomominput</code> can be used to filter out such elements. The function <code class="func">ValidateHomomInput</code> (<a href="chap3_mj.html#X7FEEE37F858F614B"><span class="RefLink">3.2-19</span></a>) provides a simple wrapper to this attribute, which calls <code class="func">validatehomominput</code> unless it is not defined, in which case <code class="func">ValidateHomomInput</code> (<a href="chap3_mj.html#X7FEEE37F858F614B"><span class="RefLink">3.2-19</span></a>) returns <code class="keyw">true</code>.</p>
<p><a id="X7FEEE37F858F614B" name="X7FEEE37F858F614B"></a></p>
<h5>3.2-19 ValidateHomomInput</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ValidateHomomInput</code>( <var class="Arg">ri</var>, <var class="Arg">x</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a boolean.</p>
<p>This is a wrapper function which calls <code class="func">validatehomominput</code> (<a href="chap3_mj.html#X7FEEE37F858F614B"><span class="RefLink">3.2-18</span></a>) of <var class="Arg">ri</var> with <var class="Arg">x</var>, or returns <code class="keyw">true</code> if <var class="Arg">ri</var> does not define <code class="func">validatehomominput</code> (<a href="chap3_mj.html#X7FEEE37F858F614B"><span class="RefLink">3.2-18</span></a>).</p>
<p>The following two attributes are concerned with the relation between the original generators and the nice generators for a node. They are used to transport this information from a successful find homomorphism method up to the recursive recognition function:</p>
<p><a id="X7EFA298E7E4760A0" name="X7EFA298E7E4760A0"></a></p>
<h5>3.2-20 calcnicegens</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ calcnicegens</code>( <var class="Arg">ri</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>To make the recursion work, we have to acquire preimages of the nice generators in image groups under the homomorphism found. But we want to keep the information, how the nice generators were found, locally at the node where they were found. This attribute solves this problem of acquiring preimages in the following way: Its value must be a function, taking the recognition node <var class="Arg">ri</var> as first argument, and a list <var class="Arg">origgens</var> of preimages of the original generators of the current node, and has to return corresponding preimages of the nice generators. Usually this task can be done by storing a straight line program writing the nice generators in terms of the original generators and executing this with inputs <var class="Arg">origgens</var>. Therefore the default value of this attribute is the function <code class="func">CalcNiceGensGeneric</code> (<a href="chap3_mj.html#X78B05A1E78564BBF"><span class="RefLink">3.2-21</span></a>) described below.</p>
<p><a id="X78B05A1E78564BBF" name="X78B05A1E78564BBF"></a></p>
<h5>3.2-21 CalcNiceGensGeneric</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CalcNiceGensGeneric</code>( <var class="Arg">ri</var>, <var class="Arg">origgens</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a list of preimages of the nice generators</p>
<p>This is the default function for leaf nodes for the attribute <code class="func">calcnicegens</code> (<a href="chap3_mj.html#X7EFA298E7E4760A0"><span class="RefLink">3.2-20</span></a>) described above. It does the following: If the value of the attribute < | | |
