Completing the picture for the Skolem Problem on order-4 linear recurrence sequences
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917134636941312 |
|---|---|
| author | Bacik, Piotr |
| author_facet | Bacik, Piotr |
| contents | For almost a century, the decidability of the Skolem Problem - that is, the problem of finding whether a given linear recurrence sequence (LRS) has a zero term - has remained open. A breakthrough in the 1980s established that the Skolem Problem is indeed decidable for algebraic LRS of order at most 3, and real algebraic LRS of order at most 4. However, for general algebraic LRS of order 4 the question of decidability has remained open. Our main contribution in this paper is to prove decidability for this last case, i.e. we show that the Skolem Problem is decidable for all algebraic LRS of order at most 4. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_01221 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Completing the picture for the Skolem Problem on order-4 linear recurrence sequences Bacik, Piotr Formal Languages and Automata Theory Number Theory For almost a century, the decidability of the Skolem Problem - that is, the problem of finding whether a given linear recurrence sequence (LRS) has a zero term - has remained open. A breakthrough in the 1980s established that the Skolem Problem is indeed decidable for algebraic LRS of order at most 3, and real algebraic LRS of order at most 4. However, for general algebraic LRS of order 4 the question of decidability has remained open. Our main contribution in this paper is to prove decidability for this last case, i.e. we show that the Skolem Problem is decidable for all algebraic LRS of order at most 4. |
| title | Completing the picture for the Skolem Problem on order-4 linear recurrence sequences |
| topic | Formal Languages and Automata Theory Number Theory |
| url | https://arxiv.org/abs/2409.01221 |