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_1^{e_1}\cdots x_n^{e_n}: e_1,\ldots,e_n \geq 0\}$

der Monome in den Variablen $x_1,\dots,x_n$ heißt Monomordnung, falls gilt

1. Für alle Monome $r,m,n \in M$ gilt

$m \leq n \Rightarrow rm \leq rn$

2. Das Monom 1 ist das kleinste Monom:

$\forall m \in M: 1 \leq m$

Bedingung (2) ist, sofern (1) erfüllt ist, äquivalent dazu, dass $\leq$ eine Wohlordnung ist, es also keine unendlichen absteigenden Ketten

$m_1 > m_2 > m_3 > \cdots$

von Monomen gibt. Diese Eigenschaft ist Grundlage vieler Terminierungsbeweise für Algorithmen im Zusammenhang mit Gröbnerbasen. Falls (2) verletzt ist, etwa m < 1, dann erhalten wird durch wiederholte Anwendung von (1) die absteigende Kette

$1 > m > m^2 > m^3 > \cdots.$

Beispiele für Monomordnungen

(Rein) Lexikalische Ordnung

Die lexikalische oder lexikographische Ordnung $\leq_\mathrm{lex}$ ist definiert durch

$x_1^{e_1}\cdots x_n^{e_n} \leq_\mathrm{lex} x_1^{f_1}\cdots x_n^{f_n} \Leftrightarrow (e_1 < f_1)\mbox{ oder }(e_1 = f_1\mbox{ und } x_2^{e_2}\cdots x_n^{e_n} \leq_\mathrm{lex} x_2^{f_2}\cdots x_n^{f_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 e_i < \sum f_i\right)\mbox{ oder }\left(\sum e_i = \sum 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)$

Blockordnungen

Jedes Monom m über einer Variablenmenge $X \cup Y$ kann auf eindeutige Weise in ein Produkt m_xm_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)$

Literatur

• Becker T., Weispfenning V.: Gröbner Bases, Springer-Verlag 1993.