4 Domains

Domain is GAP's name for structured sets. The ring of Gaussian integers Z[I] is an example of a domain, the group D_{12} of symmetries of a regular hexahedron is another.

The GAP library predefines some domains. For example the ring of Gaussian integers is predefined as GaussianIntegers (see Gaussians) and the field of rationals is predefined as Rationals (see Rationals). Most domains are constructed by functions, which are called domain constructors. For example the group D_{12} is constructed by the construction Group( (1,2,3,4,5,6), (2,6)(3,5) ) (see Group) and the finite field with 16 elements is constructed by GaloisField( 16 ) (see GaloisField).

The first place where you need domains in GAP is the obvious one. Sometimes you simply want to talk about a domain. For example if you want to compute the size of the group D_{12}, you had better be able to represent this group in a way that the Size function can understand.

The second place where you need domains in GAP is when you want to be able to specify that an operation or computation takes place in a certain domain. For example suppose you want to factor 10 in the ring of Gaussian integers. Saying Factors( 10 ) will not do, because this will return the factorization in the ring of integers [ 2, 5 ]. To allow operations and computations to happen in a specific domain, Factors, and many other functions as well, accept this domain as optional first argument. Thus Factors( GaussianIntegers, 10 ) yields the desired result [ 1+E(4), 1-E(4), 2+E(4), 2-E(4) ].

Each domain in GAP belongs to one or more categories, which are simply sets of domains. The categories in which a domain lies determine the functions that are applicable to this domain and its elements. Examples of domains are rings (the functions applicable to a domain that is a ring are described in Rings), fields (see Fields), groups (see Groups), vector spaces (see Vector Spaces), and of course the category domains that contains all domains (the functions applicable to any domain are described in this chapter).

Domain Records), how functions that can be applied to different types of domains know how to solve a problem for each of those types (see An Example of a Computation in a Domain), how domains are compared (see Comparisons of Domains), and the set theoretic functions that can be applied to any domain (see Elements, Membership Test for Domains, IsFinite, Size, IsSubset, Intersection, Union, Difference, Random).

The functions described in this chapter are implemented in the file LIBNAME/"domain.g".

Subsections

  1. Domain Records
  2. Dispatchers
  3. More about Dispatchers
  4. An Example of a Computation in a Domain
  5. Domain
  6. Elements
  7. Comparisons of Domains
  8. Membership Test for Domains
  9. IsFinite
  10. Size
  11. IsSubset
  12. Intersection
  13. Union
  14. Difference
  15. Representative
  16. Random

4.1 Domain Records

Domains are represented by records (see Records), which are called domain records in the following. Which components need to be present, which may, and what those components hold, differs from category to category, and, to a smaller extent, from domain to domain. It is generally possible though to distinguish four types of components.

Each domain record has the component isDomain, which has the value true. Furthermore, most domains also have a component that specifies which category this domain belongs to. For example, each group has the component isGroup, holding the value true. Those components are called the category components of the domain record. A domain that only has the component isDomain is a member only of the category Domains and only the functions described in this chapter are applicable to such a domain.

Every domain record also contains enough information to identify uniquely the domain in the so called identification components. For example, for a group the domain record, called group record in this case, has a component called generators containing a system of generators (and also a component identity holding the identity element of the group, needed if the generator list is empty, as is the case for the trivial group).

Next the domain record holds all the knowledge GAP has about the domain, for example the size of the domain, in the so called knowledge components. Of course, the knowledge about a certain domain will usually increase as time goes by. For example, a group record may initially hold only the knowledge that the group is finite, but may end holding all kinds of knowledge, for example the derived series, the Sylow subgroups, etc.

Finally each domain record has a component, which is called its operations record (because it is the component with the name operations and it holds a record), that tells functions like Size how to compute this information for this domain. The exact mechanism is described later (see Dispatchers).

4.2 Dispatchers

In the previous section it was mentioned that domains are represented by domain records, and that each domain record has an operations record. This operations record is used by functions like Size to find out how to compute this information for the domain. Let us discuss this mechanism using the example of Size. Suppose you call Size with a domain D.

First Size tests whether D has a component called size, i.e., if D.size is bound. If it is, Size assumes that it holds the size of the domain and returns this value.

Let us suppose that this component has no assigned value. Then Size looks at the component D.operations, which must be a record. Size takes component D.operations.Size of this record, which must be a function. Size calls this function passing D as argument. If a domain record has no Size function in its operations record, an error is signalled.

