Mathématiques universitaires — Licence 2 · Bachelor Year 2

1Ensembles et structures

Ce chapitre d’ouverture affûte les fondations posées dans le volume de première année pour en faire des outils de travail courants : le calcul des ensembles et des quotients, la comparaison des ensembles infinis (dénombrabilité, Cantor–Bernstein), et la théorie structurelle des groupes et des anneaux — le théorème de Lagrange, le groupe symétrique et sa signature, les idéaux et le théorème des restes chinois. Tout ici sert sans relâche dans la suite du livre : la signature construit le déterminant (Chapitre 2), les anneaux quotients font marcher l’arithmétique, et la dénombrabilité sous-tend à la fois la topologie et les probabilités.

1.1 Ensembles, applications, quotients

Nous utilisons librement le langage des ensembles, des applications et des relations d’équivalence et d’ordre mis en place dans le volume de première année. Deux améliorations méritent un énoncé en bonne et due forme.

Proposition 1.1 (Images et images réciproques de familles)

Soient $f \colon E \to F$ et $(A_i)_{i \in I}$ , $(B_j)_{j \in J}$ des familles de parties de $E$ , resp. $F$ . Alors

f^{-1}\Bigl(\bigcup_j B_j\Bigr) = \bigcup_j f^{-1}(B_j), \qquad f^{-1}\Bigl(\bigcap_j B_j\Bigr) = \bigcap_j f^{-1}(B_j), \qquad f^{-1}(F \setminus B) = E \setminus f^{-1}(B),

f\Bigl(\bigcup_i A_i\Bigr) = \bigcup_i f(A_i), \qquad f\Bigl(\bigcap_i A_i\Bigr) \subseteq \bigcap_i f(A_i) \quad (\text{égalité pour } f \text{ injective}).

Démonstration. Chaque identité s’obtient en déroulant les définitions ; par exemple $x \in f^{-1}(\bigcap B_j) \iff f(x) \in B_j$ pour tout $j$ $\iff x \in f^{-1}(B_j)$ pour tout $j$ . Les identités sur les images et l’échec de l’égalité dans le cas de l’intersection (avec la correction par injectivité) ont été démontrés dans le volume de première année pour deux ensembles ; les arguments sont identiques pour des familles. ∎

Exemple 1.2 (Où l’inclusion des images est stricte)

Prenons $f \colon \R \to \R$ , $f(x) = x^2$ , avec $A_1 = \intcc{-1}{0}$ et $A_2 = \intcc{0}{1}$ . Alors

f(A_1 \cap A_2) = f(\{0\}) = \{0\}, \qquad f(A_1) \cap f(A_2) = \intcc{0}{1} \cap \intcc{0}{1} = \intcc{0}{1} :

l’inclusion de la Proposition 1.1 est aussi stricte que possible — les deux antécédents $\pm x$ d’une valeur commune vivent dans des $A_i$ différents. L’injectivité est précisément ce qui interdit cette séparation, et c’est pourquoi les images réciproques (qui ne fusionnent jamais de points) vérifient les quatre identités sans condition, tandis que les images perdent celle sur les intersections. Règle empirique pour tout le livre : faites passer les images réciproques à travers les opérations ensemblistes librement ; maniez les images avec précaution.

Définition 1.3 (Ensemble quotient)

Soit $\mathcal{R}$ une relation d’équivalence sur $E$ . L’ensemble quotient $E/\mathcal{R}$ est l’ensemble des classes d’équivalence ; la surjection $\pi \colon E \to E/\mathcal{R}$ , $x \mapsto \mathrm{cl}(x)$ , est la projection canonique.

Propriété universelle (factorisation) : si $f \colon E \to F$ est compatible avec $\mathcal{R}$ (c.-à-d. $x \mathbin{\mathcal{R}} y \implies f(x) = f(y)$ ), il existe une unique application $\overline f \colon E/\mathcal{R} \to F$ telle que $f = \overline f \circ \pi$ .

Démonstration de la propriété universelle. Unicité : la condition $f = \overline f \circ \pi$ s’écrit

\overline f\bigl(\mathrm{cl}(x)\bigr) = f(x) \qquad (x \in E),

et comme $\pi$ est surjective, tout élément de $E/\mathcal{R}$ est un certain $\mathrm{cl}(x)$ : les valeurs de $\overline f$ sont toutes imposées. Existence : on prend la formule affichée comme définition de $\overline f$ ; elle est sans ambiguïté précisément grâce à la compatibilité — si $\mathrm{cl}(x) = \mathrm{cl}(y)$ , alors $x \mathbin{\mathcal{R}} y$ , donc $f(x) = f(y)$ et les deux valeurs candidates coïncident — et elle factorise $f$ par construction. Noter le partage des tâches : la surjectivité de $\pi$ donne l’unicité, la compatibilité donne l’existence. ∎

Exemple 1.4

$\Z/n\Z$ est le quotient de $\Z$ par la congruence modulo $n$ ; les vérifications de bonne définition du volume de première année étaient des cas particuliers de la propriété universelle. Les quotients transforment les « constructions compatibles sur les représentants » en applications véritables — nous nous en servons constamment ci-dessous.

1.2 Dénombrabilité et cardinalité

Définition 1.5 (Équipotence, dénombrabilité)

Deux ensembles sont équipotents lorsqu’une bijection les relie. Un ensemble est dénombrable lorsqu’il est équipotent à $\N$ (certains auteurs incluent les ensembles finis ; nous disons au plus dénombrable pour « fini ou dénombrable »).

Proposition 1.6 (Propriétés de stabilité)

Toute partie infinie de $\N$ est dénombrable ; un ensemble est au plus dénombrable si et seulement s’il s’injecte dans $\N$ si et seulement s’il est vide ou image surjective de $\N$ .
$\N \times \N$ est dénombrable ; un produit de deux ensembles au plus dénombrables est au plus dénombrable.
Une union au plus dénombrable d’ensembles au plus dénombrables est au plus dénombrable.
$\Z$ et $\Q$ sont dénombrables.

Démonstration. (1) Énumérons une partie infinie $A \subseteq \N$ par minima successifs : $a_0 = \min A$ , $a_{k+1} = \min\,(A \setminus \{a_0, \dots, a_k\})$ (non vide car $A$ est infini) ; l’application $k \mapsto a_k$ est strictement croissante, injective, et surjective sur $A$ (tout $a \in A$ ne dépasse qu’un nombre fini d’éléments de $A$ , donc il est atteint). Si $E$ s’injecte dans $\N$ via $\varphi$ , alors $E$ est équipotent à $\varphi(E) \subseteq \N$ : fini ou dénombrable. Si $s \colon \N \to E$ est surjective, alors $x \mapsto \min s^{-1}(\{x\})$ injecte $E$ dans $\N$ .

(2) L’application $(p, q) \mapsto 2^p(2q + 1) - 1$ est une bijection $\N^2 \to \N$ (tout entier strictement positif possède une unique décomposition pair–impair $2^p m$ avec $m$ impair, par unicité de la factorisation). Produits : composer les injections.

(3) Étant donné des ensembles $E_n$ munis de surjections $s_n \colon \N \to E_n$ (sans dommage lorsque l’un des $E_n$ est fini : on répète des valeurs), l’application $(n, k) \mapsto s_n(k)$ est une surjection du dénombrable $\N^2$ sur $\bigcup E_n$ .

(4) $\Z = \N \cup (-\N^*)$ : union dénombrable. $\Q$ est image surjective de $\Z \times \N^*$ (l’application fraction), donc au plus dénombrable, et infini. ∎

Exemple 1.7 (Une fonction de couplage, calculée)

La bijection $(p, q) \mapsto 2^p(2q + 1) - 1$ de la démonstration mérite d’être vue à l’œuvre. Ses premières valeurs :

\begin{array}{c|ccccc} & q = 0 & q = 1 & q = 2 & q = 3 & q = 4\\ \hline p = 0 & 0 & 2 & 4 & 6 & 8\\ p = 1 & 1 & 5 & 9 & 13 & 17\\ p = 2 & 3 & 11 & 19 & 27 & 35\\ p = 3 & 7 & 23 & 39 & 55 & 71 \end{array}

La ligne $p$ regroupe les entiers $n$ pour lesquels $n + 1$ est exactement divisible par $2^p$ : tout entier naturel apparaît exactement une fois. Le décodage est aussi explicite que le codage : pour $n = 43$ , on factorise $n + 1 = 44 = 2^2\cdot 11 = 2^2(2\cdot5 + 1)$ , d’où $(p, q) = (2, 5)$ . L’idée à retenir : les démonstrations de dénombrabilité sont souvent des algorithmes déguisés — ici, « mettre les puissances de deux en facteur ».

Exemple 1.8 (Les nombres algébriques sont dénombrables)

Un nombre complexe est algébrique lorsqu’il annule un polynôme non nul à coefficients rationnels. L’ensemble $\overline\Q$ des nombres algébriques est dénombrable : les polynômes de degré $\leq d$ sur $\Q$ s’injectent dans $\Q^{d+1}$ , un produit fini d’ensembles dénombrables (Proposition 1.6 (2)) ; l’union sur $d$ énumère les polynômes rationnels non nuls en $P_0, P_1, P_2, \dots$ ; chaque $P_k$ a un nombre fini de racines ; et

\overline\Q = \bigcup_{k \in \N}\ \{\text{racines de } P_k\}

est une union dénombrable d’ensembles finis (Proposition 1.6 (3)), infinie car elle contient $\Q$ . Combiné avec la non-dénombrabilité de $\R$ (Théorème 1.9 ci-dessous), cela prouve — sans en exhiber un seul — que les nombres transcendants existent et forment une majorité non dénombrable : l’argument de comptage de Cantor de 1874, l’existence par la seule cardinalité.

Théorème 1.9 (Cantor ; non-dénombrabilité de $\R$ )

Pour tout ensemble $E$ , il n’existe pas de surjection $E \to \mathcal{P}(E)$ .
$\R$ n’est pas dénombrable.

Démonstration. (1) a été démontré dans le volume de première année (l’ensemble diagonal $D = \{x : x \notin f(x)\}$ ).

(2) Supposons que $(x_n)_{n \in \N}$ énumère $\R$ . Construisons des segments emboîtés $I_0 \supseteq I_1 \supseteq \dots$ avec $\abs{I_n} = 3^{-n}$ et $x_n \notin I_n$ : on découpe le segment courant en trois tiers fermés ; au moins un tiers évite $x_n$ (un point rencontre au plus deux des trois). Le théorème des segments emboîtés (bornes adjacentes) fournit $\ell \in \bigcap_n I_n$ ; mais $\ell = x_N$ pour un certain $N$ , et $x_N \notin I_N$ : contradiction. ∎

Théorème 1.10 (Cantor–Bernstein)

Si $E$ s’injecte dans $F$ et $F$ s’injecte dans $E$ , alors $E$ et $F$ sont équipotents.

Démonstration. Soient $f \colon E \to F$ et $g \colon F \to E$ des injections. Pour chaque point (de $E$ ou de $F$ ), suivons sa chaîne d’ancêtres d’images réciproques successives, $x \mapsto g^{-1}(x) \mapsto f^{-1}(g^{-1}(x)) \mapsto \dots$ — chaque étape est définie tant que le point courant appartient à l’image de l’injection concernée, et est alors unique par injectivité. Trois sorts mutuellement exclusifs : la chaîne s’arrête en un point de $E \setminus g(F)$ (origine dans $E$ ), s’arrête en un point de $F \setminus f(E)$ (origine dans $F$ ), ou ne s’arrête jamais. Cela partitionne $E = E_E \cup E_F \cup E_\infty$ et $F = F_E \cup F_F \cup F_\infty$ selon l’origine.

Observons maintenant : $f$ envoie $E_E$ sur $F_E$ — la chaîne de $f(x)$ est la chaîne de $x$ précédée d’une étape, donc les origines coïncident ; et tout $y \in F_E$ possède une chaîne d’au moins une étape (son origine est dans $E$ ), donc $y = f(x)$ avec $x \in E_E$ . Le même argument donne des bijections $f \colon E_\infty \to F_\infty$ et $g \colon F_F \to E_F$ . En recollant,

h(x) = \begin{cases} f(x) & \text{si } x \in E_E \cup E_\infty,\\ g^{-1}(x) & \text{si } x \in E_F, \end{cases}

est une bijection de $E$ sur $F = F_E \cup F_\infty \cup F_F$ : elle est bijective par morceaux, et les trois morceaux d’arrivée sont disjoints. ∎

Exemple 1.11

