Monomial orderings

Monomial orderings are used to define a division algorithm for multivariate polynomials. There can be many such orderings.

A monomial ordering in $k[x_1, \ldots, x_n]$, where $k$ is a field, is essentially a multiindex⁽¹⁾ because every monomial $x_1^{i_1}x_2^{i_2}\cdots x_n^{i_n}$ is uniquely identified by a vector $\iota = (i_1, \ldots, i_n)\in \mathbb{N}^n$, which is a multiindex. An ordering of monomials is an ordering in $\N^n$.

Desiderata

Desiderata for monomial orderings A monomial ordering on $k[x_1,\ldots, x_n]$ is a relation ${}>{}$ on $\N^n$ such that

1. ${}>{}$ is a total ordering
2. If $\alpha > \beta$ and $\gamma\in\N^n$, then $\alpha+\gamma > \beta+\gamma$
3. ${}>{}$ is a well-ordering on $\N^n$

A total order implies that

1. For $a, b\in \N^n$ either $a>b$, or $b>a$, or $a=b$
2. If $a<b$ and $b<c$ then $a<c$

A well-order means that every subset $A\subset\N^n$ has a least element. This means that every sequence $a_1 > a_2 > a_3 > \ldots$ eventually terminates.

Monomial orders

Lexicographic order

We use the notation $x^\alpha >_{\rm lex} x^\beta$ whenever $\alpha >_{\rm lex} \beta$.

The lexicographic order depends on the order of the variables. Let's see how the lex order works in $k[x_1, x_2, x_3]$:

1. $x_1$ has multiindex $(1, 0, 0)$ and $x_2$ has mutiindex $(0, 1, 0)$, so $(1, 0, 0) - (0, 1, 0) = (\textcolor{red}{1}, -1, 0)$, so $x_1 >_{\rm lex} x_2$
2. The multiindex of $x_2^2x_3$ is $(0, 2, 1)$, so $x_1 >_{\rm lex} x_2^2x_3$ because $(1, 0, 0) - (0, 2, 1) = (\textcolor{red}{+1}, -2, -1)$
3. Likewise $x_1x_2x_3^2 >_{\rm lex} x_1x_2x_3$ because $(1, 1, 2) >_{\rm lex} (1, 1, 1)$ because $(1,1,2)-(1,1,1)=(0, 0, \textcolor{red}{+1})$.

The second example is a little weird. The term $x_1$ has degree $1$, but $x_2^2x_3$ has degree $3$, yet $x_1 >_{\rm lex} x_2^2x_3$.

Graded lexicographic order

To remedy this we introduce an ordering called the graded lexicographic order which firstly orders the monomials by their total degree and then lexicographically.

Back to our previous examples, although $x_1 >_{\rm lex} x_2^2x_3$, we now have $x_1 <_{\rm grlex} x_2^2x_3$ because $\deg(x^2x_3)=3$, while $\deg(x_1)=1$.

Multidegree and leading monomial

We can now define

Exercises

This is from Ref 1., p60:

Exercise 1, p60. Rewrite each of the following polynomials, ordering the terms using the lex order and the grlex order, giving $\operatorname{mdeg} f$, $\operatorname{lc}f$, $\operatorname{lm}f$, and $\operatorname{lt} f$ in each case.

1. $f_1(x, y, z) = 2x+3y+z+x^2 −z^2 +x^3$
2. $f_2(x, y, z) = 2x^2 y^8 −3x^5yz^4 +xyz^3 −xy^4$

Solution. (1) For $f_1$ we have

The lexicographic ordering is

$$(3, 0, 0) >_{\rm lex} (2, 0, 0) >_{\rm lex} (1, 0, 0) >_{\rm lex} (0, 1, 0) >_{\rm lex} (0, 0, 2) >_{\rm lex} (0, 0, 1),$$

i.e.,

$$x^3 >_{\rm lex} x^2 >_{\rm lex} x >_{\rm lex} y >_{\rm lex} z^2 >_{\rm lex} z.$$

Under this ordering:

$$\begin{aligned} \operatorname{mdeg} f {}={}& (3, 0, 0)\\ \operatorname{lc}f {}={}& 1,\\ \operatorname{lm}f {}={}& x^3,\\ \operatorname{lt}f {}={}& x^3. \end{aligned}$$

