Shuffle algebra
Encyclopedia
In mathematics, a shuffle algebra is a Hopf algebra
with a basis corresponding to words on some set, whose product is given by the shuffle product XшY of two words X, Y: the sum of all ways of interlacing them. The shuffle product was introduced by . The name "shuffle product" refers to the fact that the product can be thought of as a sum over all ways of riffle shuffling two words together.
The shuffle algebra on a finite set is the graded dual of the universal enveloping algebra
of the free Lie algebra
on the set.
Over the rational numbers, the shuffle algebra is isomorphic to the polynomial algebra in the Lyndon word
s.
The shuffle product of two words in some alphabet is often denoted by the shuffle product symbol ш (a cyrillic sha
, or the unicode
character SHUFFLE PRODUCT (U+29E2)).
Hopf algebra
In mathematics, a Hopf algebra, named after Heinz Hopf, is a structure that is simultaneously an algebra and a coalgebra, with these structures' compatibility making it a bialgebra, and that moreover is equipped with an antiautomorphism satisfying a certain property.Hopf algebras occur naturally...
with a basis corresponding to words on some set, whose product is given by the shuffle product XшY of two words X, Y: the sum of all ways of interlacing them. The shuffle product was introduced by . The name "shuffle product" refers to the fact that the product can be thought of as a sum over all ways of riffle shuffling two words together.
The shuffle algebra on a finite set is the graded dual of the universal enveloping algebra
Universal enveloping algebra
In mathematics, for any Lie algebra L one can construct its universal enveloping algebra U. This construction passes from the non-associative structure L to a unital associative algebra which captures the important properties of L.Any associative algebra A over the field K becomes a Lie algebra...
of the free Lie algebra
Free Lie algebra
In mathematics, a free Lie algebra, over a given field K, is a Lie algebra generated by a set X, without any imposed relations.-Definition:Given a set X, one can show that there exists a unique free Lie algebra L generated by X....
on the set.
Over the rational numbers, the shuffle algebra is isomorphic to the polynomial algebra in the Lyndon word
Lyndon word
In mathematics, in the areas of combinatorics and computer science, a Lyndon word is a string that is strictly smaller in lexicographic order than all of its rotations...
s.
The shuffle product of two words in some alphabet is often denoted by the shuffle product symbol ш (a cyrillic sha
Sha
For other uses, see Sha .Sha is a letter of the Cyrillic alphabet. It commonly represents the voiceless postalveolar fricative , like the pronunciation of ⟨sh⟩ in "sheep", or the somewhat similar voiceless retroflex fricative . It is used in every variation of the Cyrillic alphabet, for Slavic and...
, or the unicode
Unicode
Unicode is a computing industry standard for the consistent encoding, representation and handling of text expressed in most of the world's writing systems...
character SHUFFLE PRODUCT (U+29E2)).
Definition
The shuffle product of words of lengths m and n is a sum over the (m+n)!/m!n! ways of interleaving the two words, as shown in the following examples:- ab ш xy = abxy + axby + xaby + axyb + xayb + xyab
- aaa ш aa = 10aaaaa