diff options
author | David A. Madore <david+git@madore.org> | 2012-12-06 16:23:39 +0100 |
---|---|---|
committer | David A. Madore <david+git@madore.org> | 2012-12-06 16:23:39 +0100 |
commit | 90a16bf7bf74308b2bec4b10ce946e2dc409127c (patch) | |
tree | b63aa44e40edcde79557b21039e4a3e468a91d47 | |
parent | 06d6885f8f65c9e606e705cf9f8b54dce14602b5 (diff) | |
download | galois-90a16bf7bf74308b2bec4b10ce946e2dc409127c.tar.gz galois-90a16bf7bf74308b2bec4b10ce946e2dc409127c.tar.bz2 galois-90a16bf7bf74308b2bec4b10ce946e2dc409127c.zip |
[Gröbner] Algorithme de calcul de l'inverse (remaniement + fin de la démonstration).
-rw-r--r-- | chapitres/bases-groebner.tex | 58 |
1 files changed, 40 insertions, 18 deletions
diff --git a/chapitres/bases-groebner.tex b/chapitres/bases-groebner.tex index 1c15972..a27e2d1 100644 --- a/chapitres/bases-groebner.tex +++ b/chapitres/bases-groebner.tex @@ -1467,30 +1467,52 @@ 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'$ 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 et que celui-ci est 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). +$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$). Si on note $A = k[Z_1,\ldots,Z_d]/I$, -alors $k[Z_1,\ldots,Z_d,Y]/\tilde I = A[Y]/(xY-1)$. L'élément $x$ de -$A$ est inversible si et seulement si la flèche évidente $A \to -A[Y]/(xY-1)$ est un isomorphisme. - -\XXX +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} |