💻 computer science

On the Subspace Orbit Problem and the Simultaneous Skolem Problem

This paper establishes that the Orbit Problem is decidable with an NP^RP complexity bound when the target subspace has logarithmic dimension, while proving that the problem becomes as hard as the long-standing open Skolem Problem when the target subspace has linear dimension.

Original authors: Piotr Bacik, Anton Varonka

Published 2026-05-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Piotr Bacik, Anton Varonka

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are watching a very predictable robot move around a giant, multi-dimensional grid.

The Robot and the Grid (The Setup)
The robot starts at a specific spot. Every second, it follows a strict rule: it multiplies its current position by a fixed "magic matrix" (a grid of numbers) to find its next spot. This creates a trail of dots called an orbit.

The Question: Will this robot ever land on a specific target?
- If the target is a single dot, we already know the answer: Yes, we can calculate it quickly.
- If the target is a whole wall (a flat surface in 3D space) or a line, we also know how to solve it.
- The Problem: What if the target is a giant, complex shape (like a 4-dimensional hyper-surface)? For decades, mathematicians have been stuck. They don't know if there is a way to predict if the robot will ever hit that shape. This is known as the Subspace Orbit Problem.

The "Skolem" Monster (The Obstacle)
The reason this is so hard is linked to a famous, unsolved riddle called the Skolem Problem.
Think of the Skolem Problem as a game with a sequence of numbers. You have a rule to generate the next number based on the previous ones. The question is: Will the number zero ever appear in this sequence?

If the target shape is a "wall" (a hyperplane), the Orbit Problem is exactly the same as the Skolem Problem.
For 40+ years, no one has proven whether we can always decide if zero will appear in these sequences. It's a "locked door" in mathematics.

The Paper's New Key (The Solution)
The authors of this paper, Piotr Bacik and Anton Varonka, didn't try to break the lock on the 4-dimensional door directly. Instead, they found a clever way to look at the problem from a different angle.

They introduced the idea of "Inherent Dimension."
Imagine the robot is moving in a 100-dimensional room. But, because of its starting position and its movement rules, it's actually only moving inside a tiny, 3-dimensional corner of that room. The "inherent dimension" is the size of that actual space the robot uses, not the size of the whole room.

The Main Discovery: "The More Space, The Easier It Gets"
The paper proves a surprising counter-intuitive fact: The harder the target shape is, the easier it is to solve if the robot's "inherent dimension" is huge.

They found a "sweet spot" where the problem becomes solvable.

If the target shape is small (low dimension), it's hard.
But if the robot's movement space is logarithmically large compared to the target size, the problem becomes decidable (we can write an algorithm to solve it).

The Magic Trick: The "Simultaneous Skolem" Game
To solve this, they used a trick called the Simultaneous Skolem Problem.
Imagine you have several different number sequences running at the same time. You want to know if they all hit zero at the exact same moment.

Usually, checking if one sequence hits zero is hard.
But if you have many sequences, you can mix them together (like mixing paints) to create a new, "simpler" sequence.
The authors showed that if you have enough sequences (enough "dimensions"), you can always mix them to create a simpler sequence that falls into a known "safe zone" (called the MSTV class).
Once you are in this safe zone, you can easily calculate exactly when the zeros happen.

The Results in Plain English

We can solve it for specific sizes: They proved we can definitely solve the problem if the robot's movement space is 6-dimensional and the target is 4-dimensional, or if the space is 9-dimensional and the target is 5-dimensional, and so on.
The General Rule: They proved that for any target size, if the robot's movement space is large enough (specifically, if the space is roughly $2 \times \log_3(\text{target size})$ ), we can solve it.
The Complexity: They also showed how hard it is to solve.
- If the target size is fixed (e.g., always looking for a 4D wall), the problem is solvable with a reasonable amount of computer power (in a class called NPRP).
- If the total room size is fixed, it's even easier (solvable in coRP).

The Warning (The Hardness Result)
The paper also draws a line in the sand. They showed that if someone ever finds a magic algorithm that can solve the Orbit Problem for any target size that is a fixed fraction of the room size (e.g., "I can solve it for any target that is 10% of the room size"), then we would have solved the Skolem Problem forever.
Since the Skolem Problem has been unsolved for decades, this implies that a general solution for all sizes is likely impossible with current methods. The "logarithmic" solution they found is likely the best we can do.

Summary Analogy
Imagine trying to find a needle in a haystack.

Old View: "The haystack is too big; we can never find the needle."
This Paper's View: "If the haystack is massively huge compared to the needle, we can actually use a special magnet to find it. But if the haystack is only slightly bigger than the needle, we are still stuck."

They didn't solve the impossible riddle of the small haystack, but they proved that for the giant haystacks, we finally have a way to find the needle.

Technical Summary: On the Subspace Orbit Problem and the Simultaneous Skolem Problem

1. Problem Definition and Context
The paper investigates the Subspace Orbit Problem, a generalization of the classical Orbit Problem. Given a linear dynamical system (LDS) defined by a matrix $A \in K^{d \times d}$ and an initial vector $x \in K^d$ (where $K$ is a field, typically $\mathbb{Q}$ ), the orbit is the set $B(A, x) = \{x, Ax, A^2x, \dots\}$ . The problem asks whether this orbit intersects a given target subspace $S \subseteq K^d$ .

