2026-07-25T02:12:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25497 2026-03-19T13:34:11Z ddc:004 open_access

On the p-adic Skolem Problem Bacik, Piotr Ouaknine, Joël Purser, David Worrell, James Skolem Problem p-adic Schanuel Conjecture Skolem Conjecture Exponential Local-Global Principle exponential polynomial The Skolem Problem asks to determine whether a given linear recurrence sequence (LRS) has a zero term. Showing decidability of this problem is equivalent to giving an effective proof of the Skolem-Mahler-Lech Theorem, which asserts that a non-degenerate LRS has finitely many zeros. The latter result was proven over 90 years ago via an ineffective method showing that such an LRS has only finitely many p-adic zeros. In this paper we consider the problem of determining whether a given LRS has a p-adic zero, as well as the corresponding function problem of computing exact representations of all p-adic zeros. We present algorithms for both problems and report on their implementation. The output of the algorithms is unconditionally correct, and termination is guaranteed subject to the p-adic Schanuel Conjecture (a standard number-theoretic hypothesis concerning the p-adic exponential function). While these algorithms do not solve the Skolem Problem, they can be exploited to find natural-number and rational zeros under additional hypotheses. To illustrate this, we apply our results to show decidability of the Simultaneous Skolem Problem (determine whether two coprime linear recurrences have a common natural-number zero), again subject to the p-adic Schanuel Conjecture. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Piotr Bacik and Joël Ouaknine and David Purser and James Worrell 2026 Is Part Of LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2026.8 urn:nbn:de:0030-drops-254979 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.8 eng https://creativecommons.org/licenses/by/4.0/legalcode