[GAP Forum] Re:Extending Orderings, perhaps better posed

[Alexander Hulpke]

Dear Randy Cone,

> I've tried this, and gotten some unexpected results.  Perhaps you  
> could
> explain where I've gone wrong:

Essentially, the elements of the algebra will be different objects  
than the elements of the (semi)group. (When working by hand one often  
identifies the semigroup with a subset of the algebra, on the  
computer we have to be picky.)

What will happen is that the algebra elements are new kinds of  
objects that just multiply using the underlying semigroup.
Thus you could do the following:

gap> G:=FreeSemigroup(2);
<free semigroup on the generators [ s1, s2 ]>
gap> B:=FreeMagmaRing(Rationals,G);
<algebra over Rationals, with 2 generators>
gap> gensB:=GeneratorsOfAlgebra(B);
[ (1)*s1, (1)*s2 ]
gap> elm:=gensB[1]^3*gensB[2];
(1)*s1^3*s2
gap> map:=Embedding(G,B);
<mapping: Semigroup( [ s1, s2 ] ) -> Algebra( Rationals, [ (1)*s1, (1) 
*s2
] ) >
gap> Image(map,G.1*G.2);
(1)*s1*s2
gap> PreImagesRepresentative(map,elm);
s1^3*s2

You see that algebra elements are displayed differently, essentially  
with a prefixed (1)*. However they are really different objects:
gap> G.1;
s1
gap> B.1;
(1)*s1
gap> G.1=B.1;
false

If you need to do the translation between semigroup and algebra  
often, there is a bit of overhead in using the embedding as it tests  
validity of arguments -- you might just want to access the data  
structures more directly as the code in lib/mgmring.gi does.

(I would argue that in your example the call of `Algebra' with  
semigroup generators should produce an error message.)

>
>
>> The other option would be to write small functions that
>> take a monomial and build a ``corresponding'' semigroup
>> element, using these ``shadows'' for comparison.
>>
>
> My hope was to stay away from such machinery, and act on the objects
> (monomials of free algebras) directly as associative words.  Then, any
> improvements or extensions to the work on associative words would  
> translate
> naturally to such objects.  For example, I've implemented the  
> Horspool subword
> search algorithm for associative words.  Guess I'm outta luck, and  
> should
> consider coding orderings, subword search, overlap, etc. for  
> elements of free
> algebras?

As said above, algebra elements and words in the semigroup are really  
different objects. However I don't think that having to apply the  
embedding will be a messup of the rest of the code -- my guess is  
that there are only very few localized places where this happens.

All the best,

      Alexander Hulpke