Chapter 18
Ordering on variables and monomials

As was mentioned above (Section 10.4.1), one needs to declare a monomial order before making a Gröbner Basis. There are various monomial orders which can be used when computing Gröbner Basis. The most common are called lexicographic and graded lexicographic orders. In the previous section, we used only graded lexicographic orders. See Section 18.1 for a discussion of lexicographic orders.

We will be considering lexicographic, graded lexicographic and multi-graded lexicographic orders. Lexicographic and multi-graded lexicographic orders are examples of elimination orderings. An elimination ordering is an ordering which is used for solving for some of the variables in terms of others.

We now discuss each of these types of orders.

18.1 Lex Order: The simplest elimination order

To impose lexicographic order a << b << x << y on a, b, x and y, one types

This order is useful for attempting to solve for y in terms of a, b and x, since the highest priority of the GB algorithm is to produce polynomials which do not contain y. If producing high order polynomials is a consequence of this fanaticism so be it. Unlike graded orders, lex orders pay little attention to the degree of terms. Likewise its second highest priority is to eliminate x.

Once this order is set, one can use all of the commands in the preceeding section in exactly the same form.

We now give a simple example how one can solve for y given that a,b,x and y satisfy the equations:

If the polynomials above are converted to replacement rules, then a simple glance at the results allows one to see that y has been solved for.

Now, we change the order to

and do the same NCMakeGB as above:

In this case, it turns out that it produced the rule a**b**x**x → y + b**a which shows that the order is not set up to solve for y in terms of the other variables in the sense that y is not on the left hand side of this rule (but a human could easily solve for y using this rule). Also the algorithm created a number of other relations which involved y. If one uses the lex order a << b << y << x, the NCMakeGB call above generates 12 polynomials of high total degree which do not solve for y.

See [CoxLittleOShea].

18.2 Graded lex ordering: A non-elimination order

This is the ordering which was used in all demos appearing before this section. It puts high degree monomials high in the order. Thus it tries to decrease the total degree of expressions.

18.3 Multigraded lex ordering : A variety of elimination orders

There are other useful monomial orders which one can use other than graded lex and lex. Another type of order is what we call multigraded lex and is a mixture of graded lex and lex order. This multigraded order is set using SetMonomialOrder, SetKnowns and SetUnknowns which are described in Section 18.4. As an example, suppose that we execute the following commands:

We use the notation

For an intuitive idea of why multigraded lex is helpful, we think of A, B and C as corresponding to variables in some engineering problem which represent quantities which are known and a, b, c, d, e and f to be unknown¹. The fact that d, e and f are in the top level indicates that we are very interested in solving for d, e and f in terms of A, B, C, a, b and c, but are not willing to solve for b in terms of expressions involving either d, e or f.

For example,

(1) d > a **a **A **b

(2) d **a **A **b > a

(3) e **d > d **e

(4) b **a > a **b

(5) a **b **b > b **a

(6) a > A **B **A **B **A **B

This order induces an order on monomials in the following way. One does the following steps in determining whether a monomial m is greater in the order than a monomial n or not.

(1) First, compute the total degree of m with respect to only the variables d, e and f.

(2) Second, compute the total degree of n with respect to only the variables d, e and f.

(3) If the number from item (2) is smaller than the number from item (1), then m is smaller than n. If the number from item (2) is bigger than the number from item (1), then m is bigger than n. If the numbers from items (1) and (2) are equal, then proceed to the next item.

(4) First, compute the total degree of m with respect to only the variables a, b and c.

(5) Second, compute the total degree of n with respect to only the variables a, b and c.

(6) If the number from item (5) is smaller than the number from item (4), then m is smaller than n. If the number from item (5) is bigger than the number from item (4), then m is bigger than n. If the numbers from items (4) and (5) are equal, then proceed to the next item.

(7) First, compute the total degree of m with respect to only the variables A, B and C.

(8) Second, compute the total degree of n with respect to only the variables A, B and C.

(9) If the number from item (8) is smaller than the number from item (7), then m is smaller than n. If the number from item (8) is bigger than the number from item (7), then m is bigger than n. If the numbers from items (7) and (8) are equal, then proceed to the next item.

(10) At this point, say that m is smaller than n if and only if m is smaller than n with respect to the graded lex order A < B < C < a < b < c < d < e < f

For more information on multigraded lex orders, consult [HSStrat].

18.4 The list of commands

18.4.1 SetMonomialOrder[aListOfListsOfIndeterminates, . . . ]

Aliases: None

Description: SetMonomialOrder[a,b,c,...] sets the graded lex order a < b < c < … with a < b < c < . If one uses a list of variables rather than a single variable as one of the arguments, then multigraded lex order is used. It is synonomous with SetMonomialOrder[{a,b,c,...}]. Pure lex order a << b << c << … on these variables is set by SetMonomialOrder[{{a}, {b}, {c },...}].

