Monom Order

A monomial order or term order is a linear order on the set of monomials over a finite set of variables. Monomial orders are needed to define the division with remainder of polynomials in several variables. A Gröbner base with respect to clearly defines the rest of this division. ${\displaystyle \leq }$ ${\displaystyle \leq }$

definition

A linear order on the set ${\displaystyle \leq }$

${\displaystyle 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}\}}$

the monomial in the variables is called the monomial order if it holds ${\displaystyle x_{1},\dots ,x_{n}}$

(1) The following applies to all monomials ${\displaystyle x^{\alpha },x^{\beta },x^{\gamma }\in M}$

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

(2) The monomial is the smallest monomial, so ${\displaystyle 1}$

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

Equivalent Definitions

Other equivalent definitions are also common. For example, it is possible to replace condition (2) with another condition. In the literature you can find for example:

(2 ') Order is well-ordered ${\displaystyle \leq }$

or equivalents to it

(2 *) Regarding order, there are no infinite descending chains of monomials. ${\displaystyle \leq }$ ${\displaystyle x^{\alpha _{1}}>x^{\alpha _{2}}>x^{\alpha _{3}}>\cdots }$

The property (2 *) is the basis of many termination proofs for algorithms in connection with Gröbner bases.

Examples of monomial orders

Monomials in one variable

If we only have one variable, so there is only one monomial order . From the definition of a monomial order it follows directly that it must be in this case . ${\displaystyle n=1}$ ${\displaystyle \leq }$ ${\displaystyle 1=x^{0}\leq x^{1}\leq x^{2}\leq \dotsc }$

(Pure) lexical order

With regard to the lexical or lexicographical order, the following applies if and only if the leftmost entry other than zero is negative. That is, it can be defined recursively ${\displaystyle \leq _{\mathrm {lex} }}$ ${\displaystyle x^{\alpha }\leq _{\mathrm {lex} }x^{\beta }}$ ${\displaystyle \alpha -\beta }$

${\displaystyle 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}}).}$

Total degree order

The total degree order or graduated lexical order is defined by ${\displaystyle \leq _{\mathrm {tdeg} }}$

${\displaystyle 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)}$

Degree reverse lexicographical order

The following applies here:

${\displaystyle 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 orders

Let be invertible with the property that the first non-zero entry in each column is positive. Then: ${\displaystyle A\in \mathbb {Z} ^{n\times n}}$

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

In particular, any monomial order can be represented as a matrix order in . This results, for example, the total order (graduated lexicographical order) following matrix: . The degree reverse-lex-order can be implemented as follows in a matrix: . ${\displaystyle \mathbb {R} ^{n\times n}}$ ${\displaystyle {\begin{pmatrix}1&1&...&1&1\\1&0&...&0&0\\0&1&...&0&0\\...&...&...&...&...\\0&0&...&1&0\end{pmatrix}}}$ ${\displaystyle {\begin{pmatrix}1&1&...&1&1\\0&0&...&0&-1\\0&0&...&-1&0\\...&...&...&...&...\\0&-1&...&0&0\end{pmatrix}}}$

Block orders

Each monomial over a set of variables can be uniquely decomposed into a product , so that only variables from and only variables from occur. With this notation, for given monomials and on monomials above the variables from or the block order on monomials in is defined as ${\displaystyle m}$ ${\displaystyle X\cup Y}$ ${\displaystyle m_{x}m_{y}}$ ${\displaystyle m_{x}}$ ${\displaystyle X}$ ${\displaystyle m_{y}}$ ${\displaystyle Y}$ ${\displaystyle \leq _{x}}$ ${\displaystyle \leq _{y}}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle \leq _{x>y}}$ ${\displaystyle X\cup Y}$

${\displaystyle 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})}$

Terms related to polynomials

A monomial order allows the monomials to be arranged in a polynomial. For a polynomial , for example , the multi-degree, the leading coefficient , the leading monomial or the leading term of can be defined with respect to the monomial order. It applies ${\displaystyle f(x)=\sum _{\alpha }a_{\alpha }x^{\alpha }\in k[x]=k[x_{1},\dotsc ,x_{n}]}$ ${\displaystyle {\mbox{multideg}}_{\leq }(f)}$ ${\displaystyle {\mbox{LC}}_{\leq }(f)}$ ${\displaystyle {\mbox{LM}}_{\leq }(f)}$ ${\displaystyle {\mbox{LT}}_{\leq }(f)}$ ${\displaystyle f}$ ${\displaystyle \leq }$

${\displaystyle {\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)}.}$

For the polynomial ring in one variable, the usual definitions for the degree of the polynomial, its leading coefficient and its leading term result.

literature

• T. Becker, V. Weispfenning: Gröbner Bases, a computational approach to commutative algebra. Springer-Verlag, 1993, ISBN 3-540-97971-9 .
• David A. Cox , John B. Little , Donal O'Shea : Ideals, Varieties, and Algorithms. An Introduction to Computational Algebraic Geometry and Commutative Algebra (=  Undergraduate Texts in Mathematics ). 3. Edition. Springer, New York 2007, ISBN 978-0-387-35650-1 , 2.2. Orders on the Monomials in . ${\displaystyle k[x_{1},\dotsc ,x_{n}]}$

Individual evidence

1. ↑ DA Cox, JB Little, D. O'Shea: Ideals, Varieties, and Algorithms. 2007, 2.2. Definition 1, Lemma 2.
2. ^ Winfried Bruns: Computer Algebra. (PDF) Retrieved July 31, 2019 . 
3. ↑ M. Roczen, H. Wolter, W. Pohl, D. Popescu, R. Laza: Lineare Algebra individually - Chapter 2: Algebraic equations. (PDF) Retrieved July 31, 2019 . 
4. ↑ DA Cox, JB Little, D. O'Shea: Ideals, Varieties, and Algorithms. 2007, 2.2. Definition 7.