1.23 About Domains and Categories

Domain is GAP's name for structured sets. We already saw examples of domains in the previous sections. For example, the groups s8 and a8 in sections About Groups and About Operations of Groups are domains. Likewise the fields in section About Fields are domains. Categories are sets of domains. For example, the set of all groups forms a category, as does the set of all fields.

In those sections we treated the domains as black boxes. They were constructed by special functions such as Group and GaloisField, and they could be passed as arguments to other functions such as Size and Orbits.

In this section we will also treat domains as black boxes. We will describe how domains are created in general and what functions are applicable to all domains. Next we will show how domains with the same structure are grouped into categories and will give an overview of the categories that are available. Then we will discuss how the organization of the GAP library around the concept of domains and categories is reflected in this manual. In a later section we will open the black boxes and give an overview of the mechanism that makes all this work (see About the Implementation of Domains).

The first thing you must know is how you can obtain domains. You have basically three possibilities. You can use the domains that are predefined in the library, you can create new domains with domain constructors, and you can use the domains returned by many library functions. We will now discuss those three possibilities in turn.

The GAP library predefines some domains. That means that there is a global variable whose value is this domain. The following example shows some of the more important predefined domains.

    gap> Integers;
    Integers    # the ring of all integers
    gap> Size( Integers );
    "infinity"
    gap> GaussianRationals;
    GaussianRationals    # the field of all Gaussian
    gap> (1/2+E(4)) in GaussianRationals;
    true    # 'E(4)' is {\GAP}\'s name for the complex root of -1
    gap> Permutations;
    Permutations    # the domain of all permutations 

Note that GAP prints those domains using the name of the global variable.

You can create new domains using domain constructors such as Group, Field, etc. A domain constructor is a function that takes a certain number of arguments and returns the domain described by those arguments. For example, Group takes an arbitrary number of group elements (of the same type) and returns the group generated by those elements.

    gap> gf16 := GaloisField( 16 );
    GF(2^4)    # the finite field with 16 elements
    gap> Intersection( gf16, GaloisField( 64 ) );
    GF(2^2)
    gap> a5 := Group( (1,2,3), (3,4,5) );
    Group( (1,2,3), (3,4,5) )    # the alternating group on 5 points
    gap> Size( a5 );
    60 

Again GAP prints those domains using more or less the expression that you entered to obtain the domain.

As with groups (see About Groups) a name can be assigned to an arbitrary domain D with the assignment D.name := string;, and GAP will use this name from then on in the output.

Many functions in the GAP library return domains. In the last example you already saw that Intersection returned a finite field domain. Below are more examples.

    gap> GaloisGroup( gf16 );
    Group( FrobeniusAutomorphism( GF(2^4) ) )
    gap> SylowSubgroup( a5, 2 );
    Subgroup( Group( (1,2,3), (3,4,5) ), [ (2,4)(3,5), (2,3)(4,5) ] ) 

The distinction between domain constructors and functions that return domains is a little bit arbitrary. It is also not important for the understanding of what follows. If you are nevertheless interested, here are the principal differences. A constructor performs no computation, while a function performs a more or less complicated computation. A constructor creates the representation of the domain, while a function relies on a constructor to create the domain. A constructor knows the dirty details of the domain's representation, while a function may be independent of the domain's representation. A constructor may appear as printed representation of a domain, while a function usually does not.

After showing how domains are created, we will now discuss what you can do with domains. You can assign a domain to a variable, put a domain into a list or into a record, pass a domain as argument to a function, and return a domain as result of a function. In this regard there is no difference between an integer value such as 17 and a domain such as Group( (1,2,3), (3,4,5) ). Of course many functions will signal an error when you call them with domains as arguments. For example, Gcd does not accept two groups as arguments, because they lie in no Euclidean ring.

There are some functions that accept domains of any type as their arguments. Those functions are called the set theoretic functions. The full list of set theoretic functions is given in chapter Domains.