Arguments: A multigraded lex order a < b << c < … on these variables is set by SetMonomialOrder[{ {a, b }, {c },...}]. aListOfListsOfIndeterminates is a list of Mathematica variable or a list of Mathematica variables.

Comments / Limitations: Not available before NCAlgebra 1.2.

Equivalent to SetMonomialOrder[{a,b }, {c , A }] is SetMonomialOrder[{{a,b }, {c , A }}]. Or alternatively this is equivalent the following two commands

which we now describe.

18.4.2 SetUnknowns[aListOfIndeterminates]

Aliases: None

Description: SetUnknowns[aListOfVariables] records the variables in the list of variables aListOfIndeterminates to be corresponding to unknown quantities. This and SetUnknowns prescribe a monomial order with the knowns at the the bottom and the unknowns at the top.

Arguments: aListOfIndeterminates is a list of Mathematica variables.

Comments / Limitations: Not available before NCAlgebra 1.2. This is equivalent to Do[SetMonomialOrder[aListOfVariables[[i]],i+1], {i, 1,Length[aListOfV ariables]}]

18.4.3 SetUnKnowns[aListOfVariables]

Aliases: None

Description: SetUnKnowns[aListOfVariables] records the variables in the list of variables aListOfVariables to be corresponding to unknown quantities. This and SetUnknowns prescribe a monomial order with the knowns at the the bottom and the unknowns at the top.

Arguments: aListOfVariables is a list of Mathematica variables.

Comments / Limitations: Not available before NCAlgebra 1.2. This is equivalent to Do[SetMonomialOrder[aListOfVariables[[i]],i+1], {i, 1,Length[aListOfV ariables]}]

18.4.4 ClearMonomialOrder[]

Aliases: None

Description: After ClearMonomialOrder[] is called, there are no indeterminates which are considered ordered. The monomial order can be retrieved by using the ReinstallOrder[] command.

Arguments: None

Comments / Limitations: Not available before NCAlgebra 1.2

18.4.5 PrintMonomialOrder[]

Aliases: None

Description: PrintMonomialOrder[] prints the order to the screen.

Arguments: None

Comments / Limitations: See Chapter 18. Not available before NCAlgebra 1.2

18.4.6 NCAutomaticOrder[ aMonomialOrder, aListOfPolynomials ]

Aliases: None

Description: This command assists the user in specifying a monomial order. It inserts all of the indeterminants found in aListOfPolynomials into the monomial order. If x is an indeterminant found in aMonomialOrder then any indeterminant whose symbolic representation is a function of x will appear next to x. For example, NCAutomaticOrder[{{a},{b}},{ a**Inv[a]**tp[a] + tp[b]}] would set the order to be a < tp[a] < Inv[a] ≪ b < tp[b].

Arguments: A list of indeterminants which specifies the general order. A list of polynomials which will make up the input to the Gröbner basis command.

Comments / Limitations: If tp[Inv[a]] is found after Inv[a] NCAutomaticOrder[ ] would generate the order a < tp[Inv[a]] < Inv[a]. If the variable is self-adjoint (the input contains the relation tp[Inv[a]] == Inv[a]) we would have the rule, Inv[a] → tp[Inv[a]], when the user would probably prefer tp[Inv[a]] → Inv[a].

18.5 Fancier Order Setting Commands

The following commands were created for a project, long ago and we have not used them recently.

18.5.1 SetMonomialOrder[aListOfIndeterminants, n]

Aliases: None

Description: SetMonomialOrder[aListOfIndeterminates,n] sets the order of monomials (e.g., if aListOfIndeterminates is {a,b,c,d,f,e}, then the order is a < b < c < d < f < e) and assigns them grading level n. To obtain a graded lexicographic order, one can use n = 1.

Arguments: aListofIndeterminants is a list of indeterminates, n is a natural number

Comments / Limitations: See Chapter 18. Not available before NCAlgebra 1.2

18.5.2 ClearMonomialOrderN[n]

Aliases: None

Description: ClearMonomialOrderN[n] clears the order having level n. This command is equivalent to clearing SetMonomialOrder[{},n]

Arguments: n is an integer or blank

Comments / Limitations: Not available before NCAlgebra 1.2.

18.5.3 ClearMonomialOrderAll[]

Aliases: None

Description: ClearMonomialOrderAll[] effectively executes ClearMonomialOrderN[n] for all positive integers n.

Arguments: None

Comments / Limitations: Not available before NCAlgebra 1.2.

18.5.4 WhatIsMultiplicityOfGrading[]

Aliases: None

Description: WhatIsMultiplicityOfGrading[] returns a positive integer which is the multiplicity of the grading. If the value is 1, then one is using graded lexicographical order.

Arguments: None

Comments / Limitations: See Chapter 18. Not available before NCAlgebra 1.2

18.5.5 WhatIsSetOfIndeterminants[n]

Aliases: None

Description: WhatIsSetOfIndeterminants[n] gives the n-th set of indeterminates.

Arguments: None

Comments / Limitations: See Chapter 18. Not available before NCAlgebra 1.2