8 Congruences

8.3 Congruences on Rees matrix semigroups

8.3-1 IsRMSCongruenceByLinkedTriple

8.3-2 RMSCongruenceByLinkedTriple

8.3-3 RMSCongruenceClassByLinkedTriple

8.3-4 IsLinkedTriple

8.3-5 CanonicalRepresentative

8.3-6 AsSemigroupCongruenceByGeneratingPairs

8.3-7 AsRMSCongruenceByLinkedTriple

8.3-8 MeetSemigroupCongruences

8.3-9 JoinSemigroupCongruences

8.3-1 IsRMSCongruenceByLinkedTriple

8.3-2 RMSCongruenceByLinkedTriple

8.3-3 RMSCongruenceClassByLinkedTriple

8.3-4 IsLinkedTriple

8.3-5 CanonicalRepresentative

8.3-6 AsSemigroupCongruenceByGeneratingPairs

8.3-7 AsRMSCongruenceByLinkedTriple

8.3-8 MeetSemigroupCongruences

8.3-9 JoinSemigroupCongruences

Congruences in **Semigroups** can be described in several different ways:

Generating pairs -- the minimal congruence which contains these pairs

Rees congruences -- the congruence specified by a given ideal

Universal congruences -- the unique congruence with only one class

Linked triples -- only for simple or 0-simple semigroups (see below)

Kernel and trace -- only for inverse semigroups

The operation `SemigroupCongruence`

(8.1-1) can be used to create any of these, interpreting the arguments in a smart way. The usual way of specifying a congruence will be by giving a set of generating pairs, but a user with an ideal could instead create a Rees congruence or universal congruence.

If a congruence is specified by generating pairs on a simple, 0-simple, or inverse semigroup, then the congruence will be converted automatically to one of the last two items in the above list, to reduce the complexity of any calculations to be performed. The user need not manually specify, or even be aware of, the congruence's linked triple or kernel and trace.

`‣ SemigroupCongruence` ( S, pairs ) | ( function ) |

Returns: A semigroup congruence.

This function returns a semigroup congruence over the semigroup `S`.

If `pairs` is a list of lists of size 2 with elements from `S`, then this function will return the semigroup congruence defined by these generating pairs. The individual pairs may instead be given as separate arguments.

gap> S:=Semigroup(Transformation( [ 2, 1, 1, 2, 1 ] ), > Transformation( [ 3, 4, 3, 4, 4 ] ), > Transformation( [ 3, 4, 3, 4, 3 ] ), > Transformation( [ 4, 3, 3, 4, 4 ] ));; gap> pair1 := [ Transformation( [ 3, 4, 3, 4, 3 ] ), > Transformation( [ 1, 2, 1, 2, 1 ] ) ];; gap> pair2 := [ Transformation( [ 4, 3, 4, 3, 4 ] ), > Transformation( [ 3, 4, 3, 4, 3 ] ) ];; gap> SemigroupCongruence(S, [pair1, pair2]); <semigroup congruence over <simple transformation semigroup of degree 5 with 4 generators> with linked triple (2,4,1)> gap> SemigroupCongruence(S, pair1, pair2); <semigroup congruence over <simple transformation semigroup of degree 5 with 4 generators> with linked triple (2,4,1)>

`‣ CongruenceClassOfElement` ( cong, elm ) | ( operation ) |

Returns: A congruence class.

This operation is a synonym of `EquivalenceClassOfElement`

in the case that the argument `cong` is a congruence of a semigroup.

gap> S := ReesZeroMatrixSemigroup(SymmetricGroup(3), > [[(),(1,3,2)],[(1,2),0]]);; gap> cong := CongruencesOfSemigroup(S)[3];; gap> elm := ReesZeroMatrixSemigroupElement(S, 1, (1,3,2), 1);; gap> CongruenceClassOfElement(cong, elm); {(1,(1,3,2),1)}

`‣ CongruenceClasses` ( cong ) | ( attribute ) |

Returns: The classes of congruence.

When `cong` is a congruence of semigroup, this attribute is synonymous with `EquivalenceClasses`

.

The return value is a list containing all the equivalence classes of the semigroup congruence `cong`.

gap> S := ReesZeroMatrixSemigroup(SymmetricGroup(3), > [[(),(1,3,2)],[(1,2),0]]);; gap> cong := CongruencesOfSemigroup(S)[3];; gap> classes := CongruenceClasses(cong);; gap> Size(classes); 9

