Quelle chapA_mj.html Sprache: HTML

products/Sources/formale Sprachen/GAP/pkg/anupq/doc/chapA_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 (ANUPQ) - Appendix A: Examples</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chapA" onload="jscontent()">

<div class="chlinktop">Goto Chapter: <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="chapA_mj.html">A</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="chap7_mj.html">[Previous Chapter]</a> <a href="chapBib_mj.html">[Next Chapter]</a> </div>

<a href="chapA.html">[MathJax off]</a>
<a id="X7A489A5D79DA9E5C" name="X7A489A5D79DA9E5C"></a>
<div class="ChapSects"><a href="chapA_mj.html#X7A489A5D79DA9E5C">A Examples</a>
<div class="ContSect"> <a href="chapA_mj.html#X80676E317BF4DF13">A.1 The Relators Option</a>

</div>
<div class="ContSect"> <a href="chapA_mj.html#X80B2AA7084C57F5D">A.2 The Identities Option and PqEvaluateIdentities Function</a>

</div>
<div class="ContSect"> <a href="chapA_mj.html#X7A997D1A8532A84B">A.3 A Large Example</a>

</div>
<div class="ContSect"> <a href="chapA_mj.html#X7FB6DA8D7BB90D8C">A.4 Developing descendants trees</a>

<div class="ContSSBlock">
 <a href="chapA_mj.html#X805E6B418193CF2D">A.4-1 PqDescendantsTreeCoclassOne</a>
</div></div>
</div>

<h3>A Examples</h3>

There are a large number of examples provided with the ANUPQ package. These may be executed or displayed via the function <code class="code">PqExample</code> (see <code class="func">PqExample</code> (<a href="chap3_mj.html#X7BB0EB607F337265">3.4-4</a>)). Each example resides in a file of the same name in the directory <code class="code">examples</code>. Most of the examples are translations to GAP of examples provided for the <code class="code">pq</code> standalone by Eamonn O'Brien; the standalone examples are found in directories standalone/examples (\(p\)-quotient and \(p\)-group generation examples) and standalone/isom (standard presentation examples). The first line of each example indicates its origin. All the examples seen in earlier chapters of this manual are also available as examples, in a slightly modified form (the example which one can run in order to see something very close to the text example live is always indicated near -- usually immediately after -- the text example). The format of the (PqExample) examples is such that they can be read by the standard Read function of GAP, but certain features and comments are interpreted by the function PqExample to do somewhat more than Read does. In particular, any function without a -i, -ni or .g suffix has both a non-interactive and interactive form; in these cases, the default form is the non-interactive form, and giving PqStart as second argument generates the interactive form.

Running <code class="code">PqExample</code> without an argument or with a non-existent example <code class="code">Info</code>s the available examples and some hints on usage:

