On the Subspace Orbit Problem and the Simultaneous Skolem Problem Conference: Mystery Event; One Day; In Mystery Town CCS: Theory of computation Logic and verification

Piotr Bacik, Anton Varonka · 2026

Read On the Subspace Orbit Problem and the Simultaneous Skolem Problem Conference: Mystery Event; One Day; In Mystery Town CCS: Theory of computation Logic and verification by Piotr Bacik, Anton Varonka (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-18349.txt.

Introduction

Piotr Bacik and Anton Varonka take on two linked asks in the maths of change and reach. The first ask is old: start with a point, apply a fixed rule again and again, and ask if the path ever hits a set mark. When the mark is one point, past work showed the ask can be solved, and fast. Later work stretched that proof to wider marks.

The pair look at a harder form in which the space is cut by a rule at the same time. They also take on a twin ask about paths that must hit more than one mark in step. These asks sit at the base of checks on code and on plans that must be safe. A firm yes or no here helps prove that a design can or cannot reach a bad state.

Catalog record

CREATORPiotr Bacik, Anton Varonka
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE119 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-18349

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the Subspace Orbit Problem and the Simultaneous Skolem Problem Conference: Mystery Event; One Day; In Mystery Town CCS: Theory of computation Logic and verification Piotr Bacik, Anton Varonka 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 𝐍𝐏 𝐑𝐏 {\mathchoice{\hbox{$\mathbf{NP}$}}{\hbox{$\mathbf{NP}$}}{\mathbf{NP}}{\mathbf{NP}}}^{{\mathchoice{\hbox{$\mathbf{RP}$}}{\hbox{$\mathbf{RP}$}}{\mathbf{RP}}{\mathbf{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. 1. Introduction A linear dynamical system (LDS) consists of a matrix A\in\mathbb{K}^{d\times d} and initial vector \bm{x}\in\mathbb{K}^{d} , where \mathbb{K} is a field. An LDS (A,\bm{x}) defines an orbit \mathcal{B}(A,\bm{x})=\{\bm{x},A\bm{x},A^{2}\bm{,}\dots\} given by the image of \bm{x} under repeated application of A . The Orbit Problem, introduced by Harrison ( 18 ) in the context of the reachability problem for linear sequential machines, asks whether a given LDS (A,\bm{x})\subseteq\mathbb{Q}^{d\times d}\times\mathbb{Q}^{d} reaches a given point \bm{y}\in\mathbb{Q}^{d} , that is, whether \bm{y}\in\mathcal{B}(A,\bm{x}) . A decade later, this problem was shown to be decidable in polynomial time by Kannan and Lipton ( 20 ; 19 ) . A natural generalisation to the problem where the target point \bm{y} is replaced by a target subspace S\subseteq\mathbb{Q}^{d} was discussed in the journal version of their work ( 19 ) . Subspace Orbit Problem . Given an LDS (A,\bm{x})\in\mathbb{K}^{d\times d}\times\mathbb{K}^{d} and a subspace S\subseteq\mathbb{K}^{d} , decide whether \mathcal{B}(A,\bm{x})\cap S\neq\varnothing . Around 30 years later, a significant step forward was achieved by Chonev, Ouaknine and Worrell ( 12 ; 14 ) , who showed the Subspace Orbit Problem is in {\mathchoice{\hbox{$\mathbf{NP}$}}{\hbox{$\mathbf{NP}$}}{\mathbf{NP}}{\mathbf{NP}}}^{\mathchoice{\hbox{$\mathbf{RP}$}}{\hbox{$\mathbf{RP}$}}{\mathbf{RP}}{\mathbf{RP}}} when the dimension of the target subspace is at most 3, regardless of the dimension d of the ambient space. To date, this is the state of the art for the Subspace Orbit Problem, with decidability for higher-dimensional target subspaces remaining a major open problem. Other domains for targets have been studied in ( 13 ; 3 ; 24 ) , among which one finds polyhedra and more generally semi-algebraic sets. Cumulatively, we call these problems the orbit problems . A plethora of further generalisations and variants of orbit problems may be found in the literature ( 7 ; 2 ; 23 ; 16 ; 17 ) . An important application of the orbit problems comes from program analysis: note that LDS can be viewed as linear while loops \bm{v}\leftarrow\bm{x};\kern 5.0pt\textbf{while}\ \textsc{cond}(v)\ \textbf{do}\kern 5.0pt\bm{v}\leftarrow A\cdot\bm{v}, where reachability of a target S corresponds to the halting problem with \textsc{cond}(\bm{v})=\bm{v}\not\in S ; that is, where the looping condition is expressed as a finite disjunction of linear disequalities. We refer the reader to ( 21 ; 34 ; 22 ) for further discussions of LDS and loops. Taking one step back, a major obstruction on the way to deciding orbit problems is the Skolem Problem. A linear recurrence relation of order d over a field \mathbb{K} is an equation (1.1) u_{n}=c_{1}u_{n-1}+\dots+c_{d}u_{n-d}, where c_{i}\in\mathbb{K} for 1\leq i\leq d and c_{d}\neq 0 . A linear recurrence sequence (LRS) u=\langle u_{n}\rangle_{n\in\mathbb{N}} is a sequence of elements in \mathbb{K} satisfying ( 1.1 ). In the case that \mathbb{K} has characteristic 0, the set \mathcal{Z}(u)=\{n\in\mathbb{N}:u_{n}=0\} of zero terms of an LRS is described by the theorem of Skolem, Mahler, and Lech ( 36 ; 29 ; 27 ) : Theorem 1.1 (Skolem-Mahler-Lech). The zero set \mathcal{Z}(u) is a union of finitely many arithmetic progressions and a finite set. The proof is unfortunately ineffective — though we can find the arithmetic progressions, there is no known algorithm to compute the exceptional finite set. Computing this finite set is equivalent to solving the Skolem Problem . Skolem Problem . Given an LRS u , decide whether \mathcal{Z}(u) is non-empty. We denote the Skolem Problem on \mathbb{K} -LRS that satisfy a recurrence relation of order d as \textnormal{{Skolem}}_{\mathbb{K}}(d) ; when \mathbb{K}=\smash{\overline{\mathbb{Q}}} we simply write \textnormal{{Skolem}}(d) . It is straightforward to see that deciding the Skolem Problem is equivalent to deciding the Subspace Orbit Problem with a hyperplane target, that is, a linear subspace of \mathbb{K}^{d} of dimension d-1 . However, despite being posed close to a century ago, decidability of the Skolem Problem has stubbornly remained open; decidability is known for \textnormal{{Skolem}}(4) ( 37 ; 39 ; 6 ) , and furthermore, \textnormal{{Skolem}}_{\mathbb{Q}}(4) lies in \mathbf{coRP} ( 5 ) , but \textnormal{{Skolem}}_{\mathbb{Q}}(5) remains open ( 9 ) . In the orbit problems terminology, the decidability of reaching a 4-dimensional subspace of \mathbb{Q}^{5} is open. When considering non-degenerate sequences, the statement of Theorem 1.1 can be further refined. Define the characteristic polynomial of u satisfying Eq. 1.1 to be \displaystyle g(x)=x^{d}-c_{1}x^{d-1}-\dots-c_{d}\,. We say u is non-degenerate if no ratio of distinct roots of its characteristic polynomial is a root of unity. The Skolem-Mahler-Lech Theorem shows that a non-degenerate LRS is either identically zero or has finitely many zero terms. Crucially, for every LRS \langle u_{n}\rangle_{n\in\mathbb{N}} there exists an integer L such that each subsequence \langle u_{Ln+r}\rangle_{n\in\mathbb{N}} with 0\leq r\leq L-1 is either identically zero or non-degenerate. The Reduced Subspace Orbit Problem The Subspace Orbit Problem with target space S\subseteq\mathbb{Q}^{5} of dimension 4 is equivalent to \textnormal{{Skolem}}_{\mathbb{Q}}(5) , the decidability of which appears to be beyond the reach of current methods. A natural question is to ask whether the problem with target dimension 4 becomes tractable when the dimension of the LDS is sufficiently large. However, for this we need a sufficiently robust notion of the dimension of an LDS. For example, if (A,\bm{x})\subseteq\mathbb{K}^{d\times d}\times\mathbb{K}^{d} , then one might naïvely take the dimension of (A,\bm{x}) to be the ambient dimension d . We argue against it, as any LDS may trivially be viewed as being inside a space of arbitrarily large dimension by adding new components to A,\bm{x} that are zero everywhere. Instead, we introduce the notion of reduced LDS, and of the inherent dimension of an LDS. Call a LDS (A,\bm{x}) non-degenerate if no ratio of distinct eigenvalues of the matrix A is a root of unity. Define the Krylov dimension of an orbit to be the smallest dimension of any subspace that contains it. We say an LDS (A,\bm{x})\subseteq\smash{\overline{\mathbb{Q}}}^{d\times d}\times\smash{\overline{\mathbb{Q}}}^{d} is reduced if it is non-degenerate and the Krylov dimension of any tail of its orbit is d ; that is, \spn\{A^{n}\bm{x}:n\geq m\}=d for all m\geq 0 . By removing finitely many initial points, taking sub-orbits and restricting to smaller subspaces (see Section 2 ), the orbit of any LDS may be rewritten as a union of

Read the complete text