Copy of Free Algebra -- Sage

This worksheet describes a set of functions that deal with the free algebra $Q\langle a,b \rangle$ on two generators with the shuffle product and implement its bialgebra structure and some of its bases.
Before getting started, you need to make sure that the functions are loaded in this session. To do so, evaluate the following commands (the result of the second one should be 'True') :

load(DATA+'FreeAlgebra.sage')

is_primitive(PBW(Word('ab')))

True

True

First, we need to work with words. The word 'foo' is called with the command Word('foo'). For example :

Word('abbb')

A lot of functions relative to words are already defined in sage. For example, it is easy to know if a word is a Lyndon word, using the following :

Word('abb').is_lyndon()

True

True

The first basis that I implemented is the Poincaré-Birkhoff-Witt basis of $Q\langle a,b \rangle$. For its definition, see Reutenauer, Free Lie algebras, Clarendon Press, 1993.
Its elements are indexed by words and denoted by $P_w$. If $w = \ell$ is a Lyndon word, then $P_\ell$ is obtained by standard bracketing :

w=Word('abb')

w.is_lyndon()

True

True

Pol=PBW(w) Pol

a*b^2 - 2*b*a*b + b^2*a

a*b^2 - 2*b*a*b + b^2*a

By the way, the standard bracketing of a word is implemented in Sage and you can call it with LW.standard_bracketing(mot) :

LW.standard_bracketing(Word('ab'))

['a', 'b']

['a', 'b']

You can "realize" this bracketing as a series using the function expbrack :

expbrack(LW.standard_bracketing(Word('ab')))

a*b - b*a

a*b - b*a

The usual scalar product (which returns the coefficient of a word in a polynomial) is called ScalProd :

c1=ScalProd(Pol,Word('abb')) c2=ScalProd(Pol,Word('abbbbb')) c3=ScalProd(Pol,Word('')) c1,c2,c3

(1, 0, 0)

(1, 0, 0)

This allows us to implement the counit $\epsilon$ that returns the constant term of a series :

S=34+a*a*a*b epsilon(S)

epsilon(Pol)

It is extended through the function SP_Series to $Q \langle \langle a , b \rangle \rangle \otimes Q \langle a , b \rangle$ :

S1=3+3*a*b+4*b^2

S2=3*a*b*a*b+4

SPSeries(S1,S2)

I implemented two reciprocal morphisms between $\left\{ a , b \right\}^*$ and $k \langle a , b \rangle$ : toA and toWord.

toA(Word('abbba'))

a*b^3*a

a*b^3*a

toWord(_)

word: abbba

word: abbba

toWord(toA(Word('abba')))==Word('abba')

True

True

toA(toWord(a*b*a*b))==a*b*a*b

True

True

To go further, we need a tensor structure for $Q \langle \langle a , b \rangle \rangle \otimes Q \langle \langle a , b \rangle \rangle$. I constructed a Combinatorial Free Module which has the free monoid $\left\{ a , b \right\}^*$ as a basis. This module is called 'Module' :

Module.basis()[Word('ab')]

B[word: ab]

B[word: ab]

The tensor product of two monomials of this module is computed with TP_free_algebra :

TP_free_algebra(a*b,2*a*b*a)

2*B[a*b] # B[a*b*a]

2*B[a*b] # B[a*b*a]

The product of two tensor products is called prod_TP :

t1=TP_free_algebra(a*b,2*a*b*a) t2=TP_free_algebra(a*b,3*b*a) t1,t2

