Buchberger's algorithm.

1 files changed, 156 insertions, 8 deletions

diff --git a/notes-geoalg.tex b/notes-geoalg.tex
index 4115ab0..6d90bbd 100644
--- a/notes-geoalg.tex
+++ b/notes-geoalg.tex
@@ -31,6 +31,7 @@
 \newtheorem{cor}[comcnt]{Corollaire}
 \newtheorem{rmk}[comcnt]{Remarque}
 \newtheorem{scho}[comcnt]{Scholie}
+\newtheorem{algo}[comcnt]{Algorithme}
 \newtheorem{exmps}[comcnt]{Exemples}
 \newtheorem{princ}[comcnt]{Principe}
 \newcommand{\limp}{\mathrel{\Rightarrow}}
@@ -3343,16 +3344,19 @@ engendrent $I$).
 %
 \subsection{Ordres admissibles sur les monômes}
 
-On appelle \textbf{ordre admissible} sur les monômes de
-$k[t_1,\ldots,t_d]$ une relation d'ordre total $\preceq$ sur les
-monômes de ce dernier telle que :
+On appelle \textbf{ordre admissible} (ou \textbf{ordre monomial}) sur
+les monômes de $k[t_1,\ldots,t_d]$ une relation d'ordre total
+$\preceq$ sur les monômes de ce dernier telle que :
 \begin{itemize}
 \item $1 \preceq s$ pour tout monôme $s$, et
 \item si $s_1 \preceq s_2$ et $s$ est un monôme quelconque, alors $s
   s_1 \preceq s s_2$.
 \end{itemize}
