GAP 4.8.9 installation with standard packages -- copy to your CoCalc project to get it

1
  
2
  A Examples
3
  
4
  There  are a large number of examples provided with the ANUPQ package. These
5
  may  be  executed  or  displayed  via  the function PqExample (see PqExample
6
  (3.4-4)).  Each  example resides in a file of the same name in the directory
7
  examples.  Most of the examples are translations to GAP of examples provided
8
  for  the  pq standalone by Eamonn O'Brien; the standalone examples are found
9
  in   directories  standalone/examples  (p-quotient  and  p-group  generation
10
  examples)  and  standalone/isom  (standard presentation examples). The first
11
  line  of each example indicates its origin. All the examples seen in earlier
12
  chapters  of  this  manual  are  also  available  as examples, in a slightly
13
  modified  form (the example which one can run in order to see something very
14
  close  to  the  text  example  live  is  always  indicated  near  -- usually
15
  immediately  after  --  the  text  example).  The  format of the (PqExample)
16
  examples is such that they can be read by the standard Read function of GAP,
17
  but  certain features and comments are interpreted by the function PqExample
18
  to  do  somewhat  more than Read does. In particular, any function without a
19
  -i,  -ni  or  .g  suffix has both a non-interactive and interactive form; in
20
  these  cases,  the  default  form  is  the  non-interactive form, and giving
21
  PqStart as second argument generates the interactive form.
22
  
23
  Running  PqExample  without an argument or with a non-existent example Infos
24
  the available examples and some hints on usage:
25
  
26
    Example  
27
    gap> PqExample();
28
    #I                   PqExample Index (Table of Contents)
29
    #I                   -----------------------------------
30
    #I  This table of possible examples is displayed when calling `PqExample'
31
    #I  with no arguments, or with the argument: "index" (meant in the  sense
32
    #I  of ``list''), or with a non-existent example name.
33
    #I  
34
    #I  Examples that have a name ending in `-ni' are  non-interactive  only.
35
    #I  Examples that have a  name  ending  in  `-i'  are  interactive  only.
36
    #I  Examples with names ending in `.g' also have  only  one  form.  Other
37
    #I  examples have both a non-interactive and an  interactive  form;  call
38
    #I  `PqExample' with 2nd argument `PqStart' to get the  interactive  form
39
    #I  of the example. The substring `PG' in an  example  name  indicates  a
40
    #I  p-Group Generation example, `SP' indicates  a  Standard  Presentation
41
    #I  example, `Rel' indicates it uses  the  `Relators'  option,  and  `Id'
42
    #I  indicates it uses the `Identities' option.
43
    #I  
44
    #I  The following ANUPQ examples are available:
45
    #I  
46
    #I   p-Quotient examples:
47
    #I    general:
48
    #I     "Pq"                   "Pq-ni"                "PqEpimorphism"        
49
    #I     "PqPCover"             "PqSupplementInnerAutomorphisms"
50
    #I    2-groups:
51
    #I     "2gp-Rel"              "2gp-Rel-i"            "2gp-a-Rel-i"
52
    #I     "B2-4"                 "B2-4-Id"              "B2-8-i"
53
    #I     "B4-4-i"               "B4-4-a-i"             "B5-4.g"
54
    #I    3-groups:
55
    #I     "3gp-Rel-i"            "3gp-a-Rel"            "3gp-a-Rel-i"
56
    #I     "3gp-a-x-Rel-i"        "3gp-maxoccur-Rel-i"
57
    #I    5-groups:
58
    #I     "5gp-Rel-i"            "5gp-a-Rel-i"          "5gp-b-Rel-i"
59
    #I     "5gp-c-Rel-i"          "5gp-metabelian-Rel-i" "5gp-maxoccur-Rel-i"
60
    #I     "F2-5-i"               "B2-5-i"               "R2-5-i"
61
    #I     "R2-5-x-i"             "B5-5-Engel3-Id"
62
    #I    7-groups:
63
    #I     "7gp-Rel-i"
64
    #I    11-groups:
65
    #I     "11gp-i"               "11gp-Rel-i"           "11gp-a-Rel-i"
66
    #I     "11gp-3-Engel-Id"      "11gp-3-Engel-Id-i"
67
    #I  
68
    #I   p-Group Generation examples:
69
    #I    general:
70
    #I     "PqDescendants-1"      "PqDescendants-2"      "PqDescendants-3"
71
    #I     "PqDescendants-1-i"
72
    #I    2-groups:
73
    #I     "2gp-PG-i"             "2gp-PG-2-i"           "2gp-PG-3-i"
74
    #I     "2gp-PG-4-i"           "2gp-PG-e4-i"
75
    #I     "PqDescendantsTreeCoclassOne-16-i"
