[MathJax on]

2 Creating semigroups and monoids

In this chapter we describe the various ways that semigroups and monoids can be created in Semigroups, the options that are available at the time of creation, and describe some standard examples available in Semigroups.

Any semigroup created before Semigroups has been loaded must be recreated after Semigroups is loaded so that the options record (described in Section 2.3) is defined. Almost all of the functions and methods provided by Semigroups, including those methods for existing GAP library functions, will return an error when applied to a semigroup created before Semigroups is loaded.

2.1 Random semigroups

2.1-1 RandomInverseMonoid

Returns: An inverse monoid or semigroup.

Returns a random inverse monoid or semigroup of partial permutations with degree at most n with m generators.

gap> S := RandomInverseSemigroup(10, 10);                                
<inverse partial perm semigroup of rank 10 with 10 generators>
gap> S := RandomInverseMonoid(10, 10);   
<inverse partial perm monoid of rank 10 with 10 generators>

2.1-2 RandomTransformationMonoid

Returns: A transformation semigroup or monoid.

Returns a random transformation monoid or semigroup of at most degree n with m generators.

gap> S := RandomTransformationMonoid(5, 5);
<transformation monoid of degree 5 with 5 generators>
gap> S := RandomTransformationSemigroup(5, 5);
<transformation semigroup of degree 5 with 5 generators>

2.1-3 RandomPartialPermMonoid

Returns: A partial perm semigroup or monoid.

Returns a random partial perm monoid or semigroup of degree at most n with m generators.

gap> S:=RandomPartialPermSemigroup(5, 5);
<partial perm semigroup of rank 4 with 5 generators>
gap> S:=RandomPartialPermMonoid(5, 5);
<partial perm monoid of degree 5 with 5 generators>

2.1-4 RandomBinaryRelationMonoid

Returns: A semigroup or monoid of binary relations.

Returns a random monoid or semigroup of binary relations on n points with m generators.

gap> RandomBinaryRelationSemigroup(5,5);
<semigroup with 5 generators>
gap> RandomBinaryRelationMonoid(5,5);   
<monoid with 5 generators>

2.1-5 RandomBipartitionSemigroup

Returns: A bipartition semigroup or monoid.

Returns a random monoid or semigroup of bipartition on n points with m generators.

gap> RandomBipartitionMonoid(5, 5);
<bipartition monoid of degree 5 with 5 generators>
gap> RandomBipartitionSemigroup(5, 5);
<bipartition semigroup of degree 5 with 5 generators>

2.1-6 RandomMatrixSemigroup

Returns: A matrix semigroup or monoid.

Returns a random semigroup or monoid of n-by-n matrices over the ring R with m generators.

The optional fourth argument ranks is expected to be a list of permissible ranks for the generators. For any generator the rank is chosen uniformly randomly from the list of permissible ranks. This allows for creating more interesting random matrix semigroups and monoids. Without the ranks argument there is a very high probability that the semigroups returned by this function are full matrix monoids over the base ring.

gap> RandomMatrixSemigroup(GF(25),5,5);
<semigroup of 5x5 matrices over GF(5^2) with 5 generators>
gap> RandomMatrixSemigroup(GF(4),2,5,[1,2]);
<semigroup of 5x5 matrices over GF(2^2) with 2 generators>

2.2 New semigroups from old

2.2-1 ClosureInverseSemigroup

Returns: An inverse semigroup or monoid.

This function returns the inverse semigroup or monoid generated by the inverse semigroup S and the collection of elements coll after first removing duplicates and elements in coll that are already in S. In most cases, the new semigroup knows at least as much information about its structure as was already known about that of S.

If present, the optional third argument opts should be a record containing the values of the options for the inverse semigroup being created; these options are described in Section 2.3.

gap> S:=InverseMonoid(
> PartialPerm( [ 1, 2, 3, 5, 6, 7, 8 ], [ 5, 9, 10, 6, 3, 8, 4 ] ),
> PartialPerm( [ 1, 2, 4, 7, 8, 9 ], [ 10, 7, 8, 5, 9, 1 ] ) );;
gap> f:=PartialPerm(
> [ 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 18, 19, 20 ],
> [ 5, 1, 7, 3, 10, 2, 12, 14, 11, 16, 6, 9, 15 ]);;
gap> S:=ClosureInverseSemigroup(S, f);
<inverse partial perm semigroup of rank 19 with 4 generators>
gap> Size(S);
9744
gap> T:=Idempotents(SymmetricInverseSemigroup(10));;
gap> S:=ClosureInverseSemigroup(S, T);
<inverse partial perm semigroup of rank 19 with 854 generators>
gap> S:=InverseSemigroup(SmallGeneratingSet(S));
<inverse partial perm semigroup of rank 19 with 14 generators>

2.2-2 ClosureSemigroup

Returns: A semigroup or monoid.

