Item

Abstract

We consider reachability decision problems for linear dynamical systems:
Given a linear map on $\mathbb{R}^d$ , together with source and target sets,
determine whether there is a point in the source set whose orbit, obtained by
repeatedly applying the linear map, enters the target set. When the source and
target sets are semialgebraic, this problem can be reduced to a
point-to-polytope reachability question. The latter is generally believed not
to be substantially harder than the well-known Skolem and Positivity Problems.
The situation is markedly different for multiple reachability, i.e. the
question of whether the orbit visits the target set at least m times, for some
given positive integer m. In this paper, we prove that when the source set is
semialgebraic and the target set consists of a hyperplane, multiple
reachability is undecidable; in fact we already obtain undecidability in
ambient dimension d = 10 and with fixed m = 9. Moreover, as we observe that
procedures for dimensions 3 up to 9 would imply strong results pertaining to
effective solutions of Diophantine equations, we mainly focus on the affine
plane ($\mathbb{R}^2$). We obtain two main positive results. We show that
multiple reachability is decidable for halfplane targets, and that it is also
decidable for general semialgebraic targets, provided the linear map is a
rotation. The latter result involves a new method, based on intersections of
algebraic subgroups with subvarieties, due to Bombieri and Zannier.