76
    #I    3-groups:
77
    #I     "3gp-PG-i"             "3gp-PG-4-i"           "3gp-PG-x-i"
78
    #I     "3gp-PG-x-1-i"         "PqDescendants-treetraverse-i"
79
    #I     "PqDescendantsTreeCoclassOne-9-i"
80
    #I    5-groups:
81
    #I     "5gp-PG-i"             "Nott-PG-Rel-i"        "Nott-APG-Rel-i"
82
    #I     "PqDescendantsTreeCoclassOne-25-i"
83
    #I    7,11-groups:
84
    #I     "7gp-PG-i"             "11gp-PG-i"
85
    #I  
86
    #I   Standard Presentation examples:
87
    #I    general:
88
    #I     "StandardPresentation" "StandardPresentation-i"
89
    #I     "EpimorphismStandardPresentation"
90
    #I     "EpimorphismStandardPresentation-i"           "IsIsomorphicPGroup-ni"
91
    #I    2-groups:
92
    #I     "2gp-SP-Rel-i"         "2gp-SP-1-Rel-i"       "2gp-SP-2-Rel-i"
93
    #I     "2gp-SP-3-Rel-i"       "2gp-SP-4-Rel-i"       "2gp-SP-d-Rel-i"
94
    #I     "gp-256-SP-Rel-i"      "B2-4-SP-i"            "G2-SP-Rel-i"
95
    #I    3-groups:
96
    #I     "3gp-SP-Rel-i"         "3gp-SP-1-Rel-i"       "3gp-SP-2-Rel-i"
97
    #I     "3gp-SP-3-Rel-i"       "3gp-SP-4-Rel-i"       "G3-SP-Rel-i"
98
    #I    5-groups:
99
    #I     "5gp-SP-Rel-i"         "5gp-SP-a-Rel-i"       "5gp-SP-b-Rel-i"
100
    #I     "5gp-SP-big-Rel-i"     "5gp-SP-d-Rel-i"       "G5-SP-Rel-i"
101
    #I     "G5-SP-a-Rel-i"        "Nott-SP-Rel-i"
102
    #I    7-groups:
103
    #I     "7gp-SP-Rel-i"         "7gp-SP-a-Rel-i"       "7gp-SP-b-Rel-i"
104
    #I    11-groups:
105
    #I     "11gp-SP-a-i"          "11gp-SP-a-Rel-i"      "11gp-SP-a-Rel-1-i"
106
    #I     "11gp-SP-b-i"          "11gp-SP-b-Rel-i"      "11gp-SP-c-Rel-i"
107
    #I  
108
    #I  Notes
109
    #I  -----
110
    #I  1. The example (first) argument of  `PqExample'  is  a  string;  each
111
    #I     example above is in double quotes to remind you to include them.
112
    #I  2. Some examples accept options. To find  out  whether  a  particular
113
    #I     example accepts options, display it first (by including  `Display'
114
    #I     as  last  argument)  which  will  also  indicate  how  `PqExample'
115
    #I     interprets the options, e.g. `PqExample("11gp-SP-a-i", Display);'.
116
    #I  3. Try `SetInfoLevel(InfoANUPQ, <n>);' for  some  <n>  in  [2  ..  4]
117
    #I     before calling PqExample, to see what's going on behind the scenes.
118
    #I  
119
  
120
  
121
  If  on your terminal you are unable to scroll back, an alternative to typing
122
  PqExample(); to see the displayed examples is to use on-line help, i.e.  you
123
  may type:
124
  
125
    Example  
126
    gap> ?anupq:examples
127
  
128
  
129
  which  will  display  this  appendix in a GAP session. If you are not fussed
130
  about  the order in which the examples are organised, AllPqExamples(); lists
131
  the available examples relatively compactly (see AllPqExamples (3.4-5)).
132
  
133
  In the remainder of this appendix we will discuss particular aspects related
134
  to  the  Relators  (see 6.2)  and  Identities  (see 6.2)  options,  and  the
135
  construction of the Burnside group B(5, 4).
136
  
137
  
138
  A.1 The Relators Option
139
  
140
  The  Relators  option  was  included  because  computations  involving words
141
  containing  commutators  that are pre-expanded by GAP before being passed to
142
  the  pq program may run considerably more slowly, than the same computations
143
  being   run   with   GAP  pre-expansions  avoided.  The  following  examples
144
  demonstrate  a  case  where  the  performance  hit  due  to pre-expansion of
145
  commutators  by  GAP  is  a  factor  of  order  100  (in order to see timing
146
  information from the pq program, we set the InfoANUPQ level to 2).
147
  
