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 \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 \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 $ \N^n$ such that $\alpha > \beta$ implies $ \gamma + \alpha > \gamma + \beta$ for all $\alpha , \beta, \gamma \in \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 $\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.

cmpMethod
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 Multivariate polynomial ring in 3 variables over QQ

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

Matrix Orderings

Given a matrix $M\in \text{Mat}(k\times n,\mathbb R)$ of rank $n$, with rows $m_1,\dots,m_k$, the matrix ordering defined by $M$ is obtained by setting

\[x^\alpha>_M x^\beta \Leftrightarrow \;\exists\; 1\leq i\leq k: m_1\alpha=m_1\beta,\ldots, m_{i-1}\alpha\ =m_{i-1}\beta,\ m_i\alpha>m_i\beta\]

(here, $\alpha$ and $\beta$ are regarded as column vectors).

Note

By a theorem of Robbiano, every monomial ordering arises as a matrix ordering as above with $M\in \text{GL}(n,\mathbb R)$.

Note

To create matrix orderings, OSCAR allows for matrices with integer coefficients as input matrices.

Note

For orderings such as lex and degrevlex which are predefined in OSCAR, using the predefined version is much faster than using a representation as a matrix ordering.

matrix_orderingMethod
matrix_ordering(R::MPolyRing, M::Union{Matrix{T}, MatElem{T}}; check::Bool = true) where T -> MonomialOrdering

Given an integer matrix M such that nvars(R) = ncols(M) = rank(M), return the matrix ordering on the set of variables of R which is defined by M.

matrix_ordering(V::AbstractVector{<:MPolyRingElem}, M::Union{Matrix{T}, MatElem{T}}; check::Bool = true) where T -> MonomialOrdering

Given a vector V of variables and an integer matrix M such that length(V) = ncols(M) = rank(M), return the matrix ordering on the set of monomials in the given variables which is defined by M.

Note

The matrix M need not be square.

Note

If check = false is supplied, the rank check is omitted, and the resulting ordering may only be partial.

Examples

julia> R, (w, x, y, z) = QQ["w", "x", "y", "z"];

julia> M =[1 1 1 1; 0 -1 -1 -1; 0 0 -1 -1; 0 0 0 -1]
4×4 Matrix{Int64}:
 1   1   1   1
 0  -1  -1  -1
 0   0  -1  -1
 0   0   0  -1

julia> o1 = matrix_ordering(R, M)
matrix_ordering([w, x, y, z], [1 1 1 1; 0 -1 -1 -1; 0 0 -1 -1; 0 0 0 -1])

julia> N =[1 1; 0 -1]
2×2 Matrix{Int64}:
 1   1
 0  -1

julia> o2 = matrix_ordering([w, x], N)
matrix_ordering([w, x], [1 1; 0 -1])

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

julia> o3 = matrix_ordering(gens(R)[3:4], N)
matrix_ordering([y, z], [1 1; 0 -1])

julia> o3 = matrix_ordering(gens(R)[3:4], N)
matrix_ordering([y, z], [1 1; 0 -1])

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

As already shown above, OSCAR provides functions to recover defining matrices from given monomial orderings:

matrixMethod
matrix(ord::MonomialOrdering)

Return a matrix defining ord as a matrix ordering.

Examples

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

julia> o1 = degrevlex(R)
degrevlex([x, y, z])

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

julia> o2 = degrevlex([x, y])
degrevlex([x, y])

julia> matrix(o2)
[ 1    1   0]
[ 0   -1   0]
[-1    0   0]
source
canonical_matrixMethod
canonical_matrix(ord::MonomialOrdering)

Return the canonical matrix defining ord as a matrix ordering.

Examples

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

julia> o1 = degrevlex(R)
degrevlex([x, y, z])

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

julia> o2 = degrevlex([x, y])
degrevlex([x, y])

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

Predefined Global Orderings

The Lexicographical Ordering

The lexicographical ordering lex is defined by setting

\[x^\alpha > x^\beta \; \Leftrightarrow \;\exists \; 1 \leq i \leq n: \alpha_1 = \beta_1, \dots, \alpha_{i-1} = \beta_{i-1}, \alpha_i > \beta_i.\]

