Shuffle algebra
Let 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}.
Comments
The shuffle product is commutative and associative. It may be defined inductively for a,b \in X by ua \cdot vb = (u \cdot vb)a + (ua \cdot v)b \ .
This is also related to the notion of zinbiel algebra.
References
[a1] | C. Reutenauer, "Free Lie algebras" , Oxford Univ. Press (1993) Zbl 0798.17001 |
[b1] | M. Lothaire, Combinatorics on Words, Cambridge University Press (1997) ISBN 0-521-59924-5 Zbl 0874.20040 |
Shuffle algebra. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Shuffle_algebra&oldid=53031