148
  Firstly,  we  run  the example that allows pre-expansion of commutators (the
149
  function PqLeftNormComm is provided by the ANUPQ package; see PqLeftNormComm
150
  (3.4-1)).  Note that since the two commutators of this example are very long
151
  (taking  more  than  an  page  to  print), we have edited the output at this
152
  point.
153
  
154
    Example  
155
    gap> SetInfoLevel(InfoANUPQ, 2); #to see timing information
156
    gap> PqExample("11gp-i");
157
    #I  #Example: "11gp-i" . . . based on: examples/11gp
158
    #I  F, a, b, c, R, procId are local to `PqExample'
159
    gap> F := FreeGroup("a", "b", "c"); a := F.1; b := F.2; c := F.3;
160
    <free group on the generators [ a, b, c ]>
161
    a
162
    b
163
    c
164
    gap> R := [PqLeftNormComm([b, a, a, b, c])^11, 
165
    >          PqLeftNormComm([a, b, b, a, b, c])^11, (a * b)^11];;
166
    gap> procId := PqStart(F/R : Prime := 11);
167
    1
168
    gap> PqPcPresentation(procId : ClassBound := 7, 
169
    >                              OutputLevel := 1);
170
    #I  Lower exponent-11 central series for [grp]
171
    #I  Group: [grp] to lower exponent-11 central class 1 has order 11^3
172
    #I  Group: [grp] to lower exponent-11 central class 2 has order 11^8
173
    #I  Group: [grp] to lower exponent-11 central class 3 has order 11^19
174
    #I  Group: [grp] to lower exponent-11 central class 4 has order 11^42
175
    #I  Group: [grp] to lower exponent-11 central class 5 has order 11^98
176
    #I  Group: [grp] to lower exponent-11 central class 6 has order 11^228
177
    #I  Group: [grp] to lower exponent-11 central class 7 has order 11^563
178
    #I  Computation of presentation took 27.04 seconds
179
    gap> PqSavePcPresentation(procId, ANUPQData.outfile);
180
    #I  Variables used in `PqExample' are saved in `ANUPQData.example.vars'.
181
  
182
  
183
  Now  we  do the same calculation using the Relators option. In this way, the
184
  commutators  are  passed  directly as strings to the pq program, so that GAP
185
  does not see them and pre-expand them.
186
  
187
    Example  
188
    gap> PqExample("11gp-Rel-i");
189
    #I  #Example: "11gp-Rel-i" . . . based on: examples/11gp
190
    #I  #(equivalent to "11gp-i" example but uses `Relators' option)
191
    #I  F, rels, procId are local to `PqExample'
192
    gap> F := FreeGroup("a", "b", "c");
193
    <free group on the generators [ a, b, c ]>
194
    gap> rels := ["[b, a, a, b, c]^11", "[a, b, b, a, b, c]^11", "(a * b)^11"];
195
    [ "[b, a, a, b, c]^11", "[a, b, b, a, b, c]^11", "(a * b)^11" ]
196
    gap> procId := PqStart(F : Prime := 11, Relators := rels);
197
    2
198
    gap> PqPcPresentation(procId : ClassBound := 7, 
199
    >                              OutputLevel := 1);
200
    #I  Relators parsed ok.
201
    #I  Lower exponent-11 central series for [grp]
202
    #I  Group: [grp] to lower exponent-11 central class 1 has order 11^3
203
    #I  Group: [grp] to lower exponent-11 central class 2 has order 11^8
204
    #I  Group: [grp] to lower exponent-11 central class 3 has order 11^19
205
    #I  Group: [grp] to lower exponent-11 central class 4 has order 11^42
206
    #I  Group: [grp] to lower exponent-11 central class 5 has order 11^98
207
    #I  Group: [grp] to lower exponent-11 central class 6 has order 11^228
208
    #I  Group: [grp] to lower exponent-11 central class 7 has order 11^563
209
    #I  Computation of presentation took 0.27 seconds
210
    gap> PqSavePcPresentation(procId, ANUPQData.outfile);
211
    #I  Variables used in `PqExample' are saved in `ANUPQData.example.vars'.
212
  
213
  
214
  
215
  A.2 The Identities Option and PqEvaluateIdentities Function
216
  
217
  Please  pay  heed to the warnings given for the Identities option (see 6.2);
218
  it is written mainly at the GAP level and is not particularly optimised. The
219
  Identities  option  allows  one  to  compute  p-quotients  that  satisfy  an
220
  identity. A trivial example better done using the Exponent option, but which
221
  nevertheless demonstrates the usage of the Identities option, is as follows:
222
  
223
    Example  
224
    gap> SetInfoLevel(InfoANUPQ, 1);
225
    gap> PqExample("B2-4-Id");
226
    #I  #Example: "B2-4-Id" . . . alternative way to generate B(2, 4)
