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 double exponential of the magnitude of the
data defining the given LRS. We establish two main results. First, 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 conclude, conditionally on a strengthening of the classical
Cramér conjecture, that large zeros do not exist, which would
entail decidability of the Skolem Problem. Second, we show
unconditionally 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.
Submitted, 2026. 20 pages.
PDF
© 2026 Florian Luca, Joël Ouaknine, and James Worrell.