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 interlacing is given by the riffle shuffle permutation.
The shuffle product occurs in generic settings in non-commutative algebras; this is because it is able to preserve the relative order of factors being multiplied together - the riffle shuffle permutation. This can be held in contrast to the divided power structure, which becomes appropriate when factors are commutative.
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
It may be defined inductively by
- u ⧢ ε = ε ⧢ u = u
- ua ⧢ vb = (u ⧢ vb)a + (ua ⧢ v)b
where ε is the empty word, a and b are single elements, and u and v are arbitrary words.
The shuffle product was introduced by Eilenberg & Mac Lane (1953). 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: this is the riffle shuffle permutation. The product is commutative and associative.
The closely related infiltration product was introduced by Chen, Fox & Lyndon (1958). It is defined inductively on words over an alphabet A by
- fa ↑ ga = (f ↑ ga)a + (fa ↑ g)a + (f ↑ g)a
- fa ↑ gb = (f ↑ gb)a + (fa ↑ g)b
- ab ↑ ab = ab + 2aab + 2abb + 4 aabb + 2abab
- ab ↑ ba = aba + bab + abab + 2abba + 2baab + baba
The infiltration product is also commutative and associative.
- Chen, Kuo-Tsai; Fox, Ralph H.; Lyndon, Roger C. (1958), "Free differential calculus. IV. The quotient groups of the lower central series", Annals of Mathematics, Second Series, 68 (1): 81–95, doi:10.2307/1970044, JSTOR 1970044, MR 0102539, Zbl 0142.22304
- Eilenberg, Samuel; Mac Lane, Saunders (1953), "On the groups of H(Π,n). I", Annals of Mathematics, Second Series, 58 (1): 55–106, doi:10.2307/1969820, ISSN 0003-486X, JSTOR 1969820, MR 0056295, Zbl 0050.39304
- Green, J. A. (1995), Shuffle algebras, Lie algebras and quantum groups, Textos de Matemática. Série B, vol. 9, Coimbra: Universidade de Coimbra Departamento de Matemática, MR 1399082
- Hazewinkel, M. (2001) , "Shuffle algebra", Encyclopedia of Mathematics, EMS Press
- Hazewinkel, Michiel; Gubareni, Nadiya; Kirichenko, V. V. (2010), Algebras, rings and modules. Lie algebras and Hopf algebras, Mathematical Surveys and Monographs, vol. 168, American Mathematical Society, doi:10.1090/surv/168, ISBN 978-0-8218-5262-0, MR 2724822, Zbl 1211.16023
- Lothaire, M. (1997), Combinatorics on words, Encyclopedia of Mathematics and Its Applications, vol. 17, Perrin, D.; Reutenauer, C.; Berstel, J.; Pin, J. E.; Pirillo, G.; Foata, D.; Sakarovitch, J.; Simon, I.; Schützenberger, M. P.; Choffrut, C.; Cori, R.; Lyndon, Roger; Rota, Gian-Carlo. Foreword by Roger Lyndon (2nd ed.), Cambridge University Press, ISBN 0-521-59924-5, Zbl 0874.20040
- Reutenauer, Christophe (1993), Free Lie algebras, London Mathematical Society Monographs. New Series, vol. 7, Oxford University Press, ISBN 978-0-19-853679-6, MR 1231799, Zbl 0798.17001