# 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.

GAP 3.4.4
April 1997