On the Skolem Problem and the Skolem Conjecture

It is a longstanding open problem whether there is an algorithm to decide the Skolem Problem for linear recurrence sequences (LRS) over the integers, namely whether a given such sequence <u_n>_n=0^∞ has a zero term (i.e., whether u_n = 0 for some n). A major breakthrough in the early 1980s established decidability for LRS of order four or less, i.e., for LRS in which every new term depends linearly on the previous four (or fewer) terms. The Skolem Problem for LRS of order 5 or more, in particular, remains a major open challenge to this day.

Our main contributions in this paper are as follows:

First, we show that the Skolem Problem is decidable for reversible LRS of order 7 or less. (An integer LRS <u_n>_n=0^∞ is reversible if its unique extension to a bi-infinite LRS <u_n>_n=-∞^∞ also takes exclusively integer values; a typical example is the classical Fibonacci sequence, whose bi-infinite extension is <..., 5, -3, 2 , -1, 1, 0, 1, 1, 2, 3, 5,...>.)

Second, assuming the Skolem Conjecture (a central hypothesis in Diophantine analysis, also known as the Exponential Local-Global Principle), we show that the Skolem Problem for LRS of order 5 is decidable, and exhibit a concrete procedure for solving it.

Proceedings of LICS 22, 2022. 9 pages.

PDF © 2022 Richard J. Lipton, Florian Luca, Joris Nieuwveld, Joël Ouaknine, David Purser, and James Worrell.