The Skolem Problem asks to determine whether a given linear recurrence
sequence (LRS)
❬un❭n=0∞
over the integers has a zero term, that is, whether there exists
n such that un = 0. Decidability of the problem
is open in general, with the most notable positive result being a
decision procedure for LRS of order at most 4.
In this paper we consider a bounded version of the Skolem Problem, in
which the input consists of an LRS
❬un❭n=0∞
and a bound N ∈ N (with all integers written in binary), and
the task is to determine whether there exists
n ∈ {0, …, N} such that un = 0.
We give a randomised algorithm for this problem that, for all
d ∈ N, runs in polynomial time on the class of LRS of
order at most d. As a corollary we show that the (unrestricted)
Skolem Problem for LRS of order at most 4 lies in coRP, improving the
best previous upper bound of NPRP.
The running time of our algorithm is exponential in the order of the
LRS--a dependence that appears necessary in view of the NP-hardness
of the Bounded Skolem Problem. However, even for LRS of a fixed order,
the problem involves detecting zeros within an exponentially large
range. For this, our algorithm relies on results from p-adic analysis
to isolate polynomially many candidate zeros and then test in
randomised polynomial time whether each candidate is an actual zero by
reduction to arithmetic-circuit identity testing.
Submitted, 2025. 19 pages.
PDF
© 2025 Piotr Bacik, Joël Ouaknine, and James Worrell.