<div class="example"><pre>
gap> PqExample();
#I PqExample Index (Table of Contents)
#I -----------------------------------
#I This table of possible examples is displayed when calling `PqExample'
#I with no arguments, or with the argument: "index" (meant in the sense
#I of ``list''), or with a non-existent example name.
#I
#I Examples that have a name ending in `-ni' are non-interactive only.
#I Examples that have a name ending in `-i' are interactive only.
#I Examples with names ending in `.g' also have only one form. Other
#I examples have both a non-interactive and an interactive form; call
#I `PqExample' with 2nd argument `PqStart' to get the interactive form
#I of the example. The substring `PG' in an example name indicates a
#I p-Group Generation example, `SP' indicates a Standard Presentation
#I example, `Rel' indicates it uses the `Relators' option, and `Id'
#I indicates it uses the `Identities' option.
#I
#I The following ANUPQ examples are available:
#I
#I p-Quotient examples:
#I general:
#I "Pq" "Pq-ni" "PqEpimorphism"
#I "PqPCover" "PqSupplementInnerAutomorphisms"
#I 2-groups:
#I "2gp-Rel" "2gp-Rel-i" "2gp-a-Rel-i"
#I "B2-4" "B2-4-Id" "B2-8-i"
#I "B4-4-i" "B4-4-a-i" "B5-4.g"
#I 3-groups:
#I "3gp-Rel-i" "3gp-a-Rel" "3gp-a-Rel-i"
#I "3gp-a-x-Rel-i" "3gp-maxoccur-Rel-i"
#I 5-groups:
#I "5gp-Rel-i" "5gp-a-Rel-i" "5gp-b-Rel-i"
#I "5gp-c-Rel-i" "5gp-metabelian-Rel-i" "5gp-maxoccur-Rel-i"
#I "F2-5-i" "B2-5-i" "R2-5-i"
#I "R2-5-x-i" "B5-5-Engel3-Id"
#I 7-groups:
#I "7gp-Rel-i"
#I 11-groups:
#I "11gp-i" "11gp-Rel-i" "11gp-a-Rel-i"
#I "11gp-3-Engel-Id" "11gp-3-Engel-Id-i"
#I
#I p-Group Generation examples:
#I general:
#I "PqDescendants-1" "PqDescendants-2" "PqDescendants-3"
#I "PqDescendants-1-i"
#I 2-groups:
#I "2gp-PG-i" "2gp-PG-2-i" "2gp-PG-3-i"
#I "2gp-PG-4-i" "2gp-PG-e4-i"
#I "PqDescendantsTreeCoclassOne-16-i"
#I 3-groups:
#I "3gp-PG-i" "3gp-PG-4-i" "3gp-PG-x-i"
#I "3gp-PG-x-1-i" "PqDescendants-treetraverse-i"
#I "PqDescendantsTreeCoclassOne-9-i"
#I 5-groups:
#I "5gp-PG-i" "Nott-PG-Rel-i" "Nott-APG-Rel-i"
#I "PqDescendantsTreeCoclassOne-25-i"
#I 7,11-groups:
#I "7gp-PG-i" "11gp-PG-i"
#I
#I Standard Presentation examples:
#I general:
#I "StandardPresentation" "StandardPresentation-i"
#I "EpimorphismStandardPresentation"
#I "EpimorphismStandardPresentation-i" "IsIsomorphicPGroup-ni"
#I 2-groups:
#I "2gp-SP-Rel-i" "2gp-SP-1-Rel-i" "2gp-SP-2-Rel-i"
#I "2gp-SP-3-Rel-i" "2gp-SP-4-Rel-i" "2gp-SP-d-Rel-i"
#I "gp-256-SP-Rel-i" "B2-4-SP-i" "G2-SP-Rel-i"
#I 3-groups:
#I "3gp-SP-Rel-i" "3gp-SP-1-Rel-i" "3gp-SP-2-Rel-i"
#I "3gp-SP-3-Rel-i" "3gp-SP-4-Rel-i" "G3-SP-Rel-i"
#I 5-groups:
#I "5gp-SP-Rel-i" "5gp-SP-a-Rel-i" "5gp-SP-b-Rel-i"
#I "5gp-SP-big-Rel-i" "5gp-SP-d-Rel-i" "G5-SP-Rel-i"
#I "G5-SP-a-Rel-i" "Nott-SP-Rel-i"
#I 7-groups:
#I "7gp-SP-Rel-i" "7gp-SP-a-Rel-i" "7gp-SP-b-Rel-i"
#I 11-groups:
#I "11gp-SP-a-i" "11gp-SP-a-Rel-i" "11gp-SP-a-Rel-1-i"
#I "11gp-SP-b-i" "11gp-SP-b-Rel-i" "11gp-SP-c-Rel-i"
#I
#I Notes
#I -----
#I 1. The example (first) argument of `PqExample' is a string; each
#I example above is in double quotes to remind you to include them.
#I 2. Some examples accept options. To find out whether a particular
#I example accepts options, display it first (by including `Display'
#I as last argument) which will also indicate how `PqExample'
#I interprets the options, e.g. `PqExample("11gp-SP-a-i", Display);'.
#I 3. Try `SetInfoLevel(InfoANUPQ, <n>);' for some <n> in [2 .. 4]
#I before calling PqExample, to see what's going on behind the scenes.
#I
</pre></div>

If on your terminal you are unable to scroll back, an alternative to typing <code class="code">PqExample();</code> to see the displayed examples is to use on-line help, i.e. you may type:

<div class="example"><pre>
gap> ?anupq:examples
</pre></div>

which will display this appendix in a GAP session. If you are not fussed about the order in which the examples are organised, <code class="code">AllPqExamples();</code> lists the available examples relatively compactly (see <code class="func">AllPqExamples</code> (<a href="chap3_mj.html#X823C93FC7B87F5BC">3.4-5</a>)).

In the remainder of this appendix we will discuss particular aspects related to the <code class="code">Relators</code> (see <a href="chap6_mj.html#X87EE6DD67C9996A3">6.2</a>) and <code class="code">Identities</code> (see <a href="chap6_mj.html#X87EE6DD67C9996A3">6.2</a>) options, and the construction of the Burnside group \(B(5, 4)\).

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