This function returns the semigroup or monoid generated by the semigroup S and the collection of elements coll after removing duplicates and elements from coll that are already in S. In most cases, the new semigroup knows at least as much information about its structure as was already known about that of S.

If present, the optional third argument opts should be a record containing the values of the options for the semigroup being created as described in Section 2.3.

gap> gens:=[ Transformation( [ 2, 6, 7, 2, 6, 1, 1, 5 ] ), 
>  Transformation( [ 3, 8, 1, 4, 5, 6, 7, 1 ] ), 
>  Transformation( [ 4, 3, 2, 7, 7, 6, 6, 5 ] ), 
>  Transformation( [ 7, 1, 7, 4, 2, 5, 6, 3 ] ) ];;
gap> S:=Monoid(gens[1]);;
gap> for i in [2..4] do S:=ClosureSemigroup(S, gens[i]); od;
gap> S;
<transformation monoid of degree 8 with 4 generators>
gap> Size(S);
233606
gap> gens:=
> [ NewMatrixOverFiniteField(IsPlistMatrixOverFiniteFieldRep,GF(25),2,
>    [ [ Z(5^2), Z(5^2)^13 ], [ 0*Z(5), Z(5^2)^14 ] ]), 
>  NewMatrixOverFiniteField(IsPlistMatrixOverFiniteFieldRep,GF(25),2,
>    [ [ Z(5^2)^21, Z(5)^0 ], [ Z(5)^0, 0*Z(5) ] ]), 
>  NewMatrixOverFiniteField(IsPlistMatrixOverFiniteFieldRep,GF(25),2,
>    [ [ Z(5^2)^23, Z(5^2)^5 ], [ Z(5^2)^20, Z(5^2)^20 ] ]) ];;
gap> S := Semigroup(gens[1]);
<semigroup of 2x2 matrices over GF(5^2) with 1 generator>
gap> Size(S);
24
gap> S := ClosureSemigroup(S, gens[2]);
<semigroup of 2x2 matrices over GF(5^2) with 2 generators>
gap> Size(S);
124800
gap> S := ClosureSemigroup(S, gens[3]);
<semigroup of 2x2 matrices over GF(5^2) with 3 generators>
gap> Size(S);
374400

2.2-3 SubsemigroupByProperty

Returns: A semigroup.

SubsemigroupByProperty returns the subsemigroup of the semigroup S generated by those elements of S fulfilling func (which should be a function returning true or false).

If no elements of S fulfil func, then fail is returned.

If the optional third argument limit is present and a positive integer, then once the subsemigroup has at least limit elements the computation stops.

gap> func := function(f) return 1 ^ f <> 1 and
> ForAll([1..DegreeOfTransformation(f)], y-> y = 1 or y ^ f = y); end;
function( f ) ... end
gap> T := SubsemigroupByProperty(FullTransformationSemigroup(3), func);
<transformation semigroup of size 2, degree 3 with 2 generators>
gap> T := SubsemigroupByProperty(FullTransformationSemigroup(4), func);
<transformation semigroup of size 3, degree 4 with 3 generators>
gap> T := SubsemigroupByProperty(FullTransformationSemigroup(5), func);
<transformation semigroup of size 4, degree 5 with 4 generators>

2.2-4 InverseSubsemigroupByProperty

Returns: An inverse semigroup.

InverseSubsemigroupByProperty returns the inverse subsemigroup of the inverse semigroup S generated by those elements of S fulfilling func (which should be a function returning true or false).

If no elements of S fulfil func, then fail is returned.

If the optional third argument limit is present and a positive integer, then once the subsemigroup has at least limit elements the computation stops.

gap> IsIsometry:=function(f)
> local n, i, j, k, l;
>  n:=RankOfPartialPerm(f);
>  for i in [1..n-1] do
>    k:=DomainOfPartialPerm(f)[i];
>    for j in [i+1..n] do
>      l:=DomainOfPartialPerm(f)[j];
>      if not AbsInt(k^f-l^f)=AbsInt(k-l) then
>        return false;
>      fi;
>    od;
>  od;
>  return true;
> end;;
gap> S:=InverseSubsemigroupByProperty(SymmetricInverseSemigroup(5),
> IsIsometry);;
gap> Size(S);
142

2.3 Options when creating semigroups

When using any of the functions:

• InverseSemigroup (Reference: InverseSemigroup),

• InverseMonoid (Reference: InverseMonoid),

• Semigroup (Reference: Semigroup),

• Monoid (Reference: Monoid),

• SemigroupByGenerators (Reference: SemigroupByGenerators),

• MonoidByGenerators (Reference: MonoidByGenerators),

• ClosureInverseSemigroup (2.2-1),

• ClosureSemigroup (2.2-2),

• SemigroupIdeal (3.1-1)

a record can be given as an optional final argument. The components of this record specify the values of certain options for the semigroup being created. A list of these options and their default values is given below.

Assume that S is the semigroup created by one of the functions given above and that either: S is generated by a collection gens of transformations, partial permutations, Rees 0-matrix semigroup elements, or bipartitions; or S is an ideal of such a semigroup.

