summaryrefslogtreecommitdiffstats
path: root/chapitres
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2012-12-06 16:26:01 +0100
committerDavid A. Madore <david+git@madore.org>2012-12-06 16:26:01 +0100
commite6d5ca0e70e417b822fab26363b3c2bd04dab99a (patch)
treeec6f7bc6feb78861ee909e13bc57b87fe860de51 /chapitres
parent90a16bf7bf74308b2bec4b10ce946e2dc409127c (diff)
downloadgalois-e6d5ca0e70e417b822fab26363b3c2bd04dab99a.zip
galois-e6d5ca0e70e417b822fab26363b3c2bd04dab99a.tar.gz
galois-e6d5ca0e70e417b822fab26363b3c2bd04dab99a.tar.bz2
[Gröbner] Déplacement dans une nouvelle sous-section.
Diffstat (limited to 'chapitres')
-rw-r--r--chapitres/bases-groebner.tex133
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}