一句话：证明线性动力系统多重可达性在 d=10、m=9 时不可判定，并给出二维平面中旋转矩阵与半平面目标的可判定性。
论文研究线性动力系统中的多重可达性：给定半代数源集 S、目标集 T⊆ℝ^d 与有理矩阵 M，判定是否存在 x∈S，使其在 M 下的轨道与 T 至少有 m 个不同交点。m=1 的普通可达性可归约到线性递推序列的 Skolem 与正性问题，其可判定性长期未决；多重情形则显著不同。作者证明，当 d=10 且固定 m=9 时该问题不可判定；该构造还表明 d∈{3,…,9} 的判定程序将蕴含丢番图方程有效解的重大新结果。随后聚焦 d=2 平面情形，得到两个正面结果：M 为旋转矩阵时可判定；对半平面目标，无需限制 M 也可判定。前者依赖 Bombieri 与 Zannier 关于代数子群与子簇相交的算术几何定理。
We consider reachability problems for linear dynamical systems. In dimension d these problems are specified by respective semialgebraic sets S, T ⊆ ℝdof source and target states and a matrix $M \in {\mathbb{Q}^{d \times d}}$. The task is to determine whether there is a point in S whose orbit under M intersects the target T in at least m distinct points. The case m = 1 (mere reachability) can be reduced to mild generalisations of the Skolem and Positivity Problems for linear recurrence sequences, whose decidability has been open for many decades. The situation is markedly different for multiple reachability, where m can be greater than one. In this paper, we prove that multiple reachability is undecidable already in dimension d = 10 with fixed multiplicity m = 9. Since our undecidability construction also shows that decision procedures for dimension d ∈ {3, … , 9} would entail significant new results on effective solutions of Diophantine equations, we subsequently focus on the case d = 2, that is, multiple reachability in the plane. Here we obtain two positive results. We show that multiple reachability is decidable if the matrix M is a rotation and it is also decidable without restriction on M for halfplane targets. The former result relies on a theorem in arithmetic geometry, due to Bombieri and Zannier, concerning intersections of algebraic subgroups with subvarieties.
DOI 原文 ·
@inproceedings{paperbot8626,
title = {Multiple Reachability in Linear Dynamical Systems},
author = {Toghrul Karimov and Edon Kelmendi and Joël Ouaknine and James Worrell},
booktitle = {LICS},
year = {2025},
doi = {10.1109/lics65433.2025.00055}
}