On the Skolem Problem for Reversible Sequences

Abstract

Given an integer linear recurrence sequence $\langle X_n \rangle$, the Skolem Problem asks to determine whether there is a natural number $n$ such that $X_n=0$. In a recent paper (LICS 2022), Lipton, Luca, Nieuwveld, Ouaknine, Purser, and Worrell prove that the Skolem Problem is decidable for a class of reversible sequences up to order seven. Here we give an alternative proof of the result. The novelty of our approach arises from our use of results concerning the polynomial relations between Galois conjugates. In particular, we make repeated use of a result due to Dubickas and Smyth for algebraic integers that lie alongside all their Galois conjugates on two (but not one) concentric circles centred at the origin.

Publication
Mathematical Foundations in Computer Science, MFCS `22