︠0bbe51b1-d522-4922-ad75-b24d54634cdei︠ %html 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') : ︡4e328c60-b9b3-4029-b458-b5ba7029d998︡{"html": "\r\nThis 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$).\r\n
\r\nBefore 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') :"}︡ ︠f09d45f5-2f49-49bd-8380-9b226b9684e3︠ load(DATA+'stuffle2.sage') ︡8a317dce-507d-4897-9a23-59d18adc6825︡︡ ︠249f3b65-142b-4b48-a71b-0712da21c4bf︠ is_primitive(Pi(Mots(Word([F.gens()[3]])))) ︡5b2aa644-5fab-4902-80af-88fea6ff3bae︡{"stdout": "True"}︡ ︠b6895664-43f1-4de6-a628-67be8a072757i︠ %html 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) : ︡dbc35892-eab6-4d81-8d19-1c4613664b42︡{"html": "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 :\r\n
\r\n$u \\star 1 = 1 \\star u = u$ ;
\r\n$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)$.\r\n
\r\nfor all $y_i, \\, y_j \\in Y$ and for all $u , \\, v \\in Y^*$.\r\n\r\nWe 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\r\n
\r\n\t$|w| = \\displaystyle \\sum_{k=1}^{\\ell(w)}|w\\left[ k \\right]|$.\r\n
\r\n\r\nFirst, 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) :\r\n"}︡ ︠ccbf4bcc-97d6-46fe-9c25-b66754ca4585︠ F.gens()[4] ︡35aff08b-c24d-4e6b-a320-3814b118e2d2︡{"stdout": "y4"}︡ ︠f843a078-d539-41cc-8eb7-381c0c0b8660i︠ %html The set of words over these variable is called Mots. ︡7e5da605-d9ee-4c40-a970-7186d5b2653b︡{"html": "\r\nThe set of words over these variable is called Mots."}︡ ︠19e667c8-8cf1-49a8-849c-42ef6d16c9e7︠ Mots ︡b48def75-222e-4bf1-8177-107c0078f6ff︡{"stdout": "Words over Ordered Alphabet [y1, y2, y3, y4, y5, y6, y7, y8, y9, y10, y11, y12, y13, y14, y15, y16, y17, y18, y19]"}︡ ︠b6603cc9-596a-415c-800f-682897f3b053i︠ %html 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) : ︡75255809-753c-4b37-b243-84f705965d72︡{"html": "\r\nYou 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) :\r\n"}︡ ︠d23348cd-aff4-4f67-85cb-42ac3c4615b4︠ w=Mots(Word([F.gens()[4],F.gens()[3],F.gens()[2]])) w ︡ee4548fd-ba48-4698-a931-d4ea19b13485︡{"stdout": "word: y4,y3,y2"}︡ ︠bb9eeb09-3d47-4fff-b635-9b8665e14f83i︠ %html 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 : ︡6ad68c80-8c93-4a89-9da0-cb81f4fb085c︡{"html": "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 :\r\n"}︡ ︠11681fd9-f139-40fc-9b3d-36a6422ac6ea︠ w.is_lyndon() ︡ea6696b1-1c6f-4b1e-a40d-1c307cac7999︡{"stdout": "False"}︡ ︠e67a98dc-42f7-4133-8548-529a8ce15c74i︠ %html Each letter has a weight which is given by its index in the list F.gens() : ︡f14c9890-28e6-41f0-840e-5fba98be9f2d︡{"html": "Each letter has a weight which is given by its index in the list F.gens() :"}︡ ︠db50b272-2838-4235-b2ca-23d56715bd56︠ letter=F.gens()[4] F.gens().index(letter) ︡67f90478-3c72-48dc-9b16-5990c7a78248︡{"stdout": "4"}︡ ︠a30c2cdb-741e-4fdc-9f32-a27cfc9ba23bi︠ %html The weight of a word is returned by the function weight_word : ︡47aab2a2-606f-467b-b94a-1eeb1558fecd︡{"html": "\r\nThe weight of a word is returned by the function weight_word :\r\n"}︡ ︠b939dcb9-eb80-46e2-9386-832592eeb600︠ weight_word(w) ︡2e1e1ed7-e085-4afd-96d0-5c83ddb12099︡{"stdout": "9"}︡ ︠92ec26f1-a48c-48a4-a578-e4dbb682fe30i︠ %html The set of all words of a given weight is returned by Mots_n : ︡a0a7df42-e8f4-4cef-8545-967030285334︡{"html": "\r\nThe set of all words of a given weight is returned by Mots_n :\r\n"}︡ ︠ff465158-aa87-488f-bcbc-f9eb4af5a3c8︠ Mots_n(5) ︡889cc2b8-b3ac-4ddc-b497-bd1a32c6514c︡{"stdout": "[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]"}︡ ︠a5ede60c-61a1-4aa7-a048-e12b7932e0f4︠ [weight_word(u) for u in Mots_n(5)] ︡cfbf6e68-ca00-4c77-bd02-b1ff9758863a︡{"stdout": "[5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5]"}︡ ︠9ad6ae4d-4aa0-49f6-8c43-3c02029241f2i︠ %html The free algebra on $Y$ is defined as a Combinatorial Free Module with basis the set Mots called Module ︡dc07936e-cc26-46b9-b3d7-fd996e0928d1︡{"html": "\r\nThe free algebra on $Y$ is defined as a Combinatorial Free Module with basis the set Mots called Module\r\n"}︡ ︠0c249dbb-5caf-41cb-aa01-a8953b122266︠ Module ︡bd0f3882-43e4-4b2f-8a6a-ab8fc91c689f︡{"stdout": "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"}︡ ︠ea4832b9-93b6-4b7b-bd63-3f776da818c9i︠ %html The function toA converts words into elements of Module : ︡5ccdf179-3f2f-40a9-81a6-b79a9ae0cdc4︡{"html": "\r\nThe function toA converts words into elements of Module :\r\n"}︡ ︠57fd3ce6-cc7f-4e5a-981b-e55a882b54a3︠ toA(w) ︡cd6793db-2826-48e0-8d1e-fb021c9b6ff2︡{"stdout": "B[word: y4,y3,y2]"}︡ ︠a021bc05-3d37-47cf-b920-bd8c7ef019eci︠ %html The stuffle product of two words is computed with the function stuffle_words : ︡fe58da76-9b75-49f9-a982-f7514446ce05︡{"html": "\r\nThe stuffle product of two words is computed with the function stuffle_words :\r\n"}︡ ︠37794ec4-dffc-49f2-bc9c-28dc5806fd44︠ stuffle_words(Mots(Word([F.gens()[2],F.gens()[1]])),Mots(Word([F.gens()[2]]))) ︡7cbf46d0-1bf4-4dc7-89c5-7b46b008c708︡{"stdout": "B[word: y2,y1,y2] + 2*B[word: y2,y2,y1] + B[word: y2,y3] + B[word: y4,y1]"}︡ ︠785410de-4c9b-49fb-8696-d423ebc59f12i︠ %html The tensor product (denoted by $\#$) of $Q \langle Y \rangle$ with itself is implemented with the function TensorProduct : ︡b995fd79-106d-4b20-8afa-f86ffd73c48c︡{"html": "\r\nThe tensor product (denoted by $\\#$) of $Q \\langle Y \\rangle$ with itself is implemented with the function TensorProduct :\r\n"}︡ ︠967fceea-6aba-44ad-8756-408e11e20eb6︠ 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) ︡d993f4fd-d824-4024-84f7-67bc28c406a8︡{"stdout": "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]"}︡ ︠ca7842ba-9e83-47ff-b148-2184761a984ci︠ %html Its algebra structure is given by prod_TP which computes the product of two tensor products : ︡d8ca80f7-6ac5-4015-b64b-b93e1b537f90︡{"html": "\r\nIts algebra structure is given by prod_TP which computes the product of two tensor products :\r\n"}︡ ︠bb34e056-b289-43bd-a32b-30bb86c19f36︠ T1=TensorProduct(t1,3) T2=TensorProduct(t1,t2) prod_TP(T1,T2) ︡7beba037-ed86-45dc-8161-a34ff3b9ea51︡{"stdout": "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]"}︡ ︠5b31476a-25ed-4ec2-aeec-3eb5492449a7i︠ %html 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 : ︡76af1579-3bb1-4e7d-b2b8-f3afb288fa54︡{"html": "\r\nThe stuffle algebra has a bialgebra structure. The coproduct $\\Delta_{\\star}$ is defined by :\r\n
\r\n$\\Delta_\\star (y_\\ell) = y_\\ell \\# 1 + 1 \\# y_\\ell + \\displaystyle \\sum_{j+k = \\ell} y_j \\# y_k$\r\n
\r\nand extended as a morphism of algebras to $Q \\langle Y \\rangle$.\r\n\r\nHere, the coproduct is called Delta_stuffle for both words and series :\r\n"}︡ ︠4f9ba4bb-9004-4463-b8fb-f3e586396207︠ Delta_stuffle(Mots(Word([F.gens()[3]]))) ︡77d210e1-d254-4fa1-92bd-f66910709abd︡{"stdout": "B[word: ] # B[word: y3] + B[word: y1] # B[word: y2] + B[word: y2] # B[word: y1] + B[word: y3] # B[word: ]"}︡ ︠cd7a1d5e-8312-4e04-b0b4-fb25ea053197︠ Delta_stuffle(t1) ︡66de3889-7e3e-432f-b1b9-714ee47ef565︡{"stdout": "B[word: ] # B[word: y3] + B[word: y1] # B[word: y2] + B[word: y2] # B[word: y1] + B[word: y3] # B[word: ]"}︡ ︠0b559c7d-6365-42fd-a6f9-4f631689af17i︠ %html This gives birth to a test of the primitivity of an element, is_primitive : ︡a25be032-35c7-465b-aeb0-c255a983b8b6︡{"html": "\r\nThis gives birth to a test of the primitivity of an element, is_primitive :\r\n"}︡ ︠67ab9696-6fed-47b7-abe1-975892177dcf︠ is_primitive(3*Module(Mots(Word([F.gens()[4],F.gens()[3]])))) ︡77fbfba3-d7d7-4591-aab9-7b208a06bd5f︡{"stdout": "False"}︡ ︠4a80c078-71f9-4fb3-8ab4-817747d2027ei︠ %html The usual scalar product (which returns the coefficient of a word in a polynomial) is called ScalProd : ︡91afb382-aa8f-48b8-b9d1-9d901aa3e50e︡{"html": "\r\nThe usual scalar product (which returns the coefficient of a word in a polynomial) is called ScalProd :\r\n"}︡ ︠66b73104-cb01-4084-9fbd-72186517498a︠ 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 ︡212d589d-ca6d-4a6c-8531-4b6fa9c2ea77︡{"stdout": "(2, 3, 0, 0)"}︡ ︠3fcd8fe3-7be5-4c05-9141-8eb5d9392940i︠ %html It is extended through the function SP_Series to $Q \langle \langle a , b \rangle \rangle \# Q \langle a , b \rangle$ : ︡4f7d2401-abae-41e0-8e12-2651e59ab0dc︡{"html": "\r\nIt is extended through the function SP_Series to $Q \\langle \\langle a , b \\rangle \\rangle \\# Q \\langle a , b \\rangle$ :\r\n"}︡ ︠7bfac84c-5ad9-4516-9413-284667fe9131︠ 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)])))) ︡c6961448-9fff-41f5-b88a-29dfa96ebbbd︡{"stdout": "8"}︡ ︠7cbca3be-c3d7-4b41-9b2c-dcfe2701782fi︠ %html 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 : ︡4b076840-8505-4ea6-94c4-c44fd83a8663︡{"html": "\r\nWe are now in position to add the stuffle product of two series which is computed as follows :\r\n
\r\n$\\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$\r\n
\r\nTo compute the stuffle product of two series, use the function StuffSeries_Delta :\r\n"}︡ ︠abd189f2-184b-4e2f-8d6c-0233edc004e7︠ 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)])))) ︡d2a905b2-7dc0-4c1d-b1ea-fb6348cc6514︡{"stdout": "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]"}︡ ︠80669c5c-a2c0-4941-9759-1b5177cbc3e8i︠ %html 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 : ︡1dbe9f41-983d-4c90-909a-797a4f9a0e79︡{"html": "\r\nWe 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 :\r\n
\r\n$S_{1^{Y^*}} = 1$ ;\r\n
\r\n$S_{y_k u} = y_k S_u$ if $y_k u$ is a Lyndon word ;\r\n
\r\n$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,\r\n
\r\nand called Sbasis :\r\n"}︡ ︠f9737832-a695-4e84-a1d3-6b436bdfbc4c︠ Sbasis(Mots(Word([F.gens()[3],F.gens()[2]]))) ︡c8f5b3ab-1361-49bf-ace0-0b729d6800ea︡{"stdout": "B[word: y2,y3] + B[word: y3,y2] + B[word: y5]"}︡