Chapter 21
Commands for Making Small Bases for Ideals: Small Basis, Shrink Basis

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.

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 Tⁿ 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.

21.1 Brute Force: Shrinking

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 p_n is a member of the ideal generated by {p₁,…,p_n-1}, then the set {p₁,…,p_n} can be shrunk to {p₁,…,p_n-1}. Determining whether or not p_n is a member of the ideal generated by {p₁,…,p_n-1} can be partially decided by running the GB algorithm for several iterations.

21.1.1 SmallBasis[aListOfPolynomials, anotherListOfPolynomials, iter]

Aliases: None

Description: SmallBasis[aListOfPolynomials,,iter] computes and returns a list aList which is a subset of aListOfPolynomials such that the ideal generated by aList equals the ideal generated by aListOfPolynomials . anotherListOfPolynomials adds the feature that when one includes it in the call it just joins to the answer above without being changed. In other words, SmallBasis computes and returns a list aList which is a subset of aListOfPolynomials such that the ideal generated by Join[aList, anotherListOfPolynomials] equals the ideal generated by Join[aListOfPolynomials, anotherListOfPolynomials]. This is done via calls to NCMakeGB. NCMakeGB iterates at most iter times.
   Here is how it works: Let LP denote {p₁,p₂,…,p_u}. First SmallBasis[LP,{},iter] generates a partial GB for p₁,p₂, and reduces p₃,p₄,…,p_u with this GB. If the result is 0, then SmallBasis stops and returns {p₁,p₂}. If not SmallBasis generates GB(p₁,p₂,p₃) and reduces the remaining polynomials. Etc. Finally, SmallBasis returns {p₁,p₂,…,p_k} with the property that the partial Göbner Basis GB(p₁,…,p_k) reduces {p₁,p₂,…,p_n} to zero. Clearly, the result is very dependent on the order if the entries lie in LP. The integer iter determines the number of iterations used to produce the partial GB’s.
SmallBasis[LP1,LP2,iter] has the same functionality as Complement[ SmallBasis[ Join[LP2,LP1], {}, iter], LP2], (i.e., SmallBasis[Join[LP2,LP1], {}, iter] minus the set LP2) but is much faster.

Arguments: aListOfPolynomials and anotherListOfPolynomials are lists of polynomials. iter is a natural number.

Comments / Limitations:

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).

21.1.2 SmallBasisByCategory[aListOfPolynomials, iter]

Aliases: None

Description: SmallBasisByForCategory returns a list aList which is a sorted subset of aListOfPolynomials such that the ideal generated by Join[aList,anotherListOfPolynomials] equals the ideal generated by Join[aListOfPolynomials,anotherListOfPolynomials]. This is done via calls NCMakeGB.

Arguments: aListOfPolynomials is a list of polynomials. iter is a natural number.

Comments / Limitations: Not available before NCAlgebra 1.2

21.1.3 ShrinkOutput[aListOfPolynomials,fileName]

Aliases: None

Description: ShrinkOutput can take a very long time to run on large or complicated sets of polynomials. ShrinkOutput[aListOfPolynomials,fileName] takes the list of polynomials in aListOfPolynomials and puts a subset of aListOfPolynomials into a file via RegularOutput (subsection 23.3.1) This smaller subset is generated by the command SmallBasis (subsection 21.1.1)

Arguments: aListOfPolynomials is a list of polynomials. fileName is a character string

Comments / Limitations: Not available before NCAlgebra 1.2

21.2 Brute Force: Many shrinks

21.2.1 ShrinkBasis[aListOfPolynomials,iterations]

Aliases: None

Description: ShrinkBasis can take a long time to run and returns a {L₁,L₂,…,L_r} of lists of polynomials. Each list L_j of polynomials is contained in aListOfPolynomials. Each list L_j is a generating set for the ideal generated by aListOfPolynomials and the computer makes a limited attempt to show that any proper subset of L_j does not generate the ideal. Moreover, the union of the L_j’s is aListOfPolynomials.
 
ShrinkBasis depends upon the monomial order which is set, because it calls NCMakeGB where it iterates at most iterations times. If all of the runs of NCMakeGB generate Gröbner Bases in iterations iterations, then no proper subset of an L_j is a generating set for the ideal generated by aListOfPolynomials.
 
The command works by brute force. It selects a polynomial from aListOfPolynomials and computes a partial GB for the remaining polynomials (with iterations iterations). It uses these to eliminate the original polynomial.

Arguments: aListOfPolynomials is a list of polynomials. fileName is a string.

Comments / Limitations: Not available before NCAlgebra 1.2

21.3 First Example

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}:

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}. ¹

21.4 Second Example

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 {x² - a,x³ - b}:

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.

21.5 Smaller Bases and the Spreadsheet command

Here is a session which does roughly what the spreadsheet command does. For more detail see Chapter 15

The next command tries to see if any of the undigested relations can be made simpler using the digested relations

Finally we output the result to the file “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.

21.6 How Small Basis commands relate to the similar NCProcess Options

The small basis and small basis by cawtegory options inside NCProcess are constructed from the small basis command described in this chapter.