Skew polynomial rings, Groebner bases and the letterplace embedding of the free associative algebra

Abstract

In this paper we introduce an algebra embedding $\iota :K<X>\to S$ from the free associative algebra $K<X>$ generated by a finite or countable set $X$ into the skew monoid ring $S=P\ast \Sigma$ defined by the commutative polynomial ring $P=K[X\times N^{\ast }]$ and by the monoid $\Sigma =<\sigma >$ generated by a suitable endomorphism $\sigma :P\to P$. If $P=K[X]$ is any ring of polynomials in a countable set of commuting variables, we present also a general Gröbner bases theory for graded two-sided ideals of the graded algebra $S={⨁}_i{S}_i$ with $S_i=P{\sigma }^i$ and $\sigma :P\to 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 Gröbner 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 Gröbner bases theories for commutative and non-commutative polynomial rings. Finally, since the ring of ordinary difference polynomials $P=K[X\times N]$ fits the proposed theory one obtains that, with respect to a suitable grading, the Gröbner 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.

arXiv comment27 pages, to appear in Journal of Symbolic Computation