Start section on Gröbner bases: monomial ideals, admissible orders, and definition of Gröbner bases.upload-20100604

1 files changed, 152 insertions, 2 deletions

diff --git a/notes-geoalg.tex b/notes-geoalg.tex
index f9aa9a6..94038c5 100644
--- a/notes-geoalg.tex
+++ b/notes-geoalg.tex
@@ -45,6 +45,7 @@
 \newcommand{\degtrans}{\operatorname{deg.tr}}
 \newcommand{\Gal}{\operatorname{Gal}}
 \newcommand{\alg}{\operatorname{alg}}
+\newcommand{\init}{\operatorname{in}}
 \renewcommand{\qedsymbol}{\smiley}
 %
 \DeclareUnicodeCharacter{00A0}{~}
@@ -3284,9 +3285,158 @@ il n'y a pas besoin de passer à la clôture algébrique).
 %
 %
 
-\section{TODO}
+\section{Introduction aux bases de Gröbner}
+
+\subsection{Monômes et idéaux monomiaux}
+
+On appelle \textbf{monôme} de $k[t_1,\ldots,t_d]$ un
+$t_1^{\ell_1}\cdots t_d^{\ell_d}$.  On dit qu'un monôme
+$t_1^{\ell_1}\cdots t_d^{\ell_d}$ \textbf{divise} un monôme
+$t_1^{\ell'_1}\cdots t_d^{\ell'_d}$ lorsque $\ell_i \leq \ell'_i$ pour
+tout $i$ (c'est bien la relation de divisibilité dans l'anneau
+factoriel $k[t_1,\ldots,t_d]$, restreinte aux monômes, et le rapport
+est alors lui-même un monôme).  Un \textbf{terme} est un monôme
+multiplié par une constante (=élément de $k$) non nulle : on parle
+alors du monôme \emph{de} ce terme.  Tout polynôme s'écrit de façon
+unique comme somme de termes dont les monômes sont distincts : ce sont
+les termes de (=intervenant dans) ce polynôme.
+
+Commençons par la remarque suivante, qui est évidente, mais
+essentielle :
+\begin{prop}\label{divisibilite-monomes}
+Si $s_1,\ldots,s_r$ sont des monômes de $k[t_1,\ldots,t_d]$, alors
+pour chaque terme $c s$ de $g_1 s_1 + \cdots + g_r s_r$ (où
+$g_1,\ldots,g_r \in k[t_1,\ldots,t_d]$) le monôme $s$ de ce terme est
+divisible par l'un des $s_i$.
+\end{prop}
+\begin{proof}
+En développant l'écriture $g_1 s_1 + \cdots + g_r s_r$, puisque la
+somme comporte le terme $c s$, au moins un des facteurs comporte un
+terme dont le monôme est $s$, ce qui montre bien que $s$ est divisible
+par un des $s_i$.
+\end{proof}
+
+\begin{cor}
+Si $s_1,\ldots,s_r$ sont des monômes de $k[t_1,\ldots,t_d]$, l'idéal
+qu'ils engendrent est exactement l'idéal des polynômes dont le monôme
+de chaque terme est divisible par un des $s_i$.
+\end{cor}
+\begin{proof}
+On vient de montrer que si $f$ est dans $(s_1,\ldots,s_r)$ alors le
+monôme de chaque terme de $f$ est divisible par un des $s_i$.
+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}
+
+On appelle \textbf{idéal monomial} un idéal de $k[t_1,\ldots,t_d]$ qui
+peut être engendré par des monômes : le corollaire ci-dessus montre
+que si $I$ est un idéal monomial, alors tout terme d'un élément de $I$
+est encore un élément de $I$.  Réciproquement, si $I$ est un idéal tel
+que tout terme d'un élément de $I$ soit un élément de $I$, alors $I$
+est monomial (en effet, on peut choisir un ensemble de générateurs
+de $I$, et les monômes des termes de ces générateurs donnent des
+éléments de $I$ qui engendrent les générateurs choisis, donc
+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 :
+\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}
+
+\begin{prop}
+Si $\preceq$ est un ordre admissible sur les monômes de
+$k[t_1,\ldots,t_d]$, alors
+\begin{itemize}
+\item si $s_1 | s_2$ alors $s_1 \preceq s_2$,
+\item $\preceq$ est un bon ordre (c'est-à-dire : tout ensemble non
+  vide de monômes a un plus petit élément pour $\preceq$, ou de façon
+  équivalente, il n'y a pas de suite infinie strictement décroissante
+  de monômes pour $\preceq$).
+\end{itemize}
+\end{prop}
+\begin{proof}
+Le premier point est évident : si $s_2 = s s_1$ alors $1 \preceq s$
+entraîne $s_1 \preceq s s_1 = s_2$.  Montrons le second : si $S$ est
+un ensemble de monômes, soit $I$ l'idéal qu'ils engendrent ; comme
+$k[t_1,\ldots,t_d]$ est noethérien, il existe un sous-ensemble fini
+$S_0 \subseteq S$ qui engendre le même idéal $I$.  Soit $s$ le plus
+petit élément de $S_0$ : on prétend que $s$ est aussi le plus petit
+élément de $S$.  En effet, si $s' \in S$ alors $s' \in I$ donc $s'$
+s'écrit comme combinaison d'éléments de $S_0$, mais alors
+d'après \ref{divisibilite-monomes}, $s'$ est simplement multiple d'un
+élément de $S_0$, et d'après le premier point, $s\preceq s'$, ce qui
+conclut.
+\end{proof}
+
+Lorsque $d=1$, le seul ordre admissible sur les monômes est évidemment
+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$.
+
+
+
+%
+\subsection{Bases de Gröbner}
+
+Si $I$ est un idéal de $k[t_1,\ldots,t_d]$ (et $\preceq$ un ordre
+admissible), on appelle $\init_{\preceq}(I)$ l'idéal engendré par les
+$\init_{\preceq}(f)$ pour tous les $f\in I$ (c'est donc un idéal
+monomial).  Attention ! il n'y a aucune raison que prendre les
+$\init_{\preceq}(f)$ pour $f$ parcourant des générateur de $I$ suffise
+à engendrer $\init_{\preceq}(I)$.
+
+\begin{defn}
+Si $I$ est un idéal de $k[t_1,\ldots,t_d]$ et $\preceq$ un ordre
+admissible sur les monômes de ce dernier, on appelle \textbf{base de
+  Gröbner} de $I$ un ensemble $f_1,\ldots,f_r$ d'éléments de $I$ tels
+que $\init_{\preceq}(f_1),\ldots,\init_{\preceq}(f_r)$
+engendrent $\init_{\preceq}(I)$.
+\end{defn}
 
