The Skolem Problem in Rings of Positive Characteristic
Ruiwen Dong, Doron Shafrir
摘要
We show that the Skolem Problem is decidable in finitely generated commutative rings of positive characteristic. More precisely, we show that there exists an algorithm which, given a finite presentation of a (unitary) commutative ring R = Z /T [X 1 , . . . , X n ]/I of characteristic T > 0, and a linear recurrence sequence (γ n ) n∈N ∈ R N , determines whether (γ n ) n∈N contains a zero term. Our proof is based on two recent results: Dong and Shafrir (2026) on the solution set of S-unit equations over p e -torsion modules, and Karimov, Luca, Nieuwveld, Ouaknine, and Worrell (2025) on solving linear equations over powers of two multiplicatively independent numbers. Our result implies, moreover, that the zero set of a linear recurrence sequence over a ring of characteristic T = p e1 1 • • • p e k k is effectively a finite union of p i -normal sets in the sense of Derksen (2007).
问问这篇 Paper
智能体会读完全文。
Lune 把这篇 Paper 索引到了每一个公式,引用它的顶会 Paper 也一样。你提问,回答直接引用原文。
它引用的顶会 Paper5
- Deciding ω-regular properties on linear recurrence sequencesShaull Almagor, Toghrul Karimov, Edon Kelmendi, Joël Ouaknine 等POPL 2021 · 被引用 14 次
- On the Skolem Problem and the Skolem ConjectureRichard Lipton, Florian Luca, Joris Nieuwveld, Joël Ouaknine 等LICS 2022 · 被引用 6 次
- S-Unit Equations in Modules and Linear-Exponential Diophantine EquationsRuiwen Dong, Doron ShafrirSTOC 2026 · 被引用 4 次
- A strong version of Cobham's theoremPhilipp Hieronymi, Christian SchulzSTOC 2022 · 被引用 3 次
- On the Decidability of Presburger Arithmetic Expanded with PowersToghrul Karimov, Florian Luca, Joris Nieuwveld, Joël Ouaknine 等SODA 2025
相关 Paper
- Universal Skolem SetsFlorian Luca, Joël Ouaknine, James WorrellLICS 2021 · 被引用 3 次
- On the Complexity of the Skolem Problem at Low OrdersPiotr Bacik, Joël Ouaknine, James WorrellSODA 2026
- Linear equations with monomial constraints and decision problems in abelian-by-cyclic groupsRuiwen DongSODA 2025 · 被引用 4 次
- On the Decidability of Monadic Second-Order Logic with Arithmetic PredicatesValérie Berthé, Toghrul Karimov, Joris Nieuwveld, Joël Ouaknine 等LICS 2024 · 被引用 3 次
- Multiple Reachability in Linear Dynamical SystemsToghrul Karimov, Edon Kelmendi, Joël Ouaknine, James WorrellLICS 2025 · 被引用 1 次
