Lex Order: The simplest elimination order

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

In[14]:=SetMonomialOrder[a,b,x,y];

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:

$$-b x + x y a + x b a a = 0$$

$$x a-1=0$$

$$a x-1=0 .$$

In[15]:= NCMakeGB[{-b ** x + x ** y ** a + x ** b ** a ** a,
x**a-1,a**x-1},4];
Out[15]= {-1 + a ** x, -1 + x ** a, y + b ** a - a ** b ** x ** x}

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.

In[16]:= PolyToRule[%]
Out[16]= {a ** x -> 1, x ** a -> 1, y -> -b ** a + a ** b ** x ** x}

Now, we change the order to

In[20]:=SetMonomialOrder[y,x,b,a];

and do the same NCMakeGB as above:

In[21]:= NCMakeGB[{-b ** x + x ** y ** a + x ** b ** a ** a,
x**a-1,a**x-1},4];	
In[22]:= PolyToRule[%];
In[23]:= ColumnForm[%];
Out[23]= a ** x -> 1
         x ** a -> 1
         x ** b ** a -> -x ** y + b ** x ** x
         b ** a ** a -> -y ** a + a ** b ** x
         b ** x ** x ** x -> x ** b + x ** y ** x
         a ** b ** x ** x -> y + b ** a
         x ** b ** b ** a -> 
         >   -x ** b ** y - x ** y ** b ** x ** x + b ** x ** x ** b ** x ** x
         b ** a ** b ** a -> 
         >   -y ** y - b ** a ** y - y ** b ** a + a ** b ** x ** b ** x ** x
         x ** b ** b ** b ** a -> 
         >   -x ** b ** b ** y - x ** b ** y ** b ** x ** x - 
         >    x ** y ** b ** x ** x ** b ** x ** x + 
         >    b ** x ** x ** b ** x ** x ** b ** x ** x
         b ** a ** b ** b ** a -> 
         >   -y ** b ** y - b ** a ** b ** y - y ** b ** b ** a - 
         >    y ** y ** b ** x ** x - b ** a ** y ** b ** x ** x + 
         >    a ** b ** x ** b ** x ** x ** b ** x ** x

In this case, it turns out that it produced the rule $a ** b ** x ** x \rightarrow 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].