lexMethod
lex(R::MPolyRing) -> MonomialOrdering

Return the lexicographical ordering on the set of monomials in the variables of R.

lex(V::AbstractVector{<:MPolyRingElem}) -> MonomialOrdering

Given a vector V of variables, return the lexicographical ordering on the set of monomials in these variables.

Examples

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 = lex(R)
lex([w, x, y, z])

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

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

julia> o3 = lex(gens(R)[3:4])
lex([y, z])
source

The Degree Lexicographical Ordering

The degree lexicographical ordering deglex is defined by setting $\;\deg(x^\alpha) = \alpha_1 + \cdots + \alpha_n\;$ and

\[x^\alpha > x^\beta \; \Leftrightarrow \; \deg(x^\alpha) > \deg(x^\beta) \;\text{ or }\; (\deg(x^\alpha) = \deg(x^\beta) \;\text{ and }\; \exists \; 1 \leq i \leq n: \alpha_1 = \beta_1, \dots, \alpha_{i-1} = \beta_{i-1}, \alpha_i > \beta_i).\]

deglexMethod
deglex(R::MPolyRing) -> MonomialOrdering

Return the degree lexicographical ordering on the set of monomials in the variables of R.

deglex(V::AbstractVector{<:MPolyRingElem}) -> MonomialOrdering

Given a vector V of variables, return the degree lexicographical ordering on the set of monomials in these variables.

Examples

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 = deglex(R)
deglex([w, x, y, z])

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

julia> o2 = deglex([w, x])
deglex([w, x])

julia> o3 = deglex(gens(R)[3:4])
deglex([y, z])
source

The Inverse Lexicographical Ordering

The inverse lexicographical ordering invlex is defined by setting

\[x^\alpha > x^\beta \; \Leftrightarrow \;\exists \; 1 \leq i \leq n: \alpha_n = \beta_n, \dots, \alpha_{i+1} = \beta_{i+1}, \alpha_i > \beta_i.\]

invlexMethod
invlex(R::MPolyRing) -> MonomialOrdering

Return the inverse lexicographical ordering on the set of monomials in the variables of R.

invlex(V::AbstractVector{<:MPolyRingElem}) -> MonomialOrdering

Given a vector V of variables, return the inverse lexicographical ordering on the set of monomials in these variables.

Examples

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 = invlex(R)
invlex([w, x, y, z])

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

julia> o2 = invlex([w, x])
invlex([w, x])

julia> o3 = invlex(gens(R)[3:4])
invlex([y, z])
source

The Degree Inverse Lexicographical Ordering

The degree inverse lexicographical ordering deginvlex is defined by setting

\[x^\alpha > x^\beta \; \Leftrightarrow \deg(x^\alpha) > \deg(x^\beta) \;\text{ or }\;(\deg(x^\alpha) = \deg(x^\beta) \;\text{ and }\; \;\exists \; 1 \leq i \leq n: \alpha_n = \beta_n, \dots, \alpha_{i+1} = \beta_{i+1}, \alpha_i > \beta_i).\]

deginvlexMethod
deginvlex(R::MPolyRing) -> MonomialOrdering

Return the degree inverse lexicographical ordering on the set of monomials in the variables of R.

deginvlex(V::AbstractVector{<:MPolyRingElem}) -> MonomialOrdering

Given a vector V of variables, return the degree inverse lexicographical ordering on the set of monomials in these variables.

Examples

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 = deginvlex(R)
deginvlex([w, x, y, z])

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

julia> o2 = deginvlex([w, x])
deginvlex([w, x])

julia> o3 = deginvlex(gens(R)[3:4])
deginvlex([y, z])
source

The Degree Reverse Lexicographical Ordering

The degree reverse lexicographical ordering degrevlex is defined by setting $\;\deg(x^\alpha) = \alpha_1 + \cdots + \alpha_n\;$ and

