Signatures de permutation (encore elles ...)

Foys
Foys
Modifié (September 2022) dans Algèbre
Le souhait de proposer une preuve courte et intuitive de l'existence d'un morphisme non trivial du groupe des permutations d'un ensemble fini dans $\{-1,1\}$ a déjà été plusieurs fois abordé sur ce forum. Je n'ai pas les discussions sous la main mais on peut les retrouver.
L'examen du produit $\prod_{1\leq p < q \leq n} \frac{\sigma (q) - \sigma (p)}{q-p}$ où $n\in \N$ et $\sigma: \{1,...,n\} \to \{1,...,n\}$ n'est pas du goût de tout le monde d'après ce que j'ai vu (c'est pourtant le moyen le plus rapide de procéder probablement).

L'idée ici est d'exploiter le fait que pour tout $n$, le groupe $\mathfrak S_n$ des bijections de $\{1,...,n\}$ est engendré par les transpositions de termes successifs.
On suppose $n\geq 2$ et pour tout $k\leq n-1$ on pose $t_k(x):=x$ si $x\in \{1,...,n\}\backslash \{k,k+1\}$, $t_k(k):=k+1$ et $t_k(k+1):=k$.
Pour tout $\theta \in \mathfrak S_n$, on pose $E(\theta):= \left \{(x,y)\in \{1,...,n\}^2 \mid x<y \text{ et } \theta (x) > \theta (y) \right \}$.

1°) Soit $\sigma \in \mathfrak S_n$, $k\in \{1,...,n-1\}$ et $a,b\in \{1,...,n\}$ tels que $\sigma (a)= k$ et $\sigma (b) = k+1$.
1.i) montrer que pour tous $x,y$ tels que $\{x,y\} \neq \{a,b\}$, on a $(x,y)\in E(\sigma)$ si et seulement si $(x,y)\in E(t_k \circ \sigma)$
1.ii) en déduire que $|card(E(\sigma)) - card (E(t_k \circ \sigma))| = 1$.

2°) Montrer que pour tous $d\in \N$ et $p \in \{1,...,n-1\}^d$, $card \left (E(t_{p_d} \circ t_{p_{d-1}} \circ ... \circ t_{p_1}) \right ) = d \mod 2$ puis conclure.
Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.

