28.5 Term Orderings

Module: sage.rings.polynomial.term_order

Term Orderings

Sage supports the following term orderings:

Lexicographic (lex)

$ x^a < x^b \Leftrightarrow \exists\; 0 \le i < n : a_0 = b_0, \ldots, a_{i-1} = b_{i-1}, a_i < b_i$

sage: P.<x,y,z> = PolynomialRing(QQ,3,order='lex')
sage: x > y
True
sage: x > y^2
True
sage: x > 1
True
sage: x^1*y^2 > y^3*z^4
True
sage: x^3*y^2*z^4 < x^3*y^2*z^1
False

This term ordering is called 'lp' in Singular.

Degree reverse lexicographic (degrevlex)

Let $ deg(x^a) = a_0 + \cdots + a_{n-1},$ then $ x^a < x^b \Leftrightarrow deg(x^a) < deg(x^b)$ or $ deg(x^a) = deg(x^b)$ and $ \exists\ 0 \le i < n: a_{n-1} = b_{n-1}, \ldots, a_{i+1} = b_{i+1}, a_i > b_i.$

sage: P.<x,y,z> = PolynomialRing(GF(127),3,order='degrevlex')
sage: x > y
True
sage: x > y^2*z
False
sage: x > 1
True
sage: x^1*y^5*z^2 > x^4*y^1*z^3
True
sage: x^2*y*z^2 > x*y^3*z
False

This term ordering is called 'dp' in Singular.

Degree lexicographic (deglex)

Let $ deg(x^a) = a_0 + \cdots + a_{n-1},$ then $ x^a < x^b \Leftrightarrow deg(x^a) < deg(x^b)$ or $ deg(x^a) = deg(x^b)$ and $ \exists\ 0 \le i < n:a_0 = b_0, \ldots, a_{i-1} = b_{i-1}, a_i < b_i.$

sage: P.<x,y,z> = PolynomialRing(GF(2^8,'a'),3,order='deglex')
sage: x > y
True
sage: x > y^2*z
False
sage: x > 1
True
sage: x^1*y^2*z^3 > x^3*y^2*z^0
True
sage: x^2*y*z^2 > x*y^3*z
True

This term order is called 'Dp' in Singular.

Inverse lexicographic (invlex)

$ x^a < x^b \Leftrightarrow \exists\; 0 \le i < n : a_{n-1} = b_{n-1}, \ldots, a_{i+1} = b_{i+1}, a_i < b_i.$

sage: P.<x,y,z> = PolynomialRing(GF(127),3,order='invlex')
sage: x > y
False
sage: y > x^2
True
sage: x > 1
True
sage: x*y > z
False

This term ordering only makes sense in a non-commutative setting because if P is the ring $ k[x_1, \dots, x_n]$ and term ordering 'invlex' then it is equivalent to the ring $ k[x_n, \dots, x_1]$ with term ordering 'lex'.

This ordering is called 'rp' in Singular.

Negative lexicographic (neglex)

$ x^a < x^b \Leftrightarrow \exists\; 0 \le i < n : a_0 = b_0, \ldots, a_{i-1} = b_{i-1}, a_i > b_i$

sage: P.<x,y,z> = PolynomialRing(QQ,3,order='neglex')
sage: x > y
False
sage: x > 1
False
sage: x^1*y^2 > y^3*z^4
False
sage: x^3*y^2*z^4 < x^3*y^2*z^1
True
sage: x*y > z
False

This term ordering is called 'ls' in Singular.

Negative degree reverse lexicographic (negdegrevlex)

Let $ deg(x^a) = a_0 + \cdots + a_{n-1},$ then $ x^a < x^b \Leftrightarrow deg(x^a) > deg(x^b)$ or $ deg(x^a) = deg(x^b)$ and $ \exists\ 0 \le i < n: a_{n-1} = b_{n-1}, \ldots, a_{i+1} = b_{i+1}, a_i > b_i.$

sage: P.<x,y,z> = PolynomialRing(QQ,3,order='negdegrevlex')
sage: x > y
True
sage: x > x^2
True
sage: x > 1
False
sage: x^1*y^2 > y^3*z^4
True
sage: x^2*y*z^2 > x*y^3*z
False

This term ordering is called 'ds' in Singular.