227
    #I  #Generates B(2, 4) by using the `Identities' option
228
    #I  #... this is not as efficient as using `Exponent' but
229
    #I  #demonstrates the usage of the `Identities' option.
230
    #I  F, f, procId are local to `PqExample'
231
    gap> F := FreeGroup("a", "b");
232
    <free group on the generators [ a, b ]>
233
    gap> # All words w in the pc generators of B(2, 4) satisfy f(w) = 1 
234
    gap> f := w -> w^4;
235
    function( w ) ... end
236
    gap> Pq( F : Prime := 2, Identities := [ f ] );
237
    #I  Class 1 with 2 generators.
238
    #I  Class 2 with 5 generators.
239
    #I  Class 3 with 7 generators.
240
    #I  Class 4 with 10 generators.
241
    #I  Class 5 with 12 generators.
242
    #I  Class 5 with 12 generators.
243
    <pc group of size 4096 with 12 generators>
244
    #I  Variables used in `PqExample' are saved in `ANUPQData.example.vars'.
245
    gap> time; 
246
    1400
247
  
248
  
249
  Note  that the time statement gives the time in milliseconds spent by GAP in
250
  executing  the  PqExample("B2-4-Id");  command  (i.e. everything  up  to the
251
  Info-ing  of  the variables used), but over 90% of that time is spent in the
252
  final  Pq  statement.  The time spent by the pq program, which is negligible
253
  anyway  (you can check this by running the example while the InfoANUPQ level
254
  is set to 2), is not counted by time.
255
  
256
  Since  the  identity  used  in  the above construction of B(2, 4) is just an
257
  exponent  law,  the  right  way  to  compute  it  is via the Exponent option
258
  (see 6.2),  which  is  implemented  at  the C level and is highly optimised.
259
  Consequently,  the  Exponent  option  is  significantly faster, generally by
260
  several orders of magnitude:
261
  
262
    Example  
263
    gap> SetInfoLevel(InfoANUPQ, 2); # to see time spent by the `pq' program
264
    gap> PqExample("B2-4");
265
    #I  #Example: "B2-4" . . . the ``right'' way to generate B(2, 4)
266
    #I  #Generates B(2, 4) by using the `Exponent' option
267
    #I  F, procId are local to `PqExample'
268
    gap> F := FreeGroup("a", "b");
269
    <free group on the generators [ a, b ]>
270
    gap> Pq( F : Prime := 2, Exponent := 4 );
271
    #I  Computation of presentation took 0.00 seconds
272
    <pc group of size 4096 with 12 generators>
273
    #I  Variables used in `PqExample' are saved in `ANUPQData.example.vars'.
274
    gap> time; # time spent by GAP in executing `PqExample("B2-4");' 
275
    50
276
  
277
  
278
  The  following example uses the Identities option to compute a 3-Engel group
279
  for  the prime 11. As is the case for the example "B2-4-Id", the example has
280
  both  a  non-interactive  and an interactive form; below, we demonstrate the
281
  interactive form.
282
  
283
    Example  
284
    gap> SetInfoLevel(InfoANUPQ, 1); # reset InfoANUPQ to default level
285
    gap> PqExample("11gp-3-Engel-Id", PqStart);
286
    #I  #Example: "11gp-3-Engel-Id" . . . 3-Engel group for prime 11
287
    #I  #Non-trivial example of using the `Identities' option
288
    #I  F, a, b, G, f, procId, Q are local to `PqExample'
289
    gap> F := FreeGroup("a", "b"); a := F.1; b := F.2;
290
    <free group on the generators [ a, b ]>
291
    a
292
    b
293
    gap> G := F/[ a^11, b^11 ];
294
    <fp group on the generators [ a, b ]>
295
    gap> # All word pairs u, v in the pc generators of the 11-quotient Q of G 
296
    gap> # must satisfy the Engel identity: [u, v, v, v] = 1.
297
    gap> f := function(u, v) return PqLeftNormComm( [u, v, v, v] ); end;
298
    function( u, v ) ... end
299
    gap> procId := PqStart( G );
300
    3
301
    gap> Q := Pq( procId : Prime := 11, Identities := [ f ] );
302
    #I  Class 1 with 2 generators.
303
    #I  Class 2 with 3 generators.
304
    #I  Class 3 with 5 generators.
305
    #I  Class 3 with 5 generators.
306
    <pc group of size 161051 with 5 generators>
307
    gap> # We do a ``sample'' check that pairs of elements of Q do satisfy
308
    gap> # the given identity:
309
    gap> f( Random(Q), Random(Q) );
310
    <identity> of ...
311
    gap> f( Q.1, Q.2 );
312
    <identity> of ...