acting

this component should be true or false. In order for a semigroup to use the methods in Semigroups it must satisfy IsActingSemigroup. By default any semigroup or monoid of transformations, partial permutations, Rees 0-matrix elements, or bipartitions satisfies IsActingSemigroup. From time to time, it might be preferable to use the exhaustive algorithm in the GAP library to compute with a semigroup. If this is the case, then the value of this component can be set false when the semigroup is created. Following this none of the methods in the Semigroups package will be used to compute anything about the semigroup.

regular

this component should be true or false. If it is known a priori that the semigroup S being created is a regular semigroup, then this component can be set to true. In this case, S knows it is a regular semigroup and can take advantage of the methods for regular semigroups in Semigroups. It is usually much more efficient to compute with a regular semigroup that to compute with a non-regular semigroup.

If this option is set to true when the semigroup being defined is not regular, then the results might be unpredictable.

The default value for this option is false.

hashlen

this component should be a positive integer, which roughly specifies the lengths of the hash tables used internally by Semigroups. Semigroups uses hash tables in several fundamental methods. The lengths of these tables are a compromise between performance and memory usage; larger tables provide better performance for large computations but use more memory. Note that it is unlikely that you will need to specify this option unless you find that GAP runs out of memory unexpectedly or that the performance of Semigroups is poorer than expected. If you find that GAP runs out of memory unexpectedly, or you plan to do a large number of computations with relatively small semigroups (say with tens of thousands of elements), then you might consider setting hashlen to be less than the default value of 25013 for each of these semigroups. If you find that the performance of Semigroups is unexpectedly poor, or you plan to do a computation with a very large semigroup (say, more than 10 million elements), then you might consider setting hashlen to be greater than the default value of 25013.

You might find it useful to set the info level of the info class InfoOrb to 2 or higher since this will indicate when hash tables used by Semigroups are being grown; see SetInfoLevel (Reference: SetInfoLevel).

small

if this component is set to true, then Semigroups will compute a small subset of gens that generates S at the time that S is created. This will increase the amount of time required to create S substantially, but may decrease the amount of time required for subsequent calculations with S. If this component is set to false, then Semigroups will return the semigroup generated by gens without modifying gens. The default value for this component is false.

This option is ignored when passed to ClosureSemigroup (2.2-2) or ClosureInverseSemigroup (2.2-1).

gap> S := Semigroup(Transformation( [ 1, 2, 3, 3 ] ), 
> rec(hashlen:=100003, small:=false));
<commutative transformation semigroup of degree 4 with 1 generator>

The default values of the options described above are stored in a global variable named SemigroupsOptionsRec (2.3-1). If you want to change the default values of these options for a single GAP session, then you can simply redefine the value in GAP. For example, to change the option small from the default value of false use:

gap> SemigroupsOptionsRec.small:=true;
true

If you want to change the default values of the options stored in SemigroupsOptionsRec (2.3-1) for all GAP sessions, then you can edit these values in the file semigroups/gap/options.g.

2.3-1 SemigroupsOptionsRec

This global variable is a record whose components contain the default values of certain options for transformation semigroups created after Semigroups has been loaded. A description of these options is given above in Section 2.3.

The value of SemigroupsOptionsRec is defined in the file semigroups/gap/options.g as:

rec( acting := true, hashlen := rec( L := 25013, M := 6257, S :=
         251 ), regular := false, small := false )

2.4 Changing the representation of a semigroup

In addition, to the library functions

• IsomorphismReesMatrixSemigroup (Reference: IsomorphismReesMatrixSemigroup),

• AntiIsomorphismTransformationSemigroup (Reference: AntiIsomorphismTransformationSemigroup),

• IsomorphismTransformationSemigroup (Reference: IsomorphismTransformationSemigroup),

• IsomorphismPartialPermSemigroup (Reference: IsomorphismPartialPermSemigroup),

there are several methods for changing the representation of a semigroup in Semigroups. There are also methods for the operations given above for the types of semigroups defined in Semigroups which are not mentioned in the reference manual.

2.4-1 AsTransformationSemigroup

Returns: A semigroup.

AsTransformationSemigroup(S) is just shorthand for Range(IsomorphismTransformationSemigroup(S)), when S is a semigroup; see IsomorphismTransformationSemigroup (Reference: IsomorphismTransformationSemigroup) for more details.

The operations:

• AsPartialPermSemigroup;

• AsBipartitionSemigroup;

• AsBlockBijectionSemigroup;

are analogous to AsTransformationSemigroup.

AsMatrixSemigroup returns the range of an isomorphism from S to a semigroup of matrices over GF(2). If the optional argument F is present, then AsMatrixSemigroup returns an isomorphic semigroup over the finite field F.

