Computing difference-differential dimension polynomials by relative Gröbner bases in difference-differential modules (Q950422)

The authors present a new algorithmic approach for computing the Hilbert function of a finitely generated difference-differential module equipped with the natural double filtration. The approach is based on a method of special Gröbner bases with respect to ``generalized term orders'' on \(\mathbb N^{m} \times \mathbb Z^{n}\) and on difference-differential modules. Using relative Gröbner bases, one is able to compute difference-differential dimension polynomials in two variables. The results obtained by the authors essentially improve theories of \textit{A. Levin} [J. Symb. Comput. 30, No. 4, 357--382 (2000; Zbl 0994.13009)], where the existence of the difference-differential dimension polynomial was proved via characteristic set. The main result of the paper under review shows the following assertion: Let \(R\) be a \(\Delta\)-\(\Sigma\)-field, \(D\) the ring of \(\Delta\)-\(\Sigma\)-operators over \(R\), \(M\) a finitely generated \(\Delta\)-\(\Sigma\)-module, in particular let \(M\) have the generators \(h_1, \ldots , h_q\). Let \(F\) be a free \(\Delta\)-\(\Sigma\)-module with a basis \(e_1, \ldots ,e_q\) and \(\pi: F \to M\) the natural \(\Delta\)-\(\Sigma\) epimorphism of \(F\) onto \(M\) (\(\pi (e_i) = h_i\) for \(i = 1, \ldots ,q\)). Let \(\prec\) and \(\prec^{'}\) be the generated term orders on \(\Lambda E\) of the terms of \(F\) defined above. Consider the submodule \(N = \ker(\pi)\) of \(F\) and let \(G = \{ g_1, \ldots , g_p \}\) be a \(\prec\)-Gröbner basis of \(N\) relative to \(\prec^{'}\). Let \[ U_{r,s} = \{ w \in \Lambda E \;| \;|w|_1 \leq r, |w|_2 \leq s \;and \;w \neq \ell t_{\prec}(\lambda g_i) \;(\forall \lambda \in \Lambda) \} \;\cup \] \[ \{ w \in \Lambda E \;| \;|w|_1 \leq r, |w|_2 \leq s \;and \;|\ell t_{\prec^{'}}(\lambda g_i)|_1 > r \;(\forall \lambda) \;s.t. \;w = \ell t_{\prec}(\lambda g_i) \}. \] Then the bivariate difference-differential dimension polynomial \(\psi\) associated with \(M\) is the cardinality of \(U\) (\(i.e.\) \(\psi (r,s) = |U_{r,s}|\)).