Permutations, partitions et polynômes

claude quitté · August 2019

Sorry pour la platitude du titre. Etant donnée une permutation $\sigma \in S_n$, je note $\lambda = (\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_m)$ la partition associée i.e. la suite des longueurs des orbites rangée de manière décroissante. Et j'associe à $\sigma$ le polynôme
$$
P(\sigma) = \prod_{j=1}^m (X^{\lambda_j} - 1)
$$
Et je voudrais démontrer que :
$$
{1 \over n!} {\sum_{\sigma \in S_n} P(\sigma)^2 \over (X-1)^2} = Y^{n-1} + Y^{n-2} + \cdots + Y + 1 \qquad \text{avec} \quad Y = X^2
$$
Remarques : on se fiche de la décroissance de $\lambda$ vu ce que l'on en fait. Par ailleurs, on pourrait remplacer $X^\bullet - 1$ par $1- X^\bullet$, cela ne change évidemment rien.
Comme d'habitude, si une personne à une idée ... Merci. Et forte récompense bien entendu.

claude quitté · August 2019

Hello. J'ai trouvé ce que je cherchais en m'inspirant (fortement) de la page 11 de Don Zagier in https://people.mpim-bonn.mpg.de/zagier/files/tex/ApplRepTheoryFiniteGroups/fulltext.pdf Comme la preuve utilise une technique qui m'est inhabituelle, je la donne ci-dessous. Je change un peu les notations de mon post précédent. Voici deux égalités à montrer :
$$
{1 \over n!} \sum_{\sigma \in S_n} D(\sigma) = 1 - X, \qquad
{1 \over n!} \sum_{\sigma \in S_n} D(\sigma)^2 = (1 - X)^2 \sum_{i=0}^{n-1} X^{2i} , \qquad
\qquad \hbox {avec} \qquad
D(\sigma) = \det(1 - X\sigma)
\qquad \qquad (\heartsuit)
$$
Ce que je note $\det(1 - X\sigma)$ c'est $\det(\text{Id}_n - XP_\sigma)$ où $P_\sigma$ est la matrice de la permutation $\sigma \in S_n$. Il est clair que $D(\sigma)$ est invariant par conjugaison et s'exprime à partir de la partition $\lambda$ associée à $\sigma$
$$
D(\sigma) = \prod_j (1 - X^\lambda_j) = \prod_i (1- X^i)^{d_i} \qquad\hbox {avec} \qquad \lambda = (1^{d_1} 2^{d_2} 3^{d_3} \cdots)
$$
La suite $d_\bullet = (d_1, d_2, d_3, \cdots)$ a la signification suivante : 1 figure $d_1$ fois dans $\lambda$, 2 figure $d_2$ fois dans $\lambda$ ...etc.. Il est clair que l'on peut ajouter des $0$ à cette suite $d_\bullet$, que $\sum_i i d_i = n$, donc $d_i = 0$ pour $i > n$. Je me permettrais utiliser $D(d_\bullet)$ au lieu de $D(\sigma)$.