gap> S := Semigroup( [ Bipartition( [ [ 1, 2 ], [ 3, 6, -2 ], 
> [ 4, 5, -3, -4 ], [ -1, -6 ], [ -5 ] ] ), 
> Bipartition( [ [ 1, -4 ], [ 2, 3, 4, 5 ], [ 6 ], [ -1, -6 ], 
> [ -2, -3 ], [ -5 ] ] ) ] );
<bipartition semigroup of degree 6 with 2 generators>
gap> AsTransformationSemigroup(S);
<transformation semigroup of degree 12 with 2 generators>
gap> AsMatrixSemigroup(S);
<semigroup of 12x12 matrices over GF(2) with 2 generators>
gap> T := Semigroup(Transformation([2, 2, 3]), Transformation([3, 1, 3]));
<transformation semigroup of degree 3 with 2 generators>
gap> S := AsMatrixSemigroup(T, GF(5));
<semigroup of 3x3 matrices over GF(5) with 2 generators>
gap> Size(S);
5

2.4-2 IsomorphismPermGroup

Returns: An isomorphism.

If the semigroup S is mathematically a group, so that it satisfies IsGroupAsSemigroup (4.6-6), then IsomorphismPermGroup returns an isomorphism to a permutation group.

If S is not a group then an error is given.

gap> S := Semigroup(Transformation([2, 2, 3, 4, 6, 8, 5, 5]),
>                   Transformation([3, 3, 8, 2, 5, 6, 4, 4]));;
gap> IsGroupAsSemigroup(S);
true
gap> Range(IsomorphismPermGroup(S)); 
Group([ (5,6,8), (2,3,8,4) ])
gap> StructureDescription(Range(IsomorphismPermGroup(S)));
"S6"
gap> S := Range(IsomorphismPartialPermSemigroup(SymmetricGroup(4)));
<inverse partial perm semigroup of rank 4 with 2 generators>
gap> IsomorphismPermGroup(S);
MappingByFunction( <partial perm group of rank 4 with 2 generators>
, Group([ (1,2,3,4), (1,
2) ]), <Attribute "AsPermutation">, function( x ) ... end )
gap> G := GroupOfUnits(PartitionMonoid(4));
<bipartition group of degree 4 with 2 generators>
gap> StructureDescription(G);
"S4"
gap> iso := IsomorphismPermGroup(G);  
MappingByFunction( <bipartition group of degree 4 with 2 generators>
, S4, <Attribute "AsPermutation">, function( x ) ... end )
gap> RespectsMultiplication(iso);
true
gap> inv := InverseGeneralMapping(iso);;
gap> ForAll(G, x-> (x^iso)^inv=x);
true
gap> ForAll(G, x-> ForAll(G, y-> (x*y)^iso=x^iso*y^iso));
true

2.4-3 IsomorphismBipartitionSemigroup

Returns: An isomorphism.

If S is a semigroup, then IsomorphismBipartitionSemigroup returns an isomorphism from S to a bipartition semigroup. When S is a transformation semigroup, partial permutation semigroup, or a permutation group, on n points, IsomorphismBipartitionSemigroup returns the natural embedding of S into the partition monoid on n points. When S is a generic semigroup, this funciton returns the right regular representation of S acting on S with an identity adjoined.

See AsBipartition (5.3-1).

gap> S := InverseSemigroup(
> PartialPerm( [ 1, 2, 3, 6, 8, 10 ], 
>              [ 2, 6, 7, 9, 1, 5 ] ), 
> PartialPerm( [ 1, 2, 3, 4, 6, 7, 8, 10 ], 
>              [ 3, 8, 1, 9, 4, 10, 5, 6 ] ) );;
gap> IsomorphismBipartitionSemigroup(S);
MappingByFunction( <inverse partial perm semigroup of rank 10 with 2 
 generators>, <inverse bipartition semigroup of degree 10 with 2 
 generators>, function( x ) ... end, <Operation "AsPartialPerm"> )
gap> ForAll(Generators(Range(last)), IsPartialPermBipartition);
true

2.4-4 IsomorphismBlockBijectionSemigroup

Returns: An isomorphism.

If S is a partial perm semigroup on n points, then this function returns the embedding of S into a subsemigroup of the dual symmetric inverse monoid on n+1 points given by the FitzGerald-Leech Theorem [FL98].

See AsBlockBijection (5.3-2) for more details.

gap> S := SymmetricInverseMonoid(4);                                    
<symmetric inverse monoid of degree 4>
gap> IsomorphismBlockBijectionSemigroup(S);
MappingByFunction( <symmetric inverse monoid of degree 4>, 
<inverse bipartition monoid of degree 5 with 3 generators>
 , function( x ) ... end, function( x ) ... end )
gap> Size(Range(last));
209
gap> S:=Semigroup( PartialPerm( [ 1, 2 ], [ 3, 1 ] ), 
> PartialPerm( [ 1, 2, 3 ], [ 1, 3, 4 ] ) );;
gap> IsomorphismBlockBijectionSemigroup(S);
MappingByFunction( <partial perm semigroup of rank 3 with 2 
 generators>, <bipartition semigroup of degree 5 with 2 generators>
 , function( x ) ... end, function( x ) ... end )

