Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Bib Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

18 Translations
 18.1 Methods for translations

18 Translations

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

18.1 Methods for translations

18.1-1 IsXTranslation
‣ 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

18.1-2 IsBitranslation
‣ 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

18.1-3 IsXTranslationCollection
‣ 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.

18.1-4 XPartOfBitranslation
‣ 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.

18.1-5 XTranslation
‣ 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:

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

18.1-6 Bitranslation
‣ 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>>

18.1-7 UnderlyingSemigroup
‣ UnderlyingSemigroup( S )( attribute )
‣ UnderlyingSemigroup( arg )( attribute )

Returns: a semigroup

Given a semigroup of translations or bitranslations, returns the semigroup on which these translations act.

18.1-8 XTranslationsSemigroupOfFamily
‣ 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

18.1-9 TypeXTranslationSemigroupElements
‣ 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.

18.1-10 XTranslations
‣ 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

18.1-11 TranslationalHull
‣ 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

18.1-12 NrXTranslations
‣ 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

18.1-13 InnerXTranslations
‣ 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

18.1-14 InnerTranslationalHull
‣ 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

18.1-15 UnderlyingRepresentatives
‣ 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) ]

18.1-16 ImageSetOfTranslation
‣ 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 ] ) ]
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Bib Ind

generated by GAPDoc2HTML