1. Je vais utiliser (sans le montrer) que la classe de conjugaison d'une permutation de partition $\lambda = (1^{d_1} 2^{d_2} 3^{d_3} \cdots)$ est de cardinal
$$
c_{d_\bullet} =_{\rm def} {n! \over 1^{d_1} d_1!\, 2^{d_2} d_2!\, 3^{d_3} d_3! \cdots}
$$
2. On a l'égalité de séries formelles dans $\Q[X]Y$
$$
\prod_{i=1}^\infty E_i = {1 - XY \over 1-Y} \qquad \text{avec} \quad E_i = \exp\left( {(1-X^i) Y^i \over i} \right)
$$
Justification
$$
\sum_{i \ge 1} {(1-X^i) Y^i \over i} = \sum_{i \ge 1} {Y^i \over i} - \sum_{i \ge 1} {(XY)^i \over i} = \log {1 \over 1- Y} - \log {1 \over 1-XY} = \log {1 - XY \over 1-Y}
$$
3. On développe l'exponentielle $E_i$ en utilisant $\exp(a) = \sum_{k \ge 0} a^k / k!$
$$
E_i = \sum_{d_i \ge 0} {(1- X^i)^{d_i} Y^{id_i} \over i^{d_i}\, d_i!}
$$
4. On examine dans le produit de tous les $E_i$ le terme en $Y^n$. Il s'agit de :
$$
\sum_{d_\bullet} { (1 - X^1)^{d_1} (1 - X^2)^{d_2} (1 - X^3)^{d_3} \cdots \over 1^{d_1}d_1!\, 2^{d_2}d_2!\, 3^{d_3}d_3! \cdots}
\qquad \hbox {la somme portant sur les suites } d_\bullet \text { telles que } \sum_i i d_i = n
$$
Ce terme en $Y^n$ est donc :
$$
\sum_{d_\bullet} {D(d_\bullet) \over n! / c_{d_\bullet}} = {1 \over n!} \sum_{d_\bullet} c_{d_\bullet} D(d_\bullet)
\qquad \text {i.e. en utilisant le point 1.} \qquad
{1 \over n!} \sum_{\sigma \in S_n} D(\sigma)
$$
C'est le truc convoité à gauche dans $(\heartsuit)$ là-haut. Qui est donc le terme en $Y^n$ dans la série formelle $ {1 - XY \over 1-Y}$ i.e. $1-X$.

5. Faire la même chose pour l'autre égalité de $(\heartsuit)$. en changeant dans $E_i$ $1- X^ i$ par $(1-X^i)^2$. Merci Don Zagier.

claude quitté · August 2019

$\def\St{\text{St}}\newcommand \scp[2] {\langle#1\,|\,#2\rangle}$Suite (et fin). On ne fait pas des calculs pour le plaisir (encore que). Ce qui précède est lié aux puissances extérieures $\bigwedge^r(\St_n)$, pour $0 \le r \le n-1$, de la représentation de dimension $n-1$ (dite parfois standard) du groupe symétrique $S_n$ sur l'hyperplan $H$ de $\C^n$ défini par $x_1 + \cdots + x_n = 0$. Il s'agit en particulier de montrer que chaque représentation $\bigwedge^r(\St_n)$, de dimension $\binom {n-1}{r}$, est irréductible.

1. A la base, une décomposition $S_n$-stable $\C^n =_{\rm def} \bigoplus_{i=1}^n \C\cdot e_i = H \oplus V$ où $H = \sum_{i,j} \C \cdot (e_i-e_j)$ est l'hyperplan et $V = \C\cdot \sum_i e_i \simeq \C$. C'est classique de démontrer que $(S_n, H)$ est irréductible. C'est elle qui est notée $\St_n$. Je note $\chi_r$ le caractère de la représentation $\bigwedge^r(\St_n)$.

2. Pour $\sigma \in S_n$, on dispose des deux égalités
$$
\det(1 - X\sigma) = \det_V(1 - X\sigma) \times \det_H(1 - X\sigma) = (1-X) \times \det_H(1 - X\sigma) \qquad\qquad\qquad
\det_H(1 - x\sigma) = \sum_{r=0}^{n-1} (-x)^r \chi_r, \quad x \in C
$$
A droite, c'est du type : expression des coefficients du polynôme caractéristique d'un endomorphisme comme la trace (au signe près) des puissances extérieures de cet endomorphisme.

3. Pour démontrer que chaque $\chi_r$ est irréductible, il suffit de voir que $\scp{F}{F} = n$ où $F = \sum_{r=0}^{n-1} \chi_r$. C'est le point de vue adopté par Don Zagier dans https://people.mpim-bonn.mpg.de/zagier/files/tex/ApplRepTheoryFiniteGroups/fulltext.pdf. A noter qu'ici (cadre de $S_n$), pour toute fonction centrale $G$, une permutation $\sigma$ étant conjuguée à la permutation inverse $\sigma^{-1}$, on a
$$
\scp{G}{G} =_{\rm def} {1 \over n!} \sum_{\sigma \in S_n} G(\sigma)G(\sigma^{-1}) = {1 \over n!} \sum_{\sigma \in S_n} G(\sigma)^2
$$
4. Le calcul de $\scp{F}{F} = n$ est l'objet du lemme 4 du papier, p. 9. Et comme cela ne me plaisait pas, j'ai voulu réaliser celui de $\scp{F_x}{F_x}$ où
$$
F_x = \sum_{r=0}^{n-1} (-x)^r \chi_r = {\det(1 - x\sigma) \over 1 - x}
$$
Si on croit que les $\chi_r$ sont irréductibles (et distincts), on doit trouver que $\scp{F_x}{F_x} = \sum_{i = 0}^{n-1} x^{2i}$. Il suffira alors de faire $x := -1$ puisque $F_{-1} = F$. Bref, c'est pour cette raison que j'ai voulu déterminer :
$$
{1 \over n!} \sum_{\sigma \in S_n} \det(1 - X\sigma)^2
$$
Mais sans Don Zagier qui réalise un calcul analogue page 11, je n'y serais pas arrivé.

5. Lien avec les partitions de $S_n$. On sait que l'ensemble des représentations irréductibles de $S_n$ est en correspondance biunivoque avec l'ensemble des partitions de $n$. Je n'en connais pas les détails (tableux de Young). J'ai lu que $\bigwedge^r (\St_n)$ est associée à la partition $(n-r,1^r)$ mais je n'en connais pas de preuve (c'est fait dans Fulton-Harris, je pense).
$$
\bigwedge^0 (\St_n) \leftrightarrow (n) \text { rep. triv.} \quad
\bigwedge^1(\St_n) \leftrightarrow (n-1,1) \quad
\bigwedge^2 (\St_n) \leftrightarrow (n-2, 1^2) = (n-2,1,1) \quad
\cdots\quad
\bigwedge^{n-1} (\St_n) \leftrightarrow (1^n) = (1, \cdots, 1)
$$
6. Don Zagier, dans son papier Applications of the representation theory of finite groups, prend en charge, de manière self-contained, le B.A.BA de la théorie des représentations linéaires des groupes finis. Enfin, ce dont il a besoin pour ses applications. Il dit beaucoup de bien du papier de A. Okounkov and A. Vershik, A new approach to representation theory of symmetric groups https://arxiv.org/abs/math/0503040.
Je donne l'impression de faire de la pub pour Don Zagier (qui n'en a pas besoin) ? C'est pas faux. Mais après tout, ce n'est peut-être pas tous les jours que l'on voit des applications combinatoires (que je trouve vachement intéressantes).