2.4-5 IsomorphismMatrixSemigroup

Returns: An isomorphism to a matrix semigroup.

This attribute contains an isomorphism from the semigroup S to a matrix semigroup. Currently this is done by taking a standard basis of a vector space suitable dimension and acting on this basis over the field F if F is given, and over GF(2) if F is not given. This will not give an optimal matrix semigroup representation of S.

gap> T := Semigroup(Transformation([2, 2, 3]), Transformation([3, 1, 3]));
<transformation semigroup of degree 3 with 2 generators>
gap> iso := IsomorphismMatrixSemigroup(T);
MappingByFunction( <transformation semigroup of degree 3 with 2 
 generators>, <semigroup of 3x3 matrices over GF(2)
 with 2 generators>, function( x ) ... end, function( x ) ... end )
gap> Size(Range(iso));
5

2.5 Standard examples

In this section, we describe the operations in Semigroups that can be used to creating semigroups belonging to several standard classes of example. See Chapter 5 for more information about semigroups of bipartitions.

2.5-1 EndomorphismsPartition

Returns: A transformation monoid.

If list is a list of positive integers, then EndomorphismsPartition returns a monoid of endomorphisms preserving a partition of [1..Sum(list)] with a part of length list[i] for every i. For example, if list=[1,2,3], then EndomorphismsPartition returns the monoid of endomorphisms of the partition [[1],[2,3],[4,5,6]].

If f is a transformation of [1..n], then it is an endomorphism of a partition P on [1..n] if (i,j) in P implies that (i^f, j^f) is in P.

EndomorphismsPartition returns a monoid with a minimal size generating set, as described in [ABMS14].

gap> S:=EndomorphismsPartition([3,3,3]);
<transformation semigroup of degree 9 with 4 generators>
gap> Size(S);
531441

2.5-2 PartitionMonoid

Returns: A bipartition monoid.

If n is a positive integer, then this operation returns the partition monoid of degree n which is the monoid consisting of all the bipartitions of degree n.

SingularPartitionMonoid returns the ideal of the partition monoid consisting of the non-invertible elements (i.e. those not in the group of units).

gap> S:=PartitionMonoid(5);
<regular bipartition monoid of degree 5 with 4 generators>
gap> Size(S);
115975

2.5-3 PlanarPartitionMonoid

Returns: A bipartition monoid.

If n is a positive integer, then this operation returns the planar partition monoid of degree n which is the monoid consisting of all the planar bipartitions of degree n (planar bipartitions are defined in Chapter 5).

SingularPlanarPartitionMonoid returns the ideal of the planar partition monoid consisting of the non-invertible elements (i.e. those not in the group of units).

gap> S := PlanarPartitionMonoid(5);
<regular bipartition monoid of degree 5 with 9 generators>
gap> Size(S);
16796

2.5-4 BrauerMonoid

Returns: A bipartition monoid.

If n is a positive integer, then this operation returns the Brauer monoid of degree n. The Brauer monoid is the subsemigroup of the partition monoid consisiting of those bipartitions where the size of every block is 2.

SingularBrauerMonoid returns the ideal of the Brauer monoid consisting of the non-invertible elements (i.e. those not in the group of units), when n is at least 2.

gap> S:=BrauerMonoid(4);
<regular bipartition monoid of degree 4 with 3 generators>
gap> IsSubsemigroup(S, JonesMonoid(4));
true
gap> Size(S);
105
gap> SingularBrauerMonoid(8);
<regular bipartition semigroup ideal of degree 8 with 1 generator>

2.5-5 JonesMonoid

Returns: A bipartition monoid.

If n is a positive integer, then this operation returns the Jones monoid of degree n. The Jones monoid is the subsemigroup of the Brauer monoid consisting of those bipartitions with a planar diagram. The Jones monoid is sometimes referred to as the Temperley-Lieb monoid.

SingularJonesMonoid returns the ideal of the Jones monoid consisting of the non-invertible elements (i.e. those not in the group of units), when n is at least 2.

gap> S:=JonesMonoid(4);
<regular bipartition monoid of degree 4 with 3 generators>
gap> SingularJonesMonoid(8);
<regular bipartition semigroup ideal of degree 8 with 1 generator>

2.5-6 PartialTransformationSemigroup

Returns: A transformation monoid.

If n is a positive integer, then this function returns a semigroup of transformations on n+1 points which is isomorphic to the semigroup consisting of all partial transformation on n points. This monoid has (n+1)^n elements.

gap> PartialTransformationSemigroup(8); 
<regular transformation monoid of degree 9 with 4 generators>
gap> Size(last);
43046721

2.5-7 DualSymmetricInverseSemigroup

Returns: An inverse bipartition monoid.

