License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2023.5
URN: urn:nbn:de:0030-drops-180573
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18057/
Worrell, James
The Skolem Landscape (Invited Talk)
Abstract
The Skolem Problem asks to determine whether a given integer linear recurrence sequence (LRS) has a zero term. This decision problem arises within a number of different topics in computer science, including loop termination, weighted automata, formal power series, and probabilistic model checking, among many other examples. Decidability of the problem is notoriously open, despite having been the subject of sustained interest over several decades [Halava et al., 2005]. More specifically, the problem is known to be decidable for recurrences of order at most 4 - a result obtained some 40 years ago [Mignotte et al., 1984; Vereshchagin, 1985] - while decidability is open already for recurrences of order 5.
In this talk we take a wide-ranging view of the Skolem Problem. We survey its history and context, starting with the theorem of Skolem-Mahler-Lech characterising the set of zeros of a LRS over fields of characteristic zero. Here we explain the non-effective nature of the existing proofs of the theorem. Among modern developments, we overview versions of the Skolem-Mahler-Lech theorem for non-linear recurrences and for fields of non-zero characteristic. We also describe two recent directions of progress toward showing decidability of the Skolem Problem subject to classical number theoretic conjectures.
The first new development concerns a recent algorithm [Y. Bilu et al., 2022] that decides the problem on the class of simple LRS (those with simple characteristic roots) subject to two classical conjectures about the exponential function. The algorithm is self-certifying: its output comes with a certificate of correctness that can be checked unconditionally. The two conjectures alluded to above are required for the proof of termination of the algorithm.
A second new development concerns the notion of Universal Skolem Set [F. Luca et al., 2022]: a recursive set S of positive integers such that it is decidable whether a given non-degenerate linear recurrence sequence has a zero in S. Decidability of the Skolem Problem is equivalent to the assertion that ℕ is a Universal Skolem Set. In lieu of this one can ask whether there exists a Universal Skolem Set of density one. We will present a recent a construction of a Universal Skolem Set that has positive density unconditionally and has density one subject to the Bateman-Horn conjecture in number theory. The latter is a far-reaching generalisation of Hardy and Littlewood’s twin primes conjecture.
BibTeX - Entry
@InProceedings{worrell:LIPIcs.ICALP.2023.5,
author = {Worrell, James},
title = {{The Skolem Landscape}},
booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
pages = {5:1--5:2},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-278-5},
ISSN = {1868-8969},
year = {2023},
volume = {261},
editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18057},
URN = {urn:nbn:de:0030-drops-180573},
doi = {10.4230/LIPIcs.ICALP.2023.5},
annote = {Keywords: Automata, Formal Languages, Linear Recurrence Sequences}
}
|
Keywords: |
|
Automata, Formal Languages, Linear Recurrence Sequences |
|
Collection: |
|
50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
05.07.2023 |
