1.26 About Group Libraries

When you start GAP it already knows several groups. For example, some basic groups such as cyclic groups or symmetric groups, all primitive permutation groups of degree at most 50, and all 2-groups of size at most 256.

Each of the sets above is called a group library. The set of all groups that GAP knows initially is called the collection of group libraries.

In this section we show you how you can access the groups in those libraries and how you can extract groups with certain properties from those libraries.

Let us start with the basic groups, because they are not accessed in the same way as the groups in the other libraries.

To access such a basic group you just call a function with an appropriate name, such as CyclicGroup or SymmetricGroup.

    gap> c13 := CyclicGroup( 13 );
    Group( ( 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13) )
    gap> Size( c13 );
    13
    gap> s8 := SymmetricGroup( 8 );
    Group( (1,8), (2,8), (3,8), (4,8), (5,8), (6,8), (7,8) )
    gap> Size( s8 );
    40320 

The functions above also accept an optional first argument that describes the type of group. For example you can pass AgWords to CyclicGroup Finite Polycyclic Groups).

    gap> c13 := CyclicGroup( AgWords, 13 );
    Group( c13 ) 

Of course you cannot pass AgWords to SymmetricGroup, because symmetric groups are in general not polycyclic.

The default is to construct the groups as permutation groups, but you can also explicitly pass Permutations. Other possible arguments are AgWords for finite polycyclic groups, Words for finitely presented groups, and Matrices for matrix groups (however only Permutations and AgWords currently work).

Let us now turn to the other libraries. They are all accessed in a uniform way. For a first example we will use the group library of primitive permutation groups.

To extract a group from a group library you generally use the extraction function. In our example this function is called PrimitiveGroup. It takes two arguments. The first is the degree of the primitive permutation group that you want and the second is an integer that specifies which of the primitive permutation groups of that degree you want.

    gap> g := PrimitiveGroup( 12, 3 );
    M(11)
    gap> g.generators;
    [ ( 2, 6)( 3, 5)( 4, 7)( 9,10), ( 1, 5, 7)( 2, 9, 4)( 3, 8,10),
      ( 1,11)( 2, 7)( 3, 5)( 4, 6), ( 2, 5)( 3, 6)( 4, 7)(11,12) ]
    gap> Size( g );
    7920
    gap> IsSimple( g );
    true
    gap> h := PrimitiveGroup( 16, 19 );
    2^4.A(7)
    gap> Size( h );
    40320 

The reason for the extraction function is as follows. A group library is usually not stored as a list of groups. Instead a more compact representation for the groups is used. For example the groups in the library of 2-groups are represented by 4 integers. The extraction function hides this representation from you, and allows you to access the group library as if it was a table of groups (two dimensional in the above example).

What arguments the extraction function accepts, and how they are interpreted is described in the sections that describe the individual group libraries in chapter Group Libraries. Those functions will of course signal an error when you pass illegal arguments.

Suppose that you want to get a list of all primitive permutation groups that have a degree 10 and are simple but not cyclic. It would be very difficult to use the extraction function to extract all groups in the group library, and test each of those. It is much simpler to use the selection function. The name of the selection function always begins with All and ends with Groups, in our example it is thus called AllPrimitiveGroups.

    gap> AllPrimitiveGroups( DegreeOperation,   10,
    >                        IsSimple,          true,
    >                        IsCyclic,          false );
    [ A(5), PSL(2,9), A(10) ] 

AllPrimitiveGroups takes a variable number of argument pairs consisting of a function (e.g. DegreeOperation) and a value (e.g. 10). To understand what AllPrimitiveGroups does, imagine that the group library was stored as a long list of permutation groups. AllPrimitiveGroups takes all those groups in turn. To each group it applies each function argument and compares the result with the corresponding value argument. It selects a group if and only if all the function results are equal to the corresponding value. So in our example AllPrimitiveGroups selects those groups g for which DegreeOperation(g) = 10 and IsSimple(g) = true and IsCyclic(g) = false. Finally AllPrimitiveGroups returns the list of the selected groups.

Next suppose that you want all the primitive permutation groups that have degree at most 10, are simple but are not cyclic. You could obtain such a list with 10 calls to AllPrimitiveGroups (i.e., one call for the degree 1 groups, another for the degree 2 groups and so on), but there is a simple way. Instead of specifying a single value that a function must return you can simply specify a list of such values.

    gap> AllPrimitiveGroups( DegreeOperation,   [1..10],
    >                        IsSimple,          true,
    >                        IsCyclic,          false );
    [ A(5), PSL(2,5), A(6), PSL(3,2), A(7), PSL(2,7), A(8), PSL(2,8),
      A(9), A(5), PSL(2,9), A(10) ] 

Note that the list that you get contains A(5) twice, first in its primitive presentation on 5 points and second in its primitive presentation on 10 points.

Thus giving several argument pairs to the selection function allows you to express the logical and of properties that a group must have to be selected, and giving a list of values allows you to express a (restricted) logical or of properties that a group must have to be selected.

There is no restriction on the functions that you can use. It is even possible to use functions that you have written yourself. Of course, the functions must be unary, i.e., accept only one argument, and must be able to deal with the groups.

    gap> NumberConjugacyClasses := function ( g )
    >        return Length( ConjugacyClasses( g ) );
    > end;
    function ( g ) ... end
    gap> AllPrimitiveGroups( DegreeOperation,           [1..10],
    >                        IsSimple,                  true,
    >                        IsCyclic,                  false,
    >                        NumberConjugacyClasses,    9 );
    [ A(7), PSL(2,8) ] 

