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 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 similarly distributed 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.
Submitted, 2025. 10 pages.
PDF
© 2025 Florian Luca, Joël Ouaknine, and James Worrell.