On the Subspace Orbit Problem and the Simultaneous Skolem Problem

2026/01/26 by Piotr Bacik, Anton Varonka · 1 voice
Computer Science · #cs.DM #cs.LO

paper · pdf · doi:10.48550/arxiv.2601.18349

arxiv published 2026/01/26 · arxiv updated 2026/05/14

Abstract

The Orbit Problem asks whether the orbit of a point under a matrix reaches a given target set. When the target is a single point, the problem was shown to be decidable in polynomial time by Kannan and Lipton. This decidability result was later extended by Chonev et al. to targets of dimension 3 (in arbitrary ambient dimension), but decidability remains open for subspaces of dimension 4. At the other extreme, the special case of the Orbit Problem in which the target set is a hyperplane of codimension 1 is equivalent to the Skolem Problem for linear recurrence sequences, whose decidability has been open for many decades. In this paper, we show that the Orbit Problem is decidable if the target subspace has dimension logarithmic in the dimension of the orbit. Over rationals, we moreover obtain a complexity bound NP^RP in this case. On the other hand, we show that the version of the Orbit Problem where the dimension of the target subspace is linear in the dimension of the orbit is as hard as the Skolem Problem.

Citations

• On the Complexity of the Skolem Problem at Low Orders
• On the p-adic Skolem Problem
• Skolem Problem for Linear Recurrence Sequences with 4 Dominant Roots (after Mignotte, Shorey, Tijdeman, Vereshchagin and Bacik)
• Completing the picture for the Skolem Problem on order-4 linear recurrence sequences
• Multiple Reachability in Linear Dynamical Systems
• What's Decidable about Discrete Linear Dynamical Systems?
• Skolem Meets Schanuel
• The Pseudo-Reachability Problem for Diagonalisable Linear Dynamical Systems
• On LTL Model Checking for Low-Dimensional Discrete Linear Dynamical Systems
• The Semialgebraic Orbit Problem
• The Polyhedron-Hitting Problem
• On the Complexity of the Orbit Problem
• On Siegel's lemma
• A note on recurring series

Discussions

• Piotr Bacik, Anton Varonka: On the Subspace Orbit Problem and the Simultaneous Skolem Problem https://arxiv.org/abs/2601.18349 https://arxiv.org/pdf/2601.18349 https://arxiv.org/html/2601.18349 [bsky, 0 points, 0 comments]

Related

• Deciding subspace reachability problems with application to Skolem's Problem
• On the Complexity of the Orbit Problem
• The Semialgebraic Orbit Problem
• Orbit Problem Revisited
• The Polyhedron-Hitting Problem