2
$\begingroup$

Is the following algorithmic problem known to be decidable/undecidable?

Input: an element $\mathbf{v} \in \mathbb{Z}^n$, a matrix $\mathbf{A} \in GL_n(\mathbb{Z})$, and a subgroup $H \leqslant \mathbb{Z}^n$.

Decide: whether there exists an integer $k>0$ such that \begin{equation} \mathbf{v} \left( \sum_{i=0}^{k} \mathbf{A}^i \right) \in H \, . \end{equation}

Notes: In 1986, Kannan and Lipton [1] proved the standard orbit problem for $\mathbb{Z}^n$. However, the methods applied there seem to be based in bounding properties which are not obviously applicable in our case.

[1] Kannan, Lipton - ``Polynomial-time algorithm for the orbit problem'', J. ACM 33 (1986), no. 4, 808–821.

$\endgroup$

0

You must log in to answer this question.