The Skolem Problem asks to determine whether a given integer linear recurrence sequence (LRS) has a zero term. Decidability of this problem has been open for many decades, with little progress since the 1980s. Recently, a new approach was initiated via the notion of a Skolem set -- a set of positive integers relative to which the Skolem Problem is decidable. More precisely, S is a Skolem set for a class L of integer LRS if there is an effective procedure that, given an LRS in L, decides whether the sequence has a zero in S. A recent work exhibited a Skolem set for the class of all LRS that, while infinite, had density zero. In the present paper we construct a Skolem set of positive lower density for the class of simple LRS.
Proceedings of MFCS 22, LIPIcs 241, 2022. 12 pages.
PDF
© 2022 Florian Luca, Joël Ouaknine, and James Worrell.