Finally Size stores the value returned by D.operations.Size( D ) in the component D.size, where it is available for the next call of Size( D ).

Because functions like Size do little except dispatch to the function in the operations record they are called dispatcher functions.

Which function is called through this mechanism obviously depends on the domain and its operations record. In principle each domain could have its own Size function. In practice however this is not the case. For example all permutation groups share the operations record PermGroupOps so they all use the same Size function PermGroupOps.Size.

Note that in fact domains of the same type not only share the functions, in fact they share the operations record. So for example all permutation groups have the same operations record. This means that changing such a function for a domain D in the following way D.operations.function := new-function; will also change this function for all domains of the same type, even those that do not yet exist at the moment of the assignment and will only be constructed later. This is usually not desirable, since supposedly new-function uses some special properties of the domain D to work efficiently. We suggest therefore, that you use the following assignments instead:
D.operations := Copy( D.operations );
D.operations.function := new-function;.

Some domains do not provide a special Size function, either because no efficient method is known or because the author that implemented the domain simply was too lazy to write one. In those cases the domain inherits the default function, which is DomainOps.Size. Such inheritance is uncommon for the Size function, but rather common for the Union function.

4.3 More about Dispatchers

Usually you need not care about the mechanism described in the previous section. You just call the dispatcher functions like Size. They will call the function in the operations record, which is hopefully implementing an algorithm that is well suited for their domain, by using the structure of this domain.

There are three reasons why you might want to avoid calling the dispatcher function and call the dispatched to function directly.

The first reason is efficiency. The dispatcher functions don't do very much. They only check the types of their arguments, check if the requested information is already present, and dispatch to the appropriate function in the operations record. But sometimes, for example in the innermost loop of your algorithm, even this little is too much. In those cases you can avoid the overhead introduced by the dispatcher function by calling the function in the operations record directly. For example, you would use G.operations.Size(G) instead of Size(G).

The second reason is flexibility. Sometimes you do not want to call the function in the operations record, but another function that performs the same task, using a different algorithm. In that case you will call this different function. For example, if G is a permutation group, and the orbit of p under G is very short, GroupOps.Orbit(G,p), which is the default function to compute an orbit, may be slightly more efficient than Orbit(G,p), which calls G.operations.Orbit(G,p), which is the same as PermGroupOps.Orbit(G,p).

The third has to do with the fact that the dispatcher functions check for knowledge components like D.size or D.elements and also store their result in such components. For example, suppose you know that the result of a computation takes up quite some space, as is the case with Elements(D), and that you will never need the value again. In this case you would not want the dispatcher function to enter the value in the domain record, and therefore would call D.operations.Elements(D) directly. On the other hand you may not want to use the value in the domain record, because you mistrust it. In this case you should call the function in the operations record directly, e.g., you would use G.operations.Size(G) instead of Size(G) (and then compare the result with G.size).

4.4 An Example of a Computation in a Domain

This section contains an extended example to show you how a computation in a domain may use default and special functions to achieve its goal. Suppose you defined G, x, and y as follows.

    gap> G := SymmetricGroup( 8 );;
    gap> x := [ (2,7,4)(3,5), (1,2,6)(4,8) ];;
    gap> y := [ (2,5,7)(4,6), (1,5)(3,8,7) ];; 

Now you ask for an element of G that conjugates x to y, i.e., a permutation on 8 points that takes (2,7,4)(3,5) to (2,5,7)(4,6) and (1,2,6)(4,8) to (1,5)(3,8,7). This is done as follows (see RepresentativeOperation and Other Operations).

    gap> RepresentativeOperation( G, x, y, OnTuples );
    (1,8)(2,7)(3,4,5,6) 

Let us look at what happens step by step. First RepresentativeOperation is called. After checking the arguments it calls the function G.operations.RepresentativeOperation, which is the function SymmetricGroupOps.RepresentativeOperation, passing the arguments G, x, y, and OnTuples.

SymmetricGroupOps.RepresentativeOperation handles a lot of cases specially, but the operation on tuples of permutations is not among them. Therefore it delegates this problem to the function that it overlays, which is PermGroupOps.RepresentativeOperation.

PermGroupOps.RepresentativeOperation also does not handle this special case, and delegates the problem to the function that it overlays, which is the default function called GroupOps.RepresentativeOperation.

