## Chapter 20Commands for Making and Using GB’s

This section contains a glossary of commands available for generating and using non-commutative Gröbner Basis.

### 20.1 Simplification

Before using these commands, a monomial order must be specified. See the section after this for information on how to set the monomial order.

#### 20.1.1 NCSimplifyAll[expressions, startRelations, iterations]

Aliases: GroebnerSimplify, NCGroebnerSimplify
Description: NCSimplifyAll[expressions, startRelations, iterations] calls NCMakeGB[startRelations, iterations] and uses the result to reduce the expressions in expressions. This is useful when the form the Gröbner Basis is irrelevant and is only used to simplify some set of predetermined equations.
Arguments: exprs can be either an expression or a list of expressions. startRelations is a list of polynomials. iterations is a positive integer.
Comments / Limitations: Not available before NCAlgebra 1.2

#### 20.1.2 NCSimplifyRationalX1[expressions, startRelations, iterations]

Aliases: None
Description: NCSimplifyRationalX1[expressions, startRelations, iterations] is (essentially) equivalent to
NCSimplifyAll[expressions, Join[startRelations, inverses], iterations]
where inverses is a list of polynomials. inverses consists of the defining relations of all inverses (elements with inv[...]) in expressions and startRelations. NCSimplifyRationalX1 simplifies expressions with startRelations together with some additional innocuous relations.
NCSimplifyRationalX1 is different from NCSimplifyAll with the following adjustment: first all instances of inv are converted to Inv before calling NCSimplifyAll, and are converted back afterwards. This overrides NCAlgebra’s automatic handling of inverses. For example, the command
NCSimplifyRationalX1[{inv[x] **inv[1 - x] + y},{z **inv[y] - a}, 10]
equals
NCSimplifyAll[{Inv[x]**Inv[1-x]+y},{z**Inv[y]-a,y**Inv[y]-1,Inv[y]**y- 1,Inv[x]**x-1,x**Inv[x]-1, (1-x)**Inv[1-x]-1,Inv[1-x]**(1-x)-1}, 10].
This call to NCSimplifyAll returns Inv[x] + Inv[1-x] + y. The call to NCSimplifyRationalX1 returns inv[x] + inv[1-x] + y.
Arguments: expressions is a list of polynomials. startRelations is a list of polynomials. iterations is a natural number.
Comments / Limitations: Not available before NCAlgebra 1.2.

### 20.2 Making a Gröbner Basis and various options (with their defaults)

Before using any of these commands, you must set a monomial order. See Chapter 18.

#### 20.2.1 NCMakeGB[aListOfPolynomials, iterations]

Aliases: NCMakeRules, MorasAlgorithm
Description: The GB algorithm proceeds through at most iterations iterations until a Gröbner basis is found for the list of polynomials aListofPolynomials with respect to the order imposed by SetMonomialOrder, see §18.5.1. NCMakeGB calls a C++ program and while the C++ program is running, it prints intermediate lists of rules to the screen. When the C++ program finishes, it is either because it has run iterations number of iterations or it has found a Gröbner Basis. If it has found a Gröbner Basis, it prints a message saying so. One may also use the command FinishedComputingBasisQ[] in §20.2.5. The Mathematica output of NCMakeGB is a list of polynomials.

The following computes the Gröbner basis for the ideal generated by x2 -a and x3 -b.
For options which can be used inside NCMakeGB, see ReturnRelationsToMma, SupressCOutput??, SupressAllCOutput??, UserSelect and Deselect -DISABLED.
Arguments: aListofPolynomials is a list of polynomials. iterations is a natural number.
Comments / Limitations: Not available before NCAlgebra 1.2

#### 20.2.2 UserSelect→{}(Distinguishing important relations)