LOU16 · August 2019

Bonsoir,

Il y avait aussi cette petite récurrence qui ne fournit certes aucun éclairage sur la signification de cette stupéfiante identité:
$ \forall n \in \N^*,\:\: \mathfrak S_n$ est le groupe des permutations de $[\![1;n]\!]$, et $\quad \forall \sigma \in \mathfrak S_n, \:\: \quad a(\sigma):= \text{Card}\Big \{ \sigma^k(1) \mid k\in \N \Big\}. $
Je note également: $P_0=1\quad \text {et} \quad \forall n \in \N^*,\quad P_n =\dfrac 1 {n!}\displaystyle \sum _{\sigma \in \mathfrak S_n} P(\sigma)^2$.
Avec l'hypothèse de récurrence $\:\: \forall k \in [\![1;n]\!], \quad P_k = \dfrac {(X-1)(X^{2k}-1)}{X+1} \quad (\star),\quad$ on obtient:
$\begin{align*}\displaystyle P_{n+1} &=\: \dfrac 1{(n+1)!}\sum _{k=0} ^n \left(\sum _{ \substack {\sigma \in \mathfrak S_{n+1}\\ a(\sigma) = k+1}} P_{\sigma}^2\right) \:=\: \dfrac 1{(n+1)!} \sum _{k=0}^n \left( \dfrac {n!}{(n-k)!}(X^{k+1} -1)^2 \sum _{\sigma \in \mathfrak S_{n-k}} P(\sigma) ^2\right) \:=\: \dfrac 1 {n+1} \sum _{k=0}^n (X^{k+1} -1)^2 P_{n-k} \\&\underset {(\star)}=\:\dfrac 1{n+1} \left( (X^{n+1}-1)^2 + \dfrac {X-1}{X+1}\sum_{k=0} ^{n} (X^{k+1}-1)^2 (X^{2n-2k}-1)\right)\\ & =\:\dfrac 1{n+1}\dfrac{X-1}{X+1} \left( (X+1)(X^{n+1}-1)\sum_{k=0}^n X^k +\sum_{k=0}^n (X^{k+1}-1)^2(X^{2n-2k}-1) \right) \:=\: \dfrac {(X-1)(X^{2n+2}-1)}{X+1}\quad \square \end{align*}$