<h4>A.1 The Relators Option</h4>

The <code class="code">Relators</code> option was included because computations involving words containing commutators that are pre-expanded by GAP before being passed to the <code class="code">pq</code> program may run considerably more slowly, than the same computations being run with GAP pre-expansions avoided. The following examples demonstrate a case where the performance hit due to pre-expansion of commutators by GAP is a factor of order 100 (in order to see timing information from the <code class="code">pq</code> program, we set the <code class="code">InfoANUPQ</code> level to 2).

Firstly, we run the example that allows pre-expansion of commutators (the function <code class="code">PqLeftNormComm</code> is provided by the ANUPQ package; see <code class="func">PqLeftNormComm</code> (<a href="chap3_mj.html#X8771393B7F53F534">3.4-1</a>)). Note that since the two commutators of this example are very long (taking more than an page to print), we have edited the output at this point.

<div class="example"><pre>
gap> SetInfoLevel(InfoANUPQ, 2); #to see timing information
gap> PqExample("11gp-i");
#I #Example: "11gp-i" . . . based on: examples/11gp
#I F, a, b, c, R, procId are local to `PqExample'
gap> F := FreeGroup("a", "b", "c"); a := F.1; b := F.2; c := F.3;
<free group on the generators [ a, b, c ]>
a
b
c
gap> R := [PqLeftNormComm([b, a, a, b, c])^11, 
> PqLeftNormComm([a, b, b, a, b, c])^11, (a * b)^11];;
gap> procId := PqStart(F/R : Prime := 11);
1
gap> PqPcPresentation(procId : ClassBound := 7, 
> OutputLevel := 1);
#I Lower exponent-11 central series for [grp]
#I Group: [grp] to lower exponent-11 central class 1 has order 11^3
#I Group: [grp] to lower exponent-11 central class 2 has order 11^8
#I Group: [grp] to lower exponent-11 central class 3 has order 11^19
#I Group: [grp] to lower exponent-11 central class 4 has order 11^42
#I Group: [grp] to lower exponent-11 central class 5 has order 11^98
#I Group: [grp] to lower exponent-11 central class 6 has order 11^228
#I Group: [grp] to lower exponent-11 central class 7 has order 11^563
#I Computation of presentation took 27.04 seconds
gap> PqSavePcPresentation(procId, ANUPQData.outfile);
#I Variables used in `PqExample' are saved in `ANUPQData.example.vars'.
</pre></div>

Now we do the same calculation using the <code class="code">Relators</code> option. In this way, the commutators are passed directly as strings to the <code class="code">pq</code> program, so that GAP does not <q>see</q> them and pre-expand them.

<div class="example"><pre>
gap> PqExample("11gp-Rel-i");
#I #Example: "11gp-Rel-i" . . . based on: examples/11gp
#I #(equivalent to "11gp-i" example but uses `Relators' option)
#I F, rels, procId are local to `PqExample'
gap> F := FreeGroup("a", "b", "c");
<free group on the generators [ a, b, c ]>
gap> rels := ["[b, a, a, b, c]^11", "[a, b, b, a, b, c]^11", "(a * b)^11"];
[ "[b, a, a, b, c]^11", "[a, b, b, a, b, c]^11", "(a * b)^11" ]
gap> procId := PqStart(F : Prime := 11, Relators := rels);
2
gap> PqPcPresentation(procId : ClassBound := 7, 
> OutputLevel := 1);
#I Relators parsed ok.
#I Lower exponent-11 central series for [grp]
#I Group: [grp] to lower exponent-11 central class 1 has order 11^3
#I Group: [grp] to lower exponent-11 central class 2 has order 11^8
#I Group: [grp] to lower exponent-11 central class 3 has order 11^19
#I Group: [grp] to lower exponent-11 central class 4 has order 11^42
#I Group: [grp] to lower exponent-11 central class 5 has order 11^98
#I Group: [grp] to lower exponent-11 central class 6 has order 11^228
#I Group: [grp] to lower exponent-11 central class 7 has order 11^563
#I Computation of presentation took 0.27 seconds
gap> PqSavePcPresentation(procId, ANUPQData.outfile);
#I Variables used in `PqExample' are saved in `ANUPQData.example.vars'.
</pre></div>

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

<h4>A.2 The Identities Option and PqEvaluateIdentities Function</h4>

