We consider reachability decision problems for linear dynamical systems. Such a system in dimension d is specified by respective semialgebraic sets S,T ∈ Rd of source and target states and a matrix M ∈ Qd×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 deep theorem in arithmetic geometry, due to Bombieri and Zannier, concerning intersections of algebraic subgroups with subvarieties.
Submitted, 2024. 21 pages.
PDF
© 2023 Toghrul Karimov, Edon Kelmendi,
Joël Ouaknine, and James Worrell.