On the Skolem problem and the Skolem conjecture
<p>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 has a zero term (i.e., whether un = 0 for some n). A major breakthrough in the early 1980s established d...
| Váldodahkkit: | , , , , , |
|---|---|
| Materiálatiipa: | Conference item |
| Giella: | English |
| Almmustuhtton: |
Association for Computing Machinery
2022
|
| _version_ | 1826308305054597120 |
|---|---|
| author | Lipton, RJ Luca, L Nieuwveld, J Ouaknine, J Purser, D Worrell, J |
| author_facet | Lipton, RJ Luca, L Nieuwveld, J Ouaknine, J Purser, D Worrell, J |
| author_sort | Lipton, RJ |
| collection | OXFORD |
| description | <p>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 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.</p>
<p>Our main contributions in this paper are as follows:</p>
<p>First, we show that the Skolem Problem is decidable for reversible LRS of order 7 or less. (An integer LRS is reversible if its unique extension to a bi-infinite LRS 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, …⟩.)</p>
<p>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.</p> |
| first_indexed | 2024-03-07T07:17:33Z |
| format | Conference item |
| id | oxford-uuid:e7b28663-badf-4f12-8444-a4f83fa85a88 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:17:33Z |
| publishDate | 2022 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:e7b28663-badf-4f12-8444-a4f83fa85a882022-08-15T14:04:16ZOn the Skolem problem and the Skolem conjectureConference itemhttp://purl.org/coar/resource_type/c_5794uuid:e7b28663-badf-4f12-8444-a4f83fa85a88EnglishSymplectic ElementsAssociation for Computing Machinery2022Lipton, RJLuca, LNieuwveld, JOuaknine, JPurser, DWorrell, J<p>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 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.</p> <p>Our main contributions in this paper are as follows:</p> <p>First, we show that the Skolem Problem is decidable for reversible LRS of order 7 or less. (An integer LRS is reversible if its unique extension to a bi-infinite LRS 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, …⟩.)</p> <p>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.</p> |
| spellingShingle | Lipton, RJ Luca, L Nieuwveld, J Ouaknine, J Purser, D Worrell, J On the Skolem problem and the Skolem conjecture |
| title | On the Skolem problem and the Skolem conjecture |
| title_full | On the Skolem problem and the Skolem conjecture |
| title_fullStr | On the Skolem problem and the Skolem conjecture |
| title_full_unstemmed | On the Skolem problem and the Skolem conjecture |
| title_short | On the Skolem problem and the Skolem conjecture |
| title_sort | on the skolem problem and the skolem conjecture |
| work_keys_str_mv | AT liptonrj ontheskolemproblemandtheskolemconjecture AT lucal ontheskolemproblemandtheskolemconjecture AT nieuwveldj ontheskolemproblemandtheskolemconjecture AT ouakninej ontheskolemproblemandtheskolemconjecture AT purserd ontheskolemproblemandtheskolemconjecture AT worrellj ontheskolemproblemandtheskolemconjecture |