Aliases: None
Description: UserSelect is an option for NCMakeGB and for Spreadsheet. If UserSelectaListOfPolynomials is given as an option, then the main effect is on the display produced by RegularOuput throughout the rest of the session. UserSelect is cumulative and more and more polynomials fall into the selected category as the user puts them in. The command RegularOutput automatically scans for selected polynomials to display in the collection of relations labelled USER SELECTS. It finds them only after NCMakeGB has been run with the user selects (since RegularOutput searches for the selected polynomials by there number. Henceforth, aListOfPolynomials is displayed as a special category. The default value is {}.
Arguments: None
Comments / Limitations: Not available before NCAlgebra 1.2

#### 20.2.3 ClearUserSelect[]

Aliases: None
Description: Clears the UserSelected polynomials, that is, it makes the USER SELECTED empty
Arguments: None
Comments / Limitations: Not available before NCAlgebra 1.2

#### 20.2.4 Deselect→{} (DISABLED)

Aliases: None
Description: Deselect is an option for NCMakeGB. If DeSelectPolyaListOfPolynomials is given as an option for NCMakeGB, then certain S-polynomials will not be computed. Specifically, no S-polynomial will be formed between two deselected polynomials. Deselect is NOT cumulative. The default value is {}.
Arguments: None
Comments / Limitations: Not available before NCAlgebra 1.2. Bug: Only the deselected polynomials which are also members of the first argument for NCMakeGB are deselected.

#### 20.2.5 FinishedComputingBasisQ[] - Untested in 1999

Aliases: None
Description: FinishedComputingBasisQ[] returns 0 or 1. If it returns 1, then NCMakeRules stopped because it obtained a Gröbner Basis. If it returns 0, then NCMakeRules stopped because it ran the maximal number of iterations and did not find a Gröbner Basis.
Arguments: None
Comments / Limitations: Not available before NCAlgebra 1.2

.

#### 20.2.6 WhatIsPartialGB[]

Aliases: None
Description: Since we do not require GB algorithm to run until it obtains a Gröbner Basis, the output of the algorithm need not be a Gröbner Basis. We call the output of the algorithm a partial basis. WhatIsPartialGB[] returns a list of all of the elements in the partial groebner basis. See PartialBasis[n].
Arguments: None

#### 20.2.7 NCGBSetIntegerOverflow[False]

Aliases: None
Description: An MakeNCGB and NCProcess command which if set True permits large integers to be handled carelessly by C + +. This is dangerous since it causes mistakes when you see large integers (at about 2 billion watch out). The code runs faster with this setting, but still for saftey sake the default is NCGBSetIntegerOverflow[False].
Arguments: None

#### 20.2.8 PartialBasis[aNumber] - Untested in 1999

Aliases: None
Description: PartialBasis[aNumber] (where aNumber is a positive integer) returns a character string. If this character string is input to the built-in Mathematica command ToExpression, then the result is the aNumber-th element of the partial basis data base.
Arguments: aNumber is a natural number.
Comments / Limitations: Not available before NCAlgebra 1.2. See also 29.1.3. Note: aNumber does not correspond to the numbers generated from the WhatIsHistory command.

#### 20.2.9 IterationNumber[aList] or IterationNumber[ aNumber ] - UNTESTED 1999

Aliases: None
Description: It might be interesting to find out which relations are generated during which iteration of the algorithm. The command IterationNumber returns these numbers. The most common applications of this command will probably be IterationNumber[WhatAreGBNumbers[]] and IterationNumber[WhatAreNumbers[]].
Arguments: aList is a list of integers. aNumber is an integer
Comments / Limitations: Not available before NCAlgebra 1.2.

#### 20.2.10 CleanUp

Aliases: None
Description: CleanUp 1
Arguments: NCProcess and NCMakeGB Option which controls the reduction step inside Mora’s GB algorithm. When set to 1 the new S- polynomials reduce the current set of relations. When CleanUp 0 they do not.

#### 20.2.11 SetCleanUpBasis[n] - Untested in 1999

Aliases: None
Description: If n is nonzero (best to use n=1), SetCleanUpBasis [n] indicates that the program used to implement NCCleanUpRules should be applied after each iteration of the GB algorithm. SetCleanUpBasis[0] indicates that such additional processing should not be done.
Arguments: n is an integer
Comments / Limitations: Not available before NCAlgebra 1.2

#### 20.2.12 CleanUpBasisQ[] - Untested in 1999

Aliases: None
Description: CleanUpBasisQ[] returns the argument of the SetCleanUpBasis command the last time it was used.
Arguments: None
Comments / Limitations: Not available before NCAlgebra 1.2. This allows one to see which “cleaning” option is in force.

#### 20.2.13 History Off

NCGB has the ability to track the history of GB production. This is used when the RemoveRedundant Options are turned on in NCProcess. Since much storage is consumed by this history it is often advantageous to turn it off. If you are just running NCMakeGB and you want to turn it off do this.

The command

SetRecordHistory[False]

turns off the history collection, except that it replaces useless rules which the code produced by the one dummy rule

InvalidHistoryRule 0

The command

SetRecordHistory[True]

turns on the history collection.

If you happen to bring an InvalidHistoryRule 0 back into Mma, either

a) InvalidRuleHistory is not a member of the order (as expected) and an error message is printed and then is reformatted as 1 0 OR

b) InvalidRuleHistory is (artificially) a member of the order and one gets InvalidHistoryRule 0.

#### 20.2.14 Correspondence to sections ‘Simplification’ and ‘Reduction’

This subsection is a brief note to bring out the conceptual connection between making a Gröbner Basis and the simplification commands and the Reduction commands. Making a Gröbner Basis is the first step in the simplification commands presented above. Making a Gröbner Basis is also the main step in the the command SmallBasis in §21.1.1 and Spreadsheet in §15.2.1.

#### 20.2.16 ReinstateOrder[]

Aliases: None
Description: After a call to SetGlobalPtr[], ClearMonomialOrde r[] or ClearMonomialOrderN[n], ReinstateOrder[] is used to restore the previously established order of indeterminates. The exception is C learOrder[]. After this function is called, the order cannot be restored.
Arguments: None
Comments / Limitations: Not available before NCAlgebra 1.2.

### 20.3 Reduction

#### 20.3.1 Reduction[aListOfPolynomials, aListOfRules]

Aliases: None
Description: Reduction[aListOfPolynomials, aListOfRules] computes the Normal Forms of aListOfPolynomials with respect to the rules aListOfRules.
Arguments: aListOfPolynomials is a list of polynomials. aListOfRules is a list of rules. That is the rules are applied repeatedly to the polynomials in the list until no further reduction occurs
Comments / Limitations: Not available before NCAlgebra 1.2

#### 20.3.2 PolyToRule[aPolynomial]

Aliases: PolToRule,ToGBRule,ToGBRules
Description: PolyToRule[aPolynomial] returns the replacement rule corresponding to aPolynomial, assuming the order of monomials has been set.
Arguments: aPolynomial is a polynomial
Comments / Limitations: Not available before NCAlgebra 1.2

#### 20.3.3 RuleToPoly[aRule]

Aliases: None
Description: RuletoPoly[aRule] returns aPolynomial corresponding to the replacement rule aRule.
Arguments: aPolynomial is a polynomial
Comments / Limitations: Not available before NCAlgebra 1.2