Negative degree lexicographic (negdeglex)

Let $ deg(x^a) = a_0 + \cdots + a_{n-1},$ then $ x^a < x^b \Leftrightarrow deg(x^a) > deg(x^b)$ or $ deg(x^a) = deg(x^b)$ and $ \exists\ 0 \le i < n:a_0 = b_0, \ldots, a_{i-1} = b_{i-1}, a_i < b_i.$

sage: P.<x,y,z> = PolynomialRing(QQ,3,order='negdeglex')
sage: x > y
True
sage: x > x^2
True
sage: x > 1
False
sage: x^1*y^2 > y^3*z^4
True
sage: x^2*y*z^2 > x*y^3*z
True

This term ordering is called 'Ds' in Singular.

Of these, only 'degrevlex', 'deglex', 'invlex' and 'lex' are global orderings.

Additionally all these monomial orderings may be combined to product or block orderings, defined as:

Let $ x = (x_0, \ldots, x_{n-1})$ and $ y = (y_0, \ldots, y_{m-1})$ be two ordered sets of variables, $ <_1$ a monomial ordering on $ k[x]$ and $ <_2$ a monomial ordering on $ k[y]$ .

The product ordering (or block ordering) $ <\ := (<_1,<_2)$ on $ k[x,y]$ is defined as: $ x^a y^b < x^A y^B \Leftrightarrow x^a <_1 x^A$ or $ (x^a =x^A \textrm{ and } y^b <_2 y^B)$ .

These block orderings are constructed in Sage by giving a comma separated list of monomial orderings with the length of each block attached to them.

As an example, consider constructing a block ordering where the first four variables are compared using the degree reverse lexicographical ordering while the last two variables in the second block are compared using negative lexicographical ordering.

sage: P.<a,b,c,d,e,f> = PolynomialRing(GF(127),6,order='degrevlex(4),neglex(2)')
sage: a > c^4
False
sage: a > e^4
True
sage: e > f^2
False

The same result can be achieved by:

sage: T1 = TermOrder('degrevlex',4)
sage: T2 = TermOrder('neglex',2)
sage: T = T1 + T2
sage: P.<a,b,c,d,e,f> = PolynomialRing(GF(127),6,order=T)
sage: a > c^4
False
sage: a > e^4
True

If any other unsupported term ordering is given the provided string is passed through as is to SINGULAR, MACAULAY2, and MAGMA. This ensures that it is for example possible to calculated a Groebner basis with respect to some term ordering SINGULAR supports but Sage doesn't. However a warning is issued to make the user aware of the situation and potential typos:

sage: P.<a,b,c,d,e,f> = PolynomialRing(GF(127),6,order=T)
sage: a > c^4
False
sage: a > e^4
True

If any other unsupported term ordering is given the provided string is passed through as is to SINGULAR, MACAULAY2, and MAGMA. This ensures that it is for example possible to calculated a Groebner basis with respect to some term ordering SINGULAR supports but Sage doesn't. However a warning is issued to make the user aware of the situation and potential typos:

sage: T = TermOrder("royalorder")
verbose 0 (...: term_order.py, __init__) Term ordering 'royalorder'
unknown.

Author Log:

Class: TermOrder

class TermOrder
A term order.

See sage.rings.polynomial.term_order for details on supported term orderings.

TermOrder( self, [name=lex], [n=0], [blocks=True])

Construct a new term ordering object.

Input:

name
- name of the term ordering (default: lex)
n
- number of variables in the polynomial ring (default: 0)
blocks
- controls whether a list of blocks is maintained (internal use only, default:True)

See the sage.rings.polynomial.term_order module for help which names and orderings are available.

sage: t = TermOrder('lex')
sage: t
Lexicographic term order
sage: loads(dumps(t)) == t
True

We can construct block orderings directly as

sage: TermOrder('degrevlex(3),neglex(2)')
degrevlex(3),neglex(2) term order

or by adding together the blocks:

sage: t1 = TermOrder('degrevlex',3)
sage: t2 = TermOrder('neglex',2)
sage: t1 + t2
degrevlex(3),neglex(2) term order
sage: t2 + t1
neglex(2),degrevlex(3) term order