GroupOps.RepresentativeOperation views this problem as a general tuples problem, i.e., it does not care whether the points in the tuples are integers or permutations, and decides to solve it one step at a time. So first it looks for an element taking (2,7,4)(3,5) to (2,5,7)(4,6) by calling RepresentativeOperation( G, (2,7,4)(3,5), (2,5,7)(4,6) ).

RepresentativeOperation calls G.operations.RepresentativeOperation next, which is the function SymmetricGroupOps.RepresentativeOperation, passing the arguments G, (2,7,4)(3,5), and (2,5,7)(4,6).

SymmetricGroupOps.RepresentativeOperation can handle this case. It knows that G contains every permutation on 8 points, so it contains (3,4,7,5,6), which obviously does what we want, namely it takes x[1] to y[1]. We will call this element t.

Now GroupOps.RepresentativeOperation (see above) looks for an s in the stabilizer of x[1] taking x[2] to y[2]^(t^-1), since then for r=s*t we have x[1]^r = (x[1]^s)^t = x[1]^t = y[1] and also x[2]^r = (x[2]^s)^t = (y[2]^(t^-1))^t = y[2]. So the next step is to compute the stabilizer of x[1] in G. To do this it calls Stabilizer( G, (2,7,4)(3,5) ).

Stabilizer calls G.operations.Stabilizer, which is SymmetricGroupOps.Stabilizer, passing the arguments G and (2,7,4)(3,5). SymmetricGroupOps.Stabilizer detects that the second argument is a permutation, i.e., an element of the group, and calls Centralizer( G, (2,7,4)(3,5) ). Centralizer calls the function G.operations.Centralizer, which is SymmetricGroupOps.Centralizer, again passing the arguments G, (2,7,4)(3,5).

SymmetricGroupOps.Centralizer again knows how centralizers in symmetric groups look, and after looking at the permutation (2,7,4)(3,5) sharply for a short while returns the centralizer as Subgroup( G, [ (1,6), (1,6,8), (2,7,4), (3,5) ] ), which we will call S. Note that S is of course not a symmetric group, therefore SymmetricGroupOps.Subgroup gives it PermGroupOps as operations record and not SymmetricGroupOps.

As explained above GroupOps.RepresentativeOperation needs an element of S taking x[2] ((1,2,6)(4,8)) to y[2]^(t^-1) ((1,7)(4,6,8)). So RepresentativeOperation( S, (1,2,6)(4,8), (1,7)(4,6,8) ) is called. RepresentativeOperation in turn calls the function S.operations.RepresentativeOperation, which is, since S is a permutation group, the function PermGroupOps.RepresentativeOperation, passing the arguments S, (1,2,6)(4,8), and (1,7)(4,6,8).

PermGroupOps.RepresentativeOperation detects that the points are permutations and and performs a backtrack search through S. It finds and returns (1,8)(2,4,7)(3,5), which we call s.

Then GroupOps.RepresentativeOperation returns r = s*t = (1,8)(2,7)(3,6)(4,5), and we are done.

In this example you have seen how functions use the structure of their domain to solve a problem most efficiently, for example SymmetricGroupOps.RepresentativeOperation but also the backtrack search in PermGroupOps.RepresentativeOperation, how they use other functions, for example SymmetricGroupOps.Stabilizer called Centralizer, and how they delegate cases which they can not handle more efficiently back to the function they overlaid, for example SymmetricGroupOps.RepresentativeOperation delegated to PermGroupOps.RepresentativeOperation, which in turn delegated to to the function GroupOps.RepresentativeOperation.

4.5 Domain

Domain( list )

Domain returns a domain that contains all the elements in list and that knows how to make the ring, field, group, or vector space that contains those elements.

Note that the domain returned by Domain need in general not be a ring, field, group, or vector space itself. For example if passed a list of elements of finite fields Domain will return the domain FiniteFieldElements. This domain contains all finite field elements, no matter of which characteristic. This domain has a function FiniteFieldElementsOps.Field that knows how to make a finite field that contains the elements in list. This function knows that all elements must have the same characteristic for them to lie in a common field.

    gap> D := Domain( [ Z(4), Z(8) ] );
    FiniteFieldElements
    gap> IsField( D );
    false
    gap> D.operations.Field( [ Z(4), Z(8) ] );
    GF(2^6) 

