| 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] |