Shuffle algebra

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)

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 \ . $$

References

[b1]	M. Lothaire, Combinatorics on Words, Cambridge University Press (1997) ISBN 0-521-59924-5