\GLISSANDO (version 1.0) is a share library package that implements a GAP3 library of small semigroups and near-rings. The library files can be systematically searched for near-rings and semigroups with certain properties.
The \GLISSANDO package (version 1.0) was written by
Christof Nöbauer
Institut für Mathematik
Johannes Kepler Universität Linz
4040 Linz, Austria
e-mail noebsi@bruckner.stoch.uni-linz.ac.at
and supported by the
Austrian Fonds zur F{örderung der wissenschaftlichen Forschung}, Project P11486-TEC.
The \GLISSANDO package is completely written in the GAP3 language,
it does not require any additional programs and/or compilations. It will
run on any computer that runs GAP3. To access \GLISSANDO, use
RequirePackage( "gliss" ); (see RequirePackage).
A transformation is a mapping with equal source and range, say X. For example, X may be a set or a group. A transformation on X then acts on X by transforming each element of X into (precisely one) element of X.
Note that a transformation is just a special case of a mapping. So all GAP3 functions that work for mappings will also work for transformations.
For the following, it is important to keep in mind that in GAP3 sets are represented by sorted lists without holes and duplicates. Throughout this section, let X be a set or a group with n elements. A transformation on X is uniquely determined by a list of length n without holes and with entries which are integers between 1 and n.
For example,
for the set X := [1,2,3], the list [1,1,2] determines the
transformation on X which transforms 1 into 1, 2
into 1, and 3 into 2.
Analogously, for the cyclic group of order 3: C3, with
(the uniquely ordered) set of elements
[(),(1,2,3),(1,3,2)], the list [2,3,3] determines the
transformation on C3
which transforms () into (1,2,3), (1,2,3) into
(1,3,2), and (1,3,2) into (1,3,2).
Such a list which on a given set or group uniquely determines a transformation will be called transformation list (short tfl).
Transformations are created by the constructor functions
Trans\-for\-ma\-tion
or As\-Trans\-for\-ma\-tion and they are represented by records that
contain all the information about the transformations.
Transformation( obj, tfl )
The constructor function Transformation returns the transformation
determined by the transformation list tfl on obj where
obj must be a group or a set.
gap> t1:=Transformation([1..3],[1,1,2]); Transformation( [ 1, 2, 3 ], [ 1, 1, 2 ] ) gap> g:=Group((1,2),(3,4)); Group( (1,2), (3,4) ) gap> gt := Transformation(g,[1,1,2,5]); Error, Usage: Transformation( <obj>, <tfl> ) where <obj> must be a set or a group and <tfl> must be a valid transformation list for <obj> in Transformation( g, [ 1, 1, 2, 5 ] ) called from main loop brk> gap> gt := Transformation( g, [4,2,2,1] ); Transformation( Group( (1,2), (3,4) ), [ 4, 2, 2, 1 ] )
AsTransformation( map )
The constructor function AsTransformation returns the mapping map
as transformation. Of course, this function can only be applied to mappings
with equal source and range, otherwise an error will be signaled.
gap> s3:=Group((1,2),(1,2,3)); Group( (1,2), (1,2,3) ) gap> i:=InnerAutomorphism(s3,(2,3)); InnerAutomorphism( Group( (1,2), (1,2,3) ), (2,3) ) gap> AsTransformation(i); Transformation( Group( (1,2), (1,2,3) ), [ 1, 2, 6, 5, 4, 3 ] )
IsTransformation( obj )
IsTransformation returns true if the object obj is a
transformation and false otherwise.
gap> IsTransformation( [1,1,2] ); false # a list is not a transformation gap> IsTransformation( (1,2,3) ); false # a permutation is not a transformation gap> IsTransformation( t1 ); true
IsSetTransformation( obj )
IsSetTransformation returns true if the object obj is a
set transformation and false otherwise.
gap> IsSetTransformation( t1 ); true gap> g:= Group((1,2),(3,4)); Group( (1,2), (3,4) ) gap> gt:=Transformation(g,[4,2,2,1]); [ 4, 2, 2, 1 ] gap> IsSetTransformation( gt ); false
IsGroupTransformation( obj )
IsGroupTransformation returns true if the object obj is a
group transformation and false otherwise.
gap> IsGroupTransformation( t1 ); false gap> IsGroupTransformation( gt ); true
Note that transformations are defined to be either a set transformation or a group transformation.
IdentityTransformation( obj )
Identity\-Trans\-for\-ma\-tion is the counterpart to the GAP3 standard
library function
Iden\-ti\-ty\-Mapping. It returns the identity transformation on
obj
where obj must be a group or a set.
gap> IdentityTransformation( [1..3] ); Transformation( [ 1, 2, 3 ], [ 1, 2, 3 ] ) gap> IdentityTransformation( s3 ); Transformation( Group( (1,2), (1,2,3) ), [ 1, 2, 3, 4, 5, 6 ] )
63.9 Kernel for transformations
Kernel( t )
For a transformation t on X, the kernel of t is defined as an equivalence relation Kernel(t) as: ∀ x,y ∈ X: (x,y) ∈ Kernel(t) if\/f t(x) = t(y).
Kernel returns the kernel of the transformation t as a list l
of lists where each sublist of l represents an equivalence class of the
equivalence relation Kernel(t).
gap> t:=Transformation( [1..5], [2,3,2,4,4] ); Transformation( [ 1, 2, 3, 4, 5 ], [ 2, 3, 2, 4, 4 ] ) gap> Kernel( t ); [ [ 1, 3 ], [ 2 ], [ 4, 5 ] ]
63.10 Rank for transformations
Rank( t )
For a transformation t on X, the rank of t is defined as
the size of the image of t, i.e.
| {t(x) | x ∈ X} |,
or, in GAP3
language: Length( Image( t ) ).
Rank returns the rank of the transformation t.
gap> t1; Transformation( [ 1, 2, 3 ], [ 1, 1, 2 ] ) gap> Rank( t1 ); 2 gap> gap> gt; Transformation( Group( (1,2), (3,4) ), [ 4, 2, 2, 1 ] ) gap> Rank(gt); 3
63.11 Operations for transformations
t1 * t2
The product operator * returns the transformation which is obtained from the transformations t1 and t2, by composition of t1 and t2 (i.e. performing t2 after t1). This function works for both set transformations as well as group transformations.
gap> t1:=Transformation( [1..3], [1,1,2] ); Transformation( [ 1, 2, 3 ], [ 1, 1, 2 ] ) gap> t2:=Transformation( [1..3], [2,3,3] ); Transformation( [ 1, 2, 3 ], [ 2, 3, 3 ] ) gap> t1*t2; Transformation( [ 1, 2, 3 ], [ 2, 2, 3 ] ) gap> t2*t1; Transformation( [ 1, 2, 3 ], [ 1, 2, 2 ] )
t1 + t2
The add operator + returns the group transformation which is obtained
from the group transformations t1 and t2 by pointwise addition
of t1 and t2. (Note that in this context addition means
performing the GAP3 operation p * q for the corresponding
permutations p and q).
t1 - t2
The subtract operator - returns the group transformation which is
obtained from the group transformations t1 and t2 by pointwise
subtraction of t1 and t2. (Note that in this context subtraction
means performing the GAP3 operation p * q^{}-1 for the corresponding
permutations p and q).
Of course, those two functions + and - work only for group
transformations.
gap> g:=Group( (1,2,3) ); Group( (1,2,3) ) gap> gt1:=Transformation( g, [2,3,3] ); Transformation( Group( (1,2,3) ), [ 2, 3, 3 ] ) gap> gt2:=Transformation( g, [1,3,2] ); Transformation( Group( (1,2,3) ), [ 1, 3, 2 ] ) gap> gt1+gt2; Transformation( Group( (1,2,3) ), [ 2, 2, 1 ] ) gap> gt1-gt2; Transformation( Group( (1,2,3) ), [ 2, 1, 2 ] )
DisplayTransformation( t )
DisplayTransformation nicely displays a transformation t.
gap> t:=Transformation( [1..5], [3,3,2,1,4] );
Transformation( [ 1, 2, 3, 4, 5 ], [ 3, 3, 2, 1, 4 ] )
gap> DisplayTransformation( t );
Transformation on [ 1, 2, 3, 4, 5 ]:
1 -> 3
2 -> 3
3 -> 2
4 -> 1
5 -> 4
gap>
As almost all objects in GAP3, transformations, too, are representend by records. Such a transformation record has the following components:
isGeneralMapping:true, since in particular, any transformation is a
general mapping.
domain:Mappings.
isMapping:true since a transformation is in particular a single
valued mapping.
isTransformation:true for a transformation.
isSetTransformation:true for set transformations exclusively.
isGroupTransformation, isGroupElement:true for group transformations
exclusively.
elements:
source, range:
tfl:
operations:=, etc.
can be found here.
image, rank, ker:63.14 Transformation Semigroups
Having established transformations and being able to perform the associative
operation composition (which in GAP3 is denoted as * with
them, the next step is to consider transformation semigroups.
All functions described in this section are intended for finite
transformation semigroups, in particular transformation semigroups
on a finite set or group X.
A transformation semigroup is created by the constructor function
Trans\-for\-ma\-tion\-Semi\-group and it is represented by a record
that contains all the information about the transformation semigroup.
TransformationSemigroup( t1, ..., tn )
TransformationSemigroup( [ t1, ..., tn ] )
When called in this form, the constructor function
Trans\-for\-mation\-Semi\-group returns the
transformation semigroup generated by the transformations
t1, ..., tn. There is another way to call this function:
TransformationSemigroup( n )
If the argument is a positive integer n,
Trans\-for\-mation\-Semi\-group returns the semigroup of all
transformations on the set {1,2, ... , n}.
gap> t1 := Transformation( [1..3], [1,1,2] ); Transformation( [ 1, 2, 3 ], [ 1, 1, 2 ] ) gap> t2 := Transformation( [1..3], [2,3,3] ); Transformation( [ 1, 2, 3 ], [ 2, 3, 3 ] ) gap> s:=TransformationSemigroup( t1, t2 ); TransformationSemigroup( Transformation( [ 1, 2, 3 ], [ 1, 1, 2 ], Transformation( [ 1, 2, 3 ], [ 2, 3, 3 ] ) ) gap> s27 := TransformationSemigroup( 3 ); TransformationSemigroup( Transformation( [ 1, 2, 3 ], [ 1, 1, 1 ] ), Transformation( [ 1, 2, 3 ], [ 1, 1, 2 ] ), Transformation( [ 1, 2, 3 ], [ 1, 1, 3 ] ), Transformation( [ 1, 2, 3 ], [ 1, 2, 1 ] ), Transformation( [ 1, 2, 3 ], [ 1, 2, 2 ] ), Transformation( [ 1, 2, 3 ], [ 1, 2, 3 ] ), Transformation( [ 1, 2, 3 ], [ 1, 3, 1 ] ), Transformation( [ 1, 2, 3 ], [ 1, 3, 2 ] ), Transformation( [ 1, 2, 3 ], [ 1, 3, 3 ] ), Transformation( [ 1, 2, 3 ], [ 2, 1, 1 ] ), Transformation( [ 1, 2, 3 ], [ 2, 1, 2 ] ), Transformation( [ 1, 2, 3 ], [ 2, 1, 3 ] ), Transformation( [ 1, 2, 3 ], [ 2, 2, 1 ] ), Transformation( [ 1, 2, 3 ], [ 2, 2, 2 ] ), Transformation( [ 1, 2, 3 ], [ 2, 2, 3 ] ), Transformation( [ 1, 2, 3 ], [ 2, 3, 1 ] ), Transformation( [ 1, 2, 3 ], [ 2, 3, 2 ] ), Transformation( [ 1, 2, 3 ], [ 2, 3, 3 ] ), Transformation( [ 1, 2, 3 ], [ 3, 1, 1 ] ), Transformation( [ 1, 2, 3 ], [ 3, 1, 2 ] ), Transformation( [ 1, 2, 3 ], [ 3, 1, 3 ] ), Transformation( [ 1, 2, 3 ], [ 3, 2, 1 ] ), Transformation( [ 1, 2, 3 ], [ 3, 2, 2 ] ), Transformation( [ 1, 2, 3 ], [ 3, 2, 3 ] ), Transformation( [ 1, 2, 3 ], [ 3, 3, 1 ] ), Transformation( [ 1, 2, 3 ], [ 3, 3, 2 ] ), Transformation( [ 1, 2, 3 ], [ 3, 3, 3 ] ) )
IsSemigroup( obj )
IsSemigroup returns true if the object obj is a semigroup
and false otherwise. This function simply checks whether the record
component obj.isSemigroup is bound and is true.
gap> IsSemigroup( t1 ); false # a transformation is not a semigroup gap> IsSemigroup( Group( (1,2,3) ) ); false # a group is not a semigroup gap> IsSemigroup( s27 ); true
63.17 IsTransformationSemigroup
IsTransformationSemigroup( obj )
IsTransformationSemigroup returns true if the object obj
is a transformation semigroup and false otherwise.
gap> IsTransformationSemigroup( s27 ); true
Elements( sg )
Elements computes the elements of the semigroup sg. Note: the
GAP3 standard library dispatcher function Elements calls the function
sg.operations.Elements which performs a simple closure
algorithm.
gap> t1 := Transformation( [1..3], [1,1,2] );
Transformation( [ 1, 2, 3 ], [ 1, 1, 2 ] )
gap> t2 := Transformation( [1..3], [2,3,3] );
Transformation( [ 1, 2, 3 ], [ 2, 3, 3 ] )
gap> s := TransformationSemigroup( t1, t2 );
TransformationSemigroup( Transformation( [ 1, 2, 3 ],
[ 1, 1, 2 ] ), Transformation( [ 1, 2, 3 ], [ 2, 3, 3 ] ) )
gap> Elements( s );
[ Transformation( [ 1, 2, 3 ], [ 1, 1, 1 ] ),
Transformation( [ 1, 2, 3 ], [ 1, 1, 2 ] ),
Transformation( [ 1, 2, 3 ], [ 1, 2, 2 ] ),
Transformation( [ 1, 2, 3 ], [ 2, 2, 2 ] ),
Transformation( [ 1, 2, 3 ], [ 2, 2, 3 ] ),
Transformation( [ 1, 2, 3 ], [ 2, 3, 3 ] ),
Transformation( [ 1, 2, 3 ], [ 3, 3, 3 ] ) ]
Size( sg )
Size returns the number of elements in sg.
gap> Size( s ); 7
63.20 DisplayCayleyTable for semigroups
DisplayCayleyTable( sg )
DisplayCayleyTable prints the Cayley table of the semigroup sg. Note:
The dispatcher function DisplayCayleyTable calls the function
sg.operations.DisplayTable which performs the actual printing.
Display\-Cayley\-Table has no return value.
gap> DisplayCayleyTable( s );
Let:
s0 := Transformation( [ 1, 2, 3 ], [ 1, 1, 1 ] )
s1 := Transformation( [ 1, 2, 3 ], [ 1, 1, 2 ] )
s2 := Transformation( [ 1, 2, 3 ], [ 1, 2, 2 ] )
s3 := Transformation( [ 1, 2, 3 ], [ 2, 2, 2 ] )
s4 := Transformation( [ 1, 2, 3 ], [ 2, 2, 3 ] )
s5 := Transformation( [ 1, 2, 3 ], [ 2, 3, 3 ] )
s6 := Transformation( [ 1, 2, 3 ], [ 3, 3, 3 ] )
* | s0 s1 s2 s3 s4 s5 s6
---------------------------
s0 | s0 s0 s0 s3 s3 s3 s6
s1 | s0 s0 s1 s3 s3 s4 s6
s2 | s0 s0 s2 s3 s3 s5 s6
s3 | s0 s0 s3 s3 s3 s6 s6
s4 | s0 s1 s3 s3 s4 s6 s6
s5 | s0 s2 s3 s3 s5 s6 s6
s6 | s0 s3 s3 s3 s6 s6 s6
63.21 IdempotentElements for semigroups
IdempotentElements( sg )
An element i of a semigroup (S,.) is called an idempotent (element) if\/f i . i = i.
The function IdempotentElements returns a list of those elements of
the semigroup sg that are idempotent. (Note that for a finite
semigroup this can never be the empty list).
gap> IdempotentElements( s );
[ Transformation( [ 1, 2, 3 ], [ 1, 1, 1 ] ),
Transformation( [ 1, 2, 3 ], [ 1, 2, 2 ] ),
Transformation( [ 1, 2, 3 ], [ 2, 2, 2 ] ),
Transformation( [ 1, 2, 3 ], [ 2, 2, 3 ] ),
Transformation( [ 1, 2, 3 ], [ 3, 3, 3 ] ) ]
63.22 IsCommutative for semigroups
IsCommutative( sg )
A semigroup (S,.) is called commutative if ∀ a, b ∈ S: a . b = b . a.
The function IsCommutative returns
the according value true or false for a semigroup sg.
gap> IsCommutative( s ); false
Identity( sg )
An element i of a semigroup (S,.) is called an identity if\/f ∀ s ∈ S: s . i = i . s = s. Since for two identities, i,j: i = i . j = j, an identity is unique if it exists.
The function Identity returns a list containing as single entry the
identity of the semigroup sg
if it exists or the empty list [ ] otherwise.
gap> Identity( s );
[ ]
gap> tr1 := Transformation( [1..3], [1,1,1] );
Transformation( [ 1, 2, 3 ], [ 1, 1, 1 ] )
gap> tr2 := Transformation( [1..3], [1,2,2] );
Transformation( [ 1, 2, 3 ], [ 1, 2, 2 ] )
gap> sg := TransformationSemigroup( tr1, tr2 );
TransformationSemigroup( Transformation( [ 1, 2, 3 ],
[ 1, 1, 1 ] ), Transformation( [ 1, 2, 3 ], [ 1, 2, 2 ] ) )
gap> Elements( sg );
[ Transformation( [ 1, 2, 3 ], [ 1, 1, 1 ] ),
Transformation( [ 1, 2, 3 ], [ 1, 2, 2 ] ) ]
gap> Identity( sg );
[ Transformation( [ 1, 2, 3 ], [ 1, 2, 2 ] ) ]
The last example shows that the identity element of a transformation semigroup on a set X needs not necessarily be the identity transformation on X.
SmallestIdeal( sg )
A subset I of a semigroup (S,.) is defined as an ideal of S if ∀ i ∈ I, s ∈ S: i . s ∈ I \& s . i ∈ I. An ideal I is called minimal, if for any ideal J, J ⊆ I implies J = I. If a minimal ideal exists, then it is unique and therefore the smallest ideal of S.
The function SmallestIdeal returns the smallest ideal of the
transformation semigroup sg. Note that for a finite semigroup the
smallest ideal always exists. (Which is not necessarily true for an
arbitrary semigroup).
gap> SmallestIdeal( s );
[ Transformation( [ 1, 2, 3 ], [ 1, 1, 1 ] ),
Transformation( [ 1, 2, 3 ], [ 2, 2, 2 ] ),
Transformation( [ 1, 2, 3 ], [ 3, 3, 3 ] ) ]
IsSimple( sg )
A semigroup S is called simple if it has no honest ideals, i.e. in case that S is finite the smallest ideal of S equals S itself.
The GAP3 standard library dispatcher function IsSimple calls the
function
sg.\-op\-er\-a\-tions.\-Is\-Simple which checks if the semigroup
sg equals its smallest ideal and if so, returns true and
otherwise false.
gap> IsSimple( s ); false gap> c3 := TransformationSemigroup( Transformation( [1..3], > [2,3,1] ) ); TransformationSemigroup( Transformation( [ 1, 2, 3 ], [ 2, 3, 1 ] ) ) gap> IsSimple( c3 ); true
Green( sg, string )
Let (S,.) be a semigroup and a ∈ S. The set a . S1 := a . S ∪ {a} is called the principal right ideal generated by a. Analogously, S1 . a := S . a ∪ {a} is called the principal left ideal generated by a and S1 . a . S1 := S . a . S ∪ S . a ∪ a . S ∪ {a} is called the principal ideal generated by a.
Now, Green's equivalence relation L on S is defined as: (a,b) ∈ L: ⇔ S1 . a = S1 . b i.e. a and b generate the same principal left ideal. Similarly: (a,b) ∈ R: ⇔ a . S1 = b . S1 i.e. a and b generate the same principal right ideal and (a,b) ∈ J: ⇔ S1 . a . S1 = S1 . b . S1 i.e. a and b generate the same principal ideal. H is defined as the intersection of L and R and D is defined as the join of L and R.
In a finite semigroup, D = J.
The arguments of the function Green are a finite transformation
semigroup sg and a one character string string where
string must be one of the following: "L", "R",
"D", "J", "H". The return value of Green is
a list of lists of elements of sg representing the equivalence
classes of the according Green's relation.
gap> s;
TransformationSemigroup( Transformation( [ 1, 2, 3 ],
[ 1, 1, 2 ] ), Transformation( [ 1, 2, 3 ], [ 2, 3, 3 ] ) )
gap> Elements( s );
[ Transformation( [ 1, 2, 3 ], [ 1, 1, 1 ] ),
Transformation( [ 1, 2, 3 ], [ 1, 1, 2 ] ),
Transformation( [ 1, 2, 3 ], [ 1, 2, 2 ] ),
Transformation( [ 1, 2, 3 ], [ 2, 2, 2 ] ),
Transformation( [ 1, 2, 3 ], [ 2, 2, 3 ] ),
Transformation( [ 1, 2, 3 ], [ 2, 3, 3 ] ),
Transformation( [ 1, 2, 3 ], [ 3, 3, 3 ] ) ]
gap> Green( s, "L" );
[ [ Transformation( [ 1, 2, 3 ], [ 1, 1, 1 ] ),
Transformation( [ 1, 2, 3 ], [ 2, 2, 2 ] ),
Transformation( [ 1, 2, 3 ], [ 3, 3, 3 ] ) ],
[ Transformation( [ 1, 2, 3 ], [ 1, 1, 2 ] ),
Transformation( [ 1, 2, 3 ], [ 2, 2, 3 ] ) ],
[ Transformation( [ 1, 2, 3 ], [ 1, 2, 2 ] ),
Transformation( [ 1, 2, 3 ], [ 2, 3, 3 ] ) ] ]
gap> Green( s, "R" );
[ [ Transformation( [ 1, 2, 3 ], [ 1, 1, 1 ] ) ],
[ Transformation( [ 1, 2, 3 ], [ 1, 1, 2 ] ),
Transformation( [ 1, 2, 3 ], [ 1, 2, 2 ] ) ],
[ Transformation( [ 1, 2, 3 ], [ 2, 2, 2 ] ) ],
[ Transformation( [ 1, 2, 3 ], [ 2, 2, 3 ] ),
Transformation( [ 1, 2, 3 ], [ 2, 3, 3 ] ) ],
[ Transformation( [ 1, 2, 3 ], [ 3, 3, 3 ] ) ] ]
gap> Green( s, "H" );
[ [ Transformation( [ 1, 2, 3 ], [ 1, 1, 1 ] ) ],
[ Transformation( [ 1, 2, 3 ], [ 1, 1, 2 ] ) ],
[ Transformation( [ 1, 2, 3 ], [ 1, 2, 2 ] ) ],
[ Transformation( [ 1, 2, 3 ], [ 2, 2, 2 ] ) ],
[ Transformation( [ 1, 2, 3 ], [ 2, 2, 3 ] ) ],
[ Transformation( [ 1, 2, 3 ], [ 2, 3, 3 ] ) ],
[ Transformation( [ 1, 2, 3 ], [ 3, 3, 3 ] ) ] ]
gap> Green( s, "D" );
[ [ Transformation( [ 1, 2, 3 ], [ 1, 1, 1 ] ),
Transformation( [ 1, 2, 3 ], [ 2, 2, 2 ] ),
Transformation( [ 1, 2, 3 ], [ 3, 3, 3 ] ) ],
[ Transformation( [ 1, 2, 3 ], [ 1, 1, 2 ] ),
Transformation( [ 1, 2, 3 ], [ 1, 2, 2 ] ),
Transformation( [ 1, 2, 3 ], [ 2, 2, 3 ] ),
Transformation( [ 1, 2, 3 ], [ 2, 3, 3 ] ) ] ]
Rank( sg )
The rank of a transformation semigroup S is defined as the minimal rank of the elements of S, i.e. \min{ rank(s) | s ∈ S }.
The function Rank returns the rank of the semigroup sg.
gap> Rank( s ); 1 gap> c3; TransformationSemigroup( Transformation( [ 1, 2, 3 ], [ 2, 3, 1 ] ) ) gap> Rank( c3 ); 3
LibrarySemigroup( size, num )
The semigroup library contains all semigroups of sizes 1 up to 5,
classified into classes of isomorphic semigroups.
LibrarySemigroup retrieves a representative of an isomorphism class
from the semigroup library and returns it as a transformation semigroup.
The parameters of LibrarySemigroup are two positive integers:
size must be in {1,2,3,4,5} and indicates the size of the semigroup
to be retrieved, num indicates the number of an isomorphism class.
gap> ls := LibrarySemigroup( 4, 123 );
TransformationSemigroup( Transformation( [ 1, 2, 3, 4 ],
[ 1, 1, 3, 3 ] ), Transformation( [ 1, 2, 3, 4 ],
[ 1, 2, 3, 4 ] ), Transformation( [ 1, 2, 3, 4 ],
[ 1, 3, 3, 1 ] ), Transformation( [ 1, 2, 3, 4 ], [ 1, 4, 3, 2 ] ) )
gap> DisplayCayleyTable( ls );
Let:
s0 := Transformation( [ 1, 2, 3, 4 ], [ 1, 1, 3, 3 ] )
s1 := Transformation( [ 1, 2, 3, 4 ], [ 1, 2, 3, 4 ] )
s2 := Transformation( [ 1, 2, 3, 4 ], [ 1, 3, 3, 1 ] )
s3 := Transformation( [ 1, 2, 3, 4 ], [ 1, 4, 3, 2 ] )
* | s0 s1 s2 s3
------------------
s0 | s0 s0 s0 s0
s1 | s0 s1 s2 s3
s2 | s2 s2 s2 s2
s3 | s2 s3 s0 s1
63.29 Transformation semigroup records
Transformation Semigroups are implemented as records. Such a transformation semigroup record has the following components:
isDomain, isSemigroup:true for a transformation semigroup.
isTransformationSemigroup:true only for transformation semigroups.
generators:
multiplication:
gap> elms := Elements( s );
[ Transformation( [ 1, 2, 3 ], [ 1, 1, 1 ] ),
Transformation( [ 1, 2, 3 ], [ 1, 1, 2 ] ),
Transformation( [ 1, 2, 3 ], [ 1, 2, 2 ] ),
Transformation( [ 1, 2, 3 ], [ 2, 2, 2 ] ),
Transformation( [ 1, 2, 3 ], [ 2, 2, 3 ] ),
Transformation( [ 1, 2, 3 ], [ 2, 3, 3 ] ),
Transformation( [ 1, 2, 3 ], [ 3, 3, 3 ] ) ]
gap> s.multiplication( elms[5], elms[2] );
Transformation( [ 1, 2, 3 ], [ 1, 1, 2 ] )
operations:
size, elements, rank, smallestIdeal,
IsFinite, identity:
GreenL, GreenR, GreenD,
GreenJ, GreenH: Green with
the corresponding parameters.
In section Transformations we introduced transformations on sets and groups.
We used set transformations together with composition * to construct
transformation semigroups in section Transformation Semigroups.
In section Transformations
we also introduced the operation of pointwise addition + for group
transformations. Now we are able to use these group transformations
together with pointwise addition + and composition * to
construct (right) near-rings.
A (right) near-ring is a nonempty set N together with two binary operations on N, + and . s.t. (N,+) is a group, (N,.) is a semigroup, and . is right distributive over +, i.e. ∀ n1,n2,n3 ∈ N: (n1+n2). n3 = n1. n3+n2. n3.
Here we have to make a remark: we let transformations act from the right; yet in order to get a right transformation near-ring transformations must act from the left, hence we define a near-ring multiplication . of two transformations, t1, t2 as t1 . t2 := t2 * t1.
There are three possibilities to get a near-ring in GAP3: the
constructor function Nearring can be used in two different ways or a
near-ring can be extracted from the near-rings library by using the function
LibraryNearring. All functions described here were programmed for
permutation groups and they also work fine with them; other types of groups
(such as AG groups) are not supported.
Near-rings are represented by records that contain the necessary information to identify them and to do computations with them.
IsNrMultiplication( G, mul )
The arguments of the function Is\-Nr\-Mul\-ti\-pli\-ca\-tion are a
permutation group G and a GAP3 function mul which has two
arguments x and y which must both be elements of the group
G and returns an element z of G s.t. mul defines a
binary operation on G.
IsNrMultiplication returns true (false) if mul is
(is not) a near-ring multiplication on G i.e. it checks whether it is
well-defined, associative and right distributive over the group operation of
G.
gap> g := Group( (1,2), (1,2,3) ); Group( (1,2), (1,2,3) ) gap> mul_r := function(x,y) return x; end; function ( x, y ) ... end gap> IsNrMultiplication( g, mul_r ); true gap> mul_l := function(x,y) return y; end; function ( x, y ) ... end gap> IsNrMultiplication( g, mul_l ); specified multiplication is not right distributive. false
Nearring( G, mul )
In this form the constructor function Nearring returns the near-ring
defined by the permutation
group G and the near-ring multiplication mul. (For a detailed
explanation of mul see IsNrMultiplication). Near\-ring calls
Is\-Nr\-Mul\-ti\-pli\-ca\-tion
in order to make sure that mul is really a near-ring multiplication.
gap> g := Group( (1,2,3) );
Group( (1,2,3) )
gap> mul_r := function(x,y) return x; end;
function ( x, y ) ... end
gap> n := Nearring( g, mul_r );
Nearring( Group( (1,2,3) ), function ( x, y )
return x;
end )
gap> DisplayCayleyTable( n );
Let:
n0 := ()
n1 := (1,2,3)
n2 := (1,3,2)
+ | n0 n1 n2
---------------
n0 | n0 n1 n2
n1 | n1 n2 n0
n2 | n2 n0 n1
* | n0 n1 n2
---------------
n0 | n0 n0 n0
n1 | n1 n1 n1
n2 | n2 n2 n2
Nearring( t1, ..., tn )
Nearring( [t1, ..., tn] )
In this form the constructor function Near\-ring returns the near-ring
generated by the group
transformations t1,...,tn. All of them must be transformations
on the same permutation group.
Note that Near\-ring allows also a list of group transformations as
argument, which makes it possible to call
Nearring e.g. with a list of endomorphisms generated by the function
Endo\-mor\-phisms (see Endomorphisms for groups), which for a group
G
allows to compute E(G); Near\-ring called with the list of all
inner automorphisms of a group G would return I(G).
gap> t := Transformation( Group( (1,2) ), [2,1] );
Transformation( Group( (1,2) ), [ 2, 1 ] )
gap> n := Nearring( t );
Nearring( Transformation( Group( (1,2) ), [ 2, 1 ] ) )
gap> DisplayCayleyTable( n );
Let:
n0 := Transformation( Group( (1,2) ), [ 1, 1 ] )
n1 := Transformation( Group( (1,2) ), [ 1, 2 ] )
n2 := Transformation( Group( (1,2) ), [ 2, 1 ] )
n3 := Transformation( Group( (1,2) ), [ 2, 2 ] )
+ | n0 n1 n2 n3
------------------
n0 | n0 n1 n2 n3
n1 | n1 n0 n3 n2
n2 | n2 n3 n0 n1
n3 | n3 n2 n1 n0
* | n0 n1 n2 n3
------------------
n0 | n0 n0 n0 n0
n1 | n0 n1 n2 n3
n2 | n3 n2 n1 n0
n3 | n3 n3 n3 n3
gap> g := Group( (1,2), (1,2,3) );
Group( (1,2), (1,2,3) )
gap> e := Endomorphisms( g );
[ Transformation( Group( (1,2), (1,2,3) ), [ 1, 1, 1, 1, 1, 1 ] ),
Transformation( Group( (1,2), (1,2,3) ), [ 1, 2, 2, 1, 1, 2 ] ),
Transformation( Group( (1,2), (1,2,3) ), [ 1, 2, 6, 5, 4, 3 ] ),
Transformation( Group( (1,2), (1,2,3) ), [ 1, 3, 2, 5, 4, 6 ] ),
Transformation( Group( (1,2), (1,2,3) ), [ 1, 3, 3, 1, 1, 3 ] ),
Transformation( Group( (1,2), (1,2,3) ), [ 1, 3, 6, 4, 5, 2 ] ),
Transformation( Group( (1,2), (1,2,3) ), [ 1, 6, 2, 4, 5, 3 ] ),
Transformation( Group( (1,2), (1,2,3) ), [ 1, 6, 3, 5, 4, 2 ] ),
Transformation( Group( (1,2), (1,2,3) ), [ 1, 6, 6, 1, 1, 6 ] ),
Transformation( Group( (1,2), (1,2,3) ), [ 1, 2, 3, 4, 5, 6 ] ) ]
gap> nr := Nearring( e ); # the endomorphisms near-ring on S3
Nearring( Transformation( Group( (1,2), (1,2,3) ), [ 1, 1, 1, 1, 1, 1
] ), Transformation( Group( (1,2), (1,2,3) ), [ 1, 2, 2, 1, 1, 2
] ), Transformation( Group( (1,2), (1,2,3) ), [ 1, 2, 3, 4, 5, 6
] ), Transformation( Group( (1,2), (1,2,3) ), [ 1, 2, 6, 5, 4, 3
] ), Transformation( Group( (1,2), (1,2,3) ), [ 1, 3, 2, 5, 4, 6
] ), Transformation( Group( (1,2), (1,2,3) ), [ 1, 3, 3, 1, 1, 3
] ), Transformation( Group( (1,2), (1,2,3) ), [ 1, 3, 6, 4, 5, 2
] ), Transformation( Group( (1,2), (1,2,3) ), [ 1, 6, 2, 4, 5, 3
] ), Transformation( Group( (1,2), (1,2,3) ), [ 1, 6, 3, 5, 4, 2
] ), Transformation( Group( (1,2), (1,2,3) ), [ 1, 6, 6, 1, 1, 6 ] ) )
gap> Size( nr );
54
IsNearring( obj )
IsNearring returns true if the object obj is a near-ring
and false otherwise. This function simply checks if the record
component obj.isNear-ring is bound to the value true.
gap> n := LibraryNearring( "C3", 4 ); LibraryNearring( "C3", 4 ) gap> IsNearring( n ); true gap> IsNearring( nr ); true gap> IsNearring( Integers ); false # Integers is a ring record, not a near-ring record
63.34 IsTransformationNearring
IsTransformationNearring( obj )
IsTransformationNearring returns true if the object obj is
a transformation near-ring and false otherwise.
Is\-Trans\-for\-ma\-tion\-Near\-ring
simply checks if the record component
obj.is\-Trans\-for\-ma\-tion\-Near\-ring is
bound to true.
gap> IsTransformationNearring( nr ); true gap> IsTransformationNearring( n ); false
LibraryNearring( grp\_name, num )
LibraryNearring retrieves a near-ring from the near-rings library files.
grp\_name must be one of the following strings
indicating the name of the according group: "C2", "C3",
"C4", "V4", "C5", "C6", "S3", "C7",
"C8", "C2xC4", "C2xC2xC2", "D8", "Q8",
"C9", "C3xC3", "C10", "D10", "C11",
"C12", "C2xC6", "D12", "A4", "T",
"C13", "C14", "D14", "C15",
num must be an integer which indicates the number of the class of
near-rings on the specified group.
gap> n := LibraryNearring( "V4", 13 ); LibraryNearring( "V4", 13 )
63.36 DisplayCayleyTable for near-rings
DisplayCayleyTable( nr )
DisplayCayleyTable prints the additive and multiplicative Cayley tables
of the near-ring nr. This function
works the same way as for semigroups; the dispatcher function
Display\-Cayley\-Table calls
nr.op\-e\-ra\-tions.Display\-Ta\-ble which performs the actual printing.
gap> DisplayCayleyTable( LibraryNearring( "V4", 22 ) );
Let:
n0 := ()
n1 := (3,4)
n2 := (1,2)
n3 := (1,2)(3,4)
+ | n0 n1 n2 n3
------------------
n0 | n0 n1 n2 n3
n1 | n1 n0 n3 n2
n2 | n2 n3 n0 n1
n3 | n3 n2 n1 n0
* | n0 n1 n2 n3
------------------
n0 | n0 n0 n0 n0
n1 | n0 n1 n2 n3
n2 | n2 n2 n2 n2
n3 | n2 n3 n0 n1
Elements( nr )
The function Elements computes the elements of the near-ring nr.
As for semigroups the
GAP3 standard library dispatcher function Elements calls
nr.op\-er\-a\-tions.El\-e\-ments which
simply returns the elements of nr.\-group if nr is not a
transformation near-ring or -- if nr is a transformation near-ring --
performs a simple closure algorithm and returns a set of transformations
which are the elements of nr.
gap> t := Transformation( Group( (1,2) ), [2,1] );
Transformation( Group( (1,2) ), [ 2, 1 ] )
gap> Elements( Nearring( t ) );
[ Transformation( Group( (1,2) ), [ 1, 1 ] ),
Transformation( Group( (1,2) ), [ 1, 2 ] ),
Transformation( Group( (1,2) ), [ 2, 1 ] ),
Transformation( Group( (1,2) ), [ 2, 2 ] ) ]
gap> Elements( LibraryNearring( "C3", 4 ) );
[ (), (1,2,3), (1,3,2) ]
Size( nr )
Size returns the number of elements in the near-ring nr.
gap> Size( LibraryNearring( "C3", 4 ) ); 3
63.39 Endomorphisms for near-rings
Endomorphisms( nr )
Endomorphisms computes all the endomorphisms of the near-ring nr.
The endomorphisms are returned as a list of transformations. In fact, the
returned list contains those endomorphisms of nr.group which are
also endomorphisms of the near-ring nr.
gap> t := Transformation( Group( (1,2) ), [2,1] );
Transformation( Group( (1,2) ), [ 2, 1 ] )
gap> nr := Nearring( t );
Nearring( Transformation( Group( (1,2) ), [ 2, 1 ] ) )
gap> Endomorphisms( nr );
[ Transformation( Group( (1,2)(3,4), (1,3)(2,4) ), [ 1, 1, 1, 1 ] ),
Transformation( Group( (1,2)(3,4), (1,3)(2,4) ), [ 1, 2, 2, 1 ] ),
Transformation( Group( (1,2)(3,4), (1,3)(2,4) ), [ 1, 2, 3, 4 ] ) ]
63.40 Automorphisms for near-rings
Automorphisms( nr )
Automorphisms computes all the automorphisms of the near-ring nr.
The automorphisms are returned as a list of transformations. In fact, the
returned list contains those automorphisms of nr.group which are
also automorphisms of the near-ring nr.
gap> t := Transformation( Group( (1,2) ), [2,1] ); Transformation( Group( (1,2) ), [ 2, 1 ] ) gap> nr := Nearring( t ); Nearring( Transformation( Group( (1,2) ), [ 2, 1 ] ) ) gap> Automorphisms( nr ); [ Transformation( Group( (1,2)(3,4), (1,3)(2,4) ), [ 1, 2, 3, 4 ] ) ]
FindGroup( nr )
For a transformation near-ring nr, this function computes the additive
group of nr as a GAP3 permutation group and stores it in the record
component nr.group.
gap> t := Transformation( Group( (1,2) ), [2,1] );
Transformation( Group( (1,2) ), [ 2, 1 ] )
gap> n := Nearring( t );
Nearring( Transformation( Group( (1,2) ), [ 2, 1 ] ) )
gap> g := FindGroup( n );
Group( (1,2)(3,4), (1,3)(2,4) )
gap> Elements( g );
[ (), (1,2)(3,4), (1,3)(2,4), (1,4)(2,3) ]
gap> Elements( n );
[ Transformation( Group( (1,2) ), [ 1, 1 ] ),
Transformation( Group( (1,2) ), [ 1, 2 ] ),
Transformation( Group( (1,2) ), [ 2, 1 ] ),
Transformation( Group( (1,2) ), [ 2, 2 ] ) ]
NearringIdeals( nr )
NearringIdeals( nr, "l" )
NearringIdeals( nr, "r" )
NearringIdeals computes all (left) (right) ideals of the near-ring
nr. The return value is a list of subgroups
of the additive group of nr representing the according ideals.
In case that nr is a transformation near-ring, FindGroup is used
to determine the additive group of nr as a permutation group.
If the optional parameters "l" or "r" are passed, all left
resp. right ideals are computed.
gap> n := LibraryNearring( "V4", 11 );
LibraryNearring( "V4", 11 )
gap> NearringIdeals( n );
[ Subgroup( V4, [ ] ), Subgroup( V4, [ (3,4) ] ), V4 ]
gap> NearringIdeals( n, "r" );
[ Subgroup( V4, [ ] ), Subgroup( V4, [ (3,4) ] ), V4 ]
gap> NearringIdeals( n, "l" );
[ Subgroup( V4, [ ] ), Subgroup( V4, [ (3,4) ] ),
Subgroup( V4, [ (1,2) ] ), Subgroup( V4, [ (1,2)(3,4) ] ), V4 ]
InvariantSubnearrings( nr )
A subnear-ring (M,+,.) of a near-ring (N,+,.) is called an invariant subnear-ring if both, M . N ⊆ M and N . M ⊆ M.
The function InvariantSubnearrings computes all invariant
subnear-rings of the near-ring nr.
The function returns a list of near-rings representing the according
invariant subnear-rings.
In case that nr is a transformation near-ring, FindGroup is used
to determine the additive group of nr as a permutation group.
gap> InvariantSubnearrings( LibraryNearring( "V4", 22 ) );
[ Nearring( Subgroup( V4, [ (1,2) ] ), function ( x, y )
return elms[tfle.(f[Position( elms, y )])[Position( elms, x )]
];
end ), Nearring( V4, function ( x, y )
return elms[tfle.(f[Position( elms, y )])[Position( elms, x )]
];
end ) ]
Subnearrings( nr )
The function Subnearrings computes all subnear-rings of the near-ring
nr. The function returns a list of near-rings representing the
according subnear-rings.
In case that nr is a transformation near-ring, FindGroup is used
to determine the additive group of nr as a permutation group.
gap> Subnearrings( LibraryNearring( "V4", 22 ) );
[ Nearring( Subgroup( V4, [ ] ), function ( x, y )
return elms[tfle.(f[Position( elms, y )])[Position( elms, x )]
];
end ), Nearring( Subgroup( V4, [ (3,4) ] ), function ( x, y )
return elms[tfle.(f[Position( elms, y )])[Position( elms, x )]
];
end ), Nearring( Subgroup( V4, [ (1,2) ] ), function ( x, y )
return elms[tfle.(f[Position( elms, y )])[Position( elms, x )]
];
end ), Nearring( V4, function ( x, y )
return elms[tfle.(f[Position( elms, y )])[Position( elms, x )]
];
end ) ]
Identity( nr )
The function Identity returns a list containing the identity of the
multiplicative semigroup of the near-ring nr
if it exists and the empty list [ ] otherwise.
gap> Identity( LibraryNearring( "V4", 22 ) ); [ (3,4) ]
Distributors( nr )
An element x of a near-ring (N,+,.) is called a distributor if x = n1 . (n2 + n3 ) - (n1 . n2 + n1 . n3 ) for some elements n1, n2, n3 of N.
The function Distributors returns a list containing the distributors
of the near-ring nr.
gap> Distributors( LibraryNearring( "S3", 19 ) ); [ (), (1,2,3), (1,3,2) ]
DistributiveElements( nr )
An element d of a right near-ring (N,+,.) is called a distributive element if it is also left distributive over all elements, i.e. ∀ n1, n2 ∈ N: d . (n1 + n2 ) = d . n1 + d . n2.
The function DistributiveElements returns a list containing the
distributive elements of the near-ring nr.
gap> DistributiveElements( LibraryNearring( "S3", 25 ) ); [ (), (1,2,3), (1,3,2) ]
IsDistributiveNearring( nr )
A right near-ring N is called distributive near-ring if its multiplication is also left distributive.
The function IsDistributiveNearring simply checks if all elements
are distributive and returns the according boolean value
true or false.
gap> IsDistributiveNearring( LibraryNearring( "S3", 25 ) ); false
ZeroSymmetricElements( nr )
Let (N,+,.) be a right near-ring and denote by 0 the neutral element of (N,+). An element n of N is called a zero-symmetric element if n . 0 = 0.
Remark\: note that in a right near-ring 0 . n = 0 is true for all elements n.
The function ZeroSymmetricElements returns a list containing the
zero-symmetric elements of the near-ring nr.
gap> ZeroSymmetricElements( LibraryNearring( "S3", 25 ) ); [ (), (1,2,3), (1,3,2) ]
63.50 IsAbstractAffineNearring
IsAbstractAffineNearring( nr )
A right near-ring N is called abstract affine if its additive group is abelian and its zero-symmetric elements are exactly its distributive elements.
The function IsAbstractAffineNear-ring returns the according boolean
value true or false.
gap> IsAbstractAffineNearring( LibraryNearring( "S3", 25 ) ); false
63.51 IdempotentElements for near-rings
IdempotentElements( nr )
The function IdempotentElements returns a list containing the
idempotent elements of the multiplicative semigroup of the near-ring nr.
gap> IdempotentElements( LibraryNearring( "S3", 25 ) ); [ (), (2,3) ]
IsBooleanNearring( nr )
A right near-ring N is called boolean if all its elements are idempotent with respect to multiplication.
The function IsBooleanNearring simply checks if all elements
are idempotent and returns the according boolean value
true or false.
gap> IsBooleanNearring( LibraryNearring( "S3", 25 ) ); false
NilpotentElements( nr )
Let (N,+,.) be a near-ring with zero 0. An element n of N is called nilpotent if there is a positive integer k such that nk = 0.
The function NilpotentElements returns a list of sublists of length
2 where the first entry is a nilpotent element n and the second
entry is the smallest k such that nk = 0.
gap> NilpotentElements( LibraryNearring( "V4", 4 ) ); [ [ (), 1 ], [ (3,4), 2 ], [ (1,2), 3 ], [ (1,2)(3,4), 3 ] ]
IsNilNearring( nr )
A near-ring N is called nil if all its elements are nilpotent.
The function IsNilNearring checks if all elements
are nilpotent and returns the according boolean value
true or false.
gap> IsNilNearring( LibraryNearring( "V4", 4 ) ); true
IsNilpotentNearring( nr )
A near-ring N is called nilpotent if there is a positive integer k, s.t. Nk = {0}.
The function IsNilpotentNearring tests if
the near-ring nr is nilpotent and returns the according boolean value
true or false.
gap> IsNilpotentNearring( LibraryNearring( "V4", 4 ) ); true
IsNilpotentFreeNearring( nr )
A near-ring N is called nilpotent free if its only nilpotent element is 0.
The function IsNilpotentFreeNearring checks if
0 is the only nilpotent and returns the according boolean value
true or false.
gap> IsNilpotentFreeNearring( LibraryNearring( "V4", 22 ) ); true
63.57 IsCommutative for near-rings
IsCommutative( nr )
A near-ring (N,+,.) is called commutative if its multiplicative semigroup is commutative.
The function IsCommutative returns
the according value true or false.
gap> IsCommutative( LibraryNearring( "C15", 1235 ) ); false gap> IsCommutative( LibraryNearring( "V4", 13 ) ); true
IsDgNearring( nr )
A near-ring (N,+,.) is called distributively generated (d.g.) if (N,+) is generated additively by the distributive elements of the near-ring.
The function IsDgNearring returns
the according value true or false for a near-ring nr.
gap> IsDgNearring( LibraryNearring( "S3", 25 ) ); false gap> IsDgNearring( LibraryNearring( "S3", 1 ) ); true
IsIntegralNearring( nr )
A near-ring (N,+,.) with zero element 0 is called integral if it has no zero divisors, i.e. the condition ∀ n1,n2: n1 . n2 = 0 ⇒ n1 = 0 \lor n2 = 0 holds.
The function IsIntegralNearring returns
the according value true or false for a near-ring nr.
gap> IsIntegralNearring( LibraryNearring( "S3", 24 ) ); true gap> IsIntegralNearring( LibraryNearring( "S3", 25 ) ); false
IsPrimeNearring( nr )
A near-ring (N,+,.) with zero element 0 is called prime if the ideal { 0 } is a prime ideal.
The function IsPrimeNearring checks if nr is a prime near-ring
by using the condition for all non-zero ideals I,J: I . J ≠
{ 0 } and returns the according value true or false.
gap> IsPrimeNearring( LibraryNearring( "V4", 11 ) ); false
QuasiregularElements( nr )
Let (N,+,.) be a right near-ring. For an element z ∈ N, denote the left ideal generated by the set {n - n. z | n ∈ N} by Lz. An element z of N is called quasiregular if z ∈ Lz.
The function QuasiregularElements returns a list of all
quasiregular elements of a near-ring nr.
gap> QuasiregularElements( LibraryNearring( "V4", 4 ) ); [ (), (3,4), (1,2), (1,2)(3,4) ]
IsQuasiregularNearring( nr )
A near-ring N is called quasiregular if all its elements are quasiregular.
The function IsQuasiregularNearring simply checks if all elements
of the near-ring nr are quasiregular and returns the according
boolean value true or false.
gap> IsQuasiregularNearring( LibraryNearring( "V4", 4 ) ); true
RegularElements( nr )
Let (N,+,.) be a near-ring. An element n of N is called regular if there is an element x such that n. x. n = n.
The function RegularElements returns a list of all
regular elements of a near-ring nr.
gap> RegularElements( LibraryNearring( "V4", 4 ) ); [ () ]
IsRegularNearring( nr )
A near-ring N is called regular if all its elements are regular.
The function IsRegularNearring simply checks if all elements
of the near-ring nr are regular and returns the according
boolean value true or false.
gap> IsRegularNearring( LibraryNearring( "V4", 4 ) ); false
IsPlanarNearring( nr )
Let (N,+,.) be a right near-ring. For a,b ∈ N define the equivalence relation ≡ by a ≡ b: ⇔ ∀ n ∈ N: n. a = n. b. If a ≡ b then a and b are called equivalent multipliers. A near-ring N is called planar if | N/≡ | ≥ 3 and if every equation of the form x. a = x. b + c has a unique solution for two non equivalent multipliers a and b.
The function IsPlanarNearring returns
the according value true or false for a near-ring nr.
Remark\:
this function works only for library near-rings, i.e. near-rings which are
constructed by using the function LibraryNearring.
gap> IsPlanarNearring( LibraryNearring( "V4", 22 ) ); false
IsNearfield( nr )
Let (N,+,.) be a near-ring with zero 0 and denote by N* the set N - {0}. N is a nearfield if (N*,.) is a group.
The function IsNearfield tests if nr has an identity and
if every non-zero element has a multiplicative inverse and returns
the according value true or false.
gap> IsNearfield( LibraryNearring( "V4", 16 ) ); true
LibraryNearringInfo( group\_name, list, string )
This function provides information about the specified library near-rings
in a way similar to how near-rings are presented in the appendix of
Pil83.
The parameter group\_name specifies the name of a group; valid
names are exactly those which are also valid for the function
Library\-Near\-rings (cf. section LibraryNearring).
The parameter list must be a non-empty list of integers defining the classes of near-rings to be printed. Naturally, these integers must all fit into the ranges described in section LibraryNearring for the according groups.
The third parameter string is optional. string must be a string
consisting of one or more (or all) of the following characters:
l, m, i, v, s, e, a.
Per default, (i.e. if this parameter is not specified), the output is
minimal. According to each specified character, the following is added:
c:
m:
i:
l:
r:
v:
s:
e:
a:Examples\:
LibraryNearringInfo( "C3", [ 3 ], "lmivsea" ) will print all
available information on the third class of near-rings on the
group
C3.
LibraryNearringInfo( "C4", [ 1..12 ] ) will provide a minimal output
for all classes of near-rings on C4.
LibraryNearringInfo( "S3", [ 5, 18, 21 ], "mi" ) will print
the minimal information plus the multiplication tables plus the ideals for
the classes 5, 18, and 21 of near-rings on the group S3.
The record of a nearring has the following components:
isDomain, isNearring:true for a near-ring.
isTransformationNearring:true only for transformation near-rings (i.e.
those near-rings that are generated by group transformations by using
the constructor function Nearring in the second form).
generators:
group:
addition, subtraction, multiplication:
gap> nr := Nearring( Transformation( Group( (1,2) ), [2,1] ) );
Nearring( Transformation( Group( (1,2) ), [ 2, 1 ] ) )
gap> e := Elements( nr );
[ Transformation( Group( (1,2) ), [ 1, 1 ] ),
Transformation( Group( (1,2) ), [ 1, 2 ] ),
Transformation( Group( (1,2) ), [ 2, 1 ] ),
Transformation( Group( (1,2) ), [ 2, 2 ] ) ]
gap> nr. addition( e[2], e[3] );
Transformation( Group( (1,2) ), [ 2, 2 ] )
gap> nr.multiplication( e[2], e[4] );
Transformation( Group( (1,2) ), [ 2, 2 ] )
gap> nr.multiplication( e[2], e[3] );
Transformation( Group( (1,2) ), [ 2, 1 ] )
operations:
size, elements, endomorphisms,
automorphisms:63.69 Supportive Functions for Groups
In order to support near-ring calculations, a few functions for groups had to be added to the standard GAP3 group library functions.
63.70 DisplayCayleyTable for groups
DisplayCayleyTable( group )
DisplayCayleyTable prints the Cayley table of the group group. This
function works the same way as for semigroups and near-rings: the
dispatcher function DisplayCayleyTable calls
group.op\-er\-a\-tions.Display\-Ta\-ble which performs the printing.
gap> g := Group( (1,2), (3,4) ); # this is Klein's four group
Group( (1,2), (3,4) )
gap> DisplayCayleyTable( g );
Let:
g0 := ()
g1 := (3,4)
g2 := (1,2)
g3 := (1,2)(3,4)
+ | g0 g1 g2 g3
------------------
g0 | g0 g1 g2 g3
g1 | g1 g0 g3 g2
g2 | g2 g3 g0 g1
g3 | g3 g2 g1 g0
63.71 Endomorphisms for groups
Endomorphisms( group )
Endomorphisms computes all the endomorphisms of the group group.
This function is most essential for computing the near-rings on a group.
The endomorphisms are returned as a list of transformations s.t.
the identity endomorphism is always the last entry in this list. For each
transformation in this list the record component
is\-Group\-En\-do\-mor\-phism is
set to true and if such a transformation is in fact an automorphism
then in
addition the record component
is\-Group\-Auto\-mor\-phism is set to true.
gap> g := Group( (1,2,3) );
Group( (1,2,3) )
gap> Endomorphisms( g );
[ Transformation( Group( (1,2,3) ), [ 1, 1, 1 ] ),
Transformation( Group( (1,2,3) ), [ 1, 3, 2 ] ),
Transformation( Group( (1,2,3) ), [ 1, 2, 3 ] ) ]
63.72 Automorphisms for groups
Automorphisms( group )
Automorphisms computes all the automorphisms of the group group.
The automorphisms are returned as a list of transformations s.t.
the identity automorphism is always the last entry in this list. For each
transformation in this list the record components
is\-Group\-En\-do\-mor\-phism
and is\-Group\-Auto\-mor\-phism are both set to true.
gap> d8 := Group( (1,2,3,4), (2,4) ); # dihedral group of order 8
Group( (1,2,3,4), (2,4) )
gap> a := Automorphisms( d8 );
[ Transformation( Group( (1,2,3,4), (2,4) ), [ 1, 2, 8, 7, 5, 6, 4, 3
] ), Transformation( Group( (1,2,3,4), (2,4) ),
[ 1, 3, 2, 7, 8, 6, 4, 5 ] ), Transformation( Group( (1,2,3,4),
(2,4) ), [ 1, 3, 5, 4, 8, 6, 7, 2 ] ),
Transformation( Group( (1,2,3,4), (2,4) ), [ 1, 5, 3, 7, 2, 6, 4, 8
] ), Transformation( Group( (1,2,3,4), (2,4) ),
[ 1, 5, 8, 4, 2, 6, 7, 3 ] ), Transformation( Group( (1,2,3,4),
(2,4) ), [ 1, 8, 2, 4, 3, 6, 7, 5 ] ),
Transformation( Group( (1,2,3,4), (2,4) ), [ 1, 8, 5, 7, 3, 6, 4, 2
] ), Transformation( Group( (1,2,3,4), (2,4) ),
[ 1, 2, 3, 4, 5, 6, 7, 8 ] ) ]
InnerAutomorphisms( group )
InnerAutomorphisms computes all the inner automorphisms of the group
group.
The inner automorphisms are returned as a list of transformations s.t.
the identity automorphism is always the last entry in this list. For each
transformation in this list the record components
is\-Inner\-Auto\-mor\-phism,
is\-Group\-En\-do\-mor\-phism,
and is\-Group\-Auto\-mor\-phism are all set to true.
gap> i := InnerAutomorphisms( d8 );
[ Transformation( Group( (1,2,3,4), (2,4) ), [ 1, 2, 8, 7, 5, 6, 4, 3
] ), Transformation( Group( (1,2,3,4), (2,4) ),
[ 1, 5, 3, 7, 2, 6, 4, 8 ] ), Transformation( Group( (1,2,3,4),
(2,4) ), [ 1, 5, 8, 4, 2, 6, 7, 3 ] ),
Transformation( Group( (1,2,3,4), (2,4) ), [ 1, 2, 3, 4, 5, 6, 7, 8
] ) ]
63.74 SmallestGeneratingSystem
SmallestGeneratingSystem( group )
SmallestGeneratingSystem computes a smallest generating system of
the group group i.e. a smallest subset of the elements of the group
s.t. the group is generated by this subset.
Remark\: there is a GAP3 standard library function
Smallest\-Generators for
permutation groups. This function computes a generating set of a given
group such that its elements are smallest possible permutations (w.r.t.
the GAP3 internal sorting of permutations).
gap> s5 := SymmetricGroup( 5 ); Group( (1,5), (2,5), (3,5), (4,5) ) gap> SmallestGenerators( s5 ); [ (4,5), (3,4), (2,3), (1,2) ] gap> SmallestGeneratingSystem( s5 ); [ (1,3,5)(2,4), (1,2)(3,4,5) ]
IsIsomorphicGroup( g1, g2 )
IsIsomorphicGroup determines if the groups g1 and g2 are
isomorphic and if so, returns a group homomorphism that is an isomorphism
between these two groups and false otherwise.
gap> g1 := Group( (1,2,3) ); Group( (1,2,3) ) gap> g2 := Group( (7,8,9) ); Group( (7,8,9) ) gap> g1 = g2; false gap> IsIsomorphicGroup( g1, g2 ); GroupHomomorphismByImages( Group( (1,2,3) ), Group( (7,8,9) ), [ (1,2,3) ], [ (7,8,9) ] )
The following variables are predefined as according permutation groups
with a default smallest set of generators:
C2, C3, C4, V4, C5, C6, S3,
C7, C8, C2xC4, C2xC2xC2, D8, Q8,
C9, C3xC3, C10, D10, C11, C12,
C2xC6, D12, A4, T, C13, C14,
D14, C15.
gap> S3; S3 gap> Elements( S3 ); [ (), (2,3), (1,2), (1,2,3), (1,3,2), (1,3) ] gap> IsPermGroup( S3 ); true gap> S3.generators; [ (1,2), (1,2,3) ]
63.77 How to find near-rings with certain properties
The near-ring library files can be used to systematically search for near-rings with (or without) certain properties.
For instance, the function LibraryNearring can be integrated
into a loop or occur as a part of the Filtered or the
First function to get all numbers of classes (or just the first class)
of near-rings on a specified group which have the specified properties.
In what follows, we shall give a few examples how this can be accomplished:
To get the number of the first class of near-rings on the group C6 which have an identity, one could use a command like:
gap> First( [1..60], i -> > Identity( LibraryNearring( "C6", i ) ) <> [ ] ); 28
If we try the same with S3, we will get an error message, indicating that there is no near-ring with identity on S3:
gap> First( [1..39], i -> > Identity( LibraryNearring( "S3", i ) ) <> [ ] ); Error, at least one element of <list> must fulfill <func> in First( [ 1 .. 39 ], function ( i ) ... end ) called from main loop brk> gap>
To get all seven classes of near-rings with identity on the dihedral group D8 of order 8, something like the following will work fine:
gap> l := Filtered( [1..1447], i -> > Identity( LibraryNearring( "D8", i ) ) <> [ ] ); [ 842, 844, 848, 849, 1094, 1096, 1097 ] gap> time; 122490
Note that a search like this may take a few minutes.
Here is another example that provides the class numbers of the four boolean near-rings on D8:
gap> l := Filtered( [1..1447], i -> > IsBooleanNearring( LibraryNearring( "D8", i ) ) ); [ 1314, 1380, 1446, 1447 ]
The search for class numbers of near-rings can also be accomplished in a loop like the following:
gap> l:=[ ];; gap> for i in [1..1447] do > n := LibraryNearring( "D8", i ); > if IsDgNearring( n ) and > not IsDistributiveNearring( n ) then > Add( l, i ); > fi; > od; gap> time; 261580 gap> l; [ 765, 1094, 1098, 1306 ]
This provides a list of those class numbers of near-rings on D8 which are distributively generated but not distributive.
Two or more conditions for library near-rings can also be combined with
or:
gap> l := [ ];;
gap> for i in [1..1447] do
> n := LibraryNearring( "D8", i );
> if Size( ZeroSymmetricElements( n ) ) < 8 or
> Identity( n ) <> [ ] or
> IsIntegralNearring( n ) then
> Add( l, i );
> fi;
> od;
gap> time;
124480
gap> l;
[ 842, 844, 848, 849, 1094, 1096, 1097, 1314, 1315, 1316, 1317, 1318,
1319, 1320, 1321, 1322, 1323, 1324, 1325, 1326, 1327, 1328, 1329,
1330, 1331, 1332, 1333, 1334, 1335, 1336, 1337, 1338, 1339, 1340,
1341, 1342, 1343, 1344, 1345, 1346, 1347, 1348, 1349, 1350, 1351,
1352, 1353, 1354, 1355, 1356, 1357, 1358, 1359, 1360, 1361, 1362,
1363, 1364, 1365, 1366, 1367, 1368, 1369, 1370, 1371, 1372, 1373,
1374, 1375, 1376, 1377, 1378, 1379, 1380, 1381, 1382, 1383, 1384,
1385, 1386, 1387, 1388, 1389, 1390, 1391, 1392, 1393, 1394, 1395,
1396, 1397, 1398, 1399, 1400, 1401, 1402, 1403, 1404, 1405, 1406,
1407, 1408, 1409, 1410, 1411, 1412, 1413, 1414, 1415, 1416, 1417,
1418, 1419, 1420, 1421, 1422, 1423, 1424, 1425, 1426, 1427, 1428,
1429, 1430, 1431, 1432, 1433, 1434, 1435, 1436, 1437, 1438, 1439,
1440, 1441, 1442, 1443, 1444, 1445, 1446, 1447 ]
gap> Length( l );
141
This provides a list of all 141 class numbers of near-rings on D8 which are non-zerosymmetric or have an identity or are integral. (cf. Pil83, pp. 416ff).
The following loop does the same for the near-rings on the quaternion group of order 8, Q8:
gap> l := [ ];; gap> for i in [1..281] do > n := LibraryNearring( "Q8", i ); > if Size( ZeroSymmetricElements( n ) ) < 8 or > Identity( n ) <> [ ] or > IsIntegralNearring( n ) then > Add( l, i ); > fi; > od; gap> time; 17740 gap> l; [ 280, 281 ]
Once a list of class numbers has been computed (in this case here: l),
e.g. the function Library\-Near\-ring\-Info can be used to print
some information about these near-rings:
gap> LibraryNearringInfo( "Q8", l );
----------------------------------------------------------------------
>>> GROUP: Q8
elements: [ n0, n1, n2, n3, n4, n5, n6, n7 ]
addition table:
+ | n0 n1 n2 n3 n4 n5 n6 n7
------------------------------
n0 | n0 n1 n2 n3 n4 n5 n6 n7
n1 | n1 n2 n3 n0 n7 n4 n5 n6
n2 | n2 n3 n0 n1 n6 n7 n4 n5
n3 | n3 n0 n1 n2 n5 n6 n7 n4
n4 | n4 n5 n6 n7 n2 n3 n0 n1
n5 | n5 n6 n7 n4 n1 n2 n3 n0
n6 | n6 n7 n4 n5 n0 n1 n2 n3
n7 | n7 n4 n5 n6 n3 n0 n1 n2
group endomorphisms:
1: [ n0, n0, n0, n0, n0, n0, n0, n0 ]
2: [ n0, n0, n0, n0, n2, n2, n2, n2 ]
3: [ n0, n1, n2, n3, n5, n6, n7, n4 ]
4: [ n0, n1, n2, n3, n6, n7, n4, n5 ]
5: [ n0, n1, n2, n3, n7, n4, n5, n6 ]
6: [ n0, n2, n0, n2, n0, n2, n0, n2 ]
7: [ n0, n2, n0, n2, n2, n0, n2, n0 ]
8: [ n0, n3, n2, n1, n4, n7, n6, n5 ]
9: [ n0, n3, n2, n1, n5, n4, n7, n6 ]
10: [ n0, n3, n2, n1, n6, n5, n4, n7 ]
11: [ n0, n3, n2, n1, n7, n6, n5, n4 ]
12: [ n0, n4, n2, n6, n1, n7, n3, n5 ]
13: [ n0, n4, n2, n6, n3, n5, n1, n7 ]
14: [ n0, n4, n2, n6, n5, n1, n7, n3 ]
15: [ n0, n4, n2, n6, n7, n3, n5, n1 ]
16: [ n0, n5, n2, n7, n1, n4, n3, n6 ]
17: [ n0, n5, n2, n7, n3, n6, n1, n4 ]
18: [ n0, n5, n2, n7, n4, n3, n6, n1 ]
19: [ n0, n5, n2, n7, n6, n1, n4, n3 ]
20: [ n0, n6, n2, n4, n1, n5, n3, n7 ]
21: [ n0, n6, n2, n4, n3, n7, n1, n5 ]
22: [ n0, n6, n2, n4, n5, n3, n7, n1 ]
23: [ n0, n6, n2, n4, n7, n1, n5, n3 ]
24: [ n0, n7, n2, n5, n1, n6, n3, n4 ]
25: [ n0, n7, n2, n5, n3, n4, n1, n6 ]
26: [ n0, n7, n2, n5, n4, n1, n6, n3 ]
27: [ n0, n7, n2, n5, n6, n3, n4, n1 ]
28: [ n0, n1, n2, n3, n4, n5, n6, n7 ]
NEARRINGS:
----------------------------------------------------------------------
280) phi: [ 1, 28, 28, 28, 28, 28, 28, 28 ]; 28; -B----I--P-RW
----------------------------------------------------------------------
281) phi: [ 28, 28, 28, 28, 28, 28, 28, 28 ]; 28; -B----I--P-RW
----------------------------------------------------------------------
63.78 Defining near-rings with known multiplication table
Suppose that for a given group g the multiplication table of a binary
operation * on the elements of g is known such that * is a
near-ring multiplication on g. Then the constructor function Nearring
can be used to input the near-ring specified by g and *.
An example shall illustrate a possibility how this could be accomplished: Take the group S3, which in GAP3 can be defined e.g. by
gap> g := Group( (1,2), (1,2,3) ); Group( (1,2), (1,2,3) )
This group has the following list of elements:
gap> Elements( g ); [ (), (2,3), (1,2), (1,2,3), (1,3,2), (1,3) ]
Let 1 stand for the first element in this list, 2 for the second,
and so on up to 6 which stands for the sixth element in the following
multiplication table:
cccccc} \catcode`\=13
* & 1 & 2 & 3 & 4 & 5 & 6 g with this multiplication can be input by first defining
a multiplication function, say m in the following way:
gap> m := function( x, y ) > local elms, table; > elms := Elements( g ); > table := [ [ 1, 1, 1, 1, 1, 1 ], > [ 2, 2, 2, 2, 2, 2 ], > [ 2, 2, 6, 3, 6, 3 ], > [ 1, 1, 5, 4, 5, 4 ], > [ 1, 1, 4, 5, 4, 5 ], > [ 2, 2, 3, 6, 3, 6 ] ]; > > return elms[ table[Position( elms, x )][Position( elms, y )] ]; > end; function ( x, y ) ... end
Then the near-ring can be constructed by calling Nearring with the
parameters g and m:
gap> n := Nearring( g, m );
Nearring( Group( (1,2), (1,2,3) ), function ( x, y )
local elms, table;
elms := Elements( g );
table := [ [ 1, 1, 1, 1, 1, 1 ], [ 2, 2, 2, 2, 2, 2 ],
[ 2, 2, 6, 3, 6, 3 ], [ 1, 1, 5, 4, 5, 4 ],
[ 1, 1, 4, 5, 4, 5 ], [ 2, 2, 3, 6, 3, 6 ] ];
return elms[table[Position( elms, x )][Position( elms, y )]];
end )
Previous Up Nextgap3-jm