Letterplace ideals and non-commutative Gröbner bases

In this paper we propose a 1-to-1 correspondence between graded two-sided ideals of the free associative algebra and some class of ideals of the algebra of polynomials, whose variables are double-indexed commuting ones. We call these ideals the “letterplace analogues” of graded two-sided ideals. We...

Full description

Saved in:
Bibliographic Details
Published in:Journal of symbolic computation 2009-10, Vol.44 (10), p.1374-1393
Main Authors: La Scala, Roberto, Levandovskyy, Viktor
Format: Article
Language:English
Subjects:
Free associative algebras
Gröbner bases
Invariant ideals
Monoid action
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper we propose a 1-to-1 correspondence between graded two-sided ideals of the free associative algebra and some class of ideals of the algebra of polynomials, whose variables are double-indexed commuting ones. We call these ideals the “letterplace analogues” of graded two-sided ideals. We study the behaviour of the generating sets of the ideals under this correspondence, and in particular that of the Gröbner bases. In this way, we obtain a new method for computing non-commutative homogeneous Gröbner bases via polynomials in commuting variables. Since the letterplace ideals are stable under the action of a monoid of endomorphisms of the polynomial algebra, the proposed algorithm results in an example of a Buchberger procedure “reduced by symmetry”. Owing to the portability of our algorithm to any computer algebra system able to compute commutative Gröbner bases, we present an experimental implementation of our method in Singular. By means of a representative set of examples, we show finally that our implementation is competitive with computer algebra systems that provide non-commutative Gröbner bases from classical algorithms.
ISSN:0747-7171
1095-855X
DOI:10.1016/j.jsc.2009.03.002