If n is a positive integer, then these operations return the dual symmetric inverse monoid of degree n, which is the subsemigroup of the partition monoid consisting of the block bijections of degree n.

SingularDualSymmetricInverseSemigroup returns the ideal of the dual symmetric inverse monoid consisting of the non-invertible elements (i.e. those not in the group of units), when n is at least 2.

See IsBlockBijection (5.5-13).

gap> Number(PartitionMonoid(3), IsBlockBijection);
25
gap> S := DualSymmetricInverseSemigroup(3);
<inverse bipartition monoid of degree 3 with 3 generators>
gap> Size(S);
25

2.5-8 UniformBlockBijectionMonoid

Returns: An inverse bipartition monoid.

If n is a positive integer, then this operation returns the uniform block bijection monoid of degree n. The uniform block bijection monoid is the submonoid of the partition monoid consisting of the block bijections of degree n where the number of positive integers in a block equals the number of negative integers in that block. The uniform block bijection monoid is also referred to as the factorisable dual symmetric inverse semigroup.

SingularUniformBlockBijectionMonoid returns the ideal of the uniform block bijection monoid consisting of the non-invertible elements (i.e. those not in the group of units), when n is at least 2.

PlanarUniformBlockBijectionMonoid returns the submonoid of the uniform block bijection monoid consisting of the planar elements (i.e. those in the planar partition monoid).

SingularPlanarUniformBlockBijectionMonoid returns the ideal of the planar uniform block bijection monoid consisting of the non-invertible elements (i.e. those not in the group of units), when n is at least 2.

See IsUniformBlockBijection (5.5-14).

gap> S := UniformBlockBijectionMonoid(4);
<inverse bipartition monoid of degree 4 with 3 generators>
gap> Size(PlanarUniformBlockBijectionMonoid(8));
128
gap> S:=DualSymmetricInverseMonoid(4);
<inverse bipartition monoid of degree 4 with 3 generators>
gap> IsFactorisableSemigroup(S);
false
gap> S:=FactorisableDualSymmetricInverseSemigroup(4);
<inverse bipartition monoid of degree 4 with 3 generators>
gap> IsFactorisableSemigroup(S);
true
gap> S:=Range(IsomorphismBipartitionSemigroup(SymmetricInverseMonoid(5)));
<inverse bipartition monoid of degree 5 with 3 generators>
gap> IsFactorisableSemigroup(S);
true

2.5-9 ApsisMonoid

Returns: A bipartition monoid.

If m and n are positive integers, then this operation returns the m-apsis monoid of degree n. The m-apsis monoid is the monoid of bipartitions generated when the diapses in generators of the Jones monoid are replaced with m-apses. Note that an m-apsis is a block that contains precisely m consecutive integers.

SingularApsisMonoid returns the ideal of the apsis monoid consisting of the non-invertible elements (i.e. those not in the group of units), when m <= n.

CrossedApsisGeneratedMonoid returns the semigroup generated by the symmetric group of degree n and the m-apsis monoid of degree n.

SingularCrossedApsisMonoid returns the ideal of the crossed apsis monoid consisting of the non-invertible elements (i.e. those not in the group of units), when m <= n.

gap> S := ApsisMonoid(3, 7);
<regular bipartition monoid of degree 7 with 5 generators>
gap> Size(S);
320
gap> Size(CrossedApsisMonoid(4, 9));
24291981

2.5-10 ModularPartitionMonoid

Returns: A bipartition monoid.

If m and n are positive integers, then this operation returns the modular-m partition monoid of degree n. The modular-m partition monoid is the submonoid of the partition monoid such that the numbers of positive and negative integers contained in each block are congruent mod m.

SingularModularPartitionMonoid returns the ideal of the modular partition monoid consisting of the non-invertible elements (i.e. those not in the group of units), when either m = n = 1 or m, n > 1.

PlanarModularPartitionMonoid returns the submonoid of the modular-m partition monoid consisting of the planar elements (i.e. those in the planar partition monoid).

SingularPlanarModularPartitionMonoid returns the ideal of the planar modular partition monoid consisting of the non-invertible elements (i.e. those not in the group of units), when either m = n = 1 or m, n > 1.

gap> S := ModularPartitionMonoid(3, 7);
<regular bipartition monoid of degree 7 with 4 generators>
gap> Size(S);
826897
gap> Size(PlanarModularPartitionMonoid(4, 9));
1795

2.5-11 FullMatrixSemigroup

Returns: A matrix semigroup.

FullMatrixSemigroup, GeneralLinearSemigroup, and GLS are synonyms for each other. They both return the full matrix semigroup, or if you prefer the general linear semigroup, of d by d matrices with entries over the field with q elements. This semigroup has q ^ (d ^ 2) elements.

gap> S := FullMatrixSemigroup(3, 4);
<general linear monoid 3x3 over GF(2^2)>
gap> Size(S);
262144

2.5-12 SpecialLinearSemigroup

Returns: A matrix semigroup.

