summaryrefslogtreecommitdiffstats
path: root/chapitres
diff options
context:
space:
mode:
authorFabrice (eramangarria) <Fabrice.Orgogozo+git@gmail.com>2012-08-30 17:19:18 +0200
committerFabrice (eramangarria) <Fabrice.Orgogozo+git@gmail.com>2012-08-30 17:19:18 +0200
commit65fc33d9efeed4c8553e22294add8b7c9a0a28f1 (patch)
treee31fd21790488c9d1910e7df5bb6a84af9725218 /chapitres
parent8c8e8daca294bceb61294de1f9a04adf44a22ba7 (diff)
parent00f0d679a90f4b0661866076fd692dec477ed7c2 (diff)
downloadgalois-65fc33d9efeed4c8553e22294add8b7c9a0a28f1.zip
galois-65fc33d9efeed4c8553e22294add8b7c9a0a28f1.tar.gz
galois-65fc33d9efeed4c8553e22294add8b7c9a0a28f1.tar.bz2
Merge branch 'master' of git.madore.org:galois
Diffstat (limited to 'chapitres')
-rw-r--r--chapitres/bases-groebner.tex91
1 files changed, 75 insertions, 16 deletions
diff --git a/chapitres/bases-groebner.tex b/chapitres/bases-groebner.tex
index e28c289..72d67d2 100644
--- a/chapitres/bases-groebner.tex
+++ b/chapitres/bases-groebner.tex
@@ -148,11 +148,11 @@ Réciproquement, si c'est le cas, $f$ est somme de termes multiples
des $s_i$, qui appartiennent donc à l'idéal engendré par les $s_i$.
\end{proof}
-\begin{corollaire2}
+\begin{corollaire2}\label{equivalences-ideaux-monomiaux}
Si $I$ est un idéal de $k[Z_1,\ldots,Z_d]$, les deux propriétés
suivantes sont équivalentes :
\begin{itemize}
-\item l'idéal $I$ est engendré par des monômes,
+\item l'idéal $I$ est engendré par des monômes (ou : par tous ses monômes),
\item tout terme d'un élément de $I$ est élément de $I$.
\end{itemize}
\end{corollaire2}
@@ -525,7 +525,7 @@ l'idéal initial de $I$ comme l'ensemble des polynômes qui sont
combinaisons linéaires de monômes chacun divisible par un
$\initial_{\preceq}(f)$ pour $f\in I$.
-\begin{proposition2}
+\begin{proposition2}\label{inclusion-ideaux-et-egalite-ideaux-initiaux}
Si $J \subseteq I$ sont deux idéaux de $k[Z_1,\ldots,Z_d]$ et que
$\initial(J) = \initial(I)$ (relativement à un certain ordre
admissible $\preceq$), alors $J = I$.
@@ -1177,22 +1177,81 @@ en réduisant de nouveau par l'algorithme de division.
%
\subsection{Bases de Gröbner et élimination}
+\subsubsection{} Si $I = (f_1,\ldots,f_r)$ est un idéal de
+$k[Z_1,\ldots,Z_d]$ et $t \leq d$, l'idéal $J = I \cap
+k[Z_1,\ldots,Z_t]$ est appelé un \emph{idéal d'élimination} de $I$.
+Une interprétation intuitive de cette opération, justifiant le nom,
+consiste à imaginer que $I$ décrit un ensemble de relations
+algébriques entre les indéterminées $Z_1,\ldots,Z_d$ (relations
+engendrées par les relations données $f_1,\ldots,f_r$) et que l'idéal
+$J$ consiste en celles qui ne concernent que les $t$ premières
+indéterminées : trouver des générateurs de $J$ revient donc à
+« éliminer » les variables $Z_{t+1},\ldots,Z_d$ d'entre les équations
+$f_1{=}0,\ldots,f_r{=}0$, et trouver les meilleures relations
+possibles entre les $t$ variables restantes. (En admettant certains
+résultats de géométrie algébrique notamment le Nullstellensatz \XXX,
+lorsque $k$ est algébriquement clos, l'ensemble $\mathscr{Z}(J)$ des
+$t$-uplets $(z_1,\ldots,z_t)$ vérifiant les équations en question est
+simplement la \emph{projection} sur les $t$ premières coordonnées de
+l'ensemble $\mathscr{Z}(I)$ des $d$-uplets $(z_1,\ldots,z_d)$
+vérifiant $f_i(z_1,\ldots,z_d)=0$.) Ce problème de trouver des
+générateurs de $J$ est le problème fondamental de la théorie de
+l'élimination. Les bases de Gröbner fournissent un algorithme
+permettant de le résoudre :
+
\begin{proposition2}
-Soit $I$ un idéal de $k[Z_1,\ldots,Z_d]$ et $s\leq d$ : si
-$f_1,\ldots,f_r$ est une base de Gröbner de $I$ pour
-l'ordre $\mathrel{\preceq_{\mathtt{lex}}}$ (où on est convenu que $Z_1
-\preceq Z_2 \preceq \cdots \preceq Z_d$), alors ceux des $f_i$ qui
-appartiennent à $k[Z_1,\ldots,Z_s]$ forment une base de Gröbner de $I
-\cap k[Z_1,\ldots,Z_s]$.
+Soit $I$ un idéal de $k[Z_1,\ldots,Z_d]$ et $t\leq d$ : notons $J = I
+\cap k[Z_1,\ldots,Z_t]$. Alors on a $\initial_{\mathtt{lex}}(J) =
+\initial_{\mathtt{lex}}(I) \cap k[Z_1,\ldots,Z_t]$ (où on est convenu
+d'ordonner les variables de la manière $Z_1 \preceq Z_2 \preceq \cdots
+\preceq Z_d$) ; et si $B = \{f_1,\ldots,f_r\}$ est une base de Gröbner
+de $I$ pour l'ordre $\mathrel{\preceq_{\mathtt{lex}}}$, alors $B \cap
+k[Z_1,\ldots,Z_t]$ est une base de Gröbner de $J$.
+
+Plus généralement, ces affirmations (à $t$ fixé) valent pour tout
+ordre admissible $\preceq$ vérifiant la propriété suivante : si
+$\initial_{\preceq}(f) \in k[Z_1,\ldots,Z_t]$ alors $f \in
+k[Z_1,\ldots,Z_t]$.
\end{proposition2}
+\begin{proof}
+La propriété énoncée dans le second paragraphe est bien vérifiée (pour
+tout $t$) par l'ordre lexicographique
+d'après \ref{caracterisation-ordre-lexicographique-pur} : on va donc
+montrer les résultats sous cette hypothèse.
+
+Quitte à réordonner les $f_i$, convenons que $B \cap k[Z_1,\ldots,Z_t]
+= \{f_1,\ldots,f_u\}$.
+
+Il est clair que $(\initial(f_1),\ldots,\initial(f_u)) \subseteq
+\initial(J) \subseteq \initial(I) \cap k[Z_1,\ldots,Z_t]$. On va
+montrer que $\initial(f_1),\ldots,\initial(f_u)$ engendrent
+$\initial(I) \cap k[Z_1,\ldots,Z_t]$, c'est-à-dire
+$(\initial(f_1),\ldots,\initial(f_u)) = \initial(J) = initial(I) \cap
+k[Z_1,\ldots,Z_t]$ : ceci prouvera à la fois que $f_1,\ldots,f_u$
+forment une base de Gröbner de $J$ et que $J = I \cap
+k[Z_1,\ldots,Z_t]$.
+
+Soit $s \in \initial(I) \cap k[Z_1,\ldots,Z_t]$ un monôme (il suffit
+de montrer que $\initial(f_1),\ldots,\initial(f_u)$ engendrent les
+tels $s$, cf. \ref{equivalences-ideaux-monomiaux}) : comme
+$\initial(f_1),\ldots,\initial(f_t)$ engendrent $\initial(I)$, il
+existe $i$ tel que $\initial(f_i)$
+divise $s$ (\ref{composition-ideaux-monomiaux}). Puisque $s \in
+k[Z_1,\ldots,Z_t]$, on a aussi $\initial(f_i) \in k[Z_1,\ldots,Z_t]$,
+et l'hypothèse faite sur $\preceq$ impose $f_i \in k[Z_1,\ldots,Z_t]$,
+c'est-à-dire $i\leq u$.
+\end{proof}
+
+\XXX --- Eisenbud (proposition 15.29) prétend utiliser la
+proposition \ref{inclusion-ideaux-et-egalite-ideaux-initiaux}
+(lemme 15.5 chez lui). Je ne vois pas où ça sert : me suis-je trompé
+dans cette démonstration ?
-(En fait, il suffit que l'ordre $\preceq$ utilisé vérifie la
-propriété : si $\initial_{\preceq}(f) \in k[Z_1,\ldots,Z_s]$ alors $f \in
-k[Z_1,\ldots,Z_s]$. Une façon parfois plus efficace que l'ordre
-lexicographique pur, \emph{si on connaît $s$ à l'avance}, consiste à
-prendre l'ordre sur le degré total en les seules variables
-$Z_1,\ldots,Z_s$ comme premier critère de comparaison, et en cas
-d'égalité comparer avec $\mathrel{\preceq_{\mathtt{grevlex}}}$.)
+(Une façon parfois plus efficace que l'ordre lexicographique pur,
+\emph{si on connaît $t$ à l'avance}, consiste à prendre l'ordre sur le
+degré total en les seules variables $Z_1,\ldots,Z_t$ comme premier
+critère de comparaison, et en cas d'égalité comparer avec
+$\mathrel{\preceq_{\mathtt{grevlex}}}$.)