Skolem problem
Is there an algorithm that decides whether a linear recurrence sequence, such as a Fibonacci-like sequence, ever reaches zero?
Summary
Why it is open
A linear recurrence sequence (LRS) u of order d satisfies u(n+d) = a(d−1)u(n+d−1) + ⋯ + a(0)u(n) with a(0) ≠ 0, where d is the smallest number for which such a relation holds; its characteristic roots are the roots of the polynomial X^d − a(d−1)X^(d−1) − ⋯ − a(0) [9]. The Skolem Problem asks whether a given LRS has a zero term [9].
The Skolem–Mahler–Lech theorem states that the indices n with u(n) = 0 form a finite set together with finitely many arithmetic progressions [9]. Its core is that a non-zero, non-degenerate LRS, one in which no ratio of two distinct characteristic roots is a root of unity, has only finitely many zeros, and all known proofs of this are ineffective: it is not known how to compute those zeros [7]. A procedure to compute them would exist exactly if the Skolem Problem were decidable [7]. The problem is generally considered open since the early 1930s, because the p-adic methods behind the theorem were understood at the time not to be effective [7]. Joël Ouaknine and James Worrell note that Terence Tao called this state of affairs "faintly outrageous" and Richard Lipton a "mathematical embarrassment" [5].
Versions differ in the numbers allowed: recent papers state the problem for integer [6, 11], rational [7] or algebraic [9] sequences, and Wikipedia's list asks about algebraic ones [12]. So far only special cases are known [9]. A resolution would be an algorithm for every LRS, or a proof that none exists; no prize or committee sets the bar, and the status here follows Wikipedia's list [12].
The problem matters beyond number theory. It is connected with loop termination, formal power series, matrix semigroups, stochastic systems and control theory [9], and it is often used as a reference point to show that other open decision problems are hard [7].
What is known
Low orders (1984–2025). In the mid-1980s Mignotte, Shorey and Tijdeman and, independently, N. K. Vereshchagin showed decidability for LRS of order 4 or less, making essential use of Baker's theorem on linear forms in logarithms and of a p-adic analogue due to van der Poorten [1, 2, 5]. Decidability at order 2 is elementary, while the proofs at orders 3 and 4 use Baker's theorem [5]. More precisely, those results cover algebraic LRS of order at most 3 and real algebraic LRS of order at most 4 [1, 2, 9]; in a paper published in 2025 Piotr Bacik removed the real restriction, so that the problem is decidable for all algebraic LRS of order at most 4 [9]. Decidability is also known when at most three characteristic roots are dominant, that is, of maximal absolute value [7, 11]. The 1980s algorithms are unlikely to be implementable in practice, Yuri Bilu and colleagues write, because the constants involved are huge [7]. Even for integer sequences, decidability at order 5 is not known [9]. A proof for order 5 was announced by Halava and colleagues in a 2005 technical report; as Ouaknine and Worrell pointed out in 2012, it "seems to have a serious gap" [5]. Whether an LRS has infinitely many zeros, by contrast, was shown decidable for all LRS by Berstel and Mignotte in 1976 [5].
Complexity (2002–2026). NP-hardness, shown by Vincent Blondel and Natacha Portier in 2002 [3, 7], was the best known lower bound in 2015 [5]. In a paper published in 2026, Bacik, Ouaknine and Worrell gave a randomised algorithm for a bounded version, which asks for a zero among the first N terms with N written in binary, running in polynomial time for LRS of any fixed order [10]. As a corollary, the Skolem Problem for LRS of order at most 4 lies in the randomised class coRP, improving the previous upper bound NP^RP [10].
Conditional results (2022–2026). In 1937 Thoralf Skolem conjectured an exponential local-global principle, now called the Skolem Conjecture: if a simple LRS (one with no repeated characteristic roots), extended to negative indices, has no zero, then for some suitable integer m no term is congruent to zero modulo m [7]. It has been proved for order 2 and for certain families of order 3 [7]. In 2022 Lipton, Florian Luca, Joris Nieuwveld, Ouaknine, David Purser and Worrell proved decidability for reversible integer LRS of order at most 7, those whose extension to negative indices stays in the integers, such as the Fibonacci sequence; assuming the Skolem Conjecture, they proved it for all LRS of order 5 [6]. Bilu, Luca, Nieuwveld, Ouaknine, Purser and Worrell then gave an algorithm for simple LRS whose termination they prove assuming the Skolem Conjecture and a weak form of the p-adic Schanuel Conjecture [7]. Whenever it stops, it outputs a certificate of correctness that does not depend on either conjecture, and it is implemented in a tool called Skolem [7]. Schanuel's Conjecture over the reals also underlies Macintyre and Wilkie's conditional decidability result for the real numbers with exponentiation [7], the subject of the Papex page Tarski's exponential function problem.
A further route uses Universal Skolem Sets: infinite sets S of positive integers for which some algorithm decides whether a given LRS has a zero in S; the Skolem Problem is decidable exactly if the set of all positive integers is one [11]. In 2025 Luca, Ouaknine and Worrell called a zero "large" if its index exceeds a sixth-fold exponential of the size of the data defining the LRS [8]. They showed that the possible large zeros have null density, which gives a Universal Skolem Set of density one, and conjectured that large zeros do not exist, which would make the problem decidable [8]. In a preprint of July 2026, not peer reviewed, the same authors use a double-exponential threshold and conclude, conditionally on a strengthening of Cramér's conjecture on gaps between primes, that large zeros do not exist [11].
Positivity. The related Positivity Problem asks whether all terms of a given LRS are positive [4]. It is folklore that deciding Positivity would decide the Skolem Problem, although the reduction increases the order quadratically [5]. Ouaknine and Worrell proved Positivity, and Ultimate Positivity (all but finitely many terms positive), decidable up to order 5, and showed that order 6 would entail major breakthroughs in Diophantine approximation of transcendental numbers [4]. For the Skolem Problem, they wrote in 2015, it is not clear that a solution would necessarily entail progress in Diophantine approximation for logarithms of algebraic numbers [5].
Main approaches
Baker's method. Use Baker's theorem, which yields effective lower bounds in Diophantine approximation [5], in cases defined by how many characteristic roots have maximal absolute value [7]. Strongest evidence: decidability for all algebraic LRS of order at most 4 [9] and whenever at most three roots are dominant [7]. Main difficulty: order 5 is open even for integer sequences [9], and the constants make the algorithms impractical [7].
p-adic methods and local-global principles. Isolate zeros p-adically and certify the absence of zeros modulo suitable integers [7]. Strongest evidence: the certified algorithm for simple LRS and its implementation [7]; unconditional decidability for reversible LRS of order at most 7 [6]; p-adic analysis also isolates the candidate zeros in the coRP algorithm [10]. Main difficulty: termination rests on two unproven conjectures, and it is not known whether the Skolem Conjecture alone implies decidability of the Skolem Problem [7].
Large zeros and Universal Skolem Sets. Show that zeros cannot lie beyond an explicit bound, or decide the problem on ever larger sets of indices [8, 11]. Strongest evidence: an unconditional Universal Skolem Set of density one [8]. Main difficulty: ruling out large zeros depends on a strengthened Cramér conjecture, and the authors write that a proof "currently seems well out of reach" [11]; the best known upper bound on prime gaps, O(p^0.525), is far from Cramér's conjectured bound [11].
Open sub-questions
- Order 5. Is the Skolem Problem decidable for simple integer LRS of order 5, the case that several hardness results for other problems invoke, and which is decidable if the Skolem Conjecture holds [6, 7]?
- The Skolem Conjecture at order 3. Does the Skolem Conjecture hold for every simple LRS of order 3 extended to negative indices, beyond the families for which it is proved [7]?
- One-sided and two-sided zeros. Can the reduction of the Skolem Problem to its two-sided version, which asks for a zero at any integer index, be proved without the weak p-adic Schanuel Conjecture [7]?
- Order 4 in polynomial time. Can the coRP algorithm for order at most 4, which tests candidate zeros by arithmetic-circuit identity testing, be derandomised [10]?
- Gaps between good primes. For explicit LRS, do computed gaps between consecutive "good" primes behave as the Cramér-type hypothesis behind the conditional decidability argument assumes [11]?
Work on this in Papex
If you have a testable answer to one of the sub-questions above, you can draft it as a private hypothesis in Papex, or prepare the draft from Claude or ChatGPT with the Papex connector. You review the exact version, sign it and decide whether to publish it; a public record that names this problem is listed on this page. A Papex record shows who signed which version and when. It is not peer review and does not mean the hypothesis is correct.
Key references
- Mignotte, M., Shorey, T. N. & Tijdeman, R. (1984). The distance between terms of an algebraic recurrence sequence. Journal für die reine und angewandte Mathematik 349, 63–76. 10.1515/crll.1984.349.63 · Checked 16 Oct 2026
- Vereshchagin, N. K. (1985). Occurrence of zero in a linear recursive sequence. Mathematical Notes of the Academy of Sciences of the USSR 38(2), 609–615; Russian original in Matematicheskie Zametki 38(2). 10.1007/BF01156238 · Checked 16 Oct 2026
- Blondel, V. D. & Portier, N. (2002). The presence of a zero in an integer linear recurrent sequence is NP-hard to decide. Linear Algebra and its Applications 351–352, 91–98. 10.1016/S0024-3795(01)00466-9 · Checked 16 Oct 2026
- Ouaknine, J. & Worrell, J. (2014). Positivity problems for low-order linear recurrence sequences. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), 366–379 (published online 2013). 10.1137/1.9781611973402.27 · Checked 16 Oct 2026
- Ouaknine, J. & Worrell, J. (2015). On linear recurrence sequences and loop termination. ACM SIGLOG News 2(2), 4–13. 10.1145/2766189.2766191 · Checked 16 Oct 2026
- Lipton, R., Luca, F., Nieuwveld, J., Ouaknine, J., Purser, D. & Worrell, J. (2022). On the Skolem Problem and the Skolem Conjecture. In Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2022), 1–9. 10.1145/3531130.3533328 · Checked 16 Oct 2026
- Bilu, Y., Luca, F., Nieuwveld, J., Ouaknine, J., Purser, D. & Worrell, J. (2022). Skolem meets Schanuel. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), Leibniz International Proceedings in Informatics 241, 20:1–20:15. 10.4230/LIPIcs.MFCS.2022.20 · Checked 16 Oct 2026
- Luca, F., Ouaknine, J. & Worrell, J. (2025). On large zeros of linear recurrence sequences. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025), Leibniz International Proceedings in Informatics 345, 71:1–71:11. 10.4230/LIPIcs.MFCS.2025.71 · Checked 16 Oct 2026
- Bacik, P. (2025). Completing the picture for the Skolem Problem on order-4 linear recurrence sequences. TheoretiCS 4, 28. 10.46298/theoretics.25.28 · Checked 16 Oct 2026
- Bacik, P., Ouaknine, J. & Worrell, J. (2026). On the complexity of the Skolem Problem at low orders. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2026), 5255–5269. 10.1137/1.9781611978971.191 · Checked 16 Oct 2026
- Luca, F., Ouaknine, J. & Worrell, J. (2026). Conjectural decidability of the Skolem Problem. Preprint, arXiv:2607.15510 (version 1, 16 July 2026), not peer reviewed. Source · Checked 16 Oct 2026
- Wikipedia. List of unsolved problems in computer science (revision of 15 September 2026). Source · Checked 16 Oct 2026
Source
Open, as listed by Wikipedia · Unsolved problems in computer science. Checked 08 Oct 2026.
The status is the source’s. Papex does not decide whether a problem is solved.
Records on this problem
No public record addresses this problem yet.