Domain is the only function in the whole GAP library that knows about the various types of elements. For example, when Norm is confronted by a field element z, it does not know what to do with it. So it calls F := DefaultField( [ z ] ) to get a field in which z lies, because this field (more precisely F.operations.Norm) will know better. However, DefaultField also does not know what to do with z. So it calls D := Domain( [ z ] ) to get a domain in which z lies, because it (more precisely D.operations.DefaultField) will know how to make a default field in which z lies.

4.6 Elements

Elements( D )

Elements returns the set of elements of the domain D. The set is returned as a new proper set, i.e., as a new sorted list without holes and duplicates (see Sets). D may also be a list, in which case the set of elements of this list is returned. An error is signalled if D is an infinite domain.

    gap> Elements( GaussianIntegers );
    Error, the ring <R> must be finite to compute its elements
    gap> D12 := Group( (2,6)(3,5), (1,2)(3,6)(4,5) );;
    gap> Elements( D12 );
    [ (), (2,6)(3,5), (1,2)(3,6)(4,5), (1,2,3,4,5,6), (1,3)(4,6),
      (1,3,5)(2,4,6), (1,4)(2,3)(5,6), (1,4)(2,5)(3,6), (1,5)(2,4),
      (1,5,3)(2,6,4), (1,6,5,4,3,2), (1,6)(2,5)(3,4) ] 

Elements remembers the set of elements in the component D.elements and will return a shallow copy (see ShallowCopy) next time it is called to compute the elements of D. If you want to avoid this, for example for a large domain, for which you know that you will not need the list of elements in the future, either unbind (see Unbind) D.elements or call D.operation.Elements(D) directly.

Since there is no general method to compute the elements of a domain the default function DomainOps.Elements just signals an error. This default function is overlaid for each special finite domain. In fact, implementors of domains, must implement this function for new domains, since it is, together with IsFinite (see IsFinite) the most basic function for domains, used by most of the default functions in the domain package.

In general functions that return a set of elements are free, in fact encouraged, to return a domain instead of the proper set of elements. For one thing this allows to keep the structure, for another the representation by a domain record is usually more space efficient. Elements must not do this, its only purpose is to create the proper set of elements.

4.7 Comparisons of Domains

D = E
D < E

= evaluates to true if the two domains D and E are equal, to false otherwise. < evaluates to true if the two domains D and E are different and to false if they are equal.

Two domains are considered equal if and only if the sets of their elements as computed by Elements (see Elements) are equal. Thus, in general = behaves as if each domain operand were replaced by its set of elements. Except that = will also sometimes, but not always, work for infinite domains, for which it is of course difficult to compute the set of elements. Note that this implies that domains belonging to different categories may well be equal. As a special case of this, either operand may also be a proper set, i.e., a sorted list without holes or duplicates (see Set), and the result will be true if and only if the set of elements of the domain is, as a set, equal to the set. It is also possible to compare a domain with something else that is not a domain or a set, but the result will of course always be false in this case.

    gap> GaussianIntegers = D12;
    false    # {\GAP} knows that those domains cannot be equal because
             # 'GaussianIntegers' is infinite and 'D12' is finite
    gap> GaussianIntegers = Integers;
    false    # {\GAP} knows how to compare those two rings
    gap> GaussianIntegers = Rationals;
    Error, sorry, cannot compare the infinite domains <D> and <E>
    gap> D12 = Group( (2,6)(3,5), (1,2)(3,6)(4,5) );
    true
    gap> D12 = [(),(2,6)(3,5),(1,2)(3,6)(4,5),(1,2,3,4,5,6),(1,3)(4,6),
    >           (1,3,5)(2,4,6),(1,4)(2,3)(5,6),(1,4)(2,5)(3,6),
    >           (1,5)(2,4),(1,5,3)(2,6,4),(1,6,5,4,3,2),(1,6)(2,5)(3,4)];
    true
    gap> D12 = [(1,6,5,4,3,2),(1,6)(2,5)(3,4),(1,5,3)(2,6,4),(1,5)(2,4),
    >           (1,4)(2,5)(3,6),(1,4)(2,3)(5,6),(1,3,5)(2,4,6),(1,3)(4,6),
    >           (1,2,3,4,5,6),(1,2)(3,6)(4,5),(2,6)(3,5),()];
    false    # since the left operand behaves as a set
             # while the right operand is not a set 