NOTE: The optional $ n$ parameter is not necessary if only non-block orderings like $ deglex$ are constructed. However, it is useful if block orderings are to be constructed from this TermOrder object later.

Functions: compare_tuples_block,$ \,$ compare_tuples_dp,$ \,$ compare_tuples_Dp,$ \,$ compare_tuples_ds,$ \,$ compare_tuples_Ds,$ \,$ compare_tuples_lp,$ \,$ compare_tuples_ls,$ \,$ compare_tuples_rp,$ \,$ greater_tuple_block,$ \,$ greater_tuple_Dp,$ \,$ greater_tuple_dp,$ \,$ greater_tuple_Ds,$ \,$ greater_tuple_ds,$ \,$ greater_tuple_lp,$ \,$ greater_tuple_ls,$ \,$ greater_tuple_rp,$ \,$ is_global,$ \,$ is_local,$ \,$ macaulay2_str,$ \,$ magma_str,$ \,$ name,$ \,$ singular_str

compare_tuples_block( self, f, g)

Compares two exponent tuple with respec to the block ordering as specified when constructing this element.

Input:

f
- exponent tuple
g
- exponent tuple

sage: P.<a,b,c,d,e,f>=PolynomialRing(ZZ,6, order='degrevlex(3),degrevlex(3)')
sage: a > c^4 # indirect doctest
False
sage: a > e^4
True

compare_tuples_dp( self, f, g)

Compares two exponent tuples with respect to the degree reversed lexicographical term order.

Input:

f
- exponent tuple
g
- exponent tuple

sage: P.<x,y> = PolynomialRing(GF(127),2,order='degrevlex')
sage: x > y^2 # indirect doctest
False
sage: x > 1
True

compare_tuples_Dp( self, f, g)

Compares two exponent tuples with respect to the degree lexicographical term order.

Input:

f
- exponent tuple
g
- exponent tuple

sage: P.<x,y> = PolynomialRing(GF(127),2,order='deglex')
sage: x > y^2 # indirect doctest
False
sage: x > 1
True

compare_tuples_ds( self, f, g)

Compares two exponent tuples with respect to the negative degree reverse lexicographical term order.

Input:

f
- exponent tuple
g
- exponent tuple

sage: P.<x,y> = PolynomialRing(IntegerModRing(10), 2,order='negdegrevlex')
sage: x > y^2 # indirect doctest
True
sage: x > 1
False

compare_tuples_Ds( self, f, g)

Compares two exponent tuples with respect to the negative degree lexicographical term order.

Input:

f
- exponent tuple
g
- exponent tuple

sage: P.<x,y> = PolynomialRing(GF(2), 2,order='negdeglex')
sage: x > y^2 # indirect doctest
True
sage: x > 1
False

compare_tuples_lp( self, f, g)

Compares two exponent tuples with respect to the lexicographical term order.

Input:

f
- exponent tuple
g
- exponent tuple

sage: P.<x,y> = PolynomialRing(QQ,2,order='lex')
sage: x > y^2 # indirect doctest
True
sage: x > 1
True

compare_tuples_ls( self, f, g)

Compares two exponent tuples with respect to the negative lexicographical term order.

Input:

f
- exponent tuple
g
- exponent tuple

sage: P.<x,y> = PolynomialRing(GF(2^8,'a'),2,order='neglex')
sage: x > y^2 # indirect doctest
False
sage: x > 1
False

compare_tuples_rp( self, f, g)

Compares two exponent tuples with respect to the inversed lexicographical term order.

Input:

f
- exponent tuple
g
- exponent tuple

sage: P.<x,y> = PolynomialRing(ZZ,2,order='invlex')
sage: x > y^2 # indirect doctest
False
sage: x > 1
True

greater_tuple_block( self, f, g)

Compares two exponent tuple with respec to the block ordering as specified when constructing this element.

This method is called by the lm/lc/lt methods of MPolynomial_polydict.

Input:

f
- exponent tuple
g
- exponent tuple

sage: P.<a,b,c,d,e,f>=PolynomialRing(ZZ,6, order='degrevlex(3),degrevlex(3)')
sage: f = a + c^4; f.lm() # indirect doctest
c^4
sage: g = a + e^4; g.lm()
a

greater_tuple_Dp( self, f, g)

Returns the greater exponent tuple with respect to the total degree lexicographical term order.

