diff options
author | David A. Madore <david@procyon> | 2011-10-27 16:52:15 +0200 |
---|---|---|
committer | David A. Madore <david@procyon> | 2011-10-27 16:52:15 +0200 |
commit | 1c52f17d5fd6224f4446376c5f70f0d3a45750de (patch) | |
tree | 872778cd0824d66312486d1266e87a864be731a4 /chapitres/calculs-galois.tex | |
parent | d709168221abdcd4a212e7a833cbeacc13f50652 (diff) | |
download | galois-1c52f17d5fd6224f4446376c5f70f0d3a45750de.tar.gz galois-1c52f17d5fd6224f4446376c5f70f0d3a45750de.tar.bz2 galois-1c52f17d5fd6224f4446376c5f70f0d3a45750de.zip |
[calculs, ExG] Remaniement de tout ce où je parle de bases de Gröbner.
Ce n'est sans doute pas encore au point : il faudrait vraiment
éclaircir ces choses.
Diffstat (limited to 'chapitres/calculs-galois.tex')
-rw-r--r-- | chapitres/calculs-galois.tex | 164 |
1 files changed, 124 insertions, 40 deletions
diff --git a/chapitres/calculs-galois.tex b/chapitres/calculs-galois.tex index a72e635..0570918 100644 --- a/chapitres/calculs-galois.tex +++ b/chapitres/calculs-galois.tex @@ -1276,8 +1276,8 @@ R_P(f) = \prod_{\sigma\in\mathfrak{S}_d/H} \in L[X] \] où $H = \Stab_{\mathfrak{S}_d}(P) = \{\sigma\in\mathfrak{S}_d : -F(Z_{\sigma(1)}, \ldots, Z_{\sigma(d)}) = F(Z_1,\ldots,Z_d)\}$ est le -stabilisateur de $F$ pour l'action de $\mathfrak{S}_d$ opérant sur +P(Z_{\sigma(1)}, \ldots, Z_{\sigma(d)}) = P(Z_1,\ldots,Z_d)\}$ est le +stabilisateur de $P$ pour l'action de $\mathfrak{S}_d$ opérant sur $K[Z_1,\ldots,Z_d]$ par permutation des variables ; ce polynôme $R_P(f)$ appartient, en fait, à $K[X]$. @@ -1305,9 +1305,9 @@ définit alors la \emph{résolvante dans $\mathfrak{G}$ relativement R_{\mathfrak{G},P}(f) = \prod_{\sigma\in\mathfrak{G}/H} (X-P(\xi_{\sigma(1)},\ldots,\xi_{\sigma(d)})) \in L[X] \] -où $H = \Stab_{\mathfrak{G}}(F) = \{\sigma\in\mathfrak{G} : -F(Z_{\sigma(1)}, \ldots, Z_{\sigma(d)}) = F(Z_1,\ldots,Z_d)\}$ est le -stabilisateur de $F$ dans $\mathfrak{G}$ ; l'hypothèse sur +où $H = \Stab_{\mathfrak{G}}(P) = \{\sigma\in\mathfrak{G} : +P(Z_{\sigma(1)}, \ldots, Z_{\sigma(d)}) = P(Z_1,\ldots,Z_d)\}$ est le +stabilisateur de $P$ dans $\mathfrak{G}$ ; l'hypothèse sur $\mathfrak{G}$ assure ce polynôme $R_{\mathfrak{G},P}(f)$ appartient, en fait, à $K[X]$. \end{definition2} @@ -1577,7 +1577,7 @@ séparable irréductible de degré $d$ : \end{itemize} -\begin{remarque2} +\subsubsection{Calcul des résolvantes par calcul approché}\label{calcul-resolvantes-par-calcul-approche} Dans la stratégie ci-dessus, à l'étape de calcul de $R_P(f)$, on \emph{ne} procède généralement \emph{pas} en calculant la résolvante générale $R_P$ (comme polynômes des fonctions symétriques @@ -1605,23 +1605,102 @@ très utile de disposer d'une définition de résolvante générale $R_{\mathfrak{G},P}$ dans $\mathfrak{G}$, seule important la valeur $R_{\mathfrak{G},P}(f)$ prise sur le polynôme $f$. +\subsubsection{Calcul des résolvantes par bases de Gröbner}\label{calcul-resolvantes-par-bases-groebner} En supposant connue du lecteur la notion de base de Gröbner d'idéaux -de polynômes, voici une autre manière dont on pourrait, en principe, -approcher le calcul de $R_P(f)$ ou $R_{\mathfrak{G},P}(f)$ sans faire -appel à des calculs en précision garantie : dans -l'anneau $K[Z_1,\ldots,Z_d]$, calculer une base de Gröbner $B$ de -l'idéal $\mathfrak{I}$ engendré par les relations -$\sigma_i(Z_1,\ldots,Z_d) = (-1)^i a_i$ où $\sigma_i$ est la $i$-ième -fonction symétrique élémentaire de $Z_1,\ldots,Z_d$ et $a_i$ est le -coefficient de degré $d-i$ de $f$ ; puis, pour chaque degré $j$, -calculer le coefficient de degré $j$ de $R_{\mathfrak{G},P} = +de polynômes, décrivons succinctement une autre manière dont on peut, +en principe, aborder le calcul de $R_P(f)$ ou $R_{\mathfrak{G},F}(f)$ +sans faire appel à des calculs en précision garantie. + +Considérons d'abord le cas de $R_P(f)$ (c'est-à-dire $\mathfrak{G} = +\mathfrak{S}_d$). On commence, dans l'anneau $K[Z_1,\ldots,Z_d]$, par +calculer une base de Gröbner $B$ (pour un ordre quelconque) de l'idéal +$\mathfrak{I}$ engendré par les relations $\sigma_i(Z_1,\ldots,Z_d) = +(-1)^i a_i$ où $\sigma_i$ est la $i$-ième fonction symétrique +élémentaire de $Z_1,\ldots,Z_d$ et $a_i$ est le coefficient de +degré $d-i$ de $f$. On peut par exemple +(\cite[théorème 1.2.7]{Sturmfels}) prendre la base formée des +$h_i(Z_i,\ldots,Z_d) - \sum_{j=1}^k a_j h_{k-j}(Z_i,\ldots,Z_d)$ où +$h_j$ est le $i$-ième polynôme homogène symétrique complet de +$Z_1,\ldots,Z_d$, c'est-à-dire la somme de tous les monômes de degré +$i$ en ces variables (on pose notamment $h_0=1$), et +$h_j(Z_i,\ldots,Z_d)$ signifie qu'il est évalué en remplaçant les +$i-1$ premières variables par $0$. Puis, en réduisant modulo cette +base $B$, c'est-à-dire en travaillant dans l'anneau +$K[X,Z_1,\ldots,Z_d]/\mathfrak{I}K[X,Z_1,\ldots,Z_d]$ au moyen des +relations de $B$, on calcule le polynôme $R_P = +\prod_{\sigma\in\mathfrak{S}_d/H} +(X-P(Z_{\sigma(1)},\ldots,Z_{\sigma(d)}))$ : comme ce dernier est +invariant par $\mathfrak{S}_d$, il doit donner, une fois réduit +modulo $B$, un résultat indépendant de $Z_1,\ldots,Z_d$, qui est le +$R_P(f) \in K[X]$ recherché. + +Pour la situation dans un groupe $\mathfrak{G}$ (où on notera cette +fois $F$ le polynôme relativement auquel on cherche la résolvante +de $f$), la difficulté supplémentaire est qu'il n'est pas évident de +donner une expression « générale » de $R_{\mathfrak{G},F}$, faute de +choix évident de générateurs pour $\Fix_{\mathfrak{G}} +K[Z_1,\ldots,Z_d]$ comme le sont les fonctions symétriques +élémentaires (ou les coefficients de $f$) pour $\Fix_{\mathfrak{S}_d} +K[Z_1,\ldots,Z_d]$ (et, de fait, on peut montrer que +$\Fix_{\mathfrak{G}} K[Z_1,\ldots,Z_d]$ n'est pas toujours isomorphe à +un pur anneau de polynômes). De plus, affirmer que $\mathfrak{G}$ +(plutôt qu'un conjugué de celui-ci) contient le groupe de Galois de +$f$ suppose d'avoir fait un choix concernant la numérotation des +racines de $f$, qu'il va bien falloir faire apparaître dans le calcul. + +La situation qui se présente en général est qu'on a déterminé que le +groupe de Galois de $f$ (supposé séparable) était contenu dans +$\mathfrak{G}$, grâce au théorème \ref{utilisation-des-resolvantes}, +au moyen de la factorisation d'une première résolvante $R_P(f)$, +relativement à un polynôme $P$ ayant $\mathfrak{G}$ comme +stabilisateur pour l'action de $\mathfrak{S}_d$ par permutation des +variables. + +Faisons donc les hypothèses suivantes : on a $\mathfrak{G} = +\Stab_{\mathfrak{S}_d}(P)$ pour un polynôme $P$ tel que la résolvante +$R_P(f)$ admette une racine simple $\pi \in K$, et la numérotation +$\xi_1,\ldots,\xi_d$ des racines de $f$ est choisie pour faire en +sorte que $\pi = P(\xi_1,\ldots,\xi_d)$. On cherche alors à calculer +$R_{\mathfrak{G},F}(f)$ pour un polynôme $F$. + +Dans ces conditions, le corps $\Fix_{\mathfrak{G}} K(Z_1,\ldots,Z_d)$ +est une extension de $\Fix_{\mathfrak{S}_d} K(Z_1,\ldots,Z_d)$ de +degré $e = (\mathfrak{S}_d : \mathfrak{G})$, et elle peut être +engendrée par l'élément $P$ dont le polynôme minimal (sur +$\Fix_{\mathfrak{S}_d} K(Z_1,\ldots,Z_d)$) est donné précisément par +la résolvante générale $R_P$. Les éléments de $\Fix_{\mathfrak{G}} +K(Z_1,\ldots,Z_d)$ et, en particulier, les coefficients de la +résolvante $R_{\mathfrak{G},F}$ peuvent donc s'exprimer au moyen des +fonctions symétriques élémentaires et de $P$, et même comme +combinaisons de $1,P,\ldots,P^{e-1}$ avec des coefficients totalement +symétriques. En évaluant en $\xi_1,\ldots,\xi_d$ (les racines +de $f$), les coefficients de $R_{\mathfrak{G},F}(f)$ peuvent +s'exprimer comme de combinaisons de $1,\pi,\ldots,\pi^{e-1}$ avec des +coefficients fonctions rationnelles de $a_1,\ldots,a_d$ (les +coefficients de $f$). + +Bref, on commence, dans l'anneau $K[Z_1,\ldots,Z_d]$, par calculer une +base de Gröbner $B$ (pour un ordre quelconque) de l'idéal +$\mathfrak{I}$ engendré par les relations $\sigma_i(Z_1,\ldots,Z_d) = +(-1)^i a_i$ et $P(Z_1,\ldots,Z_d) = \pi$. Puis, en réduisant modulo +cette base $B$, c'est-à-dire en travaillant dans l'anneau +$K[X,Z_1,\ldots,Z_d]/\mathfrak{I}K[X,Z_1,\ldots,Z_d]$ au moyen des +relations de $B$, on calcule le polynôme $R_{\mathfrak{G},F} = \prod_{\sigma\in\mathfrak{G}/H} -(X-P(Z_{\sigma(1)},\ldots,Z_{\sigma(d)}))$ (c'est-à-dire, au signe -près, la $j$-ième fonction symétrique élémentaire des -$P(Z_{\sigma(1)},\ldots,Z_{\sigma(d)})$), et réduire modulo $B$, ce -qui doit donner un résultat dans $K$, i.e., indépendant -de $Z_1,\ldots,Z_d$. \XXX Faut-il expliquer mieux ça ? -\end{remarque2} +(X-F(Z_{\sigma(1)},\ldots,Z_{\sigma(d)}))$ : comme ce dernier est +invariant par $\mathfrak{G}$, il doit donner, une fois réduit +modulo $B$, un résultat indépendant de $Z_1,\ldots,Z_d$, qui est le +$R_P(f) \in K[X]$ recherché. + +On renvoie à \cite[algorithme 2.5.6]{Sturmfels} pour une justification +du calcul par base de Gröbner même sans substituer aux polynômes +$\sigma_i$ et $P$ leur valeur sur les racines $\xi_1,\ldots,\xi_d$. + +\XXX Rédigé en vitesse. Vérifier que je n'ai pas oublié des +hypothèses pour que ça marche (du style $f$ irréductible, +caractéristique $0$ ou que sais-je encore). + +\subsection{Compléments sur les résolvantes} La proposition suivante permet de calculer les résolvantes linéaires pour une combinaison linéaire de deux variables : @@ -2265,32 +2344,37 @@ signe près, et de constater qu'on obtient bien le produit de $X-F$ par la même quantité après échange de $Z_1$ et $Z_3$. Cependant, si on se demande comment une telle expression a été trouvée, une méthode consiste à calculer dans l'anneau $\QQ[Z_1,\ldots,Z_4, \mathit{\Pi}, -A_1,\ldots,A_4]$ une base de Gröbner de l'idéal engendré par $A_1 + + A_1,\ldots,A_4]$ une base de Gröbner de l'idéal engendré par $A_1 + (Z_1+Z_2+Z_3+Z_4), \ldots, A_4 - (Z_1 Z_2 Z_3 Z_4)$ et $\mathit{\Pi} - (Z_1 Z_3 + Z_2 Z_4)$ pour l'ordre lexicographique sur les monômes -prolongeant un ordre sur les variables tel que $Z_1, \ldots, Z_4 -> \mathit{\Pi} > A_1, \ldots, A_4$. En réduisant modulo cette base -les coefficients de $R_{D_4,F}$ exprimés dans les variables +prolongeant un ordre sur les variables tel que $Z_1, \ldots, Z_4 > +\mathit{\Pi} > A_1, \ldots, A_4$. En réduisant modulo cette base les +coefficients de $R_{D_4,F}$ exprimés dans les variables $Z_1,\ldots,Z_4$, on obtient leur expression en $a_1,\ldots,a_4$ et -$\pi$.) +$\pi$. On renvoie à \cite[algorithme 2.5.6]{Sturmfels} pour une +justification de ces choix et +à \ref{calcul-resolvantes-par-bases-groebner} pour une discussion.) Grâce à $R_{D_4,F}(f)$, tester si le groupe de Galois $G$ d'un polynôme $f$ est $C_4$ peut se faire selon la stratégie suivante : (i) Calculer $R_P(f)$ en utilisant l'expression donnée plus haut en -fonction des coefficients $a_1,\ldots,a_4$ de $f$, vérifier que -$R_P(f)$ est séparable et tester si elle a une racine dans $k$ : si ce -n'est pas le cas, le groupe de Galois de $f$ n'est pas inclus dans -$D_4$ (et \textit{a fortiori} pas dans $C_4$) ; si c'est le cas, on -sait au moins que le groupe de Galois de $f$ est inclus dans $D_4$ : -appeler $\pi$ la racine trouvée ; (ii) calculer $R_{D_4,F}(f)$ en -utilisant l'expression ci-dessus en fonction des coefficients -$a_1,\ldots,a_4$ de $f$ et de la racine $\pi$ qu'on vient de calculer, -vérifier que $R_{D_4,F}(f)$ est séparable et tester si elle a une -racine dans $k$ : si ce n'est pas le cas, le groupe de Galois de $f$ -n'est pas inclus dans $C_4$, tandis que si c'est le cas, il l'est. Si -l'une des deux résolvantes calculées n'était pas séparable, il -convient de remplacer $f$ par un transformé de Tschirnhaus $f^\$$ -comme expliqué de façon +fonction des coefficients $a_1,\ldots,a_4$ de $f$ (ou par l'une des +méthodes de \ref{calcul-resolvantes-par-calcul-approche} ou +\ref{calcul-resolvantes-par-bases-groebner}), vérifier que $R_P(f)$ +est séparable et tester si elle a une racine dans $k$ : si ce n'est +pas le cas, le groupe de Galois de $f$ n'est pas inclus dans $D_4$ (et +\textit{a fortiori} pas dans $C_4$) ; si c'est le cas, on sait au +moins que le groupe de Galois de $f$ est inclus dans $D_4$ : appeler +$\pi$ la racine trouvée ; (ii) calculer $R_{D_4,F}(f)$ en utilisant +l'expression ci-dessus en fonction des coefficients $a_1,\ldots,a_4$ +de $f$ et de la racine $\pi$ qu'on vient de calculer (ou, de nouveau, +par l'une des méthodes de \ref{calcul-resolvantes-par-calcul-approche} +ou \ref{calcul-resolvantes-par-bases-groebner}), vérifier que +$R_{D_4,F}(f)$ est séparable et tester si elle a une racine dans $k$ : +si ce n'est pas le cas, le groupe de Galois de $f$ n'est pas inclus +dans $C_4$, tandis que si c'est le cas, il l'est. Si l'une des deux +résolvantes calculées n'était pas séparable, il convient de remplacer +$f$ par un transformé de Tschirnhaus $f^\$$ comme expliqué de façon générale \ref{strategie-algorithmique-generale-calcul-groupes-de-galois} (et ce qui est possible d'après \ref{garantir-resolvante-separable-par-transformation-de-tschirnhaus}). |