SpecialLinearSemigroup and SLS are synonymous. The special linear semigroup of d by d matrices with entries over the field with q elements is generated by a generating set for the special linear group of d by d matrices over the field with q elements and a matrix of rank d-1.

gap> S := SLS(3,4);
<special linear monoid 3x3 over GF(2^2)>
gap> Size(S);
141184

2.5-13 MunnSemigroup

Returns: The Munn semigroup of a semilattice.

If S is a semilattice, then MunnSemigroup returns the inverse semigroup of partial permutations of isomorphisms of principal ideals of S; called the Munn semigroup of S.

This function was written jointly by J. D. Mitchell, Yann Peresse (St Andrews), Yanhui Wang (York).

Please note: the Grape package version 4.5 or higher must be available and compiled for this function to work.

gap> S := InverseSemigroup(
> PartialPerm( [ 1, 2, 3, 4, 5, 6, 7, 10 ], [ 4, 6, 7, 3, 8, 2, 9, 5 ] ),
> PartialPerm( [ 1, 2, 7, 9 ], [ 5, 6, 4, 3 ] ) );
<inverse partial perm semigroup of rank 10 with 2 generators>
gap> T := InverseSemigroup(Idempotents(S), rec(small := true));;
gap> M := MunnSemigroup(T);;
gap> NrIdempotents(M);
60
gap> NrIdempotents(S);
60

2.5-14 Monoids of order preserving functions

Returns: A semigroup of transformations or partial permutations related to a linear order.

OrderEndomorphisms(n)

OrderEndomorphisms(n) returns the monoid of transformations that preserve the usual order on {1,2,..., n} where n is a positive integer. OrderEndomorphisms(n) is generated by the n+1 transformations:

\left( \begin{array}{ccccccccc} 1&2&3&\cdots&n-1& n\\ 1&1&2&\cdots&n-2&n-1 \end{array}\right), \qquad \left( \begin{array}{ccccccccc} 1&2&\cdots&i-1& i& i+1&i+2&\cdots &n\\ 1&2&\cdots&i-1& i+1&i+1&i+2&\cdots &n\\ \end{array}\right)

where i=0,...,n-1 and has 2n-1choose n-1 elements.

POI(n)

POI(n) returns the inverse monoid of partial permutations that preserve the usual order on {1,2,..., n} where n is a positive integer. POI(n) is generated by the n partial permutations:

\left( \begin{array}{ccccc} 1&2&3&\cdots&n\\ -&1&2&\cdots&n-1 \end{array}\right), \qquad \left( \begin{array}{ccccccccc} 1&2&\cdots&i-1& i& i+1&i+2&\cdots &n\\ 1&2&\cdots&i-1& i+1&-&i+2&\cdots&n\\ \end{array}\right)

where i=1, ..., n-1 and has 2nchoose n elements.

POPI(n)

POPI(n) returns the inverse monoid of partial permutation that preserve the orientation of {1,2,..., n} where n is a positive integer. POPI(n) is generated by the partial permutations:

\left( \begin{array}{ccccc} 1&2&\cdots&n-1&n\\ 2&3&\cdots&n&1 \end{array}\right),\qquad \left( \begin{array}{cccccc} 1&2&\cdots&n-2&n-1&n\\ 1&2&\cdots&n-2&n&- \end{array}\right).

and has 1+fracn22nchoose n elements.

gap> S:=POPI(10);                                            
<inverse partial perm monoid of rank 10 with 2 generators>
gap> Size(S);
923781
gap> 1+5*Binomial(20, 10);
923781
gap> S:=POI(10);
<inverse partial perm monoid of rank 10 with 10 generators>
gap> Size(S);
184756
gap> Binomial(20,10);
184756
gap> IsSubsemigroup(POPI(10), POI(10));
true
gap> S:=OrderEndomorphisms(5);
<regular transformation monoid of degree 5 with 5 generators>
gap> IsIdempotentGenerated(S);
true
gap> Size(S)=Binomial(2*5-1, 5-1);
true

2.5-15 SingularTransformationSemigroup

Returns: The semigroup of non-invertible transformations.

If n is a integer greater than 1, then this function returns the semigroup of non-invertible transformations, which is generated by the n(n-1) idempotents of degree n and rank n-1 and has n^n-n! elements.

gap> S:=SingularTransformationSemigroup(5);
<regular transformation semigroup ideal of degree 5 with 1 generator>
gap> Size(S);
3005

2.5-16 RegularBinaryRelationSemigroup

Returns: A semigroup of binary relations.

RegularBinaryRelationSemigroup return the semigroup generated by the regular binary relations on the set {1,..., n} for a positive integer n. RegularBinaryRelationSemigroup(n) is generated by the 4 binary relations:

