Mathématiques universitaires — Licence 1 · Bachelor Year 1

7Structures algébriques

Les mêmes règles de calcul ne cessent de réapparaître : entiers, nombres réels, nombres complexes, classes de congruence, et bientôt polynômes (Chapitre 8), vecteurs et matrices (Chapitres 18 et 21). L’algèbre extrait les schémas communs et leur donne un nom : groupe, anneau, corps. Démontrer un fait une seule fois, au niveau de la structure, le démontre d’un coup pour tous les exemples.

7.1 Lois de composition

Définition 7.1

Une loi de composition interne sur un ensemble $E$ est une application $E \times E \to E$ , notée $(x, y) \mapsto x * y$ . Elle est associative lorsque $(x*y)*z = x*(y*z)$ toujours, commutative lorsque $x * y = y * x$ toujours. Un élément $e$ est un élément neutre lorsque $e * x = x * e = x$ pour tout $x$ ; alors $x'$ est un inverse de $x$ lorsque $x * x' = x' * x = e$ .

Proposition 7.2 (Unicité)

Une loi admet au plus un élément neutre ; pour une loi associative possédant un élément neutre, chaque élément a au plus un inverse.

Démonstration. Si $e$ et $e'$ sont neutres : $e = e * e' = e'$ . Si $x'$ et $x''$ inversent $x$ : $x' = x' * e = x' * (x * x'') = (x' * x) * x'' = e * x'' = x''$ . ∎

7.2 Groupes

Définition 7.3 (Groupe)

Un groupe $(G, *)$ est un ensemble muni d’une loi associative admettant un élément neutre et dans lequel tout élément possède un inverse. Le groupe est abélien lorsque la loi est commutative.

Exemple 7.4

$(\Z, +)$ , $(\Q, +)$ , $(\R, +)$ , $(\C, +)$ ; $(\Q^*, \times)$ , $(\R^*, \times)$ , $(\C^*, \times)$ , $(\mathbb{U}_n, \times)$ (racines de l’unité, Définition 3.17) ; l’ensemble $\mathfrak{S}(E)$ des bijections d’un ensemble $E$ sur lui-même, muni de la composition — le groupe symétrique de $E$ , non abélien dès que $\abs E \geq 3$ . Ne sont pas des groupes : $(\N, +)$ (pas d’inverses), $(\Z, \times)$ (seuls $\pm 1$ sont inversibles).

Proposition 7.5 (Règles de calcul)

Dans un groupe $G$ (noté multiplicativement, de neutre $e$ ) :

simplification : $ax = ay \implies x = y$ et $xa = ya \implies x = y$ ;
$(ab)^{-1} = b^{-1} a^{-1}$ et $(a^{-1})^{-1} = a$ ;
pour $a, b \in G$ , chacune des équations $ax = b$ et $xa = b$ admet une unique solution ( $x = a^{-1}b$ , resp. $x = b a^{-1}$ ).

Démonstration. (1) On multiplie par $a^{-1}$ du bon côté, en utilisant l’associativité. (2) $(b^{-1}a^{-1})(ab) = b^{-1}(a^{-1}a)b = b^{-1}b = e$ et symétriquement ; l’unicité de l’inverse conclut ; le second point est la Proposition 7.2 appliquée à $a^{-1}$ . (3) On substitue, et (1) donne l’unicité. ∎

Exemple 7.6 (Les symétries d’un rectangle)

Un rectangle (non carré) admet exactement quatre isométries de lui-même sur lui-même : l’identité $e$ , la symétrie d’axe horizontal $h$ , la symétrie d’axe vertical $v$ , et le demi-tour $r$ autour du centre. La composition fait de cet ensemble à quatre éléments un groupe : chaque élément est son propre inverse ( $h^2 = v^2 = r^2 = e$ ), et le produit de deux éléments distincts autres que le neutre est le troisième ( $hv = vh = r$ : composer les deux symétries axiales donne le demi-tour). La table est symétrique, donc le groupe est abélien — et pourtant ce n’est pas le même groupe que celui des rotations $\mathbb U_4$ de l’Exemple 7.15 : là, $\iu$ est d’ordre $4$ , tandis qu’ici tout élément est d’ordre $\leq 2$ . Deux groupes de même taille peuvent donc avoir des structures multiplicatives véritablement différentes — la figure ci-dessous affiche les deux tables côte à côte. Ce groupe à quatre éléments réapparaîtra sous la forme $\{\pm1\} \times \{\pm1\}$ , et l’Exercice 7.7 explique pourquoi tout groupe dont tous les carrés sont triviaux est, comme celui-ci, nécessairement abélien.

Deux groupes à quatre éléments : U_4 = \e, , -1, - \ (à gauche) et le groupe du rectangle (à droite), les positions du neutre étant grisées. À gauche, le neutre serpente (un élément d’ordre 4 engendre tout) ; à droite, il remplit la diagonale (tout élément a pour carré e). Aucun changement de noms ne transforme une table en l’autre : les groupes ne sont pas isomorphes. — Deux groupes à quatre éléments : $\mathbb U_4 = \{e, \iu, -1, -\iu\}$ (à gauche) et le groupe du rectangle (à droite), les positions du neutre étant grisées. À gauche, le neutre serpente (un élément d’ordre $4$ engendre tout) ; à droite, il remplit la diagonale (tout élément a pour carré $e$ ). Aucun changement de noms ne transforme une table en l’autre : les groupes ne sont pas isomorphes.

Définition 7.7 (Sous-groupe)

Une partie $H$ d’un groupe $G$ est un sous-groupe (on note $H \leq G$ ) lorsqu’elle contient $e$ , est stable par la loi et par passage à l’inverse. Alors $H$ est lui-même un groupe.

Critère : une partie non vide $H \subseteq G$ est un sous-groupe si et seulement si

\forall x, y \in H, \quad x y^{-1} \in H .

Démonstration du critère. Un sous-groupe le vérifie de façon évidente. Réciproquement, soit $H \neq \emptyset$ le vérifiant, et prenons $x_0 \in H$ . Alors $e = x_0 x_0^{-1} \in H$ ; pour $y \in H$ , $y^{-1} = e\,y^{-1} \in H$ ; et pour $x, y \in H$ , $xy = x (y^{-1})^{-1} \in H$ . ∎

Exemple 7.8

$\mathbb{U}_n \leq (\C^*, \times)$ : non vide, et pour $z, w \in \mathbb{U}_n$ , $(zw^{-1})^n = z^n (w^n)^{-1} = 1$ . Les sous-groupes de $(\Z, +)$ sont exactement les $n\Z$ (démontré en Théorème 6.4). Une intersection de sous-groupes est toujours un sous-groupe, mais une réunion ne l’est presque jamais (Exercice 7.6).

Remarque 7.9 (Pièges classiques avec les structures)