$\intoo{0}{1}$ et $\intcc{0}{1}$ sont équipotents : l’identité injecte dans un sens, $x \mapsto \frac{x + 1}{3}$ dans l’autre ; le théorème fabrique la bijection (nécessairement discontinue). De même $\R$ , $\intoo{0}{1}$ (via des bijections de type $\tanh$ ) et $\mathcal{P}(\N)$ (développements binaires, Exercice 1.3) sont tous équipotents : « la puissance du continu ».

Exemple 1.12 (Le segment et le carré)

$\intcc{0}{1}$ et $\intcc{0}{1}^2$ sont équipotents — la dimension est invisible à la cardinalité. Une injection est triviale : $x \mapsto (x, 0)$ . Pour l’autre, on envoie $(x, y)$ sur le réel dont les chiffres décimaux entrelacent ceux de $x$ et $y$ ,

(0.x_1x_2x_3\dots,\ 0.y_1y_2y_3\dots) \;\longmapsto\; 0.x_1y_1x_2y_2x_3y_3\dots,

en choisissant pour chaque coordonnée le développement qui ne se termine pas par une suite infinie de $9$ : avec cette convention, les chiffres de l’image déterminent ceux de $x$ et de $y$ , donc l’application est injective (elle n’a pas besoin d’être surjective — les images n’ont, par exemple, jamais leurs chiffres de position impaire égaux à $9$ à partir d’un certain rang — et cela ne pose pas de problème). Le théorème de Cantor–Bernstein (Théorème 1.10) assemble une véritable bijection. La continuité, bien sûr, est sans espoir : une bijection continue entre les deux est impossible — les chapitres de topologie métrique expliquent pourquoi (la connexité distingue la droite du plan, Chapitre 4).

1.3 Groupes

Définition 1.13 (Sous-groupe engendré ; ordre)

Soit $G$ un groupe et $A \subseteq G$ . Le sous-groupe engendré par $A$ , noté $\langle A \rangle$ , est le plus petit sous-groupe contenant $A$ — concrètement, tous les produits finis d’éléments de $A$ et de leurs inverses. Un groupe est cyclique lorsqu’il est engendré par un seul élément : $\langle a\rangle = \{a^k : k \in \Z\}$ . L’ordre de $a \in G$ est $\operatorname{ord}(a) = \abs{\langle a \rangle}$ (éventuellement infini) ; lorsqu’il est fini, c’est le plus petit $n \geq 1$ tel que $a^n = e$ , et $a^k = e \iff \operatorname{ord}(a) \mid k$ .

Démonstration de la caractérisation de l’ordre. S’il existe $a^m = e$ avec $m \geq 1$ , soit $n \geq 1$ le plus petit tel que $a^n = e$ . Les éléments $e, a, \dots, a^{n-1}$ sont deux à deux distincts ( $a^{i} = a^{j}$ avec $0 \leq i < j < n$ donne $a^{j-i} = e$ , contredisant la minimalité), et tout $a^k$ se ramène à l’un d’eux par division euclidienne $k = nq + r$ : $\langle a\rangle$ a exactement $n$ éléments, et $a^k = a^r = e \iff r = 0 \iff n \mid k$ . Si aucune puissance n’est triviale, tous les $a^k$ ( $k \in \Z$ ) sont distincts (même argument de division) et l’ordre est infini. ∎

Théorème 1.14 (Lagrange)

Soit $G$ un groupe fini et $H$ un sous-groupe. Alors $\abs H$ divise $\abs G$ . En particulier, l’ordre de tout élément divise $\abs G$ , et $a^{\abs G} = e$ pour tout $a \in G$ .

Démonstration. La relation $x \sim y \iff x^{-1}y \in H$ est une équivalence (réflexive : $e \in H$ ; symétrique : par les inverses ; transitive : par les produits). La classe de $x$ est la classe à gauche $xH = \{xh : h \in H\}$ , et $h \mapsto xh$ est une bijection $H \to xH$ (inverse $y \mapsto x^{-1}y$ ) : toutes les classes ont $\abs H$ éléments. Les classes partitionnent $G$ (le théorème général de partition du volume de première année), donc $\abs G = \abs H \times (\text{nombre de classes})$ . Pour un élément : on applique ceci à $H = \langle a\rangle$ ; alors $a^{\abs G} = (a^{\operatorname{ord} a})^{\abs G / \operatorname{ord} a} = e$ . ∎

Exemple 1.15 (Les classes à l’œuvre : $A_3$ dans $\mathfrak{S}_3$ )

Prenons $G = \mathfrak{S}_3$ (ordre $6$ ) et $H = A_3 = \{\mathrm{id},\ (1\,2\,3),\ (1\,3\,2)\}$ . Les classes à gauche sont

H = \{\mathrm{id},\ (1\,2\,3),\ (1\,3\,2)\}, \qquad (1\,2)H = \{(1\,2),\ (2\,3),\ (1\,3)\} :

deux classes de trois éléments partitionnant $G$ , exactement comme l’exige le décompte $\abs G = \abs H \times (\text{nombre de classes})$ — et visiblement la partition en permutations paires et impaires. Noter que $(1\,3)H = (1\,2)H$ bien que $(1\,3) \neq (1\,2)$ : les classes sont des classes, non repérées par leurs représentants, et $x^{-1}y \in H$ est la seule comparaison légitime. Cette image à deux classes est celle qui vaut en général pour la signature : $A_n$ et son unique classe compagne coupent $\mathfrak{S}_n$ en deux, ce qui est la façon dont le problème du week-end compte les positions du puzzle atteignables.

Exemple 1.16

Deux dividendes immédiats. Les groupes d’ordre premier sont cycliques : si $\abs G = p$ est premier et $a \neq e$ , alors $\operatorname{ord}(a)$ divise $p$ et n’est pas $1$ , donc vaut $p$ : $\langle a\rangle = G$ . Le treillis des sous-groupes de $\Z/12\Z$ : d’après la Proposition 1.17 ci-dessous, il y a exactement un sous-groupe par diviseur de $12$ — d’ordres $1, 2, 3, 4, 6, 12$ , engendrés respectivement par $\overline 0$ , $\overline 6$ , $\overline 4$ , $\overline 3$ , $\overline 2$ , $\overline 1$ . La mise en garde finale : la réciproque de Lagrange est fausse en général — $A_4$ est d’ordre $12$ mais n’a pas de sous-groupe d’ordre $6$ , comme nous le démontrons dans le problème du week-end de ce chapitre (Problème 1.1, question 14). Lagrange restreint les ordres possibles ; il ne les garantit pas.

Le treillis des sous-groupes de ℤ/12ℤ : un sous-groupe par diviseur de 12 (), avec une arête lorsque l’un contient l’autre avec un indice premier. Les inclusions vont à rebours de la divisibilité du générateur : 4 ⊂eq 2 car 4 est un multiple de 2. — Le treillis des sous-groupes de $\Z/12\Z$ : un sous-groupe par diviseur de $12$ (Proposition 1.17), avec une arête lorsque l’un contient l’autre avec un indice premier. Les inclusions vont *à rebours* de la divisibilité du générateur : $\langle\overline 4\rangle \subseteq \langle\overline2\rangle$ car $4$ est un multiple de $2$ .

Proposition 1.17 (Groupes cycliques)

Soit $G = \langle a \rangle$ cyclique d’ordre $n$ .

$G$ est isomorphe à $(\Z/n\Z, +)$ , via $\overline k \mapsto a^k$ .
Tout sous-groupe de $G$ est cyclique ; pour chaque diviseur $d \mid n$ il existe exactement un sous-groupe d’ordre $d$ , à savoir $\langle a^{n/d}\rangle$ .
$a^k$ engendre $G$ si et seulement si $\gcd(k, n) = 1$ : $G$ a $\varphi(n)$ générateurs (indicatrice d’Euler).

