pith. sign in

arxiv: 2601.18349 · v2 · pith:CCRLCAFDnew · submitted 2026-01-26 · 💻 cs.DM · cs.LO

On the Subspace Orbit Problem and the Simultaneous Skolem Problem

Piotr Bacik , Anton Varonka This is my paper

Pith reviewed 2026-05-21 15:22 UTC · model grok-4.3

classification 💻 cs.DM cs.LO
keywords Orbit ProblemSkolem Problemlinear recurrence sequencesdecidabilitysubspace reachabilitymatrix orbitscomputational complexity
0
0 comments X

The pith

The Orbit Problem is decidable when the target subspace has dimension logarithmic in the ambient dimension.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that reachability of a matrix orbit into a target subspace is decidable provided the subspace dimension is at most logarithmic in the ambient dimension. Over the rationals the same algorithm places the problem in NP^RP. When the target dimension instead grows linearly with the ambient dimension, the problem is shown to be computationally as hard as the long-open Skolem Problem. The result extends the known polynomial-time case for a single point and the decidability result for dimension-3 targets.

Core claim

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.

What carries the argument

A dimension-dependent reduction that converts the logarithmic-dimensional reachability question into an instance whose size is polynomial in the input, thereby inheriting decidability and NP^RP membership from known algorithms for low-dimensional cases.

If this is right

  • Decidability holds for all target subspaces of dimension O(log n) in ambient dimension n.
  • Over the rationals the same instances lie in NP^RP.
  • Linear-dimensional targets are at least as hard as Skolem's problem for linear recurrence sequences.
  • The gap between logarithmic and linear dimension marks the current boundary between known decidable and Skolem-hard regimes.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The logarithmic threshold may be improvable to a slightly larger function of n, such as polylog, without changing the proof strategy.
  • Similar dimension-restricted decidability results could apply to the simultaneous Skolem problem mentioned in the title.
  • If the logarithmic bound is tight, intermediate dimensions between log n and linear n would become the next natural target for complexity classification.

Load-bearing premise

The target subspace dimension must remain at most logarithmic in the ambient dimension; without this bound the reduction technique fails and the problem becomes equivalent to the unresolved Skolem case.

What would settle it

An explicit matrix, starting vector, and logarithmic-dimensional target subspace for which an algorithm decides reachability in time outside NP^RP, or for which no algorithm exists.

Figures

Figures reproduced from arXiv: 2601.18349 by Anton Varonka, Piotr Bacik.

