Chapter 29
History of the Production of a GB and Playing By Numbers

This chapter contains two advanced topics whose relationship is more technical than conceptual.

29.1 Play By Numbers

The Mathematica code and the C++ code both attach numbers to the polynomials which occur in the running of the GB algorithm. While these numbers are not externally visible at least in the commands described so far, they can be accessed by the user and are quite useful. One feature is that they can save typing time for the user who chooses to select or deselect relations in later runs of NCMakeGB. Also, if one is running the C++ version of the code, this will save considerable computer time because the C++ version of the code only has to send a number rather than the full polynomial to the Mathematica session. This time can be very significant when the polynomial has a large number of terms. See also section 29.2. Recall the Option ReturnRelationsToMma False for NCMakeGB stops the partial GB calculated by the C++ program from transferring the answer back to Mathematica. This is the typical prelude to a “play by numbers ” session.

Recall the option ReturnRelationsToMmaFalse for NCMakeGB stops the results from the NCMakeGB command from being returned to Mathematica. This is typically the first step in “playing by numbers”.

29.1.1 WhatAreGBNumbers[]

Aliases: None
Description: WhatAreGBNumbers[] returns a list of numbers. These numbers correspond to the elements of WhatIsHistory which determine what the ending relations are. If one computes Map[(#[[2]])&,WhatIsHistory[WhatAreGBNumbers[]]] then one gets the same result as WhatIsPartialGB[]
Arguments: None
Comments / Limitations: Not available before NCAlgebra 1.2

29.1.2 WhatAreNumbers[]

Aliases: None
Description: WhatAreNumbers[] returns a list of numbers. These numbers correspond to all of the polynomials which were used and retained inside the C++ code. One needs this command to make sense of the WhatIsHistory output. No argument is included because it can be applied only to the previous GB run.
Arguments: None
Comments / Limitations: Not available before NCAlgebra 1.2

29.1.3 WhatIsPartialGB[aListOfIntegers]

Aliases: None
Description: WhatIsPartialGB[aListOfIntegers] returns the polynomials corresponding to the entries in aListOfIntegers. The command WhatIsPartialGB[] is equivalent to WhatIsPartialGB[WhatAreGBNumbers[]].
Arguments: aListOfIntegers is a list of natural numbers.
Comments / Limitations: Not available before NCAlgebra 1.2. The list of integers does not have to be a subset of the integers in WhatAreGBNumbers[], it can also be a subset of the list of integers in WhatAreNumbers[]. In plain english this says that WhatIsPartialGB can retrieve any polynomial which has occurred in the course of running the last call to NCMakeGB (not just the output of NCMakeGB).

29.1.4 NumbersFromHistory[aPolynomial,history]

Aliases: None
Description: NumbersFromHistory[aPolynomial,history] returns all numbers n such that one of the elements of the list history has the form {n,aPolynomial,whatever,whatever2} where we do not care what the value of whatever or whatever2 is. Usually this function will return only a list with one integer in it.
Arguments: aPolynomial is a polynomial. history is the output from the command WhatIsHistory (subsection 29.2.1).
Comments / Limitations:

29.2 History of the production of a GB

29.2.1 WhatIsHistory[aListOfIntegers]

Aliases: None
Description: Applies to any List of Integers subset of the output of WhatAreNumbers[]. WhatIsHistory[ WhatAreNumbers[] ] lists the tree which produced the elements of the previous GB run. Also possible is WhatIsHistory[2,6,7] which will produce only relation numbers 2, 6, 7 and describe their immediate ancestors. It is handy if you already know that you are interested in 2, 6, 7.
Arguments: aListOfIntegers is a list of natural numbers.
Comments / Limitations: WARNING: The output to the command WhatIsHistory changes after every call to NCMakeGB. The command NCMakeGB is called during the run of the NCProcess commands (subsections 15.2.1) and the run of any of the variants of the SmallBasis command (subsections 21.1.1 and 21.1.2).

29.2.2 WhatIsKludgeHistory[aListOfIntegers]

Aliases: None
Description: WhatIsKludgeHistory[aListOfIntegers] returns the same output as WhatIsHistory[aListOfIntegers] except that second entry which is a polynomial in WhatIsKludgeHistory is much shorter (and is not a relation in the ideal) than WhatIsHistory. The point is to save time. Kludge History is generated inside of C++ and transferring it back into Mathematica takes much less time than the full history because transferring long polynomials into Mathematica takes a long time. Every polynomial in KludgeHistory lies in the same category as the polynomial it replaces in history. Thus, RemoveRedundentUseNumbers applies to KludgeHistory returns the same relation numbers as RemoveRedundentUseNumbers applied to history (if one uses the option).???
Arguments: None
Comments / Limitations: WARNING: The output to the command WhatIsHistory changes after every call to NCMakeGB. The command NCMakeGB is called during the run of the Spreadsheet commands (subsections 15.2.1) and the run of any of the variants of the SmallBasis command (subsections 21.1.1 and 21.1.2).

29.2.3 More on the History of how NCMakeGB produced its answer

We now continue with the demo from Subsection

In[14]:= WhatAreNumbers[]  
Out[14]= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}  
 
In[15]:= ColumnForm[ WhatIsHistory[Out[14]] ]  
Out[15]= {1, x ** x -> a, {0, 0}, {}}  
         {2, x ** y -> a, {0, 0}, {}}  
         {3, x ** y -> b, {0, 0}, {}}  
         {4, x ** x ** x -> b, {0, 0}, {}}  
         {5, x ** a -> a ** x, {1, 1}, {}}  
         {6, a ** y -> a ** x, {1, 2}, {5}}  
         {7, x ** b -> a ** x, {1, 3}, {6}}  
         {8, a ** x -> b, {1, 4}, {}}  
         {9, a ** a -> b, {1, 4}, {1, 7, 8}}  
         {10, b ** x -> b, {4, 1}, {1, 9}}  
         {11, b -> a, {2, 3}, {}}

We now describe what the above output means. Notice that each line is a number followed by a replacement rule followed by a pair of numbers followed by a list of zero or more numbers. The tuples mean
{relation number, relation, the 2 parents of thr relation, which rules relations were applied to the S-polynomial}

For example, we say that x**x a is the first replacement rule, x**y a is the second replacement rule,etc. The third entry is the two parents of rule There are two cases:

(Case: the third component is the pair {0,0}) When the pair {0,0} appears as the third component of list, the relations was provided as input to the NCMakeGB. In this case, the fourth list is always empty.
(Case: the third component is the pair {a,b} and a and b are positive) When the pair {a,b} appears as the third component of list, then the first step in constructing this rule comes from taking the S-polynomial of the ath and bth replacement rules. The last list of numbers indicates which replacement rules were applied to that S-polynomial in order to produce the relation.
(Case: the third component is the pair {-a,-a} and a is positive) The relation was generated using CleanUpBasis using the ath relation. The last list of numbers indicates which replacement rules were applied to this ath replacement rule to generate the present rule.

Note that one can use history to do two things. The first thing is to see how relations are derived. The second is to find a smaller subset of the relations mentioned which will generate the same ideal. Note that in the above example, x**a-a**x lies in the ideal generated by x**x-a can be seen by referring to only the above history. Also, note that one can see that a **y - a **x lies in the ideal generated by {x **x - a, x **y - a and x **a - a **x}. This will prove very helpful in finding a subset of a particular set of a generated relations R which generates the same ideal as R. (See Section 30).

29.2.4 The DAG associated with a History

Consider the following tree on the nodes {2,3,6,7,8,9}.

PICT

Let us suppose that this tree represents the history corresponding to {p2,p3,p6,p7,p8,p9}. That is, p8 is generated as an s-polynomial from p6 and p7, p6 is generated as an S-polynomial from p7 and p9 and p7 is generated as a reduced S-polynomial. The polynomial generated is from p3 and p9 and a reduction step using p2 was used. In the notation of the history output, this would take the form

{  
{2,p_2,{0,0},{}},  
{3,p_3,{0,0},{}},  
{6,p_6,{7,9},{}},  
{7,p_7,{3,9},{2}},  
{8,p_8,{6,7},{}},  
{9,p_9,{0,0},{}},  
}

One sees from the picture that

(1) p8 ∈p6,p7
(2) p6 ∈p7,p9
(3) p6 ∈p3,p2,p9
(4) p7 ∈p3,p2,p9
(5) p8 ∈p6,p3,p2,p9
(6) p8 ∈p7,p9
(7) p8 ∈p7,p3,p2,p9
(8) p8 ∈p3,p2,p9