File: chap3.txt

package info (click to toggle)
gap-polycyclic 2.15.1-1
  • links: PTS
  • area: main
  • in suites: bullseye
  • size: 2,636 kB
  • sloc: xml: 3,007; makefile: 126
file content (369 lines) | stat: -rw-r--r-- 19,282 bytes parent folder | download | duplicates (2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
  
  3 Collectors
  
  Let  G  be  a group defined by a pc-presentation as described in the Chapter
  'Introduction to polycyclic presentations'.
  
  The  process  for  computing the collected form for an arbitrary word in the
  generators  of  G  is called collection. The basic idea in collection is the
  following.  Given  a word in the defining generators, one scans the word for
  occurrences of adjacent generators (or their inverses) in the wrong order or
  occurrences  of  subwords  g_i^e_i  with  i∈ I and e_i not in the range 0...
  r_i-1. In the first case, the appropriate conjugacy relation is used to move
  the  generator  with  the smaller index to the left. In the second case, one
  uses  the  appropriate  power  relation to move the exponent of g_i into the
  required range. These steps are repeated until a collected word is obtained.
  
  There  exist a number of different strategies for collecting a given word to
  collected  form.  The  strategies implemented in this package are collection
  from  the  left  as  described  by  [LGS90]  and  [Sim94]  and combinatorial
  collection from the left by [VL90]. In addition, the package provides access
  to  Hall  polynomials  computed  by Deep Thought for the multiplication in a
  nilpotent group, see [Mer97] and [LGS98].
  
  The  first  step  in  defining  a  pc-presented  group  is setting up a data
  structure  that  knows the pc-presentation and has routines that perform the
  collection  algorithm with words in the generators of the presentation. Such
  a data structure is called a collector.
  
  To  describe  the  right hand sides of the relations in a pc-presentation we
  use  generator  exponent  lists; the word g_i_1^e_1g_i_2^e_2... g_i_k^e_k is
  represented by the generator exponent list [i_1,e_1,i_2,e_2,...,i_k,e_k].
  
  
  3.1 Constructing a Collector
  
  A  collector  for a group given by a pc-presentation starts by setting up an
  empty  data structure for the collector. Then the relative orders, the power
  relations and the conjugate relations are added into the data structure. The
  construction  is  finalised  by  calling  a  routine that completes the data
  structure  for  the collector. The following functions provide the necessary
  tools for setting up a collector.
  
  3.1-1 FromTheLeftCollector
  
  FromTheLeftCollector( n )  operation
  
  returns  an  empty  data  structure  for  a  collector with n generators. No
  generator  has  a relative order, no right hand sides of power and conjugate
  relations  are  defined.  Two  generators  for which no right hand side of a
  conjugate  relation is defined commute. Therefore, the collector returned by
  this function can be used to define a free abelian group of rank n.
  
    Example  
    gap> ftl := FromTheLeftCollector( 4 );
    <<from the left collector with 4 generators>>
    gap> PcpGroupByCollector( ftl );
    Pcp-group with orders [ 0, 0, 0, 0 ]
    gap> IsAbelian(last);
    true
  
  
  If the relative order of a generators has been defined (see SetRelativeOrder
  (3.1-2)),  but  the  right hand side of the corresponding power relation has
  not, then the order and the relative order of the generator are the same.
  
  3.1-2 SetRelativeOrder
  
  SetRelativeOrder( coll, i, ro )  operation
  SetRelativeOrderNC( coll, i, ro )  operation
  
  set  the  relative  order  in  collector  coll  for  generator  i to ro. The
  parameter    coll   is   a   collector   as   returned   by   the   function
  FromTheLeftCollector   (3.1-1),  i  is  a  generator  number  and  ro  is  a
  non-negative  integer.  The  generator  number  i is an integer in the range
  1,...,n where n is the number of generators of the collector.
  
  If ro is 0, then the generator with number i has infinite order and no power
  relation  can  be  specified.  As  a  side effect in this case, a previously
  defined power relation is deleted.
  
  If  ro  is  the  relative  order  of  a generator with number i and no power
  relation is set for that generator, then ro is the order of that generator.
  
  The NC version of the function bypasses checks on the range of i.
  
    Example  
    gap> ftl := FromTheLeftCollector( 4 );
    <<from the left collector with 4 generators>>
    gap> for i in [1..4] do SetRelativeOrder( ftl, i, 3 ); od;
    gap> G := PcpGroupByCollector( ftl );
    Pcp-group with orders [ 3, 3, 3, 3 ]
    gap> IsElementaryAbelian( G );
    true
  
  
  3.1-3 SetPower
  
  SetPower( coll, i, rhs )  operation
  SetPowerNC( coll, i, rhs )  operation
  
  set  the  right hand side of the power relation for generator i in collector
  coll  to  (a  copy  of)  rhs.  An  attempt  to set the right hand side for a
  generator without a relative order results in an error.
  
  Right hand sides are by default assumed to be trivial.
  
  The  parameter  coll  is  a  collector, i is a generator number and rhs is a
  generators exponent list or an element from a free group.
  
  The  no-check (NC) version of the function bypasses checks on the range of i
  and stores rhs (instead of a copy) in the collector.
  
  3.1-4 SetConjugate
  
  SetConjugate( coll, j, i, rhs )  operation
  SetConjugateNC( coll, j, i, rhs )  operation
  
  set the right hand side of the conjugate relation for the generators j and i
  with  j  larger  than  i.  The  parameter  coll  is a collector, j and i are
  generator  numbers and rhs is a generator exponent list or an element from a
  free group. Conjugate relations are by default assumed to be trivial.
  
  The generator number i can be negative in order to define conjugation by the
  inverse of a generator.
  
  The  no-check (NC) version of the function bypasses checks on the range of i
  and j and stores rhs (instead of a copy) in the collector.
  
  3.1-5 SetCommutator
  
  SetCommutator( coll, j, i, rhs )  operation
  
  set the right hand side of the conjugate relation for the generators j and i
  with  j larger than i by specifying the commutator of j and i. The parameter
  coll  is  a  collector, j and i are generator numbers and rhs is a generator
  exponent list or an element from a free group.
  
  The  generator  number  i  can be negative in order to define the right hand
  side of a commutator relation with the second generator being the inverse of
  a generator.
  
  3.1-6 UpdatePolycyclicCollector
  
  UpdatePolycyclicCollector( coll )  operation
  
  completes  the data structures of a collector. This is usually the last step
  in  setting  up  a collector. Among the steps performed is the completion of
  the  conjugate  relations.  For  each  non-trivial  conjugate  relation of a
  generator,  the corresponding conjugate relation of the inverse generator is
  calculated.
  
  Note  that UpdatePolycyclicCollector is automatically called by the function
  PcpGroupByCollector (see PcpGroupByCollector (4.3-1)).
  
  3.1-7 IsConfluent
  
  IsConfluent( coll )  property
  
  tests if the collector coll is confluent. The function returns true or false
  accordingly.
  
  Compare Chapter 2 for a definition of confluence.
  
  Note   that   confluence   is   automatically   checked   by   the  function
  PcpGroupByCollector (see PcpGroupByCollector (4.3-1)).
  
  The  following  example  defines a collector for a semidirect product of the
  cyclic group of order 3 with the free abelian group of rank 2. The action of
  the cyclic group on the free abelian group is given by the matrix
  
  
  \pmatrix{ 0 & 1 \cr -1 & -1}.
  
  
  
  This leads to the following polycyclic presentation:
  
  
  \langle  g_1,g_2,g_3  |  g_1^3,  g_2^{g_1}=g_3,  g_3^{g_1}=g_2^{-1}g_3^{-1},
  g_3^{g_2}=g_3\rangle.
  
  
  
    Example  
    gap> ftl := FromTheLeftCollector( 3 );
    <<from the left collector with 3 generators>>
    gap> SetRelativeOrder( ftl, 1, 3 );
    gap> SetConjugate( ftl, 2, 1, [3,1] );
    gap> SetConjugate( ftl, 3, 1, [2,-1,3,-1] );
    gap> UpdatePolycyclicCollector( ftl );
    gap> IsConfluent( ftl );
    true
  
  
  The action of the inverse of g_1 on ⟨ g_2,g_2⟩ is given by the matrix
  
  
  \pmatrix{ -1 & -1 \cr 1 & 0}.
  
  
  
  The   corresponding   conjugate  relations  are  automatically  computed  by
  UpdatePolycyclicCollector. It is also possible to specify the conjugation by
  inverse  generators.  Note  that  you  need to run UpdatePolycyclicCollector
  after one of the set functions has been used.
  
    Example  
    gap> SetConjugate( ftl, 2, -1, [2,-1,3,-1] );
    gap> SetConjugate( ftl, 3, -1, [2,1] );
    gap> IsConfluent( ftl );
    Error, Collector is out of date called from
    CollectWordOrFail( coll, ev1, [ j, 1, i, 1 ] ); called from
    <function>( <arguments> ) called from read-eval-loop
    Entering break read-eval-print loop ...
    you can 'quit;' to quit to outer loop, or
    you can 'return;' to continue
    brk>
    gap> UpdatePolycyclicCollector( ftl );
    gap> IsConfluent( ftl );
    true
  
  
  
  3.2 Accessing Parts of a Collector
  
  3.2-1 RelativeOrders
  
  RelativeOrders( coll )  attribute
  
  returns (a copy of) the list of relative order stored in the collector coll.
  
  3.2-2 GetPower
  
  GetPower( coll, i )  operation
  GetPowerNC( coll, i )  operation
  
  returns a copy of the generator exponent list stored for the right hand side
  of the power relation of the generator i in the collector coll.
  
  The  no-check (NC) version of the function bypasses checks on the range of i
  and does not create a copy before returning the right hand side of the power
  relation.
  
  3.2-3 GetConjugate
  
  GetConjugate( coll, j, i )  operation
  GetConjugateNC( coll, j, i )  operation
  
  returns  a  copy of the right hand side of the conjugate relation stored for
  the generators j and i in the collector coll as generator exponent list. The
  generator j must be larger than i.
  
  The  no-check (NC) version of the function bypasses checks on the range of i
  and j and does not create a copy before returning the right hand side of the
  power relation.
  
  3.2-4 NumberOfGenerators
  
  NumberOfGenerators( coll )  operation
  
  returns the number of generators of the collector coll.
  
  3.2-5 ObjByExponents
  
  ObjByExponents( coll, expvec )  operation
  
  returns  a  generator  exponent list for the exponent vector expvec. This is
  the  inverse  operation to ExponentsByObj. See ExponentsByObj (3.2-6) for an
  example.
  
  3.2-6 ExponentsByObj
  
  ExponentsByObj( coll, genexp )  operation
  
  returns  an  exponent vector for the generator exponent list genexp. This is
  the  inverse  operation  to  ObjByExponents.  The  function assumes that the
  generators in genexp are given in the right order and that the exponents are
  in the right range.
  
    Example  
    gap> G := UnitriangularPcpGroup( 4, 0 );
    Pcp-group with orders [ 0, 0, 0, 0, 0, 0 ]
    gap> coll := Collector ( G );
    <<from the left collector with 6 generators>>
    gap> ObjByExponents( coll, [6,-5,4,3,-2,1] );
    [ 1, 6, 2, -5, 3, 4, 4, 3, 5, -2, 6, 1 ]
    gap> ExponentsByObj( coll, last );
    [ 6, -5, 4, 3, -2, 1 ]
  
  
  
  3.3 Special Features
  
  In this section we descibe collectors for nilpotent groups which make use of
  the special structure of the given pc-presentation.
  
  3.3-1 IsWeightedCollector
  
  IsWeightedCollector( coll )  property
  
  checks  if  there  is a function w from the generators of the collector coll
  into  the positive integers such that w(g) ≥ w(x)+w(y) for all generators x,
  y and all generators g in (the normal of) [x,y]. If such a function does not
  exist,  false  is  returned.  If  such a function exists, it is computed and
  stored  in  the  collector. In addition, the default collection strategy for
  this collector is set to combinatorial collection.
  
  3.3-2 AddHallPolynomials
  
  AddHallPolynomials( coll )  function
  
  is  applicable  to a collector which passes IsWeightedCollector and computes
  the Hall multiplication polynomials for the presentation stored in coll. The
  default  strategy  for  this collector is set to evaluating those polynomial
  when multiplying two elements.
  
  3.3-3 String
  
  String( coll )  attribute
  
  converts a collector coll into a string.
  
  3.3-4 FTLCollectorPrintTo
  
  FTLCollectorPrintTo( file, name, coll )  function
  
  stores a collector coll in the file file such that the file can be read back
  using  the function 'Read' into GAP and would then be stored in the variable
  name.
  
  3.3-5 FTLCollectorAppendTo
  
  FTLCollectorAppendTo( file, name, coll )  function
  
  appends  a  collector  coll  in the file file such that the file can be read
  back into GAP and would then be stored in the variable name.
  
  3.3-6 UseLibraryCollector
  
  UseLibraryCollector global variable
  
  this  property  can  be  set  to  true  for  a  collector  to force a simple
  from-the-left  collection  strategy  implemented  in  the GAP language to be
  used. Its main purpose is to help debug the collection routines.
  
  3.3-7 USE_LIBRARY_COLLECTOR
  
  USE_LIBRARY_COLLECTOR global variable
  
  this  global  variable  can  be set to true to force all collectors to use a
  simple  from-the-left collection strategy implemented in the GAP language to
  be used. Its main purpose is to help debug the collection routines.
  
  3.3-8 DEBUG_COMBINATORIAL_COLLECTOR
  
  DEBUG_COMBINATORIAL_COLLECTOR global variable
  
  this  global  variable can be set to true to force the comparison of results
  from  the combinatorial collector with the result of an identical collection
  performed  by  a simple from-the-left collector. Its main purpose is to help
  debug the collection routines.
  
  3.3-9 USE_COMBINATORIAL_COLLECTOR
  
  USE_COMBINATORIAL_COLLECTOR global variable
  
  this  global  variable  can  be  set  to  false  in  order  to  prevent  the
  combinatorial collector to be used.