diff options
| -rw-r--r-- | notes-geoalg.tex | 164 |
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} + % |