`‣ NrCongruenceClasses` ( cong ) | ( attribute ) |

Returns: A positive integer.

This attribute describes the number of congruence classes in the semigroup congruence `cong`.

gap> S := ReesZeroMatrixSemigroup(SymmetricGroup(3), > [[(),(1,3,2)],[(1,2),0]]);; gap> cong := CongruencesOfSemigroup(S)[3];; gap> NrCongruenceClasses(cong); 9

`‣ CongruencesOfSemigroup` ( S ) | ( attribute ) |

Returns: The congruences of a semigroup.

This attribute gives a list of the congruences of the semigroup `S`.

At present this only works for simple and 0-simple semigroups.

gap> s := ReesZeroMatrixSemigroup(SymmetricGroup(3), > [[(),(1,3,2)],[(1,2),0]]);; gap> congs := CongruencesOfSemigroup(s); [ <universal semigroup congruence over <Rees 0-matrix semigroup 2x2 over Sym( [ 1 .. 3 ] )>>, <semigroup congruence over <Rees 0-matrix semigroup 2x2 over Sym( [ 1 .. 3 ] )> with linked triple (1,2,2)>, <semigroup congruence over <Rees 0-matrix semigroup 2x2 over Sym( [ 1 .. 3 ] )> with linked triple (3,2,2)>, <semigroup congruence over <Rees 0-matrix semigroup 2x2 over Sym( [ 1 .. 3 ] )> with linked triple (S3,2,2)> ]

`‣ AsLookupTable` ( cong ) | ( attribute ) |

Returns: A list.

This attribute describes the semigroup congruence `cong` as a list of positive integers with length the size of the semigroup over which `cong` is defined.

Each position in the list corresponds to an element of the semigroup (in the order defined by `SSortedList`

) and the integer at that position is a unique identifier for that element's congruence class under `cong`. Hence, two elements are congruent if and only if they have the same number at their two positions in the list.

gap> s := Monoid( [ Transformation( [ 1, 2, 2 ] ), > Transformation( [ 3, 1, 3 ] ) ] );; gap> cong := SemigroupCongruence( s, > [Transformation([1,2,1]),Transformation([2,1,2])] );; gap> AsLookupTable(cong); [ 1, 2, 3, 4, 5, 6, 3, 2, 1, 6, 5, 1 ]

This section describes the implementation of congruences of simple and 0-simple semigroups in the **Semigroups** package, and the functions associated with them. This code and this part of the manual were written by Michael Torpey. Most of the theorems used in this chapter are from Section 3.5 of [How95].

By the Rees Theorem, any 0-simple semigroup S is isomorphic to a *Rees 0-matrix semigroup* (see Reference: Rees Matrix Semigroups) over a group, with a regular sandwich matrix. That is,

S \cong \mathcal{M}^0[G; I,\Lambda; P],

where G is a group, Λ and I are non-empty sets, and P is regular in the sense that it has no rows or columns consisting soley of zeroes.

The congruences of a Rees 0-matrix semigroup are in 1-1 correspondence with the *linked triple*, which is a triple of the form `[N,S,T]`

where:

`N`

is a normal subgroup of the underlying group`G`

,`S`

is an equivalence relation on the columns of`P`

,`T`

is an equivalence relation on the rows of`P`

,

satisfying the following conditions:

a pair of

`S`

-related columns must contain zeroes in precisely the same rows,a pair of

`T`

-related rows must contain zeroes in precisely the same columns,if

`i`

and`j`

are`S`

-related,`k`

and`l`

are`T`

-related and the matrix entries p_k, i, p_k, j, p_l, i, p_l, j ≠ 0, then q_k, l, i, j ∈ N, whereq_{k, l, i, j} = p_{k, i} p_{l, i}^{-1} p_{l, j} p_{k, j}^{-1}.

By Theorem 3.5.9 in [How95], for any finite 0-simple Rees 0-matrix semigroup, there is a bijection between its non-universal congruences and its linked triples. In this way, we can internally represent any congruence of such a semigroup by storing its associated linked triple instead of a set of generating pairs, and thus perform many calculations on it more efficiently.

If a congruence is defined by a linked triple `(N,S,T)`

, then a single class of that congruence can be defined by a triple `(Nx,i/S,k/S)`

