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