Namespaces
Variants
Actions

Shuffle algebra

From Encyclopedia of Mathematics
Jump to: navigation, search


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
How to Cite This Entry:
Shuffle algebra. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Shuffle_algebra&oldid=53031
This article was adapted from an original article by M. Hazewinkel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article