TOPICS
Search

Skolem Problem


The Skolem problem is the decision problem of determining whether a recurrence sequence over the rational numbers contains zero. Thus, given initial values and coefficients a_1,...,a_k with a_k!=0 in the linear recurrence equation

 u_(n+k)=a_1u_(n+k-1)+...+a_ku_n,

the question is whether u_n=0 for some nonnegative integer n.

The problem is decidable when the linear recurrence equation has order at most four, but the general case remains open. Order five is the first unresolved order (Lipton et al. 2022). The Skolem-Mahler-Lech theorem shows that the indices at which it vanishes consist of finitely many exceptional indices together with finitely many full arithmetic progressions, but it does not provide a general effective method for finding the exceptional indices.


See also

Linear Recurrence Equation, Orbit Problem, Recurrence Sequence, Skolem-Mahler-Lech Theorem

Explore with Wolfram|Alpha

References

Lipton, R. J.; Luca, F.; Nieuwveld, J.; Ouaknine, J.; Purser, D.; and Worrell, J. "On the Skolem Problem and the Skolem Conjecture." In LICS '22: Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science. (Ed. C. Baier and D. Fisman). New York: ACM, pp. 5:1-5:9, 2022. https://doi.org/10.1145/3531130.3533328.Ouaknine, J. and Worrell, J. "Decision Problems for Linear Recurrence Sequences." In Reachability Problems: 6th International Workshop, RP 2012 (Ed. A. Finkel, J. Leroux, and I. Potapov). Berlin, Germany: Springer, pp. 21-28, 2012. https://doi.org/10.1007/978-3-642-33512-9_3.

Cite this as:

Weisstein, Eric W. "Skolem Problem." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/SkolemProblem.html

Subject classifications