On the Skolem Problem and the Skolem Conjecture

Lipton, Richard, Luca, Florian, Nieuwveld, Joris, Ouaknine, Joël, Purser, David and Worrell, James (2022) On the Skolem Problem and the Skolem Conjecture. In: LICS '22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science.

Access the full-text of this item by clicking on the Open Access link.

Official URL: http://dx.doi.org/10.1145/3531130.3533328

Abstract

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 n8=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 4 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. Our main contributions in this paper are as follows: First, we show that the Skolem Problem is decidable for reversible LRS of order 7 or less. (An integer LRS (un)n8=0 is reversible if its unique extension to a bi-infnite LRS (un)n8=-8 also takes exclusively integer values; a typical example is the classical Fibonacci sequence, whose bi-infnite extension is (. . . , 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, . . .) Second, assuming the Skolem Conjecture (a central hypothesis in Diophantine analysis, also known as the Exponential Local-Global Principle), we show that the Skolem Problem for LRS of order 5 is decidable, and exhibit a concrete procedure for solving it.

Item Type:	Conference or Workshop Item (Unspecified)
Uncontrolled Keywords:	4901 Applied Mathematics, 4903 Numerical and Computational Mathematics, 4904 Pure Mathematics, 49 Mathematical Sciences
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	29 Mar 2023 10:35
Last Modified:	04 Jul 2024 21:41
DOI:	10.1145/3531130.3533328
Open Access URL:	https://dl.acm.org/doi/pdf/10.1145/3531130.3533328
Related URLs:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3169327