Eventually fixed points of endomorphisms of virtually free groups (Q6630661)

Let \(G\) be a group, \(\operatorname{End}(G)\) be the set of all endomorphisms of the group \(G\) and \(\varphi\in\operatorname{End}(G)\). A point \(x\in G\) is said to be a fixed point if \(x\varphi=x\). The set of all fixed points forms a subgroup denoted by \(\operatorname{Fix}(\varphi)\). \N\N\textit{M. Bestvina} and \textit{M. Handel} [Ann. Math. (2) 135, No. 1, 1--51 (1992; Zbl 0757.57004)] proved using their theory of train tracks, that if \(\varphi\) is an automorphism of a free group \(F_n\), then \(\operatorname{Fix}(\varphi)\) has rank at most \(n\). (This statement had long been known as the Scott conjecture.) Around the same time, \textit{W. Imrich} and \textit{E. C. Turner} [Math. Proc. Camb. Philos. Soc. 105, No. 3, 421--422 (1989; Zbl 0675.20024)] showed that this holds for general endomorphisms by reducing the problem to the case of automorphisms. The problem of computing a basis for \(\operatorname{Fix}(\varphi)\) has a long and challenging history and was finally settled by \textit{O. Bogopolski} and \textit{O. Maslakova} [Int. J. Algebra Comput. 26, No. 1, 29--67 (2016; Zbl 1348.20030)] for automorphisms and by \textit{J. P. Mutanguha} [``Constructing stable images'', Preprint, \url{https://mutanguha.com/pdfs/relimmalgo.pdf}] for general endomorphisms of a free group.\N\NIn the paper under review, the author provides an algorithm to compute a finite generating set for the subgroup \(\operatorname{Fix}(\varphi)\) of an endomorphism \(\varphi\) of a finitely generated virtually free group (Theorem 3.2). A group is virtually free if it has a free subgroup of finite index.\N\NIn addition, the author proves that for a given finitely generated virtually free group \(G\) there exists a computable constant \(k\) such that if \(\varphi\in\operatorname{End}(G)\), \(x\in G\) and the orbit \(\operatorname{Orb}_\varphi(x)=\{x\varphi^k\mid k\in\mathbb{N}\}\) is finite, then \(|\operatorname{Orb}_\varphi(x)|<k\).\N\NThese results enable the author to solve several algorithmic problems for finitely generated virtually free groups. For example, the author proves the existence of algorithms which, given a finitely generated virtually free group \(G\) and an endomorphism \(\varphi\) of \(G\), allow deciding if \(\varphi\) is a finite order element of \(\operatorname{End}(G)\); determining if \(\varphi\) is aperiodic; checking if \(\operatorname{EvFix}(\varphi)\) is finitely generated and, in case the answer is affirmative, computing a finite set of generators; and verifying if \(\operatorname{EvFix}(\varphi)\) is a normal subgroup.\N\NAn endomorphism \(\varphi\) of \(G\) is aperiodic if \(\varphi^n=\varphi^{n+1}\) for some \(n>0\) and \(\varphi\) has finite order if there are distinct \(p,q\in\mathbb{N}\) such that \(\varphi^p=\varphi^q\). A point \(x\in G\) is eventually fixed if there is some \(m\in\mathbb{N}\) such that \(x\varphi^m\in\operatorname{Fix}(\varphi)\) or, equivalently, such that \(x\varphi^m=x\varphi^{m+1}\). The set of all eventually fixed points of \(\varphi\) is denoted by \(\operatorname{EvFix}(\varphi)\).