Please pay heed to the warnings given for the <code class="code">Identities</code> option (see <a href="chap6_mj.html#X87EE6DD67C9996A3">6.2</a>); it is written mainly at the GAP level and is not particularly optimised. The <code class="code">Identities</code> option allows one to compute \(p\)-quotients that satisfy an identity. A trivial example better done using the <code class="code">Exponent</code> option, but which nevertheless demonstrates the usage of the <code class="code">Identities</code> option, is as follows:

<div class="example"><pre>
gap> SetInfoLevel(InfoANUPQ, 1);
gap> PqExample("B2-4-Id");
#I #Example: "B2-4-Id" . . . alternative way to generate B(2, 4)
#I #Generates B(2, 4) by using the `Identities' option
#I #... this is not as efficient as using `Exponent' but
#I #demonstrates the usage of the `Identities' option.
#I F, f, procId are local to `PqExample'
gap> F := FreeGroup("a", "b");
<free group on the generators [ a, b ]>
gap> # All words w in the pc generators of B(2, 4) satisfy f(w) = 1 
gap> f := w -> w^4;
function( w ) ... end
gap> Pq( F : Prime := 2, Identities := [ f ] );
#I Class 1 with 2 generators.
#I Class 2 with 5 generators.
#I Class 3 with 7 generators.
#I Class 4 with 10 generators.
#I Class 5 with 12 generators.
#I Class 5 with 12 generators.
<pc group of size 4096 with 12 generators>
#I Variables used in `PqExample' are saved in `ANUPQData.example.vars'.
gap> time; 
1400
</pre></div>

Note that the <code class="code">time</code> statement gives the time in milliseconds spent by GAP in executing the <code class="code">PqExample("B2-4-Id");</code> command (i.e. everything up to the <code class="code">Info</code>-ing of the variables used), but over 90% of that time is spent in the final <code class="code">Pq</code> statement. The time spent by the <code class="code">pq</code> program, which is negligible anyway (you can check this by running the example while the <code class="code">InfoANUPQ</code> level is set to 2), is not counted by <code class="code">time</code>.

Since the identity used in the above construction of \(B(2, 4)\) is just an exponent law, the <q>right</q> way to compute it is via the <code class="code">Exponent</code> option (see <a href="chap6_mj.html#X87EE6DD67C9996A3">6.2</a>), which is implemented at the C level and is highly optimised. Consequently, the <code class="code">Exponent</code> option is significantly faster, generally by several orders of magnitude:

<div class="example"><pre>
gap> SetInfoLevel(InfoANUPQ, 2); # to see time spent by the `pq' program
gap> PqExample("B2-4");
#I #Example: "B2-4" . . . the ``right'' way to generate B(2, 4)
#I #Generates B(2, 4) by using the `Exponent' option
#I F, procId are local to `PqExample'
gap> F := FreeGroup("a", "b");
<free group on the generators [ a, b ]>
gap> Pq( F : Prime := 2, Exponent := 4 );
#I Computation of presentation took 0.00 seconds
<pc group of size 4096 with 12 generators>
#I Variables used in `PqExample' are saved in `ANUPQData.example.vars'.
gap> time; # time spent by GAP in executing `PqExample("B2-4");'
50
</pre></div>

The following example uses the <code class="code">Identities</code> option to compute a 3-Engel group for the prime 11. As is the case for the example <code class="code">"B2-4-Id"</code>, the example has both a non-interactive and an interactive form; below, we demonstrate the interactive form.

<div class="example"><pre>
gap> SetInfoLevel(InfoANUPQ, 1); # reset InfoANUPQ to default level
gap> PqExample("11gp-3-Engel-Id", PqStart);
#I #Example: "11gp-3-Engel-Id" . . . 3-Engel group for prime 11
#I #Non-trivial example of using the `Identities' option
#I F, a, b, G, f, procId, Q are local to `PqExample'
gap> F := FreeGroup("a", "b"); a := F.1; b := F.2;
<free group on the generators [ a, b ]>
a
b
gap> G := F/[ a^11, b^11 ];
<fp group on the generators [ a, b ]>
gap> # All word pairs u, v in the pc generators of the 11-quotient Q of G 
gap> # must satisfy the Engel identity: [u, v, v, v] = 1.
gap> f := function(u, v) return PqLeftNormComm( [u, v, v, v] ); end;
function( u, v ) ... end
gap> procId := PqStart( G );
3
gap> Q := Pq( procId : Prime := 11, Identities := [ f ] );
#I Class 1 with 2 generators.
#I Class 2 with 3 generators.
#I Class 3 with 5 generators.
#I Class 3 with 5 generators.
<pc group of size 161051 with 5 generators>
gap> # We do a ``sample'' check that pairs of elements of Q do satisfy
gap> # the given identity:
gap> f( Random(Q), Random(Q) );
<identity> of ...
gap> f( Q.1, Q.2 );
<identity> of ...
#I Variables used in `PqExample' are saved in `ANUPQData.example.vars'.
</pre></div>

