Subgroup membership in \(\mathrm{GL}(2, \mathrm{Z})\) (Q6614621)

Let \(G\) be a group. The subgroup membership problem (or generalized word problem) for \(G\) asks whether for given group elements \(x,g_{1},\ldots ,g_{k} \in G\), \(x\) belongs to the subgroup \(\langle g_{1},\ldots ,g_{k} \rangle\). If \(G\) is finitely generated, the elements of \(G\) can be encoded by finite words over a finite set of generators.\N\NFor a finitely generated free group, the subgroup membership problem can be solved using Nielsen reduction; a polynomial time algorithm was found by \textit{J. Avenhaus} and \textit{K. Madlener} in [Theor. Comput. Sci. 32, 61--76 (1984; Zbl 0555.20015)], where it is also shown that this problem is \textsf{P}-complete.\N\NIn the paper under review the author proves that the subgroup membership problem for a virtually free group can be decided in polynomial time when all group elements are represented by so-called power words, that is, words of the form \(w_{1}^{z_{1}}w_{2}^{z_{2}} \ldots w_{k}^{z_{k}}\), where the \(w_{i}\) are explicit words over a generating set and the \(z_{i}\) are binary-encoded integers. As a corollary, it follows that the subgroup membership problem for the matrix group \(\mathrm{GL}(2,\mathbb{Z})\) can be decided in polynomial time when elements of \(\mathrm{GL}(2,\mathbb{Z})\) are represented by matrices with binary-encoded integers. For the same input, the author also proves that it is possible to compute in polynomial time the index of a finitely generated subgroup of \(\mathrm{GL}(2,\mathbb{Z})\).