\begin{array}{ll} \left(\begin{array}{ccccccccc} 1&2&\cdots&n-1& n\\ 2&3&\cdots&n&1 \end{array}\right),& \quad \left(\begin{array}{ccccccccc} 1&2&3&\cdots&n\\ 2&1&3&\cdots&n \end{array}\right),\\ \left(\begin{array}{ccccccccc} 1&2&\cdots&n-1& n\\ 2&2&\cdots&n-1&\{1,n\} \end{array}\right), &\quad \left(\begin{array}{ccccccccc} 1&2&\cdots&n-1&n\\ 2&2&\cdots&n-1&- \end{array}\right). \end{array}

This semigroup has nearly 2^(n^2) elements.

2.5-17 MonogenicSemigroup

Returns: A monogenic semigroup with index m and period r.

If m and r are positive integers, then this function returns a monogenic semigroup S with index m and period r in the category given by the filter filt.

The optional argument filt may be one of the following:

• IsTransformationSemigroup (the default, if filt is not specified),

• IsPartialPermSemigroup,

• IsBipartitionSemigroup,

• IsBlockBijectionSemigroup.

The semigroup S is generated by a single element, f. S consists of the elements f, f ^ 2, ..., f ^ m, ..., f ^ m + r - 1. The minimal ideal of S consists of the elements f ^ m, ..., f ^ m + r - 1 and is isomorphic to the cyclic group of order r.

See IsMonogenicSemigroup (4.6-10) for more information about monogenic semigroups.

gap> S := MonogenicSemigroup(5, 3);
<commutative non-regular transformation semigroup of size 7, degree 8 
 with 1 generator>
gap> IsMonogenicSemigroup(S);
true
gap> I := MinimalIdeal(S);
<commutative simple transformation semigroup ideal of degree 8 with
  1 generator>
gap> IsGroupAsSemigroup(I);
true
gap> StructureDescription(I);
"C3"
gap> S := MonogenicSemigroup(IsBlockBijectionSemigroup, 9, 1);
<commutative non-regular bipartition semigroup of size 9, degree 10 
 with 1 generator>

2.5-18 RectangularBand

Returns: An m by n rectangular band.

If m and n are positive integers, then this function returns a semigroup isomorphic to an m by n rectangular band, which is in the category given by the filter filt.

The optional argument filt may be one of the following:

• IsTransformationSemigroup,

• IsBipartitionSemigroup,

• IsReesMatrixSemigroup (the default, if filt is not specified).

See IsRectangularBand (4.6-13) for more information about rectangular bands.

gap> S := RectangularBand(4, 8);
<Rees matrix semigroup 4x8 over Group(())>
gap> IsRectangularBand(S);
true
gap> IsCompletelySimpleSemigroup(S) and IsHTrivial(S);
true
gap> T := RectangularBand(IsTransformationSemigroup, 5, 6);
<transformation semigroup of size 30, degree 31 with 6 generators>
gap> IsRectangularBand(T);
true

2.5-19 ZeroSemigroup

Returns: A zero semigroup of order n.

If n is a positive integer, then this function returns a zero semigroup of order n in the category given by the filter filt.

The optional argument filt may be one of the following:

• IsTransformationSemigroup,

• IsPartialPermSemigroup (the default, if filt is not specified),

• IsBipartitionSemigroup,

• IsBlockBijectionSemigroup,

• IsReesZeroMatrixSemigroup (provided that n > 1).

See IsZeroSemigroup (4.6-23) for more information about zero semigroups.

gap> S := ZeroSemigroup(15);
<non-regular partial perm semigroup of size 15, rank 14 with 14 
 generators>
gap> Size(S);
15
gap> z := MultiplicativeZero(S);
<empty partial perm>
gap> IsZeroSemigroup(S);
true
gap> ForAll(S, x -> ForAll(S, y -> x * y = z));
true
gap> S := ZeroSemigroup(IsReesZeroMatrixSemigroup, 5);
<Rees 0-matrix semigroup 4x1 over Group(())>
gap> Matrix(S);
[ [ 0, 0, 0, 0 ] ]
gap> IsZeroSemigroup(S);
true

2.5-20 LeftZeroSemigroup

Returns: A left zero (or right zero) semigroup of order n.

If n is a positive integer, then this function returns a left zero (or right zero, as appropriate) semigroup of order n in the category given by the filter filt.

The optional argument filt may be one of the following:

• IsTransformationSemigroup (the default, if filt is not specified),

• IsBipartitionSemigroup,

• IsReesMatrixSemigroup.

See IsLeftZeroSemigroup (4.6-9) and IsRightZeroSemigroup (4.6-15) for more information about left and right zero semigroups.

gap> S := LeftZeroSemigroup(20);
<transformation semigroup of size 20, degree 21 with 20 generators>
gap> IsLeftZeroSemigroup(S);
true
gap> ForAll(Tuples(S, 2), p -> p[1] * p[2] = p[1]);
true
gap> S := RightZeroSemigroup(IsBipartitionSemigroup, 5);
<bipartition semigroup of size 5, degree 3 with 5 generators>
gap> IsRightZeroSemigroup(S);
true

generated by GAPDoc2HTML