Espèces et fonctions symétriques

Par "espèce", on entend "espèce à valeurs dans la catégorie des ensembles".

Par "espèce vectorielle", on entend "espèce à valeurs dans la catégorie des espaces vectoriels sur $\mathbb{Q}$".

On peut aussi avoir besoin des espèces à valeurs dans la catégorie des complexes de $\mathbb{Q}$-espaces vectoriels, mais pas aujourd'hui.

Objectif : expliquer un outil similaire à la série génératrice, mais plus subtil et plus riche.

Construction classique : la série génératrice

Soit $P$ une espèce. Alors la série génératrice de $P$ est

$$f_P = \sum_{n \geq 0} |P(n)| \frac{z^n}{n!},$$

et pour une espèce vectorielle

$$f_P = \sum_{n \geq 0} \dim P(n) \frac{z^n}{n!}.$$

Ces séries formelles en une variable $z$ sont utiles et contiennent de l'information.

L'application $P \mapsto f_P$ respecte la somme $+$, le produit $\times$, la structure monoïdale $\circ$ et aussi la dérivation $\partial$.

Donc si on dispose d'une équation pour l'espèce $P$ utilisant ces opérations, on en déduit une équation pour $f_P$. Idem pour des systèmes d'équations.

Exemple : toutes sortes d'arbres enracinés 🌳.

Si $P$ est une opérade donnée par générateurs et relations, calculer $f_P$ avec une grande précision est difficile a priori. On peut utiliser la technologie des bases de Gröbner opéradiques de Dotsenko-Khoroshkin.

Raffinement très fin, trop fin

Mais $P(n)$ n'est pas juste un ensemble, mais un ensemble muni d'une action de $S_n$.

On peut essayer de remplacer le cardinal $|P(n)|$ par la classe d'isomorphisme du $S_n$-ensemble fini $P(n)$.

Difficulté : on n'a pas une description simple de cet ensemble de classes d'isomorphismes.

On en fait un groupe abélien en ajoutant des inverses formels (groupe de Grothendieck).

C'est l'anneau de Burnside $B(S_n)$. La somme est induite par l'union disjointe et le produit par le produit cartésien.

Nommé d'après William Burnside (1852-1927), mathématicien et athlète anglais.

On voudrait de plus regarder la somme directe de ces groupes abéliens $\bigoplus_{n\geq 0} B(S_n)$.

Ça reste trop compliqué pour fournir un cadre dans lequel on peut faire des calculs. C'est la même chose que la théorie des espèces virtuelles (différences formelles de deux espèces).

Ce point de vue centré sur les actions des groupes symétriques est cependant utile : décompositions moléculaires et atomiques des espèces.

La décomposition moléculaire correspond à l'unique décomposition d'une action comme union disjointe d'actions transitives. Une espèce atomique est une espèce moléculaire qui est indécomposable pour le produit cartésien.

Raffinement moins fin

Du coup, on va regarder non pas des actions ensemblistes de $S_n$ mais des représentations de $S_n$ à coefficients dans $\mathbb{Q}$. On perd un peu d'information, mais pas trop.

On associe donc à une espèce $P$ la suite des représentations $\mathbb{Q} P(n)$ pour $n \geq 0$.

C-à-d. on linéarise les actions en des actions matricielles.

On introduit l'anneau des représentations $R(S_n)$ comme le groupe de Grothendieck de la catégorie monoïdale des représentations de dimension finie de $S_n$ sur $\mathbb{Q}$. La somme est induite par la somme directe et le produit par le produit tensoriel.

Alors, on sait que cet anneau $R(S_n)$ est un groupe abélien libre de rang le nombre de partitions de l'entier $n$. Il a pour base les classes des modules simples sur $R(S_n)$. Si $\lambda $ est une partition de $n$, on note $\mathsf{S}_\lambda$ le module simple associé et $s_\lambda$ son image dans l'anneau $R(S_n)$.

On associe donc à une espèce $P$ la somme des classes

$$W_P = \sum_{n \geq 0} [\mathbb{Q} P(n)] \in \prod_{n \geq 0} R(S_n)$$

qui vit dans le complété de la somme directe des anneaux de représentations. Cette application envoie la somme des espèces sur la somme.

Induction et restriction : une algèbre de Hopf

Notons ${R}$ la somme directe $\bigoplus_{n \geq 0} R(S_n)$.

Alors les inclusions paraboliques de groupes symétriques $S_m \times S_n \longrightarrow S_{m+n}$ induisent des foncteurs de restriction et d'induction entre catégories de représentations.

En passant aux groupes de Grothendieck, on obtient sur $R$ un produit associatif commutatif $\star$ et un coproduit $\Delta$ co-associatif et co-commutatif. Ces deux structures respectent la graduation et font de $R$ une algèbre de Hopf graduée connexe.

