4519.sagews

This worksheet describes a set of functions that deal with the free algebra $Q\langle Y \rangle$ where $Y = \left\{ y_i \right\}_{i \in \mathbb{N}}$ with the stuffle product (which will be denoted here by $\star$).
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+'stuffle2.sage')

is_primitive(Pi(Mots(Word([F.gens()[3]]))))

True

The alphabet in this context is $\left\{ y_i \right\}_{i \in \mathbb{N}}$. The free algebra $k \langle Y \rangle$ is endowed with the stuffle product defined by the following recursion : $u \star 1 = 1 \star u = u$ ;
$y_i u \star y_j v = y_i ( u \star y_j v ) + y_j ( y_i u \star v ) + y_{i+j} ( u \star v)$. for all $y_i, \, y_j \in Y$ and for all $u , \, v \in Y^*$. We define on $k \langle Y \rangle$ a gradation with values in $\mathbb N$ given by an integer valued weight function on $Y^*$. It is a morphism of monoids given on the letters by $|y_s| = s$. Thus $|w| = \displaystyle \sum_{k=1}^{\ell(w)}|w\left[ k \right]|$. First, we need to be able to define words. The non commutative variables $y_i$, $i=0 \dots 19$ are the elements of the list F.gens() (F is a Free Monoid used only to provide the variables) :

F.gens()[4]

y4

The set of words over these variable is called Mo

Mots

Words over Ordered Alphabet [y1, y2, y3, y4, y5, y6, y7, y8, y9, y10, y11, y12, y13, y14, y15, y16, y17, y18, y19]

You can call a single word using the following command (We form the Word defined by the list of letters and then precise that this word belongs to the set Mots) :

w=Mots(Word([F.gens()[4],F.gens()[3],F.gens()[2]]))
w

word: y4,y3,y2

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 :

w.is_lyndon()

False

Each letter has a weight which is given by its index in the list F.gens()

letter=F.gens()[4]
F.gens().index(letter)

4

The weight of a word is returned by the function weight_word :

weight_word(w)

9

The set of all words of a given weight is returned by Mots_n :

Mots_n(5)

[word: y1,y1,y1,y1,y1, word: y1,y1,y1,y2, word: y1,y1,y2,y1, word: y1,y2,y1,y1, word: y2,y1,y1,y1, word: y1,y1,y3, word: y1,y2,y2, word: y1,y3,y1, word: y2,y1,y2, word: y2,y2,y1, word: y3,y1,y1, word: y1,y4, word: y2,y3, word: y3,y2, word: y4,y1, word: y5]

[weight_word(u) for u in Mots_n(5)]

[5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5]

The free algebra on $Y$ is defined as a Combinatorial Free Module with basis the set Mots called Module

Module

Free module generated by Words over Ordered Alphabet [y1, y2, y3, y4, y5, y6, y7, y8, y9, y10, y11, y12, y13, y14, y15, y16, y17, y18, y19] over Rational Field

The function toA converts words into elements of Module :

toA(w)

B[word: y4,y3,y2]

The stuffle product of two words is computed with the function stuffle_words :

stuffle_words(Mots(Word([F.gens()[2],F.gens()[1]])),Mots(Word([F.gens()[2]])))

B[word: y2,y1,y2] + 2*B[word: y2,y2,y1] + B[word: y2,y3] + B[word: y4,y1]