313
    #I  Variables used in `PqExample' are saved in `ANUPQData.example.vars'.
314
  
315
  
316
  The  (interactive)  call  to Pq above is essentially equivalent to a call to
317
  PqPcPresentation  with  the same arguments and options followed by a call to
318
  PqCurrentGroup.   Moreover,  the  call  to  PqPcPresentation  (as  described
319
  in PqPcPresentation   (5.6-1))   is   equivalent   to  a  class  1  call  to
320
  PqPcPresentation  followed  by the requisite number of calls to PqNextClass,
321
  and  with  the  Identities option set, both PqPcPresentation and PqNextClass
322
  quietly  perform  the  equivalent  of  a  PqEvaluateIdentities  call. In the
323
  following  example we break down the Pq call into its low-level equivalents,
324
  and  set  and unset the Identities option to show where PqEvaluateIdentities
325
  fits into this scheme.
326
  
327
    Example  
328
    gap> PqExample("11gp-3-Engel-Id-i");
329
    #I  #Example: "11gp-3-Engel-Id-i" . . . 3-Engel grp for prime 11
330
    #I  #Variation of "11gp-3-Engel-Id" broken down into its lower-level component
331
    #I  #command parts.
332
    #I  F, a, b, G, f, procId, Q are local to `PqExample'
333
    gap> F := FreeGroup("a", "b"); a := F.1; b := F.2;
334
    <free group on the generators [ a, b ]>
335
    a
336
    b
337
    gap> G := F/[ a^11, b^11 ];
338
    <fp group on the generators [ a, b ]>
339
    gap> # All word pairs u, v in the pc generators of the 11-quotient Q of G 
340
    gap> # must satisfy the Engel identity: [u, v, v, v] = 1.
341
    gap> f := function(u, v) return PqLeftNormComm( [u, v, v, v] ); end;
342
    function( u, v ) ... end
343
    gap> procId := PqStart( G : Prime := 11 );
344
    4
345
    gap> PqPcPresentation( procId : ClassBound := 1);
346
    gap> PqEvaluateIdentities( procId : Identities := [f] );
347
    #I  Class 1 with 2 generators.
348
    gap> for c in [2 .. 4] do
349
    >      PqNextClass( procId : Identities := [] ); #reset `Identities' option
350
    >      PqEvaluateIdentities( procId : Identities := [f] );
351
    >    od;
352
    #I  Class 2 with 3 generators.
353
    #I  Class 3 with 5 generators.
354
    #I  Class 3 with 5 generators.
355
    gap> Q := PqCurrentGroup( procId );
356
    <pc group of size 161051 with 5 generators>
357
    gap> # We do a ``sample'' check that pairs of elements of Q do satisfy
358
    gap> # the given identity:
359
    gap> f( Random(Q), Random(Q) );
360
    <identity> of ...
361
    gap> f( Q.1, Q.2 );
362
    <identity> of ...
363
    #I  Variables used in `PqExample' are saved in `ANUPQData.example.vars'.
364
  
365
  
366
  
367
  A.3 A Large Example
368
  
369
  An  example  demonstrating how a large computation can be organised with the
370
  ANUPQ  package is the computation of the Burnside group B(5, 4), the largest
371
  group  of  exponent 4 generated by 5 elements. It has order 2^2728 and lower
372
  exponent-p  central  class  13. The example "B5-4.g" computes B(5, 4); it is
373
  based on a pq standalone input file written by M. F. Newman.
374
  
375
  To  be  able  to do examples like this was part of the motivation to provide
376
  access to the low-level functions of the standalone program from within GAP.
377
  
378
  Please  note  that  the construction uses the knowledge gained by Newman and
379
  O'Brien  in  their  initial  construction of B(5, 4), in particular, insight
380
  into  the  commutator  structure  of  the  group  and  the  knowledge of the
381
  p-central class and the order of B(5, 4). Therefore, the construction cannot
382
  be used to prove that B(5, 4) has the order and class mentioned above. It is
383
  merely  a  reconstruction of the group. More information is contained in the
384
  header of the file examples/B5-4.g.
385
  
386
    Example  
387
    procId := PqStart( FreeGroup(5) : Exponent := 4, Prime := 2 );
388
    Pq( procId : ClassBound := 2 );
389
    PqSupplyAutomorphisms( procId,
390
          [
391
            [ [ 1, 1, 0, 0, 0],      # first automorphism
392
              [ 0, 1, 0, 0, 0],
393
              [ 0, 0, 1, 0, 0],
394
              [ 0, 0, 0, 1, 0],
395
              [ 0, 0, 0, 0, 1] ],
396
    
397
            [ [ 0, 0, 0, 0, 1],      # second automorphism
398
              [ 1, 0, 0, 0, 0],
399
              [ 0, 1, 0, 0, 0],
400
              [ 0, 0, 1, 0, 0],
401
              [ 0, 0, 0, 1, 0] ]
402
                                 ] );;