The (interactive) call to <code class="code">Pq</code> above is essentially equivalent to a call to <code class="code">PqPcPresentation</code> with the same arguments and options followed by a call to <code class="code">PqCurrentGroup</code>. Moreover, the call to <code class="code">PqPcPresentation</code> (as described in <code class="func">PqPcPresentation</code> (<a href="chap5_mj.html#X7BF135DD84A781EB">5.6-1</a>)) is equivalent to a <q>class 1</q> call to <code class="code">PqPcPresentation</code> followed by the requisite number of calls to <code class="code">PqNextClass</code>, and with the <code class="code">Identities</code> option set, both <code class="code">PqPcPresentation</code> and <code class="code">PqNextClass</code> <q>quietly</q> perform the equivalent of a <code class="code">PqEvaluateIdentities</code> call. In the following example we break down the <code class="code">Pq</code> call into its low-level equivalents, and set and unset the <code class="code">Identities</code> option to show where <code class="code">PqEvaluateIdentities</code> fits into this scheme.

<div class="example"><pre>
gap> PqExample("11gp-3-Engel-Id-i");
#I #Example: "11gp-3-Engel-Id-i" . . . 3-Engel grp for prime 11
#I #Variation of "11gp-3-Engel-Id" broken down into its lower-level component
#I #command parts.
#I F, a, b, G, f, procId, Q are local to `PqExample'
gap> F := FreeGroup("a", "b"); a := F.1; b := F.2;
<free group on the generators [ a, b ]>
a
b
gap> G := F/[ a^11, b^11 ];
<fp group on the generators [ a, b ]>
gap> # All word pairs u, v in the pc generators of the 11-quotient Q of G 
gap> # must satisfy the Engel identity: [u, v, v, v] = 1.
gap> f := function(u, v) return PqLeftNormComm( [u, v, v, v] ); end;
function( u, v ) ... end
gap> procId := PqStart( G : Prime := 11 );
4
gap> PqPcPresentation( procId : ClassBound := 1);
gap> PqEvaluateIdentities( procId : Identities := [f] );
#I Class 1 with 2 generators.
gap> for c in [2 .. 4] do
> PqNextClass( procId : Identities := [] ); #reset `Identities' option
> PqEvaluateIdentities( procId : Identities := [f] );
> od;
#I Class 2 with 3 generators.
#I Class 3 with 5 generators.
#I Class 3 with 5 generators.
gap> Q := PqCurrentGroup( procId );
<pc group of size 161051 with 5 generators>
gap> # We do a ``sample'' check that pairs of elements of Q do satisfy
gap> # the given identity:
gap> f( Random(Q), Random(Q) );
<identity> of ...
gap> f( Q.1, Q.2 );
<identity> of ...
#I Variables used in `PqExample' are saved in `ANUPQData.example.vars'.
</pre></div>

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

<h4>A.3 A Large Example</h4>

An example demonstrating how a large computation can be organised with the ANUPQ package is the computation of the Burnside group \(B(5, 4)\), the largest group of exponent 4 generated by 5 elements. It has order \(2^{2728}\) and lower exponent-\(p\) central class 13. The example <code class="code">"B5-4.g"</code> computes \(B(5, 4)\); it is based on a <code class="code">pq</code> standalone input file written by M. F. Newman.

To be able to do examples like this was part of the motivation to provide access to the low-level functions of the standalone program from within GAP.

Please note that the construction uses the knowledge gained by Newman and O'Brien in their initial construction of \(B(5, 4)\), in particular, insight into the commutator structure of the group and the knowledge of the \(p\)-central class and the order of \(B(5, 4)\). Therefore, the construction cannot be used to prove that \(B(5, 4)\) has the order and class mentioned above. It is merely a reconstruction of the group. More information is contained in the header of the file examples/B5-4.g.

<div class="example"><pre>
procId := PqStart( FreeGroup(5) : Exponent := 4, Prime := 2 );
Pq( procId : ClassBound := 2 );
PqSupplyAutomorphisms( procId,
 [
 [ [ 1, 1, 0, 0, 0], # first automorphism
 [ 0, 1, 0, 0, 0],
 [ 0, 0, 1, 0, 0],
 [ 0, 0, 0, 1, 0],
 [ 0, 0, 0, 0, 1] ],

 [ [ 0, 0, 0, 0, 1], # second automorphism
 [ 1, 0, 0, 0, 0],
 [ 0, 1, 0, 0, 0],
 [ 0, 0, 1, 0, 0],
 [ 0, 0, 0, 1, 0] ]
 ] );;

