Dependence over subgroups of free groups

Abstract

Given a finitely generated subgroup $H$ of a free group $F$, we present an algorithm which computes $g_1,\dots ,g_m\in F$, such that the set of elements $g\in F$, for which there exists a non-trivial $H$-equation having $g$ as a solution, is, precisely, the disjoint union of the double cosets $H\bigsqcup H{g}_{1}H\bigsqcup \cdots \bigsqcup H{g}_{m}H$. Moreover, we present an algorithm which, given a finitely generated subgroup $H⩽F$ and an element $g\in F$, computes a finite set of elements of $H\ast ⟨x⟩$ that generate (as a normal subgroup) the ``ideal" $I_H(g)⊴H\ast ⟨x⟩$ of all ``polynomials" $w(x)$, such that $w(g)=1$. The algorithms, as well as the proofs, are based on the graph-theory techniques introduced by Stallings and on the more classical combinatorial techniques of Nielsen transformations. The key notion here is that of dependence of an element $g\in F$ on a subgroup $H$. We also study the corresponding notions of dependence sequence and dependence closure of a subgroup.