<html><head><title>[prg] 6 An Example -- Designing Arithmetic Operations</title></head>
<body text="#000000" bgcolor="#ffffff">
[<a href="../index.htm">Top</a>] [<a href = "chapters.htm">Up</a>] [<a href ="CHAP005.htm">Previous</a>] [<a href = "theindex.htm">Index</a>]
<h1>6 An Example -- Designing Arithmetic Operations</h1><p>
<P>
<H3>Sections</H3>
<oL>
<li> <A HREF="CHAP006.htm#SECT001">New Arithmetic Operations vs. New Objects</a>
<li> <A HREF="CHAP006.htm#SECT002">Designing new Multiplicative Objects</a>
</ol><p>
<p>
In this chapter, we give a --hopefully typical--
example of extending <font face="Gill Sans,Helvetica,Arial">GAP</font> by new objects with prescribed
arithmetic operations.
<p>
<p>
<h2><a name="SECT001">6.1 New Arithmetic Operations vs. New Objects</a></h2>
<p><p>
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.
<p>
<font face="Gill Sans,Helvetica,Arial">GAP</font> does <strong>not</strong> support such a procedure.
The main reason for this is that in <font face="Gill Sans,Helvetica,Arial">GAP</font>, the multiplication in a group,
a ring etc. is always written as <code>*</code>,
and the addition in a vector space, a ring etc. is always written as <code>+</code>.
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 <font face="Gill Sans,Helvetica,Arial">GAP</font> is denoted by <code>*</code>.
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 <a href="../ref/CHAP063.htm">Magma Rings</a> in the Reference Manual 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.
<p>
In situations such as the ones mentioned above,
<font face="Gill Sans,Helvetica,Arial">GAP</font>'s way to deal with the structures in question is the following.
Instead of defining <strong>new</strong> operations for the <strong>given</strong> objects,
<strong>new</strong> objects are created to which the <strong>given</strong> arithmetic operations
<code>*</code> and <code>+</code> are then made applicable.
<p>
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 <a href="../ref/CHAP024.htm#SSEC001.1">IsMatrix</a> in the Reference Manual).
A matrix with the Lie bracket as its multiplication can be created with
the function <code>LieObject</code>
from a matrix with the usual associative multiplication.
<p>
Group rings (more general: magma rings,
see Chapter <a href="../ref/CHAP063.htm">Magma Rings</a> in the Reference Manual)
can be constructed with <code>FreeMagmaRing</code> 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.
<p>
It should be noted that the <font face="Gill Sans,Helvetica,Arial">GAP</font> approach to the construction of
Lie algebras from associative algebras is generic in the sense
that all objects in the filter <code>IsLieObject</code> 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.
<p>
<p>
<h2><a name="SECT002">6.2 Designing new Multiplicative Objects</a></h2>
<p><p>
The goal of this section is to implement objects with a prescribed
multiplication.
Let us assume that we are given a field <i>F</i>,
and that we want to define a new multiplication <code>*</code> on <i>F</i>
that is given by <i>a</i> * <i>b</i> = <i>a</i> <i>b</i> − <i>a</i> − <i>b</i> + 2;
here <i>a</i> <i>b</i> denotes the ordinary product in <i>F</i>.
<p>
By the discussion in Section <a href="CHAP006.htm#SECT001">New Arithmetic Operations vs. New Objects</a>,
we know that we cannot define a new multiplication on <i>F</i> itself
but have to create new objects.
<p>
We want to distinguish these new objects from all other <font face="Gill Sans,Helvetica,Arial">GAP</font> objects,
in order to describe for example the situation that two of our objects
shall be multiplied.
This distinction is made via the <strong>type</strong> of the objects.
More precisely, we declare a new <strong>filter</strong>, a function that will return
<code>true</code> for our new objects, and <code>false</code> for all other <font face="Gill Sans,Helvetica,Arial">GAP</font> objects.
This can be done by calling <code>DeclareFilter</code> (see <a href="CHAP003.htm#SSEC017.2">DeclareFilter</a>),
but since our objects will know about the value already when they are
constructed, the filter can be created with <code>DeclareCategory</code>
(see <a href="CHAP003.htm#SSEC017.2">DeclareCategory</a> and <a href="CHAP003.htm#SSEC001.1">NewCategory</a>).
<pre>
DeclareCategory( "IsMyObject", IsObject );
</pre>
The idea is that the new multiplication will be installed only
for objects that ``lie in the category <code>IsMyObject</code>''.
<p>
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 <i>F</i>.
<font face="Gill Sans,Helvetica,Arial">GAP</font> provides two general possibilities how to store this,
namely record-like and list-like structures
(for examples, see <a href="CHAP003.htm#SECT009">Component Objects</a> and <a href="CHAP003.htm#SECT010">Positional Objects</a>).
We decide to store the data in a list-like structure, at position 1.
This <strong>representation</strong> is declared as follows.
<pre>
DeclareRepresentation( "IsMyObjectListRep", IsPositionalObjectRep, [ 1 ] );
</pre>
Of course we can argue that this declaration is superfluous
because <strong>all</strong> objects in the category <code>IsMyObject</code> 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''.
<p>
For creating the type of our objects, we need to specify to which <strong>family</strong>
(see <a href="../ref/CHAP013.htm#SECT001">Families</a> in the Reference Manual) the objects shall belong.
For the moment, we need not say anything about relations to other <font face="Gill Sans,Helvetica,Arial">GAP</font>
objects,
thus the only requirement is that all new objects lie in the <strong>same</strong> family;
therefore we create a <strong>new</strong> 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.
<pre>
MyType:= NewType( NewFamily( "MyFamily" ),
IsMyObject and IsMyObjectListRep );
</pre>
<p>
The next step is to write a function that creates a new object.
It may look as follows.
<pre>
MyObject:= val -> Objectify( MyType, [ Immutable( val ) ] );
</pre>
Note that we store an <strong>immutable copy</strong> 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 <a href="../ref/CHAP012.htm#SECT006">Mutability and Copyability</a> in the Reference Manual for more
details about mutability).
<p>
Having entered the above <font face="Gill Sans,Helvetica,Arial">GAP</font> code, we can create some of our objects.
<pre>
gap> a:= MyObject( 3 ); b:= MyObject( 5 );
<object>
<object>
gap> a![1]; b![1];
3
5
</pre>
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.
<p>
Let us improve the latter first.
There are two <font face="Gill Sans,Helvetica,Arial">GAP</font> functions <code>View</code> and <code>Print</code> for showing objects
on the screen.
<code>View</code> is thought to show a short and human readable form of the object,
and <code>Print</code> is thought to show a not necessarily short form that is
<font face="Gill Sans,Helvetica,Arial">GAP</font> readable whenever this makes sense.
We decide to show <code>a</code> as <code></code><var>3</var><code></code> by <code>View</code>, and to show the construction
<code>MyObject( 3 )</code> by <code>Print</code>;
the methods are installed for the underlying operations <code>ViewObj</code> and
<code>PrintObj</code>.
<pre>
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 );
</pre>
<p>
This is the result of the above installations.
<pre>
gap> a; Print( a, "\n" );
<3>
MyObject( 3 )
</pre>
<p>
And now we try to install the multiplication.
<pre>
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 );
</pre>
When we enter the above code, <font face="Gill Sans,Helvetica,Arial">GAP</font> runs into an error.
This is due to the fact that the operation <code>\*</code> is declared for
two arguments that lie in the category <code>IsMultiplicativeElement</code>.
One could circumvent the check whether the method matches the
declaration of the operation, by calling <code>InstallOtherMethod</code>
instead of <code>InstallMethod</code>.
But it would make sense if our objects would lie in
<code>IsMultiplicativeElement</code>, 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 <code>IsMyObject</code> implies <code>IsMultiplicativeElement</code>.
The easiest way to achieve such implications is to use the
implied filter as second argument of the <code>DeclareCategory</code> call;
but since we do not want to start anew,
we can also install the implication afterwards.
<pre>
InstallTrueMethod( IsMultiplicativeElement, IsMyObject );
</pre>
<p>
Afterwards, installing the multiplication works without problems.
Note that <code>MyType</code> and therefore also <code>a</code> and <code>b</code> are <strong>not</strong>
affected by this implication, so we construct them anew.
<pre>
gap> MyType:= NewType( NewFamily( "MyFamily" ),
> IsMyObject and IsMyObjectListRep );;
gap> a:= MyObject( 3 );; b:= MyObject( 5 );;
gap> a*b; a^27;
<9>
<134217729>
</pre>
<p>
Powering the new objects by negative integers is not possible yet,
because <font face="Gill Sans,Helvetica,Arial">GAP</font> does not know how to compute the inverse of an element <i>a</i>,
say, which is defined as the unique element <i>a</i><sup>′</sup> such that both
<i>a</i> <i>a</i><sup>′</sup> and <i>a</i><sup>′</sup> <i>a</i> are ``the unique multiplicative neutral
element that belongs to <i>a</i>''.
<p>
And also this neutral element, if it exists,
cannot be computed by <font face="Gill Sans,Helvetica,Arial">GAP</font> 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.
<p>
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 <code>\<</code> is defined for them.
<pre>
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 );
</pre>
<p>
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.
<pre>
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)> ]
</pre>
<p>
So a multiplicative neutral element exists,
in fact all elements in the magma <code>m</code> are invertible.
But what about the following.
<pre>
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> ]
</pre>
Here we found a multiplicative neutral element,
but the element <code>b</code> does not have an inverse.
If an addition would be defined for our elements then we would say
that <code>b</code> behaves like a zero element.
<p>
When we started to implement the new objects,
we said that we wanted to define the new multiplication for elements
of a given field <i>F</i>.
In principle, the current implementation would admit also something
like <code>MyObject( 2 ) * MyObject( Z(7) )</code>.
But if we decide that our initial assumption holds,
we may define the identity and the inverse of the object <code><a></code> as
<code><2*e></code> and <code><a/(a-e)></code>, respectively,
where <code>e</code> is the identity element in <i>F</i> and <code>/</code> denotes the division
in <i>F</i>;
note that the element <code><e></code> 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 <code>One( MyObject( 1 ) )</code> is defined.
<p>
(For technical reasons, we do not install the intended methods for
the attributes <code>One</code> and <code>Inverse</code> but for the operations <code>OneOp</code>
and <code>InverseOp</code>.
This is because for certain kinds of objects --mainly matrices--
one wants to support a method to compute a <strong>mutable</strong> 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.)
<p>
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 <code>IsMyObject</code>,
but we may also formulate an implication for the existing category.
<p>
<pre>
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] ) ) ) );
</pre>
Now we can form groups of our (nonzero) elements.
<pre>
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
</pre>
<p>
We are completely free to define an <strong>addition</strong> for our elements,
a natural one is given by <code><a> + <b> = <a+b-1></code>.
As we did for the multiplication, we first change <code>IsMyObject</code>
such that the additive structure is also known.
<pre>
InstallTrueMethod( IsAdditiveElementWithInverse, IsMyObject );
</pre>
Next we install the methods for the addition,
and those to compute the additive neutral element
and the additive inverse.
<pre>
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] ) ) ) );
</pre>
Let us try whether the addition works.
<pre>
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
</pre>
<p>
Similar as installing a multiplication automatically makes
powering by integers available,
multiplication with integers becomes available with the addition.
<pre>
gap> 2 * a;
<Z(7)^5>
gap> a+a;
<Z(7)^5>
gap> MyObject( 2*Z(7)^0 ) * a;
<Z(7)>
</pre>
In particular we see that this multiplication does <strong>not</strong> coincide
with the multiplication of two of our objects,
that is, an integer <strong>cannot</strong> be used as a shorthand for one of the
new objects in a multiplication.
<p>
(It should be possible to create a <strong>field</strong> 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 <code>AsField</code> whether a domain is in fact a field,
for computing the closure as a field.)
<p>
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 <font face="Gill Sans,Helvetica,Arial">GAP</font> is not suitable for such dynamic method
installations.
<p>
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 <i>F</i>,
one need not repeat it for each field one is interested in.
<p>
Similar to the above situation,
the construction of a magma ring <i>RM</i> from a coefficient ring <i>R</i>
and a magma <i>M</i> is implemented only once,
since the definition of the arithmetic operations depends only on the
given multiplication of <i>M</i> and not on <i>M</i> itself.
So the addition is not implemented for the elements in <i>M</i> or
--more precisely-- for an isomorphic copy.
In some sense, the addition is installed ``for the multiplication'',
and as mentioned in Section <a href="CHAP006.htm#SECT001">New Arithmetic Operations vs. New Objects</a>,
there is only one multiplication <code>\*</code> in <font face="Gill Sans,Helvetica,Arial">GAP</font>.
<p>
<p>
[<a href="../index.htm">Top</a>] [<a href = "chapters.htm">Up</a>] [<a href ="CHAP005.htm">Previous</a>] [<a href = "theindex.htm">Index</a>]
<P>
<font face="Gill Sans,Helvetica,Arial">GAP 4 manual<br>December 2008
</font></body></html>