Input:

f
- exponent tuple
g
- exponent tuple

sage: P.<x,y,z> = PolynomialRing(ZZ, 3, order='deglex')
sage: f = x + y; f.lm() # indirect doctest
x
sage: f = x + y^2*z; f.lm()
y^2*z

This method is called by the lm/lc/lt methods of MPolynomial_polydict.

greater_tuple_dp( self, f, g)

Returns the greater exponent tuple with respect to the total degree reversed lexicographical term order.

Input:

f
- exponent tuple
g
- exponent tuple

sage: P.<x,y,z> = PolynomialRing(ZZ, 3, order='degrevlex')
sage: f = x + y; f.lm() # indirect doctest
x
sage: f = x + y^2*z; f.lm()
y^2*z

This method is called by the lm/lc/lt methods of MPolynomial_polydict.

greater_tuple_Ds( self, f, g)

Returns the greater exponent tuple with respect to the negative degree lexicographical term order.

Input:

f
- exponent tuple
g
- exponent tuple

sage: P.<x,y,z> = PolynomialRing(ZZ,3,order='negdeglex')
sage: f = x + y; f.lm() # indirect doctest
y
sage: f = x + x^2; f.lm()
x
sage: f = x^2*y*z^2 + x*y^3*z; f.lm()
x*y^3*z

This method is called by the lm/lc/lt methods of MPolynomial_polydict.

greater_tuple_ds( self, f, g)

Returns the greater exponent tuple with respect to the negative degree reverse lexicographical term order.

Input:

f
- exponent tuple
g
- exponent tuple

sage: P.<x,y,z> = PolynomialRing(ZZ,3,order='negdegrevlex')
sage: f = x + y; f.lm() # indirect doctest
y
sage: f = x + x^2; f.lm()
x
sage: f = x^2*y*z^2 + x*y^3*z; f.lm()
x^2*y*z^2

This method is called by the lm/lc/lt methods of MPolynomial_polydict.

greater_tuple_lp( self, f, g)

Returns the greater exponent tuple with respect to the lexicographical term order.

Input:

f
- exponent tuple
g
- exponent tuple

sage: P.<x,y,z> = PolynomialRing(ZZ,3,order='lex')
sage: f = x + y^2; f.lm() # indirect doctest
x

This method is called by the lm/lc/lt methods of MPolynomial_polydict.

greater_tuple_ls( self, f, g)

Returns the greater exponent tuple with respect to the negative lexicographical term order.

This method is called by the lm/lc/lt methods of MPolynomial_polydict.

Input:

f
- exponent tuple
g
- exponent tuple

sage: P.<a,b,c,d,e,f>=PolynomialRing(ZZ,6, order='degrevlex(3),degrevlex(3)')
sage: f = a + c^4; f.lm() # indirect doctest
c^4
sage: g = a + e^4; g.lm()
a

greater_tuple_rp( self, f, g)

Returns the greater exponent tuple with respect to the inversed lexicographical term order.

Input:

f
- exponent tuple
g
- exponent tuple

sage: P.<x,y,z> = PolynomialRing(ZZ,3,order='invlex')
sage: f = x + y; f.lm() # indirect doctest
y
sage: f = y + x^2; f.lm()
y

This method is called by the lm/lc/lt methods of MPolynomial_polydict.

is_global( self)

Return True if this term ordering is definitely global. Return False otherwise, which includes unknown term orderings.

sage: T = TermOrder('lex')
sage: T.is_global()
True
sage: T = TermOrder('degrevlex', 3) + TermOrder('degrevlex', 3)
sage: T.is_global()
True
sage: T = TermOrder('degrevlex', 3) + TermOrder('negdegrevlex', 3)
sage: T.is_global()
False

is_local( self)

Return True if this term ordering is definitely local. Return False otherwise, which includes unknown term orderings.

sage: T = TermOrder('lex')
sage: T.is_local()
False
sage: T = TermOrder('negdeglex', 3) + TermOrder('negdegrevlex', 3)
sage: T.is_local()
True
sage: T = TermOrder('degrevlex', 3) + TermOrder('negdegrevlex', 3)
sage: T.is_local()
False

macaulay2_str( self)

Return a Macaulay2 representation of self.

