一句话：证明可逆 7 阶及以下线性递推序列的 Skolem 问题可判定，并在 Skolem 猜想下给出 5 阶判定过程。
Skolem 问题询问给定的整数线性递推序列（LRS）是否存在零项，其一般可判定性长期未解；此前仅知 4 阶及以下可判定。本文研究更高阶情形。作者首先利用可逆 LRS 的结构，证明可逆 LRS 在 7 阶及以下时 Skolem 问题可判定；可逆性指其唯一双无限延拓仍取整数值，Fibonacci 序列是典型例子。其次，在数论中称为指数局部-全局原理的 Skolem 猜想下，作者证明 5 阶 LRS 的 Skolem 问题可判定，并给出具体求解过程。结果推进了该问题已知可判定边界，但更高阶的无条件可判定性仍未解决。
It is a longstanding open problem whether there is an algorithm to decide the Skolem Problem for linear recurrence sequences (LRS) over the integers, namely whether a given such sequence has a zero term (i.e., whether un = 0 for some n). A major breakthrough in the early 1980s established decidability for LRS of order 4 or less, i.e., for LRS in which every new term depends linearly on the previous four (or fewer) terms. The Skolem Problem for LRS of order 5 or more, in particular, remains a major open challenge to this day. Our main contributions in this paper are as follows: First, we show that the Skolem Problem is decidable for reversible LRS of order 7 or less. (An integer LRS is reversible if its unique extension to a bi-infinite LRS also takes exclusively integer values; a typical example is the classical Fibonacci sequence, whose bi-infinite extension is ⟨…, 5, −3, 2, −1, 1, 0, 1, 1, 2, 3, 5, …⟩.) Second, assuming the Skolem Conjecture (a central hypothesis in Diophantine analysis, also known as the Exponential Local-Global Principle), we show that the Skolem Problem for LRS of order 5 is decidable, and exhibit a concrete procedure for solving it.
@inproceedings{LiptonLNOP022,
title = {On the Skolem Problem and the Skolem Conjecture},
author = {Richard Lipton and Florian Luca and Joris Nieuwveld and Joël Ouaknine and David Purser and James Worrell},
booktitle = {LICS},
year = {2022},
doi = {10.1145/3531130.3533328}
}