403
    
404
    Relations :=
405
      [ [],          ## class 1
406
        [],          ## class 2
407
        [],          ## class 3
408
        [],          ## class 4
409
        [],          ## class 5
410
        [],          ## class 6
411
        ## class 7     
412
        [ [ "x2","x1","x1","x3","x4","x4","x4" ] ],
413
        ## class 8
414
        [ [ "x2","x1","x1","x3","x4","x5","x5","x5" ] ],
415
        ## class 9
416
        [ [ "x2","x1","x1","x3","x4","x4","x5","x5","x5" ],
417
          [ "x2","x1","x1","x2","x3","x4","x5","x5","x5" ],
418
          [ "x2","x1","x1","x3","x3","x4","x5","x5","x5" ] ],
419
        ## class 10
420
        [ [ "x2","x1","x1","x2","x3","x3","x4","x5","x5","x5" ],
421
          [ "x2","x1","x1","x3","x3","x4","x4","x5","x5","x5" ] ],
422
        ## class 11
423
        [ [ "x2","x1","x1","x2","x3","x3","x4","x4","x5","x5","x5" ],
424
          [ "x2","x1","x1","x2","x3","x1","x3","x4","x2","x4","x3" ] ],
425
        ## class 12
426
        [ [ "x2","x1","x1","x2","x3","x1","x3","x4","x2","x5","x5","x5" ],
427
          [ "x2","x1","x1","x3","x2","x4","x3","x5","x4","x5","x5","x5" ] ],
428
        ## class 13
429
        [ [ "x2","x1","x1","x2","x3","x1","x3","x4","x2","x4","x5","x5","x5" 
430
            ] ]
431
    ];
432
    
433
    for class in [ 3 .. 13 ] do
434
        Print( "Computing class ", class, "\n" );
435
        PqSetupTablesForNextClass( procId );
436
    
437
        for w in [ class, class-1 .. 7 ] do
438
    
439
            PqAddTails( procId, w );   
440
            PqDisplayPcPresentation( procId );
441
    
442
            if Relations[ w ] <> [] then
443
                # recalculate automorphisms
444
                PqExtendAutomorphisms( procId );
445
    
446
                for r in Relations[ w ] do
447
                    Print( "Collecting ", r, "\n" );
448
                    PqCommutator( procId, r, 1 );
449
                    PqEchelonise( procId );
450
                    PqApplyAutomorphisms( procId, 15 ); #queue factor = 15
451
                od;
452
    
453
                PqEliminateRedundantGenerators( procId );
454
            fi;   
455
            PqComputeTails( procId, w );
456
        od;
457
        PqDisplayPcPresentation( procId );
458
    
459
        smallclass := Minimum( class, 6 );
460
        for w in [ smallclass, smallclass-1 .. 2 ] do
461
            PqTails( procId, w );
462
        od;
463
        # recalculate automorphisms
464
        PqExtendAutomorphisms( procId );
465
        PqCollect( procId, "x5^4" );
466
        PqEchelonise( procId );
467
        PqApplyAutomorphisms( procId, 15 ); #queue factor = 15
468
        PqEliminateRedundantGenerators( procId );
469
        PqDisplayPcPresentation( procId );
470
    od;
471
  
472
  
473
  
474
  A.4 Developing descendants trees
475
  
476
  In  the  following  example  we  will  explore  the  3-groups  of rank 2 and
477
  3-coclass  1 up to 3-class 5. This will be done using the p-group generation
478
  machinery  of  the  package. We start with the elementary abelian 3-group of
479
  rank  2. From within GAP, run the example "PqDescendants-treetraverse-i" via
480
  PqExample (see PqExample (3.4-4)).
481
  
482
    Example  
483
    gap> G := ElementaryAbelianGroup( 9 );
484
    <pc group of size 9 with 2 generators>
485
    gap> procId := PqStart( G );
486
    5
487
    gap> #
488
    gap> #  Below, we use the option StepSize in order to construct descendants
489
    gap> #  of coclass 1. This is equivalent to setting the StepSize to 1 in
490
    gap> #  each descendant calculation.
491
    gap> #
492
    gap> #  The elementary abelian group of order 9 has 3 descendants of
493
    gap> #  3-class 2 and 3-coclass 1, as the result of the next command
494
    gap> #  shows. 
495
    gap> #
496
    gap> PqDescendants( procId : StepSize := 1 );
497
    [ <pc group of size 27 with 3 generators>, 
498
      <pc group of size 27 with 3 generators>, 
499
      <pc group of size 27 with 3 generators> ]