-Bases de Gröbner.
+A priori, rien ne dit que $f_1,\ldots,f_r$ engendrent $I$.  C'est
+pourtant le cas :
+\begin{prop}
+Dans les conditions ci-dessus, on a $I = (f_1,\ldots,f_r)$.
+\end{prop}
+\begin{proof}
+On a $I \supseteq (f_1,\ldots,f_r)$ puisque les $f_i$ sont supposés
+dans $I$.  Supposons maintenant qu'il n'y ait pas égalité.  Soit $h
+\in I$ un polynôme avec le monôme dans $\init(h)$ le plus petit
+possible (pour $\preceq$) tel que $h \not\in (f_1,\ldots,f_r)$.
+Puisque $\init(h) \in \init(I)$, on peut écrire $\init(h) = g_1
+\init(f_1) + \cdots + g_r \init(f_r)$ par l'hypothèse faite sur
+les $f_i$ (pour certains $g_1,\ldots,g_r$).
+D'après \ref{divisibilite-monomes}, ceci montre que $\init(h) = c s
+\init(f_i)$ pour un certain monôme $s$ et $c$ une constante.  On a
+alors $s f_i \in I$, et $\init(c s f_i) = c s \init(f_i) = \init(h)$,
+donc $h - c s f_i$, qui appartient à $I$, a un terme initial de monôme
+strictement plus petit que $h$, donc par minimalité de ce dernier, $h
+- c s f_i \in (f_1,\ldots,f_r)$.  Mais alors $h \in (f_1,\ldots,f_r)$,
+une contradiction.
+\end{proof}
+
+
+
+%
+%
+%
+
+\section{TODO}
 
 Courbes et corps de dimension $1$.  But : arriver à Riemann-Roch.