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 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.
Accepted to TheoretiCS, 2026. 26 pages.
PDF
© 2026 Florian Luca, James Maynard, Armand Noubissie, Joël
Ouaknine, and James Worrell.