\[x^\alpha > x^\beta \; \Leftrightarrow \; \deg(x^\alpha) > \deg(x^\beta) \;\text{ or }\;(\deg(x^\alpha) = \deg(x^\beta) \;\text{ and }\; \exists \; 1 \leq i \leq n: \alpha_n = \beta_n, \dots, \alpha_{i+1} = \beta_{i+1}, \alpha_i < \beta_i).\]

degrevlexMethod
degrevlex(R::MPolyRing) -> MonomialOrdering

Return the degree reverse lexicographical ordering on the set of monomials in the variables of R.

degrevlex(V::AbstractVector{<:MPolyRingElem}) -> MonomialOrdering

Given a vector V of variables, return the degree reverse lexicographical ordering on the set of monomials in these variables

Examples

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(R)
degrevlex([w, x, y, z])

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

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

julia> o3 = degrevlex(gens(R)[3:4])
degrevlex([y, z])
source

Weighted Lexicographical Orderings

If W is a vector of positive integers $w_1, \dots, w_n$, the corresponding weighted lexicographical ordering wdeglex(W) is defined by setting $\;\text{wdeg}(x^\alpha) = w_1\alpha_1 + \cdots + w_n\alpha_n\;$ and

\[x^\alpha > x^\beta \; \Leftrightarrow \; \text{wdeg}(x^\alpha) > \text{wdeg}(x^\beta) \;\text{ or }\;\\ (\text{wdeg}(x^\alpha) = \text{wdeg}(x^\beta) \;\text{ and }\; \exists \; 1 \leq i \leq n: \alpha_1 = \beta_1, \dots, \alpha_{i-1} = \beta_{i-1}, \alpha_i > \beta_i).\]

wdeglexMethod
wdeglex(R::MPolyRing, W::Vector{Int}) -> MonomialOrdering

If W is a vector of positive integers, return the corresponding weighted lexicographical ordering on the set of monomials in the variables of R.

wdeglex(V::AbstractVector{<:MPolyRingElem}, W::Vector{Int}) -> MonomialOrdering

Given a vector V of variables and a vector W of positive integers, return the corresponding weighted lexicographical ordering on the set of monomials in the given variables.

Examples

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 = wdeglex(R, [1, 2, 3, 4])
wdeglex([w, x, y, z], [1, 2, 3, 4])

julia> canonical_matrix(o1)
[1    2    3    4]
[0   -2   -3   -4]
[0    0   -3   -4]
[0    0    0   -1]

julia> o2 = wdeglex([w, x], [1, 2])
wdeglex([w, x], [1, 2])

julia> o3 = wdeglex(gens(R)[3:4], [3, 4])
wdeglex([y, z], [3, 4])
source

Weighted Reverse Lexicographical Orderings

If W is a vector of positive integers $w_1, \dots, w_n$, the corresponding weighted reverse lexicographical ordering wdegrevlex is defined by setting $\;\text{wdeg}(x^\alpha) = w_1\alpha_1 + \cdots + w_n\alpha_n\;$ and

\[x^\alpha > x^\beta \; \Leftrightarrow \; \text{wdeg}(x^\alpha) > \text{wdeg}(x^\beta) \;\text{ or }\;\\ (\text{wdeg}(x^\alpha) = \text{wdeg}(x^\beta) \;\text{ and }\; \exists \; 1 \leq i \leq n: \alpha_n = \beta_n, \dots, \alpha_{i+1} = \beta_{i+1}, \alpha_i < \beta_i).\]

wdegrevlexMethod
wdegrevlex(R::MPolyRing, W::Vector{Int}) -> MonomialOrdering

If W is a vector of positive integers, return the corresponding weighted reverse lexicographical ordering on the set of monomials in the variables of R.

wdegrevlex(V::AbstractVector{<:MPolyRingElem}, W::Vector{Int}) -> MonomialOrdering

Given a vector V of variables and a vector W of positive integers, return the corresponding weighted reverse lexicographical ordering on the set of monomials in the given variables.

Examples

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 = wdegrevlex(R, [1, 2, 3, 4])
wdegrevlex([w, x, y, z], [1, 2, 3, 4])

