Quantifying orbit detection: \(\varphi\)-order and \(\varphi\)-spectrum (Q6639808)

Let \(G\) be a group and \(\varphi \in \mathrm{End}(G)\). \textit{P. Brinkmann} [J. Algebra 324, No. 5, 1083--1097 (2010; Zbl 1209.20023)] posed the problem of deciding, on input \(x, y \in G\) and \(\varphi\), whether there exists \(n\in \mathbb{N}\) such that \(x\varphi^{n}=y\) such a problem was named the orbit detection problem on \(G\) or, briefly, \(\mathrm{ODP}(G)\). The generalized orbit detection problem on \(G\), \(\mathrm{GODP}(G)\), consists of deciding, given \(x\in G\), \(K\subseteq G\) and \(\varphi\), whether there is some \(n\in \mathbb{N}\) such that \(x\varphi^{n}\in K\) or not.\N\NLet \(G\varphi^{\infty}=\bigcap_{i=1}^{\infty} \varphi^{i}(G)\) be the stable image of \(\varphi\). The main result in the paper under review is Theorem 3.1: There exists an algorithm with input a finitely generated virtually free group \(G\) and an endomorphism \(\varphi\) of \(G\) and output a finite set of generators for \(G\varphi^{\infty}\). As consequences of this result the author proves Theorem 4.6: There exists an algorithm with input a finitely generated virtually free group \(G\), an endomorphism \(\varphi\) of \(G\) and a finite set \(K =\{ g_{1}, \ldots ,g_{k} \}\subseteq G\) and output \(\varphi\)-\(\mathrm{sp}(K)\).