Note that in some cases a selection function will issue a warning. For example if you call AllPrimitiveGroups without specifying the degree, it will issue such a warning.

    gap> AllPrimitiveGroups( Size,      [100..400],
    >                        IsSimple,  true,
    >                        IsCyclic,  false );
    #W  AllPrimitiveGroups: degree automatically restricted to [1..50]
    [ A(6), PSL(3,2), PSL(2,7), PSL(2,9), A(6) ] 

If selection functions would really run over the list of all groups in a group library and apply the function arguments to each of those, they would be very inefficient. For example the 2-groups library contains 58760 groups. Simply creating all those groups would take a very long time.

Instead selection functions recognize certain functions and handle them more efficiently. For example AllPrimitiveGroups recognizes DegreeOperation. If you pass DegreeOperation to AllPrimitiveGroups it does not create a group to apply DegreeOperation to it. Instead it simply consults an index and quickly eliminates all groups that have a different degree. Other functions recognized by AllPrimitiveGroups are IsSimple, Size, and Transitivity.

So in our examples AllPrimitiveGroups, recognizing DegreeOperation and IsSimple, eliminates all but 16 groups. Then it creates those 16 groups and applies IsCyclic to them. This eliminates 4 more groups (C(2), C(3), C(5), and C(7)). Then in our last example it applies NumberConjugacyClasses to the remaining 12 groups and eliminates all but A(7) and PSL(2,8).

The catch is that the selection functions will take a large amount of time if they cannot recognize any special functions. For example the following selection will take a large amount of time, because only IsSimple is recognized, and there are 116 simple groups in the primitive groups library.

AllPrimitiveGroups( IsSimple, true, NumberConjugacyClasses, 9 );

So you should specify a sufficiently large set of recognizable functions when you call a selection function. It is also advisable to put those functions first (though in some group libraries the selection function will automatically rearrange the argument pairs so that the recognized functions come first). The sections describing the individual group libraries in chapter Group Libraries tell you which functions are recognized by the selection function of that group library.

There is another function, called the example function that behaves similar to the selection function. Instead of returning a list of all groups with a certain set of properties it only returns one such group. The name of the example function is obtained by replacing All by One and stripping the s at the end of the name of the selection function.

    gap> OnePrimitiveGroup( DegreeOperation,           [1..10],
    >                       IsSimple,                  true,
    >                       IsCyclic,                  false,
    >                       NumberConjugacyClasses,    9 );
    A(7) 

The example function works just like the selection function. That means that all the above comments about the special functions that are recognized also apply to the example function.

Let us now look at the 2-groups library. It is accessed in the same way as the primitive groups library. There is an extraction function TwoGroup, a selection function AllTwoGroups, and an example function OneTwoGroup.

    gap> g := TwoGroup( 128, 5 );
    Group( a1, a2, a3, a4, a5, a6, a7 )
    gap> Size( g );
    128
    gap> NumberConjugacyClasses( g );
    80 

The groups are all displayed as Group( a1, a2, ..., an ), where 2^n is the size of the group.

    gap> AllTwoGroups( Size,   256,
    >                  Rank,   3,
    >                  pClass, 2 );
    [ Group( a1, a2, a3, a4, a5, a6, a7, a8 ),
      Group( a1, a2, a3, a4, a5, a6, a7, a8 ),
      Group( a1, a2, a3, a4, a5, a6, a7, a8 ),
      Group( a1, a2, a3, a4, a5, a6, a7, a8 ) ]
    gap> l := AllTwoGroups( Size,                              256,
    >                       Rank,                              3,
    >                       pClass,                            5,
    >                       g -> Length( DerivedSeries( g ) ), 4 );;
    gap> Length( l );
    28 

The selection and example function of the 2-groups library recognize Size, Rank, and pClass. Note that Rank and pClass are functions that can in fact only be used in this context, i.e., they can not be applied to arbitrary groups.

The following discussion is a bit technical and you can ignore it safely.

For very big group libraries, such as the 2-groups library, the groups (or their compact representations) are not stored on a single file. This is because this file would be very large and loading it would take a long time and a lot of main memory.

Instead the groups are stored on a small number of files (27 in the case of the 2-groups). The selection and example functions are careful to load only those files that may actually contain groups with the specified properties. For example in the above example the files containing the groups of size less than 256 are never loaded. In fact in the above example only one very small file is loaded.

When a file is loaded the selection and example functions also unload the previously loaded file. That means that they forget all the groups in this file again (except those selected of course). Thus even if the selection or example functions have to search through the whole group library, only a small part of the library is held in main memory at any time. In principle it should be possible to search the whole 2-groups library with as little as 2 MByte of main memory.

If you have sufficient main memory available you can explicitly load files from the 2-groups library with ReadTwo( filename ), e.g., Read( "twogp64" ) to load the file with the groups of size 64. Those files will then not be unloaded again. This will take up more main memory, but the selection and example function will work faster, because they do not have to load those files again each time they are needed.

In this section you have seen the basic groups library and the group libraries of primitive groups and 2-groups. You have seen how you can extract a single group from such a library with the extraction function. You have seen how you can select groups with certain properties with the selection and example function. Chapter Group Libraries tells you which other group libraries are available.

Previous Up Top Next
Index

GAP 3.4.4
April 1997