On the complexity of the Skolem Problem at low orders

Conference item

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.

Authors: Bacik, P; Ouaknine, J; Worrell, J

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Society for Industrial and Applied Mathematics
• Host title: Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
• Pages: 5255-5269
• Publication date: 2026-01-01
• Acceptance date: 2025-10-03
• Event title: ACM-SIAM Symposium on Discrete Algorithms (SODA 2026)
• Event location: Vancouver, Canada
• Event website: https://www.siam.org/conferences-events/siam-conferences/soda26/
• Event start date: 2026-01-11
• Event end date: 2026-01-14
• DOI: 10.1137/1.9781611978971.191
• EISBN: 9781611978971
• Language: English