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