Above we already used one of those functions, namely Size. If you look back you will see that we applied Size to the domain Integers, which is a ring, and the domain a5, which is a group. Remember that a domain was a structured set. The size of the domain is the number of elements in the set. Size returns this number or the string "infinity" if the domain is infinite. Below are more examples.

    gap> Size( GaussianRationals );
    "infinity"    # this string is returned for infinite domains
    gap> Size( SylowSubgroup( a5, 2 ) );
    4 

IsFinite( D ) returns true if the domain D is finite and false otherwise. You could also test if a domain is finite using Size( D ) < "infinity" (GAP evaluates n < "infinity" to true for any number n). IsFinite is more efficient. For example, if D is a permutation group, IsFinite( D ) can immediately return true, while Size( D ) may take quite a while to compute the size of D.

The other function that you already saw is Intersection. Above we computed the intersection of the field with 16 elements and the field with 64 elements. The following example is similar.

    gap> Intersection( a5, Group( (1,2), (1,2,3,4) ) );
    Group( (2,3,4), (1,2)(3,4) )    # alternating group on 4 points 

In general Intersection tries to return a domain. In general this is not possible however. Remember that a domain is a structured set. If the two domain arguments have different structure the intersection may not have any structure at all. In this case Intersection returns the result as a proper set, i.e., as a sorted list without holes and duplicates. The following example shows such a case. ConjugacyClass returns the conjugacy class of (1,2,3,4,5) in the alternating group on 6 points as a domain. If we intersect this class with the symmetric group on 5 points we obtain a proper set of 12 permutations, which is only one half of the conjugacy class of 5 cycles in s5.

    gap> a6 := Group( (1,2,3), (2,3,4,5,6) );
    Group( (1,2,3), (2,3,4,5,6) )
    gap> class := ConjugacyClass( a6, (1,2,3,4,5) );
    ConjugacyClass( Group( (1,2,3), (2,3,4,5,6) ), (1,2,3,4,5) )
    gap> Size( class );
    72
    gap> s5 := Group( (1,2), (2,3,4,5) );
    Group( (1,2), (2,3,4,5) )
    gap> Intersection( class, s5 );
    [ (1,2,3,4,5), (1,2,4,5,3), (1,2,5,3,4), (1,3,5,4,2), (1,3,2,5,4),
      (1,3,4,2,5), (1,4,3,5,2), (1,4,5,2,3), (1,4,2,3,5), (1,5,4,3,2),
      (1,5,2,4,3), (1,5,3,2,4) ] 

You can intersect arbitrary domains as the following example shows.

    gap> Intersection( Integers, a5 );
    [  ]    # the empty set 

Note that we optimized Intersection for typical cases, e.g., computing the intersection of two permutation groups, etc. The above computation is done with a very simple--minded method, all elements of a5 are listed (with Elements, described below), and for each element Intersection tests whether it lies in Integers (with in, described below). So the same computation with the alternating group on 10 points instead of a5 will probably exhaust your patience.

Just as Intersection returns a proper set occasionally, it also accepts proper sets as arguments. Intersection also takes an arbitrary number of arguments. And finally it also accepts a list of domains or sets to intersect as single argument.

    gap> Intersection( a5, [ (1,2), (1,2,3), (1,2,3,4), (1,2,3,4,5) ] );
    [ (1,2,3), (1,2,3,4,5) ]
    gap> Intersection( [2,4,6,8,10], [3,6,9,12,15], [5,10,15,20,25] );
    [  ]
    gap> Intersection( [ [1,2,4], [2,3,4], [1,3,4] ] );
    [ 4 ] 

The function Union is the obvious counterpart of Intersection. Note that Union usually does not return a domain. This is because the union of two domains, even of the same type, is usually not again a domain of that type. For example, the union of two subgroups is a subgroup if and only if one of the subgroups is a subset of the other. Of course this is exactly the reason why Union is less important than Intersection in algebra.

