Monomial Orderings

Given a coefficient ring $C$ as in the previous section, let $C[x]=C[x_1, \ldots, x_n]$ be the polynomial ring over $C$ in the set of variables $x=\{x_1, \ldots, x_n\}$. Monomials in $x=\{x_1, \ldots, x_n\}$ are written using multi–indices: If $\alpha=(\alpha_1, \ldots, \alpha_n)\in \mathbb{N}^n$, set $x^\alpha=x_1^{\alpha_1}\cdots x_n^{\alpha_n}$ and

\[\text{Mon}_n(x) := \text{Mon}(x_1, \ldots, x_n) := \{x^\alpha \mid \alpha \in \mathbb{N}^n\}.\]

A monomial ordering on $\text{Mon}_n(x)$ is a total ordering $>$ on $\text{Mon}_n(x)$ such that

\[x^\alpha > x^\beta \Longrightarrow x^\gamma x^\alpha > x^\gamma x^\beta, \; \text{ for all }\; \alpha, \beta, \gamma \in \mathbb N^n.\]

A monomial ordering $>$ on $\text{Mon}_n(x)$ is called

global if $x^\alpha > 1$ for all $\alpha \not = (0, \dots, 0)$,
local if $x^\alpha < 1$ for all $\alpha \not = (0, \dots, 0)$, and
mixed if it is neither global nor local.

Note

A monomial ordering on $\text{Mon}_n(x)$ is global iff it is a well-ordering.
To give a monomial ordering on $\text{Mon}_n(x)$ means to give a total ordering $>$ on $ \mathbb{N}^n$ such that $\alpha > \beta$ implies $ \gamma + \alpha > \gamma + \beta$ for all $\alpha , \beta, \gamma \in \mathbb{N}^n.$ Rather than speaking of a monomial ordering on $\text{Mon}_n(x)$, we may, thus, also speak of a (global, local, mixed) monomial ordering on $\mathbb{N}^n$.

Note

By a result of Robbiano, every monomial ordering can be realized as a matrix ordering.

Note

The lexicograpical monomial ordering specifies the default way of storing and displaying multivariate polynomials in OSCAR (terms are sorted in descending order). The other orderings which can be attached to a multivariate polynomial ring are the degree lexicographical ordering and the degree reverse lexicographical ordering. Independently of the attached orderings, Gröbner bases can be computed with respect to any monomial ordering. See the section on Gröbner bases.

In this section, we show how to create monomial orderings in OSCAR.

Note

For the convenient construction of block orderings on the set of monomials in the variables of a given multivariate polynomial ring, we allow to construct orderings on the monomials in blocks of variables, viewing these orderings as partial orderings on the monomials in all variables.

Here are some illustrating examples:

Examples

julia> S, (w, x) = polynomial_ring(QQ, [:w, :x])
(Multivariate polynomial ring in 2 variables over QQ, QQMPolyRingElem[w, x])

julia> o = lex([w, x])
lex([w, x])

julia> canonical_matrix(o)
[1   0]
[0   1]

julia> R, (w, x, y, z) = polynomial_ring(QQ, [:w, :x, :y, :z])
(Multivariate polynomial ring in 4 variables over QQ, QQMPolyRingElem[w, x, y, z])

julia> o1 = degrevlex([w, x])
degrevlex([w, x])

julia> is_global(o1)
true

julia> canonical_matrix(o1)
[1    1   0   0]
[0   -1   0   0]

julia> o2 = neglex([y, z])
neglex([y, z])

julia> is_local(o2)
true

julia> canonical_matrix(o2)
[0   0   -1    0]
[0   0    0   -1]

julia> o3 = o1*o2
degrevlex([w, x])*neglex([y, z])

julia> canonical_matrix(o3)
[1    1    0    0]
[0   -1    0    0]
[0    0   -1    0]
[0    0    0   -1]

julia> is_mixed(o3)
true

Monomial Comparisons

The cmp function should be used for comparing two monomials with regard to a monomial ordering.

cmp — Method

cmp(ord::MonomialOrdering, a::MPolyRingElem, b::MPolyRingElem)

cmp(ord::ModuleOrdering, a::FreeModElem{T}, b::FreeModElem{T}) where T <: MPolyRingElem

Compare monomials a and b with regard to the ordering ord: Return -1 for a < b and 1 for a > b and 0 for a == b. An error is thrown if ord is a partial ordering that does not distinguish a from b.

Examples

julia> R, (x, y, z) = polynomial_ring(QQ, [:x, :y, :z]);

julia> cmp(lex([x,y]), x, one(R))
1

julia> try cmp(lex([x,y]), z, one(R)); catch e; e; end
ErrorException("z and 1 are incomparable with respect to lex([x, y])")

julia> cmp(lex([x,y,z]), z, one(R))
1

julia> F = free_module(R, 2)
Free module of rank 2 over R

julia> cmp(lex(R)*lex(F), F[1], F[2])
-1