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 Grobner bases. In this way, we obtain a new method for computing non-commutative homogeneous Grobner 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 Grobner 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 Grobner bases from classical algorithms.

Letterplace ideals and non-commutative Groebner bases

LA SCALA, Roberto;
2009

Abstract

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 Grobner bases. In this way, we obtain a new method for computing non-commutative homogeneous Grobner 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 Grobner 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 Grobner bases from classical algorithms.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11586/11610
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 23
  • ???jsp.display-item.citation.isi??? 20
social impact