next up previous contents
Next: Preview of operations Up: Finding a small generating Previous: Finding a small generating

The need to consider small generating sets

Lemma 12.2 shows that, for noncommutative polynomial rings, it is in general algorithmically impossible to compute minimal generating subsets. Therefore, we content ourselves with finding small generating subsets rather than minimal generating subsets. We now show that even if we could find minimal generating subsets, we would not necessarily want to compute them.

In a strategy, it is often the case that equations with no unknowns are the basic compatibility conditions for the problem being considered. Thus some redundancy, redundancy which promotes the retaining of equations with no unknowns, can be helpful. The next two example illustrate this. The first example shows that it is not always desirable to find a minimal generating set. The second example shows that, when seeking a generating set, it is helpful to direct ones search so that one keeps all equations which do not involve any unknowns. This is described further in §.

The following example shows that, when given a set X, one does not always want the smallest subset of X which generates the same ideal.

Example 12.3 Consider the case of the spreadsheet following equation §. That spreadsheet contained the following polynomials.


There is only one proper subset of the polynomials listed above which generates the same ideal. That subset consists of the above list of polynomials with example3247 removed. It would, however, be a tactical mistake to remove this polynomial since it reveals important information about the known P, namely that it is idempotent. This information can be derived, of course, from the remaining equations, but it is preferablel for it to be shown explicitly.

In addition, there are cases when it is not advantageous to find an arbitrary minimal generating set, but a specific minimal generating with certain properties is desired. Consider the following example.

Example 12.4 Suppose that A and P are known and that m and n are unknown. Let X be the set {PAP-AP, P-mn, nAmn-Amn, nm-1}. There are two minimal subsets or X which generate the same ideal as X. These subsets are {PAP-AP, P-mn, nm-1} and {P-mn, nAmn-Amn, nm-1}. Clearly, the first minimal generating set is preferable to the second since the first contains the polynomial PAP-AP which involves only knowns.

Wed Jul 3 10:27:42 PDT 1996