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 4 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