View source for Shuffle algebra

{{TEX|done}}

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 word]]s on $X$. I.e.,
$$
\mathrm{Sh}(X) \otimes_{\mathbb{Z}} \mathbb{Q} = \mathbb{Q}[w \in X^* : w\ \text{a Lyndon word}]
$$
[[#References|[a1]]]. It is not true that $\mathrm{Sh}(X)$ is free over $\mathbb{Z}$.

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  C. Reutenauer,   "Free Lie algebras" , Oxford Univ. Press  (1993)</TD></TR></table>