1. Introduction

Let $\mathbb {Z}[{\cal M}]$ be a monoid ring over the integers $\mathbb {Z}$. Further let the monoid ${\cal M}$ have a presentation by a finite convergent string rewriting system $(\Sigma, T)$, i.e. the representatives of the elements are words on $\Sigma$ and the word problem is decidable by normal form computation.

We show that for $f_1, \ldots, f_k \in \mathbb {Z}[{\cal M}]$ the linear inhomogeneous equation $f_1 \ast X_1 + \ldots + f_m \ast X_m = f_0$ in the variables $X_1, \ldots, X_m$ has a finite generating set of solutions in case the reduced prefix Gröbner basis of the right ideal generated by $\{ f_1, \ldots, f_m \}$ is finite and how a generating set for the solutions can be obtained. A solution for this problem in the case that ${\cal M}$ is a free monoid can be found in [1]. Starting from this approach a solution for other monoid rings is provided. While in the case of free monoids, finite prefix Gröbner bases for finitely generated right ideals always exist, this is no longer the case for arbitrary monoid rings. Therefore, we stress that the approach presented here only applies to those cases, where a finite prefix Gröbner basis exists (in the conclusions we give an outlook to more general cases). Moreover, the set of generating solutions derived from the prefix Gröbner bases in the free monoid case is not sufficient for arbitrary monoid rings. We will show why and enlarge the generating set of solutions. These additional solutions correspond to the situations which are characterized by the concept of saturation when computing Gröbner bases in monoid rings. It is outlined how this approach extends to systems of linear equations. A similar result can be shown for systems of left homogeneous equations using suffix Gröbner bases. Of course prefix reduction is a very restricted reduction relation when studying a monoid ring. If for example the monoid ring is commutative in general no finite prefix Gröbner bases will exist and hence the approach outlined here will not work. Still for many classes of monoids and groups finite Gröbner bases can be computed when using appropriate reduction relations (see e.g. [5] for an overview). We show how for these cases the approach can be adopted yielding that finite generating sets for systems of inhomogeneous equations can be constructed for finitely generated commutative monoid rings and finitely generated group rings for the classes of free groups, plain groups, and polycyclic groups.

The paper is organized as follows: Since the results presented here involve the theory of prefix Gröbner bases in monoid rings, Section 5 provides a rough overview of this field for readers not familiar with the topic. More details and leads to additional literature can be found in [5]. In Section 2 we show how Baader's results from [1] for solving one inhomogeneous equation can be extended to arbitrary monoid rings fulfilling our assumptions. We outline why additional solutions have to be defined. In Section 3 we show how this approach can be applied to characterize solutions of systems of inhomogeneous equations. In Section 4 we outline how this approach also works for certain group rings where finite Gröbner bases exist with respect to appropriate reduction relations.