The default function DomainOps.'=' checks whether both domains are infinite. If they are, an error is signalled. Otherwise, if one domain is infinite, false is returned. Otherwise the sizes (see Size) of the domains are compared. If they are different, false is returned. Finally the sets of elements of both domains are computed (see Elements) and compared. This default function is overlaid by more special functions for other domains.

D < E
D <= E
D E
D = E

<, <=, , and = evaluate to true if the domain D is less than, less than or equal to, greater than, and greater than or equal to the domain E and to false otherwise.

A domain D is considered less than a domain E if and only if the set of elements of D is less than the set of elements of the domain E. Generally you may just imagine that each domain operand is replaced by the set of its elements, and that the comparison is performed on those sets (see Comparisons of Lists). This implies that, if you compare a domain with an object that is not a list or a domain, this other object will be less than the domain, except if it is a record, in which case it is larger than the domain (see Comparisons).

Note that < does not test whether the left domain is a subset of the right operand, even though it resembles the mathematical subset notation.

    gap> GaussianIntegers < Rationals;
    Error, sorry, cannot compare <E> with the infinite domain <D>
    gap> Group( (1,2), (1,2,3,4,5,6) ) < D12;
    true     # since '(5,6)', the second element of the left operand,
             # is less than '(2,6)(3,5)', the second element of 'D12'.
    gap> D12 < [(1,6,5,4,3,2),(1,6)(2,5)(3,4),(1,5,3)(2,6,4),(1,5)(2,4),
    >           (1,4)(2,5)(3,6),(1,4)(2,3)(5,6),(1,3,5)(2,4,6),(1,3)(4,6),
    >           (1,2,3,4,5,6),(1,2)(3,6)(4,5),(2,6)(3,5),()];
    true     # since '()', the first element of 'D12', is less than
             # '(1,6,5,4,3,2)', the first element of the right operand.
    gap> 17 < D12;
    true     # objects that are not lists or records are smaller
             # than domains, which behave as if they were a set 

The default function DomainOps.'<' checks whether either domain is infinite. If one is, an error is signalled. Otherwise the sets of elements of both domains are computed (see Elements) and compared. This default function is only very seldom overlaid by more special functions for other domains. Thus the operators <, <=, , and = are quite expensive and their use should be avoided if possible.

4.8 Membership Test for Domains

elm in D

in returns true if the element elm, which may be an object of any type, lies in the domain D, and false otherwise.

    gap> 13 in GaussianIntegers;
    true
    gap> GaussianIntegers in GaussianIntegers;
    false
    gap> (1,2) in D12;
    false
    gap> (1,2)(3,6)(4,5) in D12;
    true 

The default function for domain membership tests is DomainOps.'in', which computes the set of elements of the domain with the function Elements (see Elements) and tests whether elm lies in this set. Special domains usually overlay this function with more efficient membership tests.

4.9 IsFinite

IsFinite( D )

IsFinite returns true if the domain D is finite and false otherwise. D may also be a proper set (see Set), in which case the result is of course always true.

    gap> IsFinite( GaussianIntegers );
    false
    gap> IsFinite( D12 );
    true 

The default function DomainOps.IsFinite just signals an error, since there is no general method to determine whether a domain is finite or not. This default function is overlaid for each special domain. In fact, implementors of domains must implement this function for new domains, since it is, together with Elements (see Elements), the most basic function for domains, used by most of the default functions in the domain package.

4.10 Size

Size( D )

Size returns the size of the domain D. If D is infinite, Size returns the string "infinity". D may also be a proper set (see Set), in which case the result is the length of this list. Size will, however, signal an error if D is a list that is not a proper set, i.e., that is not sorted, or has holes, or contains duplicates.

    gap> Size( GaussianIntegers );
    "infinity"
    gap> Size( D12 );
    12 

The default function to compute the size of a domain is DomainOps.Size, which computes the set of elements of the domain with the function Elements (see Elements) and returns the length of this set. This default function is overlaid in practically every domain.

4.11 IsSubset

IsSubset( D, E )

IsSubset returns true if the domain E is a subset of the domain D and false otherwise.

