Effective difference elimination and nullstellensatz. (English) Zbl 1475.12012

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:
Under what conditions does such a system have a sequence solution?
Can these solutions be made sufficiently transparent to allow for efficient computation?
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?

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:
The system \(F=0\) has a solution in \(K^{\mathbb{Z}}\);
\(F=0\) has a solution in \(K^{\mathbb{N}}\);
\(F=0\) has finite partial solutions of length \(l\) for sufficiently large \(l\);
The difference ideal \(J\) generated by \(F\) in \(K\{x_{1},\dots, x_{n}\}\) does not contain \(1\);
The reflexive closure of \(J\) in the inversive closure of \(K\{x_{1},\dots, x_{n}\}\) does not contain \(1\);
\(F=0\) has a solution in some difference \(K\)-algebra.

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.


12H10 Difference algebra
13P25 Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.)
14Q20 Effectivity, complexity and computational aspects of algebraic geometry
03C10 Quantifier elimination, model completeness, and related topics
03C60 Model-theoretic algebra
Full Text: DOI arXiv


[1] Allen, L.: Some discrete-timeSI,SIR, andSISepidemic models. Math. Biosciences124, 83- 105 (1994)Zbl 0807.92022 · Zbl 0807.92022
[2] Bates, D. J., Hauenstein, J. D., Sommese, A. J., Wampler, C. W.: Numerically Solving Polynomial Systems with Bertini. SIAM, Philadelphia, PA (2013)Zbl 1295.65057 MR 3155500 · Zbl 1295.65057
[3] Binyamini, G.: Bezout-type theorems for differential fields. Compos. Math.153, 867-888 (2017)Zbl 1376.12006 MR 3705244 · Zbl 1376.12006
[4] Brownawell, W. D.: Bounds for the degrees in the Nullstellensatz. Ann. of Math.126, 577- 591 (1987)Zbl 0641.14001 MR 0916719 · Zbl 0641.14001
[5] Chatzidakis, Z., Hrushovski, E.: Model theory of difference fields. Trans. Amer. Math. Soc. 351, 2997-3071 (1999)Zbl 0922.03054 MR 1652269 · Zbl 0922.03054
[6] Cohn, R.: Difference Algebra. Wiley, New York (1965)Zbl 0127.26402 MR 0205987 · Zbl 0127.26402
[7] Cox, D., Little, J., O’Shea, D.: Ideals, Varieties, and Algorithms. Undergrad. Texts in Math., Springer, New York (2015)Zbl 1335.13001 MR 3330490
[8] Cushing, J., Henson, S., Roeger, L.: Coexistence of competing juvenile-adult structured populations. J. Biol. Dynam.1, 201-231 (2007)Zbl 1122.92064 MR 2319998 · Zbl 1122.92064
[9] D’Alfonso, L., Jeronimo, G., Solern´o, P.: Effective differential Nullstellensatz for ordinary DAE systems over the complex numbers. J. Complexity30, 588-603 (2014) Zbl 1383.12002 MR 3239268 · Zbl 1383.12002
[10] Ekhad, S. B., Zeilberger, D.: How to generate as many Somos-like miracles as you wish. J. Difference Equations Appl.20, 852-858 (2014)Zbl 1292.39004 MR 3210318 · Zbl 1292.39004
[11] Engler, A. J., Prestel, A.: Valued Fields. Springer, Berlin (2005)Zbl 1128.12009 MR 2183496 · Zbl 1128.12009
[12] Fakhruddin, N.: Questions on self maps of algebraic varieties. J. Ramanujan Math. Soc.18, 109-122 (2003)Zbl 1053.14025 MR 1995861 · Zbl 1053.14025
[13] Gao, X. S., van der Hoeven, J., Yuan, C. M., Zhang, G. L.: Characteristic set method for differential-difference polynomial systems. J. Symbolic Comput.44, 1137-1163 (2009) Zbl 1169.13019 MR 2532162 · Zbl 1169.13019
[14] Gao, X. S., Luo, Y., Yuan, C.: A characteristic set method for ordinary difference polynomial systems. J. Symbolic Comput.44, 242-260 (2009)Zbl 1164.39008 MR 2499507 · Zbl 1164.39008
[15] Harris, J.: Algebraic Geometry: A First Course. Springer (1992)Zbl 0779.14001 MR 1416564 · Zbl 0779.14001
[16] Heintz, J.: Definability and fast quantifier elimination in algebraically closed fields. Theoret. Computer Sci.24, 239-277 (1983)Zbl 0546.03017 MR 0716823 · Zbl 0546.03017
[17] Hong, H., Ovchinnikov, A., Pogudin, G., Yap, C.: Global identifiability of differential models. Comm. Pure Appl. Math. (to appear);arXiv:1801.08112(2020)
[18] Hrushovski, E.: The elementary theory of the Frobenius automorphism.http://www.ma. huji.ac.il/∼ehud/FROB.pdf
[19] Hrushovski, E.: The Manin-Mumford conjecture and the model theory of difference fields. Ann. Pure Appl. Logic112, 43-115 (2001)Zbl 0987.03036 MR 1854232 · Zbl 0987.03036
[20] Hrushovski, E., Pillay, A.: Effective bounds for the number of transcendental points on subvarieties of semi-abelian varieties. Amer. J. Math.122, 439-450 (2000)Zbl 0971.14024 MR 1759883 · Zbl 0971.14024
[21] Hrushovski, E., Point, F.: On von Neumann regular rings with an automorphism. J. Algebra 315, 76-120 (2007)Zbl 1127.03033 MR 2344334 · Zbl 1127.03033
[22] Jelonek,Z.:OntheeffectiveNullstellensatz.Invent.Math.162,1-17(2005) Zbl 1087.14003 MR 2198324 · Zbl 1087.14003
[23] Koll´ar, J.: Sharp effective Nullstellensatz. J. Amer. Math. Soc.1, 963-975 (1988) Zbl 0682.14001 MR 0944576 · Zbl 0682.14001
[24] Kuhlmann, F. V.: Valuation theoretic and model theoretic aspects of local uniformization. In: Resolution of Singularities, Progr. Math. 181, Birkh¨auser, Basel, 381-456 (2000) Zbl 1046.14001 MR 1748629 · Zbl 1046.14001
[25] Levin, A.: Difference Algebra. Springer (2008)Zbl 1209.12003 MR 2428839 · Zbl 1209.12003
[26] Li, W., Li, Y. H.: Difference Chow form. J. Algebra428, 67-90 (2015)Zbl 1349.12004 MR 3314286 · Zbl 1349.12004
[27] Li, W., Yuan, C. M., Gao, X. S.: Sparse difference resultant. J. Symbolic Comput.68, 169-203 (2015)Zbl 1328.65266 MR 3283843 · Zbl 1328.65266
[28] Lyzell, C., Glad, T., Enqvist, M., Ljung, L.: Difference algebra and system identification. Automatica47, 1896-1904 (2011)Zbl 1227.93122 MR 2886801 · Zbl 1227.93122
[29] Ovchinnikov, A., Pogudin, G., Vo, T.: Bounds for elimination of unknowns in systems of differential-algebraic equations.arXiv:1610.04022(2018)
[30] Pierce, D., Pillay, A.: A note on the axioms for differentially closed fields of characteristic zero. J. Algebra204, 108-115 (1998)Zbl 0922.12006 MR 1623945 · Zbl 0922.12006
[31] Roeger, L., Allen, L.: Discrete May-Leonard competition models I. J. Difference Equations Appl.10, 77-98 (2004)Zbl 1047.92049 MR 2033335 · Zbl 1047.92049
[32] Shafarevich, I.: Basic Algebraic Geometry 1. Springer (2013)Zbl 1273.14004 MR 3100243 · Zbl 1273.14004
[33] Stacks Project.https://stacks.math.columbia.edu(2018)
[34] Stanley, R. P.: Enumerative Combinatorics: Vol. 1. 2nd ed., Cambridge Univ. Press (2012) Zbl 1247.05003 MR 2868112 · Zbl 1247.05003
[35] Stillman, M., Takayama, N., Verschelde, J.: Software for Algebraic Geometry. Springer (2008)Zbl 1138.68008 · Zbl 1138.68008
[36] Tomaˇsi´c, I.: Twisted Galois stratification. Nagoya Math. J.222, 1-60 (2016)Zbl 06642611 MR 3509221 · Zbl 1475.03088
[37] Tomaˇsi´c, I.: Direct twisted Galois stratification. Ann. Pure Appl. Logic169, 21-53 (2018) Zbl 06803110 MR 3718952 · Zbl 1497.03052
[38] Varshavsky, Y.: Intersection of a correspondence with a graph of Frobenius. J. Algebraic Geom.27, 1-20 (2018)Zbl 1388.14034 MR 3722688 · Zbl 1388.14034
[39] Zippel, R.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.