The Ideal Membership Problem in Non-Commutative Polynomial Rings

✍ Scribed by F.LEON PRITCHARD

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 689 KB
• Volume: 22
• Category: Article
• ISSN: 0747-7171
• DOI: 10.1006/jsco.1996.0040

✦ Synopsis

Let X be a non-commutative monoid with term order; let R be a commutative, unital ring; let I be an ideal in the non-commutative polynomial ring R X ; and let f ∈ R X . In this setting the problem of determining whether f ∈ I is studied. In a manner analogous to the commutative case, see , weak Gröbner bases are defined and their basic properties are studied. We will see that in the non-commutative setting, when the coefficient ring is not a field, and when we enlarge the polynomial ring by adding more variables, weak Gröbner bases may exhibit unpleasant behavior that has no analog in the commutative case. Quite in general for f ∈ R X , it is undecidable whether f ∈ I. This follows from the fact that the word problem for free semigroups is undecidable. If I is generated by a recursively enumerable set, then we give a semidecision procedure that halts if and only if f ∈ I. Finally we examine a class of nicely behaved ideals for which weak Gröbner bases can be easly computed.