Namespaces
Variants
Actions

Difference between revisions of "Shuffle algebra"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(LaTeX)
Line 1: Line 1:
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110110/s1101101.png" /> be a set (alphabet) and consider the [[Free associative algebra|free associative algebra]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110110/s1101102.png" /> on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110110/s1101103.png" /> over the integers, provided with the [[Hopf algebra|Hopf algebra]] structure given by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110110/s1101104.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110110/s1101105.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110110/s1101106.png" />. As an Abelian group, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110110/s1101107.png" /> is free and graded. Its graded dual is again a Hopf algebra, sometimes called the shuffle-cut Hopf algebra or merge-cut Hopf algebra. Its underlying algebra is the shuffle algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110110/s1101108.png" />. As an Abelian group, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110110/s1101109.png" /> has as basis the elements of the free monoid (see [[Free semi-group|Free semi-group]]) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110110/s11011010.png" /> of all words in the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110110/s11011011.png" />. The product of two such words <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110110/s11011012.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110110/s11011013.png" /> is the sum of all words of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110110/s11011014.png" /> that are permutations of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110110/s11011015.png" /> such that both <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110110/s11011016.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110110/s11011017.png" /> appear in their original order. E.g.,
+
{{TEX|done}}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110110/s11011018.png" /></td> </tr></table>
+
Let $X = \{X_i : i \in I \}$ be a set (alphabet) and consider the [[free associative algebra]] $\mathbb{Z}[X]$ on $X$ over the integers, provided with the [[Hopf algebra]] structure given by $\mu(X_i) = X_i \otimes 1 + 1 \otimes X_i$, $\epsilon(X_i) = 0$, $\iota(X_i) = -X_i$. As an Abelian group, $\mathbb{Z}[X]$ is free and graded. Its graded dual is again a Hopf algebra, sometimes called the shuffle-cut Hopf algebra or merge-cut Hopf algebra. Its underlying algebra is the shuffle algebra $\mathrm{Sh}(X)$. As an Abelian group, $\mathrm{Sh}(X)$ has as basis the elements of the [[free monoid]] $X^*$ of all words over the alphabet $X$. The product of two such words $u = a_1\cdots a_s$, $v = b_1\cdots b_t$ is the sum of all words of length $s+t$ that are permutations of $a_1,\ldots, a_s, b_1, \ldots, b_t$  such that both $a_1,\ldots, a_s$ and $b_1, \ldots, b_t$ appear in their original order. E.g.,
 +
$$
 +
aa \cdot b = aab + aba + baa
 +
$$
 +
$$
 +
aa \cdot a = 3aaa
 +
$$
 +
$$
 +
a_1a_2 \cdot b_1b_2 = a_1a_2 b_1b_2 + a_1b_1a_2b_2 + a_1b_1b_2a_2 + b_1a_1a_2b_2 + b_1a_1b_2a_2 + b_1b_2a_1a_2
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110110/s11011019.png" /></td> </tr></table>
+
This is the shuffle product. It derives its name from the familiar riffle shuffle of decks of playing cards.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110110/s11011020.png" /></td> </tr></table>
+
As an algebra over $\mathbb{Q}$, $\mathrm{Sh}(X)$ is a free commutative algebra with as free commutative generators the [[Lyndon word]]s on $X$. I.e.,
 
+
$$
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110110/s11011021.png" /></td> </tr></table>
+
\mathrm{Sh}(X) \otimes_{\mathbb{Z}} \mathbb{Q} = \mathbb{Q}[w \in X^* : w\ \text{a Lyndon word}]
 
+
$$
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110110/s11011022.png" /></td> </tr></table>
+
[[#References|[a1]]]. It is not true that $\mathrm{Sh}(X)$ is free over $\mathbb{Z}$.
 
 
This is the shuffle product. It derives its name from the familiar rifle shuffle of decks of playing cards.
 
 
 
As an algebra over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110110/s11011023.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110110/s11011024.png" /> is a free commutative algebra with as free commutative generators the Lyndon words in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110110/s11011025.png" />, see [[Lyndon word|Lyndon word]]. I.e.,
 
 
 
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110110/s11011026.png" /></td> </tr></table>
 
 
 
[[#References|[a1]]]. It is not true that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110110/s11011027.png" /> is free over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110110/s11011028.png" />.
 
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  C. Reutenauer,  "Free Lie algebras" , Oxford Univ. Press  (1993)</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  C. Reutenauer,  "Free Lie algebras" , Oxford Univ. Press  (1993)</TD></TR></table>

Revision as of 18:35, 15 December 2014


Let $X = \{X_i : i \in I \}$ be a set (alphabet) and consider the free associative algebra $\mathbb{Z}[X]$ on $X$ over the integers, provided with the Hopf algebra structure given by $\mu(X_i) = X_i \otimes 1 + 1 \otimes X_i$, $\epsilon(X_i) = 0$, $\iota(X_i) = -X_i$. As an Abelian group, $\mathbb{Z}[X]$ is free and graded. Its graded dual is again a Hopf algebra, sometimes called the shuffle-cut Hopf algebra or merge-cut Hopf algebra. Its underlying algebra is the shuffle algebra $\mathrm{Sh}(X)$. As an Abelian group, $\mathrm{Sh}(X)$ has as basis the elements of the free monoid $X^*$ of all words over the alphabet $X$. The product of two such words $u = a_1\cdots a_s$, $v = b_1\cdots b_t$ is the sum of all words of length $s+t$ that are permutations of $a_1,\ldots, a_s, b_1, \ldots, b_t$ such that both $a_1,\ldots, a_s$ and $b_1, \ldots, b_t$ appear in their original order. E.g., $$ aa \cdot b = aab + aba + baa $$ $$ aa \cdot a = 3aaa $$ $$ a_1a_2 \cdot b_1b_2 = a_1a_2 b_1b_2 + a_1b_1a_2b_2 + a_1b_1b_2a_2 + b_1a_1a_2b_2 + b_1a_1b_2a_2 + b_1b_2a_1a_2 $$

This is the shuffle product. It derives its name from the familiar riffle shuffle of decks of playing cards.

As an algebra over $\mathbb{Q}$, $\mathrm{Sh}(X)$ is a free commutative algebra with as free commutative generators the Lyndon words on $X$. I.e., $$ \mathrm{Sh}(X) \otimes_{\mathbb{Z}} \mathbb{Q} = \mathbb{Q}[w \in X^* : w\ \text{a Lyndon word}] $$ [a1]. It is not true that $\mathrm{Sh}(X)$ is free over $\mathbb{Z}$.

References

[a1] C. Reutenauer, "Free Lie algebras" , Oxford Univ. Press (1993)
How to Cite This Entry:
Shuffle algebra. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Shuffle_algebra&oldid=35670
This article was adapted from an original article by M. Hazewinkel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article