La stabilité par la loi ne suffit pas. $\N$ est stable par addition dans $\Z$ et contient $0$ , mais n’est pas un sous-groupe : les inverses manquent. Le critère $xy^{-1} \in H$ teste tout d’un coup — mais seulement après avoir vérifié que $H \neq \emptyset$ .
Réflexes non abéliens. Dans un groupe quelconque, $(ab)^2 = abab$ , qui ne vaut $a^2b^2$ que si $a$ et $b$ commutent ; de même $(ab)^{-1} = b^{-1}a^{-1}$ , dans l’ordre inverse. Toute identité importée de l’algèbre du lycée doit être redémontrée à partir des axiomes, ou signalée comme valable dans le cas commutatif.
Noyau contre image. $\ker f$ vit dans l’ensemble de départ, $\operatorname{im} f$ dans l’ensemble d’arrivée ; « $f$ est injectif si et seulement si $\ker f$ est trivial » (Proposition 7.11) n’a aucun analogue avec l’image ( $\operatorname{im} f = G'$ , c’est la surjectivité).
Les anneaux ne sont pas des groupes pour $\times$ . Dans un anneau, la plupart des éléments n’ont aucune raison d’être inversibles, et simplifier par $a$ exige que $a$ soit inversible ou que l’anneau soit intègre : dans $\Z/12\Z$ , $\overline3\,\overline2 = \overline3\,\overline6$ alors que $\overline2 \neq \overline6$ (Exemple 7.27).

Définition 7.10 (Morphisme de groupes)

Soient $(G, *)$ et $(G', \star)$ deux groupes. Une application $f \colon G \to G'$ est un morphisme lorsque

\forall x, y \in G, \qquad f(x * y) = f(x) \star f(y).

On a alors $f(e_G) = e_{G'}$ et $f(x^{-1}) = f(x)^{-1}$ . Le noyau et l’image de $f$ sont

\ker f = f^{-1}(\{e_{G'}\}) \leq G, \qquad \operatorname{im} f = f(G) \leq G' .

Un morphisme bijectif est un isomorphisme ; son application réciproque est alors automatiquement un morphisme.

Démonstration des assertions. $f(e) = f(e * e) = f(e)\star f(e)$ , et en simplifiant par $f(e)$ on obtient $e_{G'} = f(e)$ . Ensuite $f(x)\star f(x^{-1}) = f(x x^{-1}) = e_{G'}$ identifie $f(x^{-1})$ comme étant l’inverse. Noyau : $e \in \ker f$ ; si $x, y \in \ker f$ , $f(xy^{-1}) = f(x)f(y)^{-1} = e$ ; le critère s’applique. Image : même critère, avec $f(x)f(y)^{-1} = f(xy^{-1})$ . Réciproque d’un isomorphisme : pour $u, v \in G'$ , écrivons $u = f(x)$ , $v = f(y)$ ; alors $f^{-1}(u \star v) = f^{-1}(f(xy)) = xy = f^{-1}(u) f^{-1}(v)$ . ∎

Proposition 7.11 (Injectivité par le noyau)

Un morphisme de groupes $f$ est injectif si et seulement si $\ker f = \{e\}$ .

Démonstration. Si $f$ est injectif, $\ker f$ ne peut contenir que l’unique antécédent de $e_{G'}$ , à savoir $e$ . Réciproquement, si $\ker f = \{e\}$ et $f(x) = f(y)$ , alors $f(xy^{-1}) = f(x) f(y)^{-1} = e_{G'}$ , donc $xy^{-1} = e$ , c’est-à-dire $x = y$ . ∎

Exemple 7.12

$\exp \colon (\R, +) \to (\R_+^*, \times)$ est un morphisme ( $\eu^{x+y} = \eu^x \eu^y$ ), bijectif (Proposition 4.1) : les structures additive et multiplicative sont isomorphes — la raison d’être historique des logarithmes. Autre morphisme : $\theta \mapsto \eu^{\iu\theta}$ , de $(\R, +)$ sur le cercle unité $(\mathbb{U}, \times)$ , de noyau $2\pi\Z$ .

Exemple 7.13 (Le morphisme signe)

L’application $s \colon (\R^*, \times) \to (\{\pm1\}, \times)$ qui envoie $x$ sur son signe est un morphisme : le signe d’un produit est le produit des signes. Son noyau est $\intoo0{+\infty}$ (un sous-groupe, comme le promet Définition 7.10), son image est $\{\pm1\}$ tout entier : surjectif, massivement non injectif. Deux leçons générales en miniature. D’abord, un morphisme peut écraser de l’information : $s$ ne retient de $x$ qu’un seul bit, et c’est là sa vertu — les raisonnements de signe sont exactement les calculs qui se factorisent par $s$ . Ensuite, les morphismes à valeurs dans $\{\pm1\}$ sont les « invariants » les plus simples : la signature des permutations, construite dans le devoir maison de ce chapitre, est le même phénomène sur le groupe $\mathfrak S_n$ , et tous les raisonnements de parité qu’elle alimente passent par un tel morphisme à deux valeurs.

Définition 7.14 (Puissances, ordre d’un élément)

Dans un groupe $G$ (en notation multiplicative), on pose $x^0 = e$ , $x^{k+1} = x^k x$ et $x^{-k} = (x^k)^{-1}$ pour $k \in \N$ ; on a alors $x^{k+l} = x^k x^l$ pour tous $k, l \in \Z$ , de sorte que $k \mapsto x^k$ est un morphisme $(\Z, +) \to G$ dont l’image $\langle x \rangle = \{x^k : k \in \Z\}$ est un sous-groupe, le sous-groupe engendré par $x$ . L’ordre de $x$ est le plus petit $m \geq 1$ tel que $x^m = e$ , s’il en existe un (alors $\langle x\rangle = \{e, x, \dots, x^{m-1}\}$ a exactement $m$ éléments, et $x^k = e \iff m \mid k$ ), et $\infty$ sinon.

Exemple 7.15

Dans $(\C^*, \times)$ : $\iu$ est d’ordre $4$ , avec $\langle \iu \rangle = \{1, \iu, -1, -\iu\} = \mathbb{U}_4$ ; plus généralement $\omega = \eu^{2\iu\pi/n}$ est d’ordre $n$ et $\langle\omega\rangle = \mathbb{U}_n$ . Dans $(\Z, +)$ , tout $x \neq 0$ est d’ordre infini. Pourquoi les affirmations de la définition sont vraies : si $x$ est d’ordre $m$ , effectuons la division euclidienne d’un $k$ quelconque par $m$ ( $k = mq + r$ , $0 \leq r < m$ , Théorème 6.2) : $x^k = (x^m)^q x^r = x^r$ , donc les puissances sont périodiques de période $m$ , les éléments énumérés sont deux à deux distincts par minimalité de $m$ , et $x^k = e$ force $r = 0$ . Les ordres des permutations sont calculés dans le devoir maison ci-dessous.

Exemple 7.16 (Ordres dans $\mathbb U_{12}$ )

Quel est l’ordre de $\omega^k$ dans $\mathbb U_n$ , pour $\omega = \eu^{2\iu\pi/n}$ ? On a $(\omega^k)^m = 1$ si et seulement si $n \mid km$ , et en écrivant $d = \gcd(n, k)$ , $n = dn'$ , $k = dk'$ avec $\gcd(n', k') = 1$ : $n \mid km \iff n' \mid k'm \iff n' \mid m$ (lemme de Gauss, Théorème 6.8). Le plus petit tel $m \geq 1$ est $n' = \frac{n}{\gcd(n,k)}$ . Dans $\mathbb U_{12}$ par exemple, $\omega^8$ est d’ordre $\frac{12}{\gcd(12,8)} = 3$ (en effet $\omega^8 = \eu^{4\iu\pi/3} \in \mathbb U_3$ ), tandis que $\omega^5$ est d’ordre $12$ : il engendre le groupe tout entier, bien qu’il ne soit pas le générateur « standard ». Compter les générateurs — les $k$ tels que $\gcd(k, n) = 1$ — redonne les dénombrements d’entiers premiers avec $n$ de l’Exemple 2.25 : théorie des groupes et dénombrement se rejoignent.

7.3 Anneaux et corps

Définition 7.17 (Anneau)

Un anneau $(A, +, \times)$ est un ensemble muni de deux lois telles que : $(A, +)$ est un groupe abélien (de neutre $0$ ) ; $\times$ est associative et possède un élément neutre $1$ ; et $\times$ est distributive par rapport à $+$ des deux côtés. L’anneau est commutatif lorsque $\times$ l’est. Un élément $a$ est inversible (on dit aussi que c’est une unité) lorsque $ab = ba = 1$ pour un certain $b$ ; les inversibles forment un groupe $(A^\times, \times)$ .

Démonstration : les inversibles forment un groupe. Stabilité : si $a, a'$ sont inversibles, d’inverses $b, b'$ , alors

(aa')(b'b) = a(a'b')b = a\,1\,b = ab = 1, \qquad (b'b)(aa') = 1

symétriquement, donc $aa'$ est inversible. L’élément $1$ est inversible (il est son propre inverse), l’associativité est héritée de $A$ , et l’inverse $b$ d’un inversible $a$ est lui-même inversible (d’inverse $a$ ). Ainsi $(A^\times, \times)$ vérifie tous les axiomes de groupe. Tous les groupes de ce livre qui ne sont pas construits à partir de permutations apparaissent de cette façon : $\Q^* = \Q^\times$ , $\R^*$ , $\C^*$ , les inversibles de $\Z/n\Z$ ci-dessous, et plus tard les matrices inversibles (Chapitre 21). ∎

Exemple 7.18

$\Z, \Q, \R, \C$ sont des anneaux commutatifs ; $\Z^\times = \{1, -1\}$ , $\Q^\times = \Q^*$ . Plus tard : les anneaux de polynômes $K[X]$ (Chapitre 8), les anneaux de matrices (non commutatifs, Chapitre 21), et $\Z/n\Z$ ci-dessous. Dans tout anneau, $0 \times a = 0$ (par distributivité : $0a = (0+0)a = 0a + 0a$ ), et $(-1)a = -a$ .

Exemple 7.19 (Idempotents : des phénomènes nouveaux dans des anneaux nouveaux)

Dans $\Z$ , l’équation $x^2 = x$ , c’est-à-dire $x(x - 1) = 0$ , n’a que les solutions $0$ et $1$ . Dans $\Z/6\Z$ , en testant toutes les classes : $\overline0^2 = \overline0$ , $\overline1^2 = \overline1$ , $\overline3^2 = \overline9 = \overline3$ et $\overline4^2 = \overline{16} = \overline4$ — quatre idempotents. Les deux exotiques proviennent de diviseurs de zéro : $\overline3\,(\overline3 - \overline1) = \overline3 \times \overline2 = \overline6 = \overline0$ , sans qu’aucun des deux facteurs ne soit nul. De tels calculs recalibrent l’intuition : les faits familiers sur les équations survivent dans les anneaux intègres et dans les corps, mais un anneau quelconque peut se comporter — et se comporte — tout autrement ; voir aussi les anneaux de Boole de l’Exercice 7.10, où tout élément est idempotent.

Proposition 7.20 (Formule du binôme dans un anneau commutatif)

Si $a, b$ sont des éléments d’un anneau commutatif (plus généralement, si $ab = ba$ ), alors pour $n \in \N$ :

(a+b)^n = \sum_{k=0}^n \binom nk a^k b^{n-k}, \qquad a^n - b^n = (a - b) \sum_{k=0}^{n-1} a^k b^{\,n-1-k} .

Démonstration. Les démonstrations du Théorème 2.16 et de l’identité géométrique n’utilisent que l’associativité, la commutativité des deux éléments et la distributivité — elles s’appliquent mot pour mot. ∎

Exemple 7.21 (La formule du binôme dans un anneau inhabituel)

Deux bénéfices immédiats de cette généralité. Dans $\Z/p\Z$ ( $p$ premier), les coefficients binomiaux intermédiaires sont nuls (c’est la première étape du Théorème 6.23), de sorte que la formule s’effondre en le rêve du débutant

(a + b)^p = a^p + b^p \qquad \text{dans } \Z/p\Z ,

une véritable identité dans cet anneau, si criminelle qu’elle paraisse sur $\R$ . Et dans tout anneau commutatif contenant un élément $\varepsilon$ tel que $\varepsilon^2 = 0$ , la formule se tronque : $(a + \varepsilon)^n = a^n + n\,a^{n-1}\varepsilon$ , tous les termes suivants portant un facteur $\varepsilon^2 = 0$ . Le coefficient $n\,a^{n-1}$ de $\varepsilon$ est la dérivée de $x^n$ — ce n’est pas un hasard, et c’est un premier indice que les dérivées relèvent autant de l’algèbre que de l’analyse (comparer avec la dérivée formelle du Chapitre 8).

Définition 7.22 (Anneau intègre, corps)

Un anneau commutatif $A \neq \{0\}$ est un anneau intègre lorsqu’il n’a pas de diviseur de zéro : $ab = 0 \implies a = 0$ ou $b = 0$ . C’est un corps lorsque tout élément non nul est inversible. Tout corps est intègre ( $ab = 0$ et $a \neq 0$ donnent $b = a^{-1}ab = 0$ ).

Exemple 7.23

$\Q$ , $\R$ , $\C$ sont des corps ; $\Z$ est un anneau intègre mais n’est pas un corps. Dans un anneau intègre, on peut simplifier pour $\times$ : $ab = ac$ et $a \neq 0$ entraînent $b = c$ .

7.4 L’anneau $\Z/n\Z$

Définition 7.24

Fixons $n \in \N^*$ . Les classes de congruence modulo $n$ (Exemple 1.32) forment un ensemble $\Z/n\Z$ à $n$ éléments, notées $\overline 0, \overline 1, \dots, \overline{n-1}$ . Les opérations

\overline a + \overline b = \overline{a + b}, \qquad \overline a \times \overline b = \overline{ab}

sont bien définies — les classes des résultats ne dépendent pas des représentants, précisément parce que la congruence est compatible avec $+$ et $\times$ (Définition 6.18) — et font de $\Z/n\Z$ un anneau commutatif.

Théorème 7.25 (Inversibles de $\Z/n\Z$ ; les corps $\Z/p\Z$ )

$\overline a$ est inversible dans $\Z/n\Z$ si et seulement si $\gcd(a, n) = 1$ .
$\Z/n\Z$ est un corps si et seulement si $n$ est premier.

Démonstration. (1) n’est autre que la Proposition 6.20 réécrite en termes de classes.

(2) Si $n = p$ est premier, tout $\overline a \neq \overline 0$ vérifie $p \nmid a$ , donc $\gcd(a, p) = 1$ : il est inversible par (1) — c’est un corps. Si $n = ab$ avec $1 < a, b < n$ , alors $\overline a\, \overline b = \overline n = \overline 0$ avec $\overline a, \overline b \neq \overline 0$ : il y a des diviseurs de zéro, donc l’anneau n’est même pas intègre ; et $n = 1$ donne l’anneau nul, exclu. ∎

Exemple 7.26 (Combien de racines carrées de $1$ ?)

Résolvons $x^2 = \overline 1$ dans $\Z/8\Z$ puis dans $\Z/7\Z$ . En testant les huit classes modulo $8$ : $1^2 = 1$ , $3^2 = 9 \equiv 1$ , $5^2 = 25 \equiv 1$ , $7^2 = 49 \equiv 1$ — quatre solutions $\{\overline1, \overline3, \overline5, \overline7\}$ , alors même que le polynôme $X^2 - 1$ est de degré $2$ . Dans le corps $\Z/7\Z$ , en revanche, $x^2 = \overline1$ signifie $(x - \overline1)(x + \overline1) = \overline0$ , et un corps n’a pas de diviseur de zéro : $x = \pm\overline1$ , deux solutions seulement. L’échec modulo $8$ s’explique : $(3-1)(3+1) = 2 \times 4 = 8 \equiv 0$ sans qu’aucun des deux facteurs ne s’annule. Morale : la règle familière « une équation de degré $d$ a au plus $d$ racines » est un théorème sur les anneaux intègres (le Corollaire 8.8 le démontre sur un corps) ; dans un anneau à diviseurs de zéro, elle tombe en défaut sans prévenir — et c’est exactement pourquoi la démonstration par appariement du théorème de Wilson (Exercice 6.11) exigeait $p$ premier.

Exemple 7.27 (Calculer dans $\Z/n\Z$ )

Dans $\Z/12\Z$ : les inversibles sont $\overline 1, \overline 5, \overline 7, \overline{11}$ (les classes premières avec $12$ ), et chacun est son propre inverse ( $5^2 = 25 \equiv 1$ , $7^2 = 49 \equiv 1$ , $11^2 = 121 \equiv 1$ ). L’équation $\overline 3\, x = \overline 6$ a trois solutions ( $x \in \{\overline 2, \overline 6, \overline{10}\}$ ) : sans inversibilité, pas de simplification. Dans $\Z/11\Z$ en revanche, toute équation $\overline a x = \overline b$ avec $\overline a \neq \overline 0$ a exactement une solution.

Exemple 7.28 (Les axiomes de groupe comme permis de résoudre)

Dans le groupe $\bigl((\Z/7\Z)^*, \times\bigr)$ , résolvons $\overline 3\,x = \overline 5$ . D’après la Proposition 7.5 (3), la solution existe, elle est unique, et vaut $\overline3^{-1}\, \overline5$ ; comme $\overline3 \times \overline5 = \overline{15} = \overline1$ , l’inverse de $\overline 3$ est $\overline 5$ , d’où

x = \overline5 \times \overline5 = \overline{25} = \overline4, \qquad\text{vérification~: } \overline3 \times \overline4 = \overline{12} = \overline5 .

Ce qui compte, moins que la réponse, c’est la garantie : dans un groupe, toute équation de ce type admet une solution unique avant tout calcul, si bien qu’une procédure de résolution ne peut jamais tomber sur « pas de solution » ou « plusieurs ». Comparer avec $\overline3\,x = \overline6$ dans $\Z/12\Z$ ci-dessus, où la garantie tombe en défaut — savoir dans quelle structure on travaille, c’est savoir ce que l’on peut tenir pour acquis.

Exemple 7.29 (Produits directs)

Si $G$ et $H$ sont des groupes, l’ensemble produit $G \times H$ muni de la loi composante par composante $(g, h)(g', h') = (gg', hh')$ est un groupe : les axiomes se vérifient coordonnée par coordonnée, avec pour neutre $(e_G, e_H)$ et pour inverses $(g^{-1}, h^{-1})$ . Les ordres se combinent par le PPCM : $(g, h)^m = (g^m, h^m)$ est le neutre si et seulement si l’ordre de $g$ et l’ordre de $h$ divisent tous deux $m$ . Ainsi, dans $\Z/2\Z \times \Z/2\Z$ (noté additivement), tout élément non nul est d’ordre $2$ — c’est exactement le groupe du rectangle de l’Exemple 7.6 en coordonnées — alors que $\Z/4\Z$ possède un élément d’ordre $4$ : seconde démonstration, sans le moindre calcul, du fait que les deux groupes de cardinal $4$ ne sont pas isomorphes (un isomorphisme conserve les ordres). Les produits sont le moyen le plus simple de fabriquer des groupes nouveaux à partir d’anciens, et le plan $\R^2 = \R \times \R$ du Chapitre 18 est l’exemple le plus important de cette construction.

Remarque 7.30 (Fermat, structurellement)

Dans le corps $\Z/p\Z$ , les classes non nulles forment un groupe multiplicatif à $p - 1$ éléments, et le petit théorème de Fermat (Théorème 6.23) affirme : tout élément $x$ de ce groupe vérifie $x^{p-1} = \overline 1$ . C’est un cas particulier d’un fait général sur les groupes finis (le théorème de Lagrange), démontré en deuxième année ; la démonstration par appariement du théorème de Wilson (Exercice 6.11) avait déjà cette saveur de théorie des groupes.

Remarque 7.31 (Interlude : ce que rapporte l’abstraction)

On peut légitimement demander ce que l’on a gagné à démontrer, disons, la Proposition 7.2 pour une loi abstraite plutôt que pour des nombres. La réponse est un effet de levier. Cet argument de deux lignes couvre désormais, d’un seul coup : les réciproques des fonctions pour la composition (Théorème 1.24, dont il répète mot pour mot la démonstration d’unicité), les inverses modulo $n$ (Proposition 6.20), les inverses des réels non nuls, ceux des inversibles d’un anneau quelconque et — sans même les avoir vues — ceux des matrices inversibles du Chapitre 21, où l’unicité de $A^{-1}$ ne demandera pas une seule ligne de démonstration. La même économie vaut pour la Proposition 7.11 (un unique critère d’injectivité, réutilisé pour les applications linéaires au Chapitre 20) et pour le critère de sous-groupe. L’abstraction n’est pas ici la généralité pour elle-même : c’est le refus de démontrer cinq fois le même lemme sous cinq noms différents. Le prix — garder trace des axiomes que chaque énoncé a réellement utilisés — est précisément ce que les exercices de ce chapitre entraînent.

Remarque 7.32 (Où ce chapitre sert)

Le vocabulaire de ce chapitre est la grammaire de tout le reste du volume. Anneaux et corps organisent le Chapitre 8 ( $K[X]$ est un anneau qui imite $\Z$ ) et le Chapitre 9 ( $K(X)$ en est le corps des fractions) ; les espaces vectoriels (Chapitre 18) sont des groupes abéliens sur lesquels agit un corps ; les matrices (Chapitre 21) forment le premier anneau sérieusement non commutatif du volume, et leurs éléments inversibles un groupe dont l’étude est l’algèbre linéaire elle-même. Morphismes et noyaux reviennent sous la forme des applications linéaires et de leurs noyaux au Chapitre 20 — la Proposition 7.11 est le critère d’injectivité de ce chapitre-là, démontré ici une fois pour toutes. Le groupe symétrique, vedette du devoir maison ci-dessous, fournit la signature sur laquelle sont bâtis les déterminants au Chapitre 22.

7.5 Exercices

Exercice 7.1 ★

Sur $E = \R \setminus \{1\}$ , on définit $x * y = x + y - xy$ . Démontrer que $(E, *)$ est un groupe abélien. (Identifier l’élément neutre et l’inverse de $x$ ; vérifier la stabilité : pourquoi a-t-on $x * y \neq 1$ ?)

Solution

Solution de Exercice 7.1.

Stabilité : $x * y = 1 \iff x + y - xy = 1 \iff (1-x)(1-y) = 0$ , impossible pour $x, y \neq 1$ . En effet, l’identité clé est

1 - x * y = (1 - x)(1 - y):

l’application $\varphi(x) = 1 - x$ envoie $(E, *)$ sur $(\R^*, \times)$ avec $\varphi(x * y) = \varphi(x)\varphi(y)$ — c’est un morphisme bijectif. Tous les axiomes se transportent alors : associativité et commutativité découlent de celles de $\times$ ; l’élément neutre est $\varphi^{-1}(1) = 0$ (vérification : $x * 0 = x$ ) ; l’inverse de $x$ est $\varphi^{-1}\bigl((1-x)^{-1}\bigr) = 1 - \frac{1}{1-x} = \frac{x}{x - 1}$ (qui est $\neq 1$ ). Donc $(E, *)$ est un groupe abélien.

Exercice 7.2 ★

Lesquels des ensembles suivants sont des groupes ?

$(\intoo{0}{+\infty}, \times)$ ;
$(\{-1, 0, 1\}, +)$ ;
$(\Q^*, \times)$ ;
l’ensemble des entiers impairs muni de l’addition.

Solution

Solution de Exercice 7.2.

Oui : le produit de deux réels strictement positifs est strictement positif, neutre $1$ , inverse $\frac 1x$ , associativité héritée de $\R^*$ .
Non : pas de stabilité ( $1 + 1 = 2 \notin \{-1,0,1\}$ ).
Oui : c’est l’exemple standard.
Non : pas de stabilité (impair $+$ impair $=$ pair), et pas d’élément neutre ( $0$ est pair).

Exercice 7.3 ★

Écrire la table de composition du groupe symétrique $\mathfrak{S}_3$ de $\{1,2,3\}$ (six bijections : l’identité, trois transpositions, deux $3$ -cycles), et exhiber deux éléments qui ne commutent pas.

Solution

Solution de Exercice 7.3.

Notons $\mathrm{id}$ , les transpositions $\tau_{12}, \tau_{13}, \tau_{23}$ (qui échangent les deux points indiqués), et les cycles $c = (1\,2\,3)$ (c’est-à-dire $1 \mapsto 2 \mapsto 3 \mapsto 1$ ) et $c^2 = (1\,3\,2)$ . La table de $\sigma\rho$ (ligne $\sigma$ , colonne $\rho$ , on applique $\rho$ d’abord) :

$\sigma\backslash\rho$	$\mathrm{id}$	$c$	$c^2$	$\tau_{12}$	$\tau_{13}$	$\tau_{23}$
$\mathrm{id}$	$\mathrm{id}$	$c$	$c^2$	$\tau_{12}$	$\tau_{13}$	$\tau_{23}$
$c$	$c$	$c^2$	$\mathrm{id}$	$\tau_{13}$	$\tau_{23}$	$\tau_{12}$
$c^2$	$c^2$	$\mathrm{id}$	$c$	$\tau_{23}$	$\tau_{12}$	$\tau_{13}$
$\tau_{12}$	$\tau_{12}$	$\tau_{23}$	$\tau_{13}$	$\mathrm{id}$	$c^2$	$c$
$\tau_{13}$	$\tau_{13}$	$\tau_{12}$	$\tau_{23}$	$c$	$\mathrm{id}$	$c^2$
$\tau_{23}$	$\tau_{23}$	$\tau_{13}$	$\tau_{12}$	$c^2$	$c$	$\mathrm{id}$

Couple ne commutant pas : $\tau_{12}\tau_{13} = c^2$ tandis que $\tau_{13}\tau_{12} = c$ . (Vérification d’une case : $\tau_{12}\tau_{13}$ envoie $1 \xmapsto{\tau_{13}} 3 \xmapsto{\tau_{12}} 3$ , $3 \mapsto 1 \mapsto 2$ , $2 \mapsto 2 \mapsto 1$ : c’est $1 \mapsto 3 \mapsto 2 \mapsto 1$ , le cycle $c^2 = (1\,3\,2)$ .)

Exercice 7.4 ★

Démontrer que $H = \{z \in \C^* : \abs z = 1\}$ est un sous-groupe de $(\C^*, \times)$ , et que $\R_+^*$ en est un autre ; $H \cup \R_+^*$ est-il un sous-groupe ?

Solution

Solution de Exercice 7.4.

$H$ : $1 \in H$ ; pour $z, w \in H$ , $\abs{zw^{-1}} = \abs z / \abs w = 1$ : le critère s’applique. $\R_+^*$ : de même, la positivité remplaçant le module. Réunion : $\iu \in H$ et $2 \in \R_+^*$ , mais $2\iu$ a pour module $2 \neq 1$ et n’est pas un réel strictement positif : $2\iu \notin H \cup \R_+^*$ , donc la réunion n’est pas stable — ce n’est pas un sous-groupe (comme le prévoit Exercice 7.6, aucun des deux sous-groupes ne contient l’autre).

Exercice 7.5 ★★

Soit $f \colon (\R, +) \to (\C^*, \times)$ , $\theta \mapsto \eu^{\iu\theta}$ . Démontrer que $f$ est un morphisme, calculer $\ker f$ et $\operatorname{im} f$ , et déduire de la Proposition 7.11 que $f$ n’est pas injectif. Restreindre l’ensemble de départ de façon à rendre $f$ injectif sur un intervalle aussi grand que possible.

Solution

Solution de Exercice 7.5.

Morphisme : $\eu^{\iu(\theta + \varphi)} = \eu^{\iu\theta}\eu^{\iu\varphi}$ (Théorème 3.7). Noyau : $\eu^{\iu\theta} = 1 \iff \theta \in 2\pi\Z$ , donc $\ker f = 2\pi\Z \neq \{0\}$ : $f$ n’est pas injectif. Image : tout nombre complexe de module $1$ s’écrit $\eu^{\iu\theta}$ pour un certain $\theta$ (forme polaire), donc $\operatorname{im} f = \mathbb{U}$ , le cercle unité. La restriction de $f$ à un intervalle semi-ouvert de longueur $2\pi$ , comme $\intco{0}{2\pi}$ ou $\intoc{-\pi}{\pi}$ , est injective (deux angles de même image diffèrent d’un multiple de $2\pi$ , et un seul représentant de chaque classe tient dans l’intervalle) ; aucun intervalle de longueur supérieure ne convient, puisqu’il contient deux points distants de $2\pi$ .

Exercice 7.6 ★★

Soient $H, K$ des sous-groupes de $G$ . Démontrer que $H \cap K$ est un sous-groupe, et que $H \cup K$ n’est un sous-groupe que si $H \subseteq K$ ou $K \subseteq H$ . (Si $h \in H \setminus K$ et $k \in K \setminus H$ , où $hk$ peut-il bien vivre ?)

Solution

Solution de Exercice 7.6.

Intersection : $e \in H \cap K$ , et $x, y \in H \cap K$ donnent $xy^{-1}$ à la fois dans $H$ et dans $K$ . Réunion : si $H \subseteq K$ , la réunion est $K$ , qui est un sous-groupe (et symétriquement). Réciproquement, supposons qu’aucune des deux inclusions n’ait lieu : prenons $h \in H \setminus K$ et $k \in K \setminus H$ , et supposons que $H \cup K$ soit un sous-groupe ; alors $hk \in H \cup K$ . Si $hk \in H$ , alors $k = h^{-1}(hk) \in H$ : contradiction. Si $hk \in K$ , alors $h = (hk)k^{-1} \in K$ : contradiction. Donc $H \cup K$ n’est pas un sous-groupe.

Exercice 7.7 ★★

Un groupe $G$ vérifie $x^2 = e$ pour tout $x \in G$ . Démontrer que $G$ est abélien. (Développer $(xy)^2$ .)

Solution

Solution de Exercice 7.7.

Remarquons d’abord que $x^2 = e$ signifie $x^{-1} = x$ pour tout $x$ . Alors, pour $x, y \in G$ :

xy = (xy)^{-1} = y^{-1} x^{-1} = yx ,

en utilisant Proposition 7.5 (2). Donc $G$ est abélien.

Exercice 7.8 ★★

Dans $\Z/18\Z$ : énumérer les inversibles et trouver l’inverse de $\overline 5$ ; résoudre $\overline 5\, x = \overline 7$ ; résoudre $\overline 6\, x = \overline 3$ et $\overline 6\, x = \overline{12}$ .

Solution

Solution de Exercice 7.8.

Inversibles de $\Z/18\Z$ : les classes premières avec $18 = 2 \times 3^2$ : $\overline 1, \overline 5, \overline 7, \overline{11}, \overline{13}, \overline{17}$ . Inverse de $\overline 5$ : $5 \times 11 = 55 = 3\times 18 + 1$ , donc $\overline 5^{-1} = \overline{11}$ .

$\overline 5 x = \overline 7$ : on multiplie par $\overline{11}$ : $x = \overline{77} = \overline 5$ (car $77 = 4\times 18 + 5$ ). Solution unique.

$\overline 6 x = \overline 3$ : l’équation $6x \equiv 3 \pmod{18}$ signifie $18 \mid 6x - 3$ . Or $6x - 3 = 3(2x - 1)$ est impair, tandis que $18$ est pair : un nombre pair ne peut pas diviser un nombre impair. Pas de solution.

$\overline 6 x = \overline{12}$ : $6x \equiv 12 \pmod{18} \iff x \equiv 2 \pmod 3$ : solutions $x \in \{\overline 2, \overline 5, \overline 8, \overline{11}, \overline{14}, \overline{17}\}$ — il y en a six.

Exercice 7.9 ★★

Démontrer que l’ensemble $\Z[\sqrt 2] = \{a + b\sqrt 2 : a, b \in \Z\}$ est un anneau (un sous-anneau de $\R$ ), et que $1 + \sqrt 2$ en est un inversible dont les puissances sont deux à deux distinctes — de sorte que $\Z[\sqrt 2]^\times$ est infini, contrairement à $\Z^\times$ .

Solution

Solution de Exercice 7.9.

$\Z[\sqrt 2]$ contient $0$ et $1$ , et est stable par soustraction et par produit :

(a + b\sqrt 2)(c + d\sqrt 2) = (ac + 2bd) + (ad + bc)\sqrt 2 ,

c’est donc un sous-anneau de $\R$ (commutativité, associativité et distributivité sont héritées). Inversible : $(1 + \sqrt 2)(-1 + \sqrt 2) = 2 - 1 = 1$ , donc $1 + \sqrt 2$ est inversible, d’inverse $\sqrt 2 - 1 \in \Z[\sqrt 2]$ . Ses puissances $(1 + \sqrt 2)^n$ forment une suite strictement croissante (la base est $> 1$ ), donc sont deux à deux distinctes, et chacune est inversible ( $\bigl((1+\sqrt2)^n\bigr)^{-1} = (\sqrt 2 - 1)^n$ ) : le groupe des inversibles est infini.

Exercice 7.10 ★★★

(Anneaux de Boole) Soit $A$ un anneau dans lequel $x^2 = x$ pour tout $x$ . Démontrer que $x + x = 0$ pour tout $x$ , et que $A$ est commutatif. (Développer $(x+x)^2$ et $(x+y)^2$ .) Donner un exemple d’un tel anneau à partir de $\mathcal{P}(E)$ , en prenant la différence symétrique pour addition et l’intersection pour multiplication.

Solution

Solution de Exercice 7.10.

$x + x = (x + x)^2 = x^2 + x^2 + x^2 + x^2 = 4x^2 = 4x$ — donc $2x = 4x$ , d’où $2x = 0$ , c’est-à-dire $x + x = 0$ (chaque élément est son propre opposé). Ensuite

x + y = (x+y)^2 = x^2 + xy + yx + y^2 = x + xy + yx + y ,

donc $xy + yx = 0$ , c’est-à-dire $xy = -yx = yx$ (en utilisant $-z = z$ ). Ainsi $A$ est commutatif.

Exemple : sur $\mathcal{P}(E)$ , posons $A + B = (A \cup B) \setminus (A \cap B)$ (différence symétrique) et $A \times B = A \cap B$ . On vérifie : $(\mathcal{P}(E), +)$ est un groupe abélien de neutre $\emptyset$ , chaque partie étant son propre opposé ; $\cap$ est associative, commutative, de neutre $E$ ; la distributivité $A \cap (B + C) = (A \cap B) + (A \cap C)$ a lieu (un élément appartient au membre de gauche si et seulement s’il est dans $A$ et dans exactement l’un des deux ensembles $B, C$ ). Et $A \cap A = A$ : tout élément est idempotent, comme voulu.

Exercice 7.11 ★★★

Soit $G$ un groupe dans lequel, pour un certain $n \geq 1$ fixé, $(xy)^n = x^n y^n$ , $(xy)^{n+1} = x^{n+1}y^{n+1}$ et $(xy)^{n+2} = x^{n+2}y^{n+2}$ pour tous $x, y$ . Démontrer que $G$ est abélien. (À partir des trois identités, établir d’abord $y^n x = x y^n$ , puis $y^{n+1} x = x y^{n+1}$ , et conclure.)

Solution

Solution de Exercice 7.11.

Écrivons l’hypothèse pour $n$ et $n+1$ :

(xy)^{n+1} = x^{n+1} y^{n+1} \quad\text{et}\quad (xy)^{n+1} = (xy)(xy)^n = xy\,x^n y^n .

En identifiant : $x^{n+1} y^{n+1} = x\,y\,x^n\,y^n$ ; on simplifie par $x$ à gauche et par $y^n$ à droite : $x^n y = y x^n$ . Le même calcul un cran plus haut ( $n+1$ et $n+2$ ) donne $x^{n+1} y = y x^{n+1}$ . Alors

y\,x^{n+1} = x^{n+1} y = x\,(x^n y) = x\,y\,x^n ,

et en simplifiant par $x^n$ à droite dans $y x \cdot x^n = x y \cdot x^n$ : $yx = xy$ . Donc $G$ est abélien.

Exercice 7.12 ★★

Déterminer tous les morphismes de groupes de $(\Z, +)$ dans $(\Z, +)$ .
Démontrer que le seul morphisme de groupes de $(\Q, +)$ dans $(\Z, +)$ est le morphisme nul. (Pour $x \in \Q$ et $n \in \N^*$ , comparer $f(x)$ et $n\,f(x/n)$ .)

Solution

Solution de Exercice 7.12.

Soit $f \colon \Z \to \Z$ additive et $a = f(1)$ . Par récurrence, $f(k) = ka$ pour $k \in \N$ , et $f(-k) = -f(k) = -ka$ : $f$ est donc la multiplication par $a$ . Réciproquement, toute application $k \mapsto ak$ est un morphisme : les morphismes $(\Z,+) \to (\Z,+)$ sont exactement les multiplications par un entier fixé.
Soit $f \colon \Q \to \Z$ un morphisme, $x \in \Q$ et $n \in \N^*$ . Alors

$f(x) = f\Bigl(\underbrace{\tfrac xn + \dots + \tfrac xn}_{n}\Bigr) = n\,f\Bigl(\frac xn\Bigr) ,$

donc l’entier $f(x)$ est divisible par tout $n \geq 1$ . Le seul entier de ce type est $0$ : $f \equiv 0$ .

7.6 Problème : le groupe symétrique et le taquin

Problème 7.1

Le groupe $\mathfrak S_n$ des permutations de $\intint1n$ est le plus ancien groupe des mathématiques, et il reste le plus instructif. Ce problème en construit la théorie de A à Z — cycles, engendrement par les transpositions, le morphisme signature $\varepsilon \colon \mathfrak S_n \to \{\pm1\}$ (dont l’existence n’a rien d’évident), et le groupe alterné $\mathfrak A_n$ engendré par les $3$ -cycles — puis la met à profit sur un casse-tête classique : dans le jeu de taquin $3 \times 3$ , aucune suite de coups ne peut échanger deux pièces en laissant tout le reste en place. Les permutations agissent sur $\intint1n$ ; le produit $\sigma\tau$ signifie « appliquer $\tau$ d’abord » ; $[\,v_1, \dots, v_n]$ désigne la permutation envoyant $i$ sur $v_i$ .

Partie I — Cycles et transpositions.

Justifier $\abs{\mathfrak S_n} = n!$ (Théorème 2.12). Dans $\mathfrak S_3$ , calculer les deux produits de $\sigma = [2, 3, 1]$ et $\tau = [1, 3, 2]$ , et en conclure que $\mathfrak S_3$ n’est pas abélien.
Un $k$ -cycle $(a_1\ a_2\ \dots\ a_k)$ ( $k \geq 2$ , les $a_i$ deux à deux distincts) envoie $a_1 \mapsto a_2 \mapsto \dots \mapsto a_k \mapsto a_1$ et fixe tout le reste ; son support est $\{a_1, \dots, a_k\}$ . Démontrer que deux cycles de supports disjoints commutent.
Démontrer que tout $\sigma \in \mathfrak S_n$ est un produit de cycles à supports deux à deux disjoints, et que cette décomposition est unique à l’ordre des facteurs près. (Considérer, pour chaque $i$ , la suite $i, \sigma(i), \sigma^2(i), \dots$ : elle revient nécessairement à $i$ ; les orbites obtenues forment une partition de $\intint1n$ , et $\sigma$ agit sur chacune comme un cycle.)
Décomposer $\sigma = [4, 1, 5, 2, 3, 7, 8, 6] \in \mathfrak S_8$ en cycles disjoints. En définissant l’ordre de $\sigma$ comme dans la Définition 7.14, démontrer que l’ordre d’un produit de cycles disjoints est le PPCM de leurs longueurs, et calculer l’ordre de ce $\sigma$ .
Démontrer l’identité télescopique

$(a_1\ a_2\ \dots\ a_k) = (a_1\ a_k)(a_1\ a_{k-1})\cdots(a_1\ a_2) ,$

et en conclure que toute permutation est un produit de transpositions. Écrire le $\sigma$ de la question 4 sous cette forme.
Montrer de plus que les transpositions adjacentes $(i\ \ i{+}1)$ suffisent : pour $a < b$ ,

$(a\ b) = (a\ \ a{+}1)(a{+}1\ \ a{+}2)\cdots(b{-}1\ \ b) \cdots(a{+}1\ \ a{+}2)(a\ \ a{+}1),$

soit un produit de $2(b - a) - 1$ transpositions adjacentes — un nombre impair (cette parité servira deux fois plus bas).

Partie II — La signature existe. Pour $\sigma \in \mathfrak S_n$ , soit

N(\sigma) = \#\bigl\{(i, j) : i < j,\ \sigma(i) > \sigma(j)\bigr\}

son nombre d’inversions, et posons $\varepsilon(\sigma) = (-1)^{N(\sigma)}$ .

Calculer $N$ et $\varepsilon$ pour l’identité, pour une transposition $(i\ \ i{+}1)$ , et pour $[2, 3, 1]$ .
Démontrer que pour tout $\sigma$ et toute transposition adjacente $\tau = (i\ \ i{+}1)$ : $N(\sigma\tau) = N(\sigma) \pm 1$ . (Composer à droite par $\tau$ échange les valeurs situées aux positions $i$ et $i + 1$ ; exactement une paire change de statut d’inversion.)
En déduire, à l’aide de la question 6, que pour toute transposition $\tau$ , $\varepsilon(\sigma\tau) = -\varepsilon(\sigma)$ ; conclure que si $\sigma$ est un produit de $p$ transpositions, alors $\varepsilon(\sigma) = (-1)^p$ — en particulier la parité de $p$ ne dépend que de $\sigma$ , et non de la factorisation choisie — et que $\varepsilon \colon \mathfrak S_n \to \{\pm 1\}$ est un morphisme de groupes.
Montrer qu’un $k$ -cycle a pour signature $(-1)^{k-1}$ , et qu’en général $\varepsilon(\sigma) = (-1)^{n - c(\sigma)}$ , où $c(\sigma)$ est le nombre d’orbites de $\sigma$ (points fixes compris).
Le groupe alterné est $\mathfrak A_n = \ker\varepsilon$ . Justifier que c’est un sous-groupe, et démontrer $\abs{\mathfrak A_n} = \frac{n!}2$ pour $n \geq 2$ . (Fixer une transposition $\tau_0$ et considérer $\sigma \mapsto \sigma\tau_0$ .)
Vérification de cohérence sur $\sigma = [4, 1, 5, 2, 3, 7, 8, 6]$ : calculer $\varepsilon(\sigma)$ de trois façons — en comptant les inversions, à partir du type de cycles via la question 10, et à partir du nombre de transpositions de la question 5.

Partie III — $\mathfrak A_n$ est engendré par les $3$ -cycles.

Soient $a, b, c, d$ deux à deux distincts. Vérifier les deux identités

$(a\ b)(a\ c) = (a\ c\ b), \qquad (a\ b)(c\ d) = (a\ c\ b)(a\ c\ d) .$
Démontrer que pour $n \geq 3$ , tout élément de $\mathfrak A_n$ est un produit de $3$ -cycles. (Une permutation paire est un produit d’un nombre pair de transpositions ; les absorber deux par deux.)
Écrire explicitement $(1\ 2)(3\ 4)$ et le $5$ -cycle $(1\ 2\ 3\ 4\ 5)$ comme produits de $3$ -cycles.
Démontrer la formule de conjugaison : pour tout $\sigma \in \mathfrak S_n$ ,

$\sigma\,(a_1\ \dots\ a_k)\,\sigma^{-1} = \bigl(\sigma(a_1)\ \dots\ \sigma(a_k)\bigr) .$

Partie IV — Le taquin. Les pièces $1, \dots, 8$ coulissent dans un cadre $3 \times 3$ comportant une case vide ; un coup fait glisser dans la case vide une pièce qui lui est adjacente. Numérotons les cases $1, \dots, 9$ (ligne par ligne ; la position résolue place la pièce $i$ dans la case $i$ et la case vide en case $9$ ). Traitons la case vide comme une neuvième pièce : une position est alors une permutation $\sigma \in \mathfrak S_9$ (la pièce $\sigma(i)$ occupe la case $i$ ).

Montrer qu’un coup remplace $\sigma$ par $\sigma \circ \tau$ , où $\tau$ est la transposition des deux cases concernées ; en déduire que chaque coup change le signe de $\varepsilon(\sigma)$ .
Soit $d(\sigma)$ la distance de Manhattan (lignes plus colonnes) entre la case qu’occupe la case vide et sa case d’origine $9$ . Montrer que chaque coup fait varier $d$ de $\pm1$ , de sorte que chaque coup change aussi le signe de $(-1)^{d(\sigma)}$ . En conclure que

$I(\sigma) = \varepsilon(\sigma)\cdot(-1)^{d(\sigma)}$

est invariant par tout coup.
Démontrer l’impossibilité classique du taquin : la position qui échange les pièces $7$ et $8$ en laissant tout le reste (case vide comprise) en place ne peut pas être atteinte à partir de la position résolue.
On admet la réciproque (sa démonstration est une récurrence instructive mais longue) : toute position vérifiant $I = +1$ est atteignable. En déduire qu’exactement la moitié des $8!$ positions ayant la case vide à sa place sont solubles, soit $\frac{8!}2 = 20\,160$ .
Déduire de la question 20 que les dispositions de pièces atteignables ayant la case vide à sa place forment exactement le sous-groupe $\mathfrak A_8 \leq \mathfrak S_8$ .
Applications de l’invariant : peut-on atteindre (a) la position où les pièces $1, 2, 3$ sont permutées circulairement et où tout le reste, case vide comprise, est à sa place ? (b) la position où la pièce $5$ et la case vide ont échangé leurs places, toutes les autres pièces étant à la leur ? Justifier les deux réponses à l’aide de $I$ .

Partie V — Synthèse.

Démontrer que pour $n \geq 3$ , les seuls morphismes de groupes $f \colon \mathfrak S_n \to \{\pm 1\}$ sont le morphisme constant et $\varepsilon$ . (À l’aide de la question 16 et de la commutativité de $\{\pm1\}$ , montrer que $f$ prend la même valeur sur toutes les transpositions.)
Où exactement le problème a-t-il utilisé : (i) la notion de morphisme et la Proposition 7.11 ; (ii) les principes de dénombrement du Chapitre 2 ; (iii) le problème de bonne définition que les questions 8 et 9 résolvent ? Une phrase pour chacun.
Synthèse, en un court paragraphe : une seule fonction de parité, dont la bonne définition est démontrée une fois pour toutes, organise simultanément la structure interne de $\mathfrak S_n$ (le sous-groupe $\mathfrak A_n$ ), tranche un casse-tête matériel et — via la formule $\det = \sum_\sigma \varepsilon(\sigma)\cdots$ — définira les déterminants au Chapitre 22. Commenter le schéma récurrent : les invariants transforment « essayer toutes les suites de coups » en un unique calcul.

Solution

Solution de Problème 7.1.

1. Une permutation est une bijection de $\intint1n$ , c’est-à-dire un arrangement des $n$ objets pris $n$ à $n$ : il y en a $n!$ (Théorème 2.12). Avec $\sigma = [2,3,1]$ , $\tau = [1,3,2]$ : $\sigma\tau$ envoie $1 \mapsto 1 \mapsto 2$ , $2 \mapsto 3 \mapsto 1$ , $3 \mapsto 2 \mapsto 3$ : $\sigma\tau = [2,1,3]$ ; et $\tau\sigma$ envoie $1 \mapsto 2 \mapsto 3$ , $2 \mapsto 3 \mapsto 2$ , $3 \mapsto 1 \mapsto 1$ : $\tau\sigma = [3,2,1] \neq \sigma\tau$ .

2. Soient $\gamma, \gamma'$ de supports disjoints $S, S'$ . Pour $x \in S$ : $\gamma'(x) = x$ et $\gamma(x) \in S$ , donc $\gamma\gamma'(x) = \gamma(x) = \gamma'\gamma(x)$ . Symétriquement pour $x \in S'$ ; et les deux membres fixent tout $x \notin S \cup S'$ . Donc $\gamma\gamma' = \gamma'\gamma$ .

3. Pour $i \in \intint1n$ , les valeurs $i, \sigma(i), \sigma^2(i), \dots$ vivent dans un ensemble fini, donc $\sigma^a(i) = \sigma^b(i)$ pour certains $a < b$ ; l’injectivité donne $\sigma^{b-a}(i) = i$ : la suite revient à $i$ . Appelons orbite de $i$ l’ensemble $\{i, \sigma(i), \dots, \sigma^{k-1}(i)\}$ , où $k \geq 1$ est minimal tel que $\sigma^k(i) = i$ . Deux orbites qui se rencontrent en un point coïncident (chacune est l’ensemble des images successives de ce point par $\sigma$ ), donc les orbites forment une partition de $\intint1n$ ; $\sigma$ agit sur chaque orbite de taille $k \geq 2$ comme le $k$ -cycle $(i\ \sigma(i)\ \cdots\ \sigma^{k-1}(i))$ et fixe les singletons. Le produit de ces cycles disjoints coïncide partout avec $\sigma$ . Unicité : dans toute décomposition en cycles disjoints, le cycle passant par $i$ ne peut être que $(i\ \sigma(i)\ \cdots)$ — les cycles sont forcés d’être les orbites munies de l’action induite.

4. En suivant les orbites : $1 \to 4 \to 2 \to 1$ , $3 \to 5 \to 3$ , $6 \to 7 \to 8 \to 6$ :

\sigma = (1\ 4\ 2)(3\ 5)(6\ 7\ 8) .

Si $\sigma = \gamma_1\cdots\gamma_r$ avec des cycles disjoints de longueurs $k_1, \dots, k_r$ , la commutation (question 2) donne $\sigma^m = \gamma_1^m\cdots\gamma_r^m$ , et comme les supports sont disjoints, $\sigma^m = \mathrm{id}$ si et seulement si chaque $\gamma_i^m = \mathrm{id}$ , si et seulement si $k_i \mid m$ pour tout $i$ (un $k$ -cycle est d’ordre $k$ : $\gamma^m$ envoie $a_1$ sur $a_{1 + (m \bmod k)}$ ). Le plus petit tel $m$ est $\operatorname{lcm}(k_1, \dots, k_r)$ . Ici : $\operatorname{lcm}(3, 2, 3) = 6$ .

5. Appliquons le membre de droite à chaque point, en commençant par le facteur le plus à droite. $a_1 \mapsto a_2$ par $(a_1\ a_2)$ , puis tous les facteurs suivants fixent $a_2$ : au total $a_1 \mapsto a_2$ . Pour $2 \leq i < k$ : $a_i$ n’est pas touché jusqu’à ce que $(a_1\ a_i)$ l’envoie sur $a_1$ , et le facteur immédiatement suivant $(a_1\ a_{i+1})$ envoie $a_1$ sur $a_{i+1}$ , après quoi plus rien ne le bouge : au total $a_i \mapsto a_{i+1}$ . Enfin $a_k$ est fixé par tous les facteurs sauf le plus à gauche, qui l’envoie sur $a_1$ . C’est exactement le cycle. Comme toute permutation est un produit de cycles (question 3), c’est un produit de transpositions. Pour le $\sigma$ de la question 4 :

\sigma = (1\ 2)(1\ 4)\;(3\ 5)\;(6\ 8)(6\ 7),

soit cinq transpositions.

6. Récurrence sur $b - a$ . Pour $b = a + 1$ l’identité est triviale ( $1 = 2\cdot1 - 1$ facteur). Pour $b > a + 1$ , on vérifie directement que $(a\ b) = (a\ \ a{+}1)\,(a{+}1\ \ b)\,(a\ \ a{+}1)$ : le membre de droite envoie $a \mapsto a{+}1 \mapsto b \mapsto b$ , $b \mapsto b \mapsto a{+}1 \mapsto a$ , $a{+}1 \mapsto a \mapsto a \mapsto a{+}1$ , et fixe le reste. Par récurrence, $(a{+}1\ \ b)$ est un produit palindromique de $2(b - a - 1) - 1$ transpositions adjacentes, donc $(a\ b)$ en est un de $2(b - a) - 1$ : un nombre impair.

7. $N(\mathrm{id}) = 0$ , $\varepsilon = +1$ . Pour $(i\ \ i{+}1)$ , la seule paire inversée est $(i, i+1)$ : $N = 1$ , $\varepsilon = -1$ . Pour $[2, 3, 1]$ : les paires inversées sont $(1, 3)$ (valeurs $2 > 1$ ) et $(2, 3)$ (valeurs $3 > 1$ ) : $N = 2$ , $\varepsilon = +1$ .

8. Les listes de valeurs de $\sigma$ et de $\sigma\tau$ ne diffèrent que par l’échange des positions $i$ et $i + 1$ . Pour une paire de positions ne faisant intervenir ni $i$ ni $i+1$ , rien ne change. Pour $k < i$ , les deux paires $(k, i)$ et $(k, i+1)$ échangent leurs statuts d’inversion (les deux mêmes valeurs sont comparées à $\sigma(k)$ , dans l’ordre inverse des positions) : leur contribution totale est inchangée ; de même pour $k > i + 1$ . La seule paire restante, $(i, i+1)$ , change de statut. D’où $N(\sigma\tau) = N(\sigma) \pm 1$ .

9. Soit $\tau = (a\ b)$ une transposition quelconque : par la question 6, c’est un produit d’un nombre impair de transpositions adjacentes, donc la multiplication à droite par $\tau$ modifie $N$ d’un total impair (question 8, appliquée de façon répétée) : $\varepsilon(\sigma \tau) = -\varepsilon(\sigma)$ . Maintenant, si $\sigma = \tau_1\cdots \tau_p$ (des transpositions), construisons-le à partir de l’identité par $p$ multiplications à droite : $\varepsilon(\sigma) = (-1)^p\varepsilon(\mathrm{id}) = (-1)^p$ . Comme $\varepsilon(\sigma)$ est défini par les inversions — indépendamment de toute factorisation — la parité de $p$ est un invariant de $\sigma$ . Morphisme : en écrivant $\sigma$ avec $p$ transpositions et $\sigma'$ avec $q$ , $\sigma\sigma'$ en utilise $p + q$ : $\varepsilon(\sigma\sigma') = (-1)^{p+q} = \varepsilon(\sigma)\varepsilon(\sigma')$ .

10. Un $k$ -cycle est un produit de $k - 1$ transpositions (question 5) : $\varepsilon = (-1)^{k-1}$ . Pour un $\sigma$ général d’orbites de tailles $k_1, \dots, k_r$ ( $k_i \geq 2$ ) plus $f$ points fixes, on a $c(\sigma) = r + f$ et $n = k_1 + \dots + k_r + f$ , donc

\varepsilon(\sigma) = \prod_{i=1}^r (-1)^{k_i - 1} = (-1)^{\sum_i k_i - r} = (-1)^{n - f - r} = (-1)^{n - c(\sigma)} .

11. $\mathfrak A_n = \ker\varepsilon$ est un sous-groupe, en tant que noyau d’un morphisme (Définition 7.10). Fixons une transposition $\tau_0$ (il en existe pour $n \geq 2$ ). L’application $\sigma \mapsto \sigma\tau_0$ est une bijection de $\mathfrak S_n$ (elle est sa propre réciproque) qui échange $\mathfrak A_n$ et l’ensemble des permutations impaires (question 9). Ces deux ensembles forment une partition de $\mathfrak S_n$ et ont même cardinal : $\abs{\mathfrak A_n} = \frac{n!}2$ .

12. Inversions de $[4, 1, 5, 2, 3, 7, 8, 6]$ : la valeur $4$ domine $1, 2, 3$ : trois ; la valeur $5$ domine $2, 3$ : deux ; la valeur $7$ domine $6$ : une ; la valeur $8$ domine $6$ : une. $N = 7$ , $\varepsilon = -1$ . Type de cycles : $c = 3$ orbites, $n = 8$ : $\varepsilon = (-1)^{8-3} = -1$ . Nombre de transpositions : cinq transpositions à la question 5 : $(-1)^5 = -1$ . Les trois calculs concordent.

13. $(a\ b)(a\ c)$ (le facteur le plus à droite d’abord) : $a \mapsto c \mapsto c$ ; $c \mapsto a \mapsto b$ ; $b \mapsto b \mapsto a$ : c’est le $3$ -cycle $(a\ c\ b)$ . Et $(a\ c\ b)(a\ c\ d)$ : $a \mapsto c \mapsto b$ ; $b \mapsto b \mapsto a$ ; $c \mapsto d \mapsto d$ ; $d \mapsto a \mapsto c$ : c’est $(a\ b)(c\ d)$ , comme annoncé.

14. Soit $\sigma \in \mathfrak A_n$ : par la question 9, $\sigma = \tau_1\cdots\tau_{2m}$ avec un nombre pair de transpositions. Groupons-les par paires consécutives $\tau_{2i-1}\tau_{2i}$ : si les deux sont égales, la paire est l’identité et disparaît ; si elles ont exactement un point commun, la première identité de la question 13 écrit la paire comme un unique $3$ -cycle ; si elles sont disjointes, la seconde identité l’écrit comme deux $3$ -cycles. Ainsi $\sigma$ est un produit de $3$ -cycles (ou l’identité, produit vide — et, pour $n \geq 3$ , également $(1\ 2\ 3)^3$ ).

15. $(1\ 2)(3\ 4) = (1\ 3\ 2)(1\ 3\ 4)$ (question 13 avec $a{=}1, b{=}2, c{=}3, d{=}4$ ). Pour le $5$ -cycle : par la question 5, $(1\ 2\ 3\ 4\ 5) = (1\ 5)(1\ 4)(1\ 3)(1\ 2)$ , et en appariant : $(1\ 5)(1\ 4) = (1\ 4\ 5)$ , $(1\ 3)(1\ 2) = (1\ 2\ 3)$ :

(1\ 2\ 3\ 4\ 5) = (1\ 4\ 5)(1\ 2\ 3) .

(Vérification sur $3$ : $(1\ 2\ 3)$ envoie $3 \to 1$ , puis $(1\ 4\ 5)$ envoie $1 \to 4$ : au total $3 \to 4$ , ce qui est correct.)

16. Appliquons les deux membres à un point quelconque. Pour $i = \sigma(a_j)$ : le membre de gauche donne $\sigma\bigl((a_1\ \dots\ a_k)(a_j)\bigr) = \sigma(a_{j+1})$ (indices modulo $k$ ), ce qui est précisément l’image de $\sigma(a_j)$ par le membre de droite. Pour $i$ qui n’est pas de cette forme : $\sigma^{-1}(i)$ est hors du support, donc le membre de gauche fixe $i$ , et le membre de droite aussi. Égalité partout.

17. Faire glisser la pièce de la case $c'$ dans la case vide $c$ échange les contenus des cases $c$ et $c'$ (la pièce $9$ , le vide, va en $c'$ ). Si la pièce $\sigma(i)$ occupait la case $i$ , la nouvelle position est $\sigma' = \sigma \circ (c\ c')$ : mêmes contenus, sauf que les cases $c, c'$ portent chacune l’ancien contenu de l’autre. Par la question 9, $\varepsilon(\sigma') = -\varepsilon(\sigma)$ .

18. Un coup envoie la case vide sur une case adjacente : sa ligne ou sa colonne change d’exactement $1$ , donc la distance de Manhattan $d$ à la case $9$ varie de $\pm1$ , et $(-1)^d$ change de signe. Puisque chaque coup change le signe de $\varepsilon(\sigma)$ et celui de $(-1)^{d(\sigma)}$ , leur produit $I(\sigma)$ est inchangé par tout coup : c’est un invariant.

19. La position résolue a $\varepsilon = +1$ , $d = 0$ : $I = +1$ . La position visée (pièces $7, 8$ échangées, vide à sa place) est la transposition des contenus des cases $7$ et $8$ : $\varepsilon = -1$ , $d = 0$ : $I = -1$ . Comme $I$ est invariant et que les deux valeurs diffèrent, aucune suite de coups ne les relie.

20. Une position ayant le vide à sa place est une permutation des $8$ pièces parmi les cases $1, \dots, 8$ , c’est-à-dire un élément de $\mathfrak S_8$ ; elle vérifie $d = 0$ , donc $I = \varepsilon(\sigma)$ . Être atteignable impose $I = +1$ , c’est-à-dire $\sigma \in \mathfrak A_8$ ; la réciproque admise dit que tout $\mathfrak A_8$ est atteint. Dénombrement : $\abs{\mathfrak A_8} = \frac{8!}2 = 20\,160$ (question 11).

21. Par la question 20, les dispositions atteignables avec le vide à sa place forment exactement $\mathfrak A_8$ — en particulier un sous-groupe de $\mathfrak S_8$ : composer deux mélanges solubles, ou inverser l’un d’eux, reste soluble, ce qui est loin d’être évident par un raisonnement direct sur le taquin.

22. (a) Un $3$ -cycle de pièces avec le vide à sa place : $\varepsilon = +1$ (question 10), $d = 0$ , donc $I = +1$ : atteignable (par la réciproque admise) — on peut permuter circulairement trois pièces. (b) Pièce $5$ et vide échangés : la position est la transposition des contenus des cases $5$ et $9$ , donc $\varepsilon = -1$ ; le vide se trouve au centre, à distance de Manhattan $d = 2$ de sa case d’origine, donc $(-1)^d = +1$ et $I = -1$ : inatteignable. On ne peut pas simplement « garer le vide au milieu » en laissant les pièces par ailleurs rangées.

23. Soit $f \colon \mathfrak S_n \to \{\pm1\}$ un morphisme. Pour deux transpositions quelconques $\tau, \tau'$ , la question 16 fournit un $\sigma$ tel que $\sigma\tau\sigma^{-1} = \tau'$ (envoyer les deux points déplacés sur les deux autres ; $n \geq 3$ garantit la place nécessaire, même si $n = 2$ est ici trivial). Alors $f(\tau') = f(\sigma)f(\tau)f(\sigma)^{-1} = f(\tau)$ puisque $\{\pm1\}$ est abélien : $f$ est constant sur les transpositions. Si cette constante vaut $+1$ , alors $f = 1$ sur tous les produits de transpositions, c’est-à-dire partout (question 5). Si elle vaut $-1$ , alors $f(\sigma) = (-1)^p = \varepsilon(\sigma)$ sur un produit de $p$ transpositions. Donc $f \in \{1, \varepsilon\}$ .

24. (i) La propriété de morphisme de $\varepsilon$ et la machinerie du noyau ont donné à $\mathfrak A_n$ sa structure de sous-groupe et son cardinal, et un raisonnement du type Proposition 7.11 traverse les questions 11 et 21. (ii) Dénombrement : $\abs{\mathfrak S_n} = n!$ , l’argument de moitié de la question 11 et le compte $20\,160$ de la question 20 sont le Chapitre 2 à l’œuvre. (iii) Les questions 8 et 9 résolvent un véritable problème de bonne définition — « la parité du nombre de transpositions » présuppose que cette parité ne dépend pas de la factorisation, exactement comme les opérations de $\Z/n\Z$ exigeaient l’indépendance vis-à-vis des représentants dans la Définition 7.24.

25. La signature est un unique calcul à valeurs dans $\{\pm1\}$ , dont on a démontré une fois pour toutes qu’il est bien défini, et il remplit trois fonctions à la fois : à l’intérieur, il coupe $\mathfrak S_n$ en deux et isole $\mathfrak A_n$ avec ses générateurs $3$ -cycles ; à l’extérieur, il tranche en une ligne une question (« ces deux pièces peuvent-elles être échangées ? ») qu’une recherche naïve ne pourrait jamais régler, puisqu’aucune liste finie de suites de coups infructueuses ne démontre l’impossibilité ; et structurellement, c’est le moteur à signes alternés à l’intérieur de la formule $\det A = \sum_\sigma \varepsilon(\sigma)\, a_{1\sigma(1)}\cdots a_{n\sigma(n)}$ du Chapitre 22. Le schéma — trouver une quantité conservée par tout coup élémentaire, la calculer au départ et à l’arrivée — est l’arme standard du mathématicien contre les questions « est-ce possible ? », et il reviendra chaque fois qu’un groupe agira sur un ensemble d’états.

7.1 Lois de composition

7.2 Groupes

7.3 Anneaux et corps

7.4 L’anneau Z/nZ\Z/n\ZZ/nZ

7.5 Exercices

7.6 Problème : le groupe symétrique et le taquin

7.4 L’anneau $\Z/n\Z$