Exercice 69

1. Le sous-groupe engendré par $\sigma$ est le plus petit sous-groupe de $\mathfrak{S}_{n}$ qui contient $\sigma$ (chapitre 11, remarque qui suit la proposition 8). C'est $H = \{\sigma^{k} \mid k \in \mathbb{Z}\}$ : cet ensemble contient $\sigma$, il est un sous-groupe, puisque $\mathrm{id} = \sigma^{0}$ et $\sigma^{a}(\sigma^{b})^{-1} = \sigma^{a-b}$, et tout sous-groupe qui contient $\sigma$ contient ses puissances. Pour $x \in \llbracket 1\,,n \rrbracket$, l'ensemble $\{h(x) \mid h \in H\} = \{\sigma^{k}(x) \mid k \in \mathbb{Z}\}$ est donc l'orbite de $x$ sous $\sigma$ au sens du chapitre 17 (démonstration du théorème 1). Le sous-groupe $H$ est transitif si et seulement si l'orbite de $1$ est $\llbracket 1\,,n \rrbracket$ tout entier, c'est-à-dire si $\sigma$ n'a qu'une orbite, sur laquelle elle agit comme un cycle : $$\boxed{\langle \sigma \rangle \text{ est transitif} \iff \sigma \text{ est un cycle de longueur } n}$$

2. Un cycle de longueur $n$ s'écrit de façon unique $(1\ a_{2}\ \cdots\ a_{n})$ en le commençant par $1$, avec $a_{k} = \sigma^{k-1}(1)$ ; la liste $(a_{2}, \dots, a_{n})$ est une permutation de $\llbracket 2\,,n \rrbracket$, et toute telle liste définit un cycle de longueur $n$. Il y a donc $(n - 1)!$ cycles de longueur $n$ (théorème 1), et, la loi de $X_{n}$ étant uniforme, $$\boxed{p_{n} = \frac{(n - 1)!}{n!} = \frac{1}{n}}$$ Une permutation aléatoire n'engendre presque jamais un sous-groupe transitif quand $n$ est grand.

3. (a) Notons $H$ le sous-groupe engendré par $X_{n}$ et $Y_{n}$, pour une issue fixée.

Supposons $H$ non transitif : il existe $x$, $y$ tels que $h(x) \neq y$ pour tout $h \in H$. Soit $O$ l'ensemble des $h(x)$, pour $h \in H$ ; il contient $x = \mathrm{id}(x)$ et pas $y$. Pour $h \in H$, $X_{n}h \in H$, donc $X_{n}(O) \subset O$ ; comme $X_{n}$ est injective et $O$ fini, $X_{n}(O)$ a autant d'éléments que $O$, et $X_{n}(O) = O$. De même $Y_{n}(O) = O$. Le complémentaire $O' = \llbracket 1\,,n \rrbracket \setminus O$ vérifie aussi $X_{n}(O') = O'$ et $Y_{n}(O') = O'$, puisque $X_{n}$ et $Y_{n}$ sont des bijections de $\llbracket 1\,,n \rrbracket$. Les parties $O$ et $O'$ sont non vides, l'une contenant $x$ et l'autre $y$, et leurs cardinaux ont pour somme $n$ : l'une d'elles, que l'on note $A$, vérifie $1 \leqslant |A| \leqslant \frac{n}{2}$.

Réciproquement, soit $A$ une telle partie. L'ensemble $K = \{g \in \mathfrak{S}_{n} \mid g(A) = A\}$ est un sous-groupe de $\mathfrak{S}_{n}$ : il contient $\mathrm{id}$, et si $g(A) = h(A) = A$, alors $h^{-1}(A) = A$ et $gh^{-1}(A) = A$. Il contient $X_{n}$ et $Y_{n}$, donc il contient $H$. Soit $x \in A$ et $y \notin A$, qui existe puisque $|A| \leqslant \frac{n}{2} < n$ : pour tout $h \in H$, $h(x) \in A$, donc $h(x) \neq y$, et $H$ n'est pas transitif. $$\boxed{H \text{ non transitif} \iff \exists A \subset \llbracket 1\,,n \rrbracket,\ 1 \leqslant |A| \leqslant \tfrac{n}{2},\ X_{n}(A) = A \text{ et } Y_{n}(A) = A}$$

(b) Une permutation $\sigma$ vérifie $\sigma(A) = A$ si et seulement si elle induit une permutation de $A$ et une permutation de $\llbracket 1\,,n \rrbracket \setminus A$ ; elle est déterminée par ce couple, et tout couple convient. Il y a donc $k!\,(n - k)!$ telles permutations, et $$\boxed{\mathrm{P}\big(X_{n}(A) = A\big) = \frac{k!\,(n - k)!}{n!} = \binom{n}{k}^{-1}}$$

(c) Par indépendance de $X_{n}$ et $Y_{n}$ (définition de la section 21.5.5, avec la partie $\{\sigma \mid \sigma(A) = A\}$ de $\mathfrak{S}_{n}$), $\mathrm{P}\big(X_{n}(A) = A, Y_{n}(A) = A\big) = \tbinom{n}{k}^{-2}$ pour $|A| = k$. Par la question (a), l'événement « $H$ n'est pas transitif » est la réunion de ces événements, sur les parties $A$ telles que $1 \leqslant |A| \leqslant \frac{n}{2}$. La sous-additivité (proposition 7 (iv)), en regroupant les $\tbinom{n}{k}$ parties de cardinal $k$, donne $$1 - q_{n} \leqslant \sum_{k=1}^{\lfloor n/2 \rfloor} \binom{n}{k}\binom{n}{k}^{-2}, \qquad \boxed{1 - q_{n} \leqslant \sum_{k=1}^{\lfloor n/2 \rfloor} \binom{n}{k}^{-1}}$$ Soit $n \geqslant 4$. Le rapport $\tbinom{n}{k+1}\big/\tbinom{n}{k} = \frac{n - k}{k + 1}$ est au moins égal à $1$ pour $k \leqslant \frac{n - 1}{2}$ : les coefficients binomiaux croissent jusqu'à l'indice $\lfloor\frac{n}{2}\rfloor$, et $\tbinom{n}{k} \geqslant \tbinom{n}{2} = \frac{n(n - 1)}{2}$ pour $2 \leqslant k \leqslant \lfloor\frac{n}{2}\rfloor$. Il y a au plus $\frac{n}{2}$ tels indices, d'où $$0 \leqslant 1 - q_{n} \leqslant \frac{1}{n} + \frac{n}{2} \times \frac{2}{n(n - 1)} = \frac{1}{n} + \frac{1}{n - 1}, \qquad\text{donc}\qquad \boxed{q_{n} \xrightarrow[n \to +\infty]{} 1}$$ L'énumération exhaustive des couples donne $q_{2} = \frac{3}{4}$, $q_{3} = \frac{13}{18}$, $q_{4} = \frac{71}{96}$ et $q_{5} = \frac{461}{600}$, en accord avec la majoration ✓.

À retenir. Une permutation seule engendre un sous-groupe transitif avec une probabilité $\frac{1}{n}$ qui tend vers $0$ ; deux permutations le font avec une probabilité qui tend vers $1$. La méthode est typique : on caractérise le mauvais événement comme une réunion d'événements simples, puis la sous-additivité, grossière mais sans hypothèse, suffit à montrer qu'il est rare.