Next: The need to consider Up: Theory and more details Previous: A Gröbner Basis Theorem

# Finding a small generating set for an ideal

A principal part of the NCProcess commands is the use of the Gröbner Basis algorithm. A Gröbner Basis can be infinite and even when a Gröbner Basis is finite, it can be very large. One often finds that there are many polynomial equations which are generated which do not enhance our understanding of the mathematics. We begin with an example.

Example 12.1 The GB generated by the set {P T P - T P, P² - P} is the set regardless of the term order used. No smaller GB exists.

Here just two polynomials equations generate infinitely many. One way to view this example is that the computer discovers that if the range of P is invariant for a linear transformation T, then it is invariant for for every . The GBA tries to generate this infinite set of polynomial equations and, at any time, has generated a finite subset of them. Since the NCProcess commands are used in the discovery of theorems (as described in Part I), it would not be helpful to display , for n in a large set of natural numbers, on the spreadsheet, since these equations are mathematically and conceptually redundant. Indeed, one would not choose to state, either as a hypothesis or as a conclusion to a theorem, that the range of P is invariant for for all , since the equivalent statement that the range of P is invariant for T would suffice.

This introduces the next topic which is shrinking a set of polynomial equations 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 GBA. Also we point out that our examples in Part I used shrinking of the type described here heavily and that the undigested polynomial equations in the spreadsheets survived the deleting of many polynomial equations from a partial GB.

To be more precise, in many cases, we would like to compute a minimal length generating set for an ideal (that is, given an ideal , a minimal length generating set for the ideal would be a set Y such that every generating set for has cardinality equal to or greater than the cardinality of Y). Determining an algorithm for finding a minimal length generating set for an ideal is an open problem for commutative polynomial rings and is probably unsolvable in the noncommutative case.

We say that a set of polynomials X is a minimal generating set if no proper subset of X generates . A more practical goal is to try to find, given a finite set X of polynomials, a minimal generating subset of X (that is, a subset Y of X which generates the same ideal which X generates and which is a minimal generating set).

In the case of ideals of a commutative polynomial ring, it is well known that every minimal generating subset of a given set of polynomials can be found. In fact, one approach to finding such minimal generating subsets would be to use an algorithm based upon using reduction and using a finite number of runs of the Gröbner Basis Algorithm. Since the Gröbner Basis Algorithm is guaranteed to finish in a finite amount of time, one can compute minimal generating subsets.

In contrast to the case of commutative polynomial rings, for an ideal of a noncommutative polynomial ring, there does not exist an algorithm which can, given a finite set X of polynomials, construct every minimal generating subset of X. We prove this assertion in the following lemma.

Lemma 12.2 There does not exist an algorithm which can, in every case, given a finite set X of polynomials, construct every minimal generating subset of X.

Proof. \ Suppose that one could write such an algorithm. Given a finite set X and a polynomial p, one could use this hypothetical algorithm to find a minimal generating subset Y of X. By using this hypothetical algorithm again, we can find a and find the minimal generating subsets of . Note that no could be a proper subset of Y. With this set up, p is a member of the ideal generated by X if and only if one of the equals Y. Therefore, if such a hypothetical algorithm existed, then one could solve the membership problem for finitely generated ideals of noncommutative polynomial rings. The membership problem for noncommutative polynomial rings is known to be unsolvable ([TMora]). height4pt width4ptdepth0pt

For the case of commutative polynomial rings, one can always find a minimal generating set. To see this, let us say that a set of polynomials F is reduced if f is irreducible with respect to for every and the F is a reduced Gröbner Basis if F is a Gröbner Basis and F is reduced. If G is a reduced Gröbner Basis, then the only minimal generating subset of G is G.

A natural question to ask is if, in the setting of noncommutative polynomial rings, whether or not a reduced Gröbner Basis is a minimal generating set. This is not the case, as can be seen in Example 12.1. Thus, from a purely mathematical point of view, one natural generalization of a commutative reduced Gröbner Basis is a minimal generating subset of a reduced Gröbner Basis (even though this minimal generating subset is not itself a GB).

Next: The need to consider Up: Theory and more details Previous: A Gröbner Basis Theorem

Helton
Wed Jul 3 10:27:42 PDT 1996