︠f461ac0f-ab72-447a-9653-547df1f1eb1di︠ %html 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') : ︡c92ec455-a193-4463-ab52-34e84ded6383︡{"html": "\r\nThis 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.\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') :"}︡ ︠71c5fb3b-0812-4de8-a8c7-cd07965f145b︠ load(DATA+'FreeAlgebra.sage') ︡bf247676-a9bb-4e12-a28a-9b3adbd87420︡︡ ︠190fdb36-d0c6-4191-ab33-93f4951bf59a︠ is_primitive(PBW(Word('ab'))) ︡cf01546a-0ce6-4541-9e7f-f839fbfab919︡{"stdout": "True"}︡ ︠140df6b1-1a28-46b5-84c8-0075f9cd56ddi︠ %html First, we need to work with words. The word 'foo' is called with the command Word('foo'). For example : ︡ba19303b-9105-4b47-a9d0-9a6892a4b821︡{"html": "First, we need to work with words. The word 'foo' is called with the command Word('foo'). For example :\r\n"}︡ ︠5462905a-9cdc-405b-92c1-15a634e0c777︠ Word('abbb') ︡865c7986-2239-44b6-982b-5460f3673dcc︡{"html": "Word('abbb')"}︡ ︠3e3c78d8-21a2-4cdb-a7c7-5aac0cffd809i︠ %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 : ︡f565ed0c-46ec-44fa-a606-f4a27bdfa938︡{"html": "\r\nA 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"}︡ ︠fe33f669-9e36-4f4a-89c3-e3a072c78b6f︠ Word('abb').is_lyndon() ︡5ec170c9-7526-4dd4-98ca-1ef5053ca114︡{"stdout": "True"}︡ ︠b60f91d4-b9fa-485f-865d-8aa815d6376fi︠ %html 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 : ︡857c38a8-f80b-43e0-9287-2c0f0df2dcae︡{"html": "\r\nThe first basis that I implemented is the Poincar\u00e9-Birkhoff-Witt basis of $Q\\langle a,b \\rangle$. For its definition, see Reutenauer, Free Lie algebras, Clarendon Press, 1993.
\r\nIts 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 :\r\n"}︡ ︠8a726b43-e626-4b63-b03a-ddf9b6ff826b︠ w=Word('abb') ︡f3a18c4a-190e-4e01-8928-8a8b8a262c20︡︡ ︠176d9f58-3bbe-41ec-a143-de4bb10de542︠ w.is_lyndon() ︡b730a714-c959-44b6-a310-70d1819c147b︡{"stdout": "True"}︡ ︠91dcadc4-4faf-4661-9448-03db7e80418e︠ Pol=PBW(w) Pol ︡9ac49ad4-c392-4b7c-8ffc-7450b6639277︡{"stdout": "a*b^2 - 2*b*a*b + b^2*a"}︡ ︠e0ab80c7-dfef-426c-bd2f-ea04ddb49063i︠ %html By the way, the standard bracketing of a word is implemented in Sage and you can call it with LW.standard_bracketing(mot) : ︡260a7233-235e-4990-a3b4-0fa04143c163︡{"html": "\r\nBy the way, the standard bracketing of a word is implemented in Sage and you can call it with LW.standard_bracketing(mot) :\r\n"}︡ ︠6360d269-97aa-4fe8-85f6-976420cac590︠ LW.standard_bracketing(Word('ab')) ︡c7053650-3b70-4c5b-9e38-616841201bf2︡{"stdout": "['a', 'b']"}︡ ︠f6d20318-744f-44c4-89e6-2c86bd5b1099i︠ %html You can "realize" this bracketing as a series using the function expbrack : ︡26124d54-18d1-43c0-9d93-39a24ef50683︡{"html": "\r\nYou can \"realize\" this bracketing as a series using the function expbrack :\r\n"}︡ ︠ab9a3d78-4842-46b1-85ee-1f6f63f6623c︠ expbrack(LW.standard_bracketing(Word('ab'))) ︡fc380555-bbed-4f02-973f-8cb325e2d892︡{"stdout": "a*b - b*a"}︡ ︠d5d8c45e-5531-400e-b59b-916c45074922i︠ %html The usual scalar product (which returns the coefficient of a word in a polynomial) is called ScalProd : ︡904fda70-29dc-4f6b-829f-113883902696︡{"html": "\r\nThe usual scalar product (which returns the coefficient of a word in a polynomial) is called ScalProd :\r\n"}︡ ︠af4d01f3-9535-4fa8-a1ae-4b701e80ee2d︠ c1=ScalProd(Pol,Word('abb')) c2=ScalProd(Pol,Word('abbbbb')) c3=ScalProd(Pol,Word('')) c1,c2,c3 ︡ac32543d-ac5e-48da-ab46-2d8c853bb9bb︡{"stdout": "(1, 0, 0)"}︡ ︠51882d84-84c9-4503-8c85-1dd8fa501794i︠ %html This allows us to implement the counit $\epsilon$ that returns the constant term of a series  : ︡d5184493-c209-400b-903c-bd532a195215︡{"html": "\r\nThis allows us to implement the counit $\\epsilon$ that returns the constant term of a series  :\r\n"}︡ ︠51131cde-c3c7-4fa3-b2b3-8b1af0f0d9fa︠ S=34+a*a*a*b epsilon(S) ︡1ff7128f-cdb9-43f0-a2a1-c5c309cbba69︡{"stdout": "34"}︡ ︠1d051a5e-ed89-4a62-b652-9a81871bad0e︠ epsilon(Pol) ︡2407f914-1d97-4ad6-9860-bc40aa479940︡{"stdout": "0"}︡ ︠1c259690-288d-42a4-8c45-19698c082b0bi︠ %html It is extended through the function SP_Series to $Q \langle \langle a , b \rangle \rangle \otimes Q \langle a , b \rangle$ : ︡c97501e7-dc5e-4b8c-b39f-7f87f9df6a7f︡{"html": "\r\nIt is extended through the function SP_Series to $Q \\langle \\langle a , b \\rangle \\rangle \\otimes Q \\langle a , b \\rangle$ :\r\n"}︡ ︠805305e4-53a9-4e49-83ca-8f40219d58f6︠ S1=3+3*a*b+4*b^2 ︡79f044f4-cd48-4cad-9f0e-924965a736b2︡︡ ︠f2ac62de-1097-41b9-b2af-de7d79436619︠ S2=3*a*b*a*b+4 ︡c3a8ab62-b619-45ea-ac3d-758c1c9ccb97︡︡ ︠df57920b-ba52-447e-b3f6-40234dbbfd25︠ SPSeries(S1,S2) ︡c41d5cb8-af29-48aa-83a0-594bcfeb7d29︡{"stdout": "12"}︡ ︠cc60f237-0e95-4372-96e7-4f6012140c63i︠ %html I implemented two reciprocal morphisms between $\left\{ a , b \right\}^*$ and $k \langle a , b \rangle$ : toA and toWord. ︡50df8fce-37d3-4fec-8305-64f1a9c0e977︡{"html": "\r\nI implemented two reciprocal morphisms between $\\left\\{ a , b \\right\\}^*$ and $k \\langle a , b \\rangle$ : toA and toWord.\r\n"}︡ ︠84039430-928f-40dc-a818-3dc2a8b200c2︠ toA(Word('abbba')) ︡514ad0db-2a45-4a69-8b27-4d3fed2ed5d4︡{"stdout": "a*b^3*a"}︡ ︠39ecaea1-28df-4056-88db-ce16891278b2︠ toWord(_) ︡1448b700-e310-4fae-bd79-9ba98b31eb20︡{"stdout": "word: abbba"}︡ ︠61f03917-3e7c-4117-b4ed-dff99191b36f︠ toWord(toA(Word('abba')))==Word('abba') ︡3a5e3fd8-796c-4330-9c32-71cb04eb32c1︡{"stdout": "True"}︡ ︠32452f29-0a1b-4090-bc02-56ddd53e9f8f︠ toA(toWord(a*b*a*b))==a*b*a*b ︡ab5b49fc-e41c-447a-881e-e910729ac331︡{"stdout": "True"}︡ ︠34f07acf-b60c-44b8-ab89-0410fdaee72fi︠ %html 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' : ︡31f8bdb1-cde5-4ff9-8801-dbb9ea8fcf89︡{"html": "\r\nTo 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' :\r\n"}︡ ︠167061b3-6fb3-4514-bd43-ad75c060faed︠ Module.basis()[Word('ab')] ︡b008f594-369d-4abc-911d-c8de3e66bba2︡{"stdout": "B[word: ab]"}︡ ︠84be2c2a-2f59-4afa-90e1-0a8c634eecfai︠ %html The tensor product of two monomials of this module is computed with TP_free_algebra : ︡01c8705b-d160-4176-819a-b3bcc37cd4a1︡{"html": "\r\nThe tensor product of two monomials of this module is computed with TP_free_algebra :\r\n"}︡ ︠7741bb33-02b8-4049-80cd-1977c25168dd︠ TP_free_algebra(a*b,2*a*b*a) ︡85baedfc-5b30-480f-8349-87d828ba7a0a︡{"stdout": "2*B[a*b] # B[a*b*a]"}︡ ︠54e3d322-6c48-43b7-a0e2-563f475a8730i︠ %html The product of two tensor products is called prod_TP : ︡21fe6ffa-0a35-48a1-a240-969dee30ce32︡{"html": "\r\nThe product of two tensor products is called prod_TP :\r\n"}︡ ︠84723288-c295-4f2f-bbd7-2ff09de81a99︠ t1=TP_free_algebra(a*b,2*a*b*a) t2=TP_free_algebra(a*b,3*b*a) t1,t2 ︡ff1eda7b-bdff-4987-99f8-d0b5b4134162︡{"stdout": "(2*B[a*b] # B[a*b*a], 3*B[a*b] # B[b*a])"}︡ ︠71118445-f6e4-46bc-9243-97a8e5ed157e︠ prod_TP(t1,t2) ︡91337cd2-c10e-4083-b76d-2d4ccc2979e6︡{"stdout": "6*B[a*b*a*b] # B[a*b*a*b*a]"}︡ ︠6cb4443a-f42b-435e-beda-9e36aae8c217i︠ %html In fact, TP_free_algebra is designed for series : ︡3fd798b8-aeab-4832-86ab-b754a3c7dfd1︡{"html": "\r\nIn fact, TP_free_algebra is designed for series :\r\n"}︡ ︠400f8bea-67df-4f87-a4c3-84ef0f7f9202︠ TP_free_algebra(Pol,Pol) ︡3c40c5c4-2ea6-4fe4-93e3-dbe4d8ddfa0a︡{"stdout": "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]"}︡ ︠80136419-b88e-4167-a0ba-81d1882ab3a9i︠ %html The shuffle product of two words is implemented in Sage. I added the shuffle product of two series (ShuffSeries) : ︡55d6444e-7011-4831-8b1a-83a6de04abf7︡{"html": "\r\nThe shuffle product of two words is implemented in Sage. I added the shuffle product of two series (ShuffSeries) :\r\n"}︡ ︠e15b1339-e199-49af-af67-5d35dc557a72︠ ShuffSeries(Pol,Pol) ︡66ce6441-6213-4c52-a716-65e6fdb89420︡{"stdout": "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"}︡ ︠d7dab383-dd85-4279-98b6-3606991dcbcei︠ %html 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) : ︡2d8fc3b2-acf3-4d93-8e16-2239361ed1bc︡{"html": "\r\nIn 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) :\r\n"}︡ ︠5b4a913e-0210-49ba-bd56-f7e5c238ab72︠ Delta(Word('ab')) ︡4dd58342-b90b-4b2e-9d2b-46b0a473d1a5︡{"stdout": "B[1] # B[a*b] + B[a] # B[b] + B[b] # B[a] + B[a*b] # B[1]"}︡ ︠5339e5d0-3bd5-4b93-9cf2-8cace27f524f︠ Delta(Pol) ︡8c2c8bd5-cf93-4791-b352-c9d05c5ede55︡{"stdout": "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]"}︡ ︠8a1d20e8-3e30-4e86-8b06-1ec35eb45282i︠ %html 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. ︡4ec4f56e-f1dd-4edb-8e07-fadf836c50ad︡{"html": "\r\nThe 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\u00e9-Birkhoff-Witt basis for Lyndon words are primitive elements.\r\n"}︡ ︠8ac63299-b4e6-488c-8f6a-d62f52cdd340︠ is_primitive(Pol) ︡460790c8-b8b6-41bd-b15f-22c47d35a429︡{"stdout": "True"}︡ ︠5554549b-55b7-47ad-aa1e-cec56389b12c︠ d1=is_primitive(PBW(Word('aba'))) d2=Word('aba').is_lyndon() print(d1,d2) ︡f67f954b-ce08-4b14-a5b1-af3f724e981e︡{"stdout": "(False, False)"}︡ ︠c146917c-31f0-41f7-93fe-5133137e3e72i︠ %html 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 : ︡52a57b41-8251-481a-9031-10d81e018434︡{"html": "\r\nTwo 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 :\r\n"}︡ ︠b4914c5f-2e17-42a5-b4fd-260671abe1f9︠ Sbasis(Word('aabab')) ︡c60ab105-4f76-48a5-a94d-19343597719a︡{"stdout": "2*a^3*b^2 + a^2*b*a*b"}︡ ︠894bf48b-59bd-4451-905a-74c523f5fdd8︠ Sbasistilde(Word('aabab')) ︡34b8c71c-450c-4bfb-9674-a5683752b0b4︡{"stdout": "a^2*b*a*b"}︡ ︠0f617d0c-8d97-45a6-85f7-937da6318a51i︠ %html You can check that the PBW basis and the S basis are dual to one another : ︡2343049d-eb76-4937-aa84-d2f937a43df9︡{"html": "\r\nYou can check that the PBW basis and the S basis are dual to one another :\r\n"}︡ ︠c0fdc35a-3b51-4c67-ac23-67ddd0d1fbdb︠ for mot in Words('ab',3): print(mot==Word('abb'),SPSeries(Pol,Sbasis(mot))) ︡ab37ef7d-1a2a-4937-8a80-6968bf321d4f︡{"stdout": "(False, 0)\n(False, 0)\n(False, 0)\n(True, 1)\n(False, 0)\n(False, 0)\n(False, 0)\n(False, 0)"}︡ ︠8448eb77-c6df-4f8d-9aff-0c0f14038096i︠ %html 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) : ︡5cb8e954-02d0-4613-815f-083ec976f25c︡{"html": "\r\nIt 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) :\r\n"}︡ ︠f1957a18-b43d-4ee3-896e-24a71e028009︠ devP(a*b*a*b,[]) ︡06d293e3-aa28-44b5-bd9e-c0425da4ed7d︡{"stdout": "[(word: abab, 1), (word: baba, -1), (word: baab, 3), (word: abba, 3), (word: abab, -3), (word: aabb, -2)]"}︡ ︠2b1c3911-9864-400d-b1f3-d0a3fad5a930︠ devP(Pol,[]) ︡21543b62-0b49-4c81-b35c-3ecdd5551b00︡{"stdout": "[(word: abb, 1)]"}︡ ︠8431c5dd-1ea6-470c-b585-2d601a2a6ad5︠ devS(Pol,[]) ︡edaa4cb2-b70e-4a3d-81c0-f279dd14bbf0︡{"stdout": "[(word: bba, 1), (word: bab, -3), (word: abb, 6)]"}︡ ︠3420237f-a43d-405a-a2f3-b879ad7bb56ei︠ %html The antipode is called antipode. It is defined for word and for series : ︡e50ff506-0f41-4b6d-93af-1e7ae2c23c93︡{"html": "\r\nThe antipode is called antipode. It is defined for word and for series :\r\n"}︡ ︠3a9cb9f3-f6fb-4476-8411-28983f888119︠ antipode(2*b*a+3*b*a*a) ︡c87a418c-c1e8-408c-b95d-bf03f0242bea︡{"stdout": "2*a*b - 3*a^2*b"}︡ ︠b2e58cda-5edb-4a10-a377-d479061cfc1bi︠ %html The .sage file contains some more functions that are used in the background. I let you discover them by yourself. ︡d309870a-c679-40ca-8bfd-5f4ac2384ab0︡{"html": "\r\nThe .sage file contains some more functions that are used in the background. I let you discover them by yourself.\r\n"}︡