On peut aussi définir sur $R$ un produit scalaire qui fait des $s_\lambda$ une base orthogonale.

L'application $P \mapsto W_P$ envoie le produit des espèces sur le produit $\star$ dans $R$.

Il existe sur $R$ une structure supplémentaire de $\lambda$-anneau, qui donne une opération de pléthysme $\circ$. On en verra une description plus loin.

L'application $P \mapsto W_P$ envoie alors la structure monoidale $\circ$ des espèces sur le pléthysme $\circ$.

Donc on a bien un cadre qui associe à chaque espèce $P$ un élément $W_P$ du complété de $R$ et respecte les opérations.

Anneau des fonctions symétriques

On veut remplacer le somme formelle $W_P$ par un objet plus concret et mieux adapté aux calculs.

On va utiliser l'isomorphisme classique de Frobenius entre $R$ et l'anneau des polynômes $\mathbb{Q}[p_1,p_2,p_3,p_4,\ldots]$ en une infinité de variables.

Soit donc $\operatorname{Sym}$ l'anneau des polynômes en les variables $p_i$ pour $i \geq 1$. On définit une graduation sur $\operatorname{Sym}$ en posant $\deg p_i = i$.

On définit un coproduit $\Delta$ sur $\operatorname{Sym}$ en posant $\Delta p_i = p_i \otimes 1 + 1 \otimes p_i$ pour tout $i$, puis en étendant comme un morphisme d'algèbre.

Soient $f$ et $g$ dans $\operatorname{Sym}$. On suppose que $g$ n'a pas de terme de degré $0$. Alors le pléthysme $f \circ g$ est défini par les conditions suivantes.

• $f \circ g$ est linéaire en $f$,
• $f \circ g$ est multiplicatif en $f$,
• $p_i \circ g = g(p_i,p_{2i},p_{3i},\ldots)$, ce qui consiste à remplacer $p_k$ par $p_{ki}$ dans $g$.

On obtient sur $\operatorname{Sym}$ une structure d'algèbre de Hopf graduée connexe. Le pléthysme $\circ$ donne une structure de $\lambda$-anneau.

Application caractère de Frobenius

Si $M$ est une représentation du groupe $S_n$ de caractère $\chi_M$, on peut lui associer son caractère de Frobenius

$$M \mapsto \sum_{\lambda \vdash n} \chi_M(C_\lambda) \frac{p_\lambda}{z_\lambda},$$

où

• la somme porte sur les partitions de $n$,
• $z_\lambda$ est un certain entier,
• $C_\lambda$ est une classe de conjugaison dans $S_n$
• et $p_\lambda$ est le produit de $p_i$ pour $i$ décrivant les parts de $\lambda$.

L'image de $M$ est un élément de $\operatorname{Sym}$ homogène de degré $n$. Cette application ne dépend que de la classe $[M]$ dans $R(S_n)$ et définit un isomorphisme d'espace vectoriel entre $R(S_n)$ et la composante homogène $\operatorname{Sym}_n$.

En faisant la somme directe de toutes ces applications, on obtient un isomorphisme d'espace vectoriel gradué entre $R$ et $\operatorname{Sym}$.

Théorème : cet isomorphisme $R \simeq \operatorname{Sym}$ respecte la somme, le produit, le coproduit et le pléthysme.

Fonction symétrique associée à une espèce

Résumons : à une espèce $P$, on associe la somme infinie $W_P = \sum_{n \geq 0} [\mathbb{Q}P(n)]$ dans le complété de l'anneau des représentations $R$.

On peut ensuite composer avec l'application caractère de Frobenius.

Le résultat est la série $Z_P$ qui est un élément du complété de $\operatorname{Sym}$.

J'appelle ceci la fonction symétrique associée à $P$. C'est la "cycle index series" de $P$.

Ca marche aussi bien que la série génératrice : somme $+$, produit $\times$ et $\circ$ pour les espèces sont envoyées sur les opérations dans $\operatorname{Sym}$.

De même la dérivation des espèces est envoyée sur $\partial_{p_1}$.

Exemples:

L'espèce $X$ a pour image $p_1$.

L'espèce $L_n$ des ordres totaux à $n$ éléments a pour image $p_1^n$.

L'espèce $E_2$ des ensembles à 2 éléments est envoyée sur $\frac{1}{2} p_1^2 + \frac{1}{2} p_2$.

L'espèce $E_n$ des ensembles à n éléments est envoyée sur $\sum_{\lambda \vdash n} \frac{1}{z_\lambda} p_\lambda$.

Donc on peut calculer l'image de $E_2 \circ E_n$ ou de $E_2 \circ L_3$ directement dans $\operatorname{Sym}$.

Beaucoup d'informations

