Skolem Meets Bateman-Horn

Abstract

The Skolem Problem asks to determine whether a given integer linear recurrence sequence has a zero term. This problem arises across a wide range of topics in computer science, including loop termination, formal languages, automata theory, and control theory. Decidability is notoriously open; the state of the art is a decision procedure for recurrences of order at most 4: an advance achieved some 40 years ago, based on Baker's theorem on linear forms in logarithms of algebraic numbers. A new approach to the Skolem Problem was recently initiated in [LOW21, LOW22] via the notion of a Universal Skolem Set -- a set $S$ of positive integers such that it is decidable whether a given non-degenerate linear recurrence sequence has a zero in $S$. Clearly, proving decidability of the Skolem Problem is equivalent to showing that $\mathbb{N}$ itself is a Universal Skolem Set. The main contribution of the present paper is to construct a Universal Skolem Set that has lower density at least $1/8$. We show moreover that this set has density $1$ subject to Martin's uniform formulation of the Bateman--Horn conjecture. The latter is a far-reaching quantitative hypothesis concerning the frequency of primes among the values of systems of polynomials.