(2*B[a*b] # B[a*b*a], 3*B[a*b] # B[b*a])

(2*B[a*b] # B[a*b*a], 3*B[a*b] # B[b*a])

prod_TP(t1,t2)

6*B[a*b*a*b] # B[a*b*a*b*a]

6*B[a*b*a*b] # B[a*b*a*b*a]

In fact, TP_free_algebra is designed for series :

TP_free_algebra(Pol,Pol)

B[a*b^2] # B[a*b^2] - 2*B[a*b^2] # B[b*a*b] + B[a*b^2] # B[b^2*a] -
2*B[b*a*b] # B[a*b^2] + 4*B[b*a*b] # B[b*a*b] - 2*B[b*a*b] # B[b^2*a] +
B[b^2*a] # B[a*b^2] - 2*B[b^2*a] # B[b*a*b] + B[b^2*a] # B[b^2*a]

B[a*b^2] # B[a*b^2] - 2*B[a*b^2] # B[b*a*b] + B[a*b^2] # B[b^2*a] - 2*B[b*a*b] # B[a*b^2] + 4*B[b*a*b] # B[b*a*b] - 2*B[b*a*b] # B[b^2*a] + B[b^2*a] # B[a*b^2] - 2*B[b^2*a] # B[b*a*b] + B[b^2*a] # B[b^2*a]

The shuffle product of two words is implemented in Sage. I added the shuffle product of two series (ShuffSeries) :

ShuffSeries(Pol,Pol)

12*a^2*b^4 - 6*a*b*a*b^3 - 12*a*b^2*a*b^2 - 6*a*b^3*a*b + 12*a*b^4*a -
24*b*a^2*b^3 + 6*b*a*b*a*b^2 + 12*b*a*b^2*a*b - 6*b*a*b^3*a +
36*b^2*a^2*b^2 + 6*b^2*a*b*a*b - 12*b^2*a*b^2*a - 24*b^3*a^2*b -
6*b^3*a*b*a + 12*b^4*a^2

12*a^2*b^4 - 6*a*b*a*b^3 - 12*a*b^2*a*b^2 - 6*a*b^3*a*b + 12*a*b^4*a - 24*b*a^2*b^3 + 6*b*a*b*a*b^2 + 12*b*a*b^2*a*b - 6*b*a*b^3*a + 36*b^2*a^2*b^2 + 6*b^2*a*b*a*b - 12*b^2*a*b^2*a - 24*b^3*a^2*b - 6*b^3*a*b*a + 12*b^4*a^2

In fact, the shuffle product of two series uses the coproduct $\Delta$ which corresponds to the function Delta (defined for words as well as for series) :

Delta(Word('ab'))

B[1] # B[a*b] + B[a] # B[b] + B[b] # B[a] + B[a*b] # B[1]

B[1] # B[a*b] + B[a] # B[b] + B[b] # B[a] + B[a*b] # B[1]

Delta(Pol)

B[1] # B[a*b^2] - 2*B[1] # B[b*a*b] + B[1] # B[b^2*a] + B[a*b^2] # B[1]
- 2*B[b*a*b] # B[1] + B[b^2*a] # B[1]

B[1] # B[a*b^2] - 2*B[1] # B[b*a*b] + B[1] # B[b^2*a] + B[a*b^2] # B[1] - 2*B[b*a*b] # B[1] + B[b^2*a] # B[1]

The coproduct $\Delta$ allows us to test if an element is primitive ($\Delta (P) = P \otimes 1 + 1 \otimes P$). The function is_primitive tests this property. The elements of the Poincaré-Birkhoff-Witt basis for Lyndon words are primitive elements.

is_primitive(Pol)

True

True

d1=is_primitive(PBW(Word('aba'))) d2=Word('aba').is_lyndon() print(d1,d2)

(False, False)

(False, False)

Two more bases are implemented. They are called Sbasis and Sbasistilde. The former is defined in the book of Reutenauer (it is dual to the PBW basis). The latter is almost the same, except that for Lyndon words, it returns the word :

Sbasis(Word('aabab'))

2*a^3*b^2 + a^2*b*a*b

2*a^3*b^2 + a^2*b*a*b

Sbasistilde(Word('aabab'))

a^2*b*a*b

a^2*b*a*b

You can check that the PBW basis and the S basis are dual to one another :

for mot in Words('ab',3): print(mot==Word('abb'),SPSeries(Pol,Sbasis(mot)))

(False, 0)
(False, 0)
(False, 0)
(True, 1)
(False, 0)
(False, 0)
(False, 0)
(False, 0)

(False, 0)
(False, 0)
(False, 0)
(True, 1)
(False, 0)
(False, 0)
(False, 0)
(False, 0)

It is possible to compute the expansion (the algorithm is very similar to Euclid's algorithm) of a series on the PBW basis and on the basis Sbasistilde with the functions devP and devS. In each case, the first argument is the series whose expansion one wants to know and the second argument is an empty list (needed for the recursive call needed by the underlying algorithm) the result is a list of couples (word,coefficient) :

devP(a*b*a*b,[])

[(word: abab, 1), (word: baba, -1), (word: baab, 3), (word: abba, 3),
(word: abab, -3), (word: aabb, -2)]

[(word: abab, 1), (word: baba, -1), (word: baab, 3), (word: abba, 3), (word: abab, -3), (word: aabb, -2)]

devP(Pol,[])

[(word: abb, 1)]

[(word: abb, 1)]

devS(Pol,[])

[(word: bba, 1), (word: bab, -3), (word: abb, 6)]

[(word: bba, 1), (word: bab, -3), (word: abb, 6)]

The antipode is called antipode. It is defined for word and for series :

antipode(2*b*a+3*b*a*a)

2*a*b - 3*a^2*b

2*a*b - 3*a^2*b

The .sage file contains some more functions that are used in the background. I let you discover them by yourself.

Copy of Free Algebra

4224 days ago by comphy