Monomordnung

Eine Monomordnung oder Termordnung $\leq$ ist eine lineare Ordnung auf der Menge der Monome über einer endlichen Variablenmenge. Monomordnungen werden zur Definition der Division mit Rest von Polynomen in mehreren Variablen benötigt. Eine Gröbnerbasis bzgl. $\leq$ definiert den Rest dieser Division eindeutig.

Definition

Eine lineare Ordnung $\leq$ auf der Menge

$M:=\{x^{\alpha }=x_{1}^{\alpha _{1}}\cdots x_{n}^{\alpha _{n}}\mid \alpha =(\alpha _{1},\dotsc ,\alpha _{n})\in \mathbb {Z} _{\geq 0}^{n}\}$

der Monome in den Variablen $x_{1},\dots ,x_{n}$ heißt Monomordnung, falls gilt

(1) Für alle Monome $x^{\alpha },x^{\beta },x^{\gamma }\in M$ gilt

$x^{\alpha }\leq x^{\beta }\Rightarrow x^{\alpha +\gamma }\leq x^{\beta +\gamma }$

(2) Das Monom $1$ ist das kleinste Monom, also

$\forall x^{\alpha }\in M:1\leq x^{\alpha }$

Äquivalente Definitionen

Es sind auch andere äquivalente Definitionen üblich. So ist es etwa möglich die Bedingung (2) durch eine andere Bedingung auszutauschen. In der Literatur finden sich zum Beispiel:

