diff options
author | David A. Madore <david+git@madore.org> | 2012-12-06 16:26:01 +0100 |
---|---|---|
committer | David A. Madore <david+git@madore.org> | 2012-12-06 16:26:01 +0100 |
commit | e6d5ca0e70e417b822fab26363b3c2bd04dab99a (patch) | |
tree | ec6f7bc6feb78861ee909e13bc57b87fe860de51 /chapitres | |
parent | 90a16bf7bf74308b2bec4b10ce946e2dc409127c (diff) | |
download | galois-e6d5ca0e70e417b822fab26363b3c2bd04dab99a.tar.gz galois-e6d5ca0e70e417b822fab26363b3c2bd04dab99a.tar.bz2 galois-e6d5ca0e70e417b822fab26363b3c2bd04dab99a.zip |
[Gröbner] Déplacement dans une nouvelle sous-section.
Diffstat (limited to 'chapitres')
-rw-r--r-- | chapitres/bases-groebner.tex | 133 |
1 files changed, 69 insertions, 64 deletions
diff --git a/chapitres/bases-groebner.tex b/chapitres/bases-groebner.tex index a27e2d1..c24aa0a 100644 --- a/chapitres/bases-groebner.tex +++ b/chapitres/bases-groebner.tex @@ -1283,6 +1283,12 @@ C'est une conséquence immédiate de la proposition précédente et de \ref{bases-de-groebner-et-extensions-de-corps}. \end{proof} + +% +\subsection{Ajout d'une variable et calcul d'inverse} + +\XXX --- Il est tout pourri le titre de cette section ! + \begin{proposition2}\label{borne-degre-base-groebner-sur-une-variable-dominante} Soit $\preceq$ un ordre monomial sur $k[Z_1,\ldots,Z_d,Y]$ tel que $Y$ soit supérieur à tout monôme en $Z_1,\ldots,Z_d$. Soient @@ -1310,8 +1316,69 @@ c'est le cas de $S(h_i,h_j)$. \end{proof} \XXX --- Ce serait mieux de donner une démontration qui n'utilise pas -la construction algorithmique. Par ailleurs, il faudrait sans doute -déplacer cette proposition à un autre endroit. +la construction algorithmique. + +\begin{algorithme2}\label{algorithme-calcul-inverse-algebre-de-type-fini} +Donné un idéal $I$ (défini par ses générateurs) de +$k[Z_1,\ldots,Z_d]$, et $x$ un élément de $k[Z_1,\ldots,Z_d]/I$, on +peut déterminer si $x$ est inversible dans cette algèbre et, le cas +échéant, en calculer un inverse. +\end{algorithme2} +\begin{proof}[Description de l'algorithme] +Introduisons une nouvelle variable $Y$ : soit $\tilde I$ l'idéal de +$k[Z_1,\ldots,Z_d,Y]$ engendré par $I$ (c'est-à-dire, par les +générateurs donnés de $I$) et par $\hat x Y - 1$ (où $\hat x$ est un +relèvement quelconque de $x$ à $k[Z_1,\ldots,Z_d]$, étant évident que +$\tilde I$ ne dépend pas de ce choix). On calcule la base de Gröbner +réduite $\tilde B$ de $\tilde I$ pour un ordre monomial $\preceq$ +quelconque qui ordonne $Y$ après n'importe quel monôme en +$Z_1,\ldots,Z_d$. Cette base est de la forme $B' \cup C$ où $B' = +\tilde B \cap k[Z_1,\ldots,Z_d]$ est la base de Gröbner réduite de $I' += \tilde I \cap k[Z_1,\ldots,Z_d]$ (pour le même ordre monomial, +c'est-à-dire, pour sa restriction aux monômes en $Z_1,\ldots,Z_d$) et +$C$ est formé de polynômes dont le degré partiel en $Y$ vaut +exactement $1$. L'élément $x$ est inversible si et seulement si $I' = +I$ (ce qui se teste en vérifiant que les bases de Gröbner réduites +coïncident) et que $C$ est (soit vide, soit) réduit à un unique +polynôme de la forme $Y - g$ avec $g \in k[Z_1,\ldots,Z_d]$ ; et +lorsque c'est le cas, la classe de $g$ modulo $I$ est l'inverse +recherché (quant au cas où $I'=I$ et $C$ est vide, il ne se produit +que lorsque $k[Z_1,\ldots,Z_d]/I$ est l'algèbre nulle, ce cas étant +trivial). +\end{proof} +\begin{proof} +On sait d'après \ref{base-de-groebner-elimination} que l'ensemble $B' += \tilde B \cap k[Z_1,\ldots,Z_d]$ des éléments de $\tilde B$ ne +faisant intervenir que les variables $Z_1,\ldots,Z_d$ est la base de +Gröbner réduite de $I' = \tilde I \cap k[Z_1,\ldots,Z_d]$ (soulignons +que cet idéal contient $I$). On sait aussi +d'après \ref{borne-degre-base-groebner-sur-une-variable-dominante} que +les degrés en $Y$ des éléments de $\tilde B$ sont majorés par $1$. On +pose $C = \tilde B \setminus B'$ l'ensemble des éléments de $\tilde B$ +faisant effectivement intervenir $Y$. + +Notons $A = k[Z_1,\ldots,Z_d]/I$ : on a alors +$k[Z_1,\ldots,Z_d,Y]/\tilde I = A[Y]/(xY-1)$. Soit $\varphi \colon A +\to A[Y]/(xY-1)$ le morphisme évident. L'idéal $I'$ est l'image +réciproque dans $k[Z_1,\ldots,Z_d]$ du noyau de $\varphi$. + +Supposons d'abord $x$ inversible dans $A$, d'inverse $x^{-1}$ : alors +$A[Y]/(xY-1) = A[Y]/(Y-x^{-1})$ et $\varphi$ est un isomorphisme. En +particulier, $I' = I$ (puisque $\varphi$ est injectif). D'autre part, +si $g \in k[Z_1,\ldots,Z_d]$ représente $x^{-1}$ modulo $I$, alors $Y +- g$ est dans $\tilde I$. Cet élément a pour monôme initial $Y$ donc +il y a dans $\tilde B$ a un élément de monôme initial $Y$ (sauf si $A$ +est l'algèbre nulle, cas que nous écarterons), donc dans $C$ ; et +comme la base de Gröbner $\tilde B$ était supposée réduite, cet +élément est l'unique élément de $C$, et il est manifestement de la +forme $Y - g$ avec $g$ représentant $x^{-1}$ modulo $I$. + +Réciproquement, supposons que $I' = I$, c'est-à-dire que $\varphi$ est +injective, et que $C$ contient un élément de la forme $Y - g$ : alors +$\varphi$ envoie la classe de $g$ sur celle de $Y$, donc $\varphi$ est +surjectif, et c'est un isomorphisme. En particulier, $x$ est +inversible d'inverse $\varphi^{-1}(Y)$. +\end{proof} \section{Idéaux de dimension $0$} @@ -1453,68 +1520,6 @@ condition de \ref{equivalences-ideaux-affines-dimension-zero} est alors manifestement satisfaite de $J$ si elle l'est de $I$. \end{proof} -\begin{algorithme2}\label{algorithme-calcul-inverse-algebre-de-type-fini} -Donné un idéal $I$ (défini par ses générateurs) de -$k[Z_1,\ldots,Z_d]$, et $x$ un élément de $k[Z_1,\ldots,Z_d]/I$, on -peut déterminer si $x$ est inversible dans cette algèbre et, le cas -échéant, en calculer un inverse. -\end{algorithme2} -\begin{proof}[Description de l'algorithme] -Introduisons une nouvelle variable $Y$ : soit $\tilde I$ l'idéal de -$k[Z_1,\ldots,Z_d,Y]$ engendré par $I$ (c'est-à-dire, par les -générateurs donnés de $I$) et par $\hat x Y - 1$ (où $\hat x$ est un -relèvement quelconque de $x$ à $k[Z_1,\ldots,Z_d]$, étant évident que -$\tilde I$ ne dépend pas de ce choix). On calcule la base de Gröbner -réduite $\tilde B$ de $\tilde I$ pour un ordre monomial $\preceq$ -quelconque qui ordonne $Y$ après n'importe quel monôme en -$Z_1,\ldots,Z_d$. Cette base est de la forme $B' \cup C$ où $B' = -\tilde B \cap k[Z_1,\ldots,Z_d]$ est la base de Gröbner réduite de $I' -= \tilde I \cap k[Z_1,\ldots,Z_d]$ (pour le même ordre monomial, -c'est-à-dire, pour sa restriction aux monômes en $Z_1,\ldots,Z_d$) et -$C$ est formé de polynômes dont le degré partiel en $Y$ vaut -exactement $1$. L'élément $x$ est inversible si et seulement si $I' = -I$ (ce qui se teste en vérifiant que les bases de Gröbner réduites -coïncident) et que $C$ est (soit vide, soit) réduit à un unique -polynôme de la forme $Y - g$ avec $g \in k[Z_1,\ldots,Z_d]$ ; et -lorsque c'est le cas, la classe de $g$ modulo $I$ est l'inverse -recherché (quant au cas où $I'=I$ et $C$ est vide, il ne se produit -que lorsque $k[Z_1,\ldots,Z_d]/I$ est l'algèbre nulle, ce cas étant -trivial). -\end{proof} -\begin{proof} -On sait d'après \ref{base-de-groebner-elimination} que l'ensemble $B' -= \tilde B \cap k[Z_1,\ldots,Z_d]$ des éléments de $\tilde B$ ne -faisant intervenir que les variables $Z_1,\ldots,Z_d$ est la base de -Gröbner réduite de $I' = \tilde I \cap k[Z_1,\ldots,Z_d]$ (soulignons -que cet idéal contient $I$). On sait aussi -d'après \ref{borne-degre-base-groebner-sur-une-variable-dominante} que -les degrés en $Y$ des éléments de $\tilde B$ sont majorés par $1$. On -pose $C = \tilde B \setminus B'$ l'ensemble des éléments de $\tilde B$ -faisant effectivement intervenir $Y$. - -Notons $A = k[Z_1,\ldots,Z_d]/I$ : on a alors -$k[Z_1,\ldots,Z_d,Y]/\tilde I = A[Y]/(xY-1)$. Soit $\varphi \colon A -\to A[Y]/(xY-1)$ le morphisme évident. L'idéal $I'$ est l'image -réciproque dans $k[Z_1,\ldots,Z_d]$ du noyau de $\varphi$. - -Supposons d'abord $x$ inversible dans $A$, d'inverse $x^{-1}$ : alors -$A[Y]/(xY-1) = A[Y]/(Y-x^{-1})$ et $\varphi$ est un isomorphisme. En -particulier, $I' = I$ (puisque $\varphi$ est injectif). D'autre part, -si $g \in k[Z_1,\ldots,Z_d]$ représente $x^{-1}$ modulo $I$, alors $Y -- g$ est dans $\tilde I$. Cet élément a pour monôme initial $Y$ donc -il y a dans $\tilde B$ a un élément de monôme initial $Y$ (sauf si $A$ -est l'algèbre nulle, cas que nous écarterons), donc dans $C$ ; et -comme la base de Gröbner $\tilde B$ était supposée réduite, cet -élément est l'unique élément de $C$, et il est manifestement de la -forme $Y - g$ avec $g$ représentant $x^{-1}$ modulo $I$. - -Réciproquement, supposons que $I' = I$, c'est-à-dire que $\varphi$ est -injective, et que $C$ contient un élément de la forme $Y - g$ : alors -$\varphi$ envoie la classe de $g$ sur celle de $Y$, donc $\varphi$ est -surjectif, et c'est un isomorphisme. En particulier, $x$ est -inversible d'inverse $\varphi^{-1}(Y)$. -\end{proof} - \subsection{Algèbre de décomposition universelle d'un polynôme}\label{section-algebre-de-decomposition-universelle} |