julia> canonical_matrix(o1)
[1    2    3    4]
[0    0    0   -1]
[0    0   -1    0]
[0   -1    0    0]

julia> o2 = wdegrevlex([w, x], [1, 2])
wdegrevlex([w, x], [1, 2])

julia> o3 = wdegrevlex(gens(R)[3:4], [3, 4])
wdegrevlex([y, z], [3, 4])
source

Predefined Local Orderings

The Negative Lexicographical Ordering

The negative lexicographical ordering neglex is defined by setting

\[x^\alpha > x^\beta \; \Leftrightarrow \;\exists \; 1 \leq i \leq n: \alpha_1 = \beta_1, \dots, \alpha_{i-1} = \beta_{i-1}, \alpha_i < \beta_i.\]

neglexMethod
neglex(R::MPolyRing) -> MonomialOrdering

Return the negative lexicographical ordering on the set of monomials in the variables of R.

neglex(V::AbstractVector{<:MPolyRingElem}) -> MonomialOrdering

Given a vector V of variables, return the negative lexicographical ordering on the set of monomials in these variables.

Examples

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 = neglex(R)
neglex([w, x, y, z])

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

julia> o2 = neglex([w, x])
neglex([w, x])

julia> o3 = neglex(gens(R)[3:4])
neglex([y, z])
source

The Negative Degree Lexicographical Ordering

The negative degree lexicographical ordering negdeglex is defined by setting $\;\deg(x^\alpha) = \alpha_1 + \cdots + \alpha_n\;$ and

\[x^\alpha > x^\beta \; \Leftrightarrow \; \deg(x^\alpha) < \deg(x^\beta) \;\text{ or }\; (\deg(x^\alpha) = \deg(x^\beta) \;\text{ and }\; \exists \; 1 \leq i \leq n: \alpha_1 = \beta_1, \dots, \alpha_{i-1} = \beta_{i-1}, \alpha_i > \beta_i).\]

negdeglexMethod
negdeglex(R::MPolyRing) -> MonomialOrdering

Return the negative degree lexicographical ordering on the set of monomials in the variables of R.

negdeglex(V::AbstractVector{<:MPolyRingElem}) -> MonomialOrdering

Given a vector V of variables, return the negative degree lexicographical ordering on the set of monomials in these variables.

Examples

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 = negdeglex(R)
negdeglex([w, x, y, z])

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

julia> o2 = negdeglex([w, x])
negdeglex([w, x])

julia> o3 = negdeglex(gens(R)[3:4])
negdeglex([y, z])
source

The Negative Inverse Lexicographical Ordering

The negative inverse lexicographical ordering neginvlex is defined by setting

\[x^\alpha > x^\beta \; \Leftrightarrow \;\exists \; 1 \leq i \leq n: \alpha_n = \beta_n, \dots, \alpha_{i+1} = \beta_{i+1}, \alpha_i < \beta_i.\]

neginvlexMethod
neginvlex(R::MPolyRing) -> MonomialOrdering

Return the negative inverse lexicographical ordering on the set of monomials in the variables of R.

neginvlex(V::AbstractVector{<:MPolyRingElem}) -> MonomialOrdering

Given a vector V of variables, return the negative inverse lexicographical ordering on the set of monomials in these variables.

Examples

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 = neginvlex(R)
neginvlex([w, x, y, z])

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

julia> o2 = neginvlex([w, x])
neginvlex([w, x])

julia> o3 = neginvlex(gens(R)[3:4])
neginvlex([y, z])
source

The Negative Degree Reverse Lexicographical Ordering

The negative degree reverse lexicographical ordering negdegrevlex is defined by setting $\;\deg(x^\alpha) = \alpha_1 + \cdots + \alpha_n\;$ and

\[x^\alpha > x^\beta \; \Leftrightarrow \; \deg(x^\alpha) < \deg(x^\beta) \;\text{ or }\;(\deg(x^\alpha) = \deg(x^\beta) \;\text{ and }\; \exists \; 1 \leq i \leq n: \alpha_n = \beta_n, \dots, \alpha_{i+1} = \beta_{i+1}, \alpha_i < \beta_i).\]

