一句话：引入并构造出通用 Skolem 集，使线性递推序列的零项判定在一类无限下标集合上可有效进行。
论文关注线性递推序列的 Skolem 问题：判定给定序列是否存在零项，这是数论与可判定性中长期未决的开放问题。作者引入“通用 Skolem 集”这一概念，即正整数的一个无限子集 S，满足存在有效过程，输入任意线性递推序列 u，便能判定是否存在 n∈S 使得 u(n)=0。论文的主要技术贡献是构造出这样的集合。该结果给出 Skolem 问题在受限下标集合上的一个可判定片段，为理解整体问题的难度提供了新工具与新视角。
It is a longstanding open problem whether there is an algorithm to decide the Skolem Problem for linear recurrence sequences, namely whether a given such sequence has a zero term. In this paper we introduce the notion of a Universal Skolem Set: an infinite subsetSof the positive integers such that there is an effective procedure that inputs a linear recurrence sequence u = (u(n))n ≥ 0and decides whether u(n) = 0 for some n ∈S. The main technical contribution of the paper is to exhibit such a set.
DOI 原文 ·
@inproceedings{paperbot6181,
title = {Universal Skolem Sets},
author = {Florian Luca and Joel Ouaknine and James Worrell},
booktitle = {LICS},
year = {2021},
doi = {10.1109/lics52264.2021.9470513}
}