Relations :=
 [ [], ## class 1
 [], ## class 2
 [], ## class 3
 [], ## class 4
 [], ## class 5
 [], ## class 6
 ## class 7
 [ [ "x2","x1","x1","x3","x4","x4","x4" ] ],
 ## class 8
 [ [ "x2","x1","x1","x3","x4","x5","x5","x5" ] ],
 ## class 9
 [ [ "x2","x1","x1","x3","x4","x4","x5","x5","x5" ],
 [ "x2","x1","x1","x2","x3","x4","x5","x5","x5" ],
 [ "x2","x1","x1","x3","x3","x4","x5","x5","x5" ] ],
 ## class 10
 [ [ "x2","x1","x1","x2","x3","x3","x4","x5","x5","x5" ],
 [ "x2","x1","x1","x3","x3","x4","x4","x5","x5","x5" ] ],
 ## class 11
 [ [ "x2","x1","x1","x2","x3","x3","x4","x4","x5","x5","x5" ],
 [ "x2","x1","x1","x2","x3","x1","x3","x4","x2","x4","x3" ] ],
 ## class 12
 [ [ "x2","x1","x1","x2","x3","x1","x3","x4","x2","x5","x5","x5" ],
 [ "x2","x1","x1","x3","x2","x4","x3","x5","x4","x5","x5","x5" ] ],
 ## class 13
 [ [ "x2","x1","x1","x2","x3","x1","x3","x4","x2","x4","x5","x5","x5"
 ] ]
];

for class in [ 3 .. 13 ] do
 Print( "Computing class ", class, "\n" );
 PqSetupTablesForNextClass( procId );

 for w in [ class, class-1 .. 7 ] do

 PqAddTails( procId, w );
 PqDisplayPcPresentation( procId );

 if Relations[ w ] <> [] then
 # recalculate automorphisms
 PqExtendAutomorphisms( procId );

 for r in Relations[ w ] do
 Print( "Collecting ", r, "\n" );
 PqCommutator( procId, r, 1 );
 PqEchelonise( procId );
 PqApplyAutomorphisms( procId, 15 ); #queue factor = 15
 od;

 PqEliminateRedundantGenerators( procId );
 fi;
 PqComputeTails( procId, w );
 od;
 PqDisplayPcPresentation( procId );

 smallclass := Minimum( class, 6 );
 for w in [ smallclass, smallclass-1 .. 2 ] do
 PqTails( procId, w );
 od;
 # recalculate automorphisms
 PqExtendAutomorphisms( procId );
 PqCollect( procId, "x5^4" );
 PqEchelonise( procId );
 PqApplyAutomorphisms( procId, 15 ); #queue factor = 15
 PqEliminateRedundantGenerators( procId );
 PqDisplayPcPresentation( procId );
od;
</pre></div>

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

<h4>A.4 Developing descendants trees</h4>

In the following example we will explore the 3-groups of rank 2 and 3-coclass 1 up to 3-class 5. This will be done using the \(p\)-group generation machinery of the package. We start with the elementary abelian 3-group of rank 2. From within GAP, run the example <code class="code">"PqDescendants-treetraverse-i"</code> via <code class="code">PqExample</code> (see <code class="func">PqExample</code> (<a href="chap3_mj.html#X7BB0EB607F337265">3.4-4</a>)).

<div class="example"><pre>
gap> G := ElementaryAbelianGroup( 9 );
<pc group of size 9 with 2 generators>
gap> procId := PqStart( G );
5
gap> #
gap> # Below, we use the option StepSize in order to construct descendants
gap> # of coclass 1. This is equivalent to setting the StepSize to 1 in
gap> # each descendant calculation.
gap> #
gap> # The elementary abelian group of order 9 has 3 descendants of
gap> # 3-class 2 and 3-coclass 1, as the result of the next command
gap> # shows. 
gap> #
gap> PqDescendants( procId : StepSize := 1 );
[ <pc group of size 27 with 3 generators>,
 <pc group of size 27 with 3 generators>,
 <pc group of size 27 with 3 generators> ]