Because domains are structured sets there ought to be a membership test that tests whether an object lies in this domain or not. This is not implemented by a function, instead the operator in is used. elm in D returns true if the element elm lies in the domain D and false otherwise. We already used the in operator above when we tested whether 1/2 + E(4) lies in the domain of Gaussian integers.

    gap> (1,2,3) in a5;
    true
    gap> (1,2) in a5;
    false
    gap> (1,2,3,4,5,6,7) in a5;
    false
    gap> 17 in a5;
    false    # of course an integer does not lie in a permutation group
    gap> a5 in a5;
    false 

As you can see in the last example, in only implements the membership test. It does not allow you to test whether a domain is a subset of another domain. For such tests the function IsSubset is available.

    gap> IsSubset( a5, a5 );
    true
    gap> IsSubset( a5, Group( (1,2,3) ) );
    true
    gap> IsSubset( Group( (1,2,3) ), a5 );
    false 

In the above example you can see that IsSubset tests whether the second argument is a subset of the first argument. As a general rule GAP library functions take as first arguments those arguments that are in some sense larger or more structured.

Suppose that you want to loop over all elements of a domain. For example, suppose that you want to compute the set of element orders of elements in the group a5. To use the for loop you need a list of elements in the domain D, because for var in D do statements od will not work. The function Elements does exactly that. It takes a domain D and returns the proper set of elements of D.

    gap> Elements( Group( (1,2,3), (2,3,4) ) );
    [ (), (2,3,4), (2,4,3), (1,2)(3,4), (1,2,3), (1,2,4), (1,3,2),
      (1,3,4), (1,3)(2,4), (1,4,2), (1,4,3), (1,4)(2,3) ]
    gap> ords := [];;
    gap> for elm  in Elements( a5 )  do
    >        Add( ords, Order( a5, elm ) );
    >    od;
    gap> Set( ords );
    [ 1, 2, 3, 5 ]
    gap> Set( List( Elements( a5 ), elm -> Order( a5, elm ) ) );
    [ 1, 2, 3, 5 ]    # an easier way to compute the set of orders 

Of course, if you apply Elements to an infinite domain, Elements will signal an error. It is also not a good idea to apply Elements to very large domains because the list of elements will take much space and computing this large list will probably exhaust your patience.

    gap> Elements( GaussianIntegers );
    Error, the ring <R> must be finite to compute its elements in
    D.operations.Elements( D ) called from
    Elements( GaussianIntegers ) called from
    main loop
    brk> quit;

There are a few more set theoretic functions. See chapter Domains for a complete list.

All the set theoretic functions treat the domains as if they had no structure. Now a domain is a structured set (excuse us for repeating this again and again, but it is really important to get this across). If the functions ignore the structure than they are effectively viewing a domain only as the set of elements.

In fact all set theoretic functions also accept proper sets, i.e., sorted lists without holes and duplicates as arguments (we already mentioned this for Intersection). Also set theoretic functions may occasionally return proper sets instead of domains as result.

This equivalence of a domain and its set of elements is particularly important for the definition of equality of domains. Two domains D and E are equal (in the sense that D = E evaluates to true) if and only if the set of elements of D is equal to the set of elements of E (as returned by Elements( D ) and Elements( E )). As a special case either of the operands of = may also be a proper set, and the value is true if this set is equal to the set of elements of the domain.

    gap> a4 := Group( (1,2,3), (2,3,4) );
    Group( (1,2,3), (2,3,4) )
    gap> elms := Elements( a4 );
    [ (), (2,3,4), (2,4,3), (1,2)(3,4), (1,2,3), (1,2,4), (1,3,2),
      (1,3,4), (1,3)(2,4), (1,4,2), (1,4,3), (1,4)(2,3) ]
    gap> elms = a4;
    true 