+(On notera souvent abusivement $c s \preceq c' s'$, lorsque $cs, c's'$
+sont deux termes, pour signifier que leurs monômes vérifient $s
+\preceq s'$.)
 
-\begin{prop}
+\begin{prop}\label{properties-of-admissible-orders}
 Si $\preceq$ est un ordre admissible sur les monômes de
 $k[t_1,\ldots,t_d]$, alors
 \begin{itemize}
@@ -3383,10 +3387,11 @@ celui donné par $t^\ell \preceq t^{\ell'}$ ssi $\ell \leq \ell'$.
 Une fois fixé un ordre admissible $\preceq$ sur les monômes, si $f \in
 k[t_1,\ldots,t_d]$ est non nul, on note $\init_{\preceq}(f)$ (ou
 simplement $\init(f)$ si l'ordre est sous-entendu) et on appelle
-« terme initial de $f$ » le terme au \emph{plus grand} monôme pour
-l'ordre en question.  (Lorsque $d=1$, pour le seul ordre admissible
-sur les monômes, ceci est simplement le terme dominant de $f$.)  Si
-$f=0$ on pose (un peu abusivement) $\init(f) = 0$.
+\textbf{terme initial} (ou \textbf{terme de tête}) de $f$ le terme au
+\emph{plus grand} monôme pour l'ordre en question.  (Lorsque $d=1$,
+pour le seul ordre admissible sur les monômes, ceci est simplement le
+terme dominant de $f$.)  Si $f=0$ on pose (un peu abusivement)
+$\init(f) = 0$.
 
 \medbreak
 
@@ -3497,6 +3502,149 @@ strictement plus petit que $h$, donc par minimalité de ce dernier, $h
 une contradiction.
 \end{proof}
 
+Une évidence : tout idéal admet une base de Gröbner.  En effet, parmi
+les $\init(f)$ pour $f\in I$ qui engendrent $\init(I)$ on peut
+extraire un ensemble fini engendrant $\init(I)$ --- il s'agit d'une
+base de Gröbner de $I$.
+
+\begin{algo}[algorithme de division]\label{algorithme-de-division}
+Soient $f,f_1,\ldots,f_r \in k[t_1,\ldots,t_d]$ et $\preceq$ un ordre
+admissible sur les monômes.  Alors il existe une écriture
+\[
+f = g_1 f_1 + \cdots + g_r f_r + \rho
+\tag{$*$}
+\]
+où $g_1,\ldots,g_r,\rho \in k[t_1,\ldots,t_d]$, où aucun des monômes
+de $\rho$ n'est divisible par un des $\init(f_i)$, et où $\init(g_i
+f_i) \preceq \init(f)$ pour chaque $i$ ; et on va donner un algorithme
+pour calculer cette écriture ; un tel $\rho$ s'appelle un
+\textbf{reste} de $f$ par rapport au $f_1,\ldots,f_r$ et pour l'ordre
+monomial $\preceq$ (on dit aussi que l'écriture ($*$) s'appelle une
+\textbf{écriture standard} de $f$ par rapport aux $f_1,\ldots,f_r$ et
+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$.
+\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$.
+\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
+(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)$
+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
+$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}).
+\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
+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.
+
+Lorsque $f_1,\ldots,f_r$ ne forment pas une base de Gröbner, on peut
+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.
+
+
+%
+\subsection{L'algorithme de Buchberger}
+
+Soient $f_1,\ldots,f_r\in k[t_1,\ldots,t_d]$ : pour chaque
+couple $(i,j)$ (où $i \neq j$), on définit le \textbf{polynôme de
+  syzygie} entre $f_i$ et $f_j$ :
+\[
+\begin{array}{c}
+f_{i,j} = c_{j,i} s_{j,i} f_i - c_{i,j} s_{i,j} f_j\\
+\hbox{où~}
+c_{i,j} s_{i,j} = \init(f_i)/\pgcd(\init(f_i),\init(f_j))
+\end{array}
+\]
+Le pgcd (unitaire) de deux termes $c s$ et $c' s'$ étant défini comme
+le plus grand monôme (pour n'importe quel ordre admissible, ou pour
+l'ordre partiel de divisibilité) parmi les monômes qui divisent à la
+fois $s$ et $s'$ (c'est-à-dire $t_1^{\min(\ell_1,\ell'_1)} \cdots
+t_d^{\min(\ell_d,\ell'_d)}$ si $s = t_1^{\ell_1} \cdots t_d^{\ell_d}$
+et $s' = t_1^{\ell'_1} \cdots t_d^{\ell'_d}$).  Remarquons que
+$c_{i,j} s_{i,j} f_i$ et $c_{j,i} s_{j,i} f_j$ ont le même terme
+initial, de sorte que celui de $f_{i,j}$ a un monôme strictement plus
+petit.  (Bien sûr, $f_{i,i} = 0$ pour tout $i$, donc on ne s'intéresse
+qu'aux $f_{i,j}$ pour $i\neq j$.)
+
+On appelle \textbf{module des relations} entre $f_1,\ldots,f_r$
+l'ensemble (qui est un sous-module de $(k[t_1,\ldots,t_d])^r$, d'où le
+terme) des $(g_1,\ldots,g_r)$ tels que $g_1 f_1 + \cdots + g_r f_r =
+0$, ces $(g_1,\ldots,g_r)$ étant appelés des \textbf{relations} entre
+les $f_i$ (relation non-triviale si les $g_i$ ne sont pas tous nuls).
+
+Soit $\rho_{i,j}$ le reste (au sens de \ref{algorithme-de-division})
+de $f_{i,j}$ par rapport aux $f_1,\ldots,f_r$ (pour un ordre
+monomial $\preceq$) : si les $f_1,\ldots,f_r$ forment une base de
+Gröbner alors $\rho_{i,j} = 0$ puisque $f_{i,j} \in (f_1,\ldots,f_r)$.
+Ce qui est plus surprenant est que la réciproque est également vraie :
+
+\begin{thm}[critère de Buchberger]
+Avec les notations ci-dessus, on a $\rho_{i,j} = 0$ pour tous $i,j$ si
+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$,
+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
+  module des relations, si on prend la peine de définir la notion de
+  « base de Gröbner » d'un module et non seulement d'un idéal, pour un
+  ordre admissible sur les monômes de $k[t_1,\ldots,t_d]^r$ qui se
+  déduit facilement de $\preceq$.} le module des relations
+entre $f_1,\ldots,f_r$.
+\end{thm}
+
+\begin{algo}[algorithme de Buchberger]
+Donné $f_1,\ldots,f_r \in k[t_1,\ldots,t_d]$, on peut calculer
+effectivement une base de Gröbner de l'idéal qu'ils engendrent.
+\end{algo}
+\begin{proof}[Description de l'algorithme]
+Calculer les $\rho_{i,j}$ définis plus hauts : si les $\rho_{i,j}$
+sont tous nuls, terminer (les $f_1,\ldots,f_r$ forment une base de
+Gröbner).  Si un des $\rho_{i,j}$ est non nul, dès qu'on le trouve,
+ajouter ce $\rho_{i,j}$ parmi les $f_1,\ldots,f_r$ (c'est-à-dire,
+recommencer l'algorithme avec $f_1,\ldots,f_r,\rho_{i,j}$).
+\end{proof}
+\begin{proof}
+L'algorithme termine car l'idéal engendré par
+$\init(f_1),\ldots,\init(f_r)$ ne cesse de croître strictement : le
+processus doit donc terminer, ce qui ne peut se produire que parce que
+tous les $\rho_{i,j}$ sont tous nuls, et le critère précédent permet
+de dire qu'on a bien une base de Gröbner.
+\end{proof}
+
 
 
 %