## Universal Skolem sets

*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, namely whether a
given such sequence has a zero term. In this paper we introduce the
notion of a *Universal Skolem Set*: an infinite subset
*S* of the positive integers such that there is an effective
procedure that inputs a linear recurrence sequence
**u** = (*u*(*n*))_{n≥0} and
decides whether *u*(*n*) = 0 for some
*n* ∈ *S*. The main technical contribution of the paper is
to exhibit such a set.

*Proceedings of LICS 21*, 2021. 6 pages.

**Distinguished Paper Award.**

PDF
© 2021 IEEE Computer Society Press.

Imprint / Data Protection