E is considered a subset of D if and only if the set of elements of E is as a set a subset of the set of elements of D (see Elements and Set Functions for Sets). That is IsSubset behaves as if implemented as IsSubsetSet( Elements(D), Elements(E) ), except that it will also sometimes, but not always, work for infinite domains, and that it will usually work much faster than the above definition. Either argument may also be a proper set.

    gap> IsSubset( GaussianIntegers, [1,E(4)] );
    true
    gap> IsSubset( GaussianIntegers, Rationals );
    Error, sorry, cannot compare the infinite domains <D> and <E>
    gap> IsSubset( Group( (1,2), (1,2,3,4,5,6) ), D12 );
    true
    gap> IsSubset( D12, [ (), (1,2)(3,4)(5,6) ] );
    false 

The default function DomainOps.IsSubset checks whether both domains are infinite. If they are it signals an error. Otherwise if the E is infinite it returns false. Otherwise if D is infinite it tests if each element of E is in D (see Membership Test for Domains). Otherwise it tests whether the proper set of elements of E is a subset Set Functions for Sets).

4.12 Intersection

Intersection( D1, D2... )
Intersection( list )

In the first form Intersection returns the intersection of the domains D1, D2, etc. In the second form list must be a list of domains and Intersection returns the intersection of those domains. Each argument D or element of list respectively may also be an arbitrary list, in which case Intersection silently applies Set (see Set) to it first.

The result of Intersection is the set of elements that lie in every of the domains D1, D2, etc. Functions called by the dispatcher function Intersection however, are encouraged to keep as much structure as possible. So if D1 and D2 are elements of a common category and if this category is closed under taking intersections, then the result should be a domain lying in this category too. So for example the intersection of permutation groups will again be a permutation group.

    gap> Intersection( CyclotomicField(9), CyclotomicField(12) );
    CF(3)    # 'CF' is a shorthand for 'CyclotomicField'
             # this is one of the rare cases where the intersection
             # of two infinite domains works
    gap> Intersection( GaussianIntegers, Rationals );
    Error, sorry, cannot intersect infinite domains <D> and <E>
    gap> Intersection( D12, Group( (1,2), (1,2,3,4,5) ) );
    Group( (1,5)(2,4) )
    gap> Intersection( D12, [ (1,3)(4,6), (1,2)(3,4) ] );
    [ (1,3)(4,6) ]    # note that the second argument is not a set
    gap> Intersection( D12, [ (), (1,2)(3,4), (1,3)(4,6), (1,4)(5,6) ] );
    [ (), (1,3)(4,6) ]    # although the result is mathematically a
                          # group it is returned as a proper set
                          # because the second argument was not a group
    gap> Intersection( [2,4,6,8,10], [3,6,9,12,15], [5,10,15,20,25] );
    [  ]    # two or more domains or sets as arguments are legal
    gap> Intersection( [ [1,2,4], [2,3,4], [1,3,4] ] );
    [ 4 ]    # or a list of domains or sets
    gap> Intersection( [ ] );
    Error, List Element: <list>[1] must have a value 

The dispatcher function (see Dispatchers) Intersection is slightly different from other dispatcher functions. It does not simply call the function in the operations record passings its arguments. Instead it loops over its arguments (or the list of domains or sets) and calls the function in the operations record repeatedly, and passes each time only two domains. This obviously makes writing the function for the operations record simpler.

The default function DomainOps.Intersection checks whether both domains are infinite. If they are it signals an error. Otherwise, if one of the domains is infinite it loops over the elements of the other domain, and tests for each element whether it lies in the infinite domain. If both domains are finite it computes the proper sets of elements of both and intersects them (see Elements and Set Functions for Sets). This default method is overlaid by more special functions for most other domains. Those functions usually are faster and keep the structure of the domains if possible.

4.13 Union

Union( D1, D2... )
Union( list )

In the first form Union returns the union of the domains D1, D2, etc. In the second form list must be a list of domains and Union returns the union of those domains. Each argument D or element of list respectively may also be an arbitrary list, in which case Union silently applies Set (see Set) to it first.

