Gröbner bases with respect to generalized term orders and their application to the modelling problem (Q1918501)

Let us consider the following homogeneous linear partial difference equation with constant coefficients: \[ \sum_{(i_1,\dots, i_n)\in S}R_{i_1,\dots,i_n} w(t_1+ i_1+\dots, t_n+ i_n)=0\tag{1} \] in the unknown \(w:\mathbb{N}^n\to K^q\) (\(K\) a field), where \(S\) is a finite subset of \(\mathbb{N}^n\) and \(R_{i_1,\dots,i_n}\) are \(l\times q\)-matrices with entries in \(K\). The problem considered in the paper is to decide whether (1) provides an unfalsified model for a finite set of observations, i.e. given \(v_1,\dots, v_m\in (K^q)^\Delta\) (the observations, with \(\Delta\subseteq \mathbb{N}^n\)), decide whether there exist \(m\) solutions of (1), say \(w_1,\dots, w_m\in(K^q)^{\mathbb{N}^n}\), such that \(w_i|_\Delta=v_i\), for \(i=1,\dots, m\). The matrices \(R_{i_1,\dots,i_n}\) of (1) can be encoded by a polynomial matrix \[ R:= \sum_{(i_1,\dots, i_n)\in S}R_{i_1,\dots,i_n} x_1^{i_1}\cdots x_n^{i_n}\in K[x_1,\dots, x_n]^{l\times q}. \] It is known that two difference equations encoded by two polynomial matrices \(R_1\) and \(R_2\) have the same set of solutions iff the \(K[x_1,\dots, x_n]\)-module generated by the rows of \(R_1\) coincides with the \(K[x_1,\dots, x_n]\)-module generated by the rows of \(R_2\). This fact allows to apply Gröbner bases techniques to the study of the above modelling problem. The authors remark however, that the straightforward application of the developed theory of Gröbner bases can give a solution to the above problem only in the case of very peculiar subsets \(\Delta\) of \(\mathbb{N}^n\), therefore in the paper they propose a generalization of the notion of term-order and they develop a Gröbner bases theory according to this type of order which allows to consider a wider class of subsets \(\Delta\subseteq \mathbb{N}^n\). Finally they give an explicit procedure for checking whether a model is unfalsified based on their generalization of Gröbner bases.