Used to convert polynomial rings to their Macaulay2 representation.

sage: P = PolynomialRing(GF(127),8,names='x',order='degrevlex(3),lex(5)')
sage: T = P.term_order()
sage: T.macaulay2_str()
'(GRevLex => 3,Lex => 5)'
sage: P._macaulay2_() # optional -- requires macaulay2
ZZ/127 [x0, x1, x2, x3, x4, x5, x6, x7, MonomialOrder => {GRevLex => 3, Lex
=> 5}, MonomialSize => 16]

magma_str( self)

Return a MAGMA representation of self.

Used to convert polynomial rings to their MAGMA representation.

sage: P = PolynomialRing(GF(127),10,names='x',order='degrevlex')
sage: P._magma_() # optional, requires MAGMA
Polynomial ring of rank 10 over GF(127)
Graded Reverse Lexicographical Order
Variables: x0, x1, x2, x3, x4, x5, x6, x7, x8, x9

sage: T = P.term_order()
sage: T.magma_str()
'"grevlex"'

name( self)

sage: TermOrder('lex').name()
'lex'

singular_str( self)

Return a SINGULAR representation of self.

Used to convert polynomial rings to their SINGULAR representation.

sage: P = PolynomialRing(GF(127),10,names='x',order='lex(3),deglex(5),lex(2)')
sage: T = P.term_order()
sage: T.singular_str()
'(lp(3),Dp(5),lp(2))'
sage: P._singular_()
//   characteristic : 127
//   number of vars : 10
//        block   1 : ordering lp
//                  : names    x0 x1 x2
//        block   2 : ordering Dp
//                  : names    x3 x4 x5 x6 x7
//        block   3 : ordering lp
//                  : names    x8 x9
//        block   4 : ordering C

Special Functions: __add__,$ \,$ __cmp__,$ \,$ __getitem__,$ \,$ __init__,$ \,$ __iter__,$ \,$ __len__,$ \,$ _repr_

__add__( self, other)

Block ordering constructor.

Input:

other
- a term order

Output: a block ordering

sage: from sage.rings.polynomial.term_order import TermOrder
sage: TermOrder('deglex',2) + TermOrder('degrevlex(3),neglex(3)')
deglex(2),degrevlex(3),neglex(3) term order

__cmp__( self, other)

Only equality testing makes sense here.

sage: TermOrder('lex') == TermOrder('lex',3)
True

sage: TermOrder('degrevlex') == TermOrder('lex')
False

sage: T1 = TermOrder('lex',2)+TermOrder('lex',3)
sage: T2 = TermOrder('lex',3)+TermOrder('lex',2)
sage: T1 == T2
False

sage: T1 = TermOrder('lex',2)+TermOrder('neglex',3)
sage: T2 = TermOrder('lex',2)+TermOrder('neglex',3)
sage: T1 == T2
True

__getitem__( self, i)

Return the i-th block of this term ordering.

Input:

i
- index

sage: T = TermOrder('lex')
sage: T[0]
Lexicographic term order

sage: T = TermOrder('lex', 2) + TermOrder('degrevlex', 3)
sage: T[1]
Degree reverse lexicographic term order

Note that len(self) does not count blocks but variables.

sage: T = TermOrder('lex', 2) + TermOrder('degrevlex', 3)
sage: T[len(T)-1]
Traceback (most recent call last):
...
IndexError: tuple index out of range

__iter__( self)

Iterate over the blocks of this term ordering.

sage: T = TermOrder('lex')
sage: list(T) # indirect doctest
[Lexicographic term order]

sage: T = TermOrder('lex', 2) + TermOrder('degrevlex', 3)
sage: list(T)
[Lexicographic term order, Degree reverse lexicographic term order]

Note that len(self) and len(list(self)) are not the same. The former counts the number of variables in self while the latter counts the number of blocks.

__len__( self)

Return the length of this term ordering, i.e. the number of variables it covers. This may be zero for undefinitely many variables.

sage: T = TermOrder('lex')
sage: len(T)
0
sage: T = TermOrder('lex', 2) + TermOrder('degrevlex', 3)
sage: len(T)
5

_repr_( self)

sage: TermOrder('lex') # indirect doctest
Lexicographic term order

See About this document... for information on suggesting changes.