Algèbre de mélange

En mathématiques, et notamment en combinatoire algébrique, une algèbre de mélange est une algèbre de Hopf dont la base est formée de mots sur un certain alphabet avec, comme produit, le produit de mélange $x$ ш $y$ de deux mots $x$ et $y$ : ce produit consiste en l'entrelacement, de toutes les manières possibles, les séquences de lettres composant les mots.

L'algèbre de mélange sur un ensemble fini est l'algèbre graduée duale de l'algèbre enveloppante universelle de l'algèbre de Lie libre sur cet ensemble.

L'algèbre de mélange sur les nombres rationnels est isomorphe à l'algèbre polynomiale des mots de Lyndon.

Produit de mélange

Le produit de mélange $x$ ш $y$ de deux mots $x$ de longueur N et $y$ de longueur M est la somme des ${\frac {(N+M)!}{N!M!}}$ mots $x_{1}y_{1}x_{2}y_{2}\cdots x_{n}y_{n}$, où les $x_{i}$ et les $y_{i}$ sont des mots, tels que $x=x_{1}x_{2}\dots x_{n}$ et $y=y_{1}y_{2}\dots y_{n}$. Par exemple,

$aab$ ш $ab=6aaabb+3aabab+abaab$.

On peut aussi le définir par récurrence par :

$ua$ ш $vb$=$(u$ ш $vb)a+(ua$ ш $v)b$.

Le produit de mélange est associatif et commutatif.

Produit d'infiltration

Le produit d'infiltration est une opération semblable, introduite par Chen, Fox et Lyndon 1958. Il est défini par récurrence sur la longueur des mots, pour deux mots $f$ et $g$ et deux lettres $a\neq b$ (le mot vide est noté $\varepsilon$) comme suit :

$f\uparrow \varepsilon =\varepsilon \uparrow f=f$ ;

$fa\uparrow ga=(f\uparrow ga)a+(fa\uparrow g)a+(f\uparrow g)a$ ;

$fa\uparrow gb=(f\uparrow gb)a+(fa\uparrow g)b$.

Par exemple,

$a\uparrow a=(\varepsilon \uparrow a)a+(a\uparrow \varepsilon )a+(\varepsilon \uparrow \varepsilon )a=2aa+a$.

$a\uparrow b=(\varepsilon \uparrow b)a+(a\uparrow \varepsilon )b=ba+ab$.

De même,

$ab\uparrow ab=ab+2aab+2abb+4aabb+2abab$ ;

$ab\uparrow ba=aba+bab+abab+2abba+2baab+baba$ .

Le produit d'infiltration est également associatif et commutatif.

Notes et références

Références

• Kuo-Tsai Chen, Ralph H. Fox et Roger C. Lyndon, « Free differential calculus. IV. The quotient groups of the lower central series », Annals of Mathematics. Second Series, vol. 68, n^o 1,‎ 1958, p. 81–95 (ISSN 0003-486X, DOI 10.2307/1970044, JSTOR 1970044, MR 0102539, zbMATH 0142.22304)
• Samuel Eilenberg et Saunders Mac Lane, « On the groups of $H(\Pi ,n)$. I », Annals of Mathematics. Second Series, vol. 58,‎ 1953, p. 55–106 (ISSN 0003-486X, JSTOR 1969820, MR 0056295)
• (en) M. Lothaire, Combinatorics on words, Cambridge University Press, coll. « Encyclopedia of Mathematics and Its Applications » (n^o 17), 1997, 2^e éd., 238 p. (ISBN 978-0-521-59924-5, zbMATH 0874.20040)
• (en) Christophe Reutenauer, Free Lie algebras, The Clarendon Press Oxford University Press, coll. « London Mathematical Society Monographs. New Series » (n^o 7), 1993, 269 p. (ISBN 978-0-19-853679-6, MR 1231799, présentation en ligne)

Notes

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Shuffle algebra » (voir la liste des auteurs).

Liens externes

• (en) « Shuffle algebra », dans Michiel Hazewinkel, Encyclopædia of Mathematics, Springer, 2002 (ISBN 978-1556080104, lire en ligne)
• Le symbole ш en LateX