5 Groebner Basis

This chapter contains the declarations and implementations needed for Groebner basis. Currently, we do not provide algorithms to actually compute Groebner basis; instead, the declarations and implementations are provided here for **GAP** objects and the actual elements of Groebner basis are computed by the **GBNP** package.

`‣ InfoGroebnerBasis` | ( info class ) |

is the info class for functions dealing with Groebner basis.

`‣ GroebnerBasis` ( I, rels ) | ( operation ) |

Arguments: `I` -- an ideal, `rels` -- a list of relations generating `I`.

Returns: an object `GB` in the `IsGroebnerBasis`

(5.2-3) category with `IsCompleteGroebnerBasis`

(5.2-2) property set on true.

Sets also `GB` as a value of the attribute `GroebnerBasisOfIdeal`

(4.10-1) for `I` (so one has an access to it by calling GroebnerBasisOfIdeal(`I`)).

There are absolutely no computations and no checks for correctness in this function. Giving a set of relations that does not form a Groebner basis may result in incorrect answers or unexpected errors. This function is intended to be used by packages providing access to external Groebner basis programs and should be invoked before further computations on Groebner basis or ideal I (cf. also `IsCompleteGroebnerBasis`

(5.2-2)).

`‣ IsCompletelyReducedGroebnerBasis` ( gb ) | ( property ) |

Arguments: `GB` -- a Groebner basis.

Returns: true when `GB` is a Groebner basis which is completely reduced.

`‣ IsCompleteGroebnerBasis` ( gb ) | ( property ) |

Arguments: `GB` -- a Groebner basis.

Returns: true when `GB` is a complete Groebner basis.

While philosophically something that isn't a complete Groebner basis isn't a Groebner basis at all, this property can be used in conjuction with other properties to see if the the Groebner basis contains enough information for computations. An example of a system that creates incomplete Groebner bases is `Opal'.

*Note:* The current package used for creating Groebner bases is **GBNP**, and this package does not create incomplete Groebner bases.

`‣ IsGroebnerBasis` ( object ) | ( category ) |

Arguments: `object` -- any object in **GAP**.

Returns: true when `object` is a Groebner basis and false otherwise.

The function only returns true for Groebner bases that has been set as such using the `GroebnerBasis`

function, as illustrated in the following example.

`‣ IsHomogeneousGroebnerBasis` ( gb ) | ( property ) |

Arguments: `GB` -- a Groebner basis.

Returns: true when `GB` is a Groebner basis which is homogenous.

gap> Q := Quiver( 3, [ [1,2,"a"], [2,3,"b"] ] ); <quiver with 3 vertices and 2 arrows> gap> PA := PathAlgebra( Rationals, Q ); <Rationals[<quiver with 3 vertices and 2 arrows>]> gap> rels := [ PA.a*PA.b ]; [ (1)*a*b ] gap> gb := GBNPGroebnerBasis( rels, PA ); [ (1)*a*b ] gap> I := Ideal( PA, gb ); <two-sided ideal in <Rationals[<quiver with 3 vertices and 2 arrows>]> , (1 generators)> gap> grb := GroebnerBasis( I, gb ); <complete two-sided Groebner basis containing 1 elements> gap> alg := PA/I; <Rationals[<quiver with 3 vertices and 2 arrows>]/ <two-sided ideal in <Rationals[<quiver with 3 vertices and 2 arrows>]> , (1 generators)>> gap> IsGroebnerBasis(gb); false gap> IsGroebnerBasis(grb); true

`‣ IsTipReducedGroebnerBasis` ( gb ) | ( property ) |

Arguments: `GB` -- a Groebner Basis.

Returns: true when `GB` is a Groebner basis which is tip reduced.

`‣ AdmitsFinitelyManyNontips` ( GB ) | ( operation ) |

Arguments: `GB` -- a complete Groebner basis.

Returns: true if the Groebner basis admits only finitely many nontips and false otherwise.

`‣ CompletelyReduce` ( GB, a ) | ( operation ) |

Arguments: `GB` -- a Groebner basis, `a` -- an element in a path algebra.

Returns: `a` reduced by `GB`.

If `a` is already completely reduced, the original element `a` is returned.

`‣ CompletelyReduceGroebnerBasis` ( GB ) | ( operation ) |

Arguments: `GB` -- a Groebner basis.

Returns: the completely reduced Groebner basis of the ideal generated by `GB`.

The operation modifies a Groebner basis `GB` such that each relation in `GB` is completely reduced. The `IsCompletelyReducedGroebnerBasis`

and `IsTipReducedGroebnerBasis`

properties are set as a result of this operation. The resulting relations will be placed in sorted order according to the ordering of `GB`.

`‣ Enumerator` ( GB ) | ( operation ) |

Arguments: `GB` -- a Groebner basis.

Returns: an enumerat that enumerates the relations making up the Groebner basis.

These relations should be enumerated in ascending order with respect to the ordering for the family the elements are contained in.

`‣ IsPrefixOfTipInTipIdeal` ( GB, R ) | ( operation ) |

Arguments: `GB` -- a Groebner basis, `R` -- a relation.

Returns: true if the tip of the relation `R` is in the tip ideal generated by the tips of `GB`.

This is used mainly for the construction of right Groebner basis, but is made available for general use in case there are other unforseen applications.

`‣ Iterator` ( GB ) | ( operation ) |

Arguments: `GB` -- a Groebner basis.

Returns: an iterator (in the IsIterator category, see the **GAP** manual, chapter 28.7).

Creates an iterator that iterates over the relations making up the Groebner basis. These relations are iterated over in ascending order with respect to the ordering for the family the elements are contained in.

`‣ Nontips` ( GB ) | ( attribute ) |

Arguments: `GB` -- a Groebner basis.

Returns: a list of nontip elements for `GB`.

In order to compute the nontip elements, the Groebner basis must be complete and tip reduced, and there must be a finite number of nontips. If there are an infinite number of nontips, the operation returns `fail'.

`‣ NontipSize` ( GB ) | ( operation ) |

Arguments: `GB` -- a complete Groebner basis.

Returns: the number of nontips admitted by `GB`.

`‣ TipReduce` ( GB, a ) | ( operation ) |

Arguments: `GB` -- a Groebner basis, `a` - an element in a path algebra.

Returns: the element `a` tip reduced by the Groebner basis.

If `a` is already tip reduced, then the original `a` is returned.

`‣ TipReduceGroebnerBasis` ( GB ) | ( operation ) |

Arguments: `GB` -- a Groebner basis.

Returns: a tip reduced Groebner basis.

The returned Groebner basis is equivalent to `GB` If `GB` is already tip reduced, this function returns the original object `GB`, possibly with the addition of the `IsTipReduced`' property set.

In this section we support right Groebner basis for two-sided ideals with Groebner basis. More general cases may be supported in the future.

`‣ IsRightGroebnerBasis` ( object ) | ( property ) |

Arguments: `object` -- any object in **GAP**.

Returns: true when `object` is a right Groebner basis.

`‣ RightGroebnerBasis` ( I ) | ( operation ) |

Arguments: `I` -- a right ideal.

Returns: a right Groebner basis for `I`, which must support a right Groebner basis theory. Right now, this requires that `I` has a complete Groebner basis.

`‣ RightGroebnerBasisOfIdeal` ( I ) | ( attribute ) |

Arguments: `I` -- a right ideal.

Returns: a right Groebner basis of a right ideal, `I`, if one has been computed.

generated by GAPDoc2HTML