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
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.
© Richard J. Lipton, Florian Luca, Joël, and James Worrell.