2026-09-18T02:36:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24178 2026-09-05T18:35:33Z ddc:004 open_access

On Large Zeros of Linear Recurrence Sequences Luca, Florian Ouaknine, Joël Worrell, James Skolem Problem linear recurrence sequences decidability Cramér conjecture The Skolem Problem asks to determine whether a given integer linear recurrence sequence (LRS) has a zero term. This problem, whose decidability has been open for many decades, arises across a wide range of topics in computer science, including loop termination, formal languages, automata theory, and probabilistic model checking, amongst many others. In the present paper, we introduce a notion of "large" zeros of (non-degenerate) linear recurrence sequences, i.e., zeros occurring at an index larger than a sixth-fold exponential of the size of the data defining the given LRS . We establish two main results. First, we show that large zeros are very sparse: the set of positive integers that can possibly arise as large zeros of some LRS has null density. This in turn immediately yields a Universal Skolem Set of density one, answering a question left open in the literature. Second, we define an infinite set of prime numbers, termed "good", having density one amongst all prime numbers, with the following property: for any large zero of a given LRS, there is an interval around the large zero together with an upper bound on the number of good primes possibly present in that interval. The bound in question is much lower than one would expect if good primes were distributed similarly as ordinary prime numbers, as per the Cramér model in number theory. We therefore conjecture that large zeros do not exist, which would entail decidability of the Skolem Problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Florian Luca and Joël Ouaknine and James Worrell 2025 Is Part Of LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2025.71 urn:nbn:de:0030-drops-241781 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.71 eng https://creativecommons.org/licenses/by/4.0/legalcode