6 Special Classes of Semigroup
In this chapter functions for creating certain semigroups are given.
6.1 Some Classes of Semigroup
6.1-1 SingularSemigroup
> SingularSemigroup ( n ) | ( function ) |
creates the semigroup of singular transformations of degree n
. That is, the semigroup of all transformations of the n
-element set {1,2,...,n}
that are non-invertible.
This semigroup is known to be regular, idempotent generated (satisfies IsSemiBand
(5.2-10)), and has size n^n-n!
.
The generators used here are the idempotents of rank n-1
, so there are n(n-1)
generators in total.
gap> S:=SingularSemigroup(6);
<semigroup with 30 generators>
gap> Size(S);
45936
gap> IsRegularSemigroup(S);
true
gap> IsSemiBand(S);
true
|
6.1-2 OrderPreservingSemigroup
> OrderPreservingSemigroup ( n ) | ( operation ) |
returns the semigroup of order preserving transformations of the n
- element set {1,2,...,n}
. That is, the mappings f
such that i
is at most j
implies f(i)
is at most f(j)
for all i,j
in {1,2,...,n}
.
This semigroup is known to be regular, idempotent generated (satisfies IsSemiBand
(5.2-10)), and has size Binomial(2*n-1, n-1)
. The generators and relations used here are those specified by Aizenstat as given in [AR00] and [GH92]. That is, OrderPreservingSemigroup(n)
has the 2n-2
idempotent generators
u_2:=Transformation([2,2,3,..,n]), u_3:=Transformation([1,3,3,..,n]), ...
v_n-2:=Transformation([1,2,2,...,n]), v_n-3:=Transformation
([1,2,3,3,...,n]), ...
|
and the presentation obtained using IsomorphismFpMonoid
(7.7-4) has relations
v_n−i u_i = u_i v_n−i+1 (i=2,..., n−1)
u_n−i v_i = v_i u_n−i+1 (i=2,...,n−1),
v_n−i u_i = u_i (i=1,...,n−1),
u_n−i v_i = v_i (i=1,...,n−1),
u_i v_j = v_j u_i (i,j=1,...,n−1; not j=n-i, n-i+1),
u_1 u_2 u_1 = u_1 u_2,
v_1 v_2 v_1 = v_1 v_2.
|
gap> S:=OrderPreservingSemigroup(5);
<monoid with 8 generators>
gap> IsSemiBand(S);
true
gap> IsRegularSemigroup(S);
true
gap> Size(S)=Binomial(2*5-1, 5-1);
true
|
6.1-3 KiselmanSemigroup
> KiselmanSemigroup ( n ) | ( operation ) |
returns the Kiselman semigroup with n
generators. That is, the semigroup defined in [KM05] with the presentation
<a_1, a_2, ... , a_n | a_i^2=a_i (i=1,...n) a_ia_ja_i=a_ja_ia_j=a_ja_i
(1<=i< j<=n)>.
gap> S:=KiselmanSemigroup(3);
<fp monoid on the generators [ m1, m2, m3 ]>
gap> Elements(S);
[ <identity ...>, m1, m2, m3, m1*m2, m1*m3, m2*m1, m2*m3, m3*m1, m3*m2,
m1*m2*m3, m1*m3*m2, m2*m1*m3, m2*m3*m1, m3*m1*m2, m3*m2*m1, m2*m1*m3*m2,
m2*m3*m1*m2 ]
gap> Idempotents(S);
[ 1, m1, m2*m1, m3*m2*m1, m3*m1, m2, m3*m2, m3 ]
gap> SetInfoLevel(InfoAutos, 0);
gap> AutomorphismGroup(Range(IsomorphismTransformationSemigroup(S)));
<group of size 1 with 1 generators>
|
6.2 Zero Groups and Zero Semigroups
6.2-1 ZeroSemigroup
> ZeroSemigroup ( n ) | ( operation ) |
returns the zero semigroup S
of order n
. That is, the unique semigroup up to isomorphism of order n
such that there exists an element 0
in S
such that xy=0
for all x,y
in S
.
A zero semigroup is generated by its nonzero elements, has trivial Green's relations, and is not regular.
gap> S:=ZeroSemigroup(10);
<zero semigroup with 10 elements>
gap> Size(S);
10
gap> GeneratorsOfSemigroup(S);
[ z1, z2, z3, z4, z5, z6, z7, z8, z9 ]
gap> Idempotents(S);
[ 0 ]
gap> IsZeroSemigroup(S);
true
gap> GreensRClasses(S);
[ {0}, {z1}, {z2}, {z3}, {z4}, {z5}, {z6}, {z7}, {z8}, {z9} ]
|
6.2-2 ZeroSemigroupElt
> ZeroSemigroupElt ( n ) | ( operation ) |
returns the zero semigroup element zn
where n
is a positive integer and z0
is the multiplicative zero.
The zero semigroup element zn
belongs to every zero semigroup with degree at least n
.
gap> ZeroSemigroupElt(0);
0
gap> ZeroSemigroupElt(4);
z4
|
6.2-3 ZeroGroup
> ZeroGroup ( G ) | ( operation ) |
returns the monoid obtained by adjoining a zero element to G
. That is, the monoid S
obtained by adjoining a zero element 0
to G
with g0=0g=0
for all g
in S
.
gap> S:=ZeroGroup(CyclicGroup(10));
<zero group with 3 generators>
gap> IsRegularSemigroup(S);
true
gap> Elements(S);
[ 0, <identity> of ..., f1, f2, f1*f2, f2^2, f1*f2^2, f2^3, f1*f2^3, f2^4,
f1*f2^4 ]
gap> GreensRClasses(S);
[ {<adjoined zero>}, {ZeroGroup(<identity> of ...)} ]
|
6.2-4 ZeroGroupElt
> ZeroGroupElt ( g ) | ( operation ) |
returns the zero group element corresponding to the group element g
. The function ZeroGroupElt
is only used to create an object in the correct category during the creation of a zero group using ZeroGroup
(6.2-3).
gap> ZeroGroupElt(Random(DihedralGroup(10)));;
gap> IsZeroGroupElt(last);
true
|
6.2-5 UnderlyingGroupOfZG
> UnderlyingGroupOfZG ( ZG ) | ( attribute ) |
returns the group from which the zero group ZG
was constructed.
gap> G:=DihedralGroup(10);;
gap> S:=ZeroGroup(G);;
gap> UnderlyingGroupOfZG(S)=G;
true
|
6.2-6 UnderlyingGroupEltOfZGElt
> UnderlyingGroupEltOfZGElt ( g ) | ( attribute ) |
returns the group element from which the zero group element g
was constructed.
gap> G:=DihedralGroup(10);;
gap> S:=ZeroGroup(G);;
gap> Elements(S);
[ 0, <identity> of ..., f1, f2, f1*f2, f2^2, f1*f2^2, f2^3, f1*f2^3, f2^4,
f1*f2^4 ]
gap> x:=last[5];
f1*f2
gap> UnderlyingGroupEltOfZGElt(x);
f1*f2
|
6.3 Random Semigroups
6.3-1 RandomMonoid
> RandomMonoid ( m, n ) | ( function ) |
returns a random transformation monoid of degree n
with m
generators.
gap> S:=RandomMonoid(5,5);
<semigroup with 5 generators>
|
6.3-2 RandomSemigroup
> RandomSemigroup ( m, n ) | ( function ) |
returns a random transformation semigroup of degree n
with m
generators.
gap> S:=RandomSemigroup(5,5);
<semigroup with 5 generators>
|
6.3-3 RandomReesMatrixSemigroup
> RandomReesMatrixSemigroup ( i, j, deg ) | ( function ) |
returns a random Rees matrix semigroup with an i
by j
sandwich matrix over a permutation group with maximum degree deg
.
gap> S:=RandomReesMatrixSemigroup(4,5,5);
Rees Matrix Semigroup over Group([ (1,5,3,4), (1,3,4,2,5) ])
[ [ (), (), (), (), () ],
[ (), (1,3,5)(2,4), (1,3,5)(2,4), (1,5,3), (1,5,3) ],
[ (), (1,3,5), (1,5,3)(2,4), (), (1,5,3) ],
[ (), (), (1,3,5)(2,4), (2,4), (2,4) ] ]
|
6.3-4 RandomReesZeroMatrixSemigroup
> RandomReesZeroMatrixSemigroup ( i, j, deg ) | ( function ) |
returns a random Rees 0
-matrix semigroup with an i
by j
sandwich matrix over a permutation group with maximum degree deg
.
gap> S:=RandomReesZeroMatrixSemigroup(2,3,2);
Rees Zero Matrix Semigroup over <zero group with 2 generators>
gap> SandwichMatrixOfReesZeroMatrixSemigroup(S);
[ [ 0, (), 0 ], [ 0, 0, 0 ] ]
|