HowTo:Term Orderings

This page is an introduction into term orderings in CoCoA-5 or ApCoCoA-2. In order to understand this topic, we assume that the reader is familiar with the concept of term orderings on polynomial rings.

Mathematical definition

Let K be a field, let $P=K[x_{1},\ldots ,x_{n}]$ be the polynomial ring over K in n indeterminates and let $\mathbb {T} (P)=\{x_{1}^{\alpha _{1}}\cdots x_{n}^{\alpha _{n}}\mid \alpha _{1},\ldots ,\alpha _{n}\in \mathbb {N} _{0}\}$ be the set of all power products in P.

Let $\sigma$ be a total order on T(P). For a pair $(t_{1},t_{2})\in \sigma$, we write $t_{1}\leq _{\sigma }t_{2}$. Then $\sigma$ is called a term ordering on T(P) iff it is multiplicative, i.e. $t_{1}\leq _{\sigma }t_{2}$ implies $st_{1}\leq _{\sigma }st_{2}$ for each $t_{1},t_{2},s\in \mathbb {T} (P)$, and we have $1\leq _{\sigma }t$ for all terms $t\in \mathbb {T} (P)$.

For a polynomial $f\in P$, we can write $f=c_{1}t_{1}+\cdots +c_{s}t_{s}$ where $t_{i}\in \mathbb {T} (P)$ and $c_{i}\in K^{\times }$ for each i such that $t_{1}>_{\sigma }\cdots >_{\sigma }t_{s}$. Then we use the following notation

• ${\rm {LT}}_{\sigma }(f)=t_{1}$ is the leading terms of f,
• ${\rm {LC}}_{\sigma }(f)=c_{1}$ is the leading monomial of f and
• ${\rm {LM}}_{\sigma }(f)=c_{1}t_{1}$ is the leading coefficient of f.

Given a matrix $M=(a_{ij})\in {\rm {GL}}_{n}(\mathbb {Q} )$ such that the first entry of every column is positive, we can define a term ordering ordering Ord(M) on P in the following way: For two vectors $v,w\in K^{n}$ we define $v\leq _{\texttt {Lex}}w$ if either v = w or the first non-zero entry of w-v is positive. Then Ord(M) is defined by

$x_{1}^{\alpha _{1}}\cdots x_{n}^{\alpha _{n}}\leq _{{\rm {Ord}}(M)}x_{1}^{\beta _{1}}\cdots x_{n}^{\beta _{n}}\iff M\cdot (\alpha _{1},\ldots ,\alpha _{n})^{\rm {tr}}\leq _{\texttt {Lex}}M\cdot (\beta _{1},\ldots ,\beta _{n})^{\rm {tr}}$.

It is easy to show that this defines a term ordering on P.

Term Orderings in CoCoA

In CoCoA, term orderings are defined in the definition of polynomial rings and can not be changed later during the computation.

Setting up a Term Ordering

At top-level, the currently available term orderings are

Use P ::= QQ[x,y,z], Lex;
Use P ::= QQ[x,y,z], DegLex;
Use P ::= QQ[x,y,z], DegRevLex;

These calls create the ring $P:=\mathbb {Q} [x,y,z]$ with the corresponding term orderings. These term orderings correspond to the matrices

$M_{\texttt {Lex}}={\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix}}$

$M_{\texttt {DegLex}}={\begin{pmatrix}1&1&1\\1&0&0\\0&1&0\end{pmatrix}}$

$M_{\texttt {DegRevLex}}={\begin{pmatrix}1&1&1\\0&0&-1\\0&-1&0\end{pmatrix}}$

The default term odering is DegRevLex if no order is specified.

For term orderings different for the ones above, one can use the function NewPolyRing to create an ordered polynomial ring. Given a base ring R (which does not have to be a field), a String or a list L of indeterminates (for details, see the description of the function in CoCoA) and a matrix M corresponding to a term ordering, one can call

P := NewPolyRing(R, "x,y,z", M, 1);

in order to create the polynomial ring R[x,y,z] which is ordered by Ord(M). Using the call OrdMat(P), we can then check that P is indeed ordered by the matrix M.

There are also a couple of functions that help creating a term ordering. For instance, if we already have matrix M with n columns, only s rows where $s<n$, one can call MakeTermOrd(M) to get a term ordering matrix whose first s rows are the original matrix M. For some fixed term orderings, one can use the functions LexMat(n), XelMat(n), StdDegLexMat(n), StdDegRevLexMat(n).