However the following example shows that this does not imply that all functions return the same answer for two domains (or a domain and a proper set) that are equal. This is because those function may take the structure into account.

    gap> IsGroup( a4 );
    true
    gap> IsGroup( elms );
    false
    gap> Intersection( a4, Group( (1,2), (1,2,3) ) );
    Group( (1,2,3) )
    gap> Intersection( elms, Group( (1,2), (1,2,3) ) );
    [ (), (1,2,3), (1,3,2) ]    # this is not a group
    gap> last = last2;
    true                        # but it is equal to the above result
    gap> Centre( a4 );
    Subgroup( Group( (1,2,3), (2,3,4) ), [  ] )
    gap> Centre( elms );
    Error, <struct> must be a record in
    Centre( elms ) called from
    main loop
    brk> quit;

Generally three things may happen if you have two domains D and E that are equal but have different structure (or a domain D and a set E that are equal). First a function that tests whether a domain has a certain structure may return true for D and false for E. Second a function may return a domain for D and a proper set for E. Third a function may work for D and fail for E, because it requires the structure.

A slightly more complex example for the second case is the following.

    gap> v4 := Subgroup( a4, [ (1,2)(3,4), (1,3)(2,4) ] );
    Subgroup( Group( (1,2,3), (2,3,4) ), [ (1,2)(3,4), (1,3)(2,4) ] )
    gap> v4.name := "v4";;
    gap> rc := v4 * (1,2,3);
    (v4*(2,4,3))
    gap> lc := (1,2,3) * v4;
    ((1,2,3)*v4)
    gap> rc = lc;
    true
    gap> rc * (1,3,2);
    (v4*())
    gap> lc * (1,3,2);
    [ (1,3)(2,4), (), (1,2)(3,4), (1,4)(2,3) ]
    gap> last = last2;
    false 

The two domains rc and lc (yes, cosets are domains too) are equal, because they have the same set of elements. However if we multiply both with (1,3,2) we obtain the trivial right coset for rc and a list for lc. The result for lc is not a proper set, because it is not sorted, therefore = evaluates to false. (For the curious. The multiplication of a left coset with an element from the right will generally not yield another coset, i.e., nothing that can easily be represented as a domain. Thus to multiply lc with (1,3,2) GAP first converts lc to the set of its elements with Elements. But the definition of multiplication requires that a list l multiplied by an element e yields a new list n such that each element n[i] in the new list is the product of the element l[i] at the same position of the operand list l with e.)

Note that the above definition only defines what the result of the equality comparison of two domains D and E should be. It does not prescribe that this comparison is actually performed by listing all elements of D and E. For example, if D and E are groups, it is sufficient to check that all generators of D lie in E and that all generators of E lie in D. If GAP would really compute the whole set of elements, the following test could not be performed on any computer.

    gap> Group( (1,2), (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18) )
    > = Group( (17,18), (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18) );
    true 

If we could only apply the set theoretic functions to domains, domains would be of little use. Luckily this is not so. We already saw that we could apply GaloisGroup to the finite field with 16 elements, and SylowSubgroup to the group a5. But those functions are not applicable to all domains. The argument of GaloisGroup must be a field, and the argument of SylowSubgroup must be a group.

A category is a set of domains. So we say that the argument of GaloisGroup must be an element of the category of fields, and the argument of SylowSubgroup must be an element of the category of groups. The most important categories are rings, fields, groups, and vector spaces. Which category a domain belongs to determines which functions are applicable to this domain and its elements. We want to emphasize the each domain belongs to one and only one category. This is necessary because domains in different categories have, sometimes incompatible, representations.

Note that the categories only exist conceptually. That means that there is no GAP object for the categories, e.g., there is no object Groups. For each category there exists a function that tests whether a domain is an element of this category.

    gap> IsRing( gf16 );
    false
    gap> IsField( gf16 );
    true
    gap> IsGroup( gf16 );
    false
    gap> IsVectorSpace( gf16 );
    false 

Note that of course mathematically the field gf16 is also a ring and a vector space. However in GAP a domain can only belong to one category. So a domain is conceptually a set of elements with one structure, e.g., a field structure. That the same set of elements may also support a different structure, e.g., a ring or vector space structure, can not be represented by this domain. So you need a different domain to represent this different structure. (We are planning to add functions that changes the structure of a domain, e.g. AsRing( field ) should return a new domain with the same elements as field but with a ring structure.)

