2019/09/07 by Gleb Pogudin, Thomas Scanlon, Pogudin, Gleb +3
Computer Science · Decision Sciences · Mathematics · #Algebraic Geometry (math.AG) #Commutative Algebra and Its Applications #Dynamical Systems (math.DS) #FOS: Mathematics #Polynomial and algebraic computation #Scheduling and Timetabling Solutions
paper · pdf · doi:10.48550/arxiv.1909.03239
openalex publication_date 2019/09/07 · openalex created_date 2022/07/28 · openalex updated_date 2026/07/28
We study solutions of difference equations in the rings of sequences and,\nmore generally, solutions of equations with a monoid action in the ring of\nsequences indexed by the monoid. This framework includes, for example,\ndifference equations on grids (e.g., standard difference schemes) and\ndifference equations in functions on words.\n On the universality side, we prove a version of strong Nullstellensatz for\nsuch difference equations under the assuption that the cardinality of the\nground field is greater than the cardinality of the monoid and construct an\nexample showing that this assumption cannot be omitted.\n On the undecidability side, we show that the following problems are\nundecidable:\n bullet testing radical difference ideal membership or, equivalently,\ndetermining whether a given difference polynomial vanishes on the solution set\nof a given system of difference polynomials;\n bullet determining consistency of a system of difference equations in the\nring of real-valued sequences;\n bullet determining consistency of a system of equations with action of\n\ℤ2, \ℕ2, or the free monoid with two generators in the\ncorresponding ring of sequences over any field of characteristic zero.\n