/**/ MakeTermOrd(matrix([[1,2,3]]));
matrix(ZZ,
 [[1, 2, 3],
  [0, 0,-1],
  [0,-1, 0]])
/**/ LexMat(3);
matrix(ZZ,
 [[1, 0, 0],
  [0, 1, 0],
  [0, 0, 1]])
/**/ XelMat(3);
matrix(ZZ,
 [[0, 0, 1],
  [0, 1, 0],
  [1, 0, 0]])
/**/ StdDegLexMat(3);
matrix(ZZ,
 [[1, 1, 1],
  [1, 0, 0],
  [0, 1, 0]])
/**/ StdDegRevLexMat(3);
matrix(ZZ,
 [[1, 1, 1],
  [0, 0,-1],
  [0,-1, 0]])

A special command is the function ElimMat. Given a polynomial ring $P=K[x_{1},\ldots ,x_{n}]$ and a list L which is a the call ElimMat(L,n) produces a matrix M corresponding to an elimination ordering for $\{x_{i}\mid i\in L\}$, i.e. an odering $\sigma$ such that ${\rm {LT}}_{\sigma }(f)\in K[x_{l}\mid l\not \in L]\iff f\in K[x_{l}\mid l\not \in L]$, or - more informally - the indeterminates of P corresponding to the indices in L are infinitely larger than the other ones.

/**/ ElimMat([1,2],4);
matrix(ZZ,
 [[1, 1, 0, 0],
  [1, 1, 1, 1],
  [0, 0, 0,-1],
  [0,-1, 0, 0]])

Working with an Ordered Polynomial Ring

In CoCoA, polynomials are elements of rings and rings already fix a term ordering. This means, that the leading term of a polynomial in CoCoA does only depend on the ring which the polynomial is an element of. Therefore, the calls LT(f), LC(f), LM(f) are well-defined and do not need the ordering as an additional argument like the mathematical description Failed to parse (syntax error): {\displaystyle {\rm LT_\sigma(f)} .

Also the function GBasis(I) for computing a Gröbner basis of an ideal I does not need the term ordering as an argument as it is already fixed in the definition of the ring RingOf(I). For the same reason, the call LT(I) is well-defined.

Switching Orderings

While there is no way to change the term ordering of a ring, there is the possibility of creating a new polynomial ring an mapping the elements between them. For instance, suppose we have an ideal I in a ring P, but want to compute a Gröbner basis of I with respect to a different term ordering given by a matrix M. Then one can use the following:

/**/ Q := NewPolyRing(CoeffRing(P), SymbolRange("x",1,NumIndets(P)), M, 1);
/**/ phi := PolyAlgebraHom(P, Q, indets(Q));
/**/ I_Q := ideal(apply(phi, gens(I)));
/**/ GB_Q := GBasis(I_Q); -- a list of polynomials in Q
/**/ GB_P := [ preimage0(phi, g) | g in GB_Q ];

Note: If you now print out the result with GB_P, then the polynomials are printed out as elements of P, so their leading terms now most likely do not generate the leading term ideal of I.

A Small Example

Suppose, we start with the following code:

/**/ Use P ::= QQ[y[1..3],x[1..2]]; -- std ordering is DegRevLex
/**/ f1 := y[1] - x[1]^2;
/**/ f2 := y[2] - x[2]^2;
/**/ f3 := y[3] - x[1]*x[2];
/**/ I := ideal(f1,f2,f3);

Furthermore, suppose that we want to compute the intersection of I with the ring R = QQ[y[1],y[2],y[3]]. Then we apply the code described above:

/**/ M := ElimMat([4,5], 5);
/**/ Q := NewPolyRing(CoeffRing(P), SymbolRange("x",1,NumIndets(P)), M, 1);
/**/ phi := PolyAlgebraHom(P, Q, indets(Q));
/**/ I_Q := ideal(apply(phi, gens(I)));
/**/ GB_Q := GBasis(I_Q);
/**/ GB_P := [ preimage0(phi, g) | g in GB_Q ];

If we now print out GB_P, we see that the only polynomial in its intersection with R is y[1]*y[2] -y[3]^2. This shows that $I\cap R=\langle y_{1}y_{2}-y_{3}^{2}\rangle _{R}$.