Démonstration. (1) L’application $k \mapsto a^k$ de $\Z$ sur $G$ est compatible avec la congruence modulo $n$ ( $a^{k} = a^{k'} \iff n \mid k - k'$ , par la caractérisation de l’ordre) ; la propriété universelle (Définition 1.3) fournit un morphisme bijectif bien défini depuis $\Z/n\Z$ .

(2) Soit $H \leq G$ non trivial et $m$ le plus petit $\geq 1$ tel que $a^m \in H$ . La division euclidienne montre $H = \langle a^m\rangle$ (pour $a^k \in H$ : $k = mq + r$ force $a^r \in H$ , donc $r = 0$ ), et $m \mid n$ (on divise $n$ par $m$ : $a^{n \bmod m} \in H$ ). Alors $\abs H = n/m$ ; prendre $m = n/d$ réalise chaque diviseur $d$ . Unicité : tout sous-groupe d’ordre $d$ est, d’après ce qui précède, de la forme $\langle a^m \rangle$ avec $n/m = d$ — donc $m = n/d$ est imposé et le sous-groupe est déterminé.

(3) Nous affirmons que $\operatorname{ord}(a^k) = \frac{n}{\gcd(k, n)}$ . Posons $d = \gcd(k, n)$ . Pour tout $m \geq 1$ , la caractérisation de l’ordre de la Définition 1.13 donne la chaîne d’équivalences

(a^k)^m = e \iff n \mid km \iff \frac{n}{d} \,\Big|\, \frac{k}{d}\,m \iff \frac{n}{d} \,\Big|\, m ,

la dernière étape par le lemme de Gauss, puisque $\frac nd$ et $\frac kd$ sont premiers entre eux. Le plus petit tel $m$ est $\frac nd$ : $\operatorname{ord}(a^k) = \frac n{\gcd(k,n)}$ , qui vaut $n$ si et seulement si $\gcd(k, n) = 1$ . Il y a $\varphi(n)$ telles classes $k$ modulo $n$ . ∎

1.4 Le groupe symétrique

Définition 1.18

$\mathfrak{S}_n$ est le groupe des permutations de $\intint{1}{n}$ (d’ordre $n!$ ). Un cycle $(a_1\,a_2\,\cdots\,a_k)$ envoie $a_1 \mapsto a_2 \mapsto \dots \mapsto a_k \mapsto a_1$ et fixe tout le reste ; $k$ est sa longueur, un $2$ -cycle est une transposition. Deux cycles sont disjoints lorsque leurs supports (points non fixes) le sont.

Théorème 1.19 (Décomposition en cycles)

Toute permutation $\sigma \neq \mathrm{id}$ est un produit de cycles deux à deux disjoints, de manière unique à l’ordre des facteurs près. Des cycles disjoints commutent, et $\operatorname{ord}(\sigma)$ est le ppcm des longueurs.

Démonstration. Considérons la relation d’« orbite » sur le support de $\sigma$ : $x \sim y$ si et seulement si $y = \sigma^k(x)$ pour un certain $k \in \Z$ — une relation d’équivalence. Chaque classe $\{x, \sigma(x), \dots, \sigma^{k-1}(x)\}$ (finie, donc les itérées bouclent — la première répétition doit revenir à $x$ par injectivité) porte le cycle $(x\ \sigma(x)\ \cdots\ \sigma^{k-1}(x))$ , et $\sigma$ est le produit de ces cycles : sur chaque orbite, seul le cycle correspondant agit. Unicité : toute factorisation en cycles disjoints reproduit exactement les orbites (le cycle passant par $x$ doit être $(x\ \sigma(x)\ \cdots)$ ). Des cycles disjoints commutent puisqu’ils déplacent des points disjoints ; l’énoncé sur l’ordre s’ensuit car $\sigma^m = \mathrm{id}$ si et seulement si la puissance $m$ -ième de chaque cycle l’est (disjonction), si et seulement si chaque longueur divise $m$ . ∎

Exemple 1.20 (Le type de cycle comme recensement)

Combien de permutations de $\mathfrak{S}_9$ ont le type de cycle $(4, 3, 2)$ — un $4$ -cycle, un $3$ -cycle, une transposition ? On choisit les supports et les ordres cycliques :

\frac{9!}{4\cdot 3\cdot 2} = \frac{362\,880}{24} = 15\,120 :

on aligne les neuf symboles en ligne ( $9!$ façons), on regroupe les quatre premiers, les trois suivants, les deux derniers en cycles, et on divise par les rotations à l’intérieur de chaque groupe ( $4$ , $3$ et $2$ respectivement) qui donnent la même permutation. (Ici les longueurs des cycles sont distinctes, donc pas d’autre division ; des longueurs égales exigeraient aussi de diviser par les permutations des groupes de même taille.) Toute telle permutation est d’ordre $\operatorname{lcm}(4,3,2) = 12$ et de signature $(-1)^3(-1)^2(-1)^1 = +1$ (Théorème 1.19 et le théorème de la signature ci-dessous). Une partition de $9$ , une classe de conjugaison, un recensement — la combinatoire de $\mathfrak{S}_n$ est l’arithmétique des partitions.

Théorème 1.21 (Signature)

Il existe exactement un morphisme de groupes $\varepsilon \colon \mathfrak{S}_n \to \{\pm 1\}$ (pour $n \geq 2$ ) prenant la valeur $-1$ sur les transpositions : la signature. De plus $\varepsilon(\sigma) = (-1)^{I(\sigma)}$ où $I(\sigma)$ est le nombre d’inversions (paires $i < j$ avec $\sigma(i) > \sigma(j)$ ), un $k$ -cycle a pour signature $(-1)^{k-1}$ , et le groupe alterné $A_n = \ker\varepsilon$ est d’ordre $\frac{n!}{2}$ .

Démonstration. Existence. Pour $\sigma \in \mathfrak{S}_n$ posons

\varepsilon(\sigma) = \prod_{1 \leq i < j \leq n} \frac{\sigma(j) - \sigma(i)}{j - i} .

Les valeurs absolues des facteurs se multiplient en $1$ (les paires non ordonnées $\{\sigma(i), \sigma(j)\}$ parcourent toutes les paires), donc $\varepsilon(\sigma) = (-1)^{I(\sigma)} \in \{\pm1\}$ . Morphisme : pour $\sigma, \tau$ ,

\varepsilon(\sigma\tau) = \prod_{i<j} \frac{\sigma(\tau(j)) - \sigma(\tau(i))}{j - i} = \prod_{i<j} \frac{\sigma(\tau(j)) - \sigma(\tau(i))}{\tau(j) - \tau(i)} \cdot \prod_{i<j} \frac{\tau(j) - \tau(i)}{j - i} = \varepsilon(\sigma)\,\varepsilon(\tau),

le produit du milieu valant $\varepsilon(\sigma)$ après réindexation par les paires $\{\tau(i), \tau(j)\}$ (chaque paire non ordonnée apparaît une fois, et numérateur et dénominateur changent de signe ensemble). Une transposition $\tau = (a\,b)$ avec $a < b$ a un nombre impair d’inversions ; comptées exactement : les paires inversées $(i, j)$ , $i < j$ , avec $\tau(i) > \tau(j)$ sont

(a, j) \ \text{pour } a < j < b, \qquad (i, b) \ \text{pour } a < i < b, \qquad (a, b) \ \text{elle-même},

soit $(b - a - 1) + (b - a - 1) + 1 = 2(b - a) - 1$ d’entre elles, un nombre impair. (Autrement : vérifier $(1\,2)$ directement, avec une inversion, et conjuguer — les conjugués ont même signature puisque $\varepsilon$ est un morphisme vers un groupe abélien.) Donc $\varepsilon((a\,b)) = (-1)^{2(b-a)-1} = -1$ .

Unicité. Les transpositions engendrent $\mathfrak{S}_n$ (tout cycle $(a_1\cdots a_k) = (a_1\,a_k)(a_1\,a_{k-1})\cdots(a_1\,a_2)$ , et le Théorème 1.19 conclut) ; un morphisme vers $\{\pm1\}$ est déterminé par ses valeurs sur des générateurs.

Conséquences. L’identité sur les cycles ci-dessus écrit un $k$ -cycle comme $k - 1$ transpositions : signature $(-1)^{k-1}$ . $A_n$ : le morphisme $\varepsilon$ est surjectif (des transpositions existent pour $n \geq 2$ ), et les deux « classes » $A_n$ et $(1\,2)A_n$ sont équipotentes et partitionnent $\mathfrak{S}_n$ (argument de Lagrange) : $\abs{A_n} = \frac{n!}{2}$ . ∎

Exemple 1.22

$\sigma = \begin{pmatrix} 1&2&3&4&5&6\\ 3&6&5&4&1&2 \end{pmatrix} = (1\,3\,5)(2\,6)$ : ordre $\operatorname{lcm}(3,2) = 6$ , signature $(-1)^{2}\cdot(-1)^{1} = -1$ . La signature est le test de parité le plus rapide sur les battages — et le moteur du déterminant au Chapitre 2.

Exemple 1.23 (Trois chemins vers un même signe)

Soit $\sigma \in \mathfrak{S}_5$ envoyant $1, 2, 3, 4, 5$ sur $3, 5, 4, 1, 2$ . Par les cycles : $1 \mapsto 3 \mapsto 4 \mapsto 1$ et $2 \mapsto 5 \mapsto 2$ , donc $\sigma = (1\,3\,4)(2\,5)$ et $\varepsilon(\sigma) = (-1)^{2}(-1)^{1} = -1$ . Par les inversions : dans la liste de valeurs $3, 5, 4, 1, 2$ les paires en désordre sont $(3,1)$ , $(3,2)$ , $(5,4)$ , $(5,1)$ , $(5,2)$ , $(4,1)$ , $(4,2)$ : sept d’entre elles, et $(-1)^7 = -1$ . Par les transpositions : $\sigma = (1\,4)(1\,3)(2\,5)$ , trois facteurs, $(-1)^3 = -1$ . Trois calculs, une parité : l’unicité dans le Théorème 1.21 garantit qu’aucun schéma de comptabilité ne peut jamais les faire diverger — ce qui est exactement ce qui rend $\varepsilon$ utilisable comme invariant (voir le problème du week-end).

Remarque 1.24 (Ce que devient la signature par la suite)

La signature est la graine de trois récoltes ultérieures : elle construit le déterminant et sa règle de produit au Chapitre 2 ; elle alimente des invariants de parité pour des casse-têtes combinatoires (le problème du week-end de ce chapitre résout le taquin grâce à elle) ; et les groupes alternés $A_n$ qu’elle définit deviennent centraux dans le volume de troisième année, où leur simplicité pour $n \geq 5$ explique pourquoi les équations de degré $5$ n’ont pas de solution par radicaux.

1.5 Anneaux, idéaux, quotients

Définition 1.25 (Idéal)

Soit $A$ un anneau commutatif. Un idéal $I \subseteq A$ est un sous-groupe additif tel que $a x \in I$ pour tout $a \in A$ , $x \in I$ . Les noyaux de morphismes d’anneaux sont des idéaux ; $I = A$ si et seulement si $1 \in I$ si et seulement si $I$ contient un inversible. L’idéal engendré par $x$ est $xA = \{xa\}$ (un idéal principal).

Théorème 1.26 (Idéaux de $\Z$ et de $K[X]$ )

Tout idéal de $\Z$ est $n\Z$ pour un unique $n \in \N$ ; tout idéal de $K[X]$ ( $K$ un corps) est $P\,K[X]$ pour un unique $P$ unitaire (ou nul). Par conséquent, les pgcd existent dans les deux anneaux avec des relations de Bézout : $x\Z + y\Z = \gcd(x,y)\Z$ , et de même pour les polynômes.

Démonstration. Pour $\Z$ c’était le théorème des sous-groupes du volume de première année (un idéal est en particulier un sous-groupe, et $n\Z$ est un idéal). Pour $K[X]$ : soit $I \neq \{0\}$ un idéal et $P \in I$ non nul de degré minimal, normalisé unitaire. Pour $F \in I$ , la division euclidienne $F = PQ + R$ donne $R = F - PQ \in I$ avec $\deg R < \deg P$ : la minimalité force $R = 0$ , donc $I = P\,K[X]$ . Unicité : deux générateurs unitaires se divisent mutuellement. Les énoncés de Bézout sont l’égalité de l’idéal $x\Z + y\Z$ (resp. son analogue polynomial) avec l’idéal principal du pgcd — la définition même du pgcd utilisée en première année, reconnue maintenant comme un énoncé sur les idéaux. ∎

Exemple 1.27 (Un pgcd de polynômes, de deux façons)

Calculons $\gcd(X^3 - 1,\ X^2 - 1)$ dans $\Q[X]$ . Par Euclide :

X^3 - 1 = X\,(X^2 - 1) + (X - 1), \qquad X^2 - 1 = (X + 1)(X - 1) + 0 ,

donc le pgcd est $X - 1$ , et la remontée donne la relation de Bézout

X - 1 = 1\cdot(X^3 - 1) - X\cdot(X^2 - 1).

Par les idéaux : l’idéal $(X^3 - 1)\Q[X] + (X^2 - 1)\Q[X]$ est principal (Théorème 1.26) ; il contient $X - 1$ (la formule affichée) et est contenu dans $(X - 1)\Q[X]$ (les deux générateurs s’annulent en $1$ , donc sont multiples de $X - 1$ ) : le générateur unitaire est $X - 1$ . L’idée à retenir : le point de vue des idéaux identifie le pgcd sans diviser — les racines communes localisent l’idéal, et Euclide ne fait que le certifier.

Définition 1.28 (Anneau quotient $\Z/n\Z$ , revisité)

Pour un idéal $I$ de $A$ , la relation $x \sim y \iff x - y \in I$ est une équivalence compatible avec $+$ et $\times$ ; l’ensemble quotient $A/I$ hérite d’une structure d’anneau — l’anneau quotient — faisant de $\pi \colon A \to A/I$ un morphisme de noyau $I$ . Pour $A = \Z$ , $I = n\Z$ c’est le $\Z/n\Z$ du volume de première année, désormais muni de sa propriété universelle : tout morphisme annulant $I$ se factorise à travers $A/I$ .

Théorème 1.29 (Théorème des restes chinois, forme anneau)

Si $\gcd(m, n) = 1$ , l’application

\Z/mn\Z \longrightarrow \Z/m\Z \times \Z/n\Z, \qquad \overline{x} \longmapsto (x \bmod m,\; x \bmod n)

est un isomorphisme d’anneaux. Par conséquent $\varphi(mn) = \varphi(m)\varphi(n)$ pour $m, n$ premiers entre eux, et

\varphi(n) = n \prod_{p \mid n} \Bigl(1 - \frac 1p\Bigr) \quad (p \text{ premier}).

Démonstration. L’application est un morphisme d’anneaux bien défini (les compatibilités sont immédiates). Injectivité : $x \equiv 0$ modulo $m$ et modulo $n$ avec $\gcd(m,n) = 1$ force $mn \mid x$ (Gauss). Surjectivité : les deux membres ont $mn$ éléments, donc l’injectivité suffit (cardinaux finis égaux) — ou explicitement : à partir d’une relation de Bézout $um + vn = 1$ , la classe de

x = b\,um + a\,vn

s’envoie sur $(a \bmod m,\ b \bmod n)$ , puisque $vn = 1 - um \equiv 1 \pmod m$ fait que $x \equiv a \pmod m$ , et symétriquement modulo $n$ — la recette utilisée numériquement dans l’Exemple 1.30. Les inversibles correspondent aux couples d’inversibles (les inversibles d’un anneau produit sont les couples d’inversibles), donc $\varphi(mn) = \varphi(m)\varphi(n)$ . Pour une puissance de premier, $\varphi(p^k) = p^k - p^{k-1}$ (les non-inversibles modulo $p^k$ sont les multiples de $p$ ) ; la multiplicativité assemble la formule du produit. ∎

Exemple 1.30 (Inverser l’isomorphisme chinois)

Prenons $m = 8$ , $n = 9$ . L’inverse de l’isomorphisme est rendu explicite par les deux idempotents : on cherche $u \equiv 1 \pmod 8$ , $u \equiv 0 \pmod 9$ et $v \equiv 0 \pmod 8$ , $v \equiv 1 \pmod 9$ . De $u = 9k \equiv 1 \pmod 8$ : $k \equiv 1$ , donc $u = 9$ ; de $v = 8k \equiv 1 \pmod 9$ : $-k \equiv 1$ , $k \equiv 8$ , donc $v = 64$ . Alors la classe de $x = 9a + 64b$ modulo $72$ est l’unique solution de $x \equiv a \pmod 8$ , $x \equiv b \pmod 9$ : pour $a = 3$ , $b = 5$ on obtient $27 + 320 = 347 \equiv 59 \pmod{72}$ — exactement la valeur intermédiaire trouvée par substitution dans l’Exercice 1.8. L’idée à retenir : $u$ et $v$ vérifient $u + v \equiv 1$ , $uv \equiv 0$ , $u^2 \equiv u$ , $v^2 \equiv v$ modulo $72$ ; ce sont les images de $(1, 0)$ et $(0, 1)$ , et toute décomposition chinoise est au fond une décomposition de $1$ en idempotents orthogonaux.

Théorème 1.31 (Euler ; Fermat revisité)

Les inversibles de $\Z/n\Z$ forment un groupe d’ordre $\varphi(n)$ ; d’où pour $\gcd(a, n) = 1$ :

a^{\varphi(n)} \equiv 1 \pmod n \qquad (\text{théorème d'Euler}),

et le petit théorème de Fermat est le cas $n = p$ premier, désormais à une ligne de Lagrange.

Démonstration. Les classes inversibles sont exactement celles des entiers premiers à $n$ (volume de première année) : au nombre de $\varphi(n)$ , formant un groupe pour la multiplication. Lagrange (Théorème 1.14) : tout élément à la puissance de l’ordre du groupe est l’identité. ∎

Exemple 1.32 (Un groupe d’inversibles sans générateur)

Le groupe $(\Z/15\Z)^*$ a $\varphi(15) = \varphi(3)\varphi(5) = 8$ éléments. Est-il cyclique ? Calculons les ordres à l’aide de l’isomorphisme chinois $(\Z/15\Z)^* \simeq (\Z/3\Z)^* \times (\Z/5\Z)^*$ (un inversible modulo $15$ est un couple d’inversibles) : les facteurs ont pour ordres $2$ et $4$ , donc l’ordre de tout élément divise $\operatorname{lcm}(2, 4) = 4 < 8$ — aucun élément n’engendre. Concrètement :

2^4 = 16 \equiv 1, \qquad 4^2 = 16 \equiv 1, \qquad 7^4 \equiv 1, \qquad 11^2 = 121 \equiv 1, \qquad 14^2 \equiv 1 \pmod{15} :

des ordres $4, 2, 4, 2, 2$ et jamais $8$ . À comparer avec l’Exercice 1.10 : $(\Z/p\Z)^*$ est cyclique pour $p$ premier, car là le groupe des inversibles siège dans un corps. Le théorème d’Euler s’applique toujours avec l’exposant $\varphi(15) = 8$ , mais le véritable exposant universel ici est $4$ — Euler est une borne supérieure, pas toujours la plus fine.

Définition 1.33 (Algèbre)

Une $K$ -algèbre est un $K$ -espace vectoriel $A$ muni d’une structure d’anneau dont la multiplication est $K$ -bilinéaire. Exemples : $K[X]$ , $\mathcal{M}_n(K)$ , $\mathcal{L}(E)$ , les espaces de fonctions $\mathcal{F}(X, K)$ , $\C$ comme $\R$ -algèbre. Les morphismes d’algèbres sont les morphismes d’anneaux linéaires ; l’évaluation $P \mapsto P(u)$ de $K[X]$ vers $\mathcal{L}(E)$ (ou $\mathcal{M}_n(K)$ ) est l’exemple central, moteur du Chapitre 3.

Exemple 1.34 (Un morphisme d’évaluation et son noyau)

Prenons $A = \begin{pmatrix}0 & 1\\ 0 & 0\end{pmatrix}$ et l’évaluation $\varepsilon_A \colon \R[X] \to \mathcal{M}_2(\R)$ , $P \mapsto P(A)$ . Puisque $A^2 = 0$ ,

P(A) = P(0)\,I + P'(0)\,A = \begin{pmatrix} P(0) & P'(0)\\ 0 & P(0)\end{pmatrix},

(seuls les termes constant et linéaire de $P$ subsistent). Donc $\ker\varepsilon_A = \{P : P(0) = P'(0) = 0\} = X^2\,\R[X]$ : un idéal principal, exactement comme le prévoit le Théorème 1.26, engendré par le polynôme unitaire $X^2$ de plus petit degré dans le noyau — le polynôme minimal de $A$ , vedette du Chapitre 3. L’image est l’algèbre commutative de dimension deux $\{aI + bA\}$ : les morphismes d’évaluation réduisent le $\R[X]$ de dimension infinie à de petites algèbres calculables.

Remarque 1.35 (Perspectives : trois mélodies à écouter)

Trois idées structurelles de ce chapitre reviennent tout au long du volume, chaque fois dans une orchestration plus fournie. Factorisation par un quotient (Définition 1.3) : elle construit $\Z/n\Z$ ici, définit des applications sur les ensembles de solutions de systèmes linéaires au Chapitre 2, et sous-tend en silence tout argument de « bonne définition sur les classes ». Invariants : la signature est un morphisme vers $\{\pm1\}$ qu’aucun coup légal ne peut esquiver — la même logique donne la règle de produit du déterminant (Chapitre 2), l’invariance de la trace par similitude, et les quantités conservées du Chapitre 16. Compter contre une structure : Lagrange compte à travers les classes, la dimension compte à travers les bases (Chapitre 2), la multiplicité compte à travers les degrés des polynômes (Chapitre 3) ; chaque fois qu’une borne paraît miraculeuse, une partition ou une graduation fait le comptage.

Remarque 1.36 (Pièges classiques)

Quatre classiques. (i) Une application sur un quotient doit être vérifiée bien définie : « $\overline x \mapsto$ (formule sur $x$ ) » n’est légitime que si la formule est constante sur les classes — la compatibilité de la Définition 1.3, pas une formalité. (ii) $\operatorname{ord}(ab) = \operatorname{lcm}(\operatorname{ord}a, \operatorname{ord}b)$ est faux en général, même pour des éléments qui commutent ( $a$ et $a^{-1}$ ) ; l’Exercice 1.4 donne l’énoncé correct (premiers entre eux et commutant), et les cycles disjoints la version correcte pour les permutations. (iii) La dénombrabilité survit aux unions dénombrables et aux produits finis, mais pas aux produits dénombrables : $\{0,1\}^{\N}$ est non dénombrable (Exercice 1.3) bien que chaque facteur ait deux éléments. (iv) Cantor–Bernstein ne réclame que des injections dans les deux sens, mais la bijection qu’il construit est en général discontinue et non explicite — ne pas attendre de formule (Exemple 1.11).

Remarque 1.37 (Où ce chapitre est utilisé)

Presque partout. La signature construit les déterminants (Chapitre 2) ; le morphisme d’évaluation $P \mapsto P(u)$ et les idéaux principaux de $K[X]$ produisent les polynômes minimaux et les décompositions en noyaux du Chapitre 3 ; la dénombrabilité est la scène sur laquelle se joue le Chapitre 21 (les probabilités sur les espaces dénombrables) et la raison pour laquelle la topologie ne cesse de produire des ensembles denses dénombrables (Chapitre 4). La construction quotient $A/I$ est redéployée dans le volume de troisième année pour construire les corps $K[X]/(P)$ et, à partir d’eux, la théorie de Galois : la propriété universelle démontrée ici y est utilisée mot pour mot.

1.6 Exercices

Exercice 1.1 ★

Lesquels des ensembles suivants sont dénombrables ? L’ensemble des parties finies de $\N$ ; l’ensemble de toutes les parties de $\N$ ; $\R \setminus \Q$ ; l’ensemble des polynômes à coefficients rationnels ; l’ensemble des suites de $0$ et de $1$ nulles à partir d’un certain rang.

Solution

Solution de Exercice 1.1.

Parties finies de $\N$ : dénombrable — l’ensemble des parties de $\intint{0}{n}$ est fini, et les parties finies forment l’union dénombrable sur $n$ de celles-ci (Proposition 1.6 (3)) ; infini car il contient tous les singletons.

Toutes les parties de $\N$ : non dénombrable, par le théorème de Cantor (Théorème 1.9 (1) avec $E = \N$ ).

$\R \setminus \Q$ : non dénombrable — sinon $\R = \Q \cup (\R\setminus\Q)$ serait une union de deux ensembles dénombrables, contredisant le Théorème 1.9 (2).

Polynômes sur $\Q$ : dénombrable — les polynômes de degré $\leq n$ s’injectent dans $\Q^{n+1}$ (produits finis d’ensembles dénombrables), et prendre l’union sur $n$ .

Suites binaires nulles à partir d’un certain rang : dénombrable — elles sont en bijection avec les parties finies de $\N$ (le support).

Exercice 1.2 ★

Dans $\mathfrak{S}_7$ , soient $\sigma = (1\,4\,2\,6)(3\,5)$ et $\tau = (2\,3\,7)$ . Calculer $\sigma\tau$ et $\tau\sigma$ sous forme de cycles disjoints, les ordres et signatures des quatre permutations, et $\sigma^{2026}$ .

Solution

Solution de Exercice 1.2.

Calculer élément par élément, en appliquant d’abord le facteur de droite. $\sigma\tau$ envoie $1 \mapsto \sigma(1) = 4$ , $\;2 \mapsto \sigma(3) = 5$ , $\;3 \mapsto \sigma(7) = 7$ , $\;4 \mapsto \sigma(4) = 2$ , $\;5 \mapsto \sigma(5) = 3$ , $\;6 \mapsto \sigma(6) = 1$ , $\;7 \mapsto \sigma(2) = 6$ :

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

un $7$ -cycle. De même $\tau\sigma$ envoie $1 \mapsto \tau(4) = 4$ , $\;2 \mapsto \tau(6) = 6$ , $\;3 \mapsto \tau(5) = 5$ , $\;4 \mapsto \tau(2) = 3$ , $\;5 \mapsto \tau(3) = 7$ , $\;6 \mapsto \tau(1) = 1$ , $\;7 \mapsto \tau(7) = 2$ :

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

également un $7$ -cycle (comme prévu : $\sigma\tau$ et $\tau\sigma$ sont conjugués, donc partagent leur type de cycle).

Ordres et signatures : $\sigma$ a le type de cycle $(4,2)$ : ordre $\operatorname{lcm}(4,2) = 4$ , signature $(-1)^3(-1)^1 = +1$ ; $\tau$ est un $3$ -cycle : ordre $3$ , signature $+1$ ; les deux produits sont des $7$ -cycles : ordre $7$ , signature $(-1)^6 = +1$ .

$\sigma^{2026}$ : $2026 = 4 \times 506 + 2$ , donc $\sigma^{2026} = \sigma^2 = (1\,2)(4\,6)$ (élever le $4$ -cycle au carré ; la transposition disparaît en s’élevant au carré).

Exercice 1.3 ★

Construire des injections explicites montrant que $\mathcal{P}(\N)$ , $\intcc{0}{1}$ et l’ensemble $\{0,1\}^{\N}$ des suites binaires sont deux à deux équipotents (développements binaires dans les deux sens ; Cantor–Bernstein absorbe le désagrément de la double représentation).

Solution

Solution de Exercice 1.3.

$\{0,1\}^{\N} \to \mathcal{P}(\N)$ : une suite s’envoie sur son support — une bijection (fonctions indicatrices), aucun théorème requis.

$\{0,1\}^{\N} \to \intcc{0}{1}$ : l’application en base $3$ $(a_n) \mapsto \sum 2a_n 3^{-n-1}$ est injective (deux suites distinctes diffèrent d’abord au rang $N$ ; les queues ne peuvent compenser un écart de $2\cdot 3^{-N-1}$ , puisque $\sum_{n > N} 2\cdot 3^{-n-1} = 3^{-N-1} < 2\cdot3^{-N-1}$ ).

$\intcc{0}{1} \to \{0,1\}^{\N}$ : développement binaire, en choisissant (disons) le développement qui ne se termine pas par une suite infinie de $1$ : injective.

Par Cantor–Bernstein (Théorème 1.10) appliqué aux deux dernières injections, $\intcc{0}{1}$ et $\{0,1\}^{\N}$ sont équipotents, donc les trois ensembles le sont.

Exercice 1.4 ★

Soit $G$ un groupe et $a, b \in G$ des éléments commutant, d’ordres finis $m$ et $n$ premiers entre eux. Démontrer que $\operatorname{ord}(ab) = mn$ . Montrer par un exemple dans $\mathfrak{S}_3$ que la commutation est essentielle.

Solution

Solution de Exercice 1.4.

Soit $c = ab = ba$ et $d = \operatorname{ord}(c)$ . D’abord $c^{mn} = a^{mn} b^{mn} = e$ (la commutation permet de scinder la puissance), donc $d \mid mn$ . Réciproquement $c^d = e$ donne $a^d = b^{-d}$ ; cet élément appartient à $\langle a\rangle \cap \langle b\rangle$ , un sous-groupe dont l’ordre divise à la fois $m$ et $n$ (Lagrange dans chaque groupe cyclique), donc est trivial : $a^d = b^d = e$ , donc $m \mid d$ et $n \mid d$ , et par la coprimalité $mn \mid d$ . Donc $d = mn$ .

Dans $\mathfrak{S}_3$ : prendre $a = (1\,2)$ (ordre $2$ ) et $b = (1\,2\,3)$ (ordre $3$ ), d’ordres premiers entre eux, qui ne commutent pas : $ab = (2\,3)$ est d’ordre $2 \neq 6$ — en effet $\mathfrak{S}_3$ n’a pas d’élément d’ordre $6$ . La commutation est essentielle.

Exercice 1.5 ★★

Soit $G$ un groupe fini d’ordre pair. Démontrer que $G$ contient un élément d’ordre $2$ . (Apparier chaque élément avec son inverse ; compter ceux qui sont appariés à eux-mêmes.)

Solution

Solution de Exercice 1.5.

Apparier tout $x \in G$ avec $x^{-1}$ . Les paires $\{x, x^{-1}\}$ avec $x \neq x^{-1}$ ont deux éléments et partitionnent leur union ; les éléments restants sont exactement ceux avec $x = x^{-1}$ , c.-à-d. $x^2 = e$ . Comme $\abs G$ est pair et que les paires à deux éléments couvrent un nombre pair d’éléments, l’ensemble $\{x : x^2 = e\}$ est de cardinal pair ; il contient $e$ , donc il contient au moins un autre élément $x \neq e$ — un élément d’ordre $2$ .

Exercice 1.6 ★★

Démontrer que $A_n$ ( $n \geq 3$ ) est engendré par les $3$ -cycles. (Un produit de deux transpositions est un $3$ -cycle ou un produit de deux $3$ -cycles.)

Solution

Solution de Exercice 1.6.

Tout élément de $A_n$ est un produit d’un nombre pair de transpositions (Théorème 1.21 : décomposer en transpositions ; le compte est pair puisque la signature est $+1$ ). Il suffit d’écrire chaque produit de deux transpositions à l’aide de $3$ -cycles :

(a\,b)(a\,c) = (a\,c\,b), \qquad (a\,b)(c\,d) = (a\,c\,b)(a\,c\,d) \quad (a,b,c,d \text{ distincts}),

(vérifier par évaluation), et $(a\,b)(a\,b) = \mathrm{id}$ . Donc les $3$ -cycles engendrent $A_n$ .

Exercice 1.7 ★★

Déterminer tous les morphismes de groupes : de $(\Q, +)$ vers $(\Z, +)$ ; de $(\Z/n\Z, +)$ vers $(\Z/m\Z, +)$ (les compter : $\gcd(m,n)$ ) ; de $(\Q, +)$ vers $(\Q_+^*, \times)$ .

Solution

Solution de Exercice 1.7.

$(\Q,+) \to (\Z,+)$ : seul le morphisme nul. Pour tout $x$ et tout $n \geq 1$ , $f(x) = n f\bigl(\frac xn\bigr)$ est divisible par $n$ dans $\Z$ ; le seul entier divisible par tout $n$ est $0$ , donc $f(x) = 0$ pour tout $x$ .

$(\Z/n\Z, +) \to (\Z/m\Z, +)$ : un morphisme est déterminé par $c = f(\overline 1)$ , qui doit vérifier $n c \equiv 0 \pmod m$ , c.-à-d. $c$ est un multiple de $\frac{m}{\gcd(m,n)}$ ; il y a $\gcd(m,n)$ telles classes, et chaque choix définit bien un morphisme (factoriser $k \mapsto kc$ par $\Z/n\Z$ grâce à la propriété universelle).

$(\Q, +) \to (\Q_+^*, \times)$ : seul le morphisme trivial. Si $f(x) = y$ , alors pour tout $n$ , $y = f(n \cdot \frac xn) = f(\frac xn)^n$ est une puissance $n$ -ième dans $\Q_+^*$ . Mais un rationnel $y \neq 1$ ne peut être une puissance $n$ -ième pour tout $n$ : un certain nombre premier apparaît dans $y$ avec un exposant non nul $v$ , et $n \nmid v$ pour $n > \abs v$ (les exposants des puissances $n$ -ièmes sont des multiples de $n$ , par unicité de la factorisation). Donc $f \equiv 1$ .

Exercice 1.8 ★★

À l’aide du théorème des restes chinois, calculer $\varphi(360)$ , trouver tous les $x$ tels que $x \equiv 3 \pmod 8$ , $x \equiv 5 \pmod 9$ et $x \equiv 2 \pmod 5$ , et calculer les deux derniers chiffres de $3^{2026}$ (Euler modulo $100$ ; attention : travailler modulo $4$ et modulo $25$ ).

Solution

Solution de Exercice 1.8.

$360 = 2^3 \cdot 3^2 \cdot 5$ : $\varphi(360) = 360\bigl(1 - \tfrac12\bigr)\bigl(1 - \tfrac13\bigr)\bigl(1 - \tfrac15\bigr) = 360 \cdot \tfrac12 \cdot \tfrac23 \cdot \tfrac45 = 96$ .

Système : modules $8, 9, 5$ deux à deux premiers entre eux, total $360$ . De $x \equiv 3 \pmod 8$ et $x \equiv 5 \pmod 9$ : $x = 3 + 8k$ avec $3 + 8k \equiv 5 \pmod 9$ , c.-à-d. $-k \equiv 2$ , $k \equiv -2 \equiv 7 \pmod 9$ : $x \equiv 3 + 56 = 59 \pmod{72}$ . Puis $59 + 72\ell \equiv 2 \pmod 5$ : $4 + 2\ell \equiv 2$ , $2\ell \equiv 3 \equiv 8$ , $\ell \equiv 4 \pmod 5$ : $x \equiv 59 + 288 = 347 \pmod{360}$ .

Deux derniers chiffres de $3^{2026}$ : modulo $4$ , $3^{2026} = 9^{1013} \equiv 1$ . Modulo $25$ : $\varphi(25) = 20$ et $2026 = 20\cdot101 + 6$ , donc $3^{2026} \equiv 3^6 = 729 \equiv 4 \pmod{25}$ . Résoudre $x \equiv 1 \pmod 4$ , $x \equiv 4 \pmod{25}$ : $x = 4 + 25k \equiv 1 \pmod 4$ donne $k \equiv 1 \pmod 4$ : $x \equiv 29 \pmod{100}$ . Les deux derniers chiffres sont $29$ .

Exercice 1.9 ★★★

Démontrer qu’un anneau intègre fini est un corps. En déduire que $\Z/n\Z$ est un corps si et seulement si $n$ est premier (à nouveau).

Solution

Solution de Exercice 1.9.

Soit $A$ un anneau intègre fini et $a \in A$ , $a \neq 0$ . L’application $x \mapsto ax$ est injective ( $ax = ay \implies a(x - y) = 0 \implies x = y$ , pas de diviseurs de zéro) ; une application injective d’un ensemble fini dans lui-même est surjective (volume de première année, l’équivalence des tiroirs). Donc $1 = ab$ pour un certain $b$ : tout élément non nul est inversible, $A$ est un corps.

$\Z/n\Z$ : si $n$ est premier c’est un anneau intègre ( $n \mid ab \implies n \mid a$ ou $n \mid b$ , lemme d’Euclide), fini, donc un corps ; si $n = rs$ est composé, $\overline r\,\overline s = \overline 0$ exhibe des diviseurs de zéro.

Exercice 1.10 ★★★

(Un classique) Soit $K$ un corps et $G$ un sous-groupe fini de $(K^*, \times)$ . Démontrer que $G$ est cyclique. Indication : soit $m$ l’ordre maximal parmi les éléments de $G$ ; montrer que l’ordre de tout élément divise $m$ (en utilisant l’Exercice 1.4 sur des parties premières entre elles bien choisies), de sorte que tout $G$ vérifie $x^m = 1$ ; compter les racines de $X^m - 1$ . En particulier $(\Z/p\Z)^*$ est cyclique.

Solution

Solution de Exercice 1.10.

Soit $m = \max\{\operatorname{ord}(x) : x \in G\}$ , atteint en $a$ .

Affirmation : tout $x \in G$ a un ordre divisant $m$ . Supposons qu’un certain $x$ ait un ordre $q$ avec $q \nmid m$ : alors une certaine puissance de premier $p^k$ divise $q$ mais pas $m$ . Écrire $m = p^j m'$ avec $p \nmid m'$ et $j < k$ . L’élément $a^{p^j}$ est d’ordre $m'$ ; l’élément $x^{q/p^k}$ est d’ordre $p^k$ ; ces ordres sont premiers entre eux et les deux éléments commutent ( $G \subseteq K^*$ est abélien), donc par l’Exercice 1.4 leur produit est d’ordre $p^k m' > p^j m' = m$ : contredisant la maximalité.

Donc tout $x \in G$ vérifie $x^m = 1$ : le polynôme $X^m - 1$ a au moins $\abs G$ racines dans le corps $K$ , d’où $\abs G \leq m$ (un polynôme non nul de degré $m$ a au plus $m$ racines, volume de première année). Mais $m = \operatorname{ord}(a) \leq \abs G$ par Lagrange. Donc $m = \abs G$ et $\langle a \rangle$ , de cardinal $m = \abs G$ , est tout $G$ : cyclique.

Pour $K = \Z/p\Z$ : $(\Z/p\Z)^*$ est un sous-groupe fini de $K^*$ , donc cyclique (d’ordre $p - 1$ ).

Exercice 1.11 ★★★

Démontrer que le groupe $(\Q, +)$ n’est pas cyclique, et pire : il n’est même pas de type fini. Démontrer en revanche que tout sous-groupe de type fini de $(\Q, +)$ est cyclique.

Solution

Solution de Exercice 1.11.

Non cyclique : le sous-groupe $\langle \frac pq\rangle$ est constitué des multiples entiers de $\frac pq$ , qui ont tous un dénominateur divisant $q$ (sous forme irréductible) ; il rate donc $\frac{1}{2q}$ . Aucun générateur unique ne peut atteindre les dénominateurs non bornés de $\Q$ .

Non de type fini : le sous-groupe engendré par $\frac{p_1}{q_1}, \dots, \frac{p_k}{q_k}$ est constitué de rationnels dont les dénominateurs divisent $Q = q_1 \cdots q_k$ (les combinaisons entières ont un dénominateur divisant $Q$ ) : il rate $\frac{1}{2Q}$ .

Les sous-groupes de type fini sont cycliques : avec $Q$ comme ci-dessus, le sous-groupe $H = \langle \frac{p_1}{q_1}, \dots, \frac{p_k}{q_k}\rangle$ est contenu dans $\frac{1}{Q}\Z$ . L’application $x \mapsto Qx$ est un isomorphisme de $\frac1Q\Z$ sur $\Z$ portant $H$ sur un sous-groupe de $\Z$ , qui est $n\Z$ pour un certain $n$ (volume de première année) : donc $H = \frac{n}{Q}\Z$ est cyclique, engendré par $\frac nQ$ .

Exercice 1.12 ★★

(Critère de Dedekind) Démontrer que tout ensemble infini contient une partie dénombrable, et en déduire qu’un ensemble $E$ est infini si et seulement s’il est équipotent à une partie propre de lui-même. (Pour l’implication directe, décaler une partie dénombrable d’un cran ; pour la réciproque, se rappeler le principe des tiroirs.)

Solution

Solution de Exercice 1.12.

Une partie dénombrable. Soit $E$ infini. Construire $a_0, a_1, a_2, \dots$ par récurrence : $E$ est non vide, choisir $a_0 \in E$ ; si $a_0, \dots, a_n$ sont choisis, $E \setminus \{a_0, \dots, a_n\}$ est non vide ( $E$ n’est pas fini), y choisir $a_{n+1}$ . Les $a_n$ sont deux à deux distincts par construction, donc $A = \{a_n : n \in \N\}$ est une partie dénombrable de $E$ .

Infini $\implies$ équipotent à une partie propre. Définir $f \colon E \to E \setminus \{a_0\}$ par $f(a_n) = a_{n+1}$ et $f(x) = x$ pour $x \notin A$ . Elle est injective (les deux morceaux sont injectifs et d’images disjointes) et surjective sur $E \setminus \{a_0\}$ : tout $a_{n+1}$ est atteint, tout $x \notin A$ est atteint. Donc $E$ est équipotent à la partie propre $E \setminus \{a_0\}$ .

Réciproque. Si $E$ est fini et $g \colon E \to F$ est une bijection sur $F \subseteq E$ avec $F \neq E$ , alors $g$ est une injection de $E$ dans lui-même qui n’est pas surjective, contredisant le principe des tiroirs (volume de première année : une auto-application injective d’un ensemble fini est bijective). Donc un ensemble équipotent à une partie propre est infini.

1.7 Problème : le taquin

Le taquin est un plateau $4 \times 4$ contenant quinze tuiles coulissantes numérotées de $1$ à $15$ et une case vide ; un coup fait glisser dans la case vide l’une des tuiles qui lui sont adjacentes. Dans les années 1890, Sam Loyd popularisa le casse-tête en offrant 1000$ à quiconque parviendrait à échanger les tuiles $14$ et $15$ en ramenant toutes les autres tuiles à leur place. Personne ne les a jamais empochés, et ce problème du week-end démontre les deux moitiés de la raison : la signature du Théorème 1.21 interdit l’échange de Loyd, et — moitié plus difficile, constructive — tout ce que la signature autorise est véritablement résoluble. L’énoncé complet est le théorème de Johnson–Story (1879).

La configuration résolue et la configuration 14–15 de Sam Loyd. La question à 1000$ : des glissements légaux peuvent-ils transformer le plateau de droite en celui de gauche ? — La configuration résolue et la configuration $14$ – $15$ de Sam Loyd. La question à 1000$ : des glissements légaux peuvent-ils transformer le plateau de droite en celui de gauche ?

Problème 1.1

Problème du week-end — le théorème de résolubilité de Johnson–Story

Numérotons les cases de $1$ à $16$ dans l’ordre de lecture (de gauche à droite, de haut en bas), de sorte que la case $k$ occupe la ligne $i$ et la colonne $j$ avec $k = 4(i - 1) + j$ . La case $16$ (en bas à droite) est le domicile de la case vide ; nous traitons la case vide comme une seizième tuile, notée $b$ et identifiée au nombre $16$ . Une configuration est une bijection $\sigma \colon \intint1{16} \to \intint1{16}$ , case $\mapsto$ contenu ; la configuration résolue est $\sigma = \mathrm{id}$ . Partout, $\varepsilon$ est la signature du Théorème 1.21 et deux cases sont adjacentes lorsqu’elles partagent une arête du plateau.

Partie I — Configurations, coups, signatures.

Justifier que les configurations sont exactement les éléments de $\mathfrak{S}_{16}$ , donc qu’il y en a $16! = 20\,922\,789\,888\,000$ , et que le nombre de coups légaux depuis une configuration donnée est $2$ , $3$ ou $4$ , selon que la case vide se trouve dans un coin, sur un bord, ou à l’intérieur.
Soit $\sigma$ une configuration, $p = \sigma^{-1}(16)$ la case de la case vide, et $c$ une case adjacente à $p$ . Montrer que faire glisser la tuile de $c$ dans $p$ produit la configuration $\sigma' = \sigma \circ \tau$ avec $\tau = (p\ c)$ , et en déduire que tout coup change la signature de signe : $\varepsilon(\sigma') = -\varepsilon(\sigma)$ .
Colorions le plateau en damier : $\chi(k) = (-1)^{i+j}$ pour la case $k$ en ligne $i$ , colonne $j$ . Montrer que tout coup change $\chi(\text{case de la case vide})$ de signe, et en déduire qu’une suite de coups ramenant la case vide à sa case de départ est de longueur paire.
Montrer que

$I(\sigma) = \varepsilon(\sigma)\, \chi\bigl(\sigma^{-1}(16)\bigr)$

est invariant sous tout coup légal, et calculer $I(\mathrm{id})$ .

Partie II — La prime de Loyd : l’invariant à l’œuvre.

La configuration de Loyd $\sigma_L$ coïncide avec la configuration résolue sauf que les cases $14$ et $15$ portent les tuiles $15$ et $14$ . Calculer $I(\sigma_L)$ et conclure qu’aucune suite de coups ne relie $\sigma_L$ à la configuration résolue : les 1000$ de Loyd n’ont jamais couru le moindre risque.
Montrer qu’exactement la moitié des configurations vérifient $I = +1$ : $\abs{\{\sigma : I(\sigma) = +1\}} = 16!/2$ . (Pour une case vide fixée, apparier les configurations en composant avec une transposition fixée de deux autres cases.)
Montrer que tout coup est annulé par un coup légal, que « $\sigma'$ est atteignable depuis $\sigma$ par des coups légaux » est une relation d’équivalence, et que la classe $R$ de la configuration résolue vérifie $R \subseteq \{I = +1\}$ . Conclure qu’il y a au moins deux classes.
Supposons la case vide au domicile : $\sigma(16) = 16$ . Montrer que $I(\sigma) = \varepsilon(\rho)$ où $\rho \in \mathfrak{S}_{15}$ est la restriction de $\sigma$ aux cases $1, \dots, 15$ , et que toute configuration peut être amenée par des coups légaux à une configuration à case vide au domicile. Conclure : pour prouver $R = \{I = +1\}$ il suffit de réaliser toute permutation paire des quinze cases hors domicile par une suite de coups commençant et finissant avec la case vide au domicile.

Partie III — Tours de la case vide et groupe des programmes. Un programme est une suite finie de coups légaux, partant d’une configuration à case vide au domicile, dont la configuration finale a de nouveau la case vide au domicile. Son effet est la permutation $\pi$ des cases définie par : le contenu de la case $x$ finit dans la case $\pi(x)$ .

Montrer qu’un programme exécuté depuis $\sigma$ aboutit à $\sigma \circ \pi^{-1}$ ; qu’exécuter deux programmes l’un après l’autre compose leurs effets ; et que l’ensemble $H$ de tous les effets est un sous-groupe de $\mathfrak{S}_{15}$ (permutations des cases $1, \dots, 15$ ) contenu dans le groupe alterné $A_{15}$ .
(Le tour élémentaire) Depuis la case vide au domicile, faire tourner la case vide autour du bloc $2 \times 2$ en bas à droite : cases $16 \to 12 \to 11 \to 15 \to 16$ . Montrer que l’effet est le $3$ -cycle $(11\ 12\ 15)$ , et que le tour inverse donne $(11\ 15\ 12)$ . Les deux sont dans $H$ .
(Le grand tour) Vérifier que

$16 \to 15 \to 14 \to 13 \to 9 \to 5 \to 1 \to 2 \to 3 \to 4 \to 8 \to 7 \to 6 \to 10 \to 11 \to 12 \to 16$

est un chemin fermé parcourant les seize cases (à pas adjacents seulement), et que son effet est le $15$ -cycle

$\zeta = (15\ 12\ 11\ 10\ 6\ 7\ 8\ 4\ 3\ 2\ 1\ 5\ 9\ 13\ 14) .$

En écrivant $x_0 = 15$ , $x_1 = 12$ , $x_2 = 11$ , …, $x_{14} = 14$ pour son ordre cyclique, vérifier que le tour élémentaire inverse de la question 10 est exactement $(x_0\ x_1\ x_2)$ .
Démontrer la formule de conjugaison dans tout $\mathfrak{S}_n$ : pour une permutation $g$ et un $3$ -cycle,

$g\,(a\ b\ c)\,g^{-1} = \bigl(g(a)\ g(b)\ g(c)\bigr),$

et noter que $H$ , étant un groupe, est stable par conjugaison par ses propres éléments.
En déduire que $H$ contient les quinze $3$ -cycles consécutifs du grand tour :

$s_t = (x_t\ x_{t+1}\ x_{t+2}) \qquad (t \in \Z/15\Z, \text{ indices modulo } 15).$

Partie IV — Engendrer le groupe alterné.

(Lemme A) Soient $s$ et $t$ des $3$ -cycles dont les supports partagent exactement deux points, disons de supports $\{a, b, c\}$ et $\{b, c, d\}$ . Montrer que, quitte à remplacer $s$ ou $t$ par son inverse (ce qui ne change rien au sous-groupe engendré), le produit $st$ est une double transposition ; montrer que $A_4$ ne contient aucun sous-groupe d’ordre $6$ (un sous-groupe d’indice $2$ contient tous les carrés ; compter les $3$ -cycles parmi les carrés) ; et conclure que $\langle s, t\rangle$ est le groupe alterné tout entier des quatre lettres $\{a, b, c, d\}$ .
(Lemme B) Soit $X$ un ensemble de $k \geq 4$ lettres, $w \notin X$ , et soit $G$ un sous-groupe d’un certain $\mathfrak{S}_n$ contenant toute permutation paire de $X$ et un $3$ -cycle $(u\ v\ w)$ avec $u, v \in X$ . Montrer que pour tous $a, b \in X$ distincts il existe une permutation paire $g$ de $X$ avec $g(u) = a$ , $g(v) = b$ , et en déduire $(a\ b\ w) \in G$ .
En déduire que le groupe $G$ du lemme B contient toute permutation paire de $X \cup \{w\}$ (utiliser l’Exercice 1.6 : les $3$ -cycles engendrent). Puis, en enchaînant les lemmes A et B le long des $3$ -cycles consécutifs $s_0, s_1, \dots, s_{12}$ de la question 13, démontrer que $\langle s_0, \dots, s_{12}\rangle = A_{15}$ .
Conclure que $H = A_{15}$ : tout réarrangement pair des quinze tuiles est réalisable par un programme, et $H$ a $15!/2 = 653\,837\,184\,000$ éléments.
(Le théorème de Johnson–Story, 1879) Assembler les questions 6, 7, 8 et 17 : les configurations atteignables depuis la configuration résolue sont exactement les $16!/2 = 10\,461\,394\,944\,000$ configurations vérifiant $I = +1$ ; et l’atteignabilité a exactement deux classes, la classe de la configuration résolue et la classe du $\sigma_L$ de Loyd. (Pour le second point, renuméroter les tuiles $14$ et $15$ : montrer que $\sigma \mapsto (14\ 15) \circ \sigma$ envoie les suites de coups sur des suites de coups et échange $\{I = +1\}$ avec $\{I = -1\}$ .)

Partie V — Critères, variantes, et la vue d’en haut.

(Le critère pratique) Lire les quinze tuiles dans l’ordre de lecture de leurs cases, en sautant la case vide, et soit $N$ le nombre d’inversions de cette liste ; soit $r$ la ligne de la case vide comptée depuis le bas. Montrer que $I(\sigma) = (-1)^{N + r + 1}$ , de sorte que $\sigma$ est résoluble si et seulement si $N + r$ est impair.
(Actions de groupe) Une action d’un groupe $G$ sur un ensemble $X$ est une application $G \times X \to X$ , $(g, x) \mapsto g \cdot x$ , avec $e \cdot x = x$ et $g \cdot (h \cdot x) = (gh) \cdot x$ ; l’orbite de $x$ est $G \cdot x$ , et l’action est libre lorsque $g \cdot x = x$ force $g = e$ . Montrer que $h \cdot \sigma = \sigma \circ h^{-1}$ définit une action libre de $H$ sur l’ensemble des configurations à case vide au domicile, que ses orbites sont exactement les classes d’atteignabilité mutuelle par programmes, et retrouver, à partir du décompte des orbites, que ces configurations se répartissent en exactement $15!\,/\,\abs H = 2$ classes.
(L’obstruction $3 \times 3$ ) Montrer que le plateau $3 \times 3$ n’admet aucun chemin fermé visitant chaque case exactement une fois : la stratégie du grand tour de la partie III échoue pour le taquin à huit. (Colorier en damier les neuf cases.)
(La réparation) Sur le plateau $3 \times 3$ avec les cases $1$ à $9$ dans l’ordre de lecture et le domicile $9$ : calculer les effets du tour périmétrique $9 \to 8 \to 7 \to 4 \to 1 \to 2 \to 3 \to 6 \to 9$ (un $7$ -cycle $\zeta'$ fixant le centre $5$ ) et du tour de coin $9 \to 6 \to 5 \to 8 \to 9$ (un $3$ -cycle passant par le centre). En conjuguant le second par les puissances de $\zeta'$ et en enchaînant les lemmes A et B, démontrer que le groupe des programmes du taquin à huit est $A_8$ tout entier, donc qu’exactement $9!/2 = 181\,440$ des $9! = 362\,880$ configurations sont résolubles.
(Un plateau pauvre) Soit maintenant le plateau un unique cycle de $n \geq 4$ cases portant $n - 1$ tuiles. Montrer que l’ordre cyclique des tuiles est invariant, que chaque classe d’atteignabilité a exactement $n(n - 1)$ configurations (les classes sont les orbites d’un groupe cyclique d’ordre $\operatorname{lcm}(n, n-1) = n(n-1)$ ), et qu’il y a $(n - 2)!$ classes — pour $n \geq 5$ bien plus que $2$ : sur un plateau étroit l’invariant de parité ne capture presque rien, et la géométrie décide.
Deux verdicts par le critère de la question 19 : le plateau entièrement inversé (tuiles $15, 14, \dots, 1$ dans les cases $1$ à $15$ , case vide au domicile) et le plateau avec la case vide dans la case $1$ suivie des tuiles $15, 14, \dots, 1$ dans les cases $2$ à $16$ . Lequel est résoluble ?
(Synthèse) La démonstration a deux piliers indépendants : un invariant ( $I$ , construit à partir du morphisme signature) montrant qu’au plus la moitié des configurations sont atteignables, et un théorème de génération explicite ( $H = A_{15}$ ) montrant qu’au moins la moitié le sont. En une phrase chacun, dire où sont intervenus : la propriété de morphisme de $\varepsilon$ ; le théorème de Lagrange ; la génération de $A_n$ par les $3$ -cycles ; la conjugaison. Énoncer le méta-principe en une ligne.

Solution

Solution de Problème 1.1.

1. Une configuration attribue à chacune des $16$ cases l’un des $16$ contenus (tuiles $1$ – $15$ ou la case vide $b = 16$ ), chacun exactement une fois : précisément une bijection $\intint1{16} \to \intint1{16}$ , un élément de $\mathfrak{S}_{16}$ ; il y en a $16! = 20\,922\,789\,888\,000$ . Un coup légal fait glisser une tuile adjacente à la case vide, donc le nombre de coups est le nombre de voisines de la case de la case vide : $2$ pour les quatre cases de coin, $3$ pour les huit cases de bord, $4$ pour les quatre cases intérieures.

2. Après le glissement, la case $p$ porte l’ancien contenu de $c$ et la case $c$ porte la case vide ; toutes les autres cases sont inchangées : $\sigma'(p) = \sigma(c)$ , $\sigma'(c) = \sigma(p) = 16$ , $\sigma' = \sigma$ ailleurs. C’est exactement $\sigma' = \sigma \circ (p\ c)$ . Comme $\varepsilon$ est un morphisme et $\varepsilon\bigl((p\ c)\bigr) = -1$ : $\varepsilon(\sigma') = -\varepsilon(\sigma)$ .

3. Des cases adjacentes diffèrent d’un pas dans exactement l’une des deux coordonnées, donc $i + j$ change de parité : $\chi$ prend des valeurs opposées sur des cases adjacentes. Un coup transfère la case vide de $p$ à la case adjacente $c$ , changeant $\chi(\text{case de la case vide})$ de signe. Le long d’un chemin fermé de la case vide, $\chi$ change de signe une fois par coup et revient à sa valeur initiale : le nombre de coups est pair.

4. Par les questions 2 et 3, un coup change de signe les deux facteurs de $I(\sigma) = \varepsilon(\sigma)\chi(\sigma^{-1}(16))$ ; leur produit est inchangé. Pour la configuration résolue : $\varepsilon(\mathrm{id}) = +1$ et la case vide est à la case $16$ , ligne $4$ , colonne $4$ : $\chi(16) = (-1)^{8} = +1$ , donc $I(\mathrm{id}) = +1$ .

5. $\sigma_L$ est la transposition $(14\ 15)$ des cases : $\varepsilon(\sigma_L) = -1$ ; sa case vide est au domicile, $\chi(16) = +1$ : $I(\sigma_L) = -1 \neq +1 = I(\mathrm{id})$ . Comme $I$ est préservé par tout coup, aucune suite de coups ne relie $\sigma_L$ et $\mathrm{id}$ . Le prix était structurellement à l’abri.

6. Fixer une case $p$ et deux autres cases $c \neq d$ distinctes de $p$ , et poser $\tau_0 = (c\ d)$ . Sur l’ensemble des configurations à case vide en $p$ , l’application $\sigma \mapsto \sigma \circ \tau_0$ est une involution (elle préserve $\sigma(p) = 16$ puisque $\tau_0$ fixe $p$ ) et change $\varepsilon$ de signe, donc change $I$ de signe : elle apparie les configurations avec $I = +1$ bijectivement avec celles avec $I = -1$ . Donc chacune des $16$ positions de la case vide contribue $15!/2$ configurations avec $I = +1$ , et

\abs{\{I = +1\}} = 16 \cdot \frac{15!}{2} = \frac{16!}{2}.

7. Le coup faisant glisser la tuile de $c$ dans $p$ est annulé en faisant glisser cette même tuile (maintenant en $p$ ) de retour dans $c$ : composer deux fois avec $(p\ c)$ est l’identité. D’où : réflexivité (suite vide), symétrie (renverser la suite, en annulant chaque coup), transitivité (concaténer) : une relation d’équivalence. Tout $\sigma \in R$ a $I(\sigma) = I(\mathrm{id}) = +1$ par la question 4, donc $R \subseteq \{I = +1\}$ ; et $\sigma_L \notin R$ donne une seconde classe.

8. Si $\sigma(16) = 16$ , alors $\sigma$ permute les cases $1, \dots, 15$ ; appelons $\rho$ cette restriction. Ajouter un point fixe ne change ni le type de cycle ni la signature (décomposer $\rho$ en transpositions ; le même produit convient dans $\mathfrak{S}_{16}$ ), donc $\varepsilon(\sigma) = \varepsilon(\rho)$ , et $\chi(16) = +1$ donne $I(\sigma) = \varepsilon(\rho)$ . Toute configuration peut être amenée à une configuration à case vide au domicile : la grille est connexe, donc on promène la case vide le long d’un chemin de cases adjacentes jusqu’à la case $16$ (chaque pas est un coup légal). Supposons maintenant que tout $\rho \in \mathfrak{S}_{15}$ pair est réalisé par un programme. Étant donné $\sigma$ avec $I(\sigma) = +1$ : promener la case vide au domicile pour atteindre $\widetilde\sigma$ (équivalent à $\sigma$ ), avec $I(\widetilde\sigma) = +1$ , c.-à-d. sa restriction $\rho$ est paire ; le programme réalisant $\rho$ amène $\widetilde\sigma$ à $\widetilde\sigma \circ \rho^{-1} = \mathrm{id}$ (voir la question 9). Par transitivité $\sigma \in R$ , d’où $\{I = +1\} \subseteq R$ et l’égalité.

9. Coup isolé : le contenu de $c$ finit en $p$ et la case vide en $c$ : l’effet est $\pi = (p\ c)$ , et en effet $\sigma' = \sigma \circ (p\ c) = \sigma \circ \pi^{-1}$ . Récurrence : si une suite a pour effet $\pi_1$ et amène $\sigma$ à $\sigma \circ \pi_1^{-1}$ , la faire suivre d’un coup d’effet $\pi_2 = (p'\ c')$ donne $(\sigma \circ \pi_1^{-1}) \circ \pi_2^{-1} = \sigma \circ (\pi_2\pi_1)^{-1}$ , et les contenus se déplacent par $\pi_2 \circ \pi_1$ (d’abord $\pi_1$ , puis $\pi_2$ ). Donc les effets se composent, et un programme exécuté depuis $\sigma$ aboutit à $\sigma \circ \pi^{-1}$ . Sous-groupe : le programme vide a pour effet $\mathrm{id}$ ; la concaténation donne les produits ; renverser un programme (question 7) donne les inverses. L’effet d’un programme fixe la case $16$ (la case vide part et revient au domicile), donc $H \leq \mathfrak{S}_{15}$ . Parité : un programme de $k$ coups a $k$ pair (question 3), et $\varepsilon(\sigma \circ \pi^{-1}) = (-1)^k\varepsilon(\sigma)$ force $\varepsilon(\pi) = +1$ : $H \subseteq A_{15}$ .

10. Suivre les quatre glissements depuis la case vide en $16$ : le coup $16 \to 12$ envoie le contenu de $12$ en $16$ ; le coup $12 \to 11$ envoie le contenu de $11$ en $12$ ; le coup $11 \to 15$ envoie le contenu de $15$ en $11$ ; le coup $15 \to 16$ envoie le contenu garé en $16$ (venant à l’origine de $12$ ) en $15$ . Bilan : $11 \mapsto 12$ , $12 \mapsto 15$ , $15 \mapsto 11$ , case vide au domicile : l’effet est $(11\ 12\ 15)$ . Le tour inverse l’annule : effet $(11\ 12\ 15)^{-1} = (11\ 15\ 12)$ . Les deux sont des effets de programmes, donc dans $H$ .

11. Adjacence des cases consécutives : dans chaque paire listée les cases diffèrent de $1$ dans la même ligne ( $16{-}15$ , $15{-}14$ , $14{-}13$ ; $1{-}2$ , $2{-}3$ , $3{-}4$ ; $8{-}7$ , $7{-}6$ ; $10{-}11$ , $11{-}12$ ) ou de $4$ dans une colonne ( $13{-}9$ , $9{-}5$ , $5{-}1$ ; $4{-}8$ ; $6{-}10$ ; $12{-}16$ ) : un chemin fermé passant par les $16$ cases, de longueur $16$ . Effet : comme à la question 10, en écrivant les cases visitées $c_0 = 16, c_1 = 15, \dots, c_{15} = 12$ : le contenu de $c_i$ se déplace en $c_{i-1}$ pour $i = 2, \dots, 15$ , et le contenu de $c_1$ , garé en $16$ après le premier coup, est amené en $c_{15}$ par le dernier coup. Donc l’effet envoie $15 \mapsto 12$ , et $14 \mapsto 15$ , $13 \mapsto 14$ , $9 \mapsto 13$ , $5 \mapsto 9$ , $1 \mapsto 5$ , $2 \mapsto 1$ , $3 \mapsto 2$ , $4 \mapsto 3$ , $8 \mapsto 4$ , $7 \mapsto 8$ , $6 \mapsto 7$ , $10 \mapsto 6$ , $11 \mapsto 10$ , $12 \mapsto 11$ : exactement le $15$ -cycle $\zeta$ . Son ordre cyclique commence par $x_0 = 15$ , $x_1 = 12$ , $x_2 = 11$ , et $(x_0\ x_1\ x_2) = (15\ 12\ 11)$ envoie $15 \mapsto 12 \mapsto 11 \mapsto 15$ — ce qui est précisément $(11\ 15\ 12)$ , le tour élémentaire inverse.

12. Soit $\gamma = (a\ b\ c)$ et $x \in \intint1n$ . Si $x = g(a)$ : $g\gamma g^{-1}(x) = g(\gamma(a)) = g(b)$ ; de même $g(b) \mapsto g(c)$ et $g(c) \mapsto g(a)$ . Si $x \notin \{g(a), g(b), g(c)\}$ , alors $g^{-1}(x) \notin \{a,b,c\}$ est fixé par $\gamma$ , donc $x$ est fixé. Donc $g\gamma g^{-1} = (g(a)\ g(b)\ g(c))$ . Et pour $g, h \in H$ , $ghg^{-1} \in H$ par les axiomes de sous-groupe.

13. $\zeta \in H$ (question 11) et $s_0 = (x_0\ x_1\ x_2) \in H$ (questions 10–11). Comme $\zeta(x_i) = x_{i+1}$ (indices modulo $15$ ), la question 12 donne

\zeta^{t}\,s_0\,\zeta^{-t} = \bigl(\zeta^t(x_0)\ \zeta^t(x_1)\ \zeta^t(x_2)\bigr) = (x_t\ x_{t+1}\ x_{t+2}) = s_t \in H \qquad (t = 0, 1, \dots, 14).

14. Quitte à inverser, supposer $s = (a\ b\ c)$ et $t = (b\ c\ d)$ (un $3$ -cycle sur $\{a,b,c\}$ est $(a\ b\ c)$ ou son inverse ; de même sur $\{b,c,d\}$ ; remplacer un générateur par son inverse laisse $\langle s, t\rangle$ inchangé). Alors, en appliquant $t$ d’abord,

st \colon a \mapsto b,\quad b \mapsto a,\quad c \mapsto d,\quad d \mapsto c, \qquad\text{c.-à-d.}\quad st = (a\ b)(c\ d),

une double transposition. Le sous-groupe $G = \langle s, t\rangle$ est constitué de permutations paires des quatre lettres, donc $G \leq A_4$ et $\abs G \mid 12$ ; il contient un élément d’ordre $3$ et un d’ordre $2$ , donc $6 \mid \abs G$ (Lagrange, Théorème 1.14, appliqué aux deux sous-groupes cycliques). Si $A_4$ avait un sous-groupe $K$ d’ordre $6$ , il serait d’indice $2$ , et alors $g^2 \in K$ pour tout $g \in A_4$ : pour $g \in K$ c’est clair ; pour $g \notin K$ les seules classes sont $K$ et $gK$ , donc la classe $g^2K$ est $K$ ou $gK$ , et $g^2K = gK$ forcerait $g \in K$ . Donc tout carré est dans $K$ . Mais tout $3$ -cycle $\gamma$ est un carré, $\gamma = (\gamma^2)^2$ , et $A_4$ contient huit $3$ -cycles : $8 > 6$ , contradiction. Donc $\abs G = 12$ : $G = A_4$ .

15. Prolonger $u \mapsto a$ , $v \mapsto b$ en une bijection $g_0$ de $X$ (envoyer les $k - 2$ lettres restantes bijectivement n’importe où sur le complémentaire de $\{a, b\}$ ). Si $g_0$ est impaire, choisir deux lettres distinctes $s_1, t_1 \in X \setminus \{u, v\}$ (possible : $k \geq 4$ ) et remplacer $g_0$ par $g_0 \circ (s_1\ t_1)$ , qui est paire et envoie toujours $u \mapsto a$ , $v \mapsto b$ . Prolonger par l’identité hors de $X$ : une permutation paire $g \in G$ (c’est une permutation paire de $X$ ). Alors la question 12 :

g\,(u\ v\ w)\,g^{-1} = (g(u)\ g(v)\ g(w)) = (a\ b\ w) \in G,

en utilisant $g(w) = w$ .

16. Tout $3$ -cycle de $X \cup \{w\}$ est dans $G$ : ceux à support dans $X$ sont des permutations paires de $X$ ; un à support $\{a, b, w\}$ est $(a\ b\ w)$ ou $(b\ a\ w)$ , tous deux livrés par la question 15. Par l’Exercice 1.6, les $3$ -cycles de l’ensemble à $(k+1)$ éléments $X \cup \{w\}$ engendrent son groupe alterné, donc $G$ contient toute permutation paire de $X \cup \{w\}$ . Enchaînement : soit $G = \langle s_0, \dots, s_{12}\rangle$ . Le lemme A appliqué à $s_0 = (x_0\ x_1\ x_2)$ et $s_1 = (x_1\ x_2\ x_3)$ (supports partageant $\{x_1, x_2\}$ ) donne toutes les permutations paires de $X_4 = \{x_0, x_1, x_2, x_3\}$ . Si $G$ contient toutes les permutations paires de $X_m = \{x_0, \dots, x_{m-1}\}$ ( $4 \leq m \leq 14$ ), alors $s_{m-2} = (x_{m-2}\ x_{m-1}\ x_m)$ a $u = x_{m-2}, v = x_{m-1} \in X_m$ et nouvelle lettre $w = x_m$ : le lemme B et la première partie donnent toutes les permutations paires de $X_{m+1}$ . Récurrence jusqu’à $m = 14$ : $G \supseteq A_{15}$ (permutations paires des quinze cases), et $G \subseteq A_{15}$ puisque chaque $s_t$ est pair : $\langle s_0, \dots, s_{12}\rangle = A_{15}$ .

17. Questions 13 et 16 : $A_{15} = \langle s_0, \dots, s_{12}\rangle \subseteq H$ ; question 9 : $H \subseteq A_{15}$ . Donc $H = A_{15}$ , d’ordre $15!/2 = 653\,837\,184\,000$ : tout réarrangement pair des quinze tuiles est l’effet d’un programme.

18. La question 8 a réduit $R = \{I = +1\}$ à la réalisation de tout $\rho \in \mathfrak{S}_{15}$ pair par un programme : fait par la question 17. Avec la question 6, $\abs R = 16!/2 = 10\,461\,394\,944\,000$ . Deux classes : soit $t_0 = (14\ 15)$ agissant sur les contenus : $\varphi(\sigma) = t_0 \circ \sigma$ . Un coup légal depuis $\sigma$ est un coup légal depuis $\varphi(\sigma)$ (la case de la case vide est inchangée : $(t_0\sigma)^{-1}(16) = \sigma^{-1}(t_0(16)) = \sigma^{-1}(16)$ , et la case déplacée est la même), et $\varphi(\sigma \circ \tau) = \varphi(\sigma) \circ \tau$ : $\varphi$ envoie les suites de coups sur des suites de coups, bijectivement (c’est une involution). Elle change $I$ de signe : $\varepsilon(t_0\sigma) = -\varepsilon(\sigma)$ , même case de la case vide. Donc $\varphi$ envoie la classe $R = \{I = +1\}$ de $\mathrm{id}$ bijectivement sur la classe de $\varphi(\mathrm{id}) = \sigma_L$ , qui est donc tout $\{I = -1\}$ : exactement deux classes. C’est le théorème de Johnson–Story.

19. Indexer les cases dans l’ordre de lecture et soit $k = 4(i - 1) + j$ la case de la case vide. Compter les inversions de $\sigma$ (paires de cases $x < y$ avec $\sigma(x) > \sigma(y)$ ) : les paires de deux cases de tuiles contribuent $N$ ; les paires impliquant la case vide : les cases après la case vide portent toutes des tuiles $< 16$ , chacune inversée ( $16 - k$ paires), les cases avant elle ne sont jamais inversées. Donc $\varepsilon(\sigma) = (-1)^{N + 16 - k} = (-1)^{N + k}$ . Comme $k = 4(i-1) + j \equiv j \pmod 2$ ,

I(\sigma) = (-1)^{N + j}\,(-1)^{i + j} = (-1)^{N + i} = (-1)^{N + r + 1}

en utilisant $i = 5 - r$ . Par la question 18, $\sigma$ est résoluble si et seulement si $I(\sigma) = +1$ si et seulement si $N + r$ est impair. Vérification : résolu, $N = 0$ , $r = 1$ : impair, résoluble ; Loyd, $N = 1$ , $r = 1$ : pair, non résoluble.

20. Action : $e \cdot \sigma = \sigma \circ \mathrm{id} = \sigma$ et $g \cdot (h \cdot \sigma) = \sigma \circ h^{-1} \circ g^{-1} = \sigma \circ (gh)^{-1} = (gh) \cdot \sigma$ ; et $\sigma \circ h^{-1}$ est encore une configuration à case vide au domicile ( $h$ fixe la case $16$ ). Libre : $\sigma \circ h^{-1} = \sigma$ donne $h^{-1} = \mathrm{id}$ (composer avec $\sigma^{-1}$ ). Orbites = classes de programmes : la question 9 dit que les configurations atteignables depuis $\sigma$ par programmes sont exactement les $\sigma \circ \pi^{-1}$ , $\pi \in H$ : l’orbite $H \cdot \sigma$ . Décompte : la liberté rend $h \mapsto h \cdot \sigma$ injective, donc toute orbite a $\abs H = 15!/2$ éléments ; les $15!$ configurations à case vide au domicile se répartissent donc en $15!\,/\,(15!/2) = 2$ orbites — l’ombre à case vide au domicile des deux classes de Johnson–Story.

21. La grille $3 \times 3$ est bipartie pour le coloriage en damier : chaque pas d’un chemin change de couleur, donc tout chemin fermé est de longueur paire. Un chemin fermé visitant chacune des $9$ cases exactement une fois serait de longueur $9$ , impaire : impossible. La construction du grand tour de la partie III est donc indisponible sur le taquin à huit.

22. Tour périmétrique $9 \to 8 \to 7 \to 4 \to 1 \to 2 \to 3 \to 6 \to 9$ (tous les pas adjacents ; longueur $8$ , paire) : par la comptabilité de la question 11 avec $c_1 = 8, c_2 = 7, c_3 = 4, c_4 = 1, c_5 = 2, c_6 = 3, c_7 = 6$ , l’effet est

\zeta' = (8\ 6\ 3\ 2\ 1\ 4\ 7),

un $7$ -cycle fixant le centre $5$ (le contenu de $7$ se déplace en $8$ , de $4$ en $7$ , de $1$ en $4$ , de $2$ en $1$ , de $3$ en $2$ , de $6$ en $3$ , et de $8$ en $6$ ). Tour de coin $9 \to 6 \to 5 \to 8 \to 9$ : effet $(6\ 8\ 5)$ (le contenu de $5$ se déplace en $6$ , de $8$ en $5$ , de $6$ — garé en $9$ — en $8$ ). Poser $y_t = \zeta'^{\,t}(8)$ : $y_0 = 8, y_1 = 6, y_2 = 3, y_3 = 2, y_4 = 1, y_5 = 4, y_6 = 7$ . Conjugaison (question 12) :

\zeta'^{\,t}\,(6\ 8\ 5)\,\zeta'^{-t} = (y_{t+1}\ y_t\ 5) =: T_t \in H_{3\times3},

puisque $\zeta'$ fixe $5$ . Les supports de $T_0 = (y_1\ y_0\ 5)$ et $T_1 = (y_2\ y_1\ 5)$ partagent exactement $\{y_1, 5\}$ : le lemme A donne toutes les permutations paires de $\{y_0, y_1, y_2, 5\}$ . Puis $T_2 = (y_3\ y_2\ 5)$ adjoint $y_3$ par le lemme B (ses lettres $y_2, 5$ sont dans l’ensemble courant, $k = 4$ ), et $T_3, T_4, T_5$ adjoignent $y_4, y_5, y_6$ à leur tour : toutes les permutations paires des huit cases hors domicile sont dans le groupe des programmes, qui est aussi constitué de permutations paires (l’argument de la question 9 est indépendant du plateau). Donc $H_{3\times3} = A_8$ , et le raisonnement des questions 6, 8, 18 — lui aussi indépendant du plateau — montre que les configurations atteignables sont exactement celles avec $I = +1$ : la moitié de $9!$ , soit $181\,440$ .

23. Étiqueter les cases $0, \dots, n-1$ autour du cycle. Un coup échange la case vide avec l’une de ses deux voisines. Lire les tuiles dans l’ordre cyclique en partant juste après la case vide : un mot $w$ listant les $n - 1$ tuiles. Déplacer la case vide d’un pas en avant remplace $(p, w)$ par $(p + 1, \rho w)$ , où $p$ est la case de la case vide et $\rho$ fait tourner cycliquement le mot d’un cran ; le coup en arrière est l’inverse. L’ordre cyclique des tuiles (le mot à rotation près) est donc invariant. La classe atteignable de $(p, w)$ est l’orbite de l’application $g \colon (p, w) \mapsto (p+1, \rho w)$ , un élément d’ordre $\operatorname{lcm}(n, n-1) = n(n-1)$ dans le produit des deux groupes cycliques (translations de $\Z/n\Z$ et rotations des $n-1$ positions du mot), le ppcm valant $n(n-1)$ car $\gcd(n, n-1) = 1$ : chaque classe a exactement $n(n-1)$ configurations, toutes avec le même collier. Classes : $n!\,/\,\bigl(n(n-1)\bigr) = (n-2)!$ . Pour $n \geq 5$ , $(n-2)! > 2$ : l’invariant de parité (deux classes au mieux) est aveugle à presque toute l’obstruction ; la richesse du plateau $4 \times 4$ — où la parité est la seule obstruction — est un fait véritablement géométrique, pas formel.

24. Les deux plateaux ont les tuiles en ordre entièrement inversé, donc $N = \binom{15}{2} = 105$ dans les deux cas (toute paire de tuiles est inversée). Case vide au domicile : $r = 1$ , $N + r = 106$ pair : non résoluble. Case vide dans la case $1$ : la case vide est dans la ligne du haut, $r = 4$ , $N + r = 109$ impair : résoluble. Deux plateaux qui ne diffèrent que par l’emplacement du trou tombent de part et d’autre du mur.

25. Propriété de morphisme : elle convertit « un coup = une transposition » en « un coup = un changement de signe » (questions 2, 4), rendant $I$ calculable coup par coup. Lagrange : il a forcé $6 \mid \abs{\langle s, t\rangle}$ dans le lemme A et a dimensionné les classes dans l’exclusion de l’ordre $6$ (question 14). Génération par les $3$ -cycles : elle a converti « $H$ contient assez de $3$ -cycles » en « $H$ contient tout $A_{15}$ » (question 16). Conjugaison : elle a fabriqué les quinze $3$ -cycles consécutifs à partir d’un seul tour $2 \times 2$ transporté par le grand tour (questions 12–13), et les $3$ -cycles $(a\ b\ w)$ du lemme B. Méta-principe : un invariant démontre l’impossibilité, une construction explicite démontre la possibilité, et un problème est entièrement résolu exactement lorsque les deux bornes se rejoignent — ici, à une moitié.