negdegrevlexMethod
negdegrevlex(R::MPolyRing) -> MonomialOrdering

Return the negative degree reverse lexicographical ordering on the set of monomials in the variables of R.

negdegrevlex(V::AbstractVector{<:MPolyRingElem}) -> MonomialOrdering

Given a vector V of variables, return the negative degree reverse lexicographical ordering on the set of monomials in these variables.

Examples

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 = negdegrevlex(R)
negdegrevlex([w, x, y, z])

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

julia> o2 = negdegrevlex([w, x])
negdegrevlex([w, x])

julia> o3 = negdegrevlex(gens(R)[3:4])
negdegrevlex([y, z])
source

Negative Weighted Lexicographical Orderings

If W is a vector of positive integers $w_1, \dots, w_n$, the corresponding negative weighted lexicographical ordering negwdeglex(W) is defined by setting $\;\text{wdeg}(x^\alpha) = w_1\alpha_1 + \cdots + w_n\alpha_n\;$ and

\[x^\alpha > x^\beta \; \Leftrightarrow \; \text{wdeg}(x^\alpha) < \text{wdeg}(x^\beta) \;\text{ or }\;\\ (\text{wdeg}(x^\alpha) = \text{wdeg}(x^\beta) \;\text{ and }\; \exists \; 1 \leq i \leq n: \alpha_1 = \beta_1, \dots, \alpha_{i-1} = \beta_{i-1}, \alpha_i > \beta_i).\]

negwdeglexMethod
negwdeglex(R::MPolyRing, W::Vector{Int}) -> MonomialOrdering

If W is a vector of positive integers, return the corresponding negative weighted lexicographical ordering on the set of monomials in the variables of R.

negwdeglex(V::AbstractVector{<:MPolyRingElem}, W::Vector{Int}) -> MonomialOrdering

Given a vector V of variables and a vector W of positive integers, return the corresponding negative weighted lexicographical ordering on the set of monomials in the given variables.

Examples

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 = negwdeglex(R, [1, 2, 3, 4])
negwdeglex([w, x, y, z], [1, 2, 3, 4])

julia> canonical_matrix(o1)
[-1   -2   -3   -4]
[ 0   -2   -3   -4]
[ 0    0   -3   -4]
[ 0    0    0   -1]

julia> o2 = negwdeglex([w, x], [1, 2])
negwdeglex([w, x], [1, 2])

julia> o3 = negwdeglex(gens(R)[3:4], [3, 4])
negwdeglex([y, z], [3, 4])
source

Negative Weighted Reverse Lexicographical Orderings

If W is a vector of positive integers $w_1, \dots, w_n$, the corresponding negative weighted reverse lexicographical ordering negwdegrevlex(W) is defined by setting $\;\text{wdeg}(x^\alpha) = w_1\alpha_1 + \cdots + w_n\alpha_n\;$ and

\[x^\alpha > x^\beta \; \Leftrightarrow \; \text{wdeg}(x^\alpha) < \text{wdeg}(x^\beta) \;\text{ or }\;\\ (\text{wdeg}(x^\alpha) = \text{wdeg}(x^\beta) \;\text{ and }\; \exists \; 1 \leq i \leq n: \alpha_n = \beta_n, \dots, \alpha_{i+1} = \beta_{i+1}, \alpha_i < \beta_i).\]

negwdegrevlexMethod
negwdegrevlex(R::MPolyRing, W::Vector{Int}) -> MonomialOrdering

If W is a vector of positive integers, return the corresponding negative weighted reverse lexicographical ordering on the set of monomials in the variables of R.

negwdegrevlex(V::AbstractVector{<:MPolyRingElem}, W::Vector{Int}) -> MonomialOrdering

Given a vector V of variables and a vector W of positive integers, return the corresponding negative weighted reverse lexicographical ordering on the set of monomials in the given variables.

Examples

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 = negwdegrevlex(R, [1, 2, 3, 4])
negwdegrevlex([w, x, y, z], [1, 2, 3, 4])

