NON-COMMUTATIVE POLYNOMIAL COMPUTATIONS

These notes describe some of the key algorithms for non-commutative polyno-mial rings. They are intended for the Masterclass Computer algebra, Spring 2007. Together with a paper on Knuth-Bendix, they provide the reading material for the eleventh lecture. 1. Gröbner bases In [6] Mora described an algorithm which, if it terminates, returns a non-commutative Gröbner basis. Here we follow that paper to prove the correctness of the algorithm as implemented by Die ́ Gijsbers and the author in GAP, cf. [1]. The algorithm is the core algorithm of the GAP package GBNP for computing with non-commutative polynomials. Earlier versions of this section were written with the help of Die ́ Gijsbers. 1.1. Basic notions. We start with some definitions and lemmas inspired by [6]. We work with finitely presented algebras with a unit element 1 over a field k. Let T be the free monoid on n generators, which will be denoted by x1,..., xn. Here n is a natural number. We consider the monoid ring k〈T 〉, which has an obvious k-vector space structure with basis T. The multiplication of the monoid ring is a bilinear extension of the multiplication in T, so T is a monomial basis. The elements of T are also called the monomials of k〈T 〉. The elements of k〈T 〉 are called non-commutative polynomials, and often just polynomials. As usual in Gröbner basis theory, we need an appropriate ordering ’< ’ on the set T of monomials. Definition 1. An ordering < on T is called a reduction ordering if for all t1, t2, l, r ∈ T with t1 < t2 we have 1 ≤ lt1r < lt2r. An example of a reduction ordering is the ’total degree first, then lexicographic’ ordering. A very useful property of a reduction ordering is that if a, b ∈ T are such that a divides b, denoted by a | b (that is, there are l, r ∈ T with b = lar), then a ≤ b (for, 1 ≤ l and 1 ≤ r imply a = 1 a ≤ l a = l a 1 ≤ l a r). Definition 2. Given an ordering on T we can write each polynomial f ∈ k〈T 〉 in a unique way as a linear combination of monomials ti: f = s∑ i=1 citi with ci ∈ k \ {0} and ti ∈ T, such that t1> · · ·> ts. We call this decomposition the ordered form of f. The polynomial f is called monic if c1 = 1