Let ${cal Z$ denote the free associative algebra ${ol Z langle Z_1 , Z_2 , ldots rangle$ over the integers. This algebra carries a Hopf algebra structure for which the comultiplication is $Z_n mapsto Sigma_{i+j=n Z_i otimes Z_j$. This the noncommutative Leibniz-Hopf algebra. It carries a natural grading for which $gr(Z_n )=n$. The Ditters-Scholtens theorem says that the graded dual, ${cal M$, of ${cal Z$, herein called the overlapping shuffle algebra (on the semigroup of natural numbers), is the free commutative polynomial algebra over ${ol Z$ with as polynomial generators certain words which are called elementary unreachable words (EUW). In this note unreachable words are shown to be precisely the (concatenation) powers of Lyndon words. More precisely it is shown that the block decomposition algorithm of [4] is in fact an algorithm for obtaining the Chen-Fox-Lyndon factorization of a word into decreasing Lyndon words. Further links are discussed between the shuffle algebra and the overlapping shuffle algebra.

, ,
CWI
Department of Analysis, Algebra and Geometry [AM]

Hazewinkel, M. (1996). The Leibniz-Hopf algebra and Lyndon words. Department of Analysis, Algebra and Geometry [AM]. CWI.