Skew polynomial rings, Grobner bases and the letterplace embedding of the free associative algebra
In this paper we introduce an algebra embedding iota : K   -> S from the free associative algebra K   generated by a finite or countable set X into the skew monoid ring S = P * Sigma defined by the commutative polynomial ring P = K[X x N*] and by the monoid Sigma = (sigma) generated by a suitable endomorphism sigma : P -> P. If P = K[X] is any ring of polynomials in a countable set of commuting variables, we present also a general Grobner bases theory for graded two-sided ideals of the graded algebra S = circle plus S-i(i) with S-i = P sigma(i) and sigma : P -> P an abstract endomorphism satisfying compatibility conditions with ordering and divisibility of the monomials of P. Moreover, using a suitable grading for the algebra P compatible with the action of Sigma, we obtain a bijective correspondence, preserving Grobner bases, between graded Sigma-invariant ideals of P and a class of graded two-sided ideals of S. By means of the embedding iota this results in the unification, in the graded case, of the Grobner bases theories for commutative and non-commutative polynomial rings. Finally, since the ring of ordinary difference polynomials P = K[X x N] fits the proposed theory one obtains that, with respect to a suitable grading, the Grobner bases of finitely generated graded ordinary difference ideals can be computed also in the operators ring S and in a finite number of steps up to some fixed degree. (C) 2012 Elsevier B.V. All rights reserved.
skew polynomial rings grobner bases free algebras