gap> #
gap> # Now we will compute the descendants of coclass 1 for each of the
gap> # groups above. Then we will compute the descendants of coclass 1
gap> # of each descendant and so on. Note that the pq program keeps
gap> # one file for each class at a time. For example, the descendants
gap> # calculation for the second group of class 2 overwrites the
gap> # descendant file obtained from the first group of class 2.
gap> # Hence, we have to traverse the descendants tree in depth first
gap> # order.
gap> #
gap> PqPGSetDescendantToPcp( procId, 2, 1 );
gap> PqPGExtendAutomorphisms( procId );
gap> PqPGConstructDescendants( procId : StepSize := 1 );
2
gap> PqPGSetDescendantToPcp( procId, 3, 1 );
gap> PqPGExtendAutomorphisms( procId );
gap> PqPGConstructDescendants( procId : StepSize := 1 );
2
gap> PqPGSetDescendantToPcp( procId, 4, 1 );
gap> PqPGExtendAutomorphisms( procId );
gap> PqPGConstructDescendants( procId : StepSize := 1 );
2
gap> #
gap> # At this point we stop traversing the ``left most'' branch of the
gap> # descendants tree and move upwards.
gap> #
gap> PqPGSetDescendantToPcp( procId, 4, 2 );
gap> PqPGExtendAutomorphisms( procId );
gap> PqPGConstructDescendants( procId : StepSize := 1 );
#I group restored from file is incapable
0
gap> PqPGSetDescendantToPcp( procId, 3, 2 );
gap> PqPGExtendAutomorphisms( procId );
gap> PqPGConstructDescendants( procId : StepSize := 1 );
#I group restored from file is incapable
0
gap> # 
gap> # The computations above indicate that the descendants subtree under
gap> # the first descendant of the elementary abelian group of order 9
gap> # will have only one path of infinite length.
gap> #
gap> PqPGSetDescendantToPcp( procId, 2, 2 );
gap> PqPGExtendAutomorphisms( procId );
gap> PqPGConstructDescendants( procId : StepSize := 1 );
4
gap> #
gap> # We get four descendants here, three of which will turn out to be
gap> # incapable, i.e., they have no descendants and are terminal nodes
gap> # in the descendants tree.
gap> #
gap> PqPGSetDescendantToPcp( procId, 2, 3 );
gap> PqPGExtendAutomorphisms( procId );
gap> PqPGConstructDescendants( procId : StepSize := 1 );
#I group restored from file is incapable
0
gap> #
gap> # The third descendant of class three is incapable. Let us return
gap> # to the second descendant of class 2.
gap> #
gap> PqPGSetDescendantToPcp( procId, 2, 2 );
gap> PqPGExtendAutomorphisms( procId );
gap> PqPGConstructDescendants( procId : StepSize := 1 );
4
gap> PqPGSetDescendantToPcp( procId, 3, 1 );
gap> PqPGExtendAutomorphisms( procId );
gap> PqPGConstructDescendants( procId : StepSize := 1 );
#I group restored from file is incapable
0
gap> PqPGSetDescendantToPcp( procId, 3, 2 );
gap> PqPGExtendAutomorphisms( procId );
gap> PqPGConstructDescendants( procId : StepSize := 1 );
#I group restored from file is incapable
0
gap> #
gap> # We skip the third descendant for the moment ... 
gap> #
gap> PqPGSetDescendantToPcp( procId, 3, 4 );
gap> PqPGExtendAutomorphisms( procId );
gap> PqPGConstructDescendants( procId : StepSize := 1 );
#I group restored from file is incapable
0
gap> #
gap> # ... and look at it now.
gap> #
gap> PqPGSetDescendantToPcp( procId, 3, 3 );
gap> PqPGExtendAutomorphisms( procId );
gap> PqPGConstructDescendants( procId : StepSize := 1 );
6
gap> #
gap> # In this branch of the descendant tree we get 6 descendants of class
gap> # three. Of those 5 will turn out to be incapable and one will have
gap> # 7 descendants.
gap> #
gap> PqPGSetDescendantToPcp( procId, 4, 1 );
gap> PqPGExtendAutomorphisms( procId );
gap> PqPGConstructDescendants( procId : StepSize := 1 );
#I group restored from file is incapable
0
gap> PqPGSetDescendantToPcp( procId, 4, 2 );
gap> PqPGExtendAutomorphisms( procId );
gap> PqPGConstructDescendants( procId : StepSize := 1 );
7
gap> PqPGSetDescendantToPcp( procId, 4, 3 );
gap> PqPGExtendAutomorphisms( procId );
gap> PqPGConstructDescendants( procId : StepSize := 1 );
#I group restored from file is incapable
0
</pre></div>

