# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Multiple Reachability in Linear Dynamical Systems

##### MPS-Authors

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:2403.06515.pdf

(Preprint), 507KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Karimov, T., Kelmendi, E., Ouaknine, J., & Worrell, J. (2024). Multiple Reachability in Linear Dynamical Systems. Retrieved from https://arxiv.org/abs/2403.06515.

Cite as: https://hdl.handle.net/21.11116/0000-000F-5B85-5

##### 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.

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.