Can I read On the Skolem Problem and the Skolem Conjecture on EtoBox?

On the Skolem Problem and the Skolem Conjecture by Richard Lipton; Florian Luca; Joris Nieuwveld; Joël Ouaknine; David Purser; James Worrell is a scholarly article available to read on EtoBox.

What is On the Skolem Problem and the Skolem Conjecture about?

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 ⟨u n ⟩ ∞ n=0 has a zero term (i.e., whether u n = 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 ⟨u n ⟩ ∞ n=0 is reversible if its unique extension to a bi-infinite LRS ⟨u n ⟩ ∞ n=-∞ also takes exclusively integer values; a typical example is the classical Fibonacci sequence, whose bi-infinite 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 proc

Author

Richard Lipton; Florian Luca; Joris Nieuwveld; Joël Ouaknine; David Purser; James Worrell

Publisher

ACM

Published

2022

Language

EN