First Example

For example, after loading the files $NCGB.m$, SmallBasis3.m (§ 24.1.1) and RemoveRedundent.m (§34.1.2), we can execute the commands to compute a subset of a Gröbner Basis for the set of relations $\{p**p-p,p**a**p- a**p\}$:

In[2]:= SetKnowns[a,p]
In[3]:= {p**p-p,p**a**p - a**p}
Out[3]= {-p + p ** p, -a ** p + p ** a ** p}
In[4]:= NCMakeGB[%,4]

Out[4]= {-p + p ** p, -a ** p + p ** a ** p, -a ** a ** p + p ** a ** a ** p, 
>    -a ** a ** a ** p + p ** a ** a ** a ** p, 
>    -a ** a ** a ** a ** p + p ** a ** a ** a ** a ** p, 
>    -a ** a ** a ** a ** a ** p + p ** a ** a ** a ** a ** a ** p, 
>    -a ** a ** a ** a ** a ** a ** p + p ** a ** a ** a ** a ** a ** a ** p, 
>    -a ** a ** a ** a ** a ** a ** a ** p + 
>     p ** a ** a ** a ** a ** a ** a ** a ** p, 
>    -a ** a ** a ** a ** a ** a ** a ** a ** p + 
>     p ** a ** a ** a ** a ** a ** a ** a ** a ** p, 
>    -a ** a ** a ** a ** a ** a ** a ** a ** a ** p + 
>     p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p, 
>    -a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p + 
>     p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p, 
>    -a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p + 
>     p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p, 
>    -a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p + 
>     p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p, 
>    -a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p + 
>     p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p\
>     , -a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** 
>       a ** p + p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** 
>      a ** a ** a ** p, -a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** 
>       a ** a ** a ** a ** a ** p + 
>     p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** 
>      a ** a ** p, -a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** 
>       a ** a ** a ** a ** a ** p + 
>     p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** 
>      a ** a ** a ** p}

The command SmallBasis takes this (or any) set of relations and shrinks it down to a smaller set of relations which generate the same ideal. One must have a monomial order set because SmallBasis (§ 24.1.1) calls NCMakeGB. SmallBasis returns a subset of the original set of relations. In the example below the SmallBasis command shows that the ideal generated by the set Out[4] equals the ideal generated by $\{-p + p ** p, -a ** p + p ** a ** p\}$. ²

In[5]:= SmallBasis[%4,{},4];
Out[5]= {-p + p ** p, -a ** p + p ** a ** p}

Unfortunately in larger examples, SmallBasis is very slow which prompts the development of a more specialized command RemoveRedundant. This can be run only after NCMakeGB has been run because it uses the history of how the GB was produced. This history is equivalent to a tree which tells what relation came from what other relations RemoveRedundant uses only tree search methods so it is faster than SmallBasis.

As one sees below the information required for RemoveRedundant is a subset of the last GB produced in your session.

Before calling RemoveRedundent, one must acquire the history of the last GB produced in your section. This takes 2 commands which we now illustrate and which we explain afterward.

In[5]:= WhatAreNumbers[]
Out[5]= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17}
In[6]:= WhatIsHistory[%]

Out[6]= {{1, p ** p -> p, {0, 0}, {}}, 
>    {2, p ** a ** p -> a ** p, {0, 0}, {}}, 
>    {3, p ** a ** a ** p -> a ** a ** p, {2, 2}, {2}}, 
>    {4, p ** a ** a ** a ** p -> a ** a ** a ** p, {3, 2}, {2}}, 
>    {5, p ** a ** a ** a ** a ** p -> a ** a ** a ** a ** p, {3, 3}, {3}}, 
>    {6, p ** a ** a ** a ** a ** a ** p -> a ** a ** a ** a ** a ** p, 
>     {5, 2}, {2}}, {7, p ** a ** a ** a ** a ** a ** a ** p -> 
>      a ** a ** a ** a ** a ** a ** p, {5, 3}, {3}}, 
>    {8, p ** a ** a ** a ** a ** a ** a ** a ** p -> 
>      a ** a ** a ** a ** a ** a ** a ** p, {5, 4}, {4}}, 
>    {9, p ** a ** a ** a ** a ** a ** a ** a ** a ** p -> 
>      a ** a ** a ** a ** a ** a ** a ** a ** p, {5, 5}, {5}}, 
>    {10, p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p -> 
>      a ** a ** a ** a ** a ** a ** a ** a ** a ** p, {9, 2}, {2}}, 
>    {11, p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p -> 
>      a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p, {9, 3}, {3}}, 
>    {12, p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p -> 
>      a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p, {9, 4}, {4}}\
>     , {13, p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** 
>       p -> a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p, 
>     {9, 5}, {5}}, {14, p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** 
>       a ** a ** a ** a ** p -> 
>      a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p, 
>     {9, 6}, {6}}, {15, p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** 
>       a ** a ** a ** a ** a ** p -> 
>      a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p
>      , {9, 7}, {7}}, {16, p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** 
>       a ** a ** a ** a ** a ** a ** p -> 
>      a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** 
>       a ** p, {9, 8}, {8}}, {17, 
>     p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** 
>       a ** a ** a ** p -> 
>      a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** 
>       a ** a ** p, {9, 9}, {9}}}

The call to RemoveRedundent is:

In[7]:= RemoveRedundent[Out[4],Out[6]];
Out[7]= {-p + p ** p, -a ** p + p ** a ** p}

The first command recalls the number associated to all of the relations which occurred during the previous run of Mora's algorithm. The second command gives the ancestory and other information related to relations 1, 2, $\ldots$. One could have used any list of numbers (between 1 and 17) as the argument to the WhatIsHistory command and obtained only the history of those relations.