Debian Codegraph @

README

raw
1 #############################################################################
2 ##
3 #W README The SmallGroups Library Hans Ulrich Besche
4 ## Bettina Eick
5 ## Eamonn O'Brien
6 ##
7 ## This file contains information about the SmallGroups Library
8 ##
9
10 #############################################################################
11 #
12 # Copyright
13 #
14 #############################################################################
15
16 The SmallGroups Library is copyright by Hans Ulrich Besche, Bettina Eick and
17 Eamonn O'Brien in 2007, and is licensed under the Artistic License 2.0.
18 For details, please refer to the LICENSE file.
19
20 #############################################################################
21 #
22 # Authors
23 #
24 #############################################################################
25
26 The SmallGroups Library has been developed by
27
28 Hans Ulrich Besche
29 Fachbereich Mathematik und Informatik
30 Technische Universität Braunschweig
31 Pockelsstrasse 14
32 38106 Braunschweig
33 Germany
34
35 e-mail: [email protected]
36 http://www-public.tu-bs.de/~hubesche/
37
38 Bettina Eick
39 Fachbereich Mathematik und Informatik
40 Technische Universität Braunschweig
41 Pockelsstr. 14
42 38106 Braunschweig
43 Germany
44
45 e-mail: [email protected]
46 http://www.iaa.tu-bs.de/beick/
47
48 Eamonn A. O'Brien
49 Department of Mathematics
50 University of Auckland
51 Private Bag 92019
52 Auckland
53 New Zealand
54
55 e-mail: [email protected]
56 https://www.math.auckland.ac.nz/~obrien/
57
58 #############################################################################
59 #
60 # Introduction
61 #
62 #############################################################################
63
64 The SmallGroups Library is a catalogue of groups of `small' order.
65 Currently, (May 2008) it contains the groups
66
67 * of order at most 2000 except 1024.
68 * of squarefree order.
69 * of cubefree order at most 50 000.
70 * of order p^n for n <= 6 and all primes p.
71 * of order p^7 for the primes p = 2,3,5,7,11.
72 * whose order factorises in at most 3 primes.
73 * of order q^n * p for q^n dividing 2^8, 3^6, 5^5, 7^4 and p a prime
74 different to q
75
76 The SmallGroups Library provides access to the groups of these orders and
77 a method to identify the catalogue number of a given group for many of these
78 orders. Here we describe the organisation of this catalogue. We include
79 information on the determination of the groups, the encoding of the stored
80 groups and the algorithms used for the identification routine.
81
82 #############################################################################
83 #
84 # Available functions
85 #
86 #############################################################################
87
88 SmallGroup( order, number )
89 returns the specified group.
90
91 AllSmallGroups( order, selection-args )
92 returns all or certain groups of the given order. The optional argument
93 list of selection-args can be used to specify certain properties to the
94 function and only the groups with these properties are returned then.
95 For some properties and some group orders the desired groups are pre-
96 computed and stored. Otherwise the desired groups are filtered out of the
97 catalogue. See the GAP 4 manual for some examples.
98 Synonym: AllGroups
99
100 OneSmallGroup( order, selection-args )
101 returns one group of the given order with the specified properties or
102 fail.
103 Synonym: OneGroup
104
105 SmallGroupsInformation( order )
106 prints information on the groups of the given order. This includes
107 a description of the determination and sorting of the groups of the
108 given order.
109
110 NumberSmallGroups( order )
111 returns the number of groups of the given order.
112 Synonym: NrSmallGroups
113
114 IdGroup( G )
115 returns the catalogue number of the group G. Clearly, the groups of
116 order |G| must be available in the library for this purpose. Moreover,
117 the groups of orders 512 and 1536 are excluded.
118
119 IdsOfAllSmallGroups( order, selection-args )
120 similar to AllSmallGroups, but returns the catalogue numbers of the
121 desired groups only. This can be useful if the list of explicit groups
122 would need too much storage space to load them.
123 Synonym: IdsOfAllGroups
124
125 UnloadSmallGroupsData()
126 clears the workspace of loaded data. If some groups of the
127 catalogue are requested from GAP afterwards, then the data will
128 be loaded again automatically.
129
130 #############################################################################
131 #
132 # Layers
133 #
134 #############################################################################
135
136 The SmallGroups Library is organised in 11 layers. Each layer contains the
137 groups of certain orders:
138
139 Layer 1: the orders with at most 3 prime factors; that is, the orders
140 of type p, p^2, pq, p^3, pq^2 and pqr.
141
142 Layer 2: all remaining orders <= 1000 except 512 and 768.
143
144 Layer 3: all remaining orders of type 2^n * p with n <= 8 and
145 p an arbitrary odd prime.
146
147 Layer 4: the orders 7^4 and 5^5 and all remaining orders of type
148 q^n * p with q^n dividing 3^6, 5^5 or 7^4 and p a prime
149 different to q.
150
151 Layer 5: all remaining orders <= 2000 except 512, 1024, 1152, 1536
152 and 1920.
153
154 Layer 6: the orders 1152 and 1920.
155
156 Layer 7: the order 512.
157
158 Layer 8: the order 1536.
159
160 Layer 9: the remaining groups of order p^4, p^5 and p^6.
161
162 Layer 10: the remaining groups of squarefree order and of
163 cubefree order at most 50000.
164
165 Layer 11: the orders p^7 with p = 3,5,7,11.
166
167 This setup has been chosen for two reasons. First, the organisation in
168 layers permits to add new layers (and thus new group orders) without changes
169 to the existing catalogue. Secondly, it is possible to install a part of the
170 layers only. This might be interesting for computer-systems with little hard
171 disk space available.
172
173 For each layer i there are two internal functions:
174 `SMALL_AVAILABLE_FUNCS[i]( order )' and `ID_AVAILABLE_FUNCS[i]( order )'.
175 Both functions return fail, if the given order is not contained in this
176 layer. Otherwise the functions return an information record on the layer
177 and the order. This record contains the information needed to handle the
178 groups of the specified order internally. If the layer i is not installed,
179 then the entries SMALL_AVAILABLE_FUNCS[i] and ID_AVAILABLE_FUNCS[i] are
180 unbound.
181
182 Moreover, there are two internal header functions:
183 `SMALL_AVAILABLE( order )' and `ID_AVAILABLE( order )'.
184 These two functions are used to loop over the layer functions and find the
185 first layer containing the given order. If this layer is found, then an
186 information record on the order is returned. If there is no layer installed
187 containing the groups of this order, then the functions return fail.
188
189 #############################################################################
190 #
191 # Files and Directories
192 #
193 #############################################################################
194
195 For each layer x there are either one or two directories in small:
196 `smallx' or `smallx' and `idx'
197 The directory `smallx' contains the groups of layer x and the directory
198 `idx' contains the corresponding identification routine if available. An
199 exception to this rule is the first layer; here all the code for the groups
200 is contained in the files smlgp1.g and idgrp1.g in the main directory of
201 small. For the layers 7 and 8 there is no identitfication routine available
202 at the moment and thus there are no directories id7 and id8.
203
204 The other files in the small main directory are:
205
206 * README - this file
207 * readsml.g - for loading the small groups catalogue into GAP
208 * small.gi/gd - these are the files where the main functions for the
209 small groups catalogue are defined.
210 * gap3cat.g - identification of a small group in the Gap 3
211 `SolvableGroup' catalogue
212 * smlinfo.gi - the code for the function `SmallGroupsInformation'
213
214 #############################################################################
215 #
216 # Layer 1
217 #
218 #############################################################################
219
220 The groups whose order factorises in at most 3 primes have been classified
221 by H"older, see [11]. An algorithm to find the isomorphism type of such
222 groups was first implemented in Gap 3 by Frank Celler and Hans-Georg Esser.
223
224 H"olders classification distinguishes the groups of the following order
225 types. Let p, q and r be different primes with p < q < r.
226
227 p - 1 cyclic group
228
229 p^2 - 1 cyclic and 1 elementary abelian group
230
231 p^3 - 3 abelian groups and 2 extraspecial groups
232
233 pq - 1 cyclic group
234 1 group of type q:p if q = 1 mod p
235
236 p^2q - 2 abelian groups
237 1 group of type q:p x p if q = 1 mod p
238 1 group of type A4 if p = 2 and q = 3
239 1 group of type (pxq).p if q = 1 mod p
240 1 group of type q:C(p^2) if q = 1 mod p^2
241
242 pq^2 - 2 abelian groups
243 1 group of type q:p x q if q = 1 mod p
244 1 group of type C(q^2):p if q = 1 mod p
245 1 group of type (qxq):p if p > 2 and q+1 = 0 mod p
246 groups of type q:p + q:p
247 (1 group for p = 2 and (p+1)/2 groups otherwise)
248
249 pqr - 1 cyclic group
250 1 group of type q:p x r if q = 1 mod p
251 1 group of type r:p x q if r = 1 mod p
252 1 group of type r:q x p if r = 1 mod q
253 1 group of type r:(pxq) if r = 1 mod (p*q)
254 p-1 groups of type q:p + r:p
255
256 The groups in this layer are stored `generically'; that is, using functions
257 instead of explicit presentations. The identification routine follows the
258 classification as well.
259
260 #############################################################################
261 #
262 # Layer 2
263 #
264 #############################################################################
265
266 DETERMINATION:
267 The nilpotent groups of this layer have been constructed using p-group
268 generation, see [14] and [16]. The 2- and 3-groups of this layer have also
269 been available in the Two- and ThreeGroup library of Gap 3, see [12] and [15]
270 also. The non-nilpotent groups in this layer have been determined using the
271 Frattini extension method, the cyclic split extension method and cyclic
272 extension for the non-soluble groups, see [1], [2] and [3].
273
274 STORING:
275 The solvable groups in this layer are stored by a single long integer
276 describing a pc presentation of the group (see `PcGroupCode' or [1]).
277 For p-groups the encoded pc presentations are standard presentations and
278 they are equal to the presentations known in the 2- and 3-groups libraries
279 of GAP 3. The non-solvable groups are stored by generating permutations.
280
281 SELECTION-ARGS:
282 For the selection functions the values of the following attributes are
283 precomputed and stored:
284
285 for p-groups:
286 IsAbelian, PClassPGroup, RankPGroup, FrattinifactorSize and
287 FrattinifactorId
288
289 for non-p-groups:
290 IsAbelian, IsNilpotentGroup, IsSupersolvableGroup, IsSolvableGroup,
291 LGLength, FrattinifactorSize and FrattinifactorId
292
293 IDENTIFICATION:
294 The identification routine uses invariants of groups to identify a given
295 group. The invariants are organised as tree and stored in `ID_GROUP_TREE',
296 which contains a leaf for every group. In some cases this invariants tree
297 is not sufficient to distinguish all groups. In this case the tree is used
298 to reduce to a small number of possible groups and then a special random
299 isomorphism test finds the correct group among the possible ones.
300
301 #############################################################################
302 #
303 # Layer 3
304 #
305 #############################################################################
306
307 DETERMINATION:
308 These groups have been determined using the generic variation of the cyclic
309 split extension method and the Frattini extension method, see [3].
310
311 STORING:
312 * Nilpotent groups:
313 For each order in this layer we first list the nilpotent groups P x Q where
314 P is the cyclic group of order p and Q is a group of order 2^n. These groups
315 are sorted by the catalogue number of Q and the group Q is stored in layer 2.
316
317 * Groups with normal Sylow p-subgroup:
318 Then we consider the remaining groups with normal Sylow p-subgroup. These
319 are split extensions of type P : Q. The isomorphism type of these groups
320 depends on the isomorphism type of Q and the action homomorphism Q -> Aut(P).
321 Let K be the kernel of this homomorphism with [Q : K] = 2^i for some i. We
322 encode the homomorphisms for fixed Q and fixed i as follows.
323
324 Consider a generator g of P and let g1, ..., gr be a generating set of Q
325 (we choose the first r pc generators of Q for r the rank of Q). Consider
326 a homomorphism a : Q -> Aut(P) and let ai be the image of gi. Clearly, ai
327 is of the form ai : g -> g^li with 0 <= li <= 2^i-1. Thus we describe the
328 homomorphism a by the sequence l1, ..., lr. We encode this sequence as
329 (2^i-1)-adic number of length r; that is, we encode this sequence as
330 l1 * q^(r-1) + l2 * q^(r-2) + ... + lr * q^0 where q = 2^i. Hence each
331 homomorphism a is encoded as integer and for fixed Q and i we write all
332 these integers into a list.
333
334 A special case occurs if there are two homomorphisms a and b such that
335 ai = bi^j for some integer j; that is, the images of a are powers of the
336 images of b. In this case a is stored directly after b and we only store
337 the integer -j instead of encoding for the sequence l1, ..., lr for a.
338
339 Now we consider the case that for certain Q and i we have a list L consisting
340 of non-negative integers only; that is, the special power-case did not occur
341 for this group Q and index i. In some cases we encode such a list L further.
342 Recall that the integers in L correspond to different homomorphisms. Thus the
343 integers are all different and we may sort them in increasing order. Then we
344 can store this sorted list as binary number; that is, the list c1, ..., cs is
345 encoded as 2^(c1-1) + ... + 2^(cs-1). This is only useful, if the list L
346 does not contain large numbers.
347
348 Thus for Q and i we have either a list or an integer stored to encode the
349 corresponding homorphisms. For each index i we write all lists or integers
350 into a list such that at position Id(Q) the corresponding list or integer
351 to Q and i is found.
352
353 For i = 1 this list has no holes, since there exists at least one group
354 P : Q with K of index 2 for each group Q. Often the entry at position j
355 in this list is equal to the entry at position j-1. In this case we delete
356 the entry at position j and thus create a hole in the list.
357
358 For i > 1 there might be holes in the list if there is no group P : Q with
359 K of index 2^i. Hence the previous idea cannot be applied for i > 1. However,
360 in all the lists we have equal entries in various places. If this is the case,
361 then we substitute an entry in a list by a negative integer -j meaning that
362 the entry at this position is equal to the entry at position j.
363
364 Finally, if the list for some index i has only few entries left, then we
365 substitute the list by a record containing two lists: first the non-empty
366 positions and secondly their entries.
367
368 * Groups with normal Sylow 2-subgroup:
369 Next we consider the remaining groups of type Q : P. These exist for a few
370 primes q only. These groups are described by operation homomorphisms of the
371 type P -> Aut(Q). Here we store the catalogue number of Q and a long integer
372 for each such homomorphism a : P -> Aut(Q). Consider a generator g of P.
373 Clearly, we just need to store the image of g for each homomorphism a. The
374 image g^a is an automorphism of Q and thus we store the images under g^a
375 of a fixed generating set of Q. For this purpose we consider a canonical
376 numbering of the elements of Q and store the generator images by storing
377 their number in the element list. The sequence of these numbers are encoded
378 as (|Q|+1)-adic number; that is, the sequence e1, ..., er is stored as
379 e1 * q^(r-1) + e2 * q^(r-2) + ... + er where q = |Q| + 1.
380
381 * Groups without normal Sylow subgroup:
382 Now there are the groups of order 2^n * p without any normal Sylow subgroup
383 left. These exist for very few primes p only. They have been computed as in
384 layer 2 using the Frattini extension method. They are stored as described in
385 layer 2 using one long integer for each group.
386
387 IDENTIFICATION:
388 The identification of nilpotent groups P x Q relies on the identification of
389 Q only and this is done as in layer 2. Similarly, the groups without normal
390 Sylow subgroup are identified as described in layer 2.
391
392 For the groups Q : P with normal Sylow q-subgroup we first determine the prime
393 p and the isomorphism type of Q. If this is not sufficient, then we use the
394 methods as described in layer 2. (Recall that there are only finitely many
395 primes p possible here.)
396
397 For the groups P : Q with normal Sylow p-subgroup we first determine the
398 prime p and the isomorphism type of Q as well. Moreover, we compute the
399 centralizer K of P in Q and consider its index [Q : K] = 2^i.
400
401 In a large number of cases the catalogue numbers Id(Q) and Id(K) are
402 sufficient to determine the group P:Q uniquely. Moreover, this feature
403 is independent of p. We can recognise these cases using the tree of
404 invariants: if we can determine P:Q uniquely with Id(Q) and Id(K) only,
405 then there is no node corresponding to this case in the tree.
406
407 If there is a node in the tree, then Id(Q) and Id(K) are not sufficient to
408 determine the group uniquely. In this case we apply methods similar to
409 layer 2; that is, we use invariants. Since there are infinitely many primes
410 p which might turn up here, we need an additional idea to use the invariant
411 tree for this purpose. In the invariant tree we have invariants stored for
412 groups of type R : Q of order 2^n * r for primes r in 3, 5, 17 and 97. Now
413 we first choose the smallest prime r such that r is congruent 1 mod [Q : K].
414 The cases that [Q : K] = 2^i for i = 6, 7 or 8 cannot occur here, because
415 in this cases Id(Q) and Id(K) are always sufficient to determine the group.
416
417 Then we use that the groups P : Q behave essentially similar to the groups
418 R : Q for the chosen r. Thus we can construct a group R : Q corresponding
419 to P : Q and identify R : Q instead of P : Q.
420
421 #############################################################################
422 #
423 # Layer 4
424 #
425 #############################################################################
426
427 DETERMINATION:
428 The groups of order 2401 = 7^4 and 3125 = 5^5 have been computed using
429 p-group generation as described in layer 2 and they are stored and handled
430 similarly. The other groups in this layer have been determined as outlined
431 in layer 3 and, again, they are organised similarly.
432
433 STORING:
434 There is a difference to layer 3 in the compression of the group data; that
435 is, the groups in this layer are not compressed as efficiently as the groups
436 in layer 3. We consider the groups of type P : Q for P the cyclic group of
437 order p and Q a group of order q^n. These groups are determined by Q and
438 an operation homomorphism Q -> Aut(P). As in layer 3 we first compute
439 one integer for each operation homomorphism and then proceed to compress
440 the lists of integers for each Q and each i where q^i is the index of the
441 centralizer of P in Q. Different to layer 3 we do not compress the lists of
442 non-negative integers to a single integer and we not reduce the list for
443 i = 1 further, since in both cases the obtained compression is very small.
444
445 IDENTIFICATION:
446 The group identification is essentially similar to the procedure described
447 in layer 3. However, for the groups with normal Sylow p-subgroup we use
448 a special random isomorphism test additionally to identify groups. It is
449 a `special' version of the general algorithm: in the general algorithm we
450 use certain sets to choose generating sets from. In this special version
451 we restrict these sets suitably. (We use non-trivial elements of P and
452 certain elements of Q.) This is necessary, since the groups which appear
453 here can be to large to compute explicitly the elements sorted in conjugacy
454 classes.
455
456 #############################################################################
457 #
458 # Layer 5
459 #
460 #############################################################################
461
462 This layer is similar to layer 2.
463
464 #############################################################################
465 #
466 # Layer 6
467 #
468 #############################################################################
469
470 DETERMINATION:
471 The nilpotent groups in this layer are determined as direct products of
472 p-groups. Most of the groups of orders 1152 and 1920 have a normal Sylow
473 3-subgroup or Hall (3,5)-subgroup, resp. They are constructed using the
474 coprime split extension method, see [5]. The remaining groups of these or-
475 ders (without normal 2-complement) have been determined using the Frattini
476 extension method and the cyclic split extension method, see [1] also.
477
478 STORING:
479 Only the non-nilpotent groups with normal Sylow 3-subgroup or Hall
480 (3,5)-subgroup are stored in a special way. The remaining groups are
481 organised similar to layer 2.
482
483 For the groups of type P : Q where P is the normal Sylow 3-subgroup
484 or the Hall (3,5)-subgroup and Q is a group of order 2^7 we split a
485 pc presentation in two parts. The first part are the relators of Q.
486 These are stored within the groups of order 2^7 and thus can be
487 considered as known. The second part of the relators determine P and
488 the operation of Q on P. These second parts are stored as long integers.
489 If we consider these second parts for all the groups, then we find that
490 they are highly redundant. There are only 921 (1722) different long
491 integers for the groups of order 1152 and 1920, resp. Thus we store
492 these two sets of long integers only.
493
494 Then for each group Q of order 2^7 we store for each extension P : Q
495 the position of the corresponding long integer. Hence we obtain a list
496 of integers for Q. Again we note that the lists of integers obtained
497 for all the groups Q of order 2^7 are highly redundant. There are only
498 1298 (722) different lists for the groups of order 1152 (1920). Thus
499 we can compress the lists using the same idea again.
500
501 IDENTIFICATION:
502 The identification of groups of these orders is similar to layer 2.
503
504 #############################################################################
505 #
506 # Layer 7
507 #
508 #############################################################################
509
510 DETERMINATION:
511 The groups of order 512 have first been enumerated, see [8] and [9]. Later
512 they have been determined explicitly using p-group generation, see [14] and
513 [5]. There are 10494213 groups of this order.
514
515 STORING:
516 We introduce a special method to store such groups. Consider a pc presen-
517 tation of a given group of order 512. If we concatenate the exponent vectors
518 of the right hand sides of such a presentation, then we obtain a bit vector
519 of length 120. This can be used as encoding of a group of order 512. We
520 compress the list of such encodings further using the following method.
521
522 First we split the list of all groups of order 512 in sublists containing
523 1000 groups each. Let L be such a sublist. We suppose that L consists of
524 1000 bitlists of length 120 and we describe a method to encode this list
525 of bitlists in a single vector V using an alphabet of 83 symbols. (81
526 symbols for the encoding and 2 special symbols as signs.)
527
528 First we find those indices i in the range 1 to 120 such that for all
529 lists in L the entries at position i are fixed. Thus we note for each of
530 the 120 entries whether the entries are all 0, all 1 or variable in L.
531 There are 3^120 combinations possible which we store in a vector of length
532 30 using 81 symbols. This vector of length 30 is the initial segment of V.
533 Now we can reduce to consider the variable positions only and thus work
534 with bitlists of shorter length.
535
536 We split the shorter bitlists in blocks such that the bitlists in each block
537 have at most 6 variable entries. For this purpose we start at the beginning
538 of L and add bitlists to the current block until the next bitlist would lead
539 to more than 6 variable entries for this block. Each block can contain 1 up
540 to 64 bitlists. Now we determine a `headcode' and a `tailcode' to describe
541 the block. The head and tail codes are then concatenated to V. The head
542 contains an encoding of the variable bits for this block as above. The tail
543 then describes the vectors in the variable bits. Since they are at most 64
544 possible combinations arising here, we need only one letter in the 81-alpha-
545 bet to describe a single vector of variable bits.
546
547 Finally, we note that some of the tailcodes arise for many blocks. These
548 tailcodes are stored in a special list. If such a tailcode is occurring
549 in V, then only the reference to the special list is stored instead of
550 the full tailcode. This special list contains 1890 different tailcodes,
551 2 letters in the alphabet are sufficient to refer a tailcode.
552
553 To distinguish references and actual tailcodes we use a special sign. Each
554 new head begins with a special symbol in V. There are two special symbols
555 available for this purpose. One is used, if the corresponding tailcode is
556 referenced, and the other, if it is an ordinary tailcode.
557
558 This compression allows to store the groups of order 512 in 4.4 mb.
559
560 #############################################################################
561 #
562 # Layer 8
563 #
564 #############################################################################
565
566 DETERMINATION:
567 The 408641062 groups of order 1536 have been determined using the cyclic
568 split extension method and the improved version of the Frattini extension
569 method, see [1] and [3]. Note that the number of groups of this order is
570 too large to be an ordinary GAP integer. Thus it is not possible to loop
571 over these groups with a for-loop in GAP.
572
573 STORING:
574 We store these groups in a special way as well and we obtain a compression
575 to 6.1 mb. The groups are stored using references to the groups of order
576 512 of layer 7.
577
578 The nilpotent groups C3 x Q for Q a group of order 512 are based on the
579 groups of order 512.
580
581 The major part of the groups are the 398032384 non-nilpotent groups with
582 normal Sylow 3-subgroup. The compression of these groups follows the one
583 outlined in layer 3. As described there for each group Q of order 512 we
584 compute an integer which determines all groups of type C3 : Q. There are
585 only 15249 different integers of this type. In a first compression we
586 create a list of references to the different integers.
587
588 Now we note that a group often has the same reference as the previous
589 one. Thus we split the groups of order 512 in sets of 100 000 groups and
590 create a record for each set. The record contains two lists which
591 are used to recall the blocks in a set having the same reference.
592 Thus the first list contains the length of the blocks and the second
593 list contains the corresponding references.
594
595 Again, in both lists certain patterns occur often. In the first list
596 the length `1' appears often. Thus the `1' is not stored explicitly,
597 but a blank in this lists has to be considered as `1'. In the second
598 list often an entry is the same as the one 2 places bevor. Thus these
599 entries are deleted as well and blanks can be reconstructed by this
600 rule.
601
602 Additionally we store the number of resulting groups for each integer
603 to speed up the method to find the group with a given catalogue number.
604
605 The 18028 groups with normal Sylow 2-subgroup are stored similarly to
606 layer 3. As described for layer 3 we determine a long integer for each
607 homomorphism Q -> Aut(P) for Q of order 512 and P the cyclic group of
608 order 3. The occurring integers are highly redundant - there are 6774
609 different ones. Thus we use a list of references again.
610
611 The 96437 groups without normal Sylow subgroup are determined using the
612 Frattini extension method. As described in layer 2 they can be stored
613 by encoding the relators of a pc presentation as long integer. However,
614 the relators corresponding to the Frattini factors of the groups are
615 known. Thus it is sufficient to store the relators of the Frattini factors
616 once for all groups with this factor and encode the remaining relators only.
617 Note that there are only 16 different Frattini factors and only 12 of them
618 have order less than 1536. The groups are stored in lists corresponding
619 to the 12 Frattini factors.
620
621 #############################################################################
622 #
623 # Layer 9
624 #
625 #############################################################################
626
627 This layer contains the generic construction of groups of order p^4, p^5
628 and p^6 with order > 3125 (those with order up to 3125 are contained in
629 the lower layers of the small groups library).
630
631 DETERMINATION:
632
633 The groups of order p^4 were first determined by H\"older (1893)[11].
634 The groups of order p^5 were first determined by Bagnera (1898).
635 The groups of order p^6 were first (correctly) determined by
636 Newman, O'Brien and Vaughan-Lee (2003)[13].
637
638 STORING:
639
640 The groups of order p^4 (p >= 11) are given by pc presentations which are
641 produced at run-time by a function SMALL_GROUPS_FUNCS[ 19 ] provided by
642 Newman.
643
644 The groups of order p^5 (p >= 7) are given by pc presentations which are
645 produced at run-time by a function SMALL_GROUPS_FUNCS[ 20 ] provided by
646 Girnat (2004) [10].
647
648 The groups of order p^6 (p >= 5) are given by pc presentations which are
649 produced at run-time by a function SMALL_GROUPS_FUNCS[ 21 ] provided by
650 Newman, O'Brien and Vaughan-Lee (2003) [13].
651
652 The groups of order p^6 are given as a list of partially repetitive structures.
653 These are compressed into the file 'sml1.z'. At run-time, this compressed
654 structure will be expanded, but restricted to those parts of the structure
655 relevant for the given p when needed. It is cached into SMALL_GROUP_LIB[1].
656 As parts of this structure contain long ( O(p^2) ) lists of groups which are
657 classified by additional parameters and these lists are not dense, it might
658 be necessary to set up the complete list of indices to find the presentation
659 of a single group.
660
661 IDENTIFICATION:
662
663 A group of order p^4 can be identified and its catalogue number found by the
664 function ID_SMALL_GROUPS_FUNCS[ 19 ] based on a function provided by Newman
665 and modified by Besche.
666
667 There is no identification available for the groups of order p^5 and p^6 at
668 current.
669
670 #############################################################################
671 #
672 # Layer 10
673 #
674 #############################################################################
675
676 GROUPS OF SQUAREFREE ORDER:
677
678 DETERMINATION:
679
680 These groups have first been determined by H\"older (1895). The implemented
681 construction is based on the determination given in [7]. The key invariants
682 are the socle and socle factor.
683
684 STORING:
685
686 The groups of squarefree order which are not contained in lower layers are
687 given by pc presentations which are produced at run-time by a function
688 SMALL_GROUPS_FUNCS[ 24 ] written specially for this library.
689
690 IDENTIFICATION:
691
692 A group of this kind can be identified and its catalogue number found by the
693 function ID_SMALL_GROUPS_FUNCS[ 24 ].
694
695
696 GROUPS OF CUBEFREE but not SQUAREFREE ORDER:
697
698 DETERMINATION:
699
700 First determined in [7]. Every group with cubefree order is either solvable
701 or has a direct decomposition into a solvable group and PSL(2,p) for a
702 suitable prime.
703
704 STORING:
705
706 The groups of cubefree order < 50000 which are not contained in lower layers
707 and are not squarefree are given by pc presentations which are produced at
708 run-time by a function SMALL_GROUPS_FUNCS[ 25 ] written specially for this
709 library.
710
711 IDENTIFICATION:
712
713 A group of this kind can be identified and its catalogue number found by the
714 function ID_SMALL_GROUPS_FUNCS[ 24 ].
715
716 #############################################################################
717 #
718 # Layer 11
719 #
720 #############################################################################
721
722 DETERMINATION:
723
724 The groups of order p^7 have been determined by O'Brien and Vaughan-Lee, see
725 [17]. This layer contains these groups for some small primes: p = 3,5,7,11.
726
727 STORING:
728
729 The groups are encoded by PcGroupCode and then the various codes are stored
730 in compressed form. See the groups of order 512 for details. Pc presentations
731 for the groups are produced at run-time for these groups.
732
733 IDENTIFICATION:
734
735 There is no identification function available for the groups in this layer.
736
737 #############################################################################
738 #
739 # Concluding remarks
740 #
741 #############################################################################
742
743 The compression of group data for layer 2 has been developed long ago. A
744 first version has been used in the p-group generation algorithm and thus
745 to encode the 2- and 3-groups library of Gap 3. This compression is des-
746 cribed in [1].
747
748 The remaining compression methods for layers 3 - 8 have been introduced by
749 Hans Ulrich Besche specially for this library. They are designed to store
750 the groups in as few space as possible. For different layers there are
751 different methods, since certain approaches had been successful for certain
752 groups but not for others. Moreover, already published layers have not been
753 changed again and thus useful concepts sometimes have not been applied to
754 earlier layers.
755
756 #############################################################################
757 #
758 # References
759 #
760 #############################################################################
761
762 [1] Hans Ulrich Besche and Bettina Eick.
763 The construction of finite groups.
764 J. Symbolic Comput. 27, 387 - 404 (1999).
765
766 [2] Hans Ulrich Besche and Bettina Eick.
767 The groups of order at most 1000 except 512 and 768.
768 J. Symbolic Comput. 27, 405 - 413 (1999).
769
770 [3] Hans Ulrich Besche and Bettina Eick.
771 The groups of order q^n * p.
772 Comm. Alg. 29, 1759 - 1772 (2001)
773
774 [4] Hans Ulrich Besche and Bettina Eick.
775 The GrpConst share package of GAP 4.
776
777 [5] Hans Ulrich Besche, Bettina Eick and E. A. O'Brien.
778 A millennium project: constructing small groups.
779 Internat. J. Algebra Comput. 12, 623 - 644 (2002)
780
781 [6] Hans Ulrich Besche, Bettina Eick and E. A. O'Brien.
782 The groups of order at most 2000.
783 Electronic Research Announcements of the AMS 7, 1 - 4 (2001)
784
785 [7] Heiko Dietrich and Bettina Eick.
786 Groups of cube-free order.
787 J. Algebra. (To Appear)
788
789 [8] Bettina Eick and E. A. O'Brien.
790 The groups of order 512.
791 Proceedings of the `Abschlusstagung des DFG Schwerpunktes
792 Algorithmische Algebra und Zahlentheorie', Springer (1998)
793
794 [9] Bettina Eick and E. A. O'Brien.
795 Enumerating p-groups.
796 Austal. Math. Soc. Ser. A, 67, 191 - 205 (1999).
797
798 [10] B. Girnat.
799 Klassifikation der Gruppen bis zur Ordnung p^5.
800 Staatsexamensarbeit, TU Braunschweig.
801
802 [11] Otto H"older.
803 Die Gruppen der Ordnungen p^3, pq^2, pqr, p^4.
804 Math. Ann. 43, 301 - 412 (1893).
805
806 [12] Rodney James, M. F. Newman and E. A. O'Brien.
807 The groups of order 128.
808 J. Algebra 129 (1), 136 - 158 (1990)
809
810 [13] M. F. Newman, E. A. O'Brien and M. R. Vaughan-Lee.
811 Groups and nilpotent Lie rings whose order is the sixth power of a prime.
812 J. Algebra 278, 383 - 401 (2003)
813
814 [14] E. A. O'Brien.
815 The p-group generation algorithm.
816 J. Symbolic Comput. 9, 677 - 698 (1990)
817
818 [15] E. A. O'Brien.
819 The groups of order 256.
820 J. Algebra 143 (1), 219 - 235 (1991)
821
822 [16] E. A. O'Brien.
823 The ANUPQ share package of Gap 3.
824
825 [17] E. A. O'Brien and M. R. Vaughan-Lee.
826 The groups of order p^7 for odd prime p.
827 J. Algebra 292, 243 - 258 (2005)
828
829
830 #############################################################################
831 #
832 # Bugs and problems
833 #
834 #############################################################################
835
836 Please report bugs/problems/feedback to the authors or to gap-support
837
838 [email protected]
839 [email protected]
840 [email protected]
841 [email protected]