On the Complexity of the Skolem Problem at Low Orders

The Skolem Problem asks to determine whether a given linear recurrence sequence (LRS) ⟨u n ⟩ ∞ n=0 over the integers has a zero term, that is, whether there exists n such that u n = 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 ⟨u n ⟩ ∞ 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 u n = 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 NP RP .

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.