The Skolem Problem asks to determine whether a given linear recurrence sequence (LRS) over the integers contains a zero, while the Positivity Problem asks whether all of its terms are non-negative. The decidability of both problems has been open for many decades, despite the ubiquity of LRS and the abundance of powerful mathematical tools for their analysis. We survey the state of the art on these two problems and their natural variants, including the Bi-Skolem and Ultimate Positivity Problems. We describe known decidability results for low-order sequences, as well as conditional decidability results predicated on classical number-theoretic conjectures (most notably the Exponential Local-Global Principle, the p-adic Schanuel Conjecture, and Cramér-type heuristics on prime gaps). We pay particular attention to recent developments, including complexity advances placing the Skolem Problem at low orders in randomized polynomial time, the construction of Universal Skolem Sets of density one, algorithmic developments around the SKOLEM tool, and Diophantine hardness barriers for the Positivity Problem beyond order 5. We also exhibit two concrete integer LRS, of orders 6 and 10, for which we are currently unable to solve the Skolem and Positivity Problems respectively. We close with a tour d'horizon of related problems and applications, including the Skolem Problem in positive characteristic, continuous-time analogues, robust and pseudo-variants, the role of Skolem and Positivity as benchmarks for hardness in the algorithmic verification of loop termination and probabilistic systems, and a list of what we view as the central open problems in the area.
Submitted, 2026. 59 pages.
PDF
© 2026 Piotr Bacik, Toghrul Karimov, Florian Luca, Joris Nieuwveld,
Joël Ouaknine, David Purser, and James Worrell.