The tensor product (denoted by $\#$) of $Q \langle Y \rangle$ with itself is implemented with the function TensorProduct :

t1=2*Module(Mots(Word([F.gen(1),F.gen(2)])))+3*Module(Mots(Word([F.gen(4)])))
t2=4*Module(Mots(Word([F.gen(3)])))+5*Module(Mots(Word([F.gen(5)])))
TensorProduct(t1,t2)

8*B[word: y1,y2] # B[word: y3] + 10*B[word: y1,y2] # B[word: y5] + 12*B[word: y4] # B[word: y3] + 15*B[word: y4] # B[word: y5]

Its algebra structure is given by prod_TP which computes the product of two tensor products :

T1=TensorProduct(t1,3)
T2=TensorProduct(t1,t2)
prod_TP(T1,T2)

48*B[word: y1,y2,y1,y2] # B[word: y3] + 60*B[word: y1,y2,y1,y2] # B[word: y5] + 72*B[word: y1,y2,y4] # B[word: y3] + 90*B[word: y1,y2,y4] # B[word: y5] + 72*B[word: y4,y1,y2] # B[word: y3] + 90*B[word: y4,y1,y2] # B[word: y5] + 108*B[word: y4,y4] # B[word: y3] + 135*B[word: y4,y4] # B[word: y5]

The stuffle algebra has a bialgebra structure. The coproduct $\Delta_{\star}$ is defined by : $\Delta_\star (y_\ell) = y_\ell \# 1 + 1 \# y_\ell + \displaystyle \sum_{j+k = \ell} y_j \# y_k$ and extended as a morphism of algebras to $Q \langle Y \rangle$. Here, the coproduct is called Delta_stuffle for both words and series :

Delta_stuffle(Mots(Word([F.gens()[3]])))

B[word: ] # B[word: y3] + B[word: y1] # B[word: y2] + B[word: y2] # B[word: y1] + B[word: y3] # B[word: ]

Delta_stuffle(t1)

B[word: ] # B[word: y3] + B[word: y1] # B[word: y2] + B[word: y2] # B[word: y1] + B[word: y3] # B[word: ]

This gives birth to a test of the primitivity of an element, is_primitive :

is_primitive(3*Module(Mots(Word([F.gens()[4],F.gens()[3]]))))

False

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

S=2*Module(EmptyWord)+3*Module(w)
c1=ScalProd(S,EmptyWord)
c2=ScalProd(S,w)
c3=ScalProd(2,w)
c4=ScalProd(S,Mots(Word([F.gens()[17]])))
c1,c2,c3,c4

(2, 3, 0, 0)

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

SPSeries(2*Module(Mots(Word([F.gen(4)])))+4*Module(EmptyWord),2*Module(Mots(Word([F.gen(3)])))+4*Module(Mots(Word([F.gen(4)]))))

8

We are now in position to add the stuffle product of two series which is computed as follows : $\langle S \star T | w \rangle = \langle S \# T | \Delta_\star (w) \rangle = \displaystyle \sum_{u \star v = w} \langle S | u \rangle \langle T | v \rangle u \# v$ To compute the stuffle product of two series, use the function StuffSeries_Delta :

StuffSeries_Delta(Module(Mots(Word([F.gen(3)]))),2*Module(Mots(Word([F.gen(1),F.gen(2)])))+3*Module(Mots(Word([F.gen(1)]))))

2*B[word: y1,y2,y3] + 3*B[word: y1,y3] + 2*B[word: y1,y3,y2] + 2*B[word: y1,y5] + 3*B[word: y3,y1] + 2*B[word: y3,y1,y2] + 3*B[word: y4] + 2*B[word: y4,y2]

We implemented the basis of the stuffle algebra equivalent to the $S$ basis of Reutenauer (see Reutenauer, Free Lie algebras, Clarendon Press, 1993). It is defined as follows : $S_{1^{Y^*}} = 1$ ;
$S_{y_k u} = y_k S_u$ if $y_k u$ is a Lyndon word ;
$S_w = \frac{1}{\alpha_1! \dots \alpha_k !} S^{\star \, \alpha_1}_{\ell_1} \star \dots \star S^{\star \, \alpha_k}_{\ell_k}$ if $w = \ell_1^{\alpha_1} \dots \ell_{k}^{\alpha_k}$ is the Lyndon factorization of w, and called Sbasis :

Sbasis(Mots(Word([F.gens()[3],F.gens()[2]])))

B[word: y2,y3] + B[word: y3,y2] + B[word: y5]