A universal Skolem set of positive lower density
The Skolem Problem asks to decide whether a given integer linear recurrence sequence (LRS) has a zero term. Decidability of this problem has been open for many decades, with little progress since the 1980s. Recently, a new approach was initiated via the notion of a Skolem set - a set of positive int...
| Main Authors: | , , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2022
|
| Subjects: |
| _version_ | 1797110826779279360 |
|---|---|
| author | Luca, F Ouaknine, J Worrell, J |
| author_facet | Luca, F Ouaknine, J Worrell, J |
| author_sort | Luca, F |
| collection | OXFORD |
| description | The Skolem Problem asks to decide whether a given integer linear recurrence sequence (LRS) has a zero term. Decidability of this problem has been open for many decades, with little progress since the 1980s. Recently, a new approach was initiated via the notion of a Skolem set - a set of positive integers relative to which the Skolem Problem is decidable. More precisely, 𝒮 is a Skolem set for a class ℒ of integer LRS if there is an effective procedure that, given an LRS in ℒ, decides whether the sequence has a zero in 𝒮. A recent work exhibited a Skolem set for the class of all LRS that, while infinite, had density zero. In the present work we construct a Skolem set of positive lower density for the class of simple LRS . |
| first_indexed | 2024-03-07T08:00:11Z |
| format | Conference item |
| id | oxford-uuid:3a282bbb-a01a-4a54-b580-f4ac06a45b7c |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T08:00:11Z |
| publishDate | 2022 |
| publisher | Schloss Dagstuhl – Leibniz-Zentrum für Informatik |
| record_format | dspace |
| spelling | oxford-uuid:3a282bbb-a01a-4a54-b580-f4ac06a45b7c2023-09-26T17:20:24ZA universal Skolem set of positive lower densityConference itemhttp://purl.org/coar/resource_type/c_5794uuid:3a282bbb-a01a-4a54-b580-f4ac06a45b7cComputing methodologiesSymbolic and algebraic algorithmsNumber theory algorithmsEnglishSymplectic ElementsSchloss Dagstuhl – Leibniz-Zentrum für Informatik2022Luca, FOuaknine, JWorrell, JThe Skolem Problem asks to decide whether a given integer linear recurrence sequence (LRS) has a zero term. Decidability of this problem has been open for many decades, with little progress since the 1980s. Recently, a new approach was initiated via the notion of a Skolem set - a set of positive integers relative to which the Skolem Problem is decidable. More precisely, 𝒮 is a Skolem set for a class ℒ of integer LRS if there is an effective procedure that, given an LRS in ℒ, decides whether the sequence has a zero in 𝒮. A recent work exhibited a Skolem set for the class of all LRS that, while infinite, had density zero. In the present work we construct a Skolem set of positive lower density for the class of simple LRS . |
| spellingShingle | Computing methodologies Symbolic and algebraic algorithms Number theory algorithms Luca, F Ouaknine, J Worrell, J A universal Skolem set of positive lower density |
| title | A universal Skolem set of positive lower density |
| title_full | A universal Skolem set of positive lower density |
| title_fullStr | A universal Skolem set of positive lower density |
| title_full_unstemmed | A universal Skolem set of positive lower density |
| title_short | A universal Skolem set of positive lower density |
| title_sort | universal skolem set of positive lower density |
| topic | Computing methodologies Symbolic and algebraic algorithms Number theory algorithms |
| work_keys_str_mv | AT lucaf auniversalskolemsetofpositivelowerdensity AT ouakninej auniversalskolemsetofpositivelowerdensity AT worrellj auniversalskolemsetofpositivelowerdensity AT lucaf universalskolemsetofpositivelowerdensity AT ouakninej universalskolemsetofpositivelowerdensity AT worrellj universalskolemsetofpositivelowerdensity |