, where `Nx`

is a right coset of `N`

, `i/S`

is the equivalence class of `i`

in `S`

, and `k/S`

is the equivalence class of `k`

in `T`

. Thus we can internally represent any class of such a congruence as a triple simply consisting of a right coset and two positive integers.

An analogous condition exists for finite simple Rees matrix semigroups without zero.

`‣ IsRMSCongruenceByLinkedTriple` ( obj ) | ( category ) |

`‣ IsRZMSCongruenceByLinkedTriple` ( obj ) | ( category ) |

Returns: `true`

or `false`

.

These categories describe a type of semigroup congruence over a Rees matrix or 0-matrix semigroup. Externally, an object of this type may be used in the same way as any other object in the category `IsSemigroupCongruence`

(Reference: IsSemigroupCongruence) but it is represented internally by its *linked triple*, and certain functions may take advantage of this information to reduce computation times.

An object of this type may be constructed with `RMSCongruenceByLinkedTriple`

or `RZMSCongruenceByLinkedTriple`

, or this representation may be selected automatically by `SemigroupCongruence`

(8.1-1).

gap> G := Group( [ (1,4,5), (1,5,3,4) ] );; gap> mat := [ [ 0, 0, (1,4,5), 0, 0, (1,4,3,5) ], > [ 0, (), 0, 0, (3,5), 0 ], > [ (), 0, 0, (3,5), 0, 0 ] ];; gap> S := ReesZeroMatrixSemigroup(G, mat);; gap> N := Group([ (1,4)(3,5), (1,5)(3,4) ]);; gap> colBlocks := [ [ 1 ], [ 2, 5 ], [ 3, 6 ], [ 4 ] ];; gap> rowBlocks := [ [ 1 ], [ 2 ], [ 3 ] ];; gap> cong := RZMSCongruenceByLinkedTriple(S, N, colBlocks, rowBlocks);; gap> IsRZMSCongruenceByLinkedTriple(cong); true

`‣ RMSCongruenceByLinkedTriple` ( S, N, colBlocks, rowBlocks ) | ( function ) |

`‣ RZMSCongruenceByLinkedTriple` ( S, N, colBlocks, rowBlocks ) | ( function ) |

Returns: A Rees matrix or 0-matrix semigroup congruence by linked triple.

This function returns a semigroup congruence over the Rees matrix or 0-matrix semigroup `S` corresponding to the linked triple (`N`, `colBlocks`, `rowBlocks`). The argument `N` should be a normal subgroup of the underlying semigroup of `S`; `colBlocks` should be a partition of the columns of the matrix of `S`; and `rowBlocks` should be a partition of the rows of the matrix of `S`. For example, if the matrix has 5 rows, then a possibility for `rowBlocks` might be `[ [1,3], [2,5], [4] ]`

.

If the arguments describe a valid linked triple on `S`, then an object in the category `IsRZMSCongruenceByLinkedTriple`

is returned. This object can be used like any other semigroup congruence in **GAP**.

If the arguments describe a triple which is not *linked* in the sense described above, then this function returns an error.

gap> G := Group( [ (1,4,5), (1,5,3,4) ] );; gap> mat := [ [ 0, 0, (1,4,5), 0, 0, (1,4,3,5) ], > [ 0, (), 0, 0, (3,5), 0 ], > [ (), 0, 0, (3,5), 0, 0 ] ];; gap> S := ReesZeroMatrixSemigroup(G, mat);; gap> N := Group([ (1,4)(3,5), (1,5)(3,4) ]);; gap> colBlocks := [ [ 1 ], [ 2, 5 ], [ 3, 6 ], [ 4 ] ];; gap> rowBlocks := [ [ 1 ], [ 2 ], [ 3 ] ];; gap> cong := RZMSCongruenceByLinkedTriple(S, N, colBlocks, rowBlocks); <semigroup congruence over <Rees 0-matrix semigroup 6x3 over Group([ (1,4,5), (1,5,3,4) ])> with linked triple (2^2,4,3)>

`‣ RMSCongruenceClassByLinkedTriple` ( cong, nCoset, colClass, rowClass ) | ( operation ) |

`‣ RZMSCongruenceClassByLinkedTriple` ( cong, nCoset, colClass, rowClass ) | ( operation ) |

Returns: A Rees matrix or 0-matrix semigroup congruence class by linked triple.