jandri · September 2019

Je préfère la démonstration par récurrence donnée par LOU16 à celle donnée par Claude Quitté : elle est plus élémentaire même s'il y a un peu de calculs.
On montre de la même façon par récurrence (avec moins de calculs) la formule: $\dfrac 1 {n!}\displaystyle \sum _{\sigma \in \mathfrak S_n} P(\sigma)=(X-1)X^{n-1}$.

Cela correspond à la première formule $(\heartsuit)$ donnée par Claude Quitté dans laquelle il manque le facteur $X^{n-1}$ : une moyenne de polynômes unitaires de degré $n$ est de degré $n$.

P. · September 2019

Si $\sigma$ est aleatoire et uniforme sur $S_n$ alors $P_n$ est une variable aleatoire de moment d'ordre un $m^1_n=X^n-X^{n-1}$ et d'ordre deux $m^2_n=\frac{X-1}{X+1}(X^{2n}-1.) $ C'est curieux que la variance de $P_n$ soit justement $m^2_{n-1}.$

claude quitté · September 2019

@LOU16
J'avais loupé ton post. Merci. J'ai un peu peiné pour la vérification. Compris pourquoi il fallait introduire $P_0 = 1$ ($P_n$ est unitaire de degré $2n$). Un inconvénient de la récurrence : une fois obtenu la relation de récurrence :
$$
P_{n+1} = {1\over n+1} \sum_{k = 0}^n (X^{k+1} - 1)^2 P_{n-k}
$$
comment faire pour déterminer $P_{n+1}$ si on ne dispose pas de $P_k = (X-1)^2 \sum_{i=0}^{n-1} X^{2i}$ pour $k \ge 1$? A vrai dire, même avec cette égalité pour $P_k$, j'ai eu la flemme de vérifier ta dernière ligne de calculs (dans laquelle il n'y a évidemment PAS d'erreur).

Note : peut-être qu'il y a encore des choses à cogiter car la détermination de la somme ${1 \over n!} \sum_{\sigma \in S_n} P(\sigma)^2$ conduit à l'irréductibilité de $n$ représentations de $S_n$ à savoir les $n$ premières puissances extérieures $\bigwedge^r$ pour $r = 0, \cdots, n-1$, de la représentation standard (en degré $n-1$) de $S_n$. Montrer que ces représentations sont irréductibles n'est pas un fait banal.

@Jandri
J'ai cru au début que tu mentionnais une erreur dans mon deuxième post. Bien sûr, cela aurait pu être le cas. Mais entre le premier et le deuxième post, j'ai changé mon fusil d'épaule. Dans le premier post, $P(\sigma)$ désigne le polynôme caractéristique de la permutation $\sigma$ (défini de manière complètement tordue et je me demande bien pourquoi j'ai fait cela) et dans le deuxième post, $D(\sigma)$ est défini par $\det(1 - \sigma X)$. Et on a, comme tu dis et comme je dis
$$
{1 \over n!} \sum_{\sigma \in S_n} P(\sigma) = (X-1)X^{n-1}, \qquad\qquad
{1 \over n!} \sum_{\sigma \in S_n} D(\sigma) = 1 - X
$$
En principe, on est bien d'accord.

jandri · September 2019

@Claude Quitté
Merci pour ces précisions mais dans ton post tu écris : $D(\sigma)$ est défini par $D(\sigma)=\det(1-\sigma X)=\det(Id_n-XP_{\sigma})$ où $P_{\sigma}$ est la matrice de la permutation $\sigma\in S_n$, ce qui fait que $D(\sigma)$ est un polynôme de degré $n$. La moyenne de ces polynômes a bien un degré égal à $n$.

claude quitté · September 2019