Figure 1
Figure 1. Figure 1: A table depicting the state of the art, and our contributions for [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. This manuscript investigates the Subspace Orbit Problem, which generalizes the classical Orbit Problem by replacing a single target point with a target subspace. The central claims are that the problem is decidable when the target subspace has dimension logarithmic in the ambient dimension n, and that over the rationals this case admits an NP^RP algorithm. The authors further prove that the variant in which the target subspace has linear dimension in n is as hard as the Skolem Problem for linear recurrence sequences.

Significance. If the results hold, the work meaningfully advances the decidability landscape for orbit problems by identifying a non-trivial regime (logarithmic target dimension) where decidability and a concrete complexity bound can be established, while tightly linking the linear-dimension case to the long-open Skolem problem. The reduction techniques via enumeration of bases and effective Diophantine approximation, together with the nondeterministic certificate plus RP oracle for the complexity bound, constitute useful technical contributions that may apply to related matrix-semigroup and linear-algebraic decision problems.

major comments (2)
  1. [Abstract] Abstract and Section 1: the decidability claim for target subspaces of dimension O(log n) rests on an enumeration of candidate bases followed by a reduction to effective Diophantine approximation or matrix-semigroup problems; the manuscript must explicitly treat edge cases such as characteristic polynomials with repeated roots and base-field extensions, as these are load-bearing for confirming that the algorithm remains effective without post-hoc restrictions.
  2. [Section 1] Section 1 (hardness reduction): the embedding of a linear recurrence sequence into a subspace whose dimension is proportional to n is the key step establishing Skolem-hardness for the linear-dimension case; the reduction must be shown to preserve the Skolem instance exactly, without introducing extra assumptions on matrix entries or the underlying field.
minor comments (2)
  1. Standardize notation for ambient dimension and target-subspace dimension throughout; inconsistent use of n versus other symbols can obscure the logarithmic versus linear distinction.
  2. [Abstract] Abstract: consider stating the base of the logarithm explicitly when describing the dimension restriction, to aid precise complexity comparisons.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive review. The comments identify areas where additional explicit discussion would improve the manuscript's rigor. We address each major comment below and will revise the paper to incorporate the requested clarifications.

read point-by-point responses

  1. Referee: [Abstract] Abstract and Section 1: the decidability claim for target subspaces of dimension O(log n) rests on an enumeration of candidate bases followed by a reduction to effective Diophantine approximation or matrix-semigroup problems; the manuscript must explicitly treat edge cases such as characteristic polynomials with repeated roots and base-field extensions, as these are load-bearing for confirming that the algorithm remains effective without post-hoc restrictions.

    Authors: We agree that these edge cases require explicit treatment to fully substantiate the claims. The enumeration of bases proceeds via the rational canonical form, which handles repeated roots by working with the minimal polynomial and invariant factors rather than assuming distinct roots; the subsequent Diophantine approximation step then applies to the resulting linear forms in logarithms with the same effective bounds. For base-field extensions, the algorithm is formulated over the algebraic closure but reduces to computations in a finite extension of the rationals, where standard effective results on linear forms in logarithms continue to hold. In the revised manuscript we will insert a short subsection (or appendix paragraph) that walks through these cases explicitly, confirming that no post-hoc restrictions are needed. This is a presentational clarification; the core decidability and complexity results remain unchanged. revision: yes

  2. Referee: [Section 1] Section 1 (hardness reduction): the embedding of a linear recurrence sequence into a subspace whose dimension is proportional to n is the key step establishing Skolem-hardness for the linear-dimension case; the reduction must be shown to preserve the Skolem instance exactly, without introducing extra assumptions on matrix entries or the underlying field.

    Authors: The reduction is constructed to be faithful. Given an LRS with rational coefficients, we embed it into a block-companion matrix acting on a vector space whose basis vectors encode the initial state and successive shifts; the target subspace is the span of these basis vectors (dimension linear in the order of the recurrence). Intersection of the orbit with this subspace occurs if and only if the original Skolem instance has a positive integer solution. All matrix entries remain in the same base field (Q or Z) as the input instance, and no auxiliary assumptions are imposed. We will revise Section 1 to include an explicit lemma stating the equivalence together with a short verification that the construction introduces neither field extensions nor extra constraints on the entries. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper establishes new decidability and complexity results for the Subspace Orbit Problem restricted to target subspaces of dimension O(log n), via explicit algorithmic reductions to effective Diophantine approximation and matrix semigroup problems, together with a direct embedding hardness reduction from the Skolem Problem for the linear-dimension case. These steps rely on prior independent results by other authors (Kannan-Lipton, Chonev et al.) and on standard effective techniques in the logarithmic regime; no self-definitional equations, fitted inputs renamed as predictions, or load-bearing self-citations appear in the derivation chain. The central claims therefore remain self-contained and externally falsifiable.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper rests on standard facts from linear algebra over the rationals and complexity theory; no free parameters, ad-hoc axioms, or invented entities are introduced in the abstract.

axioms (1)
  • standard math Linear algebra and matrix iteration over the rationals behave as in standard undergraduate linear algebra.
    Invoked implicitly when discussing orbits and subspaces.

pith-pipeline@v0.9.0 · 5715 in / 1210 out tokens · 48267 ms · 2026-05-21T15:22:17.632726+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

42 extracted references · 42 canonical work pages · 1 internal anchor

  1. [1]

    Akshay, Nikhil Balaji, Aniket Murhekar, Rohith Varma, and Nikhil Vyas

    S. Akshay, Nikhil Balaji, Aniket Murhekar, Rohith Varma, and Nikhil Vyas. 2020. Near-Optimal Complexity Bounds for Fragments of the Skolem Problem. In37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 154), Christophe Paul and Markus Bläser (Eds.). Schloss D...

    work page doi:10.4230/lipics.stacs.2020.37 2020

  2. [2]

    Shaull Almagor, Toghrul Karimov, Edon Kelmendi, Joël Ouaknine, and James Worrell. 2021. Deciding𝜔-regular properties on linear recurrence sequences.Proc. ACM Program. Lang.5, POPL, Article 48 (Jan. 2021), 24 pages. doi:10.1145/3434329

    work page doi:10.1145/3434329 2021

  3. [3]

    Shaull Almagor, Joël Ouaknine, and James Worrell. 2019. The Semialgebraic Orbit Problem. In36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 126), Rolf Niedermeier and Christophe Paul (Eds.). Schloss Dagstuhl – Leibniz- Zentrum für Informatik, Dagstuhl, Ger...

    work page doi:10.4230/lipics.stacs 2019

  4. [4]

    Piotr Bacik. 2025. Completing the Picture for the Skolem Problem on Order- 4 Linear Recurrence Sequences.TheoretiCS4 (2025), 11 pages. doi:10.46298/ theoretics.25.28

    work page 2025

  5. [5]

    Piotr Bacik, Joël Ouaknine, David Purser, and James Worrell. 2025. On the p-adic Skolem Problem. doi:10.48550/arXiv.2504.14413 arXiv:2504.14413

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2504.14413 2025

  6. [6]

    Piotr Bacik, Joël Ouaknine, and James Worrell. 2026. On the Complexity of the Skolem Problem at Low Orders. InProceedings of the 2026 Annual ACM-SIAM Sym- posium on Discrete Algorithms (SODA). 5255–5269. doi:10.1137/1.9781611978971. 191

    work page doi:10.1137/1.9781611978971 2026

  7. [7]

    Whiteland, and James Worrell

    Christel Baier, Florian Funke, Simon Jantsch, Toghrul Karimov, Engel Lefaucheux, Florian Luca, Joël Ouaknine, David Purser, Markus A. Whiteland, and James Worrell. 2021. The Orbit Problem for Parametric Linear Dynamical Systems. In 32nd International Conference on Concurrency Theory (CONCUR 2021) (Leibniz International Proceedings in Informatics (LIPIcs),...

    work page doi:10.4230/lipics.concur.2021.28 2021

  8. [8]

    Beukers and R

    F. Beukers and R. Tijdeman. 1984. On the multiplicities of binary complex recurrences.Compositio Mathematica51, 2 (1984), 193–213. http://eudml.org/ doc/89641

    work page 1984

  9. [9]

    Yuri Bilu. 2025. Skolem Problem for Linear Recurrence Sequences with 4 Dominant Roots (after Mignotte, Shorey, Tijdeman, Vereshchagin and Bacik). doi:10.48550/arXiv.2501.16290 arXiv:2501.16290

    work page doi:10.48550/arxiv.2501.16290 2025

  10. [10]

    Yuri Bilu, Florian Luca, Joris Nieuwveld, Joël Ouaknine, David Purser, and James Worrell. 2022. Skolem Meets Schanuel. In47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 241). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 20:1–2...

    work page doi:10.4230/lipics.mfcs.2022.20 2022

  11. [11]

    Bombieri and J

    E. Bombieri and J. Vaaler. 1983. On Siegel’s Lemma.Inventiones mathematicae73 (1983), 11–32. http://eudml.org/doc/143033

    work page 1983

  12. [12]

    Ventsislav Chonev, Joël Ouaknine, and James Worrell. 2013. The orbit problem in higher dimensions. InProceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing(Palo Alto, California, USA)(STOC ’13). Association for Computing Machinery, New York, NY, USA, 941–950. doi:10.1145/2488608. 2488728

    work page doi:10.1145/2488608 2013

  13. [13]

    Ventsislav Chonev, Joël Ouaknine, and James Worrell. 2015. The Polyhedron- Hitting Problem.Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms2015 (07 2015), 940–956

    work page 2015

  14. [14]

    Ventsislav Chonev, Joël Ouaknine, and James Worrell. 2016. On the Complexity of the Orbit Problem.J. ACM63, 3 (2016), 23:1–23:18

    work page 2016

  15. [15]

    Julian D’Costa, Toghrul Karimov, Rupak Majumdar, Joël Ouaknine, Mahmoud Salamati, Sadegh Soudjani, and James Worrell. 2021. The Pseudo-Skolem Problem is Decidable. In46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 202), Filippo Bonchi and Simon J. Pug...

    work page 2021

  16. [16]

    Julian D’Costa, Toghrul Karimov, Rupak Majumdar, Joël Ouaknine, Mahmoud Salamati, and James Worrell. 2022. The Pseudo-Reachability Problem for Di- agonalisable Linear Dynamical Systems. In47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 40:1–40:1...

    work page 2022

  17. [17]

    Art¯uras Dubickas. 1998. On algebraic numbers close to 1.Bulletin of the Australian Mathematical Society58, 3 (1998), 423–434. doi:10.1017/S0004972700032408

    work page doi:10.1017/s0004972700032408 1998

  18. [18]

    Harrison

    Michael A. Harrison. 1969.Lectures on Linear Sequential Machines. Academic Press, Inc., USA

    work page 1969

  19. [19]

    Ravindran Kannan and Richard J. Lipton. 1980. The orbit problem is decidable. InProceedings of the twelfth annual ACM symposium on Theory of computing - STOC ’80. ACM Press, Los Angeles, California, United States, 252–261. doi:10. 1145/800141.804673

    work page arXiv 1980

  20. [20]

    Kannan and R

    R. Kannan and R. J. Lipton. 1986. Polynomial-Time Algorithm for the Orbit Problem.J. ACM33, 4 (Aug. 1986), 808–821. doi:10.1145/6490.6496

    work page doi:10.1145/6490.6496 1986

  21. [21]

    2023.Algorithmic verification of linear dynamical systems

    Toghrul Karimov. 2023.Algorithmic verification of linear dynamical systems. Ph. D. Dissertation. Saarländische Universitäts- und Landesbibliothek. doi:10.22028/ D291-41630

    work page 2023

  22. [22]

    2022.What’s Decidable About Discrete Linear Dynamical Systems?Springer Nature Switzerland, Cham, 21–38

    Toghrul Karimov, Edon Kelmendi, Joël Ouaknine, and James Worrell. 2022.What’s Decidable About Discrete Linear Dynamical Systems?Springer Nature Switzerland, Cham, 21–38. doi:10.1007/978-3-031-22337-2_2

    work page doi:10.1007/978-3-031-22337-2_2 2022

  23. [23]

    Toghrul Karimov, Edon Kelmendi, Joël Ouaknine, and James Worrell. 2025. Mul- tiple Reachability in Linear Dynamical Systems. In2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). 651–663. doi:10.1109/LICS65433. 2025.00055

    work page doi:10.1109/lics65433 2025

  24. [24]

    Whiteland, and James Worrell

    Toghrul Karimov, Engel Lefaucheux, Joël Ouaknine, David Purser, Anton Varonka, Markus A. Whiteland, and James Worrell. 2022. What’s decidable about linear loops?Proc. ACM Program. Lang.6, POPL, Article 65 (Jan. 2022), 25 pages. doi:10.1145/3498727

    work page doi:10.1145/3498727 2022

  25. [25]

    Toghrul Karimov, Joël Ouaknine, and James Worrell. 2020. On LTL Model Check- ing for Low-Dimensional Discrete Linear Dynamical Systems. In45th Interna- tional Symposium on Mathematical Foundations of Computer Science (MFCS 2020) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 170), Javier Esparza and Daniel Král’ (Eds.). Schloss Dagstuhl ...

    work page doi:10.4230/lipics.mfcs.2020.54 2020

  26. [26]

    A.N. Krylov. 1931. On the numerical solution of the equation which determines the frequencies of small vibrations of material systems for technical questions (In Russian).Bulletin of the Academy of Sciences of the USSR4 (1931), 491–539

    work page 1931

  27. [27]

    Christer Lech. 1953. A note on recurring series.Arkiv för Matematik2, 5 (8 1953), 417–421. doi:10.1007/BF02590997

    work page doi:10.1007/bf02590997 1953

  28. [28]

    Richard Lipton, Florian Luca, Joris Nieuwveld, Joël Ouaknine, David Purser, and James Worrell. 2022. On the Skolem Problem and the Skolem Conjecture. In Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science (Haifa, Israel)(LICS ’22). Association for Computing Machinery, New York, NY, USA, Article 5, 9 pages. doi:10.1145/3531130.3533328

    work page doi:10.1145/3531130.3533328 2022

  29. [29]

    Kurt Mahler. 1935. Eine arithmetische Eigenschaft der Taylor-Koeffizienten rationaler Funktionen.Proc. Akad. Wet. Amsterdam38 (1935), 50–60

    work page 1935

  30. [30]

    E M Matveev. 2000. An explicit lower bound for a homogeneous rational linear form in the logarithms of algebraic numbers. II.Izvestiya: Mathematics64, 6 (Dec. 2000), 1217–1269. doi:10.1070/IM2000v064n06ABEH000314

    work page doi:10.1070/im2000v064n06abeh000314 2000

  31. [31]

    Carl D. Meyer. 2023.Matrix analysis and applied linear algebra(second edition ed.). Number 189 in Other titles in applied mathematics. Siam, Society for Industrial and Applied Mathematics, Philadelphia, PA

    work page 2023

  32. [32]

    Mignotte and M

    M. Mignotte and M. Waldschmidt. 1994. On Algebraic Numbers of Small Height: Linear Forms in One Logarithm.Journal of Number Theory47, 1 (1994), 43–62. doi:10.1006/jnth.1994.1025

    work page doi:10.1006/jnth.1994.1025 1994

  33. [33]

    23 Alain Robert.A course in p-adic analysis

    Jürgen Neukirch. 1999.Algebraic Number Theory. Grundlehren der mathematis- chen Wissenschaften, Vol. 322. Springer Berlin Heidelberg, Berlin, Heidelberg. doi:10.1007/978-3-662-03983-0 13 Mystery’26, One Day, In Mystery Town Piotr Bacik and Anton Varonka

    work page doi:10.1007/978-3-662-03983-0 1999

  34. [34]

    Joël Ouaknine and James Worrell. 2015. On linear recurrence sequences and loop termination.ACM SIGLOG News2, 2 (April 2015), 4–13. doi:10.1145/2766189. 2766191

    work page doi:10.1145/2766189 2015

  35. [35]

    Arnold Schönhage. 1979. On the power of random access machines. InAu- tomata, Languages and Programming, Hermann A. Maurer (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 520–529

    work page 1979

  36. [36]

    Thoralf Skolem. 1935. Ein Verfahren zur Behandlung gewisser exponentialer Gleichungen und diophantischer Gleichungen. 8. Skand. Mat.-Kongr., 163-188 (1935)

    work page 1935

  37. [37]

    Tijdeman, M

    R. Tijdeman, M. Mignotte, and T.N. Shorey. 1984. The distance between terms of an algebraic recurrence sequence.Journal für die reine und angewandte Mathe- matik349 (1984), 63–76. http://eudml.org/doc/152622

    work page 1984

  38. [38]

    Trefethen and David Bau

    Lloyd N. Trefethen and David Bau. 1997.Numerical Linear Algebra. SIAM, Philadelphia, PA

    work page 1997

  39. [39]

    Vereshchagin

    N.K. Vereshchagin. 1985. Occurrence of zero in a linear recursive sequence. Mathematical notes of the Academy of Sciences of the USSR38 (1985), 609–615. https://link.springer.com/article/10.1007/BF01156238

    work page doi:10.1007/bf01156238 1985

  40. [40]

    Paul Voutier. 1996. An effective lower bound for the height of algebraic numbers. Acta Arithmetica74, 1 (1996), 81–95. doi:10.4064/aa-74-1-81-95

    work page doi:10.4064/aa-74-1-81-95 1996

  41. [41]

    2000.Diophantine Approximation on Linear Algebraic Groups

    Michel Waldschmidt. 2000.Diophantine Approximation on Linear Algebraic Groups. Grundlehren der mathematischen Wissenschaften, Vol. 326. Springer Berlin Heidelberg, Berlin, Heidelberg. doi:10.1007/978-3-662-11569-5

    work page doi:10.1007/978-3-662-11569-5 2000

  42. [42]

    Kunrui Yu. 1999. p-adic logarithmic forms and group varieties II.Acta Arithmetica 89, 4 (1999), 337–378. doi:10.4064/aa-89-4-337-378 14 On the Subspace Orbit Problem and the Simultaneous Skolem Problem Mystery’26, One Day, In Mystery Town A Missing Proofs A.1 Bound on height of determinant Lemma 5.7.For a matrix 𝐴=(𝑎 𝑖 𝑗)1≤𝑖,𝑗≤𝑚 ∈K 𝑚×𝑚 over a number field...

    work page doi:10.4064/aa-89-4-337-378 1999