2 Creating semigroups and monoids

2.5 Standard examples

2.5-1 EndomorphismsPartition

2.5-2 PartitionMonoid

2.5-3 PlanarPartitionMonoid

2.5-4 BrauerMonoid

2.5-5 JonesMonoid

2.5-6 PartialTransformationSemigroup

2.5-7 DualSymmetricInverseSemigroup

2.5-8 UniformBlockBijectionMonoid

2.5-9 ApsisMonoid

2.5-10 ModularPartitionMonoid

2.5-11 FullMatrixSemigroup

2.5-12 SpecialLinearSemigroup

2.5-13 MunnSemigroup

2.5-14 Monoids of order preserving functions

2.5-15 SingularTransformationSemigroup

2.5-16 RegularBinaryRelationSemigroup

2.5-17 MonogenicSemigroup

2.5-18 RectangularBand

2.5-19 ZeroSemigroup

2.5-20 LeftZeroSemigroup

2.5-1 EndomorphismsPartition

2.5-2 PartitionMonoid

2.5-3 PlanarPartitionMonoid

2.5-4 BrauerMonoid

2.5-5 JonesMonoid

2.5-6 PartialTransformationSemigroup

2.5-7 DualSymmetricInverseSemigroup

2.5-8 UniformBlockBijectionMonoid

2.5-9 ApsisMonoid

2.5-10 ModularPartitionMonoid

2.5-11 FullMatrixSemigroup

2.5-12 SpecialLinearSemigroup

2.5-13 MunnSemigroup

2.5-14 Monoids of order preserving functions

2.5-15 SingularTransformationSemigroup

2.5-16 RegularBinaryRelationSemigroup

2.5-17 MonogenicSemigroup

2.5-18 RectangularBand

2.5-19 ZeroSemigroup

2.5-20 LeftZeroSemigroup

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.

`‣ RandomInverseMonoid` ( m, n ) | ( operation ) |

`‣ RandomInverseSemigroup` ( m, n ) | ( operation ) |

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>

`‣ RandomTransformationMonoid` ( m, n ) | ( operation ) |

`‣ RandomTransformationSemigroup` ( m, n ) | ( operation ) |

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>

`‣ RandomPartialPermMonoid` ( m, n ) | ( operation ) |

`‣ RandomPartialPermSemigroup` ( m, n ) | ( operation ) |

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>

`‣ RandomBinaryRelationMonoid` ( m, n ) | ( operation ) |

`‣ RandomBinaryRelationSemigroup` ( m, n ) | ( operation ) |

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>

`‣ RandomBipartitionSemigroup` ( m, n ) | ( operation ) |

`‣ RandomBipartitionMonoid` ( m, n ) | ( operation ) |

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>

`‣ RandomMatrixSemigroup` ( R, m, n[, ranks] ) | ( operation ) |

`‣ RandomMatrixMonoid` ( R, m, n[, ranks] ) | ( operation ) |

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>

`‣ ClosureInverseSemigroup` ( S, coll[, opts] ) | ( operation ) |

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>

`‣ ClosureSemigroup` ( S, coll[, opts] ) | ( operation ) |

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

`‣ SubsemigroupByProperty` ( S, func ) | ( operation ) |

`‣ SubsemigroupByProperty` ( S, func, limit ) | ( operation ) |

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>

