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, 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.
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 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 0.29. We show moreover that this set has density one subject to
the Bateman-Horn conjecture. The latter is a central unifying
hypothesis concerning the frequency of prime numbers among the values
of systems of polynomials.
Submitted, 2024. 18 pages.
PDF
© 2024 Florian Luca, James Maynard, Armand Noubissie, Joël
Ouaknine, and James Worrell.