Conjectural Decidability of the Skolem Problem
Discrete Mathematics
Summary
The authors study a long-standing open problem called the Skolem Problem, which asks if an integer sequence defined by simple rules ever hits zero. They focus on very large zeroes occurring at extremely high positions in the sequence. The authors show that these large zeroes, if they exist, must have unusual patterns related to specially defined prime numbers called "good primes." Building on a famous conjecture from number theory, they argue that such large zeroes might not exist, which would solve the Skolem Problem. They also prove without assumptions that large zeroes are extremely rare, helping to better understand where zeroes in these sequences can occur.
Authors
Florian Luca, Joël Ouaknine, James Worrell
Abstract
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.