`‣ InverseSubsemigroupByProperty` ( S, func ) | ( operation ) |

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

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`

.

`‣ SemigroupsOptionsRec` | ( global variable ) |

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 )

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.

`‣ AsTransformationSemigroup` ( S ) | ( operation ) |

`‣ AsPartialPermSemigroup` ( S ) | ( operation ) |

`‣ AsBipartitionSemigroup` ( S ) | ( operation ) |

`‣ AsBlockBijectionSemigroup` ( S ) | ( operation ) |

`‣ AsMatrixSemigroup` ( S[, F] ) | ( operation ) |

Returns: A semigroup.

`AsTransformationSemigroup(`

is just shorthand for `S`)`Range(IsomorphismTransformationSemigroup(`

, when `S`))`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

`‣ IsomorphismPermGroup` ( S ) | ( operation ) |

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

`‣ IsomorphismBipartitionSemigroup` ( S ) | ( attribute ) |

`‣ IsomorphismBipartitionMonoid` ( S ) | ( attribute ) |

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

`‣ IsomorphismBlockBijectionSemigroup` ( S ) | ( attribute ) |

`‣ IsomorphismBlockBijectionMonoid` ( S ) | ( attribute ) |

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 )

`‣ IsomorphismMatrixSemigroup` ( S[, F] ) | ( attribute ) |

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

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.

`‣ EndomorphismsPartition` ( list ) | ( operation ) |

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(`

with a part of length `list`)]

for every `list`[i]`i`

. For example, if

, then `list`=[1,2,3]`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

`‣ PartitionMonoid` ( n ) | ( operation ) |

`‣ SingularPartitionMonoid` ( n ) | ( operation ) |

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

`‣ PlanarPartitionMonoid` ( n ) | ( operation ) |

`‣ SingularPlanarPartitionMonoid` ( n ) | ( operation ) |

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

`‣ BrauerMonoid` ( n ) | ( operation ) |

`‣ SingularBrauerMonoid` ( n ) | ( operation ) |

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>

`‣ JonesMonoid` ( n ) | ( operation ) |

`‣ TemperleyLiebMonoid` ( n ) | ( operation ) |

`‣ SingularJonesMonoid` ( n ) | ( operation ) |

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>

`‣ PartialTransformationSemigroup` ( n ) | ( operation ) |

Returns: A transformation monoid.

If `n` is a positive integer, then this function returns a semigroup of transformations on

points which is isomorphic to the semigroup consisting of all partial transformation on `n`+1`n` points. This monoid has `(`

elements.`n`+1)^`n`

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

`‣ DualSymmetricInverseSemigroup` ( n ) | ( operation ) |

`‣ DualSymmetricInverseMonoid` ( n ) | ( operation ) |

`‣ SingularDualSymmetricInverseSemigroup` ( n ) | ( operation ) |

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

`‣ UniformBlockBijectionMonoid` ( n ) | ( operation ) |

`‣ FactorisableDualSymmetricInverseSemigroup` ( n ) | ( operation ) |

`‣ SingularUniformBlockBijectionMonoid` ( n ) | ( operation ) |

`‣ SingularFactorisableDualSymmetricInverseSemigroup` ( n ) | ( operation ) |

`‣ PlanarUniformBlockBijectionMonoid` ( n ) | ( operation ) |

`‣ SingularPlanarUniformBlockBijectionMonoid` ( n ) | ( operation ) |

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

`‣ ApsisMonoid` ( m, n ) | ( operation ) |

`‣ SingularApsisMonoid` ( m, n ) | ( operation ) |

`‣ CrossedApsisMonoid` ( m, n ) | ( operation ) |

`‣ SingularCrossedApsisMonoid` ( m, n ) | ( operation ) |

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

`‣ ModularPartitionMonoid` ( m, n ) | ( operation ) |

`‣ SingularModularPartitionMonoid` ( m, n ) | ( operation ) |

`‣ PlanarModularPartitionMonoid` ( m, n ) | ( operation ) |

`‣ SingularPlanarModularPartitionMonoid` ( m, n ) | ( operation ) |

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

`‣ FullMatrixSemigroup` ( d, q ) | ( operation ) |

`‣ GeneralLinearSemigroup` ( d, q ) | ( operation ) |

`‣ GLS` ( d, q ) | ( operation ) |

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

elements.`q` ^ (`d` ^ 2)

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

`‣ SpecialLinearSemigroup` ( d, q ) | ( operation ) |

`‣ SLS` ( d, q ) | ( operation ) |

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

`‣ MunnSemigroup` ( S ) | ( operation ) |

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

`‣ OrderEndomorphisms` ( n ) | ( operation ) |

`‣ POI` ( n ) | ( operation ) |

`‣ POPI` ( n ) | ( operation ) |

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

`OrderEndomorphisms(`

`n`)`OrderEndomorphisms(`

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

is generated by the`n`)`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(`

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

is generated by the`n`)`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(`

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

is generated by the partial permutations:`n`)\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

`‣ SingularTransformationSemigroup` ( n ) | ( operation ) |

`‣ SingularTransformationMonoid` ( n ) | ( operation ) |

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

idempotents of degree `n`(`n`-1)`n` and rank

and has n^n-n! elements.`n`-1

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

`‣ RegularBinaryRelationSemigroup` ( n ) | ( operation ) |

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(`

is generated by the 4 binary relations:`n`)

\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.

`‣ MonogenicSemigroup` ( [filt, ]m, r ) | ( function ) |

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>

`‣ RectangularBand` ( [filt, ]m, n ) | ( function ) |

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

`‣ ZeroSemigroup` ( [filt, ]n ) | ( function ) |

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

`‣ LeftZeroSemigroup` ( [filt, ]n ) | ( function ) |

`‣ RightZeroSemigroup` ( [filt, ]n ) | ( function ) |

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