julia> canonical_matrix(o1)
[-1   -2   -3   -4]
[ 0    0    0   -1]
[ 0    0   -1    0]
[ 0   -1    0    0]

julia> o2 = negwdegrevlex([w, x], [1, 2])
negwdegrevlex([w, x], [1, 2])

julia> o3 = negwdegrevlex(gens(R)[3:4], [3, 4])
negwdegrevlex([y, z], [3, 4])
source

Weight Orderings

If $W$ is a vector of integers $w_1, \dots, w_n$, and $>$ is a monomial ordering on $\text{Mon}_n(x)$, then the corresponding weight ordering is defined by setting $\;\text{wdeg}(x^\alpha) = w_1\alpha_1 + \cdots + w_n\alpha_n\;$ and

\[x^\alpha >_{W} x^\beta \; \Leftrightarrow \; \text{wdeg}(x^\alpha) > \text{wdeg}(x^\beta) \;\text{ or }\; (\text{wdeg}(x^\alpha) = \text{wdeg}(x^\beta) \;\text{ and }\; x^\alpha > x^\beta).\]

weight_orderingMethod
weight_ordering(W::Vector{Int}, ord::MonomialOrdering) -> MonomialOrdering

Given an integer vector W and a monomial ordering ord on a set of monomials in length(W) variables, return the monomial ordering ord_W on this set of monomials which is obtained by first comparing the W-weighted degrees and then using ord in the case of a tie.

Note

The ordering ord_W is

  • global if all entries of W are positive, or if they are all non-negative and ord is global,
  • an elimination ordering for the set of variables which correspond to positive entries of W.

Examples

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

julia> W = [1, 0, -1];

julia> o = lex(R)
lex([x, y, z])

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

julia> oW = weight_ordering(W, o)
matrix_ordering([x, y, z], [1 0 -1])*lex([x, y, z])

julia> matrix(oW)
[1   0   -1]
[1   0    0]
[0   1    0]
[0   0    1]

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

julia> o2 = weight_ordering([1, -1], lex([x, z]))
matrix_ordering([x, z], [1 -1])*lex([x, z])

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

Block Orderings

The concept of block orderings (product orderings) allows one to construct new monomial orderings from already given ones: If $>_1$ and $>_2$ are monomial orderings on $\text{Mon}_s(x_1, \ldots, x_s)$ and $\text{Mon}_{n-s}(x_{s+1}, \ldots, x_n)$, respectively, then the block ordering $> \; = \; (>_1, >_2)$ on $\text{Mon}_n(x)=\text{Mon}_n(x_1, \ldots, x_n)$ is defined by setting

\[x^\alpha>x^\beta \;\Leftrightarrow\; x_1^{\alpha_1}\cdots x_s^{\alpha_s} >_1 x_1^{\beta_1}\cdots x_s^{\beta_s} \;\text{ or }\; \bigl(x_1^{\alpha_1}\cdots x_s^{\alpha_s} = x_1^{\beta_1}\cdots x_s^{\beta_s} \text{ and } x_{s+1}^{\alpha_{s+1}}\cdots x_n^{\alpha_n} >_2 x_{s+1}^{\beta_{s+1}}\cdots x_n^{\beta_n}\bigr).\]

Note

The ordering $(>_1, >_2)$

  • is global (local) iff both $>_1$ and $>_2$ are global (local). Mixed orderings arise by choosing one of $>_1$ and $>_2$ global and the other one local,
  • is an elimination ordering for the first block of variables iff $>_1$ is global.
Note
  • The definition of a block ordering above subdivides $x$ into a block of initial variables and its complementary block of variables. Block orderings for a subdivision of $x$ into any block of variables and its complementary block are defined similarly and have similar properties.
  • Inductively, one obtains block orderings composed of more than two individual orderings.

In OSCAR, block orderings are obtained by the concatenation of individual orderings using the * operator.

Examples
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> o = degrevlex([w, x])*degrevlex([y, z])
degrevlex([w, x])*degrevlex([y, z])

Elimination Orderings