This operation returns one congruence class of the congruence `cong`, as defined by the other three parameters.

The argument `cong` must be a Rees matrix or 0-matrix semigroup congruence by linked triple. If the linked triple consists of the three parameters `N`

, `colBlocks`

and `rowBlocks`

, then `nCoset` must be a right coset of `N`

, `colClass` must be a positive integer corresponding to a position in the list `colBlocks`

, and `rowClass` must be a positive integer corresponding to a position in the list `rowBlocks`

.

If the arguments are valid, an `IsRMSCongruenceClassByLinkedTriple`

or `IsRZMSCongruenceClassByLinkedTriple`

object is returned, which can be used like any other equivalence class in **GAP**. Otherwise, an error is returned.

gap> g := Group( [ (1,4,5), (1,5,3,4) ] );; gap> mat := [ [ 0, 0, (1,4,5), 0, 0, (1,4,3,5) ], > [ 0, (), 0, 0, (3,5), 0 ], > [ (), 0, 0, (3,5), 0, 0 ] ];; gap> s := ReesZeroMatrixSemigroup(g, mat);; gap> n := Group([ (1,4)(3,5), (1,5)(3,4) ]);; gap> colBlocks := [ [ 1 ], [ 2, 5 ], [ 3, 6 ], [ 4 ] ];; gap> rowBlocks := [ [ 1 ], [ 2 ], [ 3 ] ];; gap> cong := RZMSCongruenceByLinkedTriple(s, n, colBlocks, rowBlocks);; gap> class := RZMSCongruenceClassByLinkedTriple(cong, > RightCoset(n,(1,5)),2,3); {(2,(3,4),3)}

`‣ IsLinkedTriple` ( S, N, colBlocks, rowBlocks ) | ( operation ) |

Returns: `true`

or `false`

.

This operation returns true if and only if the arguments (`N`, `colBlocks`, `rowBlocks`) describe a linked triple of the Rees matrix or 0-matrix semigroup `S`, as described above.

gap> G := Group( [ (1,4,5), (1,5,3,4) ] );; gap> mat := [ [ 0, 0, (1,4,5), 0, 0, (1,4,3,5) ], > [ 0, (), 0, 0, (3,5), 0 ], > [ (), 0, 0, (3,5), 0, 0 ] ];; gap> S := ReesZeroMatrixSemigroup(G, mat);; gap> N := Group([ (1,4)(3,5), (1,5)(3,4) ]);; gap> colBlocks := [ [ 1 ], [ 2, 5 ], [ 3, 6 ], [ 4 ] ];; gap> rowBlocks := [ [ 1 ], [ 2 ], [ 3 ] ];; gap> IsLinkedTriple(S, N, colBlocks, rowBlocks); true

`‣ CanonicalRepresentative` ( class ) | ( attribute ) |

Returns: A congruence class.

This attribute gives a canonical representative for the semigroup congruence class `class`. This representative can be used to identify a class uniquely.

At present this only works for simple and 0-simple semigroups.

gap> S := ReesZeroMatrixSemigroup(SymmetricGroup(3), > [[(),(1,3,2)],[(1,2),0]]);; gap> cong := CongruencesOfSemigroup(S)[3];; gap> class := CongruenceClasses(cong)[3];; gap> CanonicalRepresentative(class); (1,(1,2,3),2)

`‣ AsSemigroupCongruenceByGeneratingPairs` ( cong ) | ( operation ) |

Returns: A semigroup congruence.

This operation takes `cong`, a semigroup congruence, and returns the same congruence relation, but described by **GAP**'s default method of defining semigroup congruences: a set of generating pairs for the congruence.

gap> S := ReesZeroMatrixSemigroup(SymmetricGroup(3), > [[(),(1,3,2)],[(1,2),0]]);; gap> cong := CongruencesOfSemigroup(S)[3];; gap> AsSemigroupCongruenceByGeneratingPairs(cong); <semigroup congruence over <Rees 0-matrix semigroup 2x2 over Sym( [ 1 .. 3 ] )> with 3 generating pairs>

`‣ AsRMSCongruenceByLinkedTriple` ( cong ) | ( operation ) |

`‣ AsRZMSCongruenceByLinkedTriple` ( cong ) | ( operation ) |

Returns: A Rees matrix or 0-matrix semigroup congruence by linked triple.