500
    gap> #
501
    gap> #  Now we will compute the descendants of coclass 1 for each of the
502
    gap> #  groups above. Then we will compute the descendants  of coclass 1
503
    gap> #  of each descendant and so  on.  Note  that the  pq program keeps
504
    gap> #  one file for each class at a time.  For example, the descendants
505
    gap> #  calculation for  the  second  group  of class  2  overwrites the
506
    gap> #  descendant file  obtained  from  the  first  group  of  class 2.
507
    gap> #  Hence,  we have to traverse the descendants tree  in depth first
508
    gap> #  order.
509
    gap> #
510
    gap> PqPGSetDescendantToPcp( procId, 2, 1 );
511
    gap> PqPGExtendAutomorphisms( procId );
512
    gap> PqPGConstructDescendants( procId : StepSize := 1 );
513
    2
514
    gap> PqPGSetDescendantToPcp( procId, 3, 1 );
515
    gap> PqPGExtendAutomorphisms( procId );
516
    gap> PqPGConstructDescendants( procId : StepSize := 1 );
517
    2
518
    gap> PqPGSetDescendantToPcp( procId, 4, 1 );
519
    gap> PqPGExtendAutomorphisms( procId );
520
    gap> PqPGConstructDescendants( procId : StepSize := 1 );
521
    2
522
    gap> #
523
    gap> #  At this point we stop traversing the ``left most'' branch of the
524
    gap> #  descendants tree and move upwards.
525
    gap> #
526
    gap> PqPGSetDescendantToPcp( procId, 4, 2 );
527
    gap> PqPGExtendAutomorphisms( procId );
528
    gap> PqPGConstructDescendants( procId : StepSize := 1 );
529
    #I  group restored from file is incapable
530
    0
531
    gap> PqPGSetDescendantToPcp( procId, 3, 2 );
532
    gap> PqPGExtendAutomorphisms( procId );
533
    gap> PqPGConstructDescendants( procId : StepSize := 1 );
534
    #I  group restored from file is incapable
535
    0
536
    gap> #  
537
    gap> #  The computations above indicate that the descendants subtree under
538
    gap> #  the first descendant of the elementary abelian group of order 9
539
    gap> #  will have only one path of infinite length.
540
    gap> #
541
    gap> PqPGSetDescendantToPcp( procId, 2, 2 );
542
    gap> PqPGExtendAutomorphisms( procId );
543
    gap> PqPGConstructDescendants( procId : StepSize := 1 );
544
    4
545
    gap> #
546
    gap> #  We get four descendants here, three of which will turn out to be
547
    gap> #  incapable, i.e., they have no descendants and are terminal nodes
548
    gap> #  in the descendants tree.
549
    gap> #
550
    gap> PqPGSetDescendantToPcp( procId, 2, 3 );
551
    gap> PqPGExtendAutomorphisms( procId );
552
    gap> PqPGConstructDescendants( procId : StepSize := 1 );
553
    #I  group restored from file is incapable
554
    0
555
    gap> #
556
    gap> #  The third descendant of class three is incapable.  Let us return
557
    gap> #  to the second descendant of class 2.
558
    gap> #
559
    gap> PqPGSetDescendantToPcp( procId, 2, 2 );
560
    gap> PqPGExtendAutomorphisms( procId );
561
    gap> PqPGConstructDescendants( procId : StepSize := 1 );
562
    4
563
    gap> PqPGSetDescendantToPcp( procId, 3, 1 );
564
    gap> PqPGExtendAutomorphisms( procId );
565
    gap> PqPGConstructDescendants( procId : StepSize := 1 );
566
    #I  group restored from file is incapable
567
    0
568
    gap> PqPGSetDescendantToPcp( procId, 3, 2 );
569
    gap> PqPGExtendAutomorphisms( procId );
570
    gap> PqPGConstructDescendants( procId : StepSize := 1 );
571
    #I  group restored from file is incapable
572
    0
573
    gap> #
574
    gap> #  We skip the third descendant for the moment ... 
575
    gap> #
576
    gap> PqPGSetDescendantToPcp( procId, 3, 4 );
577
    gap> PqPGExtendAutomorphisms( procId );
578
    gap> PqPGConstructDescendants( procId : StepSize := 1 );
579
    #I  group restored from file is incapable
580
    0
581
    gap> #
582
    gap> #  ... and look at it now.
583
    gap> #
584
    gap> PqPGSetDescendantToPcp( procId, 3, 3 );
585
    gap> PqPGExtendAutomorphisms( procId );
586
    gap> PqPGConstructDescendants( procId : StepSize := 1 );
587
    6
588
    gap> #
589
    gap> #  In this branch of the descendant tree we get 6 descendants of class