Let $C[x]=C[x_1, \ldots, x_n]$ be a multivariate polynomial ring with coefficient ring $C$. Fix a subset $\sigma\subset \{1,\dots, n\}$ and write $x_\sigma$ for the set of variables $x_i$ with $i\in\sigma$. An elimination ordering for $x\smallsetminus x_\sigma$ is a monomial ordering $>$ on $\text{Mon}_n(x)$ which satisfies the following property: If $a$ is a monomial involving one of the variables in $x\smallsetminus x_\sigma$ , and $b$ is a monomial depending only on the variables in $x_\sigma$, then $a > b.$ Computing a Gröbner basis of $I$ with respect to such an ordering provides one way of finding the intersection $I\cap C[x_\sigma]$, that is, of eliminating the variables in $x\smallsetminus x_\sigma$ from $I$: The Gröbner basis elements which only depend on the variables in $x_\sigma$ form a Gröbner basis for $I\cap C[x_\sigma]$ with respect to the restriction of $>$ to the set of monomials in $I\cap C[x_\sigma]$.

Note

The lexicographical ordering is an elimination ordering for each initial set of variables $x_1, \dots, x_k$. If only a fixed subset of variables is considered, suitable weight or block orderings as discussed above are more effective. The documentation of the is_elimination_ordering function below offers examples and non-examples.

Tests on Monomial Orderings

is_elimination_orderingMethod
is_elimination_ordering(ord::MonomialOrdering, V::Vector{<:MPolyRingElem})

Given a vector V of polynomials which are variables, return true if ord is an elimination ordering for the variables in V. Return false, otherwise.

is_elimination_ordering(ord::MonomialOrdering, V:Vector{Int})

Given a vector V of indices which specify variables, return true if ord is an elimination ordering for the specified variables. Return false, otherwise.

Examples

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

julia> o1 = lex(R)
lex([w, x, y, z])

julia> is_elimination_ordering(o1, [w, x])
true

julia> o2 = weight_ordering([1, 1, 0, 0], degrevlex(R))
matrix_ordering([w, x, y, z], [1 1 0 0])*degrevlex([w, x, y, z])

julia> is_elimination_ordering(o2, [w, x])
true

julia> o3 = weight_ordering([1, -1, 0, 0], degrevlex(R))
matrix_ordering([w, x, y, z], [1 -1 0 0])*degrevlex([w, x, y, z])

julia> is_elimination_ordering(o3, [w, x])
false

julia> o4 = degrevlex([w, x])*degrevlex([y, z])
degrevlex([w, x])*degrevlex([y, z])

julia> is_elimination_ordering(o4, [w, x])
true

julia> o5 = degrevlex([w, x])*negdegrevlex([y, z])
degrevlex([w, x])*negdegrevlex([y, z])

julia> is_elimination_ordering(o5, [w, x])
true

julia> o6 = negdegrevlex([w, x])*negdegrevlex([y, z])
negdegrevlex([w, x])*negdegrevlex([y, z])

julia> is_elimination_ordering(o6, [w, x])
false
source
is_globalMethod
is_global(ord::MonomialOrdering)

Return true if ord is global, false otherwise.

Examples

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

julia> o = matrix_ordering(R, [1 1; 0 -1])
matrix_ordering([x, y], [1 1; 0 -1])

julia> is_global(o)
true
source
is_localMethod
is_local(ord::MonomialOrdering)

Return true if ord is local, false otherwise.

Examples

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

julia> o = matrix_ordering(R, [-1 -1; 0 -1])
matrix_ordering([x, y], [-1 -1; 0 -1])

julia> is_local(o)
true
source
is_mixedMethod
is_mixed(ord::MonomialOrdering)

Return true if ord is mixed, false otherwise.

Examples

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

julia> o = matrix_ordering(R, [1 -1; 0 -1])
matrix_ordering([x, y], [1 -1; 0 -1])

julia> is_mixed(o)
true
source

Transferring an ordering from another ring

induceMethod
induce(vars::AbstractVector{<:MPolyRingElem}, ord::ModuleOrdering)

