Math Solutions 1995 October

home *** CD-ROM | disk | FTP | other *** search

/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / doc / domain.tex < prev next >

Wrap

Text File | 1993-05-05 | 39.4 KB | 818 lines

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %A domain.tex GAP documentation Martin Schoenert %% %A @(#)$Id: domain.tex,v 3.8 1993/02/19 10:48:42 gap Exp $ %% %Y Copyright 1990-1992, Lehrstuhl D fuer Mathematik, RWTH Aachen, Germany %% %% This file describes domains, the concept, their functions and operations. %% %H $Log: domain.tex,v $ %H Revision 3.8 1993/02/19 10:48:42 gap %H adjustments in line length and spelling %H %H Revision 3.7 1993/02/18 16:34:21 felsch %H another example fixed %H %H Revision 3.6 1993/02/15 09:42:18 felsch %H examples fixed %H %H Revision 3.5 1993/02/10 20:48:39 martin %H fixed some examples %H %H Revision 3.4 1992/04/30 11:57:09 martin %H changed a few sentences to avoid bold non-roman fonts %H %H Revision 3.3 1992/04/06 12:43:02 martin %H fixed some more typos %H %H Revision 3.2 1992/04/02 21:06:23 martin %H changed *domain functions* to *set theoretic functions* %H %H Revision 3.1 1992/03/11 11:40:55 martin %H changed 'Representative' to 'RepresentativeOperation' in the example %H %H Revision 3.0 1991/12/27 16:10:27 martin %H initial revision under RCS %H %% \Chapter{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). This chapter describes how domains are represented in {\GAP} (see "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 "Dispatchers", "More about Dispatchers", and "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\"'. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{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"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Dispatchers}% \index{operations record}\index{record!operations}% \index{dispatcher functions}\index{default functions} 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. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{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 under <G> is very short, 'GroupOps.Orbit(<G>,)', which is the default function to compute an orbit, may be slightly more efficient than 'Orbit(<G>,)', which calls '<G>.operations.Orbit(<G>,)', which is the same as 'PermGroupOps.Orbit(<G>,)'. 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'). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{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'. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{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. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Elements}% \index{elements!of a domain} '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. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{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. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Membership Test for Domains}% \index{in!for domains}\index{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. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IsFinite}% \index{finiteness test!for domains} '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. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Size}% \index{size!of a domain} '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. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IsSubset}% \index{subset test!for domains} '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 of the proper set of elements of <D> (see "Elements" and "Set Functions for Sets"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Intersection}% \index{intersection!of domains} '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. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Union}% \index{union!of domains} '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. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Difference}% \index{set difference!of domains} '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. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Representative} \index{representative!of a domain} '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. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Random}% \index{random element!of a domain} '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"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %E Emacs . . . . . . . . . . . . . . . . . . . . . local Emacs variables %% %% Local Variables: %% mode: outline %% outline-regexp: "\\\\Chapter\\|\\\\Section" %% fill-column: 73 %% eval: (hide-body) %% End: %%