@Jandri Ok avec le fait que $D(\sigma)$ est de degré $n$ mais il n'est pas unitaire. Si bien que la somme des $D(\sigma)$ n'est pas de degré $n$. La somme est $n! \times (1-X)$. Ce qui suit est un peu bourrin de ma part mais j'ai pas mieux pour essayer de te convaincre rapidement (il y a également la preuve dans mon post numéro 2)

[color=#000000]> D := func < sigma | Determinant(1 - X*PermutationMatrix(QX,sigma)) > ;
> n := 3 ;
> Sn := SymmetricGroup(n) ;
> Dets := [D(sigma) : sigma in Sn] ;
> Dets ;
[
    -X^3 + 3*X^2 - 3*X + 1,
    -X^3 + 1,
    -X^3 + 1,
    X^3 - X^2 - X + 1,
    X^3 - X^2 - X + 1,
    X^3 - X^2 - X + 1
]
> 1/Factorial(n) * &+Dets ;
-X + 1
[/color]

jandri · September 2019

@Claude Quitté
Excuse-moi de t'avoir importuné avec cette histoire, j'ai compris mon erreur.
Je pensais (à tort) que ta formule était la même que celle que j'ai citée alors que ce sont deux formules différentes.
C'est pour cela que je n'ai pas remarqué que $D(\sigma)$ n'était pas le polynôme caractéristique mais le polynôme avec les coefficients dans l'ordre inverse.

Sauf erreur de ma part, ta formule réécrite avec les $P(\sigma)$ devient (avec $\epsilon(\sigma)$ la signature de $\sigma$) : $${1 \over n!} \sum_{\sigma \in S_n} \epsilon(\sigma)P(\sigma) = (-1)^n(1 - X)$$

jandri · September 2019

En introduisant les signatures dans la formule initiale j'ai obtenu une autre formule:
$${1 \over n!} \sum_{\sigma \in S_n} \epsilon(\sigma)P(\sigma)^2 = n(-X)^{n-1}(X-1)^2$$

claude quitté · September 2019

@Jandri
Cette fois, on est d'accord. Je veux dire que je suis d'accord avec ton avant dernier post. Et en ce qui concerne ton dernier post, j'ai juste fait une vérification numérique ($n=5$, $n=6$), ce qui me suffit.

1. Est ce que la détermination de la moyenne des $\varepsilon(\sigma) P(\sigma)^2$ a été compliquée ? Par récurrence ?

2. Ce qu'il faut comprendre, j'ai essayé de l'expliquer dans mon post numéro 3, c'est que la détermination de la moyenne des $P(\sigma)^2$ (ou des $D(\sigma)^2$, c'est la même chose) s'intègre dans une histoire de représentations irréductibles du groupe symétrique $S_n$, cf Don Zagier in https://people.mpim-bonn.mpg.de/zagier/files/tex/ApplRepTheoryFiniteGroups/fulltext.pdf.
Je n'ai pas d'interprétation de la moyenne des $\varepsilon(\sigma) P(\sigma)$ ou des $\varepsilon(\sigma) P(\sigma)^2$.
Note : dans mon post numéro 2, je n'ai PAS fourni de preuve de la détermination de la moyenne des $P(\sigma)^2$ (je le laisse à faire dans le point 5.) ; j'ai juste donné la détermination de la moyenne des $D(\sigma)$, histoire de me faire les dents et de montrer une technique de calcul tirée de Don Zagier. A ma connaissance, la détermination de la moyenne des $D(\sigma)$ ou des $P(\sigma)$ n'est d'aucune utilité dans l'histoire des puissances extérieures de la représentation standard de $S_n$. Je dis bien ``à ma connaissance''.

jandri · September 2019

Pour la moyenne des $\varepsilon(\sigma) P(\sigma)^2$ j'ai calculé à la main les premières valeurs (jusqu'à $n=4$) ce qui m'a permis de deviner une formule générale assez simple. Je l'ai ensuite démontrée par récurrence mais comme il y a un peu de calculs j'ai utilisé Maple qui les a fait instantanément.

Les $\varepsilon(\sigma) P(\sigma)$ sont reliés aux $D(\sigma)$ par $\varepsilon(\sigma) P(\sigma)=(-1)^n D(\sigma)$. En élevant au carré on a bien $P(\sigma)^2=D(\sigma)^2$.

Permutations, partitions et polynômes

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 28