2025/07/15 by Piotr Bacik, Joël Ouaknine, Bacik, Piotr +3
Computer Science · #Complexity and Algorithms in Graphs #Polynomial and algebraic computation #Cryptography and Data Security
paper · pdf · doi:10.48550/arxiv.2507.11234
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 ∈ \mathbb 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∈ \mathbb 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.