Pour une espèce $P$, la fonction symétrique $Z_P$ contient beaucoup plus d'information que la série génératrice $f_P$.

On retrouve la série génératrice par la formule $Z_P(z,0,0,0,\ldots)$ c.-à.-d. en remplacant $p_1$ par $z$ et les $p_i$ pour $i \geq 2$ par zero.

On peut aussi déduire de $Z_P$ le nombre de classes d'isomorphismes de $P$-structures de taille $n$, en utilisant le produit scalaire naturel sur $\operatorname{Sym}$.

Lorsque $P$ est une opérade, la connaissance de $Z_P$ détermine les dimensions de toutes les $P$-algèbres libres.

La suite des coefficients de $p_n$ dans $Z_P$ définit un morphisme vers l'anneau des séries de Dirichlet.

Formules explicites

Pour certaines espèces $P$ plus ou moins classiques, on peut trouver une expression explicite complète de $Z_P$.

Pour les listes $L$ : $1/(1-p_1)$

Pour les ensembles $E$ : $\exp(\sum_{i \geq 1} p_i/i)$

🌳 Pour les arbres enracinés $T$ définis par $T = X \times E(T)$ : on peut calculer le coefficient de $p_\lambda$ pour toute partition $\lambda$, par une formule due à Labelle dans le Lecture Notes 1234.

Par exemple, $T(6)$ donne $$\frac{54}{5} p_{1,1,1,1,1,1} + \frac{16}{3} p_{2,1,1,1,1} + \frac{3}{2} p_{2,2,1,1} + \frac{3}{2} p_{3,1,1,1} + \frac{1}{6} p_{3,2,1} + \frac{1}{2} p_{4,1,1} + \frac{1}{5} p_{5,1}$$

Autre base : fonctions de Schur

Les fonctions de Schur $s_\lambda$ sont les images des représentations irréductibles $\mathsf{S}_\lambda$ du groupe $S_n$ par l'application caractère de Frobenius.

Elles forment une base de $\operatorname{Sym}$.

Donc on peut aussi décrire $Z_P$ dans cette base des fonctions de Schur.

Pour : On obtient des informations pertinentes sur la décomposition de $\mathbb{Q} P(n)$ en représentations irréductibles.

Contre : Le produit et le pléthysme deviennent nettement moins évidents.

Example :

Pour l'espèce $\operatorname{Perm}$ telle que $\operatorname{Perm}(I)= I$ pour tout ensemble fini, la représentation $\operatorname{Perm}(n)$ est de dimension $n$ et somme directe des deux représentations irréductibles $s_{n}$ et $s_{n-1,1}$.

Comme $\operatorname{Perm} = X \times E$, on a $f_{\operatorname{Perm}} = z \operatorname{exp}(z)$

et $Z_{\operatorname{Perm}} = p_1 \times Z_E$.

🌳 Pour l'espèce $T$ des arbres enracinés, on ne connait pas de description des coefficients de $Z_T$ dans la base des fonctions de Schur.

Outils de calcul

Dans SageMath, on a des outils puissants pour calculer dans ce cadre.

• une implémentation des fonctions symétriques, dans une version paresseuse,

• une implémentation des espèces de structure.

Le tout est de grande qualité, et en cours d'amélioration par le travail remarquable de Martin Rubey (Merci !)

Beaucoup de ces outils ne sont disponibles que dans cette implémentation.

Calculs avec fonctions symétriques

sage: p = SymmetricFunctions(QQ).p()
sage: s = SymmetricFunctions(QQ).s()

sage: Lp = LazySymmetricFunctions(p)

sage: X = p[1]
sage: E = Lp(lambda n:s[n], valuation=0)

sage: T = Lp(None, valuation=1)
sage: T.define(X*E(T))

sage: unicode_art(T[:5])

⎡ p  , p  , 3/2*p   + 1/2*p   , 8/3*p   + p    + 1/3*p     ⎤
⎢  ┌┐   ┌┐       ┌┐        ┌┬┐       ┌┐    ┌┬┐        ┌┬┬┐ ⎥
⎢  └┘   ├┤       ├┤        ├┼┘       ├┤    ├┼┘        ├┼┴┘ ⎥
⎢       └┘       ├┤        └┘        ├┤    ├┤         └┘   ⎥
⎢                └┘                  ├┤    └┘              ⎥
⎣                                    └┘                    ⎦

Exemple de calcul avec des espèces

Pour l'espèce des arbres enracinés d'ensembles non-vides. 🌴

sage: E1 = species.SetSpecies(min=1)
sage: E = species.SetSpecies()

sage: T = species.CombinatorialSpecies(min=1)
sage: T.define(E1*E(T))

sage: T.isotype_generating_series()

z + 2*z^2 + 5*z^3 + 13*z^4 + 37*z^5 + 108*z^6 + 332*z^7 + O(z^8)