Worrell

File contents

Algorithmic Combinatorics Seminar and Computer Algebra Seminar

Title: New Developments on the Skolem Problem

Speaker: Prof. Dr. James Worrell
(Oxford University, UK)

Time: Wednesday, June 28, 2023, 13:30
Location: RISC, castle, seminar room


Abstract The Skolem Problem asks to determine whether a given integer linear recurrence sequence (LRS) has a zero term.  The problem has been studied in the context of program analysis and automata theory over many decades and it is one of the most natural restrictions of the Halting Problem whose decidability remains open.

This talk considers two recent approaches toward showing decidability of the Skolem Problem.
The first part of the talk concerns an algorithm that decides the problem on the class of simple LRS (those with simple characteristic roots) subject to two 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.

The second part of the talk concerns the notion of Universal Skolem Set: 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 the set of natural numbers is a Universal Skolem Set.  In lieu of this objective one can ask whether there exists a Universal Skolem Set of density one.  We present a recent construction of a Universal Skolem Set that has positive density unconditionally and has density one subject to the Bateman-Horn conjecture in number theory.