An algorithm to recognize echelon subgroups of a free group (Q6573213)

Let \(F_{n}\) be the free group of rank \(n\) and let \(\varphi: F_{n} \rightarrow F_{n}\) be an automorphism. \textit{S. M. Gersten} [Adv. Math. 64, 51--85 (1987; Zbl 0616.20014)] showed that \(\mathrm{Fix}(\varphi)\) is finitely generated, subsequently \textit{M. Bestvina} and \textit{M. Handel} [Ann. Math. (2) 135, No. 1, 1--51 (1992; Zbl 0757.57004)] proved that \(\operatorname{rank}(\mathrm{Fix}(\varphi)) \leq n\). It turns out that fixed-point subgroups behave in a very controlled manner with respect to intersections. A subgroup \(H \leq F_{n}\) is called echelon if there is a basis \(b_{1}, \ldots , b_{n}\) for \(F_{n}\) such that\N\[\N\operatorname{rank}(H \cap \langle b_{1}, \ldots, b_{i} \rangle) \leq \operatorname{rank}(H \cap \langle b_{1}, \ldots, b_{i-1} \rangle)+1 \text{ for } i=1, \ldots, n.\N\]\NFrom the normal form of \textit{A. Martino} and \textit{E. Ventura} [Topology 43, No. 5, 1133--1164 (2004; Zbl 1056.20017)] it follows that \(\mathrm{Fix}(\varphi)\) is echelon in \(F_{n}\).\N\NIn the paper under review, the author provides an algorithm that, given a finite set of generators for a subgroup \(H\) of a free group \(F_{n}\), determines whether \(H\) is echelon or not and, in case of affirmative answer, also computes a basis with respect to which \(H\) is in echelon form. He also proves, by means of a counterexample, that the intersection of two echelon subgroups needs not to be echelon. These results provide an answer to two questions posed by \textit{A. Rosenmann} [Groups Complex. Cryptol. 5, No. 2, 211--221 (2013; Zbl 1298.20032)].