The result of Union is the set of elements that lie in any the domains D1, D2, etc. Functions called by the dispatcher function Union however, are encouraged to keep as much structure as possible. However, currently GAP does not support any category that is closed under taking unions except the category of all domains. So the only case that structure will be kept is when one argument D or element of list respectively is a superset of all the other arguments or elements of list.

    gap> Union( GaussianIntegers, Rationals );
    Error, sorry, cannot unite <E> with the infinite domain <D>
    gap> Union( D12, Group( (1,2), (1,2,3) ) );
    [ (), (2,3), (2,6)(3,5), (1,2), (1,2)(3,6)(4,5), (1,2,3),
      (1,2,3,4,5,6), (1,3,2), (1,3), (1,3)(4,6), (1,3,5)(2,4,6),
      (1,4)(2,3)(5,6), (1,4)(2,5)(3,6), (1,5)(2,4), (1,5,3)(2,6,4),
      (1,6,5,4,3,2), (1,6)(2,5)(3,4) ]
    gap> Union( [2,4,6,8,10], [3,6,9,12,15], [5,10,15,20,25] );
    [ 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 20, 25 ]
        # two or more domains or sets as arguments are legal
    gap> Union( [ [1,2,4], [2,3,4], [1,3,4] ] );
    [ 1, 2, 3, 4 ]    # or a list of domains or sets
    gap> Union( [ ] );
    [  ] 

The dispatcher function (see Dispatchers) Union is slightly different from other dispatcher functions. It does not simply call the function in the operations record passings its arguments. Instead it loops over its arguments (or the list of domains or sets) and calls the function in the operations record repeatedly, and passes each time only two domains. This obviously makes writing the function for the operations record simpler.

The default function DomainOps.Union checks whether either domain is infinite. If one is it signals an error. If both domains are finite it computes the proper sets of elements of both and unites them (see Elements and Set Functions for Sets). This default method is overlaid by more special functions for some other domains. Those functions usually are faster.

4.14 Difference

Difference( D, E )

Difference returns the set difference of the domains D and E. Either argument may also be an arbitrary list, in which case Difference silently applies Set (see Set) to it first.

The result of Difference is the set of elements that lie in D but not in E. Note that E need not be a subset of D. The elements of E, however, that are not element of D play no role for the result.

    gap> Difference( D12, [(),(1,2,3,4,5,6),(1,3,5)(2,4,6),
    >                    (1,4)(2,5)(3,6),(1,6,5,4,3,2),(1,5,3)(2,6,4)] );
    [ (2,6)(3,5), (1,2)(3,6)(4,5), (1,3)(4,6), (1,4)(2,3)(5,6),
      (1,5)(2,4), (1,6)(2,5)(3,4) ] 

The default function DomainOps.Difference checks whether D is infinite. If it is it signals an error. Otherwise Difference computes the proper sets of elements of D and E and returns the difference of those sets (see Elements and SubtractSet). This default function is currently not overlaid for any domain.

4.15 Representative

Representative( D )

Representative returns a representative of the domain D.

The existence of a representative, and the exact definition of what a representative is, depends on the category of D. The representative should be an element that, within a given context, identifies the domain D. For example if D is a cyclic group, its representative would be a generator of D, or if D is a coset, its representative would be an arbitrary element of the coset.

Note that Representative is pretty free in choosing a representative if there are several. It is not even guaranteed that Representative returns the same representative if it is called several times for one domain. Thus the main difference between Representative and Random (see Random) is that Representative is free to choose a value that is cheap to compute, while Random must make an effort to randomly distribute its answers.

    gap> C := Coset( Subgroup( G, [(1,4)(2,5)(3,6)] ), (1,6,5,4,3,2) );;
    gap> Representative( C );
    (1,3,5)(2,4,6) 

Representative first tests whether the component D.representative is bound. If the field is bound it returns its value. Otherwise it calls D.operations.Representative( D ), remembers the returned value in D.representative, and returns it.

The default function called this way is DomainOps.Representative, which simply signals an error, since there is no default way to find a representative.

4.16 Random

Random( D )

Random returns a random element of the domain D. The distribution of elements returned by Random depends on the domain D. For finite domains all elements are usually equally likely. For infinite domains some reasonable distribution is used. See the chapters of the various domains to find out which distribution is being used.

    gap> Random( GaussianIntegers );
    1-4*E(4)
    gap> Random( GaussianIntegers );
    1+2*E(4)
    gap> Random( D12 );
    ()
    gap> Random( D12 );
    (1,4)(2,5)(3,6) 

The default function for random selection is DomainOps.Random, which computes the set of elements using Elements and selects a random element of this list using RandomList (see RandomList for a description of the pseudo random number generator used). This default function can of course only be applied to finite domains. It is overlaid by other functions for most other domains.

All random functions called this way rely on the low level random number generator provided by RandomList (see RandomList).

Previous Up Next
Index

GAP 3.4.4
April 1997