Historical Context: When $S$ is a single point, the problem is decidable in polynomial time (Kannan and Lipton). When $S$ is a hyperplane (codimension 1), the problem is equivalent to the Skolem Problem for linear recurrence sequences (LRS), which has been open for decades.
Current State of the Art: Chonev, Ouaknine, and Worrell established decidability for target subspaces of dimension up to 3 (in arbitrary ambient dimension). Decidability for dimension 4 remains open.
The Challenge: The difficulty arises from the "Skolem barrier." The paper introduces the concept of inherent dimension (the Krylov dimension of a reduced, non-degenerate LDS) to distinguish between the ambient dimension $d$ and the effective complexity of the system. The authors note that while the problem is Skolem-hard for $(d, t) = (5, 4)$ , it becomes tractable for $(d, t) = (6, 4)$ , motivating a study of the relationship between the inherent dimension $d$ and the target dimension $t$ .

2. Methodology and Core Approach
The authors establish a formal equivalence between the Subspace Orbit Problem and the Simultaneous Skolem Problem (SimSkolem).

Equivalence: Deciding if an orbit hits a subspace of codimension $k$ is equivalent to deciding if $k$ linearly independent LRS share a common zero (Theorem 8).
Reduction Strategy: The central technique involves finding a linear combination $w = \sum \beta_i u^{(i)}$ of the $k$ LRS such that $w$ falls into the MSTV class (Mignotte, Shorey, Tijdeman, Vereshchagin). The MSTV class consists of LRS with a limited number of dominant roots (at most 3 for Archimedean absolute values, at most 2 for non-Archimedean).
Theorem 11 (Dominant Term Bound): A key theoretical tool is a generalization of previous lemmas, proving that for any set of algebraic numbers with equal modulus, there exists an absolute value with respect to which at most $\lfloor t/2 \rfloor$ terms are dominant (where $t$ is the number of terms).
MSTV-Reducibility: An instance is "MSTV-reducible" if a linear combination exists that lies in the MSTV class. If such a combination exists, the zero set of the combination is finite and computable (via Baker's theorem techniques), allowing one to check if any of these zeros are common to all original sequences.

3. Key Contributions and Results

Specific Decidability Results: The authors prove decidability for specific pairs of $(d, k)$ (where $d$ is the order of the LRS and $k$ is the number of simultaneous sequences), which correspond to $(d, t)$ for the Orbit Problem:
- SimSkolem(6, 2) and Orbit(6, 4) are decidable.
- SimSkolem(9, 4) and Orbit(9, 5) are decidable.
- SimSkolem(12, 6) and Orbit(12, 6) are decidable.
- These results are shown to be optimal for the techniques used; examples are provided where $(5, 1)$ , $(8, 3)$ , and $(11, 5)$ are not MSTV-reducible.
General Decidability Theorem: The paper establishes a broad decidability result based on the relationship between the inherent dimension and the target dimension:
- Theorem 2: SimSkolem $(d, k)$ is decidable for all pairs satisfying $d - k \le 2 \log_3 d$ .
- Corollary: The Subspace Orbit Problem is decidable whenever the target dimension $t$ satisfies $t \le 2 \log_3 d$ .
- This implies that for any fixed target dimension $t$ , the problem is decidable provided the inherent dimension of the LDS is sufficiently large.
Hardness Reduction: The paper provides a reduction showing that if there exists a constant $C \in (0, 1)$ such that Orbit $(d, t)$ is decidable for all $t \le Cd$ , then the general Skolem Problem would be decidable. This suggests that the authors' results (where $t$ is logarithmic in $d$ ) are likely the best possible without resolving the Skolem Problem itself.
Complexity Bounds:
- For fixed target dimension $t$ , the problem Orbit $_{\mathbb{Q}}(d, t)$ (under the logarithmic constraint) is in NPRP (Nondeterministic Polynomial time with Randomized Polynomial verification, specifically NPEqSLP).
- If the ambient dimension $d$ is fixed, the problem lies in coRP.
- The complexity analysis relies on bounding the height of coefficients in the linear combinations and the magnitude of the zeros, utilizing Siegel's Lemma and properties of algebraic number heights.

4. Significance and Claims
The paper claims to advance the state of the art in the Orbit Problem by:

Extending Decidability: Moving beyond the dimension 3 barrier established by Chonev et al., providing new decidable instances for dimensions 4, 5, and 6 (in specific high-dimensional contexts).
Characterizing the Boundary: Identifying that the problem becomes tractable when the target dimension is logarithmic relative to the system's inherent dimension, contrasting with the hardness when the target dimension is linear in the system dimension.
Methodological Insight: Demonstrating that the "Simultaneous Skolem" perspective, combined with the MSTV class reduction, allows for the resolution of higher-order recurrence problems that are currently intractable for single sequences.
Limitations: The authors explicitly state that their results are the best possible with current MSTV-based techniques, as evidenced by the construction of non-reducible instances (Example 21) and the hardness reduction to the Skolem Problem. They do not claim to solve the general Skolem Problem or the Subspace Orbit Problem for all dimensions.

The work is framed as a significant step in understanding the decidability landscape of linear dynamical systems, bridging the gap between the known polynomial-time case (point targets) and the open Skolem case (hyperplane targets).

More like this