Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-10T05:50:45.463Z Has data issue: false hasContentIssue false
  • English
  • Français

SOLVING DIFFERENCE EQUATIONS IN SEQUENCES: UNIVERSALITY AND UNDECIDABILITY

Part of: Difference equations Differential and difference algebra Computability and recursion theory Computational aspects and applications Computational aspects in algebraic geometry Difference and functional equations

Published online by Cambridge University Press:  30 June 2020

GLEB POGUDIN ,
THOMAS SCANLON  and
MICHAEL WIBMER
GLEB POGUDIN
Affiliation:
Department of Computer Science, National Research University Higher School of Economics, Moscow, Russia; gleb.pogudin@lix.polytechnique.fr
THOMAS SCANLON
Affiliation:
University of California at Berkeley, Department of Mathematics, Berkeley, USA; scanlon@math.berkeley.edu
MICHAEL WIBMER
Affiliation:
Institute of Analysis and Number Theory, Graz University of Technology, Graz, Austria; wibmer@math.tugraz.at

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We study solutions of difference equations in the rings of sequences and, more generally, solutions of equations with a monoid action in the ring of sequences indexed by the monoid. This framework includes, for example, difference equations on grids (for example, standard difference schemes) and difference equations in functions on words. On the universality side, we prove a version of strong Nullstellensatz for such difference equations under the assumption that the cardinality of the ground field is greater than the cardinality of the monoid and construct an example showing that this assumption cannot be omitted. On the undecidability side, we show that the following problems are undecidable:

MSC classification

Primary: 12H10: Difference algebra
Secondary: 39A10: Difference equations, additive 13P25: Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.) 14Q20: Effectivity, complexity 03D35: Undecidability and degrees of sets of sentences

Information

Type
Differential Equations
Information
Forum of Mathematics, Sigma , Volume 8 , 2020 , e33
Creative Commons
Creative Common License - CCCreative Common License - BY
This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.
Copyright
© The Author(s) 2020

References

Berger, R., ‘The undecidability of the domino problem’, Mem. Amer. Math. Soc. 66 (1966), 1–72.Google Scholar
Bournez, O. and Pouly, A., Handbook of Computability and Complexity in Analysis, A Survey on Analog Models of Computation (Springer, 2018), to appear, https://arxiv.org/abs/1805.05729.Google Scholar
Bustamante Medina, R. F., ‘Differentially closed fields of characteristic zero with a generic automorphism’, Rev. Mat. Teor. Apl. 14(1) (2007), 81–100.Google Scholar
Chatzidakis, Z., ‘Model theory of fields with operators – a survey’, inLogic Without Borders – Essays on Set Theory, Model Theory, Philosophical Logic and Philosophy of Mathematics (Walter de Gruyter, Berlin/Boston/Munich, 2015), 91–114.Google Scholar
Chatzidakis, Z. and Hrushovski, E., ‘Model theory of difference fields’, Trans. Amer. Math. Soc. 351(8) (1999), 2997–3071.CrossRefGoogle Scholar
Cohn, R., Difference Algebra (Interscience Publishers John Wiley & Sons, New York–London–Sydney, 1965).Google Scholar
Everest, G., van der Poorten, A., Shparlinski, I. and Ward, T., Recurrence Sequences (American Mathematical Society, Providence, RI, 2003).CrossRefGoogle Scholar
Gao, X.-S., Luo, Y. and Yuan, C., ‘A characteristic set method for ordinary difference polynomial systems’, J. Symbolic Comput. 44(3) (2009), 242–260.CrossRefGoogle Scholar
Gao, X. S., van der Hoeven, J., Yuan, C. M. and Zhang, G. L., ‘Characteristic set method for differential–difference polynomial systems’, J. Symbolic Comput. 44(9) (2009), 1137–1163.CrossRefGoogle Scholar
Hardy, G. H. and Wright, E. M., An Introduction to the Theory of Numbers, 6th edn, (Oxford University Press, 2008).Google Scholar
Heilbronn, H. A., ‘On discrete harmonic functions’, Math. Proc. Cambridge Philos. Soc. 45(2) (1949), 194–206.CrossRefGoogle Scholar
Hrushovski, E., ‘The Manin–Mumford conjecture and the model theory of difference fields’, Ann. Pure Appl. Logic 112(1) (2001), 43–115.CrossRefGoogle Scholar
Hrushovski, E. and Point, F., ‘On von Neumann regular rings with an automorphism’, J. Algebra 315(1) (2007), 76–120.CrossRefGoogle Scholar
Jelonek, Z., ‘On the effective Nullstellensatz’, Invent. Math. 162(1) (2005), 1–17.CrossRefGoogle Scholar
Kikyo, H., ‘On generic predicates and automorphisms’, RIMS Kˆokyˆuroku Bessatsu 1390 (2004), 1–8.Google Scholar
Koiran, P. and Moore, C., ‘Closed-form analytic maps in one and two dimensions can simulate universal Turing machines’, Theor. Comput. Sci. 210(1) (1999), 217–223.CrossRefGoogle Scholar
Kolchin, E. R., Differential Algebra and Algebraic Groups (Academic Press, New York, 1973).Google Scholar
Lang, S., ‘Hilbert’s Nullstellensatz in infinite-dimensional space’, Proc. Amer. Math. Soc. 3 (1952), 407–410.Google Scholar
Léon Sánchez, O., ‘On the model companion of partial differential fields with an automorphism’, Israel J. Math. 212(1) (2016), 419–442.Google Scholar
Levin, A., Difference Algebra (Springer, The Netherlands, 2008).CrossRefGoogle Scholar
Makanin, G. S., ‘The problem of solvability of equations in a free semigroup’, Math. USSR Sbornik 32(2) (1977), 129–198.CrossRefGoogle Scholar
Matijasevic, Y. V., ‘Enumerable sets are Diophantine’, Soviet Math. Dokl. 11 (1970), 354–357.Google Scholar
Moore, C., ‘Unpredictability and undecidability in dynamical systems’, Phys. Rev. Lett. 64 (1990), 2354–2357.CrossRefGoogle ScholarPubMed
Ovchinnikov, A., Pogudin, G. and Scanlon, T., Effective difference elimination and Nullstellensatz. Accepted for publication in the J. Eur. Math. Soc., (2019).CrossRefGoogle Scholar
Ritt, J., Differential Algebra (American Mathematical Society, Providence, RI, 1950).CrossRefGoogle Scholar
Schnorr, C. P., ‘A unified approach to the definition of random sequences’, Math. Sys. Theory 5(3) (1971), 246–258.CrossRefGoogle Scholar
Singer, M. F., ‘The model theory of ordered differential fields’, J. Symbolic Logic 43(1) (1978), 82–91.CrossRefGoogle Scholar
Tarski, A., A Decision Method for Elementary Algebra and Geometry, (RAND Corporation, Santa Monica, CA, 1948).Google Scholar
Umirbaev, U., ‘Algorithmic problems for differential polynomial algebras’, J. Algebra 455 (2016), 77–92.CrossRefGoogle Scholar