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