summaryrefslogtreecommitdiffstats
path: root/notes-geoalg.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2010-06-07 12:39:43 +0200
committerDavid A. Madore <david+git@madore.org>2010-06-07 12:39:43 +0200
commit6e9b98a3074e10bfed62f01cd8857c868f89cf5e (patch)
tree96c1c1351841344bb739ed69b79af97be251115b /notes-geoalg.tex
parent14b013b12aca8d58fb639dde589759241db125d5 (diff)
downloadmdi349-6e9b98a3074e10bfed62f01cd8857c868f89cf5e.tar.gz
mdi349-6e9b98a3074e10bfed62f01cd8857c868f89cf5e.tar.bz2
mdi349-6e9b98a3074e10bfed62f01cd8857c868f89cf5e.zip
Corrections/additions noted during course on 2010-06-07.upload-20100607
Diffstat (limited to 'notes-geoalg.tex')
-rw-r--r--notes-geoalg.tex50
1 files changed, 29 insertions, 21 deletions
diff --git a/notes-geoalg.tex b/notes-geoalg.tex
index ff4edb2..3b72c08 100644
--- a/notes-geoalg.tex
+++ b/notes-geoalg.tex
@@ -3525,26 +3525,27 @@ pour cet ordre monomial).
Lorsque les $f_1,\ldots,f_r$ forment une base de Gröbner (d'un
idéal $I = (f_1,\ldots,f_r)$), on a $f \in (f_1,\ldots,f_r)$ si et
-seulement si $\rho = 0$.
+seulement si $\rho = 0$, et $\rho$ est défini de façon unique par $f$.
\end{algo}
\begin{proof}[Description de l'algorithme]
-Si $\init(f)$ n'est divisible par aucun des $\init(f_i)$,
-retourner $\rho = f$ (et tous les $g_i = 0$). Sinon, mettons
-$\init(f) = c s \init(f_i)$ où $c$ est une constante et $s$ un
-monôme : appliquer récursivement l'algorithme à $f' = f - c s f_i$
-(qui vérifie $\init(f') \prec \init(f)$), si $f' = g'_1 f_1 + \cdots +
-g'_r f_r + \rho'$ est le résultat, renvoyer $g_j = g'_j$ sauf $g_i =
-g'_i + c s$, et $\rho' = \rho$.
+Si aucun terme de $f$ n'est divisible par aucun des $\init(f_i)$,
+retourner $\rho = f$ (et tous les $g_i = 0$). Sinon, soit $c s
+\init(f_i)$ (où $c\neq 0$ est une constante et $s$ un monôme) le
+$\preceq$-plus grand terme de $f$ qui soit divisible par un
+des $\init(f_i)$ : on applique récursivement l'algorithme à $f' = f -
+c s f_i$ (qui vérifie $\init(f') \preceq \init(f)$), si $f' = g'_1 f_1
++ \cdots + g'_r f_r + \rho'$ est le résultat, renvoyer $g_j = g'_j$
+sauf $g_i = g'_i + c s$, et $\rho = \rho'$.
\end{proof}
\begin{proof}
-L'algorithme termine car $\init(f') \prec \init(f)$, donc les monômes
-$\init(f)$ auxquels on l'applique décroissent strictement, or
-$\preceq$ est un bon ordre
+L'algorithme termine car le $\preceq$-plus grand monôme de $f$
+divisible par un des $\init(f_i)$ décroît strictement à chaque
+itération, or $\preceq$ est un bon ordre
(cf. \ref{properties-of-admissible-orders}). La propriété sur $\rho$
-est évidente. La propriété $\init(g_i f_i) \preceq \init(f)$ découle
-par induction de $\init(g'_i f_i) \preceq \init(f') \prec \init(f)$
+est évidente. La propriété $\init(g_j f_j) \preceq \init(f)$ découle
+par induction de $\init(g'_j f_j) \preceq \init(f') \preceq \init(f)$
et $\init(c s f_i) = c s \init(f_i) = c\init(f)$.
Si $\rho = 0$, le fait que $f \in (f_1,\ldots,f_r)$ est trivial. Si
@@ -3552,13 +3553,18 @@ $f_1,\ldots,f_r$ forment une base de Gröbner et $f \in
(f_1,\ldots,f_r)$, comme on a aussi $\rho \in (f_1,\ldots,f_r)$, alors
$\init(\rho) \in (\init(f_1),\ldots,\init(f_r))$, ce qui vu le fait
qu'aucun monôme de $\rho$ n'est divisible par un des $\init(f_i)$,
-n'est possible que si $\rho = 0$ (cf. \ref{divisibilite-monomes}).
+n'est possible que si $\rho = 0$ (cf. \ref{divisibilite-monomes}) ; de
+même, si $\rho$ et $\rho'$ sont deux restes différents du même $f$,
+disons $f = g_1 f_1 + \cdots + g_r f_r + \rho$ et $f = g'_1 f_1 +
+\cdots + g'_r f_r + \rho'$, alors $(g'_1-g_1) f_1 + \cdots +
+(g'_r-g_r) f_r + (\rho'-\rho)$ est une écriture standard de $0$, donc
+$\rho'=\rho$.
\end{proof}
\textbf{Moralité :} Connaître une base de Gröbner d'un idéal $I$
permet de répondre à la question de savoir si $f\in I$ pour un idéal
donné. Mieux, si $(f_1,\ldots,f_r)$ est cette base de Gröbner,
-l'ensemble des monômes qui ne sont divisibles par aucun
+l'ensemble des classes des monômes qui ne sont divisibles par aucun
des $\init(f_i)$ constitue une base de $k[t_1,\ldots,t_d]/I$, ce qui,
avec l'algorithme de division, permet de calculer dans l'anneau en
question.
@@ -3568,9 +3574,11 @@ très bien avoir $\rho \neq 0$ et pourtant que $\rho$
(c'est-à-dire, $f$) appartienne à l'idéal $(f_1,\ldots,f_r)$. Par
exemple, pour deux polynômes, $g_1 f_1 + g_2 f_2$ pourrait avoir un
coefficient initial beaucoup plus petit que ceux de $f_1,f_2$ à cause
-d'une annulation entre ceux-ci. L'algorithme de Buchberger pour
-calculer les bases de Gröbner se fonde sur l'idée qu'il suffit
-d'éviter ce phénomène.
+d'une annulation entre ceux-ci (dans ce cas, l'algorithme de division
+appliqué à $g_1 f_1 + g_2 f_2$ par rapport à $f_1,f_2$ donnerait $g_1
+f_1 + g_2 f_2$ lui-même comme reste, bien que ce polynôme appartienne
+à $(f_1,f_2)$). L'algorithme de Buchberger pour calculer les bases de
+Gröbner se fonde sur l'idée qu'il suffit d'éviter ce phénomène.
%
@@ -3615,7 +3623,7 @@ et seulement $f_1,\ldots,f_r$ forment une base de Gröbner (de l'idéal
qu'ils engendrent).
(Spears-Schreyer) De plus, lorsque c'est le cas, les relations
-$c_{j,i} s_{j,i} f_i - c_{i,j} s_{i,j} f_j + \sum_u g^{(i,j)}_u f_u$,
+$c_{j,i} s_{j,i} f_i - c_{i,j} s_{i,j} f_j - \sum_u g^{(i,j)}_u f_u$,
où $f_{i,j} = g^{(i,j)}_1 f_1 + \cdots + g^{(i,j)}_r f_r$ est une
écriture standard de $f_{i,j}$, engendrent\footnote{En fait, les
relations en question forment elles-même une base de Gröbner du
@@ -3695,12 +3703,12 @@ $t_1,\ldots,t_s$ comme premier critère de comparaison, et en cas
d'égalité comparer avec $\mathrel{\preceq_{\mathtt{grevlex}}}$.)
\begin{prop}
-Soit $I$ un idéal de $k[t_1,\ldots,t_d]$ et $s \leq d$. Alors $V(I
+Soit $I$ un idéal de $k[t_1,\ldots,t_d]$ et $s \leq d$. Alors $Z(I
\cap k[t_1,\ldots,t_s])$ est l'adhérence de Zariski dans
$\mathbb{A}^s$ de la projection (c'est-à-dire l'image au sens
de \ref{image-of-a-morphism} par le morphisme $\mathbb{A}^d \to
\mathbb{A}^s$ qui projette sur les $s$ premières coordonnées
-c'est-à-dire $(x_1,\ldots,x_d) \mapsto (x_1,\ldots,x_d)$) de $V(I)$.
+c'est-à-dire $(x_1,\ldots,x_d) \mapsto (x_1,\ldots,x_d)$) de $Z(I)$.
\end{prop}