[Radicaux] Algorithme de calcul des expressions des racines en radicaux: cas de la caractéristique 0 avec assez de racines de l'unité.

1 files changed, 115 insertions, 6 deletions

diff --git a/chapitres/radicaux.tex b/chapitres/radicaux.tex
index 06adcf4..b853aba 100644
--- a/chapitres/radicaux.tex
+++ b/chapitres/radicaux.tex
@@ -19,6 +19,7 @@
 
 \externaldocument{KASW}
 \externaldocument{calculs-galois}
+\externaldocument{bases-groebner}
 
 \title{Radicaux, r\'esolubilit\'e, calculs explicites et cyclotomie}
  
@@ -220,13 +221,14 @@ les conditions équivalentes suivantes :
 \item il existe une chaîne $G = G_0 \geq G_1 \geq \cdots \geq G_r =
   \{1\}$ de sous-groupes de $G$ telle que pour chaque $i$ le
   sous-groupe $G_{i+1}$ soit distingué dans $G_i$ (mais non
-  nécessairement dans $G$) \commentaire{En fait, OPS les $G_i$ distingués dans $G$.
-Il faut probablement le dire.}
-et que le quotient $G_i / G_{i+1}$ soit
-  \emph{cyclique d'ordre premier},
-\item (la même condition, en omettant les mots « d'ordre premier »),
+  nécessairement dans $G$) et que le quotient $G_i / G_{i+1}$ soit
+  \emph{cyclique d'ordre premier} ;
+\item (la même condition, en omettant les mots « d'ordre premier ») ;
 \item (la même condition, en remplaçant « cyclique d'ordre premier »
-  par « abélien »),
+  par « abélien ») ;
+\item la même condition que l'une des trois précédentes, mais en
+  imposant que chaque $G_i$ soit distingué dans $G$ (et pas seulement
+  dans le précédent) ;
 \item si on note $G'$ le sous-groupe, dit \emph{groupe dérivé}
   engendré par les commutateurs (éléments de la forme
   $xyx^{-1}y^{-1}$) des éléments de $G$, qui est également le plus
@@ -1521,6 +1523,113 @@ L_1 + L_2 + L_3 + L_4)$ de $f$ dans les complexes, on obtient
 \par}
 
 
+\subsection{Une stratégie algorithmique générale}
+
+Nous proposons d'étudier dans cette section le problème suivant : on
+suppose que $f = X^d + a_1 X^{d-1} + \cdots + a_d \in k[X]$ est un
+polynôme unitaire séparable sur un corps $k$, dans lequel on suppose
+au moins qu'on sait mener des calculs et factoriser des polynômes, et,
+en supposant que le groupe de Galois de $f$ est résoluble, on cherche
+à calculer de façon algorithmique une expression en radicaux des
+racines de $f$, dans le corps de décomposition de celui-ci.
+
+Les algorithmes que nous exposons ici sont avant tout théoriques, et
+ne sont pas forcément utilisables en tant que tels dans la pratique en
+raison de leur complexité considérable : de nombreuses améliorations
+et optimisations sont possibles afin de les rendre pratiques.
+
+\subsubsection{Cas de caractéristique $0$ avec assez de racines de l'unité}
+On suppose ici que $k$ est un corps de caractéristique $0$ et qu'il
+contient « assez » de racines de l'unité (où le sens de « assez » va
+être précisé en fonction du groupe de Galois, mais il sera en tout cas
+suffisant que $k$ contienne les racines $\ppcm(1,2,3,\ldots,d)$-ièmes
+de l'unité, où $d = \deg f$).
+
+Comme en
+\refext{Groebner}{section-algebre-de-decomposition-universelle}, on
+introduit l'algèbre de décomposition universelle $k[Z_1,\ldots,Z_d]/I$
+de $f$, où $I$ est l'idéal engendré par les relations $\sigma_i =
+(-1)^i a_i$ où $\sigma_i$ désigne le $i$-ième polynôme symétrique
+élémentaire en $Z_1,\ldots,Z_d$.  Le groupe $\mathfrak{S}_d$ agit par
+permutation sur les $Z_i$.  Comme en
+\refext{Groebner}{section-calcul-galois-par-base-de-groebner}, où on a
+vu comment le calculer algorithmiquement, on appelle $J$ un idéal
+premier de $k[Z_1,\ldots,Z_d]$ contenant $I$ : alors $E =
+k[Z_1,\ldots,Z_d]/J$ est le corps de décomposition de $f$, et le
+groupe $G$ des permutations de $Z_1,\ldots,Z_d$ laissant $J$ invariant
+est le groupe de Galois de $f$.  On sait effectuer algorithmiquement
+des calculs dans $E$, et on sait naturellement faire agir $G$ sur ses
+éléments (puisqu'il s'agit simplement de permutations des $Z_i$).
+
+On supposera que $k$ contient les racines $N$-ièmes de l'unité, où $N$
+est tel que $g^N = 1$ pour tout $g \in G$ (et dès lors que $k$
+\emph{contient} ces éléments, on sait les représenter explicitement
+puisque nous avons supposé savoir factoriser des polynômes sur $k$ :
+il suffit de factoriser le $N$-ième polynôme cyclotomique $\Phi_N$
+pour disposer d'une racine primitive $N$-ième).
+
+Soit $G = G_0 \geq G_1 \geq \cdots \geq G_r = \{1\}$ une suite de
+sous-groupes de $G$ avec $G_{u+1}$ distingué dans $G_u$ et
+$G_u/G_{u+1}$ cyclique d'ordre $m_u$ engendré par un élément
+représenté par un élément $\tau_u$ de $G_u$.  Par récurrence sur $u$,
+nous montrons qu'on peut calculer des expressions par radicaux
+d'éléments du sous-corps de $E$ fixé par $G_u$.  Pour $u=0$, un
+élément de $E$ fixé par $G_0 = G$ est un élément de $k$, et la
+représentation choisie est transparente (c'est-à-dire que dans
+$k[Z_1,\ldots,Z_d]/J$ on verra cet élément comme $c \cdot 1$ avec $c
+\in k$ et $1$ le monôme unité).  Si maintenant le problème est de
+calculer une expression par radicaux de $\gamma \in E$ fixé par
+$G_{u+1}$, on calcule les valeurs dans $E$ des sommes de Lagrange
+$\alpha_j = \sum_{i=0}^{m_u-1} \zeta^{ij} {\tau_u}^i(\gamma)$, où
+$\zeta$ est une racine primitive $m_u$-ième de l'unité dans $k$ (par
+exemple $\omega^{N/m_u}$ avec $\omega$ une racine primitive $N$-ième
+fixée une fois pour toutes).  Puisque $\tau_u$ est connu comme
+permutation des $Z_i$, ces $\alpha_j$ sont explicitement calculables
+dans $E = k[Z_1,\ldots,Z_d]/J$.  Comme les
+$(\alpha_j)^{m_u/\pgcd(j,m_u)}$ sont stables par $G_{u+1}$ et
+$\tau_u$, donc par $G_u$, l'hypothèse de récurrence assure qu'on sait
+en calculer explicitement une expression en radicaux.  On peut donc
+écrire $\alpha_j$ comme une racine de cette quantité, ce qui en donne
+une expression en radicaux (cf. la remarque suivante), et alors
+$\gamma = \frac{1}{m_u} \sum_{j=0}^{m_u-1} \alpha_j$ donne une
+expression en radicaux de $\gamma$.  En appliquant ceci à n'importe
+lequel des $Z_i$ (modulo $J$), on a trouvé une expression en radicaux
+des racines de $f$.
+
+\begin{remarque2}
+Pour que l'expression en radicaux obtenue définisse correctement la
+quantité écrite, il faut fixer un choix de déterminations des racines
+extraites.  En général, il n'y a pas de manière particulièrement
+intelligente de procéder.  On pourrait par exemple décider qu'à chaque
+fois que l'algorithme veut écrire un élément $\alpha \in E$ comme
+racine $m$-ième d'un $a \in E$, on cherche si une racine $m$-ième de
+ce même $a$ a déjà été utilisée : si ce n'est pas le cas, on décide
+que $\alpha$ sera l'élément noté $\root m\of a$, et on enregistre le
+triplet $(a,m,\alpha)$ ; sinon, on appelle $\alpha_0$ la racine
+$m$-ième précédemment choisie pour $a$ (c'est-à-dire qu'on a
+enregistré le triplet $(a,m,\alpha_0)$), et on écrit $\alpha = \zeta^t
+\root m\of a$ où $\root m\of a$ a déjà servi à désigner $\alpha_0$, et
+$\zeta^t$ est la racine $m$-ième de l'unité $\alpha/\alpha_0$ (qu'on
+peut calculer explicitement dans $E$).
+
+Si les calculs sont menés sur $\QQ$ (ou de façon générale sur un
+sous-corps de $\CC$), il existe bien sûr un choix standard de
+déterminations des racines $m$-ièmes.  Pour pouvoir réaliser ce choix,
+il faut, lorsqu'on réalise le corps de décomposition de $f$ comme
+$k[Z_1,\ldots,Z_d]/J$, choisir en même temps un plongement compatible
+dans $\CC$, c'est-à-dire trouver une numérotation des racines
+complexes $\zeta_1,\ldots,\zeta_d$ de $f$ telles que toutes les
+relations engendrant $J$ soient satisfaites pour cette numérotation
+(ou inversement, choisir l'idéal $J$ premier contenant $I$ qui soit
+compatible avec la numérotation préalablement choisie des $\zeta_i$).
+Ceci permet, à chaque étape de l'algorithme, d'obtenir une valeur
+complexe approchée des éléments de $E$ qui apparaissent, et donc,
+quand il s'agit d'extraire une racine $m$-ième de $a$, de choisir
+l'écriture $\zeta^t \root m\of a$ qui fait intervenir la détermination
+principale complexe.
+\end{remarque2}
+
+
 
 \ifx\danslelivre\undefined
 \bibliography{../configuration/bibliographie-livre}