590
    gap> #  three.  Of those 5 will turn out to be incapable and one will have
591
    gap> #  7 descendants.
592
    gap> #
593
    gap> PqPGSetDescendantToPcp( procId, 4, 1 );
594
    gap> PqPGExtendAutomorphisms( procId );
595
    gap> PqPGConstructDescendants( procId : StepSize := 1 );
596
    #I  group restored from file is incapable
597
    0
598
    gap> PqPGSetDescendantToPcp( procId, 4, 2 );
599
    gap> PqPGExtendAutomorphisms( procId );
600
    gap> PqPGConstructDescendants( procId : StepSize := 1 );
601
    7
602
    gap> PqPGSetDescendantToPcp( procId, 4, 3 );
603
    gap> PqPGExtendAutomorphisms( procId );
604
    gap> PqPGConstructDescendants( procId : StepSize := 1 );
605
    #I  group restored from file is incapable
606
    0
607
  
608
  
609
  To automate the above procedure to some extent we provide:
610
  
611
  A.4-1 PqDescendantsTreeCoclassOne
612
  
613
  PqDescendantsTreeCoclassOne( i )  function
614
  PqDescendantsTreeCoclassOne(  )  function
615
  
616
  for the ith or default interactive ANUPQ process, generate a descendant tree
617
  for  the  group  of  the  process (which must be a pc p-group) consisting of
618
  descendants  of  p-coclass  1  and  extending to the class determined by the
619
  option  TreeDepth  (or  6  if  the option is omitted). In an XGAP session, a
620
  graphical  representation  of  the  descendants  tree  appears in a separate
621
  window. Subsequent calls to PqDescendantsTreeCoclassOne for the same process
622
  may  be used to extend the descendant tree from the last descendant computed
623
  that  itself  has more than one descendant. PqDescendantsTreeCoclassOne also
624
  accepts  the  options CapableDescendants (or AllDescendants) and any options
625
  accepted   by  the  interactive  PqDescendants  function  (see PqDescendants
626
  (5.3-6)).
627
  
628
  Notes
629
  
630
  1   PqDescendantsTreeCoclassOne     first    calls    PqDescendants.    If
631
        PqDescendants  has  already  been called for the process, the previous
632
        value computed is used and a warning is Info-ed at InfoANUPQ level 1.
633
  
634
  2   As  each  descendant  is  processed its unique label defined by the pq
635
        program and number of descendants is Info-ed at InfoANUPQ level 1.
636
  
637
  3   PqDescendantsTreeCoclassOne   is  an  experimental  function  that  is
638
        included  to demonstrate the sort of things that are possible with the
639
        p-group generation machinery.
640
  
641
  Ignoring   the   extra   functionality   provided   in   an   XGAP  session,
642
  PqDescendantsTreeCoclassOne,  with  one  argument  that  is  the index of an
643
  interactive ANUPQ process, is approximately equivalent to:
644
  
645
  
646
    PqDescendantsTreeCoclassOne := function( procId )
647
        local des, i;
648
    
649
        des := PqDescendants( procId : StepSize := 1 );
650
        RecurseDescendants( procId, 2, Length(des) );
651
    end;
652
  
653
  
654
  where RecurseDescendants is (approximately) defined as follows:
655
  
656
  
657
    RecurseDescendants := function( procId, class, n )
658
        local i, nr;
659
    
660
        if class > ValueOption("TreeDepth") then return; fi;
661
    
662
        for i in [1..n] do
663
            PqPGSetDescendantToPcp( procId, class, i );
664
            PqPGExtendAutomorphisms( procId );
665
            nr := PqPGConstructDescendants( procId : StepSize := 1 );
666
            Print( "Number of descendants of group ", i,
667
                   " at class ", class, ": ", nr, "\n" );
668
            RecurseDescendants( procId, class+1, nr );
669
        od;
670
        return;
671
    end;
672
  
673
  
674
  The  following  examples  (executed  via  PqExample; see PqExample (3.4-4)),
675
  demonstrate the use of PqDescendantsTreeCoclassOne:
676
  
677
  "PqDescendantsTreeCoclassOne-9-i"
678
        approximately  does example "PqDescendants-treetraverse-i" again using
679
        PqDescendantsTreeCoclassOne;
680
  
681
  "PqDescendantsTreeCoclassOne-16-i"
682
        uses the option CapableDescendants; and
683
  
684
  "PqDescendantsTreeCoclassOne-25-i"
685
        calculates all descendants by omitting the CapableDescendants option.
686
  
687
  The  numbers 9, 16 and 25 respectively, indicate the order of the elementary
688
  abelian  group  to  which  PqDescendantsTreeCoclassOne  is applied for these
689
  examples.
690
  
691

692