Domains may have certain properties. For example a ring may be commutative and a group may be nilpotent. Whether a domain has a certain property Property can be tested with the function IsProperty.

    gap> IsCommutativeRing( GaussianIntegers );
    true
    gap> IsNilpotent( a5 );
    false 

There are also similar functions that test whether a domain (especially a group) is represented in a certain way. For example IsPermGroup tests whether a group is represented as a permutation group.

    gap> IsPermGroup( a5 );
    true
    gap> IsPermGroup( a4 / v4 );
    false    # 'a4 / v4' is represented as a generic factor group 

There is a slight difference between a function such as IsNilpotent and a function such as IsPermGroup. The former tests properties of an abstract group and its outcome is independent of the representation of that group. The latter tests whether a group is given in a certain representation.

This (rather philosophical) issue is further complicated by the fact that sometimes representations and properties are not independent. This is especially subtle with IsSolvable (see IsSolvable) and IsAgGroup (see IsAgGroup). IsSolvable tests whether a group G is solvable. IsAgGroup tests whether a group G is represented as a finite polycyclic group, i.e., by a finite presentation that allows to Finite Polycyclic Groups). Of course every finite polycyclic group is solvable, so IsAgGroup( G ) implies IsSolvable( G ). On the other hand IsSolvable( G ) does not imply IsAgGroup( G ), because, even though each solvable group can be represented as a finite polycyclic group, it need not, e.g., it could also be represented as a permutation group.

The organization of the manual follows the structure of domains and categories.

After the description of the programming language and the environment chapter Domains describes the domains and the functions applicable to all domains.

Next come the chapters that describe the categories rings, fields, groups, and vector spaces.

The remaining chapters describe GAP's data--types and the domains one can make with those elements of those data-types. The order of those chapters roughly follows the order of the categories. The data--types whose elements form rings and fields come first (e.g., integers and finite fields), followed by those whose elements form groups (e.g., permutations), and so on. The data--types whose elements support little or no algebraic structure come last (e.g., booleans). In some cases there may be two chapters for one data--type, one describing the elements and the other describing the domains made with those elements (e.g., permutations and permutation groups).

The GAP manual not only describes what you can do, it also gives some hints how GAP performs its computations. However, it can be tricky to find those hints. The index of this manual can help you.

Suppose that you want to intersect two permutation groups. If you read the section that describes the function Intersection (see Intersection) you will see that the last paragraph describes the default method used by Intersection. Such a last paragraph that describes the default method is rather typical. In this case it says that Intersection computes the proper set of elements of both domains and intersect them. It also says that this method is often overlaid with a more efficient one. You wonder whether this is the case for permutation groups. How can you find out? Well you look in the index under Intersection. There you will find a reference Intersection, for permutation groups to section Set Functions for Permutation Groups (see Set Functions for Permutation Groups). This section tells you that Intersection uses a backtrack for permutation groups (and cites a book where you can find a description of the backtrack).

Let us now suppose that you intersect two factor groups. There is no reference in the index for Intersection, for factor groups. But there is a reference for Intersection, for groups to the section Set Functions for Groups (see Set Functions for Groups). Since this is the next best thing, look there. This section further directs you to the section Intersection for Groups (see Intersection for Groups). This section finally tells you that Intersection computes the intersection of two groups G and H as the stabilizer in G of the trivial coset of H under the operation of G on the right cosets of H.

In this section we introduced domains and categories. You have learned that a domain is a structured set, and that domains are either predefined, created by domain constructors, or returned by library functions. You have seen most functions that are applicable to all domains. Those functions generally ignore the structure and treat a domain as the set of its elements. You have learned that categories are sets of domains, and that the category a domain belongs to determines which functions are applicable to this domain.

More information about domains can be found in chapter Domains. Chapters Rings, Fields, Groups, and Vector Spaces define the About the Implementation of Domains opens that black boxes and shows how all this works.

Previous Up Top Next
Index

GAP 3.4.4
April 1997