To automate the above procedure to some extent we provide:

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

<h5>A.4-1 PqDescendantsTreeCoclassOne</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PqDescendantsTreeCoclassOne</code>( <var class="Arg">i</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">‣ PqDescendantsTreeCoclassOne</code>( )</td><td class="tdright">( function )</td></tr></table></div>
for the <var class="Arg">i</var>th or default interactive ANUPQ process, generate a descendant tree for the group of the process (which must be a pc \(p\)-group) consisting of descendants of \(p\)-coclass 1 and extending to the class determined by the option <code class="code">TreeDepth</code> (or 6 if the option is omitted). In an XGAP session, a graphical representation of the descendants tree appears in a separate window. Subsequent calls to <code class="code">PqDescendantsTreeCoclassOne</code> for the same process may be used to extend the descendant tree from the last descendant computed that itself has more than one descendant. <code class="code">PqDescendantsTreeCoclassOne</code> also accepts the options <code class="code">CapableDescendants</code> (or <code class="code">AllDescendants</code>) and any options accepted by the interactive <code class="code">PqDescendants</code> function (see <code class="func">PqDescendants</code> (<a href="chap5_mj.html#X795817217C53AB89">5.3-6</a>)).

Notes

<ol>
<li><code class="code">PqDescendantsTreeCoclassOne</code> first calls <code class="code">PqDescendants</code>. If <code class="code">PqDescendants</code> has already been called for the process, the previous value computed is used and a warning is <code class="code">Info</code>-ed at <code class="code">InfoANUPQ</code> level 1.

</li>
<li>As each descendant is processed its unique label defined by the <code class="code">pq</code> program and number of descendants is <code class="code">Info</code>-ed at <code class="code">InfoANUPQ</code> level 1.

</li>
<li><code class="code">PqDescendantsTreeCoclassOne</code> is an <q>experimental</q> function that is included to demonstrate the sort of things that are possible with the \(p\)-group generation machinery.

</li>
</ol>
Ignoring the extra functionality provided in an XGAP session, <code class="code">PqDescendantsTreeCoclassOne</code>, with one argument that is the index of an interactive ANUPQ process, is approximately equivalent to:

<div class="example"><pre>
PqDescendantsTreeCoclassOne := function( procId )
 local des, i;

 des := PqDescendants( procId : StepSize := 1 );
 RecurseDescendants( procId, 2, Length(des) );
end;
</pre></div>

where <code class="code">RecurseDescendants</code> is (approximately) defined as follows:

<div class="example"><pre>
RecurseDescendants := function( procId, class, n )
 local i, nr;

 if class > ValueOption("TreeDepth") then return; fi;

 for i in [1..n] do
 PqPGSetDescendantToPcp( procId, class, i );
 PqPGExtendAutomorphisms( procId );
 nr := PqPGConstructDescendants( procId : StepSize := 1 );
 Print( "Number of descendants of group ", i,
 " at class ", class, ": ", nr, "\n" );
 RecurseDescendants( procId, class+1, nr );
 od;
 return;
end;
</pre></div>

The following examples (executed via <code class="code">PqExample</code>; see <code class="func">PqExample</code> (<a href="chap3_mj.html#X7BB0EB607F337265">3.4-4</a>)), demonstrate the use of <code class="code">PqDescendantsTreeCoclassOne</code>:

<dl>
<dt><code class="code">"PqDescendantsTreeCoclassOne-9-i"</code></dt>
<dd>approximately does example <code class="code">"PqDescendants-treetraverse-i"</code> again using <code class="code">PqDescendantsTreeCoclassOne</code>;

</dd>
<dt><code class="code">"PqDescendantsTreeCoclassOne-16-i"</code></dt>
<dd>uses the option <code class="code">CapableDescendants</code>; and

</dd>
<dt><code class="code">"PqDescendantsTreeCoclassOne-25-i"</code></dt>
<dd>calculates all descendants by omitting the <code class="code">CapableDescendants</code> option.

</dd>
</dl>
The numbers <code class="code">9</code>, <code class="code">16</code> and <code class="code">25</code> respectively, indicate the order of the elementary abelian group to which <code class="code">PqDescendantsTreeCoclassOne</code> is applied for these examples.

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

<div class="chlinkbot">Goto Chapter: <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="chapA_mj.html">A</a> <a href="chapBib_mj.html">Bib</a> <a href="chapInd_mj.html">Ind</a> </div>

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

quality100%

¤ Dauer der Verarbeitung: 0.23 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

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

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.