This operation takes a semigroup congruence `cong` over a finite simple or 0-simple Rees 0-matrix semigroup, and returns that congruence relation in a new form: as either a congruence by linked triple, or a universal congruence.

If the congruence is not defined over an appropriate type of semigroup, then this function returns an error.

gap> S := ReesZeroMatrixSemigroup(SymmetricGroup(3), > [[(),(1,3,2)],[(1,2),0]]);; gap> x := ReesZeroMatrixSemigroupElement(S, 1, (1,3,2), 1);; gap> y := ReesZeroMatrixSemigroupElement(S, 1, (), 1);; gap> cong := SemigroupCongruenceByGeneratingPairs(S, [ [x,y] ]);; gap> AsRZMSCongruenceByLinkedTriple(cong); <semigroup congruence over <Rees 0-matrix semigroup 2x2 over Sym( [ 1 .. 3 ] )> with linked triple (3,2,2)>

`‣ MeetSemigroupCongruences` ( c1, c2 ) | ( operation ) |

Returns: A semigroup congruence.

This operation returns the *meet* of the two semigroup congruences `c1` and `c2` -- that is, the largest semigroup congruence contained in both `c1` and `c2`.

At present this only works for simple and 0-simple semigroups.

gap> S := ReesZeroMatrixSemigroup(SymmetricGroup(3), > [[(),(1,3,2)],[(1,2),0]]);; gap> congs := CongruencesOfSemigroup(S);; gap> MeetSemigroupCongruences(congs[2], congs[3]); <semigroup congruence over <Rees 0-matrix semigroup 2x2 over Sym( [ 1 .. 3 ] )> with linked triple (1,2,2)>

`‣ JoinSemigroupCongruences` ( c1, c2 ) | ( operation ) |

Returns: A semigroup congruence.

This operation returns the *join* of the two semigroup congruences `c1` and `c2` -- that is, the smallest semigroup congruence containing all the relations in both `c1` and `c2`.

At present this only works for simple and 0-simple semigroups.

gap> S := ReesZeroMatrixSemigroup(SymmetricGroup(3), > [[(),(1,3,2)],[(1,2),0]]);; gap> congs := CongruencesOfSemigroup(S);; gap> JoinSemigroupCongruences(congs[2], congs[3]); <semigroup congruence over <Rees 0-matrix semigroup 2x2 over Sym( [ 1 .. 3 ] )> with linked triple (3,2,2)>

The linked triples of a completely 0-simple Rees 0-matrix semigroup describe only its non-universal congruences. In any one of these, the zero element of the semigroup is related only to itself. However, for any semigroup S the universal relation S × S is a congruence; called the *universal congruence*. The universal congruence on a semigroup has its own unique representation.

Since many things we want to calculate about congruences are trivial in the case of the universal congruence, this package contains a category specifically designed for it, `IsUniversalSemigroupCongruence`

. We also define `IsUniversalSemigroupCongruenceClass`

, which represents the single congruence class of the universal congruence.

`‣ IsUniversalSemigroupCongruence` ( obj ) | ( category ) |

Returns: `true`

or `false`

.

This category describes a type of semigroup congruence, which must refer to the *universal semigroup congruence* S × S. Externally, an object of this type may be used in the same way as any other object in the category `IsSemigroupCongruence`

(Reference: IsSemigroupCongruence).

An object of this type may be constructed with `UniversalSemigroupCongruence`

or this representation may be selected automatically as an alternative to an `IsRZMSCongruenceByLinkedTriple`

object (since the universal congruence cannot be represented by a linked triple).

gap> S := Semigroup([ Transformation([ 3, 2, 3 ]) ]);; gap> U := UniversalSemigroupCongruence(S);; gap> IsUniversalSemigroupCongruence(U); true

`‣ UniversalSemigroupCongruence` ( S ) | ( operation ) |

Returns: A universal semigroup congruence.

This operation returns the universal semigroup congruence for the semigroup `S`. It can be used in the same way as any other semigroup congruence object.

gap> S := ReesZeroMatrixSemigroup(SymmetricGroup(3), > [[(),(1,3,2)],[(1,2),0]]);; gap> UniversalSemigroupCongruence(S); <universal semigroup congruence over <Rees 0-matrix semigroup 2x2 over Sym( [ 1 .. 3 ] )>>

generated by GAPDoc2HTML