Monomordnung

Eine Monomordnung oder Termordnung $\le$ 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. $\le$ definiert den Rest dieser Division eindeutig.

Definition

Eine lineare Ordnung $\le$ auf der Menge

$M:=\{x^{\alpha }=x_1^{{\alpha }_1}\cdots x_n^{{\alpha }_n}\mid \alpha =({\alpha }_1,\dots ,{\alpha }_n)\in {\mathbb{Z}}_{\ge 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 }\le x^{\beta }\Rightarrow x^{\alpha +\gamma }\le x^{\beta +\gamma }$

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

$\mathrm{\forall }{x}^{\alpha }\in M:1\le 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 $\le$ ist eine Wohlordnung

oder auch äquivalenten dazu

(2*) Bezüglich der Ordnung $\le$ 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 $\le$. Aus der Definition einer Monomordnung folgt nämlich direkt, dass in diesem Fall $1=x^0\le x^1\le x^2\le \dots$ sein muss.

(Rein) Lexikalische Ordnung

Bezüglich der lexikalischen oder lexikographischen Ordnung ${\le }_{\mathrm{l}\mathrm{e}\mathrm{x}}$ gilt $x^{\alpha }{\le }_{\mathrm{l}\mathrm{e}\mathrm{x}}{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 }{\le }_{\mathrm{l}\mathrm{e}\mathrm{x}}{x}^{\beta }\iff ({\alpha }_1<{\beta }_1)\text{ oder }({\alpha }_1={\beta }_1\text{ und }{x}_2^{{\alpha }_2}\cdots x_n^{{\alpha }_n}{\le }_{\mathrm{l}\mathrm{e}\mathrm{x}}{x}_2^{{\beta }_2}\cdots x_n^{{\beta }_n}).$

Totalgradordnung

Die Totalgradordnung oder graduierte lexikalische Ordnung ${\le }_{\mathrm{t}\mathrm{d}\mathrm{e}\mathrm{g}}$ ist definiert durch

$x_1^{e_1}\cdots x_n^{e_n}{\le }_{\mathrm{t}\mathrm{d}\mathrm{e}\mathrm{g}}{x}_1^{f_1}\cdots x_n^{f_n}\iff (\sum _{i=1}^n{e}_i<\sum _{i=1}^n{f}_i)\text{ oder }(\sum _{i=1}^n{e}_i=\sum _{i=1}^n{f}_i\text{ und }{x}_1^{e_1}\cdots x_n^{e_n}{\le }_{\mathrm{l}\mathrm{e}\mathrm{x}}{x}_1^{f_1}\cdots x_n^{f_n})$

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

Hier gilt:

$x_1^{e_1}\cdots x_n^{e_n}{\le }_{\mathrm{d}\mathrm{e}\mathrm{g}\mathrm{r}\mathrm{e}\mathrm{v}\mathrm{l}\mathrm{e}\mathrm{x}}{x}_1^{f_1}\cdots x_n^{f_n}\iff (\sum _{i=1}^n{e}_i<\sum _{i=1}^n{f}_i)\text{ oder }(\sum _{i=1}^n{e}_i=\sum _{i=1}^n{f}_i\text{ und }{f}_j\le e_j\text{ für }j=max\{i:e_i\ne f_i\})$

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 }{\le }_{\mathrm{A}}{x}^{\beta }\iff (A\alpha {\le }_{\mathrm{l}\mathrm{e}\mathrm{x}}A\beta ).$

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

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 ${\le }_x$ und ${\le }_y$ auf Monomen über den Variablen aus $X$ bzw. $Y$ die Blockordnung ${\le }_{x>y}$ auf Monomen in $X\cup Y$ definiert als

$m{\le }_{x>y}n\text{ genau dann, wenn }(m_x{\le }_x{n}_x)\text{ oder }(m_x=n_x\text{ und }{m}_y{\le }_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,\dots ,x_n]$ kann dann zum Beispiel der Multigrad ${\text{multideg}}_{\le }(f)$, der Leitkoeffizient ${\text{LC}}_{\le }(f)$, das Leitmonom ${\text{LM}}_{\le }(f)$ oder der Leitterm ${\text{LT}}_{\le }(f)$ von $f$ bezüglich der Monomordnung $\le$ definiert werden. Es gilt

${\text{multideg}}_{\le }(f):=\underset{\alpha \in {\mathbb{Z}}_{\ge 0}^n,a_{\alpha }\ne 0}{\max }\alpha ,{\text{LC}}_{\le }(f):=a_{{\text{multideg}}_{\le }(f)},{\text{LM}}_{\le }(f):=x^{{\text{multideg}}_{\le }(f)},{\text{LT}}_{\le }(f):={\text{LC}}_{\le }(f){\text{LM}}_{\le }(f)=a_{{\text{multideg}}_{\le }(f)}{x}^{{\text{multideg}}_{\le }(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.
• Vorlage:Literatur