diff options
author | David A. Madore <david+git@madore.org> | 2012-11-15 15:26:40 +0100 |
---|---|---|
committer | David A. Madore <david+git@madore.org> | 2012-11-15 15:26:40 +0100 |
commit | 2f0b004aef3da69db3b6f7196f37b3e55a482235 (patch) | |
tree | 28c6470eac5f2550d388187813e7bcf780cfe337 /chapitres/radicaux.tex | |
parent | 342e906b1cd64762dfaba1584e40e9051263659e (diff) | |
download | galois-2f0b004aef3da69db3b6f7196f37b3e55a482235.tar.gz galois-2f0b004aef3da69db3b6f7196f37b3e55a482235.tar.bz2 galois-2f0b004aef3da69db3b6f7196f37b3e55a482235.zip |
[Radicaux] Algorithme de calcul des expressions des racines en radicaux: cas de la caractéristique 0 avec assez de racines de l'unité.
Diffstat (limited to 'chapitres/radicaux.tex')
-rw-r--r-- | chapitres/radicaux.tex | 121 |
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} |