The graded lexicographic ordering is

$$(3, 0, 0) >_{\rm grlex} (2, 0, 0) >_{\rm grlex} (0, 0, 2) >_{\rm grlex} (1, 0, 0) >_{\rm grlex} (0, 1, 0) >_{\rm grlex} (0, 0, 1),$$

or, in terms of monomials

$$x^3 >_{\rm grlex} x^2 >_{\rm grlex} z^2 >_{\rm grlex} x >_{\rm grlex} y >_{\rm grlex} z.$$

and under the graded lex ordering we have the same multideg as before.

(2) For $f_2$ we have the following table

Here the lexicographic and graded lexicographic orderings coincide:

$$x^5yz^4 > x^2y^8 > xy^4 > xyz^3,$$

and

$$\begin{aligned} \operatorname{mdeg} f_2 {}={}& (5, 1, 4)\\ \operatorname{lc}f_2 {}={}& -3,\\ \operatorname{lm}f_2 {}={}& x^5yz^4,\\ \operatorname{lt} f_2 {}={}& -3x^5yz^4. \end{aligned}$$

This completes the solution. $\bullet$

We can show that

We can also show the following regarding $\operatorname{lt}$:

The property $\operatorname{lt}(fg)=\operatorname{lt}(f)\operatorname{lt}(g)$ is because $k$ is a field, thus an integral domain⁽²⁾, so the product of two nonzero elements is nonzero. No cancellation can occur when multiplying.

MATLAB implementations

Implementation of lex order:

function y = lex(a, b)
% Lexicographic ordering of multiindices
%
% INPUTS:
% a, b: multiindices (arrays)
% OUTPUT:
% 1 if a > b, -1 if b > a, 0 if a = b

d = a - b;
idx_d = find(d~=0, 1, 'first');
if isempty(idx_d)
    y = 0;
else
    y = sign(d(idx_d));
end

The graded lex ordering is as follows:

function y = grlex(a, b)
% Graded lexicographic ordering of multiindices
%
% INPUTS:
% a, b: multiindices (arrays)
% OUTPUT:
% 1 if a > b, -1 if b > a, 0 if a = b

d_deg = sum(a) - sum(b);
if d_deg ~= 0
    y = sign(d_deg);
else
    y = lex(a, b);
end

The following function orders a sequence of multiindices according to a monomial ordering. The sequence of monomials is provided as a matrix where each row is a multiindex. This implementation is adapted from code found on Wikipedia’s article on the cocktail shaker sort.

% INPUTS:
% x - matrix of multiindices (monomials)
% ord - monomial ordering as function handle
%       defaults to lex
% OUTPUT:
% x - sorted x

if nargin == 1
    ord = @(s1, s2) lex(s1, s2);
end

beginIdx = 1;
endIdx = size(x, 1) - 1;

while beginIdx <= endIdx
    newBeginIdx = endIdx;
    newEndIdx = beginIdx;
    for ii = beginIdx:endIdx
        if ord(x(ii,:), x(ii + 1, :)) == -1
            [x(ii+1, :), x(ii, :)] = deal(x(ii, :), x(ii+1, :));
            newEndIdx = ii;
        end
    end
    
    endIdx = newEndIdx - 1;
    
    for ii = endIdx:-1:beginIdx
        if ord(x(ii, :), x(ii + 1,:)) == -1
            [x(ii+1, :), x(ii, :)] = deal(x(ii, :), x(ii+1,:));
            newBeginIdx = ii;
        end
    end
    beginIdx = newBeginIdx + 1;
end
end

Example of use:

sort1 = monomial_sort([1 2 0;0 2 1;2 0 0; 1 0 0; 1 1 1]);
grl = @(s1, s2) grlex(s1, s2);
sort2 = monomial_sort([1 2 0;0 2 1;2 0 0; 1 0 0; 1 1 1], grl);

References

1. David A. Cox, John Little, Donal O’Shea, Ideals, Varieties and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, Springer, 2015

Endnotes

1. A multiindex is an $n$-tuple of nonnegative integers. The length of a multiindex $\alpha$ is the sum of its components and it is denoted as $|\alpha|$.

2. Recall that an integral domain is a nonzero commutative ring where the product of nonzero elements is nonzero ($ab=0$ implies $a=0$ or $b=0$).