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 ] ]
|