In this chapter we describe the functionality in Semigroups for working with translations of semigroups. The notation used (as well as a number of results) is based on [Pet70]. Translations are of interest mainly due to their role in ideal extensions. A description of this role can also be found in [Pet70]. The implementation of translations in this package is only applicable to finite semigroups satisfying CanUseFroidurePin (6.1-4).
For a semigroup \(S\), a transformation \(\lambda\) of \(S\) (written on the left) is a left translation if for all \(s, t\) in \(S\), \(\lambda (s)t = \lambda (st) \). A right translation \(\rho\) (written on the right) is defined dually.
The set \(L\) of left translations of \(S\) is a semigroup under composition of functions, as is the set \(R\) of right translations. The associativity of \(S\) guarantees that left [right] multiplication by any element \(s\) of \(S\) represents a left [right] translation; this is the inner left [right] translation \(\lambda_s\) [\(\rho_s\)]. The inner left [right] translations form an ideal in \(L\) [\(R\)].
A left translation \(\lambda\) and right translation \(\rho\) are linked if for all s, t in \(S\), \(s\lambda(t) = (s)\rho t\). A pair of linked translations is called a bitranslation. The set of all bitranslations forms a semigroup \(H\) called the translational hull of \(S\) where the operation is componentwise. If the components are inner translations corresponding to multiplication by the same element, then the bitranslation is inner. The inner bitranslations form an ideal of the translational hull.
Translations of a normalized Rees matrix semigroup \(T\) (see RMSNormalization (6.5-7)) over a group \(G\) can be represented through certain tuples, which can be computed very efficiently compared to arbitrary translations. For left translations these tuples consist of a function from the row indices of \(T\) to G and a transformation on the row indices of \(T\); the same is true of right translations and columns. More specifically, given a normalised Rees matrix semigroup \(S\) over a group \(G\) with sandwich matrix \(P\), rows \(I\) and columns \(J\), the left translations are characterised by pairs \((\theta, \chi)\) where \(\theta\) is a function from \(I\) to \(G\) and \(\chi\) is a transformation of \(I\). The left translation \(\lambda\) defined by \((\theta, \chi)\) acts on \(S\) via
\[ \lambda((i, a, \mu)) = ((i)\chi, (i)\theta \cdot a, \mu), \]
where \(i \in I\), \(a \in G\), and \(\mu \in J\) Dually, right translations \(\rho\) are characterised by pairs \((\omega, \psi)\) where \(\omega\) is a function from \(J\) to \(G\) and \(\psi\) is a transformation of \(J\), with action given by
\[ ((i, a, \mu))\rho = (i, a \cdot (\mu)\psi, (\mu)\psi). \]
Similarly, bitranslations \((\lambda, \rho)\) of \(S\) can be characterised by triples \((g, \chi, \psi)\) such that \(g \in G\), \(\chi\) and \(\psi\) are transformations of \(I, J\) respectively, and
\[ p_{\mu, (i)\chi} \cdot g \cdot p_{(1)\psi, i} = p_{\mu, (1)\chi} \cdot g \cdot p_{(mu)\psi, i}. \]
The action of \(\lambda\) on \(S\) is then given by
\[ \lambda((i, a, \mu)) = ((i)\chi, b \cdot p_{(1)\psi, i} \cdot a, \mu), \]
and of \(\rho\) on \(S\) by
\[ ((i, a, \mu))\rho = (i, a \cdot p_{\mu, (1)\chi} \cdot b, (\mu)\psi). \]
Further details may be found in [CP77].
‣ IsSemigroupTranslation( arg ) | ( filter ) |
‣ IsLeftTranslation( arg ) | ( filter ) |
‣ IsRightTranslation( arg ) | ( filter ) |
Returns: true or false
All, and only, left [right] translations belong to IsLeftTranslation [IsRightTranslation]. These are both subcategories of IsSemigroupTranslation, which itself is a subcategory of IsAssociativeElement.
gap> S := RectangularBand(3, 4);; gap> l := Representative(LeftTranslations(S));; gap> IsSemigroupTranslation(l); true gap> IsLeftTranslation(l); true gap> IsRightTranslation(l); false gap> l = One(LeftTranslations(S)); true gap> l * l = l; true
‣ IsBitranslation( arg ) | ( filter ) |
Returns: true or false
All, and only, bitranslations belong to IsBitranslation. This is a subcategory of IsAssociativeElement (Reference: IsAssociativeElement).
gap> G := Group((1, 2), (3, 4));; gap> A := AsList(G);; gap> mat := [[A[1], 0, A[1]], > [A[2], A[2], A[4]]];; gap> S := ReesZeroMatrixSemigroup(G, mat);; gap> L := LeftTranslations(S);; gap> R := RightTranslations(S);; gap> l := OneOp(Representative(L));; gap> r := OneOp(Representative(R));; gap> H := TranslationalHull(S);; gap> x := Bitranslation(H, l, r);; gap> IsBitranslation(x); true gap> IsSemigroupTranslation(x); false
‣ IsSemigroupTranslationCollection( obj ) | ( filter ) |
‣ IsLeftTranslationCollection( obj ) | ( filter ) |
‣ IsRightTranslationCollection( obj ) | ( filter ) |
‣ IsBitranslationCollection( obj ) | ( filter ) |
Returns: true or false
Every collection of left-, right-, or bi-translations belongs to the respective category IsXTranslationCollection.
‣ LeftPartOfBitranslation( h ) | ( function ) |
‣ RightPartOfBitranslation( arg ) | ( function ) |
Returns: a left or right translation
For a Bitranslation h consisting of a linked pair \((l, r)\), of left and right translations, LeftPartOfBitranslation(b) returns the left translation l, and RightPartOfBitranslation(b) returns the right translation r.
‣ LeftTranslation( T, x[, y] ) | ( operation ) |
‣ RightTranslation( arg1, arg2 ) | ( operation ) |
Returns: a left or right translation
For the semigroup T of left or right translations of a semigroup \( S\) and x one of:
a mapping on the underlying semigroup; note that in this case only the values of the mapping on the UnderlyingRepresentatives of T are checked and used, so mappings which do not define translations can be used to create translations if they are valid on that subset of S;
a list of indices representing the images of the UnderlyingRepresentatives of T, where the ordering is that of PositionCanonical (11.1-2) on S;
(for LeftTranslation) a list of length Length(Rows(S)) containing elements of UnderlyingSemigroup(S); in this case S must be a normalised Rees matrix semigroup and y must be a Transformation of Rows(S);
(for RightTranslation) a list of length Length(Columns(S)) containing elements of UnderlyingSemigroup(S); in this case S must be a normalised Rees matrix semigroup and y must be a Transformation of Columns(S);
LeftTranslation and RightTranslation return the corresponding translations.
gap> S := RectangularBand(3, 4);; gap> L := LeftTranslations(S);; gap> s := AsList(S)[1];; gap> map := MappingByFunction(S, S, x -> s * x);; gap> l := LeftTranslation(L, map); <left translation on <regular transformation semigroup of size 12, degree 8 with 4 generators>> gap> s ^ l; Transformation( [ 1, 2, 1, 1, 5, 5, 5, 5 ] )
‣ Bitranslation( H, l, r ) | ( operation ) |
Returns: a bitranslation
If H is a translational hull over a semigroup \(S\), and l and r are linked left and right translations respectively over \(S\), then this function returns the bitranslation \((\textit{l}, \textit{r})\). If l and r are not linked, then an error is produced.
gap> G := Group((1, 2), (3, 4));; gap> A := AsList(G);; gap> mat := [[A[1], 0], > [A[2], A[2]]];; gap> S := ReesZeroMatrixSemigroup(G, mat);; gap> L := LeftTranslations(S);; gap> R := RightTranslations(S);; gap> l := LeftTranslation(L, MappingByFunction(S, S, s -> S.1 * s));; gap> r := RightTranslation(R, MappingByFunction(S, S, s -> s * S.1));; gap> H := TranslationalHull(S);; gap> x := Bitranslation(H, l, r); <bitranslation on <regular semigroup of size 17, with 4 generators>>
‣ UnderlyingSemigroup( S ) | ( attribute ) |
‣ UnderlyingSemigroup( arg ) | ( attribute ) |
Returns: a semigroup
Given a semigroup of translations or bitranslations, returns the semigroup on which these translations act.
‣ LeftTranslationsSemigroupOfFamily( fam ) | ( attribute ) |
‣ RightTranslationsSemigroupOfFamily( arg ) | ( attribute ) |
‣ TranslationalHullOfFamily( arg ) | ( attribute ) |
Returns: the semigroup of left or right translations, or the translational hull
Given a family fam of left-, right- or bi-translations, returns the translations semigroup or translational hull to which they belong.
gap> S := RectangularBand(3, 3);; gap> L := LeftTranslations(S);; gap> l := Representative(L);; gap> LeftTranslationsSemigroupOfFamily(FamilyObj(l)) = L; true gap> H := TranslationalHull(S);; gap> h := Representative(H);; gap> TranslationalHullOfFamily(FamilyObj(h)) = H; true
‣ TypeLeftTranslationsSemigroupElements( arg ) | ( attribute ) |
‣ TypeRightTranslationsSemigroupElements( arg ) | ( attribute ) |
‣ TypeBitranslations( arg ) | ( attribute ) |
Returns: a type
Given a (bi)translations semigroup, returns the type of the elements that it contains.
‣ LeftTranslations( S ) | ( attribute ) |
‣ RightTranslations( arg ) | ( attribute ) |
Returns: the semigroup of left or right translations
Given a finite semigroup S satisfying CanUseFroidurePin (6.1-4), returns the semigroup of all left or right translations of S.
gap> S := Semigroup([Transformation([1, 4, 3, 3, 6, 5]), > Transformation([3, 4, 1, 1, 4, 2])]);; gap> L := LeftTranslations(S); <the semigroup of left translations of <transformation semigroup of degree 6 with 2 generators>> gap> Size(L); 361
‣ TranslationalHull( S ) | ( attribute ) |
Returns: the translational hull
Given a finite semigroup S satisfying CanUseFroidurePin (6.1-4), returns the translational hull of S.
gap> S := Semigroup([Transformation([1, 4, 3, 3, 6, 5]), > Transformation([3, 4, 1, 1, 4, 2])]);; gap> H := TranslationalHull(S); <translational hull over <transformation semigroup of degree 6 with 2 generators>> gap> Size(H); 38
‣ NrLeftTranslations( S ) | ( attribute ) |
‣ NrRightTranslations( arg ) | ( attribute ) |
‣ NrBitranslations( arg ) | ( attribute ) |
Returns: the number of left-, right-, or bi-translations
Given a finite semigroup S satisfying CanUseFroidurePin (6.1-4), returns the number of left-, right-, or bi-translations of S. This is typically more efficient than calling Size(LeftTranslations(S)), as the [bi]translations may not be produced.
gap> S := Semigroup([Transformation([1, 4, 3, 3, 6, 5, 2]), > Transformation([3, 4, 1, 1, 4, 2])]);; gap> NrLeftTranslations(S); 1444 gap> NrRightTranslations(S); 398 gap> NrBitranslations(S); 69
‣ InnerLeftTranslations( S ) | ( attribute ) |
‣ InnerRightTranslations( arg ) | ( attribute ) |
Returns: the monoid of inner left or right translations
For a finite semigroup S satisfying CanUseFroidurePin (6.1-4), InnerLeftTranslations(S) returns the inner left translations of S (i.e. the translations defined by left multiplication by a fixed element of S), and InnerRightTranslations(S) returns the inner right translations of S (i.e. the translations defined by right multiplication by a fixed element of S).
gap> S := Semigroup([Transformation([1, 4, 3, 3, 6, 5]), > Transformation([3, 4, 1, 1, 4, 2])]);; gap> I := InnerLeftTranslations(S); <left translations semigroup over <transformation semigroup of size 22, degree 6 with 2 generators>> gap> Size(I) <= Size(S); true
‣ InnerTranslationalHull( S ) | ( attribute ) |
Returns: the inner translational hull
Given a finite semigroup S satisfying CanUseFroidurePin (6.1-4), returns the inner translational hull of S, i.e. the bitranslations whose left and right translation components are inner translations defined by left and right multiplication by the same fixed element of S.
gap> S := Semigroup([Transformation([1, 4, 3, 3, 6, 5]), > Transformation([3, 4, 1, 1, 4, 2])]);; gap> I := InnerTranslationalHull(S); <semigroup of bitranslations over <transformation semigroup of size 22, degree 6 with 2 generators>> gap> L := LeftTranslations(S);; gap> R := RightTranslations(S);; gap> H := TranslationalHull(S);; gap> inners := [];; gap> for s in S do > l := LeftTranslation(L, MappingByFunction(S, S, x -> s * x)); > r := RightTranslation(R, MappingByFunction(S, S, x -> x * s)); > AddSet(inners, Bitranslation(H, l, r)); > od; gap> Set(I) = inners; true
‣ UnderlyingRepresentatives( T ) | ( attribute ) |
Returns: a set of representatives
For efficiency, we typically store translations on a semigroup \(S\) as their actions on a small subset of \(S\). For left translations, this is a set of representatives of the maximal \(\mathscr{R}\)-classes of \(S\); dually for right translations we use representatives of the maximal \(\mathscr{L}\)-classes. You can use UnderlyingRepresentatives to access these representatives.
gap> G := Range(IsomorphismPermGroup(SmallGroup(12, 1)));; gap> mat := [[G.1, G.2], [G.1, G.1], > [G.2, G.3], [G.1 * G.2, G.1 * G.3]];; gap> S := ReesMatrixSemigroup(G, mat);; gap> L := LeftTranslations(S);; gap> R := RightTranslations(S);; gap> UnderlyingRepresentatives(L); [ (1,(),1), (2,(),2) ] gap> UnderlyingRepresentatives(R); [ (1,(),1), (2,(),2), (1,(),3), (1,(),4) ]
‣ ImageSetOfTranslation( t ) | ( operation ) |
Returns: a set of elements
Given a left or right translation t on a semigroup \(S\), returns the set of elements of \(S\) lying in the image of t.
gap> S := Semigroup([Transformation([1, 3, 3, 4]), > Transformation([3, 4, 1, 2])]);; gap> t := Set(LeftTranslations(S))[4]; <left translation on <transformation semigroup of size 8, degree 4 with 2 generators>> gap> ImageSetOfTranslation(t); [ Transformation( [ 1, 2, 3, 1 ] ), Transformation( [ 1, 3, 3, 1 ] ), Transformation( [ 3, 1, 1, 3 ] ), Transformation( [ 3, 4, 1, 3 ] ) ]
generated by GAPDoc2HTML