summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2010-06-06 19:58:14 +0200
committerDavid A. Madore <david+git@madore.org>2010-06-06 19:58:14 +0200
commit7d579da960ef9838b322091db6e960b8a3f1d23b (patch)
tree547174d59d5be0846a070df62e7c486c2fd29617
parent851e4da99736ad859d95d7091f63a8dae5a430a6 (diff)
downloadmdi349-7d579da960ef9838b322091db6e960b8a3f1d23b.tar.gz
mdi349-7d579da960ef9838b322091db6e960b8a3f1d23b.tar.bz2
mdi349-7d579da960ef9838b322091db6e960b8a3f1d23b.zip
Important monomial orders (lex, glex and grevlex).
-rw-r--r--notes-geoalg.tex67
1 files changed, 67 insertions, 0 deletions
diff --git a/notes-geoalg.tex b/notes-geoalg.tex
index 94038c5..4115ab0 100644
--- a/notes-geoalg.tex
+++ b/notes-geoalg.tex
@@ -3388,6 +3388,73 @@ 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
+
+Exemples importants d'ordres admissibles sur les monômes : (on
+supposera toujours, quitte à renuméroter les variables, que $t_1
+\preceq t_2 \preceq \cdots \preceq t_d$) :
+
+* L'\textbf{ordre lexicographique (pur)} est défini par $t_1^{\ell_1}
+\cdots t_d^{\ell_d} \mathrel{\preceq_{\mathtt{lex}}} t_1^{\ell'_1}
+\cdots t_d^{\ell'_d}$ ssi $\ell_i < \ell'_i$ pour le \emph{plus
+ grand} $i$ tel que $\ell_i \neq \ell'_i$. Pour cet ordre on a donc
+$1 \preceq t_1 \preceq t_1^2 \preceq t_1^3 \preceq \cdots \preceq t_2
+\preceq t_1 t_2 \preceq t_1^2 t_2 \preceq \cdots \preceq t_2^2 \preceq
+t_1 t_2^2 \preceq \cdots \preceq t_2^3 \preceq \cdots \preceq t_3
+\preceq t_1 t_3 \preceq t_1^2 t_3 \preceq \cdots \preceq t_2 t_3
+\preceq t_1 t_2 t_3 \preceq \cdots \preceq t_3^2 \preceq \cdots
+\preceq t_4 \preceq \cdots$. (Attention, l'ordre donne le poids fort
+à l'exposant de la dernière variable, ce qui correspond à la
+convention faite $t_1 \preceq t_2 \preceq \cdots \preceq t_d$ ; plus
+généralement, tout ordre total sur l'ensemble des variables définit un
+unique ordre lexicographique pur associé.)
+
+\emph{Caractérisation :} Si $\init_{\mathtt{lex}}(f) \in
+k[t_1,\ldots,t_s]$ (pour un $s\leq d$) alors $f \in
+k[t_1,\ldots,t_s]$.
+
+* L'\textbf{ordre lexicographique par degré} ou \textbf{ordre
+ lexicographique gradué} est défini par $t_1^{\ell_1} \cdots
+t_d^{\ell_d} \mathrel{\preceq_{\mathtt{glex}}} t_1^{\ell'_1} \cdots
+t_d^{\ell'_d}$ ssi $\sum \ell_i < \sum \ell'_i$ ou $\sum \ell_i = \sum
+\ell'_i$ et $\ell_i < \ell'_i$ pour le \emph{plus grand} $i$ tel que
+$\ell_i \neq \ell'_i$. Autrement dit, les monômes sont classés par
+degré total en priorité puis, faute de cela, par l'ordre
+lexicographique pur défini ci-dessus. Pour cet ordre, on a donc $1
+\preceq t_1 \preceq t_2 \preceq t_3 \preceq t_4 \preceq \cdots \preceq
+t_1^2 \preceq t_1 t_2 \preceq t_2^2 \preceq t_1 t_3 \preceq t_2 t_3
+\preceq t_3^2 \preceq \cdots \preceq t_1^3 \preceq t_1^2 t_2 \preceq
+t_1 t_2^2 \preceq t_2^3 \preceq t_1^2 t_3 \preceq t_1 t_2 t_3 \preceq
+\cdots$. (Même remarque que ci-dessus : il y a un tel ordre pour
+chaque ordre total sur les variables.)
+
+\emph{Caractérisation :} L'ordre $\mathrel{\preceq_{\mathtt{glex}}}$
+raffine l'ordre partiel donné par le degré total ; et si $f$ homogène
+vérifie $\init_{\mathtt{glex}}(f) \in k[t_1,\ldots,t_s]$ (pour
+un $s\leq d$) alors $f \in k[t_1,\ldots,t_s]$.
+
+* L'\textbf{ordre lexicographique inversé par degré} (ou
+\textbf{...gradué}) est défini par $t_1^{\ell_1} \cdots t_d^{\ell_d}
+\mathrel{\preceq_{\mathtt{grevlex}}} t_1^{\ell'_1} \cdots
+t_d^{\ell'_d}$ ssi $\sum \ell_i < \sum \ell'_i$ ou $\sum \ell_i = \sum
+\ell'_i$ et $\ell_i > \ell'_i$ (attention au sens !) pour le
+\emph{plus petit} $i$ tel que $\ell_i \neq \ell'_i$. Pour cet ordre,
+on a donc $1 \preceq t_1 \preceq t_2 \preceq t_3 \preceq t_4 \preceq
+\cdots \preceq t_1^2 \preceq t_1 t_2 \preceq t_1 t_3 \preceq t_1 t_4
+\preceq \cdots \preceq t_2^2 \preceq t_2 t_3 \preceq \cdots \preceq
+t_3^2 \preceq \cdots \preceq t_1^3 \preceq t_1^2 t_2 \preceq t_1^2 t_3
+\preceq \cdots \preceq t_1 t_2^2 \preceq t_1 t_2 t_3 \preceq \cdots
+\preceq t_2^3 \preceq \cdots$. (Même remarque que ci-dessus : il y a
+un tel ordre pour chaque ordre total sur les variables. De plus,
+$\mathrel{\preceq_{\mathtt{grevlex}}}$ et
+$\mathrel{\preceq_{\mathtt{glex}}}$ coïncident lorsqu'il n'y a que
+deux variables, une fois fixé l'ordre entre celles-ci.)
+
+\emph{Caractérisation :} L'ordre
+$\mathrel{\preceq_{\mathtt{grevlex}}}$ raffine l'ordre partiel donné
+par le degré total ; et si $f$ homogène vérifie
+$\init_{\mathtt{grevlex}}(f) \in (t_1,\ldots,t_s)$ (pour un $s\leq d$)
+alors $f \in (t_1,\ldots,t_s)$.
%