Effective difference elimination and nullstellensatz (Q783738): Difference between revisions

A sequence \((a_{j})_{j=0}^{\infty}\) of elements of a field \(K\) is said to be a solution of a difference equation with constant coefficients if there is a nonzero polynomial \(F(x_{0},\dots, x_{e})\in K[x_{0},\dots, x_{e}]\) such that for every natural number \(j\), one has \(F(a_{j}, a_{j+1},\dots, a_{j+e}) = 0\). This concept can be naturally generalized to systems of difference equations in several variables. The paper under review answers the following fundamental questions about sequence solutions of systems of ordinary difference equations: \begin{itemize} \item[(i)] Under what conditions does such a system have a sequence solution? \item[(ii)] Can these solutions be made sufficiently transparent to allow for efficient computation? \item[(iii)] Given a system of difference equations on \((n+m)\)-tuples of sequences, how does one eliminate some of the variables so as to deduce the consequences of these equations on the first \(n\) variables? \end{itemize} As the answers to these questions, the authors prove two strong results the first of which (Theorem 3.1 of the paper) can be viewed as effective difference Nullstellensatz; it reduces the problem of solvability of a system of difference equations to the problem of consistency of certain system of finitely many polynomial equations. The second main result of the paper (Theorem 3.4) is an effective difference elimination theorem; it reduces the question of existing/finding a consequence in the \(\mathbf{x}\)-variables of a system of difference equations in \(\mathbf{x}\) and \(\mathbf{u}\) (\(\mathbf{x}=(x_{1},\dots, x_{m})\) and \(\mathbf{u}=(u_{1},\dots, u_{r})\) are two sets of variables) to a question about a polynomial ideal in a polynomial ring in finitely many variables. Among other important results of the paper, one has to mention is a version of difference Nullstellensatz over an uncountable algebraically closed inversive difference field \(K\). It is shown that if \(F\) is a finite subset of the ring of difference polynomials \(K\{x_{1},\dots, x_{n}\}\), then the following statements are equivalent: \begin{itemize} \item[(i)] The system \(F=0\) has a solution in \(K^{\mathbb{Z}}\); \item[(ii)] \(F=0\) has a solution in \(K^{\mathbb{N}}\); \item[(iii)] \(F=0\) has finite partial solutions of length \(l\) for sufficiently large \(l\); \item[(iv)] The difference ideal \(J\) generated by \(F\) in \(K\{x_{1},\dots, x_{n}\}\) does not contain \(1\); \item[(v)] The reflexive closure of \(J\) in the inversive closure of \(K\{x_{1},\dots, x_{n}\}\) does not contain \(1\); \item[(vi)] \(F=0\) has a solution in some difference \(K\)-algebra. \end{itemize} The paper also contains a number of examples that illustrate applications of the obtained results and counterexamples that show one cannot have a coefficient-independent effective strong Nullstellensatz for systems of difference equations.