hide
Free keywords:
Computer Science, Discrete Mathematics, cs.DM,Mathematics, Number Theory, math.NT
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, (weighted) automata
theory, and the analysis of linear dynamical systems, amongst many others.
Decidability of the Skolem Problem 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.
Recently, a new approach to the Skolem Problem was initiated via the notion
of a Universal Skolem Set: a set $\mathbf{S}$ of positive integers such that it
is decidable whether a given non-degenerate linear recurrence sequence has a
zero in $\mathbf{S}$. Clearly, proving decidability of the Skolem Problem is
equivalent to showing that $\mathbb{N}$ is a Universal Skolem Set. The main
contribution of the present paper is to exhibit a Universal Skolem Set of
positive density that moreover has density one subject to the Bateman-Horn
conjecture in number theory. The latter is a central unifying hypothesis
concerning the frequency of prime numbers among the values of systems of
polynomials, and provides a far-reaching generalisation of many classical
results and conjectures on the distribution of primes.