Réponses

  • bisam
    bisam
    Modifié (September 2022)
    Je pense qu'il y a un bug dans ta question 1.i) et que tu voulais dire $\notin$ pour l'un des deux.
    C'est une des méthodes les plus classiques, il me semble, même si la présentation diffère une peu de celles que j'ai déjà rencontrées.
    On retrouve une démonstration similaire dans ce document (que j'ai déjà joint dans d'autres fils), au début de la page numérotée 13 (mais qui est la page 8 du pdf). Elle ressemble également à celle de la page 17 (ou 12 du pdf), utilisant les cycles des permutations.
  • john_john
    john_john
    La définition par $\displaystyle\prod_{1\leqslant p < q \leqslant n} \frac{\sigma (q) - \sigma (p)}{q-p}$ est certes séduisante, mais elle présente le défaut de ne s'appliquer qu'à un ensemble énuméré (ou ordonné). Si l'on doit choisir un ordre, il faut encore vérifier qu'elle ne dépend pas des $n!$ possibles.

    Je connais quelqu'un qui a été barré à l'oral de l'agrég pour cela, dans les années soixante-dix  >:) 
  • Lars
    Lars
    Modifié (September 2022)
    Bonjour
    Je ne vois rien d'intuitif dans cette preuve ni dans celles qui sont enseignées.
    Par contre, je trouve la construction page 13 (due à Lagrange) très intuitive. Et on peut s'en inspirer pour faire une preuve express en utilisant l'algèbre linéaire et le déterminant (qui sera bien sûr circulaire si on ne sait pas construire le déterminant sans la signature).
  • Foys
    Foys
    Modifié (September 2022)
    john_john a dit :
    La définition par $\displaystyle\prod_{1\leqslant p < q \leqslant n} \frac{\sigma (q) - \sigma (p)}{q-p}$ est certes séduisante, mais elle présente le défaut de ne s'appliquer qu'à un ensemble énuméré (ou ordonné). Si l'on doit choisir un ordre, il faut encore vérifier qu'elle ne dépend pas des $n!$ possibles.
    Je connais quelqu'un qui a été barré à l'oral de l'agrég pour cela, dans les années soixante-dix  >:) 
    C'est dommage car
    1°) Ici on considère $\{1,\ldots,n\}$ qui est ordonné naturellement.
    2°) Soient $n\geq 2$ et $f,g$ deux morphismes de $\mathfrak S_n$ dans $(\{-1,1\},\times)$. Si $f((n-1,n)) = g((n-1,n))$ alors $f=g$.
    En effet, soient $i,j\in \{1,\ldots,n\}$ tels que $i<j$. Soit $\sigma$ une bijection de $\{1,\ldots,n\}$ envoyant $i$ sur $n-1$ et $j$ sur $n$. Alors $\sigma^{-1} \circ (n-1,n) \circ \sigma = (i,j)$. Par suite pour tout morphisme $h:\mathfrak S_n \to \{-1,1\}$, $h((i,j)) = h(\sigma^{-1}) h((n-1,n)) h (\sigma) = h((n-1,n))$. Par suite $f$ et $g$ ont la même valeur sur toutes les transpositions de $\{1,\ldots,n\}$, et donc aussi sur tout le groupe qu'elles engendrent, à savoir $\mathfrak S_n$.
    Bref il y a au plus deux morphismes de $\mathfrak S_n$ dans $\{-1,1\}$ (ou dans n'importe quel groupe commutatif) et si $E$ est un ensemble fini quelconque, il y a au plus deux morphismes de groupes de $\mathfrak S_E$ dans $\{-1,1\}$ dont celui qui est constant égal à l'identité.
    Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
  • Foys
    Foys
    Modifié (September 2022)
    bisam a dit :
    Je pense qu'il y a un bug dans ta question 1.i) et que tu voulais dire $\notin$ pour l'un des deux.
    Je ne vois pas trop où.
    Si $x=y$ alors $(x,y) \notin E(\sigma) \cup E(t_k \circ \sigma)$ (ces ensembles ne contenant que des couples d'éléments distincts) et alors l'équivalence est évidente.
    Sinon, dans le cas où $x\neq y$, $\{x,y\} \neq \{a,b\}$ si et seulement si $x\notin \{a,b\}$ ou $y \notin \{a,b\}$. Le sens $\Leftarrow $ est évident. Réciproquement, pour le sens direct, $\{x,y\}$ et $\{a,b\}$ possèdent chacun deux éléments (par hypothèse pour le premier et parce que les images de $a$ et $b$ sont distinctes par $\sigma$ pour le second). L'inclusion $\{x,y\}\subseteq \{a,b\}$ entraîne donc l'égalité $\{x,y\} = \{a,b\}$ qui contredit l'hypothèse de la question 1.i). Donc cette inclusion est fausse, autrement dit $x\notin \{a,b\}$ ou $y\notin \{a,b\}$.
    Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
  • bisam
    bisam
    Effectivement, j'ai lu trop vite.
  • Foys
    Foys
    Pour 1.i), il suffit de remarquer que, étant donnés $(p,q)$ distincts dans $\{1,...,n\}$, le seul cas où $t_k(p) - t_k(q)$ n'est pas du même signe que $p-q$ est celui où $\{p,q\} = \{k,k+1\}$.
    Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
  • Math Coss
    Math Coss
    Modifié (September 2022)
    Très coxeterienne, la méthode de Foys. Elle ressemble beaucoup à ce que Cartier propose en haut de la p. 13 dans l'article cité plus haut.
    Plutôt que les couples $(i,j)$ avec $i<j$, Oliver considère pour une permutation $\sigma$ donnée l'ensemble $P_\sigma$ des paires $\{i,j\}$ avec $i<j$ et $\sigma(i)>\sigma(j)$. Ainsi, une paire est dans $P_\sigma$ ssi la restriction de $\sigma$ à cette paire est décroissante. On vérifie facilement que \[P_{\sigma'\sigma}=P_{\sigma\triangle\sigma^{-1}}(P_{\sigma'}),\] où $\sigma$ et $\sigma'$ sont deux permutations quelconques et $\triangle$ est la différence symétrique. On vérifie alors que $\newcommand{\card}{\mathop{\mathrm{card}}}\varepsilon:\sigma\mapsto(-1)^{\card P_\sigma}$ est un morphisme non trivial, car pour deux ensembles finis $A$ et $B$ quelconques, on a \[\card(A\triangle B )=\card(A)+\card(B)-2\card(A\cap B ).\]
  • Maxtimax
    Maxtimax
    Voir ici pour une variante de la construction de Cartier, que je trouve très claire (et intuitive !)
  • john_john
    john_john
    Foys : mon intervention n'était pas destinée à déconseiller la définition  de $\varepsilon(\sigma)$ par un produit, mais devait servir de mise en garde. Le candidat malheureux d'il y a cinquante ans n'avait peut-être pas prévu que le jury allait lui demander si sa définition s'étendait au cas d'un ensemble fini non énuméré.
  • Thierry Poma
    Thierry Poma
    @Math Coss : bonsoir. Bisam a déjà cité le premier document que tu présentes.
    @Maxtimax : bonsoir. Intuif, pour qui ?
    Le chat ouvrit les yeux, le soleil y entra. Le chat ferma les yeux, le soleil y resta. Voilà pourquoi le soir, quand le chat se réveille, j'aperçois dans le noir deux morceaux de soleil. (Maurice Carême).
  • Math Coss
    Math Coss
    Une façon de montrer les inversions d'une permutation, disons par exemple \[\sigma=\begin{pmatrix}1&2&3&4&5&6&7&8\\4&6&2&5&8&3&7&1\end{pmatrix}=(1458)(263),\]c'est de regarder les intersections dans un diagramme comme le suivant.
    On en déduit aussi facilement une décomposition en transpositions de la forme $(k,k+1)$, celles du message initial de Foys. Ici, $\sigma=\cdots(34)(12)(45)(67)\ (78)(23)(56)$.

  • Thierry Poma
    Thierry Poma
    Bonjour
    Je ne peux pas laisser de côté la belle contribution de GaBuZoMeu que nous trouvons ici. Je trouve qu'il n'y a pas plus naturel d'introduire le concept de signature d'une permutation.
    Titi
    Le chat ouvrit les yeux, le soleil y entra. Le chat ferma les yeux, le soleil y resta. Voilà pourquoi le soir, quand le chat se réveille, j'aperçois dans le noir deux morceaux de soleil. (Maurice Carême).
  • Foys
    Foys
    Merci beaucoup (en retard !! désolé) à @Maxtimax pour cette preuve catégoriste (mais qui montre qu'on peut se focaliser sur des orientations et non sur des ordres totaux qu'elles généralisent -ce que font les preuves classiques au fond-).
    Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
  • GG
    GG
    Modifié (October 2022)
    Bonjour,

    dans le fil de messages cité par Thierry Poma  ici, il y a 5 ans, CC avait donné un argument trés astucieux pour montrer que l'dentité est toujours le produit d'un nombre pair de transpositions (et par conséquent, fournissant une définition parfaitement intrinsèque de la signature, sans faire appel à une construction auxiliaire d'un polynôme, ni à une quelconque relation d'ordre). Il l'avait attribué à l'intervenant gb. Quelqu'un sait-il si celui-ci l'avait inventé ou si c'est un fait connu dans la littérature mathématique ?
  • Foys
    Foys
    Modifié (October 2022)
    La preuve de gb est très élégante! elle se base sur le simple fait suivant: Soit $X$ un ensemble, $x\in X$, $T$ l'ensemble des transpositions de $X$ (permutations échangeant exactement deux éléments) et $T_x$ le sous-ensemble de $T$ dont les éléments sont les $\varphi$ telles que $\varphi(x) \neq x$. Alors pour tous $\alpha,\beta \in T$, il existe $\alpha',\beta' \in T$ telles que $\alpha \circ \beta = \alpha' \circ \beta'$ et *** $\beta' \notin T_x $ ***.
    Une simple distinction de cas suffit (étant données deux transpositions, soit elles commutent, soit leur composition est un 3-cycle)
    Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 12

HéhéhéJean-Louis Aymegai requinmtho5stfjtroisqua +6 Invités