\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 ] )
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 ] ]
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
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
:
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( t_{1}, ..., t_{n} )
TransformationSemigroup( [ t_{1}, ..., t_{n} ] )
When called in this form, the constructor function
Trans\-for\-mation\-Semi\-group
returns the
transformation semigroup generated by the transformations
t_{1}, ..., t_{n}. 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
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
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
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 ] ) ]
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 . S^{1} := a . S ∪ {a} is called the principal right ideal generated by a. Analogously, S^{1} . a := S . a ∪ {a} is called the principal left ideal generated by a and S^{1} . a . S^{1} := 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: ⇔ S^{1} . a = S^{1} . b i.e. a and b generate the same principal left ideal. Similarly: (a,b) ∈ R: ⇔ a . S^{1} = b . S^{1} i.e. a and b generate the same principal right ideal and (a,b) ∈ J: ⇔ S^{1} . a . S^{1} = S^{1} . b . S^{1} 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
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. ∀ n_{1},n_{2},n_{3} ∈ N: (n_{1}+n_{2}). n_{3} = n_{1}. n_{3}+n_{2}. n_{3}.
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, t_{1}, t_{2} as t_{1} . t_{2} := t_{2} * t_{1}.
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( t_{1}, ..., t_{n} )
Nearring( [t_{1}, ..., t_{n}] )
In this form the constructor function Near\-ring
returns the near-ring
generated by the group
transformations t_{1},...,t_{n}. 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
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 )
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
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 ] ) ]
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 = n_{1} . (n_{2} + n_{3} ) - (n_{1} . n_{2} + n_{1} . n_{3} ) for some elements n_{1}, n_{2}, n_{3} 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. ∀ n_{1}, n_{2} ∈ N: d . (n_{1} + n_{2} ) = d . n_{1} + d . n_{2}.
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) ]
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
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 n^{k} = 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 n^{k} = 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. N^{k} = {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
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 ∀ n_{1},n_{2}: n_{1} . n_{2} = 0 ⇒ n_{1} = 0 \lor n_{2} = 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 L_{z}. An element z of N is called quasiregular if z ∈ L_{z}.
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
C_{3}.
LibraryNearringInfo( "C4", [ 1..12 ] )
will provide a minimal output
for all classes of near-rings on C_{4}.
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 S_{3}.
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
:In order to support near-ring calculations, a few functions for groups had to be added to the standard GAP3 group library functions.
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
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 ] ) ]
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 ] ) ]
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) ]
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 C_{6} 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 S_{3}, we will get an error message, indicating that there is no near-ring with identity on S_{3}:
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 D_{8} 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 D_{8}:
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 D_{8} 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 D_{8} 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, Q_{8}:
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 ----------------------------------------------------------------------
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 S_{3}, 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 Next
gap3-jm