\ifx\danslelivre\undefined \documentclass[9pt]{../configuration/smfart} \input{../configuration/commun} \input{../configuration/smf} \input{../configuration/adresse} \input{../configuration/gadgets} \input{../configuration/francais} \input{../configuration/numerotation} \input{../configuration/formules} \input{../configuration/encoredesmacros} \usepackage{stmaryrd} \usepackage{graphics} \usepackage[usenames,dvipsnames]{xcolor} \usepackage{srcltx} \externaldocument{correspondance-galois} \externaldocument{exemples-galois} \title{Algorithmes de calcul} \begin{document} \maketitle \setcounter{tocdepth}{2} \tableofcontents \else \chapter{Algorithmes de calcul} \fi \section{Algorithmes généraux} Nous nous attachons dans ce chapitre à présenter certaines des techniques permettant de calculer, de façon effective, le groupe de Galois d'un polynôme. Dans un premier temps, nous exposerons certaines techniques complètement générales prouvant que le problème (de déterminer le groupe de Galois d'un polynôme, disons, sur $\QQ$) est au moins théoriquement algorithmique (c'est-à-dire, décidable au sens de Church-Turing), même si ces algorithmes tout à fait généraux sont inutilisables dans la pratique en raison de leur complexité. \subsection{La méthode de Kronecker} Le résultat suivant, dû à Kronecker, ramène la détermination d'un groupe de Galois à la factorisation d'un polynôme. \begin{proposition2} Soit $f = X^d + a_1 X^{d-1} + \cdots + a_d \in K[X]$ un polynôme (unitaire, de degré $d$) séparable à coefficients dans un corps $K$, et $\xi_1,\ldots,\xi_d$ ses racines dans son corps de décomposition noté $L$ (de sorte que $f = \prod_{i=1}^d (X-\xi_i)$). On définit la \emph{résolvante de Kronecker} de $f$ comme \[ s = \prod_{\sigma\in\mathfrak{S}_d} \Big(X-\sum_{i=1}^d Y_i \xi_{\sigma(i)}\Big) \in L[X, Y_1,\ldots,Y_d] \] Ce polynôme $s$ est, en fait, à coefficients dans $K$, et il est invariant par $\mathfrak{S}_d$ agissant par permutation sur les variables $Y_1,\ldots,Y_d$. Soit $h$ un facteur irréductible quelconque de $s$ dans $K[X, Y_1,\ldots,Y_d]$, choisi unitaire comme polynôme en $X$ ; et soit $S_h$ le sous-groupe de $\mathfrak{S}_d$ formé des permutations $\sigma\in\mathfrak{S}_d$ (permutant les $Y_i$) qui laissent $h$ invariant. Alors $S_h$ est conjugué, dans $\mathfrak{S}_d$, au groupe de Galois $G = \Gal(L/K)$ de $f$ sur $K$ vu comme un groupe de permutations sur $\{\xi_i\}$. \end{proposition2} \begin{proof} Remarquons tout d'abord que les facteurs $X-\sum_{i=1}^d Y_i \xi_{\sigma(i)}$, étant linéaires, sont irréductibles dans $L[X,Y_1,\ldots,Y_d]$, donc l'expression définissant $s$ donne exactement sa décomposition en facteurs irréductibles dans $L[X,Y_1,\ldots,Y_d]$. La même chose vaudra pour n'importe quel produit de tels facteurs (et en particulier pour le polynôme $g$ défini ci-dessous). Le polynôme $s$ est, par construction, totalement invariant par n'importe quelle permutation $\sigma\in\mathfrak{S}_d$ des $\xi_i$, et notamment par l'action du groupe de Galois $G \leq \mathfrak{S}_d$ de $f$. Il s'ensuit que $s$ est à coefficients dans le corps fixe par $G$ dans $L$, c'est-à-dire $K$ ; cette même remarque prouve aussi que le polynôme $g$ défini par $g = \prod_{\sigma\in G} \big(X-\sum_{i=1}^d Y_i \xi_{\sigma(i)}\big)$ est aussi à coefficients dans $K$ (et c'est manifestement un facteur de $s$). Ici, on a identifié $G$ à un sous-groupe de $\mathfrak{S}_d$ au moyen de la numérotation choisie pour les racines, c'est-à-dire en posant $\xi_{\sigma(i)} = \sigma(\xi_i)$. Comme $\sum_{i=1}^d Y_i \xi_{\sigma(i)} = \sum_{i=1}^d Y_{\sigma^{-1}(i)} \xi_i$, on peut encore réécrire $s$ comme $s = \prod_{\sigma\in\mathfrak{S}_d} \big(X-\sum_{i=1}^d Y_{\sigma(i)} \xi_{i}\big)$, donc $s$ est bien invariant par l'action de $\mathfrak{S}_d$ qui permute les variables $Y_1,\ldots,Y_d$. Pour ce qui est de $g$, il est pour la même raison fixé au moins par l'action de $G$ sur les $Y_i$ (soulignons on a identifié $G$ à un sous-groupe de $\mathfrak{S}_d$). Pour montrer qu'il n'est pas fixé par plus (c'est-à-dire que $S_g = G$ exactement), on observe que si un $\tau\in \mathfrak{S}_d$ laisse $g$ invariant (en agissant par permutation sur les $Y_i$), il doit permuter les facteurs irréductibles de $g$ dans $L[X,Y_1,\ldots,Y_d]$, et notamment il envoie $X-\sum_{i=1}^d Y_i \xi_i$ sur $X-\sum_{i=1}^d Y_i \xi_{\tau^{-1}(i)}$ ce qui prouve que $\tau \in G$. Dans $L[X,Y_1,\ldots,Y_d]$, on a signalé que les facteurs irréductibles de $s$ sont donnés exactement par les $X-\sum_{i=1}^d Y_i \xi_{\sigma(i)}$. En particulier, la factorisation de $h$ doit être donnée par un sous-ensemble de ces facteurs ; quitte à permuter les variables $Y_i$ (ce qui revient à conjuguer le sous-groupe $S_h$ à l'intérieur de $\mathfrak{S}_d$), on peut supposer que $h$ comporte le facteur $X-\sum_{i=1}^d Y_i \xi_i$ (correspondant à $\sigma = \Id$). On cherche alors à prouver que $S_h = G$. Étant donné que $h$ est à coefficients dans $K$, il est invariant par l'action de $G$ agissant sur les $\xi_i$ : puisque $h$ comporte le facteur $X-\sum_{i=1}^d Y_i \xi_i$, il est aussi divisible par tous les facteurs $X-\sum_{i=1}^d Y_i \xi_{\sigma(i)}$ avec $\sigma \in G$, c'est-à-dire que $g$ divise $h$ (dans $L[X,Y_1,\ldots,Y_d]$ mais donc aussi dans $K[X,Y_1,\ldots,Y_d]$, où ces deux polynômes vivent). Or $h$ était supposé irréductible (dans $K[X,Y_1,\ldots,Y_d]$), et tous deux sont unitaires, donc $g=h$ et $S_h=S_g=G$. \end{proof} \begin{remarques2} \begin{itemize} \item La démonstration ci-dessus décrit exactement la décomposition en facteurs irréductibles de $s$ dans $K[X,Y_1,\ldots,Y_d]$ : ce sont les $\tau(g) = \prod_{\sigma\in G\tau^{-1}} \big(X-\sum_{i=1}^d Y_i \xi_{\sigma(i)}\big)$, où $G\tau^{-1}$ parcourt les classes à gauche de $G$ dans $\mathfrak{S}_d$. \item Si on sait déjà que le groupe de Galois de $G$ est contenu dans un certain sous-groupe $\mathfrak{G}$ de $\mathfrak{S}_d$, l'énoncé reste vrai en utilisant la résolvante $s_{\mathfrak{G}} = \prod_{\sigma\in\mathfrak{G}} \Big(X-\sum_{i=1}^d Y_i \xi_{\sigma(i)}\Big) \in L[X, Y_1,\ldots,Y_d]$ au lieu de $s$ (ceci ne possède d'intérêt algorithmique, toutefois, que si on sait exprimer comme éléments de $K$ les polynômes $\mathfrak{G}$-invariants des $\xi_i$, cf. ci-dessous). Toutefois, il faut se garder de croire que le fait que le $s_{\mathfrak{G}}$ défini ci-dessus soit dans $K[X,Y_1,\ldots,Y_d]$ suffise à impliquer que $\mathfrak{G}$ contienne le (ou un conjugué du) groupe de Galois de $G$. En effet, si $\mathfrak{G}$ est l'intersection de tous les conjugués $\sigma G \sigma^{-1}$ de $G$ dans $\mathfrak{S}_d$, alors $s_{\mathfrak{G}}$ est le pgcd des $s_{\sigma G \sigma^{-1}}$ qui appartiennent tous à $K[X,Y_1,\ldots,Y_d]$, donc il est bien à coefficients dans $K$, et pourtant ce $\mathfrak{G}$ peut être strictement plus petit que tout conjugué $\sigma G \sigma^{-1}$ de $G$. \XXX (Je ne dis pas des bêtises, là ?) \item Le calcul explicite de $s$ est, au moins en principe, algorithmique à partir de la connaissance de $f$ : on peut, par exemple, calculer le polynôme « universel » \[ \Upsilon := \prod_{\sigma\in\mathfrak{S}_d} \Big(X-\sum_{i=1}^d Y_i Z_{\sigma(i)}\Big) \in \ZZ[X,Y_1,\ldots,Y_d,Z_1,\ldots,Z_d] \] qui est totalement symétrique dans les variables $Z_1,\ldots,Z_d$ et s'écrit donc, et de façon algorithmique, comme polynôme (à coefficients dans $\ZZ[X,Y_1,\ldots,Y_d]$) dans les fonctions symétriques élémentaires $\sigma_j$ en les $Z_i$ (soit $\sigma_1=Z_1+\cdots+Z_d$, $\sigma_2=\sum_{\alpha<\beta} Z_\alpha Z_\beta$, ..., $\sigma_d=Z_1\cdots Z_n$) ; en substituant $(-1)^i a_i$ (les coefficients de $f$, au signe près) à $\sigma_i$ dans $\Upsilon$ on obtient précisément le polynôme $s$. \end{itemize} \end{remarques2} \begin{exemple2} Soit $f = X^3 + X^2 - 2 X - 1$ (cf. \refext{ExG}{exemple-galois-cubique-cyclique}). On peut alors vérifier que \[ \begin{array}{r@{}l} s =& \phantom{\cdot}\Big(X^3 + (Y_1+Y_2+Y_3) X^2\\ & \mskip25mu + \big(-2(Y_1^2+Y_2^2+Y_3^2) + 3(Y_1Y_2 + Y_2Y_3 + Y_3Y_1)\big) X\\ & \mskip25mu + \big(-(Y_1^3+Y_2^3+Y_3^3) - 3(Y_1^2 Y_2 + Y_2^2 Y_3 + Y_3^1 Y_1)\\ & \mskip50mu + 4(Y_1 Y_2^2 + Y_2 Y_3^2 + Y_3 Y_1^2) + Y_1 Y_2 Y_3\big)\Big)\\ & \cdot\Big(X^3 + (Y_1+Y_2+Y_3) X^2\\ & \mskip25mu + \big(-2(Y_1^2+Y_2^2+Y_3^2) + 3(Y_1Y_2 + Y_2Y_3 + Y_3Y_1)\big) X\\ & \mskip25mu + \big(-(Y_1^3+Y_2^3+Y_3^3) + 4(Y_1^2 Y_2 + Y_2^2 Y_3 + Y_3^1 Y_1)\\ & \mskip50mu - 3(Y_1 Y_2^2 + Y_2 Y_3^2 + Y_3 Y_1^2) + Y_1 Y_2 Y_3\big)\Big)\\ \end{array} \] L'existence de cette factorisation prouve que le groupe de Galois de $f$ est contenu dans $\ZZ/3\ZZ$ opérant cycliquement sur les racines ; et le fait que ces deux facteurs soient irréductibles est équivalent au fait que le groupe de Galois de $f$ n'est pas strictement plus petit (c'est-à-dire, que $f$ n'est pas scindé). \end{exemple2} Il résulte de ce qui précède que, dès lors que le corps $K$ est tel qu'on sache algorithmiquement faire des calculs dans $K$ et factoriser en irréductibles les polynômes à plusieurs variables à coefficients dans $K$, il est également possible algorithmiquement de calculer le groupe de Galois d'un polynôme à coefficients dans $K$. La proposition suivante justifie que c'est le cas pour $\QQ$ ainsi que pour tout corps pour lequel on sait (faire des calculs et) factoriser les polynômes à une seule indéterminée. \begin{proposition2}\label{factorisation-des-polynomes-est-algorithmique} Les problèmes suivants sont résolubles algorithmiquement (i.e., décidables au sens de Church-Turing) : \begin{itemize} \item Décomposer un élément de $\QQ[X]$ en facteurs irréductibles. \item Décomposer un élément de $K[T_1,\ldots,T_n]$ en facteurs irréductibles, en supposant algorithmiques les opérations dans $K$ et le fait de décomposer un élément de $K[X]$ en facteurs irréductibles. \end{itemize} \end{proposition2} \begin{proof} Commençons par considérer le problème de la factorisation dans $\ZZ[X]$. On peut supposer que le polynôme $f$ à factoriser est primitif (c'est-à-dire de contenu $1$, le contenu étant le pgcd de ses coefficients), ce qui écarte les facteurs constants. Il s'agit alors, pour chaque $k > 0$ inférieur au degré de $f$, de décider si $f$ possède un facteur de degré $k$ et le cas échéant de le calculer. On calcule $f(0),\ldots,f(k)$ et, pour chaque choix $(d_0,\ldots,d_k)$ de diviseurs des entiers $(f(0),\ldots,f(k))$, on calcule l'unique polynôme $g \in \QQ[X]$ de degré $k$ tel que $g(0) = d_0$, ..., $g(k) = d_k$ (polynôme interpolateur de Lagrange), et, si $g \in \ZZ[X]$, on teste si $g$ divise $f$. Si un diviseur de $f$ existe, il sera nécessairement trouvé par cet algorithme. Le cas de $\QQ[X]$ découle de $\ZZ[X]$ : si $f \in \QQ[X]$, on peut écrire $f = c f_1$ où $c \in \QQ$ et $f_1 \in\ZZ[X]$ est primitif. Les facteurs irréductibles de $f$ sont alors ceux de $f_1$. \XXX Montrons maintenant que la connaissance d'un algorithme de factorisation pour une seule variable permet, en principe, de factoriser les polynômes à plusieurs variables. Donné $f \in K[T_1,\ldots,T_n]$, on choisit $e$ un entier strictement supérieur au degré de $f$ dans n'importe laquelle des variables $T_i$ et on calcule $S_e(f) := f(X,X^e,X^{e^2},\ldots,X^{e^{n-1}}) \in K[X]$. Si $f$ possède un facteur $g$ non-trivial, alors manifestement $S_e(g)$ divise $S_e(f)$. Supposant qu'on sait factoriser le polynôme univarié $S_e(f)$, on peut vérifier pour chacun de ses facteurs s'il est susceptible de s'écrire sous la forme $S_e(g)$ avec $g$ de degré inférieur à $e$ en chaque variable : le polynôme $g$ se retrouve de façon unique en remplaçant chaque monôme $X^{i_0 + i_1 e + i_2 e^2 + \cdots + i_{n-1} e^{n-1}}$ (l'exposant étant écrit en base $e$) par $T_1^{i_0} \cdots T_n^{i_{n-1}}$ ; on teste alors si $g$ divise $f$. Si un diviseur de $f$ existe, il sera nécessairement trouvé par cet algorithme. \end{proof} \XXX --- Faut-il mentionner ici le fait qu'une extension algébrique finie séparable (par un polynôme explicite) d'un corps dans lequel on sait algorithmiquement factoriser les polynômes possède la même propriété ? (Cf.  Fried \& Jarden, lemme 19.2.2.) En revanche, sans supposer l'extension séparable, ce n'est pas vrai en général : cf. Fröhlich \& Shepherdson, « Effective Procedures in Field Theory », \textit{Phil. Trans. R. Soc. A} \textbf{248} (1956) 407--432, théorème 7.27. \subsection{Factorisations successives} \XXX À écrire : on peut calculer le groupe de Galois d'un polynôme en factorisant successivement dans tous les corps de rupture possibles. \section{Transformations de Tschirnhaus} \subsection{Généralités} \begin{definition2}\label{definition-transformation-de-tschirnhaus} Soit $P \in k[X]$ un polynôme unitaire à coefficients dans un corps $k$ : on notera $k(x) = k[X]/(P)$ l'algèbre quotient, où $x$ désigne la classe dans $k[X]/(P)$ de l'indéterminée $X$. On appelle \emph{transformation de Tschirnhaus} sur $P$ un élément $y$ de $k(x)$ dont le polynôme minimal $Q$ sur $P$ soit du même degré que $P$ --- c'est-à-dire que les puissances $1,y,y^2,\ldots,y^{\deg P-1}$ forment une base de la $k$-algèbre $k(x)$ de dimension $\deg P$. On représentera la transformation sous la forme $U(x)$ avec $U \in k[X]$ un polynôme (considéré modulo $P$) qui sera souvent par abus de langage identifié avec la transformation de Tschirnhaus elle-même. Le polynôme minimal unitaire $Q$ de $U(x)$ sur $k$ (dont le degré est, par hypothèse, le même que $P$) sera qualifié de polynôme obtenu à partir de $P$ par la transformation de Tschirnhaus définie par $U$, ou de polynôme \emph{transformé} de $P$ par la transformation $U$. Si $U$ est une fraction rationnelle dont le dénominateur est premier avec $P$, ce qui donne un sens à l'élément $U(x)$ de $k(x)$, on pourra aussi considérer $U$ comme représentant une transformation de Tschirnhaus sur $P$, à savoir celle définie par l'élément $y = U(x)$ (à condition que son polynôme minimal soit de degré $\deg P$). \end{definition2} Le cas le plus important, qu'il faut avoir à l'esprit dans ce qui suit, est celui où $P$ est irréductible, auquel cas une transformation de Tschirnhaus sur $P$ équivaut à la donnée d'un élément primitif du corps de rupture $k(x)$ de $P$, c'est-à-dire un élément engendrant celui-ci (i.e., de degré $\deg P$). Remarquons d'ores et déjà que dans ce cas, le polynôme $Q$ transformé est nécessairement lui aussi irréductible (puisque c'est le polynôme minimal d'un élément dans un corps). \begin{exemples2}\label{exemples-transformations-de-tschirnhaus} \begin{itemize} \item Soit $P = X^3 - 2 \in \QQ[X]$, dont on note $\root3\of2$ la racine dans le corps de rupture. Le polynôme $U = X+1$ définit une transformation de Tschirnhaus sur $P$ car $\root3\of2 + 1$ est encore de degré $3$ sur $\QQ$ : son polynôme minimal est $Q = (X-1)^3-2 = X^3 - 3X^2 + 3X - 3$ (c'est donc le polynôme obtenu à partir de $P = X^3 - 2$ par la transformation de Tschirnhaus définie par $U = X + 1$). Le polynôme $U = X^2$ définit lui aussi une transformation de Tschirnhaus sur $P$ : le polynôme minimal de $\root3\of4$ est $Q = X^3 - 4$, qui est donc le polynôme obtenu à partir de $P = X^3 - 2$ par la transformation de Tschirnhaus définie par $U = X^2$. La fraction rationnelle $U = \frac{1}{X}$ définit encore une transformation de Tschirnhaus sur $P$, qui transforme ce dernier en $Q = X^3 - \frac{1}{2}$. En revanche, le polynôme $X^3 + 1$ ne définit pas une transformation de Tschirnhaus sur $P$, car $(\root3\of2)^3 + 1 = 3 \in \QQ$. \item Soit $P = \prod_{i=1}^d (X-\xi_i) \in k[X]$ un polynôme unitaire scindé et séparable de degré $d$ dont on note $\xi_1,\ldots,\xi_d$ les racines deux à deux distinctes dans le corps $k$. Alors l'algèbre quotient $k[X]/(P)$ est isomorphe au produit $k^d$ de $d$ copies du corps $k$ (l'isomorphisme envoyant un polynôme $U$ considéré modulo $P$ sur l'ensemble $(U(\xi_1),\ldots,U(\xi_d))$ de ses valeurs sur les $\xi_i$, cf. par exemple \refext{Spec}{lemme chinois}) ; la condition traduisant le fait que $U$ définisse bien une transformation de Tschirnhaus sur $P$ est la non annulation du déterminant de Vandermonde défini par les $U(\xi_1),\ldots,U(\xi_d)$, c'est-à-dire simplement le fait que ces valeurs soient deux à deux distinctes. Le polynôme transformé est alors simplement $Q = \prod_{i=1}^d (X-U(\xi_i))$. \item Soit $P = X^d \in k[X]$, et considérons un polynôme $U(X) = c_0 + c_1 X + c_2 X^2 + \cdots + c_{d-1} X^{d-1}$. Demandons-nous à quelle condition $U(X)$ définit une transformation de Tschirnhaus sur $P$, c'est-à-dire à quelle condition les éléments $1, U(x), U(x)^2, \ldots, U(x)^{d-1}$ de $k(x) = k[X]/(X^d)$ en forment une base. Supposons d'abord $c_0 = 0$. Lorsque $c_1 \neq 0$, les polynômes $1, U(x), U(x)^2, \ldots, U(x)^{d-1}$ (considérés modulo $X^d$) sont échelonnés en valuation (c'est-à-dire que leur expression dans la base $1,x,x^2,\ldots,x^{d-1}$ de $k[X]/(X^d)$ forme une matrice triangulaire dont la diagonale est formée des coefficients $1,c_1,c_1^2,\ldots,c_1^{d-1}$ tous non nuls, donc $U$ est bien une transformation de Tschirnhaus. Lorsque $c_1 = 0$ (toujours en supposant $c_0=0$), les polynômes $U(x)^i$ sont nuls pour $i \geq \frac{d}{2}$, donc on n'a pas affaire à une transformation de Tschirnhaus (sauf dans le cas trivial $d=1$). Bref, dans le cas $c_0 = 0$, nous avons montré que $U$ définit une transformation de Tschirnhaus si et seulement si $c_1 \neq 0$. Enfin, pour $c_0$ quelconque, on peut exprimer les polynômes $1, U(x)-c_0, (U(x)-c_0)^2, \ldots$ en fonction de $1, U(x), U(x)^2, \ldots$ par un système triangulaire de diagonale $1$, donc la condition $c_1 \neq 0$ est encore celle qui détermine si $U$ est une transformation de Tschirnhaus. L'élément $y = U(x) \in k(x)$ vérifie manifestement $(y-c_0)^d = 0$ donc, lorsque $U$ est bien une transformation de Tschirnhaus (i.e., $c_1 \neq 0$ comme on vient de le voir), ce polynôme $Q(Y) := (Y-c_0)^d$ est le polynôme minimal de $y$, c'est-à-dire le polynôme obtenu à partir de $P$ par la transformation $U$. \end{itemize} \end{exemples2} La notion de transformation de Tschirnhaus en elle-même est peu intéressante, mais elle le devient un peu plus en raison des observations suivantes : \begin{remarques2}\label{remarques-calcul-transformation-de-tschirnhaus} Donné un polynôme $P \in k[X]$ unitaire, et un polynôme $U \in k[X]$, on dispose d'un \emph{algorithme} permettant de déterminer si $U$ définit une transformation de Tschirnhaus sur $P$, et le cas échéant de calculer le polynôme transformé, dès lors que les opérations arithmétiques et l'égalité dans $k$ sont décidables. En effet, pour déterminer si $U$ définit une transformation de Tschirnhaus, on peut par exemple écrire les coefficients des $\deg P$ quantités $1, U(x), U(x)^2, \ldots, U(x)^{\deg P-1}$ sur la base évidente $1,x,x^2,\ldots,x^{\deg P-1}$ de $k(x) = k[X]/(P)$ (ceci se fait en effectuant des divisions euclidiennes des différentes puissances de $U$ par $P$), et chercher si la matrice ainsi définie est inversible, ce qui revient à calculer un déterminant ; et si c'est le cas, on peut obtenir le polynôme $Q$ transformé de $P$ par $U$ en exprimant $U(x)^{\deg P} \in k(x)$ sur la base $1, U(x), U(x)^2, \ldots, U(x)^{\deg P-1}$ (le polynôme $Q$ est alors le polynôme unitaire de degré $\deg P$ dont l'annulation en $U(x)$ exprime cette relation). Une conséquence de cette remarque, et du fait qu'un déterminant ne dépend pas du corps sur lequel il est calculé, est le fait suivant : si $P$ est un polynôme unitaire de degré $d$ et $U$ un polynôme quelconque, le fait que $U$ définisse une transformation de Tschirnhaus sur $P$, ainsi que le cas échéant la valeur du polynôme transformé, ne dépendent pas du corps contenant les coefficients de $P$ et $U$. Notamment, lorsque $P$ est séparable, on peut penser à la transformation de Tschirnhaus comme dans le deuxième exemple de \ref{exemples-transformations-de-tschirnhaus} : si $E$ est un corps contenant les racines $\xi_1,\ldots,\xi_d$ de $P$ (deux à deux distinctes), alors $Q$ vaut $\prod_{i=1}^d (X-U(\xi_i))$ (comparer avec \ref{transformation-de-tschirnhaus-preserve-galois} ci-dessous). C'est la manière dont on visualise les transformations de Tschirnhaus : $Q$ est le polynôme obtenu en appliquant $U$ à chaque racine de $P$. (On verra en \ref{transformation-de-tschirnhaus-et-factorisation} ci-dessous que cette description convient encore, convenablement interprétée, quand les polynômes ne sont plus séparables.) Remarquons encore au passage que si $P$ est séparable, le polynôme $Q$ transformé l'est aussi. \end{remarques2} \begin{remarques2} Nous avons introduit ci-dessus, pour évoquer la question algorithmique de reconnaître une transformation de Tschirnhaus, et calculer le polynôme transformé, la matrice donnant les coordonnées de $1, U(x), U(x)^2, \ldots, U(x)^{\deg P-1}$ sur la base $1, x, x^2, \ldots, x^{\deg P-1}$ de $k(x) = k[X]/(P)$. Si l'on préfère, une autre matrice naturellement associée à la situation est celle qui représente, toujours sur la base $1,x,x^2,\ldots,x^{\deg P-1}$ de $k(x)$, la multiplication par $U(x)$. Le polynôme minimal de cette matrice est celui de l'élément $U(x)$ de $k(x)$, et le fait que $U$ soit une transformation de Tschirnhaus se reconnaît au fait que ce polynôme minimal soit de degré $\deg P$, i.e., coïncide avec le polynôme caractéristique, qui est alors le polynôme $Q$ transformé de $P$ par $U$. On peut encore reformuler ceci en signalant que, lorsque $U(X)$ est une transformation de Tschirnhaus sur $P(X)$, alors le polynôme $Q(Y)$ transformé peut se calculer comme le résultant de $P(X)$ et $Y - U(X)$ comme polynômes de la variable $X$ (on rappelle que le résultant de deux polynômes $A(X)$ et $B(X)$ vaut $a^e \prod_{i=1}^d B(\xi_i)$ où $A(X) = a\prod_{i=1}^d(X-\xi_i)$ est la factorisation de $A$ dans un corps dans lequel il est décomposé, le résultat n'en dépendant pas puisqu'on peut aussi l'écrire comme un déterminant de Sylvester, et où $e$ est le degré de $B$) ; en effet, si $P(X) = \prod_{i=1}^d(X-\xi_i)$, le résultant en question vaut $\prod_{i=1}^d (Y-U(\xi_i))$, ce qui est bien $Q(Y)$ d'après les les remarques précédentes. Cette façon de procéder peut être algorithmiquement utile. (S'il s'agit de vérifier si $U$ définit bien une transformation de Tschirnhaus, lorsque $P$ est séparable, on peut effectuer le calcul du résultant et vérifier après coup si le polynôme $\prod_{i=1}^d (Y-U(\xi_i))$ ainsi obtenu est séparable : d'après ce que nous avons déjà vu, cela équivaut au fait que $U$ soit une transformation de Tschirnhaus.) \end{remarques2} \begin{remarque2}\label{transformation-de-tschirnhaus-et-composee} Soulignons que si $U$ est une transformation de Tschirnhaus sur $P$ et $Q$ le polynôme transformé, on a $Q \circ U \equiv 0 \pmod P$ (ceci signifie exactement $Q(U(x)) = 0 \in k[X]/(P)$). Réciproquement, si on a $Q \circ U \equiv 0 \pmod{P}$ \emph{et que $Q$ est irréductible} (sur $k$), de même degré que $P$, alors $U$ est une transformation de Tschirnhaus sur $P$ et $Q$ le polynôme transformé : en effet, l'hypothèse signifie $Q(U(x)) = 0 \in k[X]/(P)$, et puisque $Q$ est irréductible il est nécessairement minimal. \end{remarque2} \begin{proposition2}\label{transformation-de-tschirnhaus-et-isomorphisme-de-rupture} Soient $P \in k[X]$ et $Q \in k[Y]$ deux polynômes unitaires de même degré : on notera $k[X]/(P)$ et $k[Y]/(Q)$ les algèbres quotient et $x,y$ les classes des indéterminées $X,Y$ dans ceux-ci respectivement. Alors la donnée d'une transformation de Tschirnhaus $U$ transformant $P$ en $Q$ équivaut à la donnée d'un isomorphisme $k[Y]/(Q) \buildrel\sim\over\to k[X]/(P)$ (en tant que $k$-algèbres), l'isomorphisme étant donné à partir de la transformation $U$ par $A(y) \mapsto A(U(x))$, et réciproquement $U$ étant déterminé (modulo $P$) à partir de l'isomorphisme $k[Y]/(Q) \to k[X]/(P)$ comme l'image de la classe $y$ de $Y$ par celui-ci. En particulier, donnée une transformation de Tschirnhaus $U \in k[X]$ transformant $P$ en $Q$, il existe (modulo $Q$) un unique polynôme $V \in k[Y]$ tel que le polynôme composé $V \circ U$ soit congru à $X$ modulo $P$, et l'existence d'un tel polynôme $V$ pour un polynôme $U$ donné implique que $U$ est bien une transformation de Tschirnhaus sur $P$ (en le $Q$ de même degré que $P$ tel que $Q \circ U \equiv 0 \pmod{P}$). Le polynôme $V$ est alors une transformation de Tschirnhaus de $Q$ en $P$, telle que l'isomorphisme $k[X]/(P) \to k[Y]/(Q), \penalty-100\; B(x) \mapsto B(V(y))$ qu'il définit comme expliqué ci-dessus soit réciproque de celui défini par $U$. Le polynôme $U \circ V$ est congru à $Y$ modulo $Q$. \end{proposition2} \begin{proof} À cause des propriétés catégoriques (universelles) des anneaux de polynômes et anneaux quotients, la donnée d'un morphisme de $k$-algèbres $k[Y]/(Q) \to k[X]/(P)$ est exactement équivalente à la donnée de l'image $z$ de $y$ par celui-ci, qui doit vérifier $Q(z) = 0$ dans $k[X]/(P)$, l'image d'un élément $A(y)$ quelconque de $k[Y]/(Q)$ étant alors $A(z)$. Dire que le morphisme en question est un isomorphisme (c'est-à-dire, qu'il est injectif ou, de façon équivalente, surjectif) signifie que tout élément de $k[X]/(P)$ est polynôme en $z$ (les $1,z,z^2,\ldots$ engendrent $k[X]/(P)$ comme $k$-espace vectoriel, donc en fait les $1,z,z^2,\ldots,z^{\deg Q-1}$ l'engendrent), donc définisse une transformation de Tschirnhaus (sous la forme $z = U(x)$). Ceci équivaut aussi au fait que le simple élément $x$ puisse s'écrire sous la forme $V(z)$, c'est-à-dire qu'on puisse trouver $V$ tel que $V(U(x))=x$. Les différentes affirmations de la propositions sont alors toutes claires. \end{proof} Cette proposition éclaire le fait, déjà signalé, que le polynôme transformé d'un polynôme irréductible (resp. séparable) par une transformation de Tschirnhaus est encore irréductible (resp. séparable), puisque ces deux propriétés se lisent sur l'algèbre quotient (comme le fait qu'elle soit un corps, resp. une algèbre étale). La transformation de Tschirnhaus $V$ de $Q$ en $P$ définie par la proposition précédente à partir d'une transformation de Tschirnhaus $U$ de $P$ en $Q$ s'appelle la transformation de Tschirnhaus \emph{réciproque} de $U$. \begin{exemples2}\label{exemples-transformations-de-tschirnhaus-reciproques} Reprenons les exemples de \ref{exemples-transformations-de-tschirnhaus} pour en expliciter les réciproques. \begin{itemize} \item Soit $P = X^3 - 2 \in \QQ[X]$, dont on note $\root3\of2$ la racine dans le corps de rupture. La transformation de Tschirnhaus réciproque de $U = X+1$ est évidemment $V = Y-1$. La transformation de Tschirnhaus réciproque de $U = X^2$ est $V = \frac{1}{2}Y^2$ car $\frac{1}{2} ((\root3\of2)^2)^2 = \root3\of2$. La transformation réciproque de $U = \frac{1}{X}$ (qui peut également s'écrire $\frac{1}{2} X^2$, l'inverse de $X$ modulo $P = X^3-2$) est $V = 2 Y^2$ (qu'on peut aussi vouloir écrire $\frac{1}{Y}$, puisque $2Y^2$ est l'inverse de $Y$ modulo $Q = Y^3 - \frac{1}{2}$). \item Soit $P = \prod_{i=1}^d (X-\xi_i) \in k[X]$ un polynôme unitaire scindé et séparable de degré $d$ dont on note $\xi_1,\ldots,\xi_d$ les racines deux à deux distinctes dans le corps $k$, et $U$ un polynôme tel que $U(\xi_1),\ldots,U(\xi_d)$ soient deux à deux distinctes. Alors la réciproque de $U$ vu comme une transformation de Tschirnhaus sur $P$ est tout polynôme $V \in k[Y]$ (modulo $Q = \prod(X-U(\xi_i))$) prenant en $U(\xi_i)$ la valeur $\xi_i$. \item Soit $P = X^d$, et soit $U(X) = c_1 X + c_2 X^2 + \cdots + c_{d-1} X^{d-1}$ (on suppose $c_0 = 0$ et $c_1 \neq 0$) un polynôme considéré modulo $P$, qu'on peut donc imaginer comme un développement limité tronqué à partir de l'ordre $d$ : la transformation de Tschirnhaus réciproque de $V$ est alors le polynôme $V = c'_1 Y + c'_2 Y^2 + \cdots + c'_{d-1} Y^{d-1}$ définissant le développement limité réciproque de $U$, c'est-à-dire que $V\circ U$ est de valuation $\geq d$ (on peut donner des formules explicites : $c'_1 = 1/c_1$, $c'_2 = -c_2/c_1^3$, $c'_3 = (2 c_2^2 - c_1 c_3)/c_1^5$ et ainsi de suite). \end{itemize} \end{exemples2} \begin{remarque2} Pour faire suite à \ref{remarques-calcul-transformation-de-tschirnhaus}, signalons qu'on peut calculer algorithmiquement la transformation de Tschirnhaus réciproque d'une transformation $U$ sur un polynôme $P$ : nous avons observé que le fait que $U$ soit une transformation de Tschirnhaus se détecte à l'inversibilité de la matrice représentant les puissances $1, U(x), U(x)^2, \ldots, U(x)^{\deg P-1}$ dans $k[X]/(P)$ sur la base $1,x,x^2,\ldots,x^{\deg P-1}$ de ce dernier ; en inversant cette même matrice, on obtient celle représentant $1,x,x^2,\ldots,x^{\deg P-1}$ sur la base $1, U(x), U(x)^2, \ldots, U(x)^{\deg P-1}$, c'est-à-dire exactement $1,V(y),V(y)^2,\ldots,V(y)^{\deg P-1}$ sur la base $1,y,y^2,\ldots,y^{\deg P-1}$ de $k[Y]/(Q)$ avec $Q$ le polynôme transformé. \end{remarque2} \begin{remarques2} Contrairement à ce que pourraient laisser penser les propositions précédentes (ou la terminologie), les transformations de Tschirnhaus ne forment pas un groupe (mais plutôt un « groupoïde ») : il est bien possible de composer une transformation de Tschirnhaus $U$ de $P$ en $Q$ avec une transformation de Tschirnhaus $V$ de $Q$ en $R$, la composée étant donnée comme on s'y attend par le polynôme $V\circ U$, en revanche, données deux transformations de Tschirnhaus différentes sur un polynôme $P$, il n'y a pas de façon évidente de les composer (si $U$ transforme $P$ en $Q$ et que $V$ est une autre transformation de Tschirnhaus sur $P$, il n'y a pas de raison que ce même polynôme constitue une transformation de Tschirnhaus sur $Q$, ou que deux polynômes représentant la même transformation de Tschirnhaus sur $P$ représentent la même sur $Q$). En revanche, si on considère les transformations de Tschirnhaus transformant un polynôme $P$ en \emph{lui-même}, alors on a bien affaire à un groupe, et la proposition \ref{transformation-de-tschirnhaus-et-isomorphisme-de-rupture} montre qu'il s'agit d'un groupe bien familier, à savoir celui des automorphismes de l'algèbre quotient $k[X]/(P)$ de $P$ ; lorsque $P$ est un polynôme irréductible séparable dont le corps de rupture $k[X]/(P)$ coïncide avec le corps de décomposition, il s'agit du groupe de Galois de $P$. \end{remarques2} \begin{proposition2}\label{transformation-de-tschirnhaus-preserve-galois} Soit $Q$ un polynôme obtenu à partir d'un polynôme $P \in k[X]$ unitaire séparable par une transformation de Tschirnhaus définie par un polynôme $U$. Alors le corps de décomposition de $Q$ sur $k$ est isomorphe à celui de $P$, les racines de $Q$ dans ce corps sont les $U(\xi_1),\ldots,U(\xi_d)$ où $\xi_1,\ldots,\xi_d$ sont les racines (deux à deux distinctes) de $P$ ; et le groupe de Galois de $Q$ sur $k$ est isomorphe à celui de $P$. \end{proposition2} \begin{proof} Soit $E$ un corps de décomposition de $P$, et soient $\xi_1,\ldots,\xi_d$ les racines de ce dernier dans $E$ (qui l'engendrent). Alors chacun des éléments $U(\xi_i)$ est racine de $Q$ (puisque $Q\circ U$ est congru à $0$ modulo $P$). En introduisant $V$ la transformation de Tschirnhaus réciproque de $U$, on a $V(U(\xi_i)) = \xi_i$ pour chaque $i$ puisque $V\circ U$ est congru à $X$ modulo $P$ : ceci permet d'affirmer que les racines $U(\xi_i)$ de $Q$ sont deux à deux distinctes, donc que $E$, qui les contient, scinde le polynôme $Q$, et comme les $U(\xi_i)$ engendrent les $\xi_i$ (on vient de le voir) donc tout $E$, le corps $E$ est aussi corps de décomposition de $Q$. Ceci prouve tout ce qu'on voulait. \end{proof} \begin{exemple2}\label{exemple-transformations-de-tschirnhaus-sur-quadratiques} Soit $P = X^2 + bX + c \in k[X]$ un polynôme quadratique sur un corps $k$ de caractéristique $\neq 2$. Une transformation de Tschirnhaus sur $P$ est décrite par un polynôme $U = \lambda x + \mu$, et la condition pour que $U$ définisse bien une transformation de Tschirnhaus, compte tenu des remarques \ref{remarques-calcul-transformation-de-tschirnhaus}, est simplement : $\lambda \neq 0$. Lorsque c'est le cas, on calcule aisément que $U(x)^2 = \lambda(2\mu - b\lambda) x + (\mu^2 - c\lambda^2) \in k[X]/(P)$ (en notant comme d'habitude $x$ la classe de $X$) et donc que $U(x)$ est racine de $Q(Y) := Y^2 + (b\lambda - 2\mu) Y + (c\lambda^2 - \mu^2)$ qui, compte tenu de son degré, est bien le polynôme minimal de $U(x)$, c'est-à-dire le transformé de $P$ par la transformation de Tschirnhaus $U$. Le discriminant de $Q$ est $\lambda^2 (b^2-4c)$, c'est-à-dire celui de $P$ multiplié par un carré : ceci permet de dire que si le rapport des discriminants de $P$ et $Q$ n'est pas un carré dans $k^\times$, alors $P$ et $Q$ ne sont pas reliés par une transformation de Tschirnhaus (ils ne sont pas « Tschirnhaus-équivalents » en anticipant sur la définition \ref{definition-polynomes-tschirnhaus-equivalents}). Réciproquement, comme $P$ peut être transformé (en prenant $\lambda = 1$ et $\mu = -\frac{b}{2}$) en $Y^2 - \frac{1}{4}(b^2-4c)$, deux polynômes quadratiques unitaires dont les discriminants sont en rapport carré peuvent être transformés l'un en l'autre par une transformation de Tschirnhaus (sont « Tschirnhaus-équivalents »). On peut aussi, dans ce contexte, chercher les transformations de Tschirnhaus transformant $P$ en lui-même : il s'agit de résoudre le système $b\lambda-2\mu = b$ et $c\lambda^2-\mu^2 = c$, dont on peut vérifier que si $b^2-4c\neq 0$ il admet pour seules solutions l'identité $(\lambda,\mu) = (1,0)$ et l'unique autre transformation $(\lambda,\mu) = (\frac{b^2+4c}{b^2-4c}, \frac{4bc}{b^2-4c})$. Autrement dit, si $P$ est irréductible, son groupe de Galois est $\ZZ/2\ZZ$, ce qu'on savait bien sûr déjà. (Lorsque $b^2-4c = 0$, en revanche, les transformations de Tschirnhaus de $P$ en $P$ sont tous les $(\lambda,\mu)$ tels que $\mu = \frac{b}{2}(\lambda-1)$ --- \XXX revérifier ce truc.) \end{exemple2} \subsection{Transformations de Tschirnhaus et factorisation} Cherchons à présent à montrer comment les transformations de Tschirnhaus sur un polynôme quelconque peuvent se ramener à celles sur un polynôme irréductible. Commençons par le cas facile d'un produit de deux polynômes étrangers : \begin{proposition2}\label{transformation-de-tschirnhaus-sur-un-produit} Soient $P_1,P_2 \in k[X]$ deux polynômes unitaires premiers entre eux, et $P = P_1 P_2$. Alors la donnée d'une transformation de Tschirnhaus $U$ de $P$ équivaut à la donnée de transformations de Tschirnhaus $U_1,U_2$ de $P_1,P_2$ respectivement telles que les polynômes transformés $Q_1,Q_2$ respectivement soient premiers entre eux, le polynome $U$ étant alors congru à $U_i$ modulo $P_i$ (pour $i=1,2$). Et dans ces conditions, le polynôme transformé $Q$ de $P$ par $U$ vaut $Q_1 Q_2$. \end{proposition2} \begin{proof} D'après le théorème chinois (cf. par exemple \refext{Spec}{lemme chinois}), $k[X]/(P)$ est isomorphe à $(k[X]/(P_1)) \times (k[X]/(P_2))$. En notant $x_1,x_2$ les classes de $X$ modulo $P_1,P_2$ respectivement, l'élément $(U_1(x_1),U_2(x_2))$ engendre le produit en tant qu'algèbre si et seulement si $U_1(x_1)$ et $U_2(x_2)$ engendrent chacun des facteurs et que leurs polynômes minimaux $Q_1,Q_2$ sont premiers entre eux. \end{proof} Pour généraliser le dernier exemple de \ref{exemples-transformations-de-tschirnhaus}, attachons-nous maintenant à déterminer les transformations de Tschirnhaus entre puissances de polynômes irréductibles. Commençons par identifier la manière dont on peut relever la transformation identité sur $P$ : \begin{lemme2}\label{lemme-relevement-transformation-de-tschirnhaus-identite} Soit $P$ un polynôme unitaire sur un corps $k$, et soit $U$ un polynôme dans $k[X]$ tel que $U(X) \equiv X \pmod{P}$ : alors $U$ définit une transformation de Tschirnhaus de $P^r$ en lui-même pour tout $r\geq 1$. \end{lemme2} \begin{proof} Puisque $U(X) \equiv X \pmod{P}$, on a $P\circ U \equiv 0 \pmod{P}$, disons $P\circ U = S P$ avec $S \in k[X]$, et ainsi $P^r \circ U = S^r P^r \equiv 0 \pmod{P^r}$. Ceci montre que $x \mapsto U(x)$ définit bien un morphisme $k[X]/(P^r) \to k[X]/(P^r)$. Il s'agit de voir que c'est un isomorphisme, et par égalité des dimensions sur $k$ il suffit de voir qu'il est injectif, c'est-à-dire que si $Q\circ U \equiv 0 \pmod{P^r}$ avec $Q \in k[X]$ alors $Q \equiv 0 \pmod{P^r}$. Or, si $d = \deg P$, les polynômes $1,U,U^2,\ldots,U^{rd-1}$ sont échelonnés en valuation, donc ils forment une base de $k[X]/(P^r)$ comme $k$-espace vectoriel. Ceci montre qu'aucun polynôme $Q$ de degré $