Return the monomial ordering on the variables vars induced by transferring the ordering ord.

Examples

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

julia> S, (a, b, c) = polynomial_ring(GF(5), ["a", "b", "c"]);

julia> ord = degrevlex([x, y])*neglex([z]);

julia> induce([a, b, c], ord)
degrevlex([a, b])*neglex([c])
source

Module Orderings

Let $R = C[x]=C[x_1, \ldots, x_n]$ be a multivariate polynomial ring with coefficient ring $C$. Referring to the section on free modules for details, we recall that by a free $R$-module we mean a free module of type $R^p$ , where we think of $R^p$ as a free module with a given basis, namely the basis of standard unit vectors. In what follows, $F$ will denote such free $R$-module, and $\{e_1 ,\dots , e_p\}$ will denote the given basis.

A monomial in $F$, involving the basis element $e_i$, is a monomial in $R$ times $e_i$. A term in $F$ is a monomial in $F$ multiplied by a coefficient $c\in C$. Every nonzero element $f\in F$ can be uniquely expressed as the sum of finitely many nonzero terms involving distinct monomials. These terms (monomials) are called the terms (monomials} of $f$.

A monomial ordering on $F$ is a total ordering $>$ on the set of monomials in $F$ such that if $x^\alpha e_i$ and $x^\beta e_j$ are monomials in $F$, and $x^\gamma$ is a monomial in $R$, then

\[x^\alpha e_i > x^\beta e_j \Longrightarrow x^\gamma x^\alpha e_i > x^\gamma x^\beta e_j.\]

In OSCAR, we require in addition that

\[x^\alpha e_i > x^\beta e_i \;\text{ iff }\; x^\alpha e_j > x^\beta e_j \;\text{ for all }\; i,j.\]

Then $>$ induces a unique monomial ordering on $R$ in the obvious way, and we say that $>$ is global, local, or mixed if the induced ordering on $R$ is global, local, or mixed.

One way of getting a monomial ordering on $F$ is to pick a monomial ordering $>$ on $R$, and extend it to $F$. For instance, setting

\[x^\alpha e_i > x^\beta e_j \iff x^\alpha > x^\beta \;\text{ or }\; (x^\alpha = x^\beta \;\text{ and }\; i > j)\]

gives priority to the monomials in $R$, whereas the ordering defined below gives priority to the components of $F$:

\[x^\alpha e_i > x^\beta e_j \iff i > j \;\text{ or }\; (i = j\;\text{ and } x^\alpha > x^\beta).\]

Alternatively, we may wish to use $i < j$ instead of $i > j$ in this definition.

In other words, these orderings are obtained by concatenating a monomial ordering on the monomials of $R$ with a way of ordering the basis vectors of $F$ or vice versa. In OSCAR, we refer to the $i < j$ ordering on the basis vectors as lex, and to the $i > j$ ordering as invlex. And, we use the * operator for concatenation.

Examples
julia> R, (w, x, y, z) = polynomial_ring(QQ, ["w", "x", "y", "z"]);

julia> F = free_module(R, 3)
Free module of rank 3 over Multivariate polynomial ring in 4 variables over QQ

julia> o1 = degrevlex(R)*invlex(gens(F))
degrevlex([w, x, y, z])*invlex([gen(1), gen(2), gen(3)])

julia> o2 = invlex(gens(F))*degrevlex(R)
invlex([gen(1), gen(2), gen(3)])*degrevlex([w, x, y, z])

The induced ordering on the given polynomial ring is recovered as follows:

induced_ring_orderingMethod
induced_ring_ordering(ord::ModuleOrdering)

Return the ring ordering induced by ord.

Examples

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

julia> F = free_module(R, 3)
Free module of rank 3 over Multivariate polynomial ring in 4 variables over QQ

julia> o = invlex(gens(F))*degrevlex(R)
invlex([gen(1), gen(2), gen(3)])*degrevlex([w, x, y, z])

julia> induced_ring_ordering(o)
degrevlex([w, x, y, z])
source

The comparison function cmp as well as the tests is_global, is_local, and is_mixed are also available for module orderings.