Gröbner bases for ideals in Laurent polynomial rings and their application to systems of difference equations (Q1290507)

A Gröbner basis for an ideal of the commutative ring of Laurent polynomials \(R[x,x^{-1}]: =R[x_1,\dots, x_n,x_1^{-1}, \dots,x_n^{-1}]\) over a field \(R\) can be computed via a factor algebra. However, this paper presents a direct method using generalized term orders and allows \(R\) to be a commutative Noetherian ring (provided linear equations over \(R\) can be solved). The problem over \(\mathbb{Z}\) was first considered by \textit{C. Sims} [``Computation with finitely presented groups'' (1994; Zbl 0828.20001)] and the present approach extends an idea of \textit{F. Pauer} and \textit{S. Zampieri} [J. Symb. Comput. 21, 155-168 (1996; Zbl 0869.39001)]. Let \(\Gamma\) be an index set and \(R^{(\Gamma)}\) the \(R\)-submodule of all maps from \(\Gamma\) to \(R\) with finite support. The paper defines a triangular basis for a submodule \(W\) of \(R^{(\Gamma)}\) and shows how it may be used to solve a system of linear partial difference equations over \(\mathbb{Z}^n\) by computing a Gröbner basis for \(W\), as first introduced by \textit{W. Oberst} [Acta Appl. Math. 20, 1-175 (1990; Zbl 0715.93014)]. Let \(T\) be a finitely generated submonoid of the group \(\{x^i\mid i\in\mathbb{Z}^n\}\) of power-products in \(R[x,x^{-1}]\). A conic decomposition of \(T\) is essentially a partition into ``conical'' regions with vertex at the identity element. This notion is used to define a generalized term order on \(U:=\{tb \mid t\in T,b\in B\}\), where \(B\) is a basis for a finite-dimensional free \(R[T] \)-module \(V\), and it is shown how to construct a generalized term order on \(T\) and on \(U\). Various concepts that depend on term order are defined, such as leading term (lt), leading coefficient (lc) and leading monomial (lm). Now a generalized Gröbner basis can be defined. Let \(W\) be an \(R[T]\)-submodule of \(V\) and let \(G\) be a finite subset of \(W\setminus \{0\}\). Then \(G\) is a Gröbner basis of \(W\) (with respect to conic decompositions \((T_i)_{i\in i}\) of \(T\) and \((U_i)_{i\in I}\) of \(U\), and a generalized term order \(<\) on \(U\)) iff for all \(i\in I\) the \(R[T_i]\)-module \(_{R[T_i]} \langle\text{lm}(f); f\neq 0,f \in W, \text{lt}(f) \in U_i\rangle\) is generated by \(\{\text{lm} (tg);g\in G,t \in T_i(g)\}\). Generalized division of \(g\in V\) by a finite subset of \(V \setminus \{0\}\) and a generalized concept of ``\(S\)-polynomial'' are defined and then used to state and prove a generalized version of Buchberger's algorithm to compute a generalized Gröbner basis. The paper concludes with several examples of the computation of conic decompositions and of Gröbner bases of Laurent polynomial ideals, and of their use to solve systems of difference equations.