A Gröbner Basis can be infinite. Even when a Gröbner Basis is finite, it can be very large and therefore difficult for a person to digest. One often finds that there are many relations which are generated which do not enhance our understanding of the mathematics. In many cases we want a basis for an ideal which is minimal (i.e., has smallest cardinality) or which is minimal as a subset of a given basis. We, therefore, find it helpful to take a list of rules which are generated by the GB algorithm and make them smaller. Consider the following example.
Example 21.1 A GB generated by the set {PTP -TP,P2-P} is the set {PTnP -TnP : n ≥ 1}∪{P2 - P} regardless of the term order used. No smaller GB exists.
Here just two relations generate infinitely many. One way to view this example is that the computer discovers that if a subspace (represented by ran(P) in the computation) is invariant for a linear transformation T, then it is invariant for Tn for every n ≥ 1.
The GB algorithms tries to generate this infinite set of relations and at any time has generated a finite subset of them. When we are trying to discover a theorem or elegant formulas, often these relations having higher powers are irrelevant and clutter the spreadsheet which merely serves to confuse the user.
This introduces the next topic which is shrinking a set of relations to eliminate redundancy. Our desire is to take the generated basis and to remove mathematical redundancy from the generating set without destroying the information which was gained while running the GB algorithm.
We have two lines of attack on this problem. One will be described in this chapter, another will be described in Chapter 30.
Our second line of attack can be slower. It finds a subset of the set of relations by applying the GB machinery. For example, if one knows that pn is a member of the ideal generated by {p1,…,pn-1}, then the set {p1,…,pn} can be shrunk to {p1,…,pn-1}. Determining whether or not pn is a member of the ideal generated by {p1,…,pn-1} can be partially decided by running the GB algorithm for several iterations.
WARNING: This command calls NCMakeGB which effects the output of the WhatIsHistory command which in turn can effect the use of the command RemoveRedundant and its variants (subsections 30.1.2, 30.1.3, 30.1.4 and 30.1.5) or the use of the command SmallBasis and its variants (subsections 21.1.1 and 21.1.2).
For example, after loading the files NCGB.m, SmallBasis.m (§21.1.1) 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 (§21.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}. 1
In[5]:= SmallBasis[%4,{},4];
Out[5]= {-p + p ** p, -a ** p + p ** a ** p} |
As a second example, after loading the files NCGB.m, SmallBasis.m and RemoveRedundent.m, we can execute the following commands to compute a Gröbner Basis for the set of relations {x2 - a,x3 - b}:
In[3]:= SetKnowns[a,b,x]
In[4]:= NCMakeGB[{x**x-a,x**x**x-b},10] Out[4]= {-a + x ** x, -b + a ** x, -b + x ** a, -a ** a + b ** x, > -a ** b + b ** a, -a ** a + x ** b, -b ** b + a ** a ** a} |
Now, one might want to find a smaller generating set for the ideal specified above. The following command does that and took 9 seconds using the C++ version of the code.
In[5]:= SmallBasis[%4,{},3]
Out[5]= {a ** x -> b, x ** x -> a} |
Here is a session which does roughly what the spreadsheet command does. For more detail see Chapter 15
In[11]:=NCMakeGB[FAC,2];
In[11]:=SmallBasisByCategory[ RemoveRedundant[%, HISTORY see Section \ref{}??] ]; |
The next command tries to see if any of the undigested relations can be made simpler using the digested relations
In[12]:=NCSimplifyAll[%11, DigestedRelations[%11] ];
|
Finally we output the result to the file “SecondOutputForDemo”.
In[13]:=RegularOutput[%12, "SecondOutputForDemo"];
|
Now we return to the strategy demos of Chapter 15.
Inserting the command RemoveRedundant, see Section 30, inside of small basis may change the answer, but it yields the same answer as SmallBasis would have given with one particular order on the set of relations given as input. All this assumes that the number of iterations is large. Inserting RemoveRedundant saves much computer time.
The small basis and small basis by cawtegory options inside NCProcess are constructed from the small basis command described in this chapter.