On Primitive Words I: A New Algorithm

Abstract

Let $F_k$ be the free group on $k$ generators, and let $H\le J\le \F_k$ be subgroups of finite rank. We present a new elementary algorithm to determine whether $H$ is a free factor of $J$. In particular, this algorithm can determine whether a given element $w\in F_k$ is primitive, i.e. whether it belongs to some basis of $F_k$.

arXiv commentThis paper was unified with "On Primitive Words II: Measure Preservation" (arXiv:1104.3991), under the new title "Primitive Words, Free Factors and Measure Preservation"