(2') Die Ordnung $\leq$ ist eine Wohlordnung

oder auch äquivalenten dazu

(2*) Bezüglich der Ordnung $\leq$ gibt es keine unendlichen absteigenden Ketten $x^{\alpha _{1}}>x^{\alpha _{2}}>x^{\alpha _{3}}>\cdots$ von Monomen.

Die Eigenschaft (2*) ist Grundlage vieler Terminierungsbeweise für Algorithmen im Zusammenhang mit Gröbnerbasen.

Beispiele für Monomordnungen

Monome in einer Variablen

Falls wir nur eine Variable haben, also $n=1$ gilt, gibt es nur eine Monomordnung $\leq$. Aus der Definition einer Monomordnung folgt nämlich direkt, dass in diesem Fall $1=x^{0}\leq x^{1}\leq x^{2}\leq \dotsc$ sein muss.

(Rein) Lexikalische Ordnung

Bezüglich der lexikalischen oder lexikographischen Ordnung $\leq _{\mathrm {lex} }$ gilt $x^{\alpha }\leq _{\mathrm {lex} }x^{\beta }$ genau dann, wenn der am weitesten links stehende, von Null verschiedene Eintrag von $\alpha -\beta$ negativ ist. Das heißt, es kann rekursiv definiert werden

$x^{\alpha }\leq _{\mathrm {lex} }x^{\beta }\Leftrightarrow (\alpha _{1}<\beta _{1}){\mbox{ oder }}(\alpha _{1}=\beta _{1}{\mbox{ und }}x_{2}^{\alpha _{2}}\cdots x_{n}^{\alpha _{n}}\leq _{\mathrm {lex} }x_{2}^{\beta _{2}}\cdots x_{n}^{\beta _{n}}).$

Totalgradordnung

Die Totalgradordnung oder graduierte lexikalische Ordnung $\leq _{\mathrm {tdeg} }$ ist definiert durch

$x_{1}^{e_{1}}\cdots x_{n}^{e_{n}}\leq _{\mathrm {tdeg} }x_{1}^{f_{1}}\cdots x_{n}^{f_{n}}\Leftrightarrow \left(\sum _{i=1}^{n}e_{i}<\sum _{i=1}^{n}f_{i}\right){\mbox{ oder }}\left(\sum _{i=1}^{n}e_{i}=\sum _{i=1}^{n}f_{i}{\mbox{ und }}x_{1}^{e_{1}}\cdots x_{n}^{e_{n}}\leq _{\mathrm {lex} }x_{1}^{f_{1}}\cdots x_{n}^{f_{n}}\right)$

Grad-revers-lex-Ordnung (Degree reverse lexicographical order)

Hier gilt:

$x_{1}^{e_{1}}\cdots x_{n}^{e_{n}}\leq _{\mathrm {degrevlex} }x_{1}^{f_{1}}\cdots x_{n}^{f_{n}}\Leftrightarrow \left(\sum _{i=1}^{n}e_{i}<\sum _{i=1}^{n}f_{i}\right){\mbox{ oder }}\left(\sum _{i=1}^{n}e_{i}=\sum _{i=1}^{n}f_{i}{\mbox{ und }}f_{j}\leq e_{j}{\mbox{ für }}j=max\{i:e_{i}\neq f_{i}\}\right)$

Matrix-Ordnungen

Sei $A\in \mathbb {Z} ^{n\times n}$invertierbar mit der Eigenschaft, dass in jeder Spalte der erste von Null verschiedene Eintrag positiv ist. Dann gilt:

$x^{\alpha }\leq _{\mathrm {A} }x^{\beta }\Leftrightarrow (A\alpha \leq _{\mathrm {lex} }A\beta ).$

Insbesondere kann man jede beliebige Monomordnung als Matrixordnung in $\mathbb {R} ^{n\times n}$darstellen. So ergibt sich beispielsweise für die Totalordnung (graduiert lexikographische Ordnung) folgende Matrix: ${\begin{pmatrix}1&1&...&1&1\\1&0&...&0&0\\0&1&...&0&0\\...&...&...&...&...\\0&0&...&1&0\end{pmatrix}}$. Die Grad-revers-lex-Ordnung kann folgendermaßen in eine Matrix umgesetzt werden: ${\begin{pmatrix}1&1&...&1&1\\0&0&...&0&-1\\0&0&...&-1&0\\...&...&...&...&...\\0&-1&...&0&0\end{pmatrix}}$.

Blockordnungen oder Eliminationsordnungen

Jedes Monom $m$ über einer Variablenmenge $X\cup Y$ kann auf eindeutige Weise in ein Produkt $m_{x}m_{y}$ zerlegt werden, so dass in $m_{x}$ nur Variablen aus $X$ und in $m_{y}$ nur Variablen aus $Y$ vorkommen. Mit dieser Schreibweise wird für gegebene Monomordnungen $\leq _{x}$ und $\leq _{y}$ auf Monomen über den Variablen aus $X$ bzw. $Y$ die Blockordnung $\leq _{x>y}$ auf Monomen in $X\cup Y$ definiert als

$m\leq _{x>y}n{\mbox{ genau dann, wenn }}(m_{x}\leq _{x}n_{x}){\mbox{ oder }}(m_{x}=n_{x}{\mbox{ und }}m_{y}\leq _{y}n_{y})$

Begriffe im Zusammenhang mit Polynomen

Eine Monomordnung erlaubt es die Monome in einem Polynom anzuordnen. Für ein Polynom $f(x)=\sum _{\alpha }a_{\alpha }x^{\alpha }\in k[x]=k[x_{1},\dotsc ,x_{n}]$ kann dann zum Beispiel der Multigrad ${\mbox{multideg}}_{\leq }(f)$, der Leitkoeffizient ${\mbox{LC}}_{\leq }(f)$, das Leitmonom ${\mbox{LM}}_{\leq }(f)$ oder der Leitterm ${\mbox{LT}}_{\leq }(f)$ von $f$ bezüglich der Monomordnung $\leq$ definiert werden. Es gilt

${\mbox{multideg}}_{\leq }(f):=\max _{\alpha \in \mathbb {Z} _{\geq 0}^{n},a_{\alpha }\neq 0}\alpha ,\quad {\mbox{LC}}_{\leq }(f):=a_{{\mbox{multideg}}_{\leq }(f)},\quad {\mbox{LM}}_{\leq }(f):=x^{{\mbox{multideg}}_{\leq }(f)},\quad {\mbox{LT}}_{\leq }(f):={\mbox{LC}}_{\leq }(f){\mbox{LM}}_{\leq }(f)=a_{{\mbox{multideg}}_{\leq }(f)}x^{{\mbox{multideg}}_{\leq }(f)}.$

Für den Polynomring in einer Variablen ergeben sich daraus die üblichen Definitionen für den Grad des Polynoms, seinen Leitkoeffizienten und seinen Leitterm.

Literatur

• T. Becker, V. Weispfenning: Gröbner Bases, a computational approach to commutative algebra. Springer-Verlag, 1993, ISBN 3-540-97971-9.