Signatures de permutation (encore elles ...)
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
-
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.
-
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 -
BonjourJe 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).
-
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-dixC'est dommage car1°) 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$. -
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$.
-
Effectivement, j'ai lu trop vite.
-
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$. -
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 ).\]
-
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é.
-
@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).
-
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)$.
-
BonjourJe 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.TitiLe 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).
-
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$. -
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 ? -
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!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.8K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 52 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres