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.MFCS.2022.20
URN: urn:nbn:de:0030-drops-168180
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16818/
Go to the corresponding LIPIcs Volume Portal

Bilu, Yuri ; Luca, Florian ; Nieuwveld, Joris ; Ouaknine, Joël ; Purser, David ; Worrell, James

Skolem Meets Schanuel

pdf-format:
LIPIcs-MFCS-2022-20.pdf (0.8 MB)

Abstract

The celebrated Skolem-Mahler-Lech Theorem states that the set of zeros of a linear recurrence sequence is the union of a finite set and finitely many arithmetic progressions. The corresponding computational question, the Skolem Problem, asks to determine whether a given linear recurrence sequence has a zero term. Although the Skolem-Mahler-Lech Theorem is almost 90 years old, decidability of the Skolem Problem remains open. The main contribution of this paper is an algorithm to solve the Skolem Problem for simple linear recurrence sequences (those with simple characteristic roots). Whenever the algorithm terminates, it produces a stand-alone certificate that its output is correct - a set of zeros together with a collection of witnesses that no further zeros exist. We give a proof that the algorithm always terminates assuming two classical number-theoretic conjectures: the Skolem Conjecture (also known as the Exponential Local-Global Principle) and the p-adic Schanuel Conjecture. Preliminary experiments with an implementation of this algorithm within the tool Skolem point to the practical applicability of this method.

BibTeX - Entry

@InProceedings{bilu_et_al:LIPIcs.MFCS.2022.20,
  author =	{Bilu, Yuri and Luca, Florian and Nieuwveld, Joris and Ouaknine, Jo\"{e}l and Purser, David and Worrell, James},
  title =	{{Skolem Meets Schanuel}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{20:1--20:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16818},
  URN =		{urn:nbn:de:0030-drops-168180},
  doi =		{10.4230/LIPIcs.MFCS.2022.20},
  annote =	{Keywords: Skolem Problem, Skolem Conjecture, Exponential Local-Global Principle, p-adic Schanuel Conjecture}
}

Keywords: Skolem Problem, Skolem Conjecture, Exponential Local-Global Principle, p-adic Schanuel Conjecture
Collection: 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Issue Date: 2022
Date of publication: 22.08.2022
Supplementary Material: Software: https://skolem.mpi-sws.org

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI