In this chapter, we give a –hopefully typical– example of extending GAP by new objects with prescribed arithmetic operations (for a simple approach that may be useful to get started though does not permit to exploit all potential features, see also ArithmeticElementCreator (80.9-1)).
A usual procedure in mathematics is the definition of new operations for given objects; here are a few typical examples. The Lie bracket defines an interesting new multiplicative structure on a given (associative) algebra. Forming a group ring can be viewed as defining a new addition for the elements of the given group, and extending the multiplication to sums of group elements in a natural way. Forming the exterior algebra of a given vector space can be viewed as defining a new multiplication for the vectors in a natural way.
GAP does not support such a procedure. The main reason for this is that in GAP, the multiplication in a group, a ring etc. is always written as *, and the addition in a vector space, a ring etc. is always written as +. Therefore it is not possible to define the Lie bracket as a "second multiplication" for the elements of a given algebra; in fact, the multiplication in Lie algebras in GAP is denoted by *. Analogously, constructing the group ring as sketched above is impossible if an addition is already defined for the elements; note the difference between the usual addition of matrices and the addition in the group ring of a matrix group! (See Chapter 65 for an example.) Similarly, there is already a multiplication defined for row vectors (yielding the standard scalar product), hence these vectors cannot be regarded as elements of the exterior algebra of the space.
In situations such as the ones mentioned above, GAP's way to deal with the structures in question is the following. Instead of defining new operations for the given objects, new objects are created to which the given arithmetic operations * and + are then made applicable.
With this construction, matrix Lie algebras consist of matrices that are different from the matrices with associative multiplication; technically, the type of a matrix determines how it is multiplied with other matrices (see IsMatrix (24.2-1)). A matrix with the Lie bracket as its multiplication can be created with the function LieObject (64.1-1) from a matrix with the usual associative multiplication.
Group rings (more general: magma rings, see Chapter 65) can be constructed with FreeMagmaRing (65.1-1) from a coefficient ring and a group. The elements of the group are not contained in such a group ring, one has to use an embedding map for creating a group ring element that corresponds to a given group element.
It should be noted that the GAP approach to the construction of Lie algebras from associative algebras is generic in the sense that all objects in the filter IsLieObject (64.1-2) use the same methods for their addition, multiplication etc., by delegating to the "underlying" objects of the associative algebra, no matter what these objects actually are. Analogously, also the construction of group rings is generic.
The goal of this section is to implement objects with a prescribed multiplication. Let us assume that we are given a field F, and that we want to define a new multiplication * on F that is given by a * b = a b - a - b + 2; here a b denotes the ordinary product in F.
By the discussion in Section 82.1, we know that we cannot define a new multiplication on F itself but have to create new objects.
We want to distinguish these new objects from all other GAP objects, in order to describe for example the situation that two of our objects shall be multiplied. This distinction is made via the type of the objects. More precisely, we declare a new filter, a function that will return true for our new objects, and false for all other GAP objects. This can be done by calling DeclareFilter (79.18-5), but since our objects will know about the value already when they are constructed, the filter can be created with DeclareCategory (79.18-1) or NewCategory (79.1-1).
DeclareCategory( "IsMyObject", IsObject );
The idea is that the new multiplication will be installed only for objects that "lie in the category IsMyObject".
The next question is what internal data our new objects store, and how they are accessed. The easiest solution is to store the "underlying" object from the field F. GAP provides two general possibilities how to store this, namely record-like and list-like structures (for examples, see 79.10 and 79.11). We decide to store the data in a list-like structure, at position 1. This representation is declared as follows.
DeclareRepresentation( "IsMyObjectListRep", IsPositionalObjectRep, [ 1 ] );
Of course we can argue that this declaration is superfluous because all objects in the category IsMyObject will be represented this way; it is possible to proceed like that, but often (in more complicated situations) it turns out to be useful that several representations are available for "the same element".
For creating the type of our objects, we need to specify to which family (see 13.1) the objects shall belong. For the moment, we need not say anything about relations to other GAP objects, thus the only requirement is that all new objects lie in the same family; therefore we create a new family. Also we are not interested in properties that some of our objects have and others do not have, thus we need only one type, and store it in a global variable.
MyType:= NewType( NewFamily( "MyFamily" ),
IsMyObject and IsMyObjectListRep );
The next step is to write a function that creates a new object. It may look as follows.
MyObject:= val -> Objectify( MyType, [ Immutable( val ) ] );
Note that we store an immutable copy of the argument in the returned object; without doing so, for example if the argument would be a mutable matrix then the corresponding new object would be changed whenever the matrix is changed (see 12.6 for more details about mutability).
Having entered the above GAP code, we can create some of our objects.
gap> a:= MyObject( 3 ); b:= MyObject( 5 ); <object> <object> gap> a![1]; b![1]; 3 5
But clearly a lot is missing. Besides the fact that the desired multiplication is not yet installed, we see that also the way how the objects are printed is not satisfactory.
Let us improve the latter first. There are two GAP functions View (6.3-3) and Print (6.3-4) for showing objects on the screen. View (6.3-3) is thought to show a short and human readable form of the object, and Print (6.3-4) is thought to show a not necessarily short form that is GAP readable whenever this makes sense. We decide to show a as 3 by View (6.3-3), and to show the construction MyObject( 3 ) by Print (6.3-4); the methods are installed for the underlying operations ViewObj (6.3-5) and PrintObj (6.3-5).
InstallMethod( ViewObj,
"for object in `IsMyObject'",
[ IsMyObject and IsMyObjectListRep ],
function( obj )
Print( "<", obj![1], ">" );
end );
InstallMethod( PrintObj,
"for object in `IsMyObject'",
[ IsMyObject and IsMyObjectListRep ],
function( obj )
Print( "MyObject( ", obj![1], " )" );
end );
This is the result of the above installations.
gap> a; Print( a, "\n" ); <3> MyObject( 3 )
And now we try to install the multiplication.
InstallMethod( \*,
"for two objects in `IsMyObject'",
[ IsMyObject and IsMyObjectListRep,
IsMyObject and IsMyObjectListRep ],
function( a, b )
return MyObject( a![1] * b![1] - a![1] - b![1] + 2 );
end );
When we enter the above code, GAP runs into an error. This is due to the fact that the operation \* (31.12-1) is declared for two arguments that lie in the category IsMultiplicativeElement (31.14-10). One could circumvent the check whether the method matches the declaration of the operation, by calling InstallOtherMethod (78.2-2) instead of InstallMethod (78.2-1). But it would make sense if our objects would lie in IsMultiplicativeElement (31.14-10), for example because some generic methods for objects with multiplication would be available then, such as powering by positive integers via repeated squaring. So we want that IsMyObject implies IsMultiplicativeElement (31.14-10). The easiest way to achieve such implications is to use the implied filter as second argument of the DeclareCategory (79.18-1) call; but since we do not want to start anew, we can also install the implication afterwards.
InstallTrueMethod( IsMultiplicativeElement, IsMyObject );
Afterwards, installing the multiplication works without problems. Note that MyType and therefore also a and b are not affected by this implication, so we construct them anew.
gap> MyType:= NewType( NewFamily( "MyFamily" ), > IsMyObject and IsMyObjectListRep );; gap> a:= MyObject( 3 );; b:= MyObject( 5 );; gap> a*b; a^27; <9> <134217729>
Powering the new objects by negative integers is not possible yet, because GAP does not know how to compute the inverse of an element a, say, which is defined as the unique element a' such that both a a' and a' a are "the unique multiplicative neutral element that belongs to a".
And also this neutral element, if it exists, cannot be computed by GAP in our current situation. It does, however, make sense to ask for the multiplicative neutral element of a given magma, and for inverses of elements in the magma.
But before we can form domains of our objects, we must define when two objects are regarded as equal; note that this is necessary in order to decide about the uniqueness of neutral and inverse elements. In our situation, equality is defined in the obvious way. For being able to form sets of our objects, also an ordering via \< (31.11-1) is defined for them.
InstallMethod( \=,
"for two objects in `IsMyObject'",
[ IsMyObject and IsMyObjectListRep,
IsMyObject and IsMyObjectListRep ],
function( a, b )
return a![1] = b![1];
end );
InstallMethod( \<,
"for two objects in `IsMyObject'",
[ IsMyObject and IsMyObjectListRep,
IsMyObject and IsMyObjectListRep ],
function( a, b )
return a![1] < b![1];
end );
Let us look at an example. We start with finite field elements because then the domains are finite, hence the generic methods for such domains will have a chance to succeed.
gap> a:= MyObject( Z(7) ); <Z(7)> gap> m:= Magma( a ); <magma with 1 generators> gap> e:= MultiplicativeNeutralElement( m ); <Z(7)^2> gap> elms:= AsList( m ); [ <Z(7)>, <Z(7)^2>, <Z(7)^5> ] gap> ForAll( elms, x -> ForAny( elms, y -> x*y = e and y*x = e ) ); true gap> List( elms, x -> First( elms, y -> x*y = e and y*x = e ) ); [ <Z(7)^5>, <Z(7)^2>, <Z(7)> ]
So a multiplicative neutral element exists, in fact all elements in the magma m are invertible. But what about the following.
gap> b:= MyObject( Z(7)^0 ); m:= Magma( a, b ); <Z(7)^0> <magma with 2 generators> gap> elms:= AsList( m ); [ <Z(7)^0>, <Z(7)>, <Z(7)^2>, <Z(7)^5> ] gap> e:= MultiplicativeNeutralElement( m ); <Z(7)^2> gap> ForAll( elms, x -> ForAny( elms, y -> x*y = e and y*x = e ) ); false gap> List( elms, x -> b * x ); [ <Z(7)^0>, <Z(7)^0>, <Z(7)^0>, <Z(7)^0> ]
Here we found a multiplicative neutral element, but the element b does not have an inverse. If an addition would be defined for our elements then we would say that b behaves like a zero element.
When we started to implement the new objects, we said that we wanted to define the new multiplication for elements of a given field F. In principle, the current implementation would admit also something like MyObject( 2 ) * MyObject( Z(7) ). But if we decide that our initial assumption holds, we may define the identity and the inverse of the object <a> as <2*e> and <a/(a-e)>, respectively, where e is the identity element in F and / denotes the division in F; note that the element <e> is not invertible, and that the above definitions are determined by the multiplication defined for our objects. Further note that after the installations shown below, also One( MyObject( 1 ) ) is defined.
(For technical reasons, we do not install the intended methods for the attributes One (31.10-2) and Inverse (31.10-8) but for the operations OneOp (31.10-2) and InverseOp (31.10-8). This is because for certain kinds of objects –mainly matrices– one wants to support a method to compute a mutable identity or inverse, and the attribute needs only a method that takes this object, makes it immutable, and then returns this object. As stated above, we only want to deal with immutable objects, so this distinction is not really interesting for us.)
A more interesting point to note is that we should mark our objects as likely to be invertible, since we add the possibility to invert them. Again, this could have been part of the declaration of IsMyObject, but we may also formulate an implication for the existing category.
InstallTrueMethod( IsMultiplicativeElementWithInverse, IsMyObject );
InstallMethod( OneOp,
"for an object in `IsMyObject'",
[ IsMyObject and IsMyObjectListRep ],
a -> MyObject( 2 * One( a![1] ) ) );
InstallMethod( InverseOp,
"for an object in `IsMyObject'",
[ IsMyObject and IsMyObjectListRep ],
a -> MyObject( a![1] / ( a![1] - One( a![1] ) ) ) );
Now we can form groups of our (nonzero) elements.
gap> MyType:= NewType( NewFamily( "MyFamily" ), > IsMyObject and IsMyObjectListRep );; gap> gap> a:= MyObject( Z(7) ); <Z(7)> gap> b:= MyObject( 0*Z(7) ); g:= Group( a, b ); <0*Z(7)> <group with 2 generators> gap> Size( g ); 6
We are completely free to define an addition for our elements, a natural one is given by <a> + <b> = <a+b-1>. As we did for the multiplication, we first change IsMyObject such that the additive structure is also known.
InstallTrueMethod( IsAdditiveElementWithInverse, IsMyObject );
Next we install the methods for the addition, and those to compute the additive neutral element and the additive inverse.
InstallMethod( \+,
"for two objects in `IsMyObject'",
[ IsMyObject and IsMyObjectListRep,
IsMyObject and IsMyObjectListRep ],
function( a, b )
return MyObject( a![1] + b![1] - 1 );
end );
InstallMethod( ZeroOp,
"for an object in `IsMyObject'",
[ IsMyObject and IsMyObjectListRep ],
a -> MyObject( One( a![1] ) ) );
InstallMethod( AdditiveInverseOp,
"for an object in `IsMyObject'",
[ IsMyObject and IsMyObjectListRep ],
a -> MyObject( a![1] / ( a![1] - One( a![1] ) ) ) );
Let us try whether the addition works.
gap> MyType:= NewType( NewFamily( "MyFamily" ), > IsMyObject and IsMyObjectListRep );; gap> a:= MyObject( Z(7) );; b:= MyObject( 0*Z(7) );; gap> m:= AdditiveMagma( a, b ); <additive magma with 2 generators> gap> Size( m ); 7
Similar as installing a multiplication automatically makes powering by integers available, multiplication with integers becomes available with the addition.
gap> 2 * a; <Z(7)^5> gap> a+a; <Z(7)^5> gap> MyObject( 2*Z(7)^0 ) * a; <Z(7)>
In particular we see that this multiplication does not coincide with the multiplication of two of our objects, that is, an integer cannot be used as a shorthand for one of the new objects in a multiplication.
(It should be possible to create a field with the new multiplication and addition. Currently this fails, due to missing methods for computing several kinds of generators from field generators, for computing the characteristic in the case that the family does not know this in advance, for checking with AsField (58.1-9) whether a domain is in fact a field, for computing the closure as a field.)
It should be emphasized that the mechanism described above may be not suitable for the situation that one wants to consider many different multiplications "on the same set of objects", since the installation of a new multiplication requires the declaration of at least one new filter and the installation of several methods. But the design of GAP is not suitable for such dynamic method installations.
Turning this argument the other way round, the implementation of the new arithmetics defined by the above multiplication and addition is available for any field F, one need not repeat it for each field one is interested in.
Similar to the above situation, the construction of a magma ring RM from a coefficient ring R and a magma M is implemented only once, since the definition of the arithmetic operations depends only on the given multiplication of M and not on M itself. So the addition is not implemented for the elements in M or –more precisely– for an isomorphic copy. In some sense, the addition is installed "for the multiplication", and as mentioned in Section 82.1, there is only one multiplication \* (31.12-1) in GAP.
generated by GAPDoc2HTML