The Skolem Problem for reversible linear recurrence sequences

Richard J. Lipton, Florian Luca, Joël Ouaknine, and James Worrell

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 (un)n=0 has a zero term (i.e., whether un = 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.

In this paper, we restrict our attention to reversible linear recurrence sequences: an integer LRS (un)n=0 is reversible if its unique extension to a bi-infinite LRS (un)n=-∞ also takes exclusively integer values. (A typical example is the Fibonacci sequence, whose bi-infinite extension is (...,5,-3,2,-1,1,0,1,1,2,3,5,...).) Our main result is that, for reversible LRS of order 7 or less, the Skolem Problem is decidable.

Submitted, 2021. 10 pages.

PDF © Richard J. Lipton, Florian Luca, Joël, and James Worrell.



Imprint / Data Protection