A universal Skolem set of positive lower density

Conference item

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 .

Authors: Luca, F; Ouaknine, J; Worrell, J

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Host title: Leibniz International Proceedings in Informatics (LIPIcs)
• Volume: 241
• Pages: 73:1--73:12
• Article number: 73
• Publication date: 2022-08-22
• Event title: 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
• Event location: Vienna, Austria
• Event website: https://www.ac.tuwien.ac.at/mfcs2022/
• Event start date: 2022-08-22
• Event end date: 2022-08-26
• DOI: 10.4230/LIPIcs.MFCS.2022.73
• ISSN: 1868-8969
• ISBN: 9783959772563
• Language: English
• Keywords: exponential diophantine equations; Skolem Problem; sieve methods; FFR; linear recurrence sequences
• Subjects: Computing methodologies; Symbolic and algebraic algorithms; Number theory algorithms