Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 32 min ago
PreprintarXiv licencearXiv

Decidability of the Orbit Problem Over ℚ(X)

  • Joshua Holden
  • Alexa Renner
Open at sourcePDFDOICite

Abstract

The orbit problem is the problem of whether, given x, y∈ ℚn and an n× n matrix A, there exists an i∈ℕ such that Aix = y. In 1980, Kannan and Lipton proved that the orbit problem is decidable. We show that a generalization of the orbit problem, where the field is ℚ(X) for X a countable set of transcendentals, is also decidable. We define the orbit power problem for an arbitrary group G to be the problem of when, given x, y∈ G, there exists an n∈ℤ such that xn = y. We then use the main result to show that the power orbit problem is decidable for an assortment of groups, including the braid groups and Aut(F2).

Related

  1. Higher limits over the fusion orbit category via subgroup complexes
    Ergun Yalcin
    arXivPreprintarXiv licenceFull textGeometry & topologyarXiv
  2. Hyperbolic Completion of Newton's Off-Center Orbit Problem: Constant-Curvature Rigidity, SO(2,1) Symmetry, and Magnetic Uniqueness
    Dipesh Bhandari
    arXivPreprintCC BY 4.0Full textMathematical physicsarXiv
  3. SpaceDiffusion: Over-the-Orbit Diffusion for Space Generate-and-Forward Communications
    Jianhao Huang, Zhanwei Wang, Khaled B. Letaief +1
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv
  4. Markovian renormalisation for percolation in high-dimension: Semi-decidability of mean field behavior
    Arthur Blanc-Renaudie
    HALPreprintarXiv licenceFull textMathematical physicsProbabilityHALarXiv
  5. On the sample complexity of the generalized hidden shift problem over arbitrary finite groups
    Juntai Zhou
    arXivPreprintarXiv licenceFull textAlgebra & number theoryQuantum physics & quantum informationarXiv

Cite

BibTeXRIS
BibTeX
@misc{holden2026decidability,
  title = {{Decidability of the Orbit Problem Over $\mathbbQ(X)$}},
  author = {Joshua Holden and Alexa Renner},
  howpublished = {arXiv},
  year = {2026},
  month = aug,
  doi = {10.48550/arxiv.2608.29440},
  eprint = {2608.29440},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.29440},
}
RIS
TY  - UNPB
TI  - Decidability of the Orbit Problem Over ℚ(X)
AU  - Joshua Holden
AU  - Alexa Renner
PY  - 2026
DA  - 2026/08/29
PB  - arXiv
DO  - 10.48550/arxiv.2608.29440
UR  - https://arxiv.org/abs/2608.29440
AB  - The orbit problem is the problem of whether, given x, y∈ ℚ^n and an n× n matrix A, there exists an i∈ℕ such that A^ix = y. In 1980, Kannan and Lipton proved that the orbit problem is decidable. We show that a generalization of the orbit problem, where the field is ℚ(X) for X a countable set of transcendentals, is also decidable. We define the orbit power problem for an arbitrary group G to be the problem of when, given x, y∈ G, there exists an n∈ℤ such that x^n = y. We then use the